X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=solutions%2Fp1-2.patch;h=70944edea534ac48332ddf3d8bebeb9bd2a7d270;hb=21608dd0aeb9880516e71cc6e9b16e58224118c4;hp=7e3858281d98108f7386c4f916d5ede12826ec5b;hpb=096f7f960b7a6ae9659a37a80d5647557aa9aca8;p=pintos-anon diff --git a/solutions/p1-2.patch b/solutions/p1-2.patch index 7e38582..70944ed 100644 --- a/solutions/p1-2.patch +++ b/solutions/p1-2.patch @@ -1,171 +1,308 @@ -diff -X pat -urpN threads/synch.c! src/threads/synch.c ---- src/threads/synch.c~ 2004-09-19 21:29:53.000000000 -0700 -+++ src/threads/synch.c 2004-09-27 16:50:14.000000000 -0700 -@@ -330,3 +330,35 @@ cond_name (const struct condition *cond) - - return cond->name; +Index: src/threads/synch.c +=================================================================== +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 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,18 @@ sema_down (struct semaphore *sema) + intr_set_level (old_level); } -+ -+void -+latch_init (struct latch *latch, const char *name) + ++/* Returns true if thread A has lower priority than thread B. */ ++static bool ++donated_lower_priority (const struct list_elem *a_, ++ const struct list_elem *b_, ++ void *aux UNUSED) +{ -+ latch->released = false; -+ lock_init (&latch->monitor_lock, name); -+ cond_init (&latch->rel_cond, name); -+} ++ const struct thread *a = list_entry (a_, struct thread, donor_elem); ++ const struct thread *b = list_entry (b_, struct thread, donor_elem); + -+void -+latch_acquire (struct latch *latch) -+{ -+ lock_acquire (&latch->monitor_lock); -+ if (!latch->released) -+ { -+ cond_wait (&latch->rel_cond, &latch->monitor_lock); -+ ASSERT (latch->released); -+ } -+ lock_release (&latch->monitor_lock); ++ return a->priority < b->priority; +} + -+void -+latch_release (struct latch *latch) -+{ -+ lock_acquire (&latch->monitor_lock); -+ if (!latch->released) + /* 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 (); +- if (!list_empty (&sema->waiters)) +- thread_unblock (list_entry (list_pop_front (&sema->waiters), +- struct thread, elem)); + sema->value++; ++ if (!list_empty (&sema->waiters)) + { -+ latch->released = true; -+ cond_signal (&latch->rel_cond, &latch->monitor_lock); ++ /* Find highest-priority waiting thread. */ ++ struct thread *max = list_entry (list_max (&sema->waiters, ++ donated_lower_priority, NULL), ++ struct thread, elem); ++ ++ /* Remove `max' from wait list and unblock. */ ++ list_remove (&max->elem); ++ thread_unblock (max); ++ ++ /* 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 () && old_level == INTR_ON) ++ thread_yield_to_higher_priority (); + } -+ lock_release (&latch->monitor_lock); -+} -diff -X pat -urpN src/threads/synch.h~ src/threads/synch.h ---- src/threads/synch.h~ 2004-09-19 21:29:53.000000000 -0700 -+++ src/threads/synch.h 2004-09-27 16:50:14.000000000 -0700 -@@ -44,4 +44,16 @@ void cond_signal (struct condition *, st - void cond_broadcast (struct condition *, struct lock *); - const char *cond_name (const struct condition *); - -+/* Latch. */ -+struct latch -+ { -+ bool released; /* Released yet? */ -+ struct lock monitor_lock; /* Monitor lock. */ -+ struct condition rel_cond; /* Signaled when released. */ -+ }; -+ -+void latch_init (struct latch *, const char *); -+void latch_acquire (struct latch *); -+void latch_release (struct latch *); -+ - #endif /* threads/synch.h */ -diff -X pat -urpN src/threads/thread.c~ src/threads/thread.c ---- src/threads/thread.c~ 2004-09-26 14:15:17.000000000 -0700 -+++ src/threads/thread.c 2004-09-27 16:51:03.000000000 -0700 -@@ -80,6 +80,7 @@ thread_init (void) - init_thread (initial_thread, "main", PRI_DEFAULT); - initial_thread->status = THREAD_RUNNING; - initial_thread->tid = allocate_tid (); -+ sema_up (&initial_thread->can_die); + intr_set_level (old_level); } - /* Starts preemptive thread scheduling by enabling interrupts. -@@ -148,6 +149,7 @@ thread_create (const char *name, int pri - /* Initialize thread. */ - init_thread (t, name, priority); - tid = t->tid = allocate_tid (); -+ list_push_back (&thread_current ()->children, &t->children_elem); - - /* Stack frame for kernel_thread(). */ - kf = alloc_frame (t, sizeof *kf); -@@ -224,16 +226,34 @@ thread_tid (void) - void - thread_exit (void) +@@ -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); ++ ++ /* 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 +244,38 @@ void + lock_release (struct lock *lock) { + enum intr_level old_level; + struct thread *t = thread_current (); -+ list_elem *e, *next; -+ - ASSERT (!intr_context ()); ++ struct list_elem *e; - #ifdef USERPROG - process_exit (); - #endif + ASSERT (lock != NULL); + ASSERT (lock_held_by_current_thread (lock)); -+ /* Notify our parent that we're dying. */ -+ latch_release (&t->ready_to_die); + old_level = intr_disable (); + -+ /* Notify our children that they can die. */ -+ for (e = list_begin (&t->children); e != list_end (&t->children); 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 *child = list_entry (e, struct thread, children_elem); -+ next = list_next (e); -+ list_remove (e); -+ sema_up (&child->can_die); ++ struct thread *donor = list_entry (e, struct thread, donor_elem); ++ if (donor->want_lock == lock) ++ { ++ donor->donee = NULL; ++ e = list_remove (e); ++ } ++ else ++ e = list_next (e); + } + -+ /* Wait until our parent is ready for us to die. */ -+ sema_down (&t->can_die); ++ /* Release lock. */ + lock->holder = NULL; + sema_up (&lock->semaphore); ++ ++ /* 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 (); + - /* Just set our status to dying and schedule another process. - We will be destroyed during the call to schedule_tail(). */ - intr_disable (); -- thread_current ()->status = THREAD_DYING; -+ t->status = THREAD_DYING; + intr_set_level (old_level); + } + +Index: src/threads/thread.c +=================================================================== +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 +--- 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. */ + thread_unblock (t); ++ if (priority > thread_get_priority ()) ++ thread_yield (); + + return tid; + } +@@ -186,6 +188,19 @@ thread_block (void) schedule (); - NOT_REACHED (); } -@@ -270,6 +290,22 @@ thread_block (void) - thread_current ()->status = THREAD_BLOCKED; + ++/* Returns true if A has higher priority than B, ++ within a list of threads. */ ++static bool ++thread_higher_priority (const struct list_elem *a_, ++ const struct 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); ++ ++ return a->priority > b->priority; ++} ++ + /* 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 +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_higher_priority, NULL); + t->status = THREAD_READY; + intr_set_level (old_level); + } +@@ -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_higher_priority, NULL); + cur->status = THREAD_READY; schedule (); + intr_set_level (old_level); } +@@ -274,19 +288,75 @@ + { + } + +-/* 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; +-} + -+/* Waits for thread with tid CHILD_TID to die. */ ++/* Sets the current thread's priority to PRIORITY. */ +void -+thread_join (tid_t child_tid) ++thread_set_priority (int priority) +{ -+ struct thread *cur = thread_current (); -+ list_elem *e; ++ struct thread *t = thread_current (); ++ enum intr_level old_level; ++ ++ t->normal_priority = priority; + -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); ) ++ 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 struct list_elem *a_, ++ const struct 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 *child = list_entry (e, struct thread, children_elem); -+ e = list_next (e); -+ if (child->tid == child_tid) -+ latch_acquire (&child->ready_to_die); ++ 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,6 +371,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; - t->priority = priority; -+ latch_init (&t->ready_to_die, "ready-to-die"); -+ sema_init (&t->can_die, 0, "can-die"); -+ list_init (&t->children); +- t->priority = priority; ++ t->priority = t->normal_priority = priority; t->magic = THREAD_MAGIC; ++ list_init (&t->donors); } -diff -X pat -urpN src/threads/thread.h~ src/threads/thread.h ---- src/threads/thread.h~ 2004-09-26 14:15:17.000000000 -0700 -+++ src/threads/thread.h 2004-09-27 16:50:14.000000000 -0700 -@@ -4,6 +4,7 @@ - #include - #include - #include -+#include "threads/synch.h" - - /* States in a thread's life cycle. */ - enum thread_status -@@ -89,6 +90,12 @@ struct thread + /* Allocates a SIZE-byte frame at the top of thread T's stack and +Index: src/threads/thread.h +=================================================================== +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 +--- 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. */ - -+ /* Members for implementing thread_join(). */ -+ struct latch ready_to_die; /* Release when thread about to die. */ -+ struct semaphore can_die; /* Up when thread allowed to die. */ -+ struct list children; /* List of child threads. */ -+ list_elem children_elem; /* Element of `children' list. */ +- int priority; /* Priority. */ + ++ /* Thread priority. */ ++ int priority; /* Priority, including donations. */ ++ int normal_priority; /* Priority, without donations. */ ++ struct list donors; /* Threads donating priority to us. */ ++ struct 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. */ + struct 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 *); + void thread_set_priority (int); + int thread_get_priority (void);