From 3d1e18466b44b2de06dd7c00a85e78ed9340906d Mon Sep 17 00:00:00 2001 From: manuel Date: Thu, 3 May 2012 16:18:11 +0200 Subject: initial commit of proj1 including the draft of our (yet empty) design document and the first schedule code mostly submitted by karo and peter --- proj1.txt | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ threads/thread.c | 24 ++++++++++++++-- 2 files changed, 107 insertions(+), 2 deletions(-) create mode 100644 proj1.txt diff --git a/proj1.txt b/proj1.txt new file mode 100644 index 0000000..274ef34 --- /dev/null +++ b/proj1.txt @@ -0,0 +1,85 @@ + +--------------------+ + | CS 140 | + | PROJECT 1: THREADS | + | DESIGN DOCUMENT | + +--------------------+ + +---- GROUP ---- + +>> Fill in the names and email addresses of your group members. + +Peter Ketscher +Karoline Knoth +Manuel Mausz + +---- PRELIMINARIES ---- + +>> If you have any preliminary comments on your submission, notes for the +>> TAs, or extra credit, please give them here. + +>> Please cite any offline or online sources you consulted while +>> preparing your submission, other than the Pintos documentation, course +>> text, lecture notes, and course staff. + +Stallings, W. - Operating Systems +http://en.wikipedia.org/wiki/Priority_inversion +http://hynek.me/studies/sched_ausarbeitung.pdf + + PRIORITY SCHEDULING + =================== + +---- DATA STRUCTURES ---- + +>> B1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. + +>> B2: Explain the data structure used to track priority donation. +>> Use ASCII art to diagram a nested donation. (Alternately, submit a +>> .png file.) + +---- ALGORITHMS ---- + +>> B3: How do you ensure that the highest priority thread waiting for +>> a lock, semaphore, or condition variable wakes up first? + +>> B4: Describe the sequence of events when a call to lock_acquire() +>> causes a priority donation. How is nested donation handled? + +>> B5: Describe the sequence of events when lock_release() is called +>> on a lock that a higher-priority thread is waiting for. + +---- SYNCHRONIZATION ---- + +>> B6: Describe a potential race in thread_set_priority() and explain +>> how your implementation avoids it. Can you use a lock to avoid +>> this race? + +---- RATIONALE ---- + +>> B7: Why did you choose this design? In what ways is it superior to +>> another design you considered? + + SURVEY QUESTIONS + ================ + +Answering these questions is optional, but it will help us improve the +course in future quarters. Feel free to tell us anything you +want--these questions are just to spur your thoughts. You may also +choose to respond anonymously in the course evaluations at the end of +the quarter. + +>> In your opinion, was this assignment, or any one of the three problems +>> in it, too easy or too hard? Did it take too long or too little time? + +>> Did you find that working on a particular part of the assignment gave +>> you greater insight into some aspect of OS design? + +>> Is there some particular fact or hint we should give students in +>> future quarters to help them solve the problems? Conversely, did you +>> find any of our guidance to be misleading? + +>> Do you have any suggestions for the TAs to more effectively assist +>> students, either for future quarters or the remaining projects? + +>> Any other comments? diff --git a/threads/thread.c b/threads/thread.c index 845f059..3fefbd8 100644 --- a/threads/thread.c +++ b/threads/thread.c @@ -71,6 +71,16 @@ static void schedule (void); void thread_schedule_tail (struct thread *prev); static tid_t allocate_tid (void); +//TODO: should take donated priority into account +static bool +ready_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->priority > t2->priority); +} + /* Initializes the threading system by transforming the code that's currently running into a thread. This can't work in general and it is possible in this case only because loader.S @@ -212,6 +222,7 @@ thread_create (const char *name, int priority, /* Add to run queue. */ thread_unblock (t); + thread_yield (); return tid; } @@ -249,7 +260,8 @@ thread_unblock (struct thread *t) old_level = intr_disable (); ASSERT (t->status == THREAD_BLOCKED); - list_push_back (&ready_list, &t->elem); + /* add thread to our ordered ready_list */ + list_insert_ordered (&ready_list, &t->elem, &ready_list_cmp_less, NULL); t->status = THREAD_READY; intr_set_level (old_level); } @@ -320,7 +332,7 @@ thread_yield (void) old_level = intr_disable (); if (cur != idle_thread) - list_push_back (&ready_list, &cur->elem); + list_insert_ordered (&ready_list, &cur->elem, &ready_list_cmp_less, NULL); cur->status = THREAD_READY; schedule (); intr_set_level (old_level); @@ -348,6 +360,14 @@ void thread_set_priority (int new_priority) { thread_current ()->priority = new_priority; + + /* compare priority with the highest priority in the list */ + if (!list_empty (&ready_list)) + { + struct thread *t = list_entry (list_front (&ready_list), struct thread, elem); + if (t->priority > thread_current ()->priority) + thread_yield(); + } } /* Returns the current thread's priority. */ -- cgit v1.2.3