From 11c1519a12cdae1ce05d31a6e389a103259c6c93 Mon Sep 17 00:00:00 2001 From: manuel Date: Mon, 26 Mar 2012 20:18:23 +0200 Subject: first timer alarm implementation --- pintos-progos/.gitignore | 6 ++++++ pintos-progos/devices/timer.c | 45 ++++++++++++++++++++++++++++++++++++++---- pintos-progos/threads/thread.h | 16 +++++++++------ proj0.txt | 23 +++++++++++++++++---- 4 files changed, 76 insertions(+), 14 deletions(-) create mode 100644 pintos-progos/.gitignore diff --git a/pintos-progos/.gitignore b/pintos-progos/.gitignore new file mode 100644 index 0000000..e87c613 --- /dev/null +++ b/pintos-progos/.gitignore @@ -0,0 +1,6 @@ +intro/bochsout.txt +intro/bochsrc.txt +intro/build +threads/bochsout.txt +threads/bochsrc.txt +threads/build diff --git a/pintos-progos/devices/timer.c b/pintos-progos/devices/timer.c index befaaae..bf78351 100644 --- a/pintos-progos/devices/timer.c +++ b/pintos-progos/devices/timer.c @@ -30,11 +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 + * and currently put to sleep */ +static struct list alarm_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); pit_configure_channel (0, 2, TIMER_FREQ); intr_register_ext (0x20, timer_interrupt, "8254 Timer"); } @@ -89,11 +94,26 @@ timer_elapsed (int64_t then) void timer_sleep (int64_t ticks) { - int64_t start = timer_ticks (); + struct thread *t = thread_current (); + enum intr_level old_level; - ASSERT (intr_get_level () == INTR_ON); - while (timer_elapsed (start) < ticks) - thread_yield (); + /* nothing to sleep here */ + if (ticks <= 0) + return; + + t->alarm_tick = timer_ticks () + ticks; + + /* add thread to alarm list + * disable interrupts as this is critical */ + old_level = intr_disable (); + ASSERT (t->status == THREAD_RUNNING); + list_push_back (&alarm_list, &t->elem); + + /* block the thread */ + thread_block(); + + /* restore interrupt */ + intr_set_level (old_level); } /* Sleeps for approximately MS milliseconds. Interrupts must be @@ -170,8 +190,25 @@ timer_print_stats (void) static void timer_interrupt (struct intr_frame *args UNUSED) { + struct list_elem *el, *next; + ticks++; thread_tick (); + + /* check for threads waiting for an alarm event */ + for (el = list_begin (&alarm_list); el != list_end (&alarm_list); el = next) + { + struct thread *t = list_entry (el, struct thread, elem); + if (t->alarm_tick == timer_ticks ()) + { + next = list_remove (el); + /* unblock must be called AFTER removing, + * as thread_unblock() will reuse thread.elem */ + thread_unblock (t); + } + else + next = list_next (el); + } } /* Returns true if LOOPS iterations waits for more than one timer diff --git a/pintos-progos/threads/thread.h b/pintos-progos/threads/thread.h index eebf42c..9cc5ef7 100644 --- a/pintos-progos/threads/thread.h +++ b/pintos-progos/threads/thread.h @@ -76,11 +76,13 @@ typedef int tid_t; set to THREAD_MAGIC. Stack overflow will normally change this value, triggering the assertion. */ /* The `elem' member has a dual purpose. It can be an element in - the run queue (thread.c), or it can be an element in a - semaphore wait list (synch.c). It can be used these two ways - only because they are mutually exclusive: only a thread in the - ready state is on the run queue, whereas only a thread in the - blocked state is on a semaphore wait list. */ + 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 + 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. */ struct thread { /* Owned by thread.c. */ @@ -91,7 +93,7 @@ struct thread int priority; /* Priority. */ struct list_elem allelem; /* List element for all threads list. */ - /* Shared between thread.c and synch.c. */ + /* Shared between thread.c, synch.c and timer.c. */ struct list_elem elem; /* List element. */ #ifdef USERPROG @@ -103,6 +105,8 @@ struct thread /* Owned by thread.c. */ unsigned magic; /* Detects stack overflow. */ + + int64_t alarm_tick; /* absolute tick when to trigger an alarm event */ }; /* If false (default), use round-robin scheduler. diff --git a/proj0.txt b/proj0.txt index d77cdb9..8cdfb49 100644 --- a/proj0.txt +++ b/proj0.txt @@ -3,14 +3,14 @@ | PROJECT 0: INTRO | | DESIGN DOCUMENT | +--------------------+ - + ---- GROUP ---- >> Fill in the names and email addresses of your group members. -FirstName LastName -FirstName LastName -FirstName LastName +Peter Ketscher +Karoline Koth +Manuel Mausz ---- PRELIMINARIES ---- @@ -21,6 +21,7 @@ FirstName LastName >> preparing your submission, other than the Pintos documentation, course >> text, lecture notes, and course staff. +TODO ALARM CLOCK =========== @@ -30,27 +31,41 @@ FirstName LastName >> `struct' member, global or static variable, `typedef', or >> 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 + ---- ALGORITHMS ---- >> A2: Briefly describe what happens in a call to timer_sleep(), >> including the effects of the timer interrupt handler. +TODO + >> A3: What steps are taken to minimize the amount of time spent in >> the timer interrupt handler? +TODO + ---- SYNCHRONIZATION ---- >> A4: How are race conditions avoided when multiple threads call >> timer_sleep() simultaneously? +TODO + >> A5: How are race conditions avoided when a timer interrupt occurs >> during a call to timer_sleep()? +We've disabled the interrupts during list operations. + ---- RATIONALE ---- >> A6: Why did you choose this design? In what ways is it superior to >> another design you considered? +It's very simple, doesn't require any complex structures and memory allocations +and fulfills the needs of project0. + ARGUMENT PASSING ================ -- cgit v1.2.3