From 4f670845ff9ab6c48bcb5f7bf4d4ef6dc3c3064b Mon Sep 17 00:00:00 2001 From: manuel Date: Tue, 27 Mar 2012 11:51:08 +0200 Subject: reorganize file structure to match the upstream requirements --- notes/2.txt | 164 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 164 insertions(+) create mode 100644 notes/2.txt (limited to 'notes/2.txt') diff --git a/notes/2.txt b/notes/2.txt new file mode 100644 index 0000000..c81b980 --- /dev/null +++ b/notes/2.txt @@ -0,0 +1,164 @@ +Projekt 1 - Threads +=================== + +alarm clock +----------- +The simplest strategy is to maintain a wait list for +all threads blocked for sleep. + + * In 'timer_interrupt', check for threads which can be + unblocked from sleeping + * In 'sleep', set sleep timeout in thread, block the + thread and put it on the sleep list + +Notes: + + * There are three places where a thread is added to the + ready list: + - thread_init + - thread_yield + - thread_unblock + * Iterate list with removal: + for (e = list_begin (&list); e != list_end (&list); ) + if(...) + e = list_remove(e)->prev; + /* Unblock must be called AFTER removing, as thread.elem is reused */ + else + e = list_next(e); + +Stats: + + pintos/src/devices/timer.c | 40 ++++++++++++++++++++++++++++++++++++++-- + pintos/src/threads/thread.h | 3 +++ + 2 files changed, 41 insertions(+), 2 deletions(-) + + Design & Implementation time: 4 hours + +Priority Scheduler +------------------ + +A simple implementation of the priority scheduler (64 priority levels, round robin within +one priority group). + + * If a new task arrives with a higher priority, switch to this group + * If the currently active group is empty, search for the group with the next highest priority + +Notes: + + * thread_{init,unblock,yield} now call thread_ready, which updates the lowest ready priority + * The thread_unblock operation does not yield a new thread immediately. Therefore, we need to check + later whether we need to switch to a higher priority thread (via thread_yield). + As thread_unblock is called with interrupts off, it seemed best to perform + this check when interrupts are enabled. This is only necessary if a higher priority task + is ready. + * First attempt passed alarm-priority, but failed to pass the priority-preempt test. + But the debugging facilities are fantastic, so it was easy to spot the problem + * Wolfgang suggested to yield a software interrupt when unblocking instead of modifying + interrupt_enable. + +Stats: + + pintos/src/threads/interrupt.c | 3 +- + pintos/src/threads/thread.c | 60 ++++++++++++++++++++++++++++++++-------- + pintos/src/threads/thread.h | 1 + + 3 files changed, 51 insertions(+), 13 deletions(-) + + Design and implementation time: 3 hours + +Priority Locks +-------------- + +We also need to select higher priority task first from locks, semaphores and condition variables. +This easiest implementation searches for the thread with the highest priority in the wait queue. + +Notes: + + * It is sufficient to implement the priority based selection twice, for sema_up and + cond_signal. cond_signal is a little bit harder, as we need to store the priority + (or the waiting thread) in the semaphore_elem type + * There are some handy list utility functions; in this case, list_max does a fine job + for both sema_up and cond_signal + * It is difficult to implement this in an efficient (sublinear) way, because priority donation + may boost a thread at any time! + +Stats: + + pintos/src/threads/synch.c | 40 ++++++++++++++++++++++++++++++++++------ + 1 files changed, 34 insertions(+), 6 deletions(-) + + Design and Implementation time: 1 hour + +Priority Donation +----------------- +If a thread aquires a lock, the lock holder needs to be boosted to the donated priority. +We need to deal with nesting and chaining: + + * Lock/Thread correspondence: Each lock is associated with at most one thread that holds it. + Therefore, donated priority can be associated with a lock. + * If a thread t wants to obtain a lock L, and a thread with a lower priority holds it, + the thread holding the lock is boosted to the priority of the requesting thread + * Chaining: If the boosted thread is also blocked on a lock, than we also need to donate + the priority to that lock, in a transitive way. + * Nesting: If a thread may hold more than one lock, we need to keep track of the donation + to each lock. When a lock is released or the static priority changes, the highest priority + donated to other locks is assigned to the thread. + +With this information, the following rules seem suitable (without proof of correctness): + + * If thread T tries to aquire lock L + + ==> if(L.owner) + T.locked_on = L + donate_priority (L, T.priority) + end + donate_priority (L ,p) := + L.priority v= p + L.holder.priority v= p + donate_priority( L.holder.locked_on, p) + end + + * If a thread T aquires a lock L + + ==> L.holder = T + T.locks += L + T.lock_on = none + + + * If a thread T releases a lock L + + ==> L.holder = none + T.locks -= L + T.priority = max (T.locks.priority, static_priority) + +To implement this, each thread needs to maintain a list of locks, a static priority, +and a reference to the lock blocking it. + +Notes: + + * Difficult to design, really a challenge. + Literature (short paper) could be helpful. + Maybe it would be interesting to ask for correctness proof sketches? + + * First design was wrong, because I assumed locks are aquired in FIFO fashion + * First implementation failed to pass donate tests, due to a typo. Debugging + facilities are fantastic, no problem to spot this one. + * Next try, priority-donate-lower failed. Looking at the source code revealed that + we need to recompute the priority at the end of thread_set_priority. + * Next try, priority-donate-chain failed. Chaining is tricky to get right; + in my implementation, chained donations were lost after one lock was released. + + * It would be an interesting option to ask for new test cases from the students + * I think it would also be a cool task to write a test for a RMS scheduling + scenario with blocking. + +Stats: + + pintos/src/threads/synch.c | 15 ++++++++++++ + pintos/src/threads/synch.h | 6 +++- + pintos/src/threads/thread.c | 53 +++++++++++++++++++++++++++++++++++++++++- + pintos/src/threads/thread.h | 9 ++++++- + pintos/src/utils/pintos | 2 +- + + Design: 5h + Implementation: 3h + -- cgit v1.2.3