keep and use a sorted list of sleeping threads

1 files changed, 18 insertions, 7 deletions

diff --git a/src/devices/timer.c b/src/devices/timer.c
index 5b9e527..856a14e 100644
--- a/src/devices/timer.c
+++ b/src/devices/timer.c
@@ -110,13 +110,22 @@ timer_sleep (int64_t ticks)
 {
   int64_t start = timer_ticks ();
 
-  struct waiting_thread waiting_thread;
-  waiting_thread.tick_target = start + ticks;
-
-  sema_init (&waiting_thread.sema, 0);
-  list_push_back (&waiting_threads, &waiting_thread.elem);
+  struct waiting_thread new_waiting_thread;
+  new_waiting_thread.tick_target = start + ticks;
+  sema_init (&new_waiting_thread.sema, 0);
+
+  struct list_elem *before = list_begin (&waiting_threads);
+  while (before != list_end (&waiting_threads)) {
+    struct list_elem *next = list_next (before);
+    struct waiting_thread *waiting_thread = list_entry (before, struct waiting_thread, elem);
+    if (new_waiting_thread.tick_target < waiting_thread->tick_target) {
+      break;
+    }
+    before = next;
+  }
+  list_insert (before, &new_waiting_thread.elem);
 
-  sema_down (&waiting_thread.sema);
+  sema_down (&new_waiting_thread.sema);
 }
 
 /* Suspends execution for approximately MS milliseconds. */
@@ -161,8 +170,10 @@ timer_interrupt (struct intr_frame *args UNUSED)
     if (ticks >= waiting_thread->tick_target) {
       sema_up (&waiting_thread->sema);
       list_remove (e);
+      e = next;
+    } else {
+      break;
     }
-    e = next;
   }
 }