From b5f0874cd96ee2a62aabc645b9626c2749cb6a01 Mon Sep 17 00:00:00 2001 From: manuel Date: Mon, 26 Mar 2012 12:54:45 +0200 Subject: initial pintos checkin --- doc/pintos_3.html | 375 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 375 insertions(+) create mode 100644 doc/pintos_3.html (limited to 'doc/pintos_3.html') diff --git a/doc/pintos_3.html b/doc/pintos_3.html new file mode 100644 index 0000000..c90148d --- /dev/null +++ b/doc/pintos_3.html @@ -0,0 +1,375 @@ + + + + + +Pintos Projects: Project 1--Threads + + + + + + + + + + + + + + + + + + + +

[ << ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

+ +

3. Project 1: Threads

+ +

+ +In this assignment, we give you a minimally functional thread system. +Your job is to extend the functionality of this system to gain a +better understanding of synchronization problems. +

+ +You will be working primarily in the threads directory for +this assignment, with some work in the devices directory on the +side. Compilation should be done in the threads directory. +

+ +Before you read the description of this project, you should read all of +the following sections: 1. Introduction, B. Coding Standards, +D. Debugging Tools, and E. Development Tools. You should at least +skim the material from A.1 Loading through A.5 Memory Allocation, especially A.3 Synchronization. +

+ + +

+ +

3.1 Background

+ +

+ +Before you start with project 1, be sure to refresh your knowledge +on the thread subsystem introduced in the last project +(2.1 Understanding Threads). +

+ + +

+ +

3.2 Requirements

+ +

+ + +

+ +

3.2.1 Design Document

+ +

+ +Before you turn in your project, you must copy the +project 1 design document template into your source tree under the name +pintos/src/threads/DESIGNDOC and fill it in. We recommend that +you read the design document template before you start working on the +project. +

+ + +

+ +

3.2.2 Priority Scheduling

+ +

+ +Implement priority scheduling in Pintos. +When a thread is added to the ready list that has a higher priority +than the currently running thread, the current thread should +immediately yield the processor to the new thread. Similarly, when +threads are waiting for a lock, semaphore, or condition variable, the +highest priority waiting thread should be awakened first. A thread +may raise or lower its own priority at any time, but lowering its +priority such that it no longer has the highest priority must cause it +to immediately yield the CPU. +

+ +Thread priorities range from PRI_MIN (0) to PRI_MAX (63). +Lower numbers correspond to lower priorities, so that priority 0 +is the lowest priority and priority 63 is the highest. +The initial thread priority is passed as an argument to +thread_create(). If there's no reason to choose another +priority, use PRI_DEFAULT (31). The PRI_ macros are +defined in threads/thread.h, and you should not change their +values. +

+ +One issue with priority scheduling is "priority inversion". Consider +high, medium, and low priority threads H, M, and L, +respectively. If H needs to wait for L (for instance, for a +lock held by L), and M is on the ready list, then H +will never get the CPU because the low priority thread will not get any +CPU time. A partial fix for this problem is for H to "donate" +its priority to L while L is holding the lock, then recall +the donation once L releases (and thus H acquires) the lock. +

+ +Implement priority donation. You will need to account for all different +situations in which priority donation is required. Be sure to handle +multiple donations, in which multiple priorities are donated to a single +thread. You must also handle nested donation: if H is waiting on +a lock that M holds and M is waiting on a lock that L +holds, then both M and L should be boosted to H's +priority. If necessary, you may impose a reasonable limit on depth of +nested priority donation, such as 8 levels. +

+ +You must implement priority donation for locks. You need not +implement priority donation for the other Pintos synchronization +constructs. You do need to implement priority scheduling in all +cases. +

+ +Finally, implement the following functions that allow a thread to +examine and modify its own priority. Skeletons for these functions are +provided in threads/thread.c. +

+ + +

Function: void thread_set_priority (int new_priority) +: Sets the current thread's priority to new_priority. If the +current thread no longer has the highest priority, yields. +

+ + +

Function: int thread_get_priority (void) +: Returns the current thread's priority. In the presence of priority +donation, returns the higher (donated) priority. +

+ +You need not provide any interface to allow a thread to directly modify +other threads' priorities. +

+ +The priority scheduler is not a necessary for project 2. +

+ + +

+ +

3.3 FAQ

+ +

How much code will I need to write? +

+ +Here's a summary of our reference solution, produced by the +diffstat program. The final row gives total lines inserted +and deleted; a changed line counts as both an insertion and a deletion. +

+ +The reference solution represents just one possible solution. Many +other solutions are also possible and many of those differ greatly from +the reference solution. Some excellent solutions may not modify all the +files modified by the reference solution, and some may modify files not +modified by the reference solution. +

+ +

Doesn't priority scheduling lead to starvation? +

+ +Yes, strict priority scheduling can lead to starvation +because a thread will not run if any higher-priority thread is runnable. +The advanced scheduler introduces a mechanism for dynamically +changing thread priorities. +

+ +Strict priority scheduling is valuable in real-time systems because it +offers the programmer more control over which jobs get processing +time. High priorities are generally reserved for time-critical +tasks. It's not "fair," but it addresses other concerns not +applicable to a general-purpose operating system. +

+ +

What thread should run after a lock has been released? +

+ +When a lock is released, the highest priority thread waiting for that +lock should be unblocked and put on the list of ready threads. The +scheduler should then run the highest priority thread on the ready +list. +

+ +

If the highest-priority thread yields, does it continue running? +

+ +Yes. If there is a single highest-priority thread, it continues +running until it blocks or finishes, even if it calls +thread_yield(). +If multiple threads have the same highest priority, +thread_yield() should switch among them in "round robin" order. +

+ +

What happens to the priority of a donating thread? +

+ +Priority donation only changes the priority of the donee +thread. The donor thread's priority is unchanged. +Priority donation is not additive: if thread A (with priority 5) donates +to thread B (with priority 3), then B's new priority is 5, not 8. +

+ +

Can a thread's priority change while it is on the ready queue? +

+ +Yes. Consider a ready, low-priority thread L that holds a lock. +High-priority thread H attempts to acquire the lock and blocks, +thereby donating its priority to ready thread L. +

+ +

Can a thread's priority change while it is blocked? +

+ +Yes. While a thread that has acquired lock L is blocked for any +reason, its priority can increase by priority donation if a +higher-priority thread attempts to acquire L. This case is +checked by the priority-donate-sema test. +

+ +

Can a thread added to the ready list preempt the processor? +

+ +Yes. If a thread added to the ready list has higher priority than the +running thread, the correct behavior is to immediately yield the +processor. It is not acceptable to wait for the next timer interrupt. +The highest priority thread should run as soon as it is runnable, +preempting whatever thread is currently running. +

+ +

How does thread_set_priority() affect a thread receiving donations? +

+ +It sets the thread's base priority. The thread's effective priority +becomes the higher of the newly set priority or the highest donated +priority. When the donations are released, the thread's priority +becomes the one set through the function call. This behavior is checked +by the priority-donate-lower test. +

+ +

Doubled test names in output make them fail. +

+ +Suppose you are seeing output in which some test names are doubled, +like this: +

+ +

(alarm-priority) begin +(alarm-priority) (alarm-priority) Thread priority 30 woke up. +Thread priority 29 woke up. +(alarm-priority) Thread priority 28 woke up. +

+ +What is happening is that output from two threads is being +interleaved. That is, one thread is printing "(alarm-priority) +Thread priority 29 woke up.\n" and another thread is printing +"(alarm-priority) Thread priority 30 woke up.\n", but the first +thread is being preempted by the second in the middle of its output. +

+ +This problem indicates a bug in your priority scheduler. After all, a +thread with priority 29 should not be able to run while a thread with +priority 30 has work to do. +

+ +Normally, the implementation of the printf() function in the +Pintos kernel attempts to prevent such interleaved output by acquiring +a console lock during the duration of the printf call and +releasing it afterwards. However, the output of the test name, +e.g., (alarm-priority), and the message following it is output +using two calls to printf, resulting in the console lock being +acquired and released twice. +

+ +

+ + + + + + + +

[ << ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

+
+ +This document was generated +by on March, 6 2012 +using texi2html + + + + -- cgit v1.2.3