Nachos 2014: Build a thread system

Nachos has an incomplete thread system. In this assignment, your job is to complete it, and then use it to solve several synchronization problems.

Getting Started

After installing the Nachos distribution, run the program nachos.machine.Machine -[] nachos-sjtu/conf/proj1.conf for a simple test of our code. This causes the methods of nachos.threads.ThreadedKernel to be called in the order listed in threads/ThreadedKernel.java:

• The ThreadedKernel constructor is invoked to create the Nachos kernel.
• This kernel is initialized with initialize().
• This kernel is tested with selfTest().
• This kernel is finally "run" with run(). For now, run() does nothing, since our kernel is not yet able to run user programs.

Useful Hint

Trace the execution path (by hand) for the simple test cases we provide. When you trace the execution path, it is helpful to keep track of the state of each thread and which procedures are on each thread's execution stack.

Nachos code is repeatable if you call it repeatedly with the same arguments, it will do exactly the same thing each time. Specifically, invoking with fixed parameter "-s <some-long-value>" will always result in same execution.

Phase Description

In this phase, you need to complete a basic thread system with the following sub-tasks: thread operations (fork, join, etc. ), synchronization operators (lock, semaphores and condition variables) and also the thread scheduler.

Task 1

Implement KThread.join(): Blocks the calling thread until the joined thread terminates.

Note that a thread does not have to call join(). And if it is called, it will only be called once. The result of calling join() a second time is undefined.

A thread must finish executing normally, whether it is joined or not.

Task 2

Implement condition variables directly, and you can use enable/disable interrupt to provide atomicity.

We have provided a sample implementation for condition variable via semaphores; your job is to provide an equivalent implementation without directly using semaphores.

You may, of course, still use locks, even though they indirectly use semaphores. Once you are done, you will have two alternative implementations that provide the exact same functionality.

Your second implementation of condition variables must reside in class nachos.threads.Condition2.

Task 3

Complete the implementation of the Alarm class, which is a hardware timer providing preemption and allowing threads to sleep. You may only modified the waitUntil function.

A thread calls waitUntil(long x) will suspend its own execution until time has advanced to at least now + x.

This operation is useful for threads that operate in real-time, for example, for blinking the cursor once per second. There is no requirement that threads start running immediately after waking up; just put them on the ready queue in the timer interrupt handler until they have waited for at least the right amount of time.

Do not fork any additional threads to implement waitUntil(); you need only modify waitUntil() and the timer interrupt handler. waitUntil is not limited to one thread; any number of threads may call it and be suspended at any one time.

Task 4

Implement the Communicator class with operations, void speak(int word) and int listen(), which synchronously send and receive one word messages (also known as Ada-style rendezvous).

using condition variables (don't use semaphores!).

Speak() may wait on the communication, if there is no listener, until listen() is called on the same Communicator object, and then transfers the word over to listen(). Once the transfer is made, both can return. Similarly, listen() may wait until speak() is called.

Your solution should work even if there are multiple speakers and listeners for the same Communicator Note that, this is just like a zero-length bounded buffer: since the buffer has no room, the producer and consumer must interact directly, requiring that they wait for one another.

Each communicator should only use exactly one lock. If you're using more than one lock, you're making things too complicated.

Task 5

Implement priority scheduling, which is a key building block in real-time system, by completing the PriorityScheduler class.

Note that in order to use your priority scheduler, you will need to change a line in nachos.conf that specifies the scheduler class to use. The ThreadedKernel.scheduler key is initially equal to nachos.threads.RoundRobinScheduler. You need to change this to nachos.threads.PriorityScheduler when you're ready to run Nachos with priority scheduling.

Note that all scheduler classes extend the abstract class nachos.threads.Scheduler. You must implement the methods getPriority(), getEffectivePriority(), and setPriority(). You may optionally also implement increasePriority() and decreasePriority().

In choosing which thread to dequeue, the scheduler should always choose a thread of the highest effective priority. If multiple threads with the same highest priority are waiting, the scheduler should choose the one that has been waiting in the queue the longest.

An issue with priority scheduling is priority inversion. If a high priority thread needs to wait for a low priority thread, and there exists another high priority thread on the ready queue, 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 the priority scheduler so that it donates priority, if needed. Be sure to implement Scheduler.getEffectivePriority(), which returns the priority of a thread after taking into account all the donations it is receiving.

Note that while solving the priority donation problem, you will find a point where you can easily calculate the effective priority for a thread, but this calculation takes a long time. To receive full credit for the design aspect of this project, you need to speed this up. One optional choice is caching the effective priority and only recalculating a thread's effective priority when it is possible for it to change.

It is important that you do not break the abstraction barriers while doing this part. Priority donation should be accomplished by creating a subclass of ThreadQueue that will accomplish priority donation when used with the existing Lock class, and still work correctly when used with the existing Semaphore and Condition classes.

Task 6

A number of Hawaiian adults and children are trying to get from Oahu to Molokai. Unfortunately, they have only one boat which can carry maximally two children or one adult (but not one child and one adult). The boat can be rowed back to Oahu, but it requires a pilot to do so.

Note that you have all of these synchronization devices, use them to solve this problem. You will find condition variables to be the most useful synchronization method for this problem.

Arrange a solution to transfer everyone from Oahu to Molokai. You may assume that there are at least two children.

The method Boat.begin() should fork off a thread for each child or adult. Your mechanism cannot rely on knowing how many children or adults are present beforehand, although you are free to attempt to determine this among the threads, i.e. you can't pass the values to your threads, but you are free to have each thread increment a shared variable, if you wish.

To show that the trip is properly synchronized, make calls to the appropriate BoatGrader methods every time someone crosses the channel. When a child pilots the boat from Oahu to Molokai, call ChildRowToMolokai. When a child rides as a passenger from Oahu to Molokai, call ChildRideToMolokai. Make sure that when a boat with two people on it crosses, the pilot calls the ...RowTo... method before the passenger calls the ...RideTo... method.

Your solution must have no busy waiting, and it must eventually end. Note that it is not necessary to terminate all the threads -- you can leave them blocked waiting for a condition variable. The threads representing the adults and children cannot have access to the numbers of threads that were created, but you will probably need to use these number in begin() in order to determine when all the adults and children are across and you can return.

The idea behind this task is to use independent threads to solve a problem. You are to program the logic that a child or an adult would follow if that person were in this situation. For example, it is reasonable to allow a person to see how many children or adults are on the same island they are on. A person could see whether the boat is at their island. A person can know which island they are on. All of this information may be stored with each individual thread or in shared variables. So a counter that holds the number of children on Oahu would be allowed, so long as only threads that represent people on Oahu could access it.

What is not allowed is a thread which executes a "top-down" strategy for the simulation. For example, you may not create threads for children and adults, then have a controller thread simply send commands to them through communicators. The threads must act as if they were individuals.

Information which is not possible in the real world is also not allowed. For example, a child on Molokai cannot magically see all of the people on Oahu. That child may remember the number of people that he or she has seen leaving, but the child may not view people on Oahu as if it were there. (Assume that the people do not have any technology other than a boat!)

You will reach a point in your simulation where the adult and child threads believe that everyone is across on Molokai. At this point, you are allowed to do one-way communication from the threads to begin() in order to inform it that the simulation may be over. It may be possible, however, that your adult and child threads are incorrect. Your simulation must handle this case without requiring explict or implict communication from begin() to the threads.

Hints

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 KThread.yield() anywhere in your code where interrupts are enabled, and your code should still be correct.

Note that there should be no busy-waiting in any of your solutions to this assignment.

In this project,

1. The only package you will modify nachos.threads, so don't add any source files to any other package.
2. The autograder will not call ThreadedKernel.selfTest() or ThreadedKernel.run(). If there is any kernel initialization you need to do, you should finish it before ThreadedKernel.initialize() returns.
3. There are some mandatory autograder calls in the KThread code. Leave them as they are.

Please consider the following questions:

1. Why is it fortunate that we did not ask you to implement priority donation for semaphores?
2. A student proposes to solve the boats problem by use of a counter, AdultsOnOahu. Since this number isn't known initially, it will be started at zero, and incremented by each adult thread before they do anything else. Is this solution likely to work? Why or why not?