2 ===================================================================
3 RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v
4 retrieving revision 1.14
5 diff -u -p -u -r1.14 synch.c
6 --- threads/synch.c 29 Sep 2004 01:04:09 -0000 1.14
7 +++ threads/synch.c 11 Oct 2004 07:29:34 -0000
8 @@ -89,10 +89,32 @@ sema_up (struct semaphore *sema)
11 old_level = intr_disable ();
12 - if (!list_empty (&sema->waiters))
13 - thread_unblock (list_entry (list_pop_front (&sema->waiters),
14 - struct thread, elem));
16 + if (!list_empty (&sema->waiters))
21 + max = list_entry (list_front (&sema->waiters), struct thread, elem);
22 + for (e = list_begin (&sema->waiters);
23 + e != list_end (&sema->waiters); e = list_next (e))
25 + struct thread *t = list_entry (e, struct thread, elem);
26 + if (t->priority > max->priority)
29 + list_remove (&max->elem);
30 + thread_unblock (max);
32 + /* Kind of a funny interaction with donation here.
33 + We only support donation for locks, and locks turn off
34 + interrupts before calling us, so we automatically don't
35 + do the yield here, delegating to lock_release(). */
36 + if (!intr_context ()
37 + && max->priority > thread_get_priority ()
38 + && old_level == INTR_ON)
41 intr_set_level (old_level);
44 @@ -166,6 +188,21 @@ lock_init (struct lock *lock, const char
45 sema_init (&lock->semaphore, 1, name);
49 +revise_priority (struct thread *t)
53 + t->priority = t->normal_priority;
54 + for (e = list_begin (&t->donors); e != list_end (&t->donors);
57 + struct thread *donor = list_entry (e, struct thread, donor_elem);
58 + if (donor->priority > t->priority)
59 + t->priority = donor->priority;
63 /* Acquires LOCK, sleeping until it becomes available if
64 necessary. The lock must not already be held by the current
66 @@ -184,6 +221,17 @@ lock_acquire (struct lock *lock)
67 ASSERT (!lock_held_by_current_thread (lock));
69 old_level = intr_disable ();
71 + if (lock->holder != NULL)
73 + struct thread *donor = thread_current ();
74 + donor->want_lock = lock;
75 + donor->donee = lock->holder;
76 + list_push_back (&lock->holder->donors, &donor->donor_elem);
77 + revise_priority (lock->holder);
78 + //recurse_donation (&lock->holder);
81 sema_down (&lock->semaphore);
82 lock->holder = thread_current ();
83 intr_set_level (old_level);
84 @@ -198,13 +246,32 @@ void
85 lock_release (struct lock *lock)
87 enum intr_level old_level;
88 + struct thread *t = thread_current ();
89 + list_elem *e, *next;
90 + bool did_donate = false;
92 ASSERT (lock != NULL);
93 ASSERT (lock_held_by_current_thread (lock));
95 old_level = intr_disable ();
96 + for (e = list_begin (&t->donors); e != list_end (&t->donors);
99 + struct thread *donor = list_entry (e, struct thread, donor_elem);
100 + next = list_next (e);
101 + if (donor->want_lock == lock)
103 + donor->donee = NULL;
108 + revise_priority (t);
111 sema_up (&lock->semaphore);
114 intr_set_level (old_level);
117 diff -u -p -u -p -r1.48 thread.c
118 --- threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48
119 +++ threads/thread.c 14 Oct 2004 05:21:08 -0000
120 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
122 /* Add to run queue. */
124 + if (priority > thread_get_priority ())
129 @@ -186,6 +188,16 @@ thread_block (void)
134 +thread_greater_priority (const list_elem *a_, const list_elem *b_,
137 + const struct thread *a = list_entry (a_, struct thread, elem);
138 + const struct thread *b = list_entry (b_, struct thread, elem);
140 + return a->priority > b->priority;
143 /* Transitions a blocked thread T to the ready-to-run state.
144 This is an error if T is not blocked. (Use thread_yield() to
145 make the running thread ready.) */
146 @@ -198,7 +210,7 @@ thread_unblock (struct thread *t)
148 old_level = intr_disable ();
149 ASSERT (t->status == THREAD_BLOCKED);
150 - list_push_back (&ready_list, &t->elem);
151 + list_insert_ordered (&ready_list, &t->elem, thread_greater_priority, NULL);
152 t->status = THREAD_READY;
153 intr_set_level (old_level);
155 @@ -266,11 +278,44 @@ thread_yield (void)
156 ASSERT (!intr_context ());
158 old_level = intr_disable ();
159 - list_push_back (&ready_list, &cur->elem);
160 + list_insert_ordered (&ready_list, &cur->elem, thread_greater_priority, NULL);
161 cur->status = THREAD_READY;
163 intr_set_level (old_level);
167 +thread_set_priority (int priority)
169 + struct thread *t = thread_current ();
170 + int old_priority, new_priority;
173 + old_priority = t->priority;
174 + new_priority = t->normal_priority = priority;
175 + for (e = list_begin (&t->donors); e != list_end (&t->donors);
178 + struct thread *donor = list_entry (e, struct thread, donor_elem);
179 + if (donor->priority > t->priority)
180 + new_priority = donor->priority;
183 + t->priority = new_priority;
185 + if (new_priority < old_priority)
187 + /* FIXME: if this is still (one of) the highest priority
188 + threads then don't yield. */
194 +thread_get_priority (void)
196 + return thread_current ()->priority;
199 /* Idle thread. Executes when no other thread is ready to run. */
201 @@ -335,8 +380,9 @@ init_thread (struct thread *t, const cha
202 t->status = THREAD_BLOCKED;
203 strlcpy (t->name, name, sizeof t->name);
204 t->stack = (uint8_t *) t + PGSIZE;
205 - t->priority = priority;
206 + t->priority = t->normal_priority = priority;
207 t->magic = THREAD_MAGIC;
208 + list_init (&t->donors);
211 /* Allocates a SIZE-byte frame at the top of thread T's stack and
212 Index: threads/thread.h
213 ===================================================================
214 RCS file: /u/blp/cvs/pintos/src/threads/thread.h,v
215 retrieving revision 1.28
216 diff -u -p -u -r1.28 thread.h
217 --- threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28
218 +++ threads/thread.h 11 Oct 2004 07:29:35 -0000
219 @@ -88,6 +88,13 @@ struct thread
220 char name[16]; /* Name (for debugging purposes). */
221 uint8_t *stack; /* Saved stack pointer. */
222 int priority; /* Priority. */
223 + int normal_priority; /* Priority. */
225 + /* Priority donation. */
226 + struct list donors;
227 + list_elem donor_elem;
228 + struct thread *donee;
229 + struct lock *want_lock;
231 /* Shared between thread.c and synch.c. */
232 list_elem elem; /* List element. */