X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=blobdiff_plain;f=src%2Fdevices%2Ftimer.c;h=70234a808844e425d8309f6cd04c09ce11ad230e;hp=200d58f8251e0b660bd3a4fa49367b337a882857;hb=cc5c971c3cc498d528a2f74f4dc2f8e27a690311;hpb=208fb587faa75eaa0e740db9b605ff3d7ba24905 diff --git a/src/devices/timer.c b/src/devices/timer.c index 200d58f..70234a8 100644 --- a/src/devices/timer.c +++ b/src/devices/timer.c @@ -1,10 +1,15 @@ #include "devices/timer.h" #include +#include #include +#include #include "threads/interrupt.h" #include "threads/io.h" +#include "threads/synch.h" #include "threads/thread.h" +/* See [8254] for hardware details of the 8254 timer chip. */ + #if TIMER_FREQ < 19 #error 8254 timer requires TIMER_FREQ >= 19 #endif @@ -12,16 +17,20 @@ #error TIMER_FREQ <= 1000 recommended #endif -/* Number of timer ticks that a process gets before being - preempted. */ -#define TIME_SLICE 1 - /* Number of timer ticks since OS booted. */ -static volatile int64_t ticks; +static 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 bool too_many_loops (unsigned loops); +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); -/* Sets up the 8254 Programmable Interrupt Timer (PIT) to +/* Sets up the 8254 Programmable Interval Timer (PIT) to interrupt PIT_FREQ times per second, and registers the corresponding interrupt. */ void @@ -35,7 +44,34 @@ timer_init (void) outb (0x40, count & 0xff); outb (0x40, count >> 8); - intr_register (0x20, 0, INTR_OFF, timer_interrupt, "8254 Timer"); + intr_register_ext (0x20, 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; + ASSERT (loops_per_tick != 0); + } + + /* 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. */ @@ -45,6 +81,7 @@ timer_ticks (void) enum intr_level old_level = intr_disable (); int64_t t = ticks; intr_set_level (old_level); + barrier (); return t; } @@ -56,40 +93,86 @@ timer_elapsed (int64_t then) return timer_ticks () - then; } -/* Suspends execution for approximately TICKS timer ticks. */ +/* Sleeps for approximately TICKS timer ticks. Interrupts must + be turned on. */ void timer_sleep (int64_t ticks) { int64_t start = timer_ticks (); + ASSERT (intr_get_level () == INTR_ON); while (timer_elapsed (start) < ticks) - if (intr_get_level () == INTR_ON) - thread_yield (); + thread_yield (); } -/* Returns MS milliseconds in timer ticks, rounding up. */ -int64_t -timer_ms2ticks (int64_t ms) +/* Sleeps for approximately MS milliseconds. Interrupts must be + turned on. */ +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) +/* Sleeps for approximately US microseconds. Interrupts must be + turned on. */ +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) +/* Sleeps for approximately NS nanoseconds. Interrupts must be + turned on. */ +void +timer_nsleep (int64_t ns) +{ + real_time_sleep (ns, 1000 * 1000 * 1000); +} + +/* Busy-waits for approximately MS milliseconds. Interrupts need + not be turned on. + + Busy waiting wastes CPU cycles, and busy waiting with + interrupts off for the interval between timer ticks or longer + will cause timer ticks to be lost. Thus, use timer_msleep() + instead if interrupts are enabled. */ +void +timer_mdelay (int64_t ms) +{ + real_time_delay (ms, 1000); +} + +/* Sleeps for approximately US microseconds. Interrupts need not + be turned on. + + Busy waiting wastes CPU cycles, and busy waiting with + interrupts off for the interval between timer ticks or longer + will cause timer ticks to be lost. Thus, use timer_usleep() + instead if interrupts are enabled. */ +void +timer_udelay (int64_t us) { - return DIV_ROUND_UP (ns * TIMER_FREQ, 1000000000); + real_time_delay (us, 1000 * 1000); +} + +/* Sleeps execution for approximately NS nanoseconds. Interrupts + need not be turned on. + + Busy waiting wastes CPU cycles, and busy waiting with + interrupts off for the interval between timer ticks or longer + will cause timer ticks to be lost. Thus, use timer_nsleep() + instead if interrupts are enabled.*/ +void +timer_ndelay (int64_t ns) +{ + real_time_delay (ns, 1000 * 1000 * 1000); +} + +/* Prints timer statistics. */ +void +timer_print_stats (void) +{ + printf ("Timer: %"PRId64" ticks\n", timer_ticks ()); } /* Timer interrupt handler. */ @@ -97,6 +180,76 @@ static void timer_interrupt (struct intr_frame *args UNUSED) { ticks++; - if (ticks % TIME_SLICE == 0) - intr_yield_on_return (); + thread_tick (); +} + +/* Returns true if LOOPS iterations waits for more than one timer + tick, otherwise false. */ +static bool +too_many_loops (unsigned loops) +{ + /* Wait for a timer tick. */ + int64_t start = ticks; + while (ticks == start) + barrier (); + + /* Run LOOPS loops. */ + start = ticks; + busy_wait (loops); + + /* If the tick count changed, we iterated too long. */ + barrier (); + 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) + barrier (); +} + +/* 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. */ + real_time_delay (num, denom); + } +} + +/* Busy-wait for approximately NUM/DENOM seconds. */ +static void +real_time_delay (int64_t num, int32_t denom) +{ + /* 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)); }