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,
Each project for this class will be broken up into two phases. In phase I, you will create and submit a design document to be reviewed by your TA. This is to ensure that b) You have not made any egregious mistakes or misunderstanding of the project and b) You have a reasonable mastery of the skeleton code and the concepts of the project you are attempting to implement. In phase II, you will submit your implemented, functional, fully tested code along with a revised draft of your design document incorporating all your changes. The initial design document is worth 10 points of your project grade. See "Design Document Instructions" on the course page. Along with being graded for general correctness, we will grade you for including a reasonable and viable testing plan in the document. Include a one to two sentence description of each test you plan to implment in the "Testing" section of your doc. Your tests should cover all code you implement, and they should cover both basic functionality and proposed edge cases and/or stress tests. The initial document must be no longer than 15 pages maximum, in a readble font size (no less than 10.5, please.) If you violate this parameter, your TAs will go blind, and you will be penalized.
Your final design doc will be worth 20 points of your total project grade. Of those points, 10 will be allocated for making the appropriate changes to satisfy all correctness constraints of the design. Please highlight all changes or additions you made that are different from your initial design doc. Otherwise, we may not read that section and you may not get credit. The other 10 will allocated for a description of each test case you've implemented. This description should include the purpose of the test, how it works/what it does, a note of where it is and what it is called in your submission code, and pseudocode where appropriate if the test code is convoluted or hard to understand from reading the source. This semester, we are requiring all groups to enforce version control through our class allocated GitHub accounts. If we cannot find your test cases by browsing your repo because you did not include the file location/method names or because you lied about their existence, you will be penalized. We expect you to take testing as seriously as your project code. Your final design document will have an extended maximum length of 18 pages to accomodate this extra detail.
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 ten days before the due date, and should take around 20-25 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 one day after the phase is due (might not change from the design review document if you design well).
To submit your code for grading, 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 (
autograder will mail you test results from all submissions).
For testing purposes, submit to the autograder with the command submit proj1-test
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). This means that neither thread may return from listen() or speak() until the word transfer has been made. 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.
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() (these are not required). 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 (for instance, for a lock held by a low priority thread), and another high 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 the priority scheduler so that it donates priority, where possible. 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 by 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 -- the Lock class does not need to be modified. 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. Priority should also be donated through thread joins.
Priority Donation Implementation Details:
1) A thread's effective priority is calculated by taking the max of the donor's and the recipient's priority. If thread A with priority 4 donates to thread B with priority 2, then thread B's effective priority is now 4. Note that thread A's priority is also still 4. A thread that donates priority to another thread does not lose any of its own priority. For these reasons, the term "priority inheritance" is in many ways a more appropriate name than the term "priority donation".
2) Priority donation is transitive. If thread A donates to thread B and then thread B donates to thread C, thread B will be donating its new effective priority (which it received from thread A) to thread C.
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. We will refer to the thread that called Boat.begin() as the parent thread. 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 parameters adults and children in the method begin() to your threads, but you are free to have each thread increment shared variables to try and determine this value, 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. The simulation ends when the parent thread finishes running. Note that it is not necessary to terminate all the forked threads -- you can leave them blocked waiting for a condition variable. While you cannot pass the number of threads created to the threads representing adults and children, you can and probably will need to use this 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. This also means you cannot serialize your code by disabling interrupts inside Boat.java explicitly, for any reason. Every person must be thinking, and acting, independently at all times.
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 adult/child threads to begin() (the parent thread) 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() (the parent thread) to the adult/child threads.