X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=solutions%2Fp1-2.patch;h=70944edea534ac48332ddf3d8bebeb9bd2a7d270;hb=15aa248a41556196803c75cb4f56ddad05f5d64e;hp=5e5ea21e5054f69b9511aacdd6d1614977e88665;hpb=31ea3e0d81304ca46d13e200dd998ea04a194e19;p=pintos-anon

diff --git a/solutions/p1-2.patch b/solutions/p1-2.patch
index 5e5ea21..70944ed 100644
--- a/solutions/p1-2.patch
+++ b/solutions/p1-2.patch
@@ -1,121 +1,308 @@
---- 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);
 +}
  
  /* 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);