From 1a39d0619947a0a3cda8322e5856975ba46c602d Mon Sep 17 00:00:00 2001 From: manuel Date: Mon, 26 Mar 2012 22:05:09 +0200 Subject: - rename alarm list/tick to wakeup list/tick - order wakeup list by wakeup tick in ascending order which allows to bail out early inside timer_interrupt --- pintos-progos/devices/timer.c | 40 +++++++++++++++++++++++++++------------- pintos-progos/threads/thread.h | 10 +++++----- proj0.txt | 11 ++++++++--- 3 files changed, 40 insertions(+), 21 deletions(-) diff --git a/pintos-progos/devices/timer.c b/pintos-progos/devices/timer.c index bf78351..3533fe7 100644 --- a/pintos-progos/devices/timer.c +++ b/pintos-progos/devices/timer.c @@ -30,16 +30,16 @@ 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); -/* list of processes waiting for an alarm event +/* list of processes waiting for an wakeup event * and currently put to sleep */ -static struct list alarm_list; +static struct list wakeup_list; /* Sets up the timer to interrupt TIMER_FREQ times per second, and registers the corresponding interrupt. */ void timer_init (void) { - list_init (&alarm_list); + list_init (&wakeup_list); pit_configure_channel (0, 2, TIMER_FREQ); intr_register_ext (0x20, timer_interrupt, "8254 Timer"); } @@ -89,6 +89,16 @@ timer_elapsed (int64_t then) return timer_ticks () - then; } +/* Comparison function for our ascending ordered wakeup list. */ +static bool +wakeup_list_cmp_less(const struct list_elem *a, const struct list_elem *b, + void *AUX UNUSED) +{ + struct thread *t1 = list_entry (a, struct thread, elem); + struct thread *t2 = list_entry (b, struct thread, elem); + return (t1->wakeup_tick < t2->wakeup_tick); +} + /* Sleeps for approximately TICKS timer ticks. Interrupts must be turned on. */ void @@ -97,20 +107,22 @@ timer_sleep (int64_t ticks) struct thread *t = thread_current (); enum intr_level old_level; + ASSERT (intr_get_level () == INTR_ON); + /* nothing to sleep here */ if (ticks <= 0) return; - t->alarm_tick = timer_ticks () + ticks; + t->wakeup_tick = timer_ticks () + ticks; - /* add thread to alarm list + /* add thread to sorted wakeup list * disable interrupts as this is critical */ old_level = intr_disable (); ASSERT (t->status == THREAD_RUNNING); - list_push_back (&alarm_list, &t->elem); + list_insert_ordered (&wakeup_list, &t->elem, &wakeup_list_cmp_less, NULL); /* block the thread */ - thread_block(); + thread_block (); /* restore interrupt */ intr_set_level (old_level); @@ -195,19 +207,21 @@ timer_interrupt (struct intr_frame *args UNUSED) ticks++; thread_tick (); - /* check for threads waiting for an alarm event */ - for (el = list_begin (&alarm_list); el != list_end (&alarm_list); el = next) + /* Check threads waiting to get woken up/unblocked. + * Since this is an ordered list we can bail out as soon + * as the first element doesn't need to get unblocked. */ + for (el = list_begin (&wakeup_list); el != list_end (&wakeup_list); el = next) { struct thread *t = list_entry (el, struct thread, elem); - if (t->alarm_tick == timer_ticks ()) + if (t->wakeup_tick == timer_ticks ()) { next = list_remove (el); /* unblock must be called AFTER removing, - * as thread_unblock() will reuse thread.elem */ + * as thread_unblock() will reuse t.elem */ thread_unblock (t); + continue; } - else - next = list_next (el); + break; } } diff --git a/pintos-progos/threads/thread.h b/pintos-progos/threads/thread.h index 9cc5ef7..4ba5ef2 100644 --- a/pintos-progos/threads/thread.h +++ b/pintos-progos/threads/thread.h @@ -77,12 +77,12 @@ typedef int tid_t; value, triggering the assertion. */ /* The `elem' member has a dual purpose. It can be an element in the run queue (thread.c), it can be an element in a semaphore - wait list (synch.c), or it can be an element in the alarm sleep - list (timer.c). It can be used these two ways only because they + wait list (synch.c), or it can be an element in the timer/alarm sleep + list (timer.c). It can be used these three ways only because they are mutually exclusive: only a thread in the ready state is on the run queue, only a thread in the blocked state is on a semaphore - wait list, whereas only a thread waiting for an alarm event is on - the alarm sleep list. */ + wait list, whereas only a thread waiting for an timer/alarm event is on + the timer/alarm sleep list. */ struct thread { /* Owned by thread.c. */ @@ -106,7 +106,7 @@ struct thread /* Owned by thread.c. */ unsigned magic; /* Detects stack overflow. */ - int64_t alarm_tick; /* absolute tick when to trigger an alarm event */ + int64_t wakeup_tick; /* absolute tick when to wake up the thread */ }; /* If false (default), use round-robin scheduler. diff --git a/proj0.txt b/proj0.txt index 8cdfb49..7284b9e 100644 --- a/proj0.txt +++ b/proj0.txt @@ -32,19 +32,24 @@ TODO >> enumeration. Identify the purpose of each in 25 words or less. struct thread: -int64_t alarm_tick ...absolute tick when to trigger an alarm event +int64_t wakeup_tick ...absolute tick when to wake up the thread ---- ALGORITHMS ---- >> A2: Briefly describe what happens in a call to timer_sleep(), >> including the effects of the timer interrupt handler. -TODO +In case of a positive tick value we calculate the tick when to awake the +current thread and store that inside the per thread structure. Afterwards +we disable interrupts and insert the thread into our wakup list which is +sorted by wakeup-tick in ascending order. Finally we block the thread +and restore the interrupt value. >> A3: What steps are taken to minimize the amount of time spent in >> the timer interrupt handler? -TODO +We sort our alarm/wake-up list by wakeup-tick value in ascending order. +Thus we can return as soon as the first thread doesn't need to get unblocked. ---- SYNCHRONIZATION ---- -- cgit v1.2.3