MI307/IMI005 Nachos Project 1: Threads

¡@

Due: April 30, 2005 at Midnight (Note that this is a Saturday)

Submission Instructions

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. [0 pts] The first step is to understand how the partial thread system is used within Nachos. You will not implement anything in this part of the project. Rather, you will go through the exercise of building and running a nachos executable.
   1. Download or copy the appropriate nachos distribution for the system that you are using, and unpack it using gunzip and tar (see Distributions in the class project guide). Build a nachos executable using the gmake command. Run gmake (with no arguments) in the code directory; the nachos executable is deposited in the threads subdirectory. Once you are in the threads subdirectory with a nachos executable, you can run a simple test of Nachos by entering the command "nachos" (if that doesn't work, try ./nachos). When you run the nachos executable, it should produce output similar to the following:

      
      [cs120f@sdcc7]$ ./nachos
      *** thread 0 looped 0 times
      *** thread 1 looped 0 times
      *** thread 0 looped 1 times
      *** thread 1 looped 1 times
      *** thread 0 looped 2 times
      *** thread 1 looped 2 times
      *** thread 0 looped 3 times
      *** thread 1 looped 3 times
      *** thread 0 looped 4 times
      *** thread 1 looped 4 times
      No threads ready or runnable, and no pending interrupts.
      Assuming the program completed.
      Machine halting!
      
      Ticks: total 130, idle 0, system 130, user 0
      Disk I/O: reads 0, writes 0
      Console I/O: reads 0, writes 0
      Paging: faults 0
      Network I/O: packets received 0, sent 0
      
      Cleaning up...
      

      See Installing and Building Nachos from the Duke equivalent of this course for notes on building nachos executables (ignore the first two paragraphs and the references to the different projects in the third paragraph).

   2. If you examine threads/main.cc, you will see that you are executing the ThreadTest function in threadtest.cc. It is the printf in the SimpleTest class that produced the initial output when you ran the nachos executable. ThreadTest is a simple example of a concurrent program. In this case there are two independent threads of control executing "at the same time" and accessing the same data. Your first goal is to understand the thread primitives used by this program, and to do some experiments to help you understand what really happens with multiple threads at runtime. To understand the execution path, trace through the code for the simple test case. See the notes in Tracing and Debugging Nachos Programs from the Duke equivalent of this course for some tips on how to do this.

   3. ThreadTest in threadtest.cc is an example of a test case for exercising the Nachos system. As you work on the problems below, you will need to extend threadtest.cc to test your changes to the Nachos system.

2. [15 pts] Implement condition variables using interrupt enable and disable to provide atomicity. The file code/threads/synch.h defines the class "Condition", and it is your task to implement the functions defined by that class (in synch.cc).

   The file pingcvtest.cc is an implementation of the PingPong program described in lecture that uses locks and condition variables. You can use this as an initial test of your Lock and Condition classes. Note that you will want to stress test your implementation with more rigorous test cases, and tests that validate that error conditions are appropriately handled. [Sample Output]

3. [15 pts] 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).

   You can implement the "Mailbox" class in synch.h and sync.cc, or in new files. If you create new files, be sure to update the dependency information in the Makefile; see Installing and Building Nachos from the Duke equivalent of this course for directions on how to do this.

4. [20 pts] 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. The implemention of the Thread class is in code/threads/thread.{h,cc}.

5. [25 pts] 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 than the currently running thread, the current thread gives up the processor to the new thread (a thread with the same priority as the current thread does not preempt it). Similarly, when threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be woken up first. Use the following signature for the method to set the thread priority:

   void setPriority(int newPriority);
   

   The range of valid priorities is the entire range of an "int". Assume that all threads are created with priority 0. Roughly speaking, threads set to have a negative priority have "less priority", and threads set to have a positive priority have "more priority". Compare thread priorities directly to determine higher priority (e.g., a priority of 1 is lower than a priority of 2).

   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 holding the lock. Implement this fix separately for both situations: (1) the Lock class and (2) the Join method.

6. [25 pts] You have been hired by Greenpeace to help the environment. Because unscrupulous commercial interests have dangerously lowered the whale population, whales are having synchronization problems in finding a mate. The trick is that in order to have children, whales are needed, one male, one female, and one to play matchmaker -- literally, to push the other two whales together (I'm not making this up!). Your job is to write the three procedures Male(), Female(), and Matchmaker(). Each whale is represented by a separate thread. A male whale calls Male(), which waits until there is a waiting female and matchmaker; similarly, a female whale must wait until a male whale and a matchmaker are present. Once all three are present, all three return.

Submitting The Project

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 me and Sanjeev by midnight on Saturday, October 28. You do not have to write anything for problem 1. An example of writing up a problem is shown in this skeleton.

To turn in your project, you will use the "turnin" command. This command is in /home/ostl/cs120f/public/bin (ostl) and /home/solaris/ieng9/cs120f/public/bin (uape), but it should also be in your path by default. Here are steps on how to use turnin:

% cd nachos-3.4/code
% turnin -ccse120 threads

These steps (1) change directory to the code subdirectory of nachos, and (2) turn in your "threads" directory.

To see which files have been submitted, execute:

% turnin -ccse120 -v

This should list all of your files that have been submitted (all of the files in your "threads" directory). The man page for turnin describes all of its command line options.

Note that you can submit any number of times: You can turn in one version early, and then work some more, and resubmit later (the resubmission will overwrite what you submitted earlier).