pintos-os.org Git - pintos-anon/blob - solutions/p1-3.patch

   1 ? threads.1
   2 Index: Make.config
   3 ===================================================================
   4 RCS file: /u/blp/cvs/pintos/src/Make.config,v
   5 retrieving revision 1.2
   6 diff -u -p -u -r1.2 Make.config
   7 --- Make.config 20 Sep 2004 04:27:28 -0000      1.2
   8 +++ Make.config 11 Oct 2004 07:29:34 -0000
   9 @@ -23,7 +23,7 @@ CAT = cat
  10
  11  # Compiler and assembler invocation.
  12  WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes -Wsystem-headers
  13 -CFLAGS = -g -O3 -MMD -msoft-float
  14 +CFLAGS = -g -MMD -msoft-float
  15  ASFLAGS = -Wa,--gstabs -MMD
  16
  17  %.o: %.c
  18 Index: devices/timer.c
  19 ===================================================================
  20 RCS file: /u/blp/cvs/pintos/src/devices/timer.c,v
  21 retrieving revision 1.15
  22 diff -u -p -u -r1.15 timer.c
  23 --- devices/timer.c     6 Oct 2004 18:27:00 -0000       1.15
  24 +++ devices/timer.c     11 Oct 2004 07:29:34 -0000
  25 @@ -109,6 +109,8 @@ timer_interrupt (struct intr_frame *args
  26  {
  27    ticks++;
  28    thread_tick ();
  29 +#if 0
  30    if (ticks % TIME_SLICE == 0)
  31      intr_yield_on_return ();
  32 +#endif
  33  }
  34 Index: threads/synch.c
  35 ===================================================================
  36 RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v
  37 retrieving revision 1.14
  38 diff -u -p -u -r1.14 synch.c
  39 --- threads/synch.c     29 Sep 2004 01:04:09 -0000      1.14
  40 +++ threads/synch.c     11 Oct 2004 07:29:34 -0000
  41 @@ -89,10 +89,32 @@ sema_up (struct semaphore *sema)
  42    ASSERT (sema != NULL);
  43
  44    old_level = intr_disable ();
  45 -  if (!list_empty (&sema->waiters))
  46 -    thread_unblock (list_entry (list_pop_front (&sema->waiters),
  47 -                                struct thread, elem));
  48    sema->value++;
  49 +  if (!list_empty (&sema->waiters))
  50 +    {
  51 +      struct thread *max;
  52 +      list_elem *e;
  53 +
  54 +      max = list_entry (list_front (&sema->waiters), struct thread, elem);
  55 +      for (e = list_begin (&sema->waiters);
  56 +           e != list_end (&sema->waiters); e = list_next (e))
  57 +        {
  58 +          struct thread *t = list_entry (e, struct thread, elem);
  59 +          if (t->priority > max->priority)
  60 +            max = t;
  61 +        }
  62 +      list_remove (&max->elem);
  63 +      thread_unblock (max);
  64 +
  65 +      /* Kind of a funny interaction with donation here.
  66 +         We only support donation for locks, and locks turn off
  67 +         interrupts before calling us, so we automatically don't
  68 +         do the yield here, delegating to lock_release(). */
  69 +      if (!intr_context ()
  70 +          && max->priority > thread_get_priority ()
  71 +          && old_level == INTR_ON)
  72 +        thread_yield ();
  73 +    }
  74    intr_set_level (old_level);
  75  }
  76
  77 @@ -166,6 +188,21 @@ lock_init (struct lock *lock, const char
  78    sema_init (&lock->semaphore, 1, name);
  79  }
  80
  81 +static void
  82 +revise_priority (struct thread *t)
  83 +{
  84 +  list_elem *e;
  85 +
  86 +  t->priority = t->normal_priority;
  87 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
  88 +       e = list_next (e))
  89 +    {
  90 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
  91 +      if (donor->priority > t->priority)
  92 +        t->priority = donor->priority;
  93 +    }
  94 +}
  95 +
  96  /* Acquires LOCK, sleeping until it becomes available if
  97     necessary.  The lock must not already be held by the current
  98     thread.
  99 @@ -184,6 +221,17 @@ lock_acquire (struct lock *lock)
 100    ASSERT (!lock_held_by_current_thread (lock));
 101
 102    old_level = intr_disable ();
 103 +
 104 +  if (lock->holder != NULL)
 105 +    {
 106 +      struct thread *donor = thread_current ();
 107 +      donor->want_lock = lock;
 108 +      donor->donee = lock->holder;
 109 +      list_push_back (&lock->holder->donors, &donor->donor_elem);
 110 +      revise_priority (lock->holder);
 111 +      //recurse_donation (&lock->holder);
 112 +    }
 113 +
 114    sema_down (&lock->semaphore);
 115    lock->holder = thread_current ();
 116    intr_set_level (old_level);
 117 @@ -198,13 +246,32 @@ void
 118  lock_release (struct lock *lock)
 119  {
 120    enum intr_level old_level;
 121 +  struct thread *t = thread_current ();
 122 +  list_elem *e, *next;
 123 +  bool did_donate = false;
 124
 125    ASSERT (lock != NULL);
 126    ASSERT (lock_held_by_current_thread (lock));
 127
 128    old_level = intr_disable ();
 129 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
 130 +       e = next)
 131 +    {
 132 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
 133 +      next = list_next (e);
 134 +      if (donor->want_lock == lock)
 135 +        {
 136 +          donor->donee = NULL;
 137 +          list_remove (e);
 138 +          did_donate = true;
 139 +        }
 140 +    }
 141 +  revise_priority (t);
 142    lock->holder = NULL;
 143 +
 144    sema_up (&lock->semaphore);
 145 +  if (did_donate)
 146 +    thread_yield ();
 147    intr_set_level (old_level);
 148  }
 149
 150 Index: threads/thread.c
 151 ===================================================================
 152 RCS file: /u/blp/cvs/pintos/src/threads/thread.c,v
 153 retrieving revision 1.48
 154 diff -u -p -u -r1.48 thread.c
 155 --- threads/thread.c    9 Oct 2004 18:01:37 -0000       1.48
 156 +++ threads/thread.c    11 Oct 2004 07:29:35 -0000
 157 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
 158
 159    /* Add to run queue. */
 160    thread_unblock (t);
 161 +  if (priority > thread_get_priority ())
 162 +    thread_yield ();
 163
 164    return tid;
 165  }
 166 @@ -186,6 +188,16 @@ thread_block (void)
 167    schedule ();
 168  }
 169
 170 +static bool
 171 +thread_greater_priority (const list_elem *a_, const list_elem *b_,
 172 +                         void *aux UNUSED)
 173 +{
 174 +  const struct thread *a = list_entry (a_, struct thread, elem);
 175 +  const struct thread *b = list_entry (b_, struct thread, elem);
 176 +
 177 +  return a->priority > b->priority;
 178 +}
 179 +
 180  /* Transitions a blocked thread T to the ready-to-run state.
 181     This is an error if T is not blocked.  (Use thread_yield() to
 182     make the running thread ready.) */
 183 @@ -198,7 +210,7 @@ thread_unblock (struct thread *t)
 184
 185    old_level = intr_disable ();
 186    ASSERT (t->status == THREAD_BLOCKED);
 187 -  list_push_back (&ready_list, &t->elem);
 188 +  list_insert_ordered (&ready_list, &t->elem, thread_greater_priority, NULL);
 189    t->status = THREAD_READY;
 190    intr_set_level (old_level);
 191  }
 192 @@ -266,11 +278,33 @@ thread_yield (void)
 193    ASSERT (!intr_context ());
 194
 195    old_level = intr_disable ();
 196 -  list_push_back (&ready_list, &cur->elem);
 197 +  list_insert_ordered (&ready_list, &cur->elem, thread_greater_priority, NULL);
 198    cur->status = THREAD_READY;
 199    schedule ();
 200    intr_set_level (old_level);
 201  }
 202 +
 203 +void
 204 +thread_set_priority (int priority)
 205 +{
 206 +  struct thread *t = thread_current ();
 207 +  int old_priority = t->priority;
 208 +  t->normal_priority = priority;
 209 +  if (t->normal_priority > t->priority)
 210 +    t->priority = t->normal_priority;
 211 +  if (priority < old_priority)
 212 +    {
 213 +      /* FIXME: if this is still (one of) the highest priority
 214 +         threads then don't yield. */
 215 +      thread_yield ();
 216 +    }
 217 +}
 218 +
 219 +int
 220 +thread_get_priority (void)
 221 +{
 222 +  return thread_current ()->priority;
 223 +}
 224  \f
 225  /* Idle thread.  Executes when no other thread is ready to run. */
 226  static void
 227 @@ -335,8 +369,9 @@ init_thread (struct thread *t, const cha
 228    t->status = THREAD_BLOCKED;
 229    strlcpy (t->name, name, sizeof t->name);
 230    t->stack = (uint8_t *) t + PGSIZE;
 231 -  t->priority = priority;
 232 +  t->priority = t->normal_priority = priority;
 233    t->magic = THREAD_MAGIC;
 234 +  list_init (&t->donors);
 235  }
 236
 237  /* Allocates a SIZE-byte frame at the top of thread T's stack and
 238 Index: threads/thread.h
 239 ===================================================================
 240 RCS file: /u/blp/cvs/pintos/src/threads/thread.h,v
 241 retrieving revision 1.28
 242 diff -u -p -u -r1.28 thread.h
 243 --- threads/thread.h    29 Sep 2004 01:04:20 -0000      1.28
 244 +++ threads/thread.h    11 Oct 2004 07:29:35 -0000
 245 @@ -88,6 +88,13 @@ struct thread
 246      char name[16];                      /* Name (for debugging purposes). */
 247      uint8_t *stack;                     /* Saved stack pointer. */
 248      int priority;                       /* Priority. */
 249 +    int normal_priority;                /* Priority. */
 250 +
 251 +    /* Priority donation. */
 252 +    struct list donors;
 253 +    list_elem donor_elem;
 254 +    struct thread *donee;
 255 +    struct lock *want_lock;
 256
 257      /* Shared between thread.c and synch.c. */
 258      list_elem elem;                     /* List element. */