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

   1 ? solutions/p1-1.patch
   2 Index: src/devices/timer.c
   3 ===================================================================
   4 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/devices/timer.c,v
   5 retrieving revision 1.16
   6 diff -u -p -u -r1.16 timer.c
   7 --- src/devices/timer.c 13 Dec 2004 22:42:01 -0000      1.16
   8 +++ src/devices/timer.c 31 Dec 2004 07:12:25 -0000
   9 @@ -27,6 +27,9 @@ static volatile int64_t ticks;
  10     Initialized by timer_calibrate(). */
  11  static unsigned loops_per_tick;
  12
  13 +/* Threads waiting in timer_sleep(). */
  14 +static struct list wait_list;
  15 +
  16  static intr_handler_func timer_interrupt;
  17  static bool too_many_loops (unsigned loops);
  18  static void busy_wait (int64_t loops);
  19 @@ -47,6 +50,8 @@ timer_init (void)
  20    outb (0x40, count >> 8);
  21
  22    intr_register (0x20, 0, INTR_OFF, timer_interrupt, "8254 Timer");
  23 +
  24 +  list_init (&wait_list);
  25  }
  26
  27  /* Calibrates loops_per_tick, used to implement brief delays. */
  28 @@ -91,15 +96,35 @@ timer_elapsed (int64_t then)
  29    return timer_ticks () - then;
  30  }
  31
  32 +/* Compares two threads based on their wake-up times. */
  33 +static bool
  34 +compare_threads_by_wakeup_time (const list_elem *a_, const list_elem *b_,
  35 +                                void *aux UNUSED)
  36 +{
  37 +  const struct thread *a = list_entry (a_, struct thread, timer_elem);
  38 +  const struct thread *b = list_entry (b_, struct thread, timer_elem);
  39 +
  40 +  return a->wakeup_time < b->wakeup_time;
  41 +}
  42 +
  43  /* Suspends execution for approximately TICKS timer ticks. */
  44  void
  45  timer_sleep (int64_t ticks)
  46  {
  47 -  int64_t start = timer_ticks ();
  48 +  struct thread *t = thread_current ();
  49 +
  50 +  /* Schedule our wake-up time. */
  51 +  t->wakeup_time = timer_ticks () + ticks;
  52
  53 +  /* Atomically insert the current thread into the wait list. */
  54    ASSERT (intr_get_level () == INTR_ON);
  55 -  while (timer_elapsed (start) < ticks)
  56 -    thread_yield ();
  57 +  intr_disable ();
  58 +  list_insert_ordered (&wait_list, &t->timer_elem,
  59 +                       compare_threads_by_wakeup_time, NULL);
  60 +  intr_enable ();
  61 +
  62 +  /* Wait. */
  63 +  sema_down (&t->timer_sema);
  64  }
  65
  66  /* Suspends execution for approximately MS milliseconds. */
  67 @@ -138,6 +163,16 @@ timer_interrupt (struct intr_frame *args
  68    thread_tick ();
  69    if (ticks % TIME_SLICE == 0)
  70      intr_yield_on_return ();
  71 +
  72 +  while (!list_empty (&wait_list))
  73 +    {
  74 +      struct thread *t = list_entry (list_front (&wait_list),
  75 +                                     struct thread, timer_elem);
  76 +      if (ticks < t->wakeup_time)
  77 +        break;
  78 +      sema_up (&t->timer_sema);
  79 +      list_pop_front (&wait_list);
  80 +    }
  81  }
  82
  83  /* Returns true if LOOPS iterations waits for more than one timer
  84 Index: src/threads/thread.c
  85 ===================================================================
  86 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v
  87 retrieving revision 1.48
  88 diff -u -p -u -r1.48 thread.c
  89 --- src/threads/thread.c        9 Oct 2004 18:01:37 -0000       1.48
  90 +++ src/threads/thread.c        31 Dec 2004 07:12:26 -0000
  91 @@ -337,6 +337,7 @@ init_thread (struct thread *t, const cha
  92    t->stack = (uint8_t *) t + PGSIZE;
  93    t->priority = priority;
  94    t->magic = THREAD_MAGIC;
  95 +  sema_init (&t->timer_sema, 0, "timer");
  96  }
  97
  98  /* Allocates a SIZE-byte frame at the top of thread T's stack and
  99 Index: src/threads/thread.h
 100 ===================================================================
 101 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v
 102 retrieving revision 1.28
 103 diff -u -p -u -r1.28 thread.h
 104 --- src/threads/thread.h        29 Sep 2004 01:04:20 -0000      1.28
 105 +++ src/threads/thread.h        31 Dec 2004 07:12:26 -0000
 106 @@ -4,6 +4,7 @@
 107  #include <debug.h>
 108  #include <list.h>
 109  #include <stdint.h>
 110 +#include "threads/synch.h"
 111
 112  /* States in a thread's life cycle. */
 113  enum thread_status
 114 @@ -91,6 +92,11 @@ struct thread
 115
 116      /* Shared between thread.c and synch.c. */
 117      list_elem elem;                     /* List element. */
 118 +
 119 +    /* Problem 1-1. */
 120 +    int64_t wakeup_time;                /* Time to wake this thread up. */
 121 +    list_elem timer_elem;               /* Element in timer_wait_list. */
 122 +    struct semaphore timer_sema;        /* Semaphore. */
 123
 124  #ifdef USERPROG
 125      /* Owned by userprog/process.c. */