- 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

3 files changed, 40 insertions, 21 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;
     }
 }
 
diff --git a/pintos-progos/threads/thread.h b/pintos-progos/threads/thread.h
index 9cc5ef7..4ba5ef2 100644
--- a/pintos-progos/threads/thread.h
+++ b/pintos-progos/threads/thread.h
@@ -77,12 +77,12 @@ typedef int tid_t;
    value, triggering the assertion. */
 /* The `elem' member has a dual purpose.  It can be an element in
    the run queue (thread.c), it can be an element in a semaphore
-   wait list (synch.c), or it can be an element in the alarm sleep
-   list (timer.c).  It can be used these two ways only because they
+   wait list (synch.c), or it can be an element in the timer/alarm sleep
+   list (timer.c).  It can be used these three ways only because they
    are mutually exclusive: only a thread in the ready state is on
    the run queue, only a thread in the blocked state is on a semaphore
-   wait list, whereas only a thread waiting for an alarm event is on
-   the alarm sleep list. */
+   wait list, whereas only a thread waiting for an timer/alarm event is on
+   the timer/alarm sleep list. */
 struct thread
   {
     /* Owned by thread.c. */
@@ -106,7 +106,7 @@ struct thread
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
 
-    int64_t alarm_tick;                 /* absolute tick when to trigger an alarm event */
+    int64_t wakeup_tick;                /* absolute tick when to wake up the thread */
   };
 
 /* If false (default), use round-robin scheduler.
diff --git a/proj0.txt b/proj0.txt
index 8cdfb49..7284b9e 100644
--- a/proj0.txt
+++ b/proj0.txt
@@ -32,19 +32,24 @@ TODO
 >> enumeration.  Identify the purpose of each in 25 words or less.
 
 struct thread:
-int64_t alarm_tick  ...absolute tick when to trigger an alarm event
+int64_t wakeup_tick  ...absolute tick when to wake up the thread
 
 ---- ALGORITHMS ----
 
 >> A2: Briefly describe what happens in a call to timer_sleep(),
 >> including the effects of the timer interrupt handler.
 
-TODO
+In case of a positive tick value we calculate the tick when to awake the
+current thread and store that inside the per thread structure. Afterwards
+we disable interrupts and insert the thread into our wakup list which is
+sorted by wakeup-tick in ascending order. Finally we block the thread
+and restore the interrupt value.
 
 >> A3: What steps are taken to minimize the amount of time spent in
 >> the timer interrupt handler?
 
-TODO
+We sort our alarm/wake-up list by wakeup-tick value in ascending order.
+Thus we can return as soon as the first thread doesn't need to get unblocked.
 
 ---- SYNCHRONIZATION ----