1 Index: src/threads/synch.c
2 ===================================================================
3 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v
4 retrieving revision 1.15
5 diff -u -p -u -r1.15 synch.c
6 --- src/threads/synch.c 31 Dec 2004 21:13:38 -0000 1.15
7 +++ src/threads/synch.c 31 Dec 2004 22:31:03 -0000
8 @@ -77,6 +77,18 @@ sema_down (struct semaphore *sema)
9 intr_set_level (old_level);
12 +/* Returns true if thread A has lower priority than thread B. */
14 +donated_lower_priority (const struct list_elem *a_,
15 + const struct list_elem *b_,
18 + const struct thread *a = list_entry (a_, struct thread, donor_elem);
19 + const struct thread *b = list_entry (b_, struct thread, donor_elem);
21 + return a->priority < b->priority;
24 /* Up or "V" operation on a semaphore. Increments SEMA's value
25 and wakes up one thread of those waiting for SEMA, if any.
27 @@ -89,10 +100,28 @@ sema_up (struct semaphore *sema)
28 ASSERT (sema != NULL);
30 old_level = intr_disable ();
31 - if (!list_empty (&sema->waiters))
32 - thread_unblock (list_entry (list_pop_front (&sema->waiters),
33 - struct thread, elem));
35 + if (!list_empty (&sema->waiters))
37 + /* Find highest-priority waiting thread. */
38 + struct thread *max = list_entry (list_max (&sema->waiters,
39 + donated_lower_priority, NULL),
40 + struct thread, elem);
42 + /* Remove `max' from wait list and unblock. */
43 + list_remove (&max->elem);
44 + thread_unblock (max);
46 + /* Yield to a higher-priority thread, if we're running in a
47 + context where it makes sense to do so.
49 + Kind of a funny interaction with donation here.
50 + We only support donation for locks, and locks turn off
51 + interrupts before calling us, so we automatically don't
52 + do the yield here, delegating to lock_release(). */
53 + if (!intr_context () && old_level == INTR_ON)
54 + thread_yield_to_higher_priority ();
56 intr_set_level (old_level);
59 @@ -184,6 +213,23 @@ lock_acquire (struct lock *lock)
60 ASSERT (!lock_held_by_current_thread (lock));
62 old_level = intr_disable ();
64 + if (lock->holder != NULL)
66 + /* Donate our priority to the thread holding the lock.
67 + First, update the data structures. */
68 + struct thread *donor = thread_current ();
69 + donor->want_lock = lock;
70 + donor->donee = lock->holder;
71 + list_push_back (&lock->holder->donors, &donor->donor_elem);
73 + /* Now implement the priority donation itself
74 + by recomputing the donee's priority
75 + and cascading the donation as far as necessary. */
76 + while (donor->donee != NULL && thread_recompute_priority (donor->donee))
77 + donor = donor->donee;
80 sema_down (&lock->semaphore);
81 lock->holder = thread_current ();
82 intr_set_level (old_level);
83 @@ -198,13 +244,38 @@ void
84 lock_release (struct lock *lock)
86 enum intr_level old_level;
87 + struct thread *t = thread_current ();
88 + struct list_elem *e;
90 ASSERT (lock != NULL);
91 ASSERT (lock_held_by_current_thread (lock));
93 old_level = intr_disable ();
95 + /* Remove donations from threads that want the lock we're
97 + for (e = list_begin (&t->donors); e != list_end (&t->donors); )
99 + struct thread *donor = list_entry (e, struct thread, donor_elem);
100 + if (donor->want_lock == lock)
102 + donor->donee = NULL;
103 + e = list_remove (e);
109 + /* Release lock. */
111 sema_up (&lock->semaphore);
113 + /* Recompute our priority based on our remaining donations,
114 + then yield to a higher-priority ready thread if one now
116 + thread_recompute_priority (t);
117 + thread_yield_to_higher_priority ();
119 intr_set_level (old_level);
122 Index: src/threads/thread.c
123 ===================================================================
124 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v
125 retrieving revision 1.48
126 diff -u -p -u -r1.48 thread.c
127 --- src/threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48
128 +++ src/threads/thread.c 31 Dec 2004 22:31:03 -0000
129 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
131 /* Add to run queue. */
133 + if (priority > thread_get_priority ())
138 @@ -186,6 +188,19 @@ thread_block (void)
142 +/* Returns true if A has higher priority than B,
143 + within a list of threads. */
145 +thread_higher_priority (const struct list_elem *a_,
146 + const struct list_elem *b_,
149 + const struct thread *a = list_entry (a_, struct thread, elem);
150 + const struct thread *b = list_entry (b_, struct thread, elem);
152 + return a->priority > b->priority;
155 /* Transitions a blocked thread T to the ready-to-run state.
156 This is an error if T is not blocked. (Use thread_yield() to
157 make the running thread ready.) */
158 @@ -198,7 +212,7 @@ thread_unblock (struct thread *t)
160 old_level = intr_disable ();
161 ASSERT (t->status == THREAD_BLOCKED);
162 - list_push_back (&ready_list, &t->elem);
163 + list_insert_ordered (&ready_list, &t->elem, thread_higher_priority, NULL);
164 t->status = THREAD_READY;
165 intr_set_level (old_level);
167 @@ -266,8 +280,8 @@ thread_yield (void)
168 ASSERT (!intr_context ());
170 old_level = intr_disable ();
171 - list_push_back (&ready_list, &cur->elem);
172 + list_insert_ordered (&ready_list, &cur->elem, thread_higher_priority, NULL);
173 cur->status = THREAD_READY;
175 intr_set_level (old_level);
177 @@ -274,19 +288,75 @@
181 -/* Sets the current thread's priority to NEW_PRIORITY. */
183 -thread_set_priority (int new_priority)
185 - thread_current ()->priority = new_priority;
188 -/* Returns the current thread's priority. */
190 -thread_get_priority (void)
192 - return thread_current ()->priority;
195 +/* Sets the current thread's priority to PRIORITY. */
197 +thread_set_priority (int priority)
199 + struct thread *t = thread_current ();
200 + enum intr_level old_level;
202 + t->normal_priority = priority;
204 + old_level = intr_disable ();
205 + while (thread_recompute_priority (t) && t->donee != NULL)
207 + thread_yield_to_higher_priority ();
208 + intr_set_level (old_level);
211 +/* Returns the current thread's priority. */
213 +thread_get_priority (void)
215 + return thread_current ()->priority;
218 +/* Returns true if thread A has lower priority than thread B,
219 + within a list of donors. */
221 +donated_lower_priority (const struct list_elem *a_,
222 + const struct list_elem *b_,
225 + const struct thread *a = list_entry (a_, struct thread, donor_elem);
226 + const struct thread *b = list_entry (b_, struct thread, donor_elem);
228 + return a->priority < b->priority;
231 +/* Recomputes T's priority in terms of its normal priority and
232 + its donors' priorities, if any.
233 + Returns true if T's new priority is higher than its old
234 + priority, false otherwise. */
236 +thread_recompute_priority (struct thread *t)
238 + int old = t->priority;
240 + if (!list_empty (&t->donors))
241 + donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL),
242 + struct thread, donor_elem)->priority;
243 + t->priority = donation > t->normal_priority ? donation : t->normal_priority;
244 + return t->priority > old;
247 +/* If the ready list contains a thread with a higher priority,
250 +thread_yield_to_higher_priority (void)
252 + enum intr_level old_level = intr_disable ();
253 + if (!list_empty (&ready_list))
255 + struct thread *cur = thread_current ();
256 + struct thread *max = list_entry (list_front (&ready_list),
257 + struct thread, elem);
258 + if (max->priority > cur->priority)
261 + intr_set_level (old_level);
264 /* Idle thread. Executes when no other thread is ready to run. */
266 @@ -335,8 +417,9 @@ init_thread (struct thread *t, const cha
267 t->status = THREAD_BLOCKED;
268 strlcpy (t->name, name, sizeof t->name);
269 t->stack = (uint8_t *) t + PGSIZE;
270 - t->priority = priority;
271 + t->priority = t->normal_priority = priority;
272 t->magic = THREAD_MAGIC;
273 + list_init (&t->donors);
276 /* Allocates a SIZE-byte frame at the top of thread T's stack and
277 Index: src/threads/thread.h
278 ===================================================================
279 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v
280 retrieving revision 1.28
281 diff -u -p -u -r1.28 thread.h
282 --- src/threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28
283 +++ src/threads/thread.h 31 Dec 2004 22:31:03 -0000
284 @@ -87,7 +87,14 @@ struct thread
285 enum thread_status status; /* Thread state. */
286 char name[16]; /* Name (for debugging purposes). */
287 uint8_t *stack; /* Saved stack pointer. */
288 - int priority; /* Priority. */
290 + /* Thread priority. */
291 + int priority; /* Priority, including donations. */
292 + int normal_priority; /* Priority, without donations. */
293 + struct list donors; /* Threads donating priority to us. */
294 + struct list_elem donor_elem; /* Element in donors list. */
295 + struct thread *donee; /* Thread we're donating to. */
296 + struct lock *want_lock; /* Lock we're waiting to acquire. */
298 /* Shared between thread.c and synch.c. */
299 struct list_elem elem; /* List element. */
300 @@ -118,6 +125,8 @@ const char *thread_name (void);
302 void thread_exit (void) NO_RETURN;
303 void thread_yield (void);
304 +void thread_yield_to_higher_priority (void);
305 +bool thread_recompute_priority (struct thread *);
307 void thread_set_priority (int);
308 int thread_get_priority (void);