X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=solutions%2Fp1-3.patch;h=81bca57e584b9c64f7bc8d0e6b99ff93d87f2cab;hb=fac66eca0db7c89882f17c7d58a9b37e4293478c;hp=7e111db878dae8057e8d8616707582d5d5d7f8b3;hpb=0f2a218006a27a609c29c61d3fea5761b5805186;p=pintos-anon

diff --git a/solutions/p1-3.patch b/solutions/p1-3.patch
index 7e111db..81bca57 100644
--- a/solutions/p1-3.patch
+++ b/solutions/p1-3.patch
@@ -1,11 +1,29 @@
-Index: threads/synch.c
+Index: src/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) 
+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,17 @@ 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 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 ();
@@ -15,108 +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 ();
++
++  /* 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 ();
++
    intr_set_level (old_level);
  }
  
-diff -u -p -u -p -r1.48 thread.c
---- threads/thread.c	9 Oct 2004 18:01:37 -0000	1.48
-+++ threads/thread.c	14 Oct 2004 05:21:08 -0000
+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. */
@@ -126,13 +134,15 @@ diff -u -p -u -p -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);
@@ -143,62 +153,97 @@ diff -u -p -u -p -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,44 @@ thread_yield (void) 
+@@ -266,11 +280,79 @@ 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);
  }
 +
++/* Sets the current thread's priority to PRIORITY. */
 +void
 +thread_set_priority (int priority) 
 +{
 +  struct thread *t = thread_current ();
-+  int old_priority, new_priority;
-+  list_elem *e;
++  enum intr_level old_level;
 +
-+  old_priority = t->priority;
-+  new_priority = t->normal_priority = 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)
-+        new_priority = donor->priority;
-+    }
++  t->normal_priority = priority;
 +
-+  t->priority = new_priority;
-+  
-+  if (new_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 +380,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;
@@ -209,24 +254,35 @@ diff -u -p -u -p -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);