Support accurate short delays in the timer code, to speed up disk

access.  (Before, a "400 ns" sleep took up to 1/TIMER_FREQ seconds.
Now it should be an accurate delays.)

Update projects, tour.

diff --git a/doc/threads.texi b/doc/threads.texi
index 2e0032657560c8be1799fcb5b8906e1beb8ce077..49183be9c6027536815b01b835a5bb700bb23083 100644 (file)
--- a/doc/threads.texi
+++ b/doc/threads.texi
@@ -387,11 +387,17 @@ advanced far enough.  This is undesirable because it wastes time that
 could potentially be used more profitably by another thread.  Your
 solution should not busy wait.
 
 could potentially be used more profitably by another thread.  Your
 solution should not busy wait.
 

-The argument to @func{timer_sleep} is expressed in timer ticks, not
-in milliseconds or another unit.  There are @code{TIMER_FREQ} timer
+The argument to @func{timer_sleep} is expressed in timer ticks, not in
+milliseconds or any another unit.  There are @code{TIMER_FREQ} timer

 ticks per second, where @code{TIMER_FREQ} is a macro defined in
 @code{devices/timer.h}.
 
 ticks per second, where @code{TIMER_FREQ} is a macro defined in
 @code{devices/timer.h}.
 

+Separate functions @func{timer_msleep}, @func{timer_usleep}, and
+@func{timer_nsleep} do exist for sleeping a specific number of
+milliseconds, microseconds, or nanoseconds, respectively, but these will
+call @func{timer_sleep} automatically when necessary.  You do not need
+to modify them.
+

 If your delays seem too short or too long, reread the explanation of the
 @option{-r} option to @command{pintos} (@pxref{Debugging versus
 Testing}).
 If your delays seem too short or too long, reread the explanation of the
 @option{-r} option to @command{pintos} (@pxref{Debugging versus
 Testing}).

diff --git a/doc/tour.texi b/doc/tour.texi
index ee90cca0f55d22b0896bcc144a35416624655a8f..e9ba008f89ef9a15843dac2875e423b3f1ceefb7 100644 (file)
--- a/doc/tour.texi
+++ b/doc/tour.texi
@@ -173,7 +173,8 @@ and @func{syscall_init}.
 Now that interrupts are set up, we can start preemptively scheduling
 threads with @func{thread_start}, which also enables interrupts.
 Interrupt-driven serial port I/O is also possible now, so we use
 Now that interrupts are set up, we can start preemptively scheduling
 threads with @func{thread_start}, which also enables interrupts.
 Interrupt-driven serial port I/O is also possible now, so we use

-@func{serial_init_queue} to switch to that mode.
+@func{serial_init_queue} to switch to that mode.  Finally,
+@func{timer_calibrate} calibrates the timer for accurate short delays.

 
 If the filesystem is compiled in, as it will be in project 2 and
 later, we now initialize the disks with @func{disk_init}, then the
 
 If the filesystem is compiled in, as it will be in project 2 and
 later, we now initialize the disks with @func{disk_init}, then the

diff --git a/src/devices/disk.c b/src/devices/disk.c
index 206f69c91feceed3f6a5eef2776f1c8e34a8521b..971f3af537288f38523d92e0807e2489870e33f6 100644 (file)
--- a/src/devices/disk.c
+++ b/src/devices/disk.c
@@ -285,12 +285,12 @@ reset_channel (struct channel *c)
   /* Issue soft reset sequence, which selects device 0 as a side effect.
      Also enable interrupts. */
   outb (reg_ctl (c), 0);
   /* Issue soft reset sequence, which selects device 0 as a side effect.
      Also enable interrupts. */
   outb (reg_ctl (c), 0);

-  timer_sleep (timer_us2ticks (10));
+  timer_usleep (10);

   outb (reg_ctl (c), CTL_SRST);
   outb (reg_ctl (c), CTL_SRST);

-  timer_sleep (timer_us2ticks (10));
+  timer_usleep (10);

   outb (reg_ctl (c), 0);
 
   outb (reg_ctl (c), 0);
 

-  timer_sleep (timer_ms2ticks (150));
+  timer_msleep (150);

 
   /* Wait for device 0 to clear BSY. */
   if (present[0]) 
 
   /* Wait for device 0 to clear BSY. */
   if (present[0]) 


@@ -309,7 +309,7 @@ reset_channel (struct channel *c)
         {
           if (inb (reg_nsect (c)) == 1 && inb (reg_lbal (c)) == 1)
             break;
         {
           if (inb (reg_nsect (c)) == 1 && inb (reg_lbal (c)) == 1)
             break;

-          timer_sleep (timer_ms2ticks (10));
+          timer_msleep (10);

         }
       wait_while_busy (&c->devices[1]);
     }
         }
       wait_while_busy (&c->devices[1]);
     }


@@ -475,7 +475,7 @@ wait_until_idle (const struct disk *d)
     {
       if ((inb (reg_status (d->channel)) & (STA_BSY | STA_DRQ)) == 0)
         return;
     {
       if ((inb (reg_status (d->channel)) & (STA_BSY | STA_DRQ)) == 0)
         return;

-      timer_sleep (timer_us2ticks (10));
+      timer_usleep (10);

     }
 
   printf ("%s: idle timeout\n", d->name);
     }
 
   printf ("%s: idle timeout\n", d->name);


@@ -501,7 +501,7 @@ wait_while_busy (const struct disk *d)
             printf ("ok\n");
           return (inb (reg_alt_status (c)) & STA_DRQ) != 0;
         }
             printf ("ok\n");
           return (inb (reg_alt_status (c)) & STA_DRQ) != 0;
         }

-      timer_sleep (timer_ms2ticks (10));
+      timer_msleep (10);

     }
 
   printf ("failed\n");
     }
 
   printf ("failed\n");


@@ -518,7 +518,7 @@ select_device (const struct disk *d)
     dev |= DEV_DEV;
   outb (reg_device (c), dev);
   inb (reg_alt_status (c));
     dev |= DEV_DEV;
   outb (reg_device (c), dev);
   inb (reg_alt_status (c));

-  timer_sleep (timer_ns2ticks (400));
+  timer_nsleep (400);

 }
 
 /* Select disk D in its channel, as select_device(), but wait for
 }
 
 /* Select disk D in its channel, as select_device(), but wait for

diff --git a/src/devices/timer.c b/src/devices/timer.c
index ecf6c5aacdfee97c6577c8b60912475ef99e4e77..3724abf944ab4fbf7d53936cdbe822a2a7b9a5a5 100644 (file)
--- a/src/devices/timer.c
+++ b/src/devices/timer.c
@@ -23,7 +23,14 @@
 /* Number of timer ticks since OS booted. */
 static volatile int64_t ticks;
 
 /* Number of timer ticks since OS booted. */
 static volatile int64_t ticks;
 

+/* Number of loops per timer tick.
+   Initialized by timer_calibrate(). */
+static unsigned loops_per_tick;
+

 static intr_handler_func timer_interrupt;
 static intr_handler_func timer_interrupt;

+static bool too_many_loops (unsigned loops);
+static void busy_wait (int64_t loops);
+static void real_time_sleep (int64_t num, int32_t denom);

 
 /* Sets up the 8254 Programmable Interval Timer (PIT) to
    interrupt PIT_FREQ times per second, and registers the
 
 /* Sets up the 8254 Programmable Interval Timer (PIT) to
    interrupt PIT_FREQ times per second, and registers the


@@ -42,6 +49,30 @@ timer_init (void)
   intr_register (0x20, 0, INTR_OFF, timer_interrupt, "8254 Timer");
 }
 
   intr_register (0x20, 0, INTR_OFF, timer_interrupt, "8254 Timer");
 }
 

+/* Calibrates loops_per_tick, used to implement brief delays. */
+void
+timer_calibrate (void) 
+{
+  unsigned high_bit, test_bit;
+
+  ASSERT (intr_get_level () == INTR_ON);
+  printf ("Calibrating timer...  ");
+
+  /* Approximate loops_per_tick as the largest power-of-two
+     still less than one timer tick. */
+  loops_per_tick = 1u << 10;
+  while (!too_many_loops (loops_per_tick << 1))
+    loops_per_tick <<= 1;
+
+  /* Refine the next 8 bits of loops_per_tick. */
+  high_bit = loops_per_tick;
+  for (test_bit = high_bit >> 1; test_bit != high_bit >> 10; test_bit >>= 1)
+    if (!too_many_loops (high_bit | test_bit))
+      loops_per_tick |= test_bit;
+
+  printf ("%'"PRIu64" loops/s.\n", (uint64_t) loops_per_tick * TIMER_FREQ);
+}
+

 /* Returns the number of timer ticks since the OS booted. */
 int64_t
 timer_ticks (void) 
 /* Returns the number of timer ticks since the OS booted. */
 int64_t
 timer_ticks (void) 


@@ -71,29 +102,25 @@ timer_sleep (int64_t ticks)
     thread_yield ();
 }
 
     thread_yield ();
 }
 

-/* Returns MS milliseconds in timer ticks, rounding up. */
-int64_t
-timer_ms2ticks (int64_t ms) 
+/* Suspends execution for approximately MS milliseconds. */
+void
+timer_msleep (int64_t ms) 

 {
 {

-  /*       MS / 1000 s          
-     ------------------------ = MS * TIMER_FREQ / 1000 ticks. 
-     (1 / TIMER_FREQ) ticks/s
-  */
-  return DIV_ROUND_UP (ms * TIMER_FREQ, 1000);
+  real_time_sleep (ms, 1000);

 }
 
 }
 

-/* Returns US microseconds in timer ticks, rounding up. */
-int64_t
-timer_us2ticks (int64_t us) 
+/* Suspends execution for approximately US microseconds. */
+void
+timer_usleep (int64_t us) 

 {
 {

-  return DIV_ROUND_UP (us * TIMER_FREQ, 1000000);
+  real_time_sleep (us, 1000 * 1000);

 }
 
 }
 

-/* Returns NS nanoseconds in timer ticks, rounding up. */
-int64_t
-timer_ns2ticks (int64_t ns) 
+/* Suspends execution for approximately NS nanoseconds. */
+void
+timer_nsleep (int64_t ns) 

 {
 {

-  return DIV_ROUND_UP (ns * TIMER_FREQ, 1000000000);
+  real_time_sleep (ns, 1000 * 1000 * 1000);

 }
 
 /* Prints timer statistics. */
 }
 
 /* Prints timer statistics. */


@@ -112,3 +139,68 @@ timer_interrupt (struct intr_frame *args UNUSED)
   if (ticks % TIME_SLICE == 0)
     intr_yield_on_return ();
 }
   if (ticks % TIME_SLICE == 0)
     intr_yield_on_return ();
 }

+
+/* Returns true if LOOPS iterations waits for more than one timer
+   tick, otherwise false. */
+static bool
+too_many_loops (unsigned loops) 
+{
+  int64_t start;
+
+  /* Wait for a timer tick. */
+  start = ticks;
+  while (ticks == start)
+    continue;
+
+  /* Run LOOPS loops. */
+  start = ticks;
+  busy_wait (loops);
+
+  /* If the tick count changed, we iterated too long. */
+  return start != ticks;
+}
+
+/* Iterates through a simple loop LOOPS times, for implementing
+   brief delays.
+
+   Marked NO_INLINE because code alignment can significantly
+   affect timings, so that if this function was inlined
+   differently in different places the results would be difficult
+   to predict. */
+static void NO_INLINE
+busy_wait (int64_t loops) 
+{
+  while (loops-- > 0)
+    continue;
+}
+
+/* Sleep for approximately NUM/DENOM seconds. */
+static void
+real_time_sleep (int64_t num, int32_t denom) 
+{
+  /* Convert NUM/DENOM seconds into timer ticks, rounding down.
+          
+        (NUM / DENOM) s          
+     ---------------------- = NUM * TIMER_FREQ / DENOM ticks. 
+     1 s / TIMER_FREQ ticks
+  */
+  int64_t ticks = num * TIMER_FREQ / denom;
+
+  ASSERT (intr_get_level () == INTR_ON);
+  if (ticks > 0)
+    {
+      /* We're waiting for at least one full timer tick.  Use
+         timer_sleep() because it will yield the CPU to other
+         processes. */                
+      timer_sleep (ticks); 
+    }
+  else 
+    {
+      /* Otherwise, use a busy-wait loop for more accurate
+         sub-tick timing.  We scale the numerator and denominator
+         down by 1000 to avoid the possibility of overflow. */
+      ASSERT (denom % 1000 == 0);
+      busy_wait (loops_per_tick * num / 1000 * TIMER_FREQ / (denom / 1000)); 
+    }
+}
+

diff --git a/src/devices/timer.h b/src/devices/timer.h
index 59f7c9a57835dc6fbc523b47c4cdd3d086119a17..45a3f72e1127cd02f97b79d995277bec67a0812f 100644 (file)
--- a/src/devices/timer.h
+++ b/src/devices/timer.h
@@ -8,14 +8,15 @@
 #define TIMER_FREQ 100
 
 void timer_init (void);
 #define TIMER_FREQ 100
 
 void timer_init (void);

+void timer_calibrate (void);
+

 int64_t timer_ticks (void);
 int64_t timer_elapsed (int64_t);
 
 void timer_sleep (int64_t ticks);
 int64_t timer_ticks (void);
 int64_t timer_elapsed (int64_t);
 
 void timer_sleep (int64_t ticks);

-
-int64_t timer_ms2ticks (int64_t ms);
-int64_t timer_us2ticks (int64_t us);
-int64_t timer_ns2ticks (int64_t ns);
+void timer_msleep (int64_t milliseconds);
+void timer_usleep (int64_t microseconds);
+void timer_nsleep (int64_t nanoseconds);

 
 void timer_print_stats (void);
 
 
 void timer_print_stats (void);
 

diff --git a/src/threads/init.c b/src/threads/init.c
index 741f0e42e4339b8824f16646aae237de0f365dc0..1135ae7ccecc79ad1593671c7e3bbd906c31caa1 100644 (file)
--- a/src/threads/init.c
+++ b/src/threads/init.c
@@ -105,6 +105,7 @@ main (void)
   /* Start thread scheduler and enable interrupts. */
   thread_start ();
   serial_init_queue ();
   /* Start thread scheduler and enable interrupts. */
   thread_start ();
   serial_init_queue ();

+  timer_calibrate ();

 
 #ifdef FILESYS
   /* Initialize filesystem. */
 
 #ifdef FILESYS
   /* Initialize filesystem. */