---- cs140/pintos/src/threads/thread.c 2004-09-17 23:16:15.000000000 -0700
-+++ cs140/ref/pintos/src/threads/thread.c 2004-09-17 23:19:03.000000000 -0700
-@@ -75,6 +75,7 @@
- init_thread (initial_thread, "main", PRI_DEFAULT);
- initial_thread->status = THREAD_RUNNING;
- initial_thread->tid = allocate_tid ();
-+ sema_up (&initial_thread->can_die);
-
- /* Initialize run queue. */
- list_init (&ready_list);
-@@ -244,12 +245,29 @@
- void
- thread_exit (void)
+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);
+ }
+
++/* 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)
++{
++ 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 ();
+- if (!list_empty (&sema->waiters))
+- thread_unblock (list_entry (list_pop_front (&sema->waiters),
+- struct thread, elem));
+ sema->value++;
++ if (!list_empty (&sema->waiters))
++ {
++ /* 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 ();
++ }
+ intr_set_level (old_level);
+ }
+
+@@ -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;
-+
- ASSERT (!intr_context ());
++ struct list_elem *e;
-+ /* Notify our parent that we're dying. */
-+ sema_up (&t->ready_to_die);
+ ASSERT (lock != NULL);
+ ASSERT (lock_held_by_current_thread (lock));
+
+ old_level = intr_disable ();
+
-+ /* Notify our children that they can die. */
-+ for (e = list_begin (&t->children); e != list_end (&t->children);
-+ e = list_next (e))
++ /* 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);
-+ 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 ();
}
-@@ -286,6 +304,31 @@
- 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;
+
-+ for (e = list_begin (&cur->children); e != list_end (&cur->children); )
-+ {
-+ struct thread *child = list_entry (e, struct thread, children_elem);
-+ e = list_next (e);
-+ if (child->tid == child_tid)
-+ {
-+ /* Wait until child is ready to die. */
-+ sema_down (&child->ready_to_die);
++ t->normal_priority = priority;
++
++ 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);
++}
+
-+ /* Remove from list of children. */
-+ list_remove (&child->children_elem);
++/* Returns the current thread's priority. */
++int
++thread_get_priority (void)
++{
++ return thread_current ()->priority;
++}
+
-+ /* Notify child that it can finish dying. */
-+ sema_up (&child->can_die);
-+ }
++/* 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 *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);
+}
\f
/* Idle thread. Executes when no other thread is ready to run. */
static void
-@@ -348,12 +391,13 @@
- {
- init_thread (t, name, priority);
- t->tid = allocate_tid ();
-+ list_push_back (&thread_current ()->children, &t->children_elem);
- }
-
- return t;
- }
-
--/* Does basic initialization of T as a blocked thread named
-+/* Does basic initialization of T as a new, blocked thread named
- NAME. */
- static void
- init_thread (struct thread *t, const char *name, int priority)
-@@ -367,6 +411,9 @@
+@@ -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;
-+ sema_init (&t->ready_to_die, 0, "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);
}
---- cs140/pintos/src/threads/thread.h 2004-09-16 21:42:35.000000000 -0700
-+++ cs140/ref/pintos/src/threads/thread.h 2004-09-17 23:21:14.000000000 -0700
-@@ -4,6 +4,7 @@
- #include <debug.h>
- #include <list.h>
- #include <stdint.h>
-+#include "threads/synch.h"
-
- #ifdef USERPROG
- #include "userprog/addrspace.h"
-@@ -93,6 +94,12 @@
+ /* 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 semaphore ready_to_die; /* Up 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);
projects / pintos-anon / blobdiff