3 ===================================================================
4 RCS file: /u/blp/cvs/pintos/src/Make.config,v
5 retrieving revision 1.2
6 diff -u -p -u -r1.2 Make.config
7 --- Make.config 20 Sep 2004 04:27:28 -0000 1.2
8 +++ Make.config 11 Oct 2004 07:29:34 -0000
9 @@ -23,7 +23,7 @@ CAT = cat
11 # Compiler and assembler invocation.
12 WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes -Wsystem-headers
13 -CFLAGS = -g -O3 -MMD -msoft-float
14 +CFLAGS = -g -MMD -msoft-float
15 ASFLAGS = -Wa,--gstabs -MMD
18 Index: devices/timer.c
19 ===================================================================
20 RCS file: /u/blp/cvs/pintos/src/devices/timer.c,v
21 retrieving revision 1.15
22 diff -u -p -u -r1.15 timer.c
23 --- devices/timer.c 6 Oct 2004 18:27:00 -0000 1.15
24 +++ devices/timer.c 11 Oct 2004 07:29:34 -0000
25 @@ -109,6 +109,8 @@ timer_interrupt (struct intr_frame *args
30 if (ticks % TIME_SLICE == 0)
31 intr_yield_on_return ();
34 Index: threads/synch.c
35 ===================================================================
36 RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v
37 retrieving revision 1.14
38 diff -u -p -u -r1.14 synch.c
39 --- threads/synch.c 29 Sep 2004 01:04:09 -0000 1.14
40 +++ threads/synch.c 11 Oct 2004 07:29:34 -0000
41 @@ -89,10 +89,32 @@ sema_up (struct semaphore *sema)
42 ASSERT (sema != NULL);
44 old_level = intr_disable ();
45 - if (!list_empty (&sema->waiters))
46 - thread_unblock (list_entry (list_pop_front (&sema->waiters),
47 - struct thread, elem));
49 + if (!list_empty (&sema->waiters))
54 + max = list_entry (list_front (&sema->waiters), struct thread, elem);
55 + for (e = list_begin (&sema->waiters);
56 + e != list_end (&sema->waiters); e = list_next (e))
58 + struct thread *t = list_entry (e, struct thread, elem);
59 + if (t->priority > max->priority)
62 + list_remove (&max->elem);
63 + thread_unblock (max);
65 + /* Kind of a funny interaction with donation here.
66 + We only support donation for locks, and locks turn off
67 + interrupts before calling us, so we automatically don't
68 + do the yield here, delegating to lock_release(). */
69 + if (!intr_context ()
70 + && max->priority > thread_get_priority ()
71 + && old_level == INTR_ON)
74 intr_set_level (old_level);
77 @@ -166,6 +188,21 @@ lock_init (struct lock *lock, const char
78 sema_init (&lock->semaphore, 1, name);
82 +revise_priority (struct thread *t)
86 + t->priority = t->normal_priority;
87 + for (e = list_begin (&t->donors); e != list_end (&t->donors);
90 + struct thread *donor = list_entry (e, struct thread, donor_elem);
91 + if (donor->priority > t->priority)
92 + t->priority = donor->priority;
96 /* Acquires LOCK, sleeping until it becomes available if
97 necessary. The lock must not already be held by the current
99 @@ -184,6 +221,17 @@ lock_acquire (struct lock *lock)
100 ASSERT (!lock_held_by_current_thread (lock));
102 old_level = intr_disable ();
104 + if (lock->holder != NULL)
106 + struct thread *donor = thread_current ();
107 + donor->want_lock = lock;
108 + donor->donee = lock->holder;
109 + list_push_back (&lock->holder->donors, &donor->donor_elem);
110 + revise_priority (lock->holder);
111 + //recurse_donation (&lock->holder);
114 sema_down (&lock->semaphore);
115 lock->holder = thread_current ();
116 intr_set_level (old_level);
117 @@ -198,13 +246,32 @@ void
118 lock_release (struct lock *lock)
120 enum intr_level old_level;
121 + struct thread *t = thread_current ();
122 + list_elem *e, *next;
123 + bool did_donate = false;
125 ASSERT (lock != NULL);
126 ASSERT (lock_held_by_current_thread (lock));
128 old_level = intr_disable ();
129 + for (e = list_begin (&t->donors); e != list_end (&t->donors);
132 + struct thread *donor = list_entry (e, struct thread, donor_elem);
133 + next = list_next (e);
134 + if (donor->want_lock == lock)
136 + donor->donee = NULL;
141 + revise_priority (t);
144 sema_up (&lock->semaphore);
147 intr_set_level (old_level);
150 Index: threads/test.c
151 ===================================================================
152 RCS file: /u/blp/cvs/pintos/src/threads/test.c,v
153 retrieving revision 1.4
154 diff -u -p -u -r1.4 test.c
155 --- threads/test.c 17 Sep 2004 06:52:27 -0000 1.4
156 +++ threads/test.c 11 Oct 2004 07:29:34 -0000
158 +/* Problem 1-3: Priority Scheduling tests.
160 + Based on a test originally submitted for Stanford's CS 140 in
161 + winter 1999 by by Matt Franklin
162 + <startled@leland.stanford.edu>, Greg Hutchins
163 + <gmh@leland.stanford.edu>, Yu Ping Hu <yph@cs.stanford.edu>.
164 + Modified by arens. */
166 #include "threads/test.h"
168 #include "threads/synch.h"
169 #include "threads/thread.h"
170 -#include "devices/timer.h"
172 -static void test_sleep (int iterations);
173 +static void test_preempt (void);
174 +static void test_fifo (void);
175 +static void test_donate_return (void);
182 + /* Make sure our prority is the default. */
183 + ASSERT (thread_get_priority () == PRI_DEFAULT);
187 + test_donate_return ();
190 -/* Based on a test originally submitted for Stanford's CS 140 in
191 - winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
192 - Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
193 - <tolik@cs.stanford.edu>. */
194 -struct sleep_thread_data
196 - int64_t start; /* Start time. */
197 - int duration; /* Number of ticks to sleep. */
198 - int iterations; /* Number of iterations to run. */
199 - int *product; /* Largest product so far. */
200 - struct lock *lock; /* Lock on access to `product'. */
201 - struct semaphore done; /* Completion semaphore. */
202 - tid_t tid; /* Thread ID. */
204 +static thread_func simple_thread_func;
205 +static thread_func acquire_thread_func;
207 -static void sleeper (void *);
212 + "Testing priority preemption.\n");
213 + thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL);
214 + printf ("The high-priority thread should have already completed.\n"
215 + "Priority preemption test done.\n");
219 -test_sleep (int iterations)
222 - struct sleep_thread_data threads[5];
223 - const int thread_cnt = sizeof threads / sizeof *threads;
231 - "Testing %d sleeps per thread.\n"
232 - "If successful, product of iteration count and\n"
233 - "sleep duration will appear in nondescending order.\n",
236 - /* Start all the threads. */
238 - lock_init (&lock, "product");
239 - start = timer_ticks ();
240 - for (i = 0; i < thread_cnt; i++)
241 + "Testing FIFO preemption.\n"
242 + "5 threads will iterate 10 times in the same order each time.\n"
243 + "If the order varies then there is a bug.\n");
245 + thread_set_priority (PRI_DEFAULT + 2);
246 + for (i = 0; i < 5; i++)
248 - struct sleep_thread_data *t;
251 - snprintf (name, sizeof name, "thread %d", i);
254 - t->duration = (i + 1) * 10;
255 - t->iterations = iterations;
256 - t->product = &product;
258 - sema_init (&t->done, 0, name);
259 - t->tid = thread_create (name, PRI_DEFAULT, sleeper, t);
262 - /* Wait for all the threads to finish. */
263 - for (i = 0; i < thread_cnt; i++)
265 -#ifdef THREAD_JOIN_IMPLEMENTED
266 - thread_join (threads[i].tid);
268 - sema_down (&threads[i].done);
270 + snprintf (name, sizeof name, "%d", i);
271 + thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL);
273 + thread_set_priority (PRI_DEFAULT);
275 - printf ("...done\n");
276 + printf ("FIFO preemption test done.\n");
281 +test_donate_return (void)
283 - struct sleep_thread_data *t = t_;
287 - for (i = 1; i <= t->iterations; i++)
290 - int new_product = i * t->duration;
292 + "Testing priority donation.\n"
293 + "If the statements printed below are all true, you pass.\n");
295 - timer_sleep ((t->start + new_product) - timer_ticks ());
296 + lock_init (&lock, "donor");
297 + lock_acquire (&lock);
298 + thread_create ("acquire1", PRI_DEFAULT + 1, acquire_thread_func, &lock);
299 + printf ("This thread should have priority %d. Actual priority: %d.\n",
300 + PRI_DEFAULT + 1, thread_get_priority ());
301 + thread_create ("acquire2", PRI_DEFAULT + 2, acquire_thread_func, &lock);
302 + printf ("This thread should have priority %d. Actual priority: %d.\n",
303 + PRI_DEFAULT + 2, thread_get_priority ());
304 + lock_release (&lock);
305 + printf ("acquire2 and acquire1 must already have finished, in that order.\n"
306 + "This should be the last line before finishing this test.\n"
307 + "Priority donation test done.\n");
310 - lock_acquire (t->lock);
311 - old_product = *t->product;
312 - *t->product = new_product;
313 - lock_release (t->lock);
315 - printf ("%s: duration=%d, iteration=%d, product=%d\n",
316 - thread_name (), t->duration, i, new_product);
318 - if (old_product > new_product)
319 - printf ("%s: Out of order sleep completion (%d > %d)!\n",
320 - thread_name (), old_product, new_product);
323 +simple_thread_func (void *aux UNUSED)
327 - /* Signal completion. */
328 - sema_up (&t->done);
329 + for (i = 0; i < 5; i++)
331 + printf ("Thread %s iteration %d\n", thread_name (), i);
334 + printf ("Thread %s done!\n", thread_name ());
338 +acquire_thread_func (void *lock_)
340 + struct lock *lock = lock_;
342 + lock_acquire (lock);
343 + printf ("%s: got the lock\n", thread_name ());
344 + lock_release (lock);
345 + printf ("%s: done\n", thread_name ());
347 Index: threads/thread.c
348 ===================================================================
349 RCS file: /u/blp/cvs/pintos/src/threads/thread.c,v
350 retrieving revision 1.48
351 diff -u -p -u -r1.48 thread.c
352 --- threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48
353 +++ threads/thread.c 11 Oct 2004 07:29:35 -0000
354 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
356 /* Add to run queue. */
358 + if (priority > thread_get_priority ())
363 @@ -186,6 +188,16 @@ thread_block (void)
368 +thread_greater_priority (const list_elem *a_, const list_elem *b_,
371 + const struct thread *a = list_entry (a_, struct thread, elem);
372 + const struct thread *b = list_entry (b_, struct thread, elem);
374 + return a->priority > b->priority;
377 /* Transitions a blocked thread T to the ready-to-run state.
378 This is an error if T is not blocked. (Use thread_yield() to
379 make the running thread ready.) */
380 @@ -198,7 +210,7 @@ thread_unblock (struct thread *t)
382 old_level = intr_disable ();
383 ASSERT (t->status == THREAD_BLOCKED);
384 - list_push_back (&ready_list, &t->elem);
385 + list_insert_ordered (&ready_list, &t->elem, thread_greater_priority, NULL);
386 t->status = THREAD_READY;
387 intr_set_level (old_level);
389 @@ -266,11 +278,33 @@ thread_yield (void)
390 ASSERT (!intr_context ());
392 old_level = intr_disable ();
393 - list_push_back (&ready_list, &cur->elem);
394 + list_insert_ordered (&ready_list, &cur->elem, thread_greater_priority, NULL);
395 cur->status = THREAD_READY;
397 intr_set_level (old_level);
401 +thread_set_priority (int priority)
403 + struct thread *t = thread_current ();
404 + int old_priority = t->priority;
405 + t->normal_priority = priority;
406 + if (t->normal_priority > t->priority)
407 + t->priority = t->normal_priority;
408 + if (priority < old_priority)
410 + /* FIXME: if this is still (one of) the highest priority
411 + threads then don't yield. */
417 +thread_get_priority (void)
419 + return thread_current ()->priority;
422 /* Idle thread. Executes when no other thread is ready to run. */
424 @@ -335,8 +369,9 @@ init_thread (struct thread *t, const cha
425 t->status = THREAD_BLOCKED;
426 strlcpy (t->name, name, sizeof t->name);
427 t->stack = (uint8_t *) t + PGSIZE;
428 - t->priority = priority;
429 + t->priority = t->normal_priority = priority;
430 t->magic = THREAD_MAGIC;
431 + list_init (&t->donors);
434 /* Allocates a SIZE-byte frame at the top of thread T's stack and
435 Index: threads/thread.h
436 ===================================================================
437 RCS file: /u/blp/cvs/pintos/src/threads/thread.h,v
438 retrieving revision 1.28
439 diff -u -p -u -r1.28 thread.h
440 --- threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28
441 +++ threads/thread.h 11 Oct 2004 07:29:35 -0000
442 @@ -88,6 +88,13 @@ struct thread
443 char name[16]; /* Name (for debugging purposes). */
444 uint8_t *stack; /* Saved stack pointer. */
445 int priority; /* Priority. */
446 + int normal_priority; /* Priority. */
448 + /* Priority donation. */
449 + struct list donors;
450 + list_elem donor_elem;
451 + struct thread *donee;
452 + struct lock *want_lock;
454 /* Shared between thread.c and synch.c. */
455 list_elem elem; /* List element. */