- Official site
- CS162 Spring 2015 Materials
- HW1
- Section 2: Processes - My Solution
- Section 3: thread - My Solution
- CS 162 Project 1:Threads
- Pintos Guide
- Due: 2/18
- For the first checkpoint, the following code features will be due
- (5 points) A completely working Alarm Clock implementation that passes all our given tests, and a priority scheduler that passes all non-donation tests.
- (10 points) An initial design document that details how you will implement the alarm clock, priority scheduler with priority donation, and the advanced scheduler.
- (10 points) Your design review with your TA (being able to answer questions about the project)
- Due: 3/04
- (50 points) A fully functional alarm, priority scheduler, and advanced scheduler.
- (10 points) Good design and clean code through out your entire project
- Due: 3/06
- (10 points) Final Report (A cleaned up version of your initial design document)
=============================================================================================================
Reimplement timer_sleep(), defined in devices/timer.c Although a working implementation is provided, it “busy waits,” that is, it spins in a loop checking the current time and calling thread_yield() until enough time has gone by. Reimplement it to avoid busy waiting.
Suspends execution of the calling thread until time has advanced by at least x timer ticks. Unless the system is otherwise idle, the thread need not wake up after exactly x ticks. Just put it on the ready queue after they have waited for the right amount of time. timer_sleep() is useful for threads that operate in real-time, e.g. for blinking the cursor once per second.
The argument to timer_sleep() is expressed in timer ticks, not in milliseconds or any another unit. There are TIMER_FREQ timer ticks per second, where TIMER_FREQ is a macro defined in devices/timer.h. The default value is 100. We don’t recommend changing this value, because any change is likely to cause many of the tests to fail.
Separate functions timer_msleep(), timer_usleep(), and timer_nsleep() do exist for sleeping a specific number of milliseconds, microseconds, or nanoseconds, respectively, but these will call timer_sleep() automatically when necessary. You do not need to modify them. If your delays seem too short or too long, reread the explanation of the -r option to pintos. The alarm clock implementation is not needed for later projects.
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, fix the following functions that allow a thread to examine and modify its own priority. Skeletons for these functions are provided in threads/thread.c.
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.
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 used in any later project.