- rename alarm list/tick to wakeup list/tick

- order wakeup list by wakeup tick in ascending order
which allows to bail out early inside timer_interrupt

1 files changed, 27 insertions, 13 deletions

diff --git a/pintos-progos/devices/timer.c b/pintos-progos/devices/timer.c
index bf78351..3533fe7 100644
--- a/pintos-progos/devices/timer.c
+++ b/pintos-progos/devices/timer.c
@@ -30,16 +30,16 @@ static void busy_wait (int64_t loops);
 static void real_time_sleep (int64_t num, int32_t denom);
 static void real_time_delay (int64_t num, int32_t denom);
 
-/* list of processes waiting for an alarm event
+/* list of processes waiting for an wakeup event
  * and currently put to sleep */
-static struct list alarm_list;
+static struct list wakeup_list;
 
 /* Sets up the timer to interrupt TIMER_FREQ times per second,
    and registers the corresponding interrupt. */
 void
 timer_init (void) 
 {
-  list_init (&alarm_list);
+  list_init (&wakeup_list);
   pit_configure_channel (0, 2, TIMER_FREQ);
   intr_register_ext (0x20, timer_interrupt, "8254 Timer");
 }
@@ -89,6 +89,16 @@ timer_elapsed (int64_t then)
   return timer_ticks () - then;
 }
 
+/* Comparison function for our ascending ordered wakeup list. */
+static bool
+wakeup_list_cmp_less(const struct list_elem *a, const struct list_elem *b,
+  void *AUX UNUSED)
+{
+  struct thread *t1 = list_entry (a, struct thread, elem);
+  struct thread *t2 = list_entry (b, struct thread, elem);
+  return (t1->wakeup_tick < t2->wakeup_tick);
+}
+
 /* Sleeps for approximately TICKS timer ticks.  Interrupts must
    be turned on. */
 void
@@ -97,20 +107,22 @@ timer_sleep (int64_t ticks)
   struct thread *t = thread_current ();
   enum intr_level old_level;
 
+  ASSERT (intr_get_level () == INTR_ON);
+
   /* nothing to sleep here */
   if (ticks <= 0)
     return;
 
-  t->alarm_tick = timer_ticks () + ticks;
+  t->wakeup_tick = timer_ticks () + ticks;
 
-  /* add thread to alarm list
+  /* add thread to sorted wakeup list
    * disable interrupts as this is critical */
   old_level = intr_disable ();
   ASSERT (t->status == THREAD_RUNNING);
-  list_push_back (&alarm_list, &t->elem);
+  list_insert_ordered (&wakeup_list, &t->elem, &wakeup_list_cmp_less, NULL);
 
   /* block the thread */
-  thread_block();
+  thread_block ();
 
   /* restore interrupt */
   intr_set_level (old_level);
@@ -195,19 +207,21 @@ timer_interrupt (struct intr_frame *args UNUSED)
   ticks++;
   thread_tick ();
 
-  /* check for threads waiting for an alarm event */
-  for (el = list_begin (&alarm_list); el != list_end (&alarm_list); el = next)
+  /* Check threads waiting to get woken up/unblocked.
+   * Since this is an ordered list we can bail out as soon
+   * as the first element doesn't need to get unblocked. */
+  for (el = list_begin (&wakeup_list); el != list_end (&wakeup_list); el = next)
     {
       struct thread *t = list_entry (el, struct thread, elem);
-      if (t->alarm_tick == timer_ticks ())
+      if (t->wakeup_tick == timer_ticks ())
         {
           next = list_remove (el);
           /* unblock must be called AFTER removing,
-           * as thread_unblock() will reuse thread.elem */
+           * as thread_unblock() will reuse t.elem */
           thread_unblock (t);
+          continue;
         }
-      else
-        next = list_next (el);
+      break;
     }
 }