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