X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=solutions%2Fp1-3.patch;h=dc54595dcde3ad09f369d855945284288183b73b;hb=01f46f42675434436caff072a40cb2bc904c2df4;hp=db95713f1b58e22c35afc8435e9a75da0d767903;hpb=f80f136740163b8d910db6e804ce60f8e6313cf8;p=pintos-anon diff --git a/solutions/p1-3.patch b/solutions/p1-3.patch index db95713..dc54595 100644 --- a/solutions/p1-3.patch +++ b/solutions/p1-3.patch @@ -1,44 +1,29 @@ -? threads.1 -Index: Make.config +Index: src/threads/synch.c =================================================================== -RCS file: /u/blp/cvs/pintos/src/Make.config,v -retrieving revision 1.2 -diff -u -p -u -r1.2 Make.config ---- Make.config 20 Sep 2004 04:27:28 -0000 1.2 -+++ Make.config 11 Oct 2004 07:29:34 -0000 -@@ -23,7 +23,7 @@ CAT = cat - - # Compiler and assembler invocation. - WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes -Wsystem-headers --CFLAGS = -g -O3 -MMD -msoft-float -+CFLAGS = -g -MMD -msoft-float - ASFLAGS = -Wa,--gstabs -MMD - - %.o: %.c -Index: devices/timer.c -=================================================================== -RCS file: /u/blp/cvs/pintos/src/devices/timer.c,v +RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v retrieving revision 1.15 -diff -u -p -u -r1.15 timer.c ---- devices/timer.c 6 Oct 2004 18:27:00 -0000 1.15 -+++ devices/timer.c 11 Oct 2004 07:29:34 -0000 -@@ -109,6 +109,8 @@ timer_interrupt (struct intr_frame *args - { - ticks++; - thread_tick (); -+#if 0 - if (ticks % TIME_SLICE == 0) - intr_yield_on_return (); -+#endif +diff -u -p -u -r1.15 synch.c +--- src/threads/synch.c 31 Dec 2004 21:13:38 -0000 1.15 ++++ src/threads/synch.c 31 Dec 2004 22:31:03 -0000 +@@ -77,6 +77,17 @@ sema_down (struct semaphore *sema) + intr_set_level (old_level); } -Index: threads/synch.c -=================================================================== -RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v -retrieving revision 1.14 -diff -u -p -u -r1.14 synch.c ---- threads/synch.c 29 Sep 2004 01:04:09 -0000 1.14 -+++ threads/synch.c 11 Oct 2004 07:29:34 -0000 -@@ -89,10 +89,32 @@ sema_up (struct semaphore *sema) + ++/* Returns true if thread A has lower priority than thread B. */ ++static bool ++donated_lower_priority (const list_elem *a_, const list_elem *b_, ++ void *aux UNUSED) ++{ ++ const struct thread *a = list_entry (a_, struct thread, donor_elem); ++ const struct thread *b = list_entry (b_, struct thread, donor_elem); ++ ++ return a->priority < b->priority; ++} ++ + /* Up or "V" operation on a semaphore. Increments SEMA's value + and wakes up one thread of those waiting for SEMA, if any. + +@@ -89,10 +100,28 @@ sema_up (struct semaphore *sema) ASSERT (sema != NULL); old_level = intr_disable (); @@ -48,309 +33,98 @@ diff -u -p -u -r1.14 synch.c sema->value++; + if (!list_empty (&sema->waiters)) + { -+ struct thread *max; -+ list_elem *e; ++ /* Find highest-priority waiting thread. */ ++ struct thread *max = list_entry (list_max (&sema->waiters, ++ donated_lower_priority, NULL), ++ struct thread, elem); + -+ max = list_entry (list_front (&sema->waiters), struct thread, elem); -+ for (e = list_begin (&sema->waiters); -+ e != list_end (&sema->waiters); e = list_next (e)) -+ { -+ struct thread *t = list_entry (e, struct thread, elem); -+ if (t->priority > max->priority) -+ max = t; -+ } ++ /* Remove `max' from wait list and unblock. */ + list_remove (&max->elem); + thread_unblock (max); + -+ /* Kind of a funny interaction with donation here. ++ /* Yield to a higher-priority thread, if we're running in a ++ context where it makes sense to do so. ++ ++ Kind of a funny interaction with donation here. + We only support donation for locks, and locks turn off + interrupts before calling us, so we automatically don't + do the yield here, delegating to lock_release(). */ -+ if (!intr_context () -+ && max->priority > thread_get_priority () -+ && old_level == INTR_ON) -+ thread_yield (); ++ if (!intr_context () && old_level == INTR_ON) ++ thread_yield_to_higher_priority (); + } intr_set_level (old_level); } -@@ -166,6 +188,21 @@ lock_init (struct lock *lock, const char - sema_init (&lock->semaphore, 1, name); - } - -+static void -+revise_priority (struct thread *t) -+{ -+ list_elem *e; -+ -+ t->priority = t->normal_priority; -+ for (e = list_begin (&t->donors); e != list_end (&t->donors); -+ e = list_next (e)) -+ { -+ struct thread *donor = list_entry (e, struct thread, donor_elem); -+ if (donor->priority > t->priority) -+ t->priority = donor->priority; -+ } -+} -+ - /* Acquires LOCK, sleeping until it becomes available if - necessary. The lock must not already be held by the current - thread. -@@ -184,6 +221,17 @@ lock_acquire (struct lock *lock) +@@ -184,6 +213,23 @@ lock_acquire (struct lock *lock) ASSERT (!lock_held_by_current_thread (lock)); old_level = intr_disable (); + + if (lock->holder != NULL) + { ++ /* Donate our priority to the thread holding the lock. ++ First, update the data structures. */ + struct thread *donor = thread_current (); + donor->want_lock = lock; + donor->donee = lock->holder; + list_push_back (&lock->holder->donors, &donor->donor_elem); -+ revise_priority (lock->holder); -+ //recurse_donation (&lock->holder); ++ ++ /* Now implement the priority donation itself ++ by recomputing the donee's priority ++ and cascading the donation as far as necessary. */ ++ while (donor->donee != NULL && thread_recompute_priority (donor->donee)) ++ donor = donor->donee; + } + sema_down (&lock->semaphore); lock->holder = thread_current (); intr_set_level (old_level); -@@ -198,13 +246,32 @@ void +@@ -198,13 +244,38 @@ void lock_release (struct lock *lock) { enum intr_level old_level; + struct thread *t = thread_current (); -+ list_elem *e, *next; -+ bool did_donate = false; ++ list_elem *e; ASSERT (lock != NULL); ASSERT (lock_held_by_current_thread (lock)); old_level = intr_disable (); -+ for (e = list_begin (&t->donors); e != list_end (&t->donors); -+ e = next) ++ ++ /* Remove donations from threads that want the lock we're ++ releasing. */ ++ for (e = list_begin (&t->donors); e != list_end (&t->donors); ) + { + struct thread *donor = list_entry (e, struct thread, donor_elem); -+ next = list_next (e); + if (donor->want_lock == lock) + { + donor->donee = NULL; -+ list_remove (e); -+ did_donate = true; ++ e = list_remove (e); + } ++ else ++ e = list_next (e); + } -+ revise_priority (t); ++ ++ /* Release lock. */ lock->holder = NULL; -+ sema_up (&lock->semaphore); -+ if (did_donate) -+ thread_yield (); - intr_set_level (old_level); - } - -Index: threads/test.c -=================================================================== -RCS file: /u/blp/cvs/pintos/src/threads/test.c,v -retrieving revision 1.4 -diff -u -p -u -r1.4 test.c ---- threads/test.c 17 Sep 2004 06:52:27 -0000 1.4 -+++ threads/test.c 11 Oct 2004 07:29:34 -0000 -@@ -1,110 +1,109 @@ -+/* Problem 1-3: Priority Scheduling tests. -+ -+ Based on a test originally submitted for Stanford's CS 140 in -+ winter 1999 by by Matt Franklin -+ , Greg Hutchins -+ , Yu Ping Hu . -+ Modified by arens. */ + - #include "threads/test.h" - #include - #include "threads/synch.h" - #include "threads/thread.h" --#include "devices/timer.h" - --static void test_sleep (int iterations); -+static void test_preempt (void); -+static void test_fifo (void); -+static void test_donate_return (void); - - void - test (void) - { -- test_sleep (1); -- test_sleep (7); -+ /* Make sure our prority is the default. */ -+ ASSERT (thread_get_priority () == PRI_DEFAULT); ++ /* Recompute our priority based on our remaining donations, ++ then yield to a higher-priority ready thread if one now ++ exists. */ ++ thread_recompute_priority (t); ++ thread_yield_to_higher_priority (); + -+ //test_preempt (); -+ //test_fifo (); -+ test_donate_return (); - } - --/* Based on a test originally submitted for Stanford's CS 140 in -- winter 1998 by Rob Baesman , Ben -- Taskar , and Toli Kuznets -- . */ --struct sleep_thread_data -- { -- int64_t start; /* Start time. */ -- int duration; /* Number of ticks to sleep. */ -- int iterations; /* Number of iterations to run. */ -- int *product; /* Largest product so far. */ -- struct lock *lock; /* Lock on access to `product'. */ -- struct semaphore done; /* Completion semaphore. */ -- tid_t tid; /* Thread ID. */ -- }; -+static thread_func simple_thread_func; -+static thread_func acquire_thread_func; - --static void sleeper (void *); -+static void -+test_preempt (void) -+{ -+ printf ("\n" -+ "Testing priority preemption.\n"); -+ thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL); -+ printf ("The high-priority thread should have already completed.\n" -+ "Priority preemption test done.\n"); -+} - - static void --test_sleep (int iterations) -+test_fifo (void) - { -- struct sleep_thread_data threads[5]; -- const int thread_cnt = sizeof threads / sizeof *threads; -- struct lock lock; -- int64_t start; -- int product; - int i; -- -+ - printf ("\n" -- "Testing %d sleeps per thread.\n" -- "If successful, product of iteration count and\n" -- "sleep duration will appear in nondescending order.\n", -- iterations); -- -- /* Start all the threads. */ -- product = 0; -- lock_init (&lock, "product"); -- start = timer_ticks (); -- for (i = 0; i < thread_cnt; i++) -+ "Testing FIFO preemption.\n" -+ "5 threads will iterate 10 times in the same order each time.\n" -+ "If the order varies then there is a bug.\n"); -+ -+ thread_set_priority (PRI_DEFAULT + 2); -+ for (i = 0; i < 5; i++) - { -- struct sleep_thread_data *t; - char name[16]; -- -- snprintf (name, sizeof name, "thread %d", i); -- t = threads + i; -- t->start = start; -- t->duration = (i + 1) * 10; -- t->iterations = iterations; -- t->product = &product; -- t->lock = &lock; -- sema_init (&t->done, 0, name); -- t->tid = thread_create (name, PRI_DEFAULT, sleeper, t); -- } -- -- /* Wait for all the threads to finish. */ -- for (i = 0; i < thread_cnt; i++) -- { --#ifdef THREAD_JOIN_IMPLEMENTED -- thread_join (threads[i].tid); --#else -- sema_down (&threads[i].done); --#endif -+ snprintf (name, sizeof name, "%d", i); -+ thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL); - } -+ thread_set_priority (PRI_DEFAULT); - -- printf ("...done\n"); -+ printf ("FIFO preemption test done.\n"); + intr_set_level (old_level); } - static void --sleeper (void *t_) -+test_donate_return (void) - { -- struct sleep_thread_data *t = t_; -- int i; -+ struct lock lock; - -- for (i = 1; i <= t->iterations; i++) -- { -- int old_product; -- int new_product = i * t->duration; -+ printf ("\n" -+ "Testing priority donation.\n" -+ "If the statements printed below are all true, you pass.\n"); - -- timer_sleep ((t->start + new_product) - timer_ticks ()); -+ lock_init (&lock, "donor"); -+ lock_acquire (&lock); -+ thread_create ("acquire1", PRI_DEFAULT + 1, acquire_thread_func, &lock); -+ printf ("This thread should have priority %d. Actual priority: %d.\n", -+ PRI_DEFAULT + 1, thread_get_priority ()); -+ thread_create ("acquire2", PRI_DEFAULT + 2, acquire_thread_func, &lock); -+ printf ("This thread should have priority %d. Actual priority: %d.\n", -+ PRI_DEFAULT + 2, thread_get_priority ()); -+ lock_release (&lock); -+ printf ("acquire2 and acquire1 must already have finished, in that order.\n" -+ "This should be the last line before finishing this test.\n" -+ "Priority donation test done.\n"); -+} - -- lock_acquire (t->lock); -- old_product = *t->product; -- *t->product = new_product; -- lock_release (t->lock); -- -- printf ("%s: duration=%d, iteration=%d, product=%d\n", -- thread_name (), t->duration, i, new_product); -- -- if (old_product > new_product) -- printf ("%s: Out of order sleep completion (%d > %d)!\n", -- thread_name (), old_product, new_product); -- } -+static void -+simple_thread_func (void *aux UNUSED) -+{ -+ int i; - -- /* Signal completion. */ -- sema_up (&t->done); -+ for (i = 0; i < 5; i++) -+ { -+ printf ("Thread %s iteration %d\n", thread_name (), i); -+ thread_yield (); -+ } -+ printf ("Thread %s done!\n", thread_name ()); -+} -+ -+static void -+acquire_thread_func (void *lock_) -+{ -+ struct lock *lock = lock_; -+ -+ lock_acquire (lock); -+ printf ("%s: got the lock\n", thread_name ()); -+ lock_release (lock); -+ printf ("%s: done\n", thread_name ()); - } -Index: threads/thread.c +Index: src/threads/thread.c =================================================================== -RCS file: /u/blp/cvs/pintos/src/threads/thread.c,v +RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v retrieving revision 1.48 diff -u -p -u -r1.48 thread.c ---- threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48 -+++ threads/thread.c 11 Oct 2004 07:29:35 -0000 +--- src/threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48 ++++ src/threads/thread.c 31 Dec 2004 22:31:03 -0000 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri /* Add to run queue. */ @@ -360,13 +134,15 @@ diff -u -p -u -r1.48 thread.c return tid; } -@@ -186,6 +188,16 @@ thread_block (void) +@@ -186,6 +188,18 @@ thread_block (void) schedule (); } ++/* Returns true if A has higher priority than B, ++ within a list of threads. */ +static bool -+thread_greater_priority (const list_elem *a_, const list_elem *b_, -+ void *aux UNUSED) ++thread_higher_priority (const list_elem *a_, const list_elem *b_, ++ void *aux UNUSED) +{ + const struct thread *a = list_entry (a_, struct thread, elem); + const struct thread *b = list_entry (b_, struct thread, elem); @@ -377,51 +153,114 @@ diff -u -p -u -r1.48 thread.c /* Transitions a blocked thread T to the ready-to-run state. This is an error if T is not blocked. (Use thread_yield() to make the running thread ready.) */ -@@ -198,7 +210,7 @@ thread_unblock (struct thread *t) +@@ -198,7 +212,7 @@ thread_unblock (struct thread *t) old_level = intr_disable (); ASSERT (t->status == THREAD_BLOCKED); - list_push_back (&ready_list, &t->elem); -+ list_insert_ordered (&ready_list, &t->elem, thread_greater_priority, NULL); ++ list_insert_ordered (&ready_list, &t->elem, thread_higher_priority, NULL); t->status = THREAD_READY; intr_set_level (old_level); } -@@ -266,11 +278,33 @@ thread_yield (void) +@@ -266,8 +280,8 @@ thread_yield (void) ASSERT (!intr_context ()); old_level = intr_disable (); - list_push_back (&ready_list, &cur->elem); -+ list_insert_ordered (&ready_list, &cur->elem, thread_greater_priority, NULL); ++ list_insert_ordered (&ready_list, &cur->elem, thread_higher_priority, NULL); cur->status = THREAD_READY; schedule (); intr_set_level (old_level); } +@@ -274,19 +288,74 @@ + { + } + +-/* Sets the current thread's priority to NEW_PRIORITY. */ +-void +-thread_set_priority (int new_priority) +-{ +- thread_current ()->priority = new_priority; +-} +- +-/* Returns the current thread's priority. */ +-int +-thread_get_priority (void) +-{ +- return thread_current ()->priority; +-} + ++/* Sets the current thread's priority to PRIORITY. */ +void +thread_set_priority (int priority) +{ + struct thread *t = thread_current (); -+ int old_priority = t->priority; ++ enum intr_level old_level; ++ + t->normal_priority = priority; -+ if (t->normal_priority > t->priority) -+ t->priority = t->normal_priority; -+ if (priority < old_priority) -+ { -+ /* FIXME: if this is still (one of) the highest priority -+ threads then don't yield. */ -+ thread_yield (); -+ } ++ ++ old_level = intr_disable (); ++ while (thread_recompute_priority (t) && t->donee != NULL) ++ t = t->donee; ++ thread_yield_to_higher_priority (); ++ intr_set_level (old_level); +} + ++/* Returns the current thread's priority. */ +int +thread_get_priority (void) +{ + return thread_current ()->priority; ++} ++ ++/* Returns true if thread A has lower priority than thread B, ++ within a list of donors. */ ++static bool ++donated_lower_priority (const list_elem *a_, const list_elem *b_, ++ void *aux UNUSED) ++{ ++ const struct thread *a = list_entry (a_, struct thread, donor_elem); ++ const struct thread *b = list_entry (b_, struct thread, donor_elem); ++ ++ return a->priority < b->priority; ++} ++ ++/* Recomputes T's priority in terms of its normal priority and ++ its donors' priorities, if any. ++ Returns true if T's new priority is higher than its old ++ priority, false otherwise. */ ++bool ++thread_recompute_priority (struct thread *t) ++{ ++ int old = t->priority; ++ int donation = 0; ++ if (!list_empty (&t->donors)) ++ donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL), ++ struct thread, donor_elem)->priority; ++ t->priority = donation > t->normal_priority ? donation : t->normal_priority; ++ return t->priority > old; ++} ++ ++/* If the ready list contains a thread with a higher priority, ++ yields to it. */ ++void ++thread_yield_to_higher_priority (void) ++{ ++ enum intr_level old_level = intr_disable (); ++ if (!list_empty (&ready_list)) ++ { ++ struct thread *cur = thread_current (); ++ struct thread *max = list_entry (list_front (&ready_list), ++ struct thread, elem); ++ if (max->priority > cur->priority) ++ thread_yield (); ++ } ++ intr_set_level (old_level); +} /* Idle thread. Executes when no other thread is ready to run. */ static void -@@ -335,8 +369,9 @@ init_thread (struct thread *t, const cha +@@ -335,8 +417,9 @@ init_thread (struct thread *t, const cha t->status = THREAD_BLOCKED; strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; @@ -432,24 +271,35 @@ diff -u -p -u -r1.48 thread.c } /* Allocates a SIZE-byte frame at the top of thread T's stack and -Index: threads/thread.h +Index: src/threads/thread.h =================================================================== -RCS file: /u/blp/cvs/pintos/src/threads/thread.h,v +RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v retrieving revision 1.28 diff -u -p -u -r1.28 thread.h ---- threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28 -+++ threads/thread.h 11 Oct 2004 07:29:35 -0000 -@@ -88,6 +88,13 @@ struct thread +--- src/threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28 ++++ src/threads/thread.h 31 Dec 2004 22:31:03 -0000 +@@ -87,7 +87,14 @@ struct thread + enum thread_status status; /* Thread state. */ char name[16]; /* Name (for debugging purposes). */ uint8_t *stack; /* Saved stack pointer. */ - int priority; /* Priority. */ -+ int normal_priority; /* Priority. */ +- int priority; /* Priority. */ + -+ /* Priority donation. */ -+ struct list donors; -+ list_elem donor_elem; -+ struct thread *donee; -+ struct lock *want_lock; ++ /* Thread priority. */ ++ int priority; /* Priority, including donations. */ ++ int normal_priority; /* Priority, without donations. */ ++ struct list donors; /* Threads donating priority to us. */ ++ list_elem donor_elem; /* Element in donors list. */ ++ struct thread *donee; /* Thread we're donating to. */ ++ struct lock *want_lock; /* Lock we're waiting to acquire. */ /* Shared between thread.c and synch.c. */ list_elem elem; /* List element. */ +@@ -118,6 +125,8 @@ const char *thread_name (void); + + void thread_exit (void) NO_RETURN; + void thread_yield (void); ++void thread_yield_to_higher_priority (void); ++bool thread_recompute_priority (struct thread *); + + /* This function will be implemented in problem 1-2. */ + void thread_join (tid_t);