Stock Nachos has an incomplete thread system. In this assignment, 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 have written for you. This thread system implements thread fork, thread completion, and semaphores for synchronization. It also provides locks and condition variables built on top of semaphores.
After installing the Nachos distribution, run the program nachos (in the proj1 subdirectory) 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:
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. You will notice that when one thread calls TCB.contextSwitch(), that thread stops executing, and another thread starts running. The first thing the new thread does is to return from TCB.contextSwitch(). We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand why the TCB.contextSwitch() that gets called is different from the TCB.contextSwitch() that returns.
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() (causing the scheduler to choose another thread to run) anywhere in your code where interrupts are enabled, and your code should still be correct. You will be asked to write properly synchronized code as part of the later assignments, so understanding how to do this is crucial to being able to do the project.
To aid you in this, code linked in with Nachos will cause KThread.yield() to be called on your behalf in a repeatable (but sometimes 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 -s <some-long-value>", with a different number each time, calls to KThread.yield() will be inserted at different places in the code.
You are encouraged to add new classes to your solution as you see fit; the code we provide you is not a complete skeleton for the project. Also, there should be no busy-waiting in any of your solutions to this assignment.
Your project code will be automatically graded. There are two reasons for this:
Of course, there is a downside. Everything that will be tested needs to have a standard interface that the autograder can use, leaving slightly less room for you to be creative. Your code must strictly follow these interfaces (the documented *Interface classes).
In order for you to verify that your code is compatible with the autograder, there are some simple compatibility tests you can run before you submit.
Since your submissions will be processed by a program, there are some very important things you must do, as well as things you must not do.
For all of the projects in this class...
In this project,
To make sure that you have a working design before you attempt to implement it, you should meet with a TA to review your design. These meetings will be held around seven to ten days before the due date, and should take around 20-30 minutes. Please bring a copy of your design for the TA to read. In addition, you will turn in your final design document reflecting the actual implementation two days after the phase is due (might not change from the design review document if you design well).
To submit your code (which should include your test cases), run the command submit proj1-code from within the nachos directory. It will only take files from the threads directory. We will grade only the last submission by any member of your group (though the autograder will mail you test results from all submissions).
There are five tasks, each gives a percentage representing its portion of the whole, and a number of lines which is a rough estimate of how many lines it will take to complete a task.
speak() atomically waits 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() waits until speak() is called, at which point the transfer is made, and both can return (listen() returns the word). Your solution should work even if there are multiple speakers and listeners for the same Communicator (note: this is equivalent to 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.
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.
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.
Please answer the following questions in your design document (due two days after the code for this phase is due).