first timer alarm implementation

4 files changed, 76 insertions, 14 deletions

diff --git a/pintos-progos/.gitignore b/pintos-progos/.gitignore
new file mode 100644
index 0000000..e87c613
--- /dev/null
+++ b/pintos-progos/.gitignore
@@ -0,0 +1,6 @@
+intro/bochsout.txt
+intro/bochsrc.txt
+intro/build
+threads/bochsout.txt
+threads/bochsrc.txt
+threads/build
diff --git a/pintos-progos/devices/timer.c b/pintos-progos/devices/timer.c
index befaaae..bf78351 100644
--- a/pintos-progos/devices/timer.c
+++ b/pintos-progos/devices/timer.c
@@ -30,11 +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
+ * and currently put to sleep */
+static struct list alarm_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);
   pit_configure_channel (0, 2, TIMER_FREQ);
   intr_register_ext (0x20, timer_interrupt, "8254 Timer");
 }
@@ -89,11 +94,26 @@ timer_elapsed (int64_t then)
 void
 timer_sleep (int64_t ticks) 
 {
-  int64_t start = timer_ticks ();
+  struct thread *t = thread_current ();
+  enum intr_level old_level;
 
-  ASSERT (intr_get_level () == INTR_ON);
-  while (timer_elapsed (start) < ticks) 
-    thread_yield ();
+  /* nothing to sleep here */
+  if (ticks <= 0)
+    return;
+
+  t->alarm_tick = timer_ticks () + ticks;
+
+  /* add thread to alarm list
+   * disable interrupts as this is critical */
+  old_level = intr_disable ();
+  ASSERT (t->status == THREAD_RUNNING);
+  list_push_back (&alarm_list, &t->elem);
+
+  /* block the thread */
+  thread_block();
+
+  /* restore interrupt */
+  intr_set_level (old_level);
 }
 
 /* Sleeps for approximately MS milliseconds.  Interrupts must be
@@ -170,8 +190,25 @@ timer_print_stats (void)
 static void
 timer_interrupt (struct intr_frame *args UNUSED)
 {
+  struct list_elem *el, *next;
+
   ticks++;
   thread_tick ();
+
+  /* check for threads waiting for an alarm event */
+  for (el = list_begin (&alarm_list); el != list_end (&alarm_list); el = next)
+    {
+      struct thread *t = list_entry (el, struct thread, elem);
+      if (t->alarm_tick == timer_ticks ())
+        {
+          next = list_remove (el);
+          /* unblock must be called AFTER removing,
+           * as thread_unblock() will reuse thread.elem */
+          thread_unblock (t);
+        }
+      else
+        next = list_next (el);
+    }
 }
 
 /* Returns true if LOOPS iterations waits for more than one timer
diff --git a/pintos-progos/threads/thread.h b/pintos-progos/threads/thread.h
index eebf42c..9cc5ef7 100644
--- a/pintos-progos/threads/thread.h
+++ b/pintos-progos/threads/thread.h
@@ -76,11 +76,13 @@ typedef int tid_t;
    set to THREAD_MAGIC.  Stack overflow will normally change this
    value, triggering the assertion. */
 /* The `elem' member has a dual purpose.  It can be an element in
-   the run queue (thread.c), or it can be an element in a
-   semaphore wait list (synch.c).  It can be used these two ways
-   only because they are mutually exclusive: only a thread in the
-   ready state is on the run queue, whereas only a thread in the
-   blocked state is on a semaphore wait list. */
+   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
+   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. */
 struct thread
   {
     /* Owned by thread.c. */
@@ -91,7 +93,7 @@ struct thread
     int priority;                       /* Priority. */
     struct list_elem allelem;           /* List element for all threads list. */
 
-    /* Shared between thread.c and synch.c. */
+    /* Shared between thread.c, synch.c and timer.c. */
     struct list_elem elem;              /* List element. */
 
 #ifdef USERPROG
@@ -103,6 +105,8 @@ struct thread
 
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
+
+    int64_t alarm_tick;                 /* absolute tick when to trigger an alarm event */
   };
 
 /* If false (default), use round-robin scheduler.
diff --git a/proj0.txt b/proj0.txt
index d77cdb9..8cdfb49 100644
--- a/proj0.txt
+++ b/proj0.txt
@@ -3,14 +3,14 @@
                         | PROJECT 0: INTRO   |
                         |   DESIGN DOCUMENT  |
                         +--------------------+
-                                
+
 ---- GROUP ----
 
 >> Fill in the names and email addresses of your group members.
 
-FirstName LastName <email@domain.example>
-FirstName LastName <email@domain.example>
-FirstName LastName <email@domain.example>
+Peter Ketscher <e9651415@mail.student.tuwien.ac.at>
+Karoline Koth <e0326266@student.tuwien.ac.at>
+Manuel Mausz <manuel-uni@mausz.at>
 
 ---- PRELIMINARIES ----
 
@@ -21,6 +21,7 @@ FirstName LastName <email@domain.example>
 >> preparing your submission, other than the Pintos documentation, course
 >> text, lecture notes, and course staff.
 
+TODO
                              ALARM CLOCK
                              ===========
 
@@ -30,27 +31,41 @@ FirstName LastName <email@domain.example>
 >> `struct' member, global or static variable, `typedef', or
 >> 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
+
 ---- ALGORITHMS ----
 
 >> A2: Briefly describe what happens in a call to timer_sleep(),
 >> including the effects of the timer interrupt handler.
 
+TODO
+
 >> A3: What steps are taken to minimize the amount of time spent in
 >> the timer interrupt handler?
 
+TODO
+
 ---- SYNCHRONIZATION ----
 
 >> A4: How are race conditions avoided when multiple threads call
 >> timer_sleep() simultaneously?
 
+TODO
+
 >> A5: How are race conditions avoided when a timer interrupt occurs
 >> during a call to timer_sleep()?
 
+We've disabled the interrupts during list operations.
+
 ---- RATIONALE ----
 
 >> A6: Why did you choose this design?  In what ways is it superior to
 >> another design you considered?
 
+It's very simple, doesn't require any complex structures and memory allocations
+and fulfills the needs of project0.
+
                            ARGUMENT PASSING
                            ================