Project Assignment #1: Build a Threads System

 

CSE 451

Due April 23, at 11:59pm.

 

In this assignment, we will give you part of a working thread system. Your job is to complete it and then use it to solve several synchronization problems.

 

The first step is to read and understand the partial thread system we’ve provided. This thread system implements thread fork, thread completion, and semaphores for synchronization.

 

Properly synchronized code should work no matter what order the scheduler chooses to run the threads on the ready list. In other words, we should be able to put a call to Thread::Yield() (which causes the scheduler to pick another thread to run) anywhere in your code where interrupts are enabled without changing the correctness of your code. You will be asked to write properly synchronized code as part of later assignments, so understanding how to do this is crucial to being able to do the project.

 

To aid you in this task, code linked in with Nachos will cause Thread::Yield() to be called in a repeatable but unpredictable way. Nachos code is repeatable in that if you call it repeatedly with the same arguments, it will do exactly the same thing each time. However, if you invoke Nachos with “nachos -rs #”, with a different number each time, calls to Thread::Yield() will be inserted in different places in the code.

 

Warning: in our implementation of threads, each thread is assigned a small, fixed-size execution stack.  This may cause bizarre problems (such as segmentation faults at strange lines of code) if you declare large data structures to be automatic variables (e.g., ``int buf[1000];''). You will probably not notice this during the semester, but if you do,

you may change the size of the stack by modifying the StackSize define in switch.h.

 

Although the solutions can be written as normal C routines, you will find organizing your code to be easier if you structure your code as C++ classes.  Also, there should be no busy-waiting in any of your solutions to this assignment.

 

Don’t worry if you don’t have to write much code for each of these: the assignment is largely conceptual and not a programming chore.

 

  1. Implement condition variables using interrupt enable and disable to provide atomicity.

 

  1. Implement synchronous send and receive of one word messages using condition variables.  Create a “Mailbox” class with the operations Mailbox::Send(int message) and Mailbox::Receive(int * Message). Send atomically waits until Receive is called on the same mailbox, and then copies the message into the receive buffer. Once the copy is made, both can return. Similarly, Receive waits until Send is called, at which point the copy is made and both calls return. Your solution should work even if there are multiple senders and receivers for the same mailbox. (Hint: this is equivalent to a zero-length bounded buffer).

 

  1. Implement Thread::Join(). Add a parameter to the thread constructor to indicate whether or not Join will be called on this thread. Your solution should properly delete the thread control block whether or not Join is to be called, and whether or not the forked thread finishes before the Join is called. Note that you do not need to implement Join so that it returns the value returned from the forked thread. You can assume that Join will only be called by a parent thread (e.g. parentThread->Join(childThread)) but remark that in reality, a child thread should be able to join a parent as well.

 

  1. Implement preemptive priority scheduling in Nachos. Priority scheduling is a key building block for real-time systems. Add a call to the Thread class to set the priority of the thread. When a thread is added to the ready list that is a higher priority then the currently running thread, the current thread gives up 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 woken up first.

    An issue with priority scheduling is “priority inversion”. If a high priority thread needs to wait for a low priority thread, such as for a lock held by a low priority thread or for a Join to complete, and a middle priority thread is on the ready list, then the high priority thread will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is to have the waiting thread “donate” its priority to the low priority thread while it is hodling the lock. Although you are not required to implement priority inversion, you need to take it into account when you are testing your preemptive scheduling code. If you are ambitious, implement this.

 

  1. Implement the synchronization for a "lockup-free" cache using condition variables. A lockup-free cache is one that can continue to accept requests, even while it is waiting for a response from memory. This is useful, for instance, if the processor can pre-fetch data into the cache before it is needed; this hides memory latency only if it does not interfere with normal cache accesses.

    The behavior of a lockup-free cache can be modelled with threads, where each thread can ask the cache to read or write the data at some physical memory location. For a read, if the data is cached, the data can be immediately returned. If the data is not cached, the cache must (i) kick something out of the cache to clear space (potentially having to write it back to physical memory if it is dirty), (ii) ask memory to fetch the item, and (iii) when the data returns, put it in the cache and return the data to the original caller. The cache stores data in one unit chunks, so a write request need not read the location in before over-writing. While memory is being queried, the cache can accept requests from the other threads. Of course, the cache is fixed size, so it is possible (although unlikely) that all items in the cache may have been kicked out by earlier requests.

    You are to implement the routines CacheRead(addr) and CacheWrite(addr, val); these routines call MemRead(addr) and MemWrite(addr, val) on a cache miss - you can implement MemRead and MemWrite to just be dummy functions. We are more interested that the cache works correctly than that you have real data.

 

All the code you write should be well commented so we can understand what you changed. To hand in code, one of the members of your project should use the turnin command:

 

To turnin a set of files or directories, run:

 

turnin –ccse451 –pthreads {list of files or directories to turning)

 

For example, to turning all the files in the “threads” directory, you would run this command in the “code” directory:

 

turnin –ccse451 –pthreads threads

 

To see which files were turned in, run:

 

turnin –ccse451 -v

 

You should hand in all the code you changed as well as a file named “readme” containing your group name and the members of the team. In addition, we would like a short paper write-up describing what changes you made, how well they worked, how you tested your changes, and how each group member contributed to the project. The write-up should be mailed to the TA by 11:59pm on April 24th, so that you won’t need to worry about working on it just before the code is due.