Assignment 1: Build a synchronized, multi-threaded system

Remember to do your work in accordance with USC's USC code of Academic Integrity.

In this assignment, we give you part of a working thread system; your job is to complete it, and then to 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, along with semaphores for synchronization. Run the program `nachos' for a simple test of our code. Trace the execution path (by hand) for the simple test case 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 SWITCH, another thread starts running, and the first thing the new thread does is to return from SWITCH. We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand why the SWITCH that gets called is different from the SWITCH that returns. (Note: because gdb does not understand threads, you will get bizarre results if you try to trace in gdb across a call to SWITCH.)

The files for this assignment are:

• main.cc, threadtest.cc - a simple test of our thread routines.
• thread.h, thread.cc - thread data structures and thread operations such as thread fork, thread sleep and thread finish.
• scheduler.h, scheduler.cc - manages the list of threads that are ready to run.
• synch.h, synch.cc - synchronization routines: semaphores, locks, and condition variables.
• list.h, list.cc - generic list management (LISP in C++).
• synchlist.h, synchlist.cc - synchronized access to lists using locks and condition variables (useful as an example of the use of synchronization primitives).
• system.h, system.cc - Nachos startup/shutdown routines.
• utility.h, utility.cc - some useful definitions and debugging routines.
• switch.h, switch.s - assembly language magic for starting up threads and context switching between them.
• interrupt.h, interrupt.cc - manage enabling and disabling interrupts as part of the machine emulation.
• timer.h, timer.cc - emulate a clock that periodically causes an interrupt to occur.
• stats.h - collect interesting statistics.

You will not need to modify them all. They are located in the code/threads/ directory.

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 (causing the scheduler to choose 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 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 can cause Thread::Yield to be called on your behalf 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 -rs integer, with a different number each time, calls to Thread::Yield will be inserted at different places in the code. This simulates a timesharing environment.

Invoking Nachos

Make sure to run various test cases against your solutions to these problems. At the very least make sure that your solutions run for various parameters to -rs.

You may not make any modifications to functions in the code/machine directory. It is not necessary to make any changes to the context switching code in switch.h.

There cannot be any busy-waiting in any of your solutions to this assignment.

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.

The assignment is below. Note that you will use locks in later assignments, so making sure that they work correctly now will save you time in later assignments.

1. (10 points) Implement locks and condition variables. The comments in the code describe the functions you need to implement. You may either use semaphores as a building block, or you may use more primitive thread routines (such as Thread::Sleep). We have provided the public interface to locks and condition variables in synch.h. You need to define the private data and implement the interface. Note that it should not take you very much code to implement locks and ondition variables.

Your implementation should address issues like a thread trying to release a lock that it does not hold. You must document the error conditions you identify and how your implementation handles them. For example: If a thread tries to release a lock it does not hold, that request is to be ignored.

A comment on locks in synch.h says: In addition, by convention, only the thread that acquired the lock may release it. You may not assume this; your implementation must enforce it.

Condition variables are generally used with monitors, but because C++ does not support monitors, we implement the synchronization they provide explicitly using locks. Lock::Acquire() is the equivalent of entering a monitor, and Lock::Release() is leaving it.

You may assume that a Condition variable is always used with the same lock. If you do not assume this, you must document what assumptions you use.

synch.h makes a distinction between Hoare monitors and Mesa monitors. This assignment calls for you to implement Mesa semantics. The distinction is in the semantics of Condition::Signal(). Under Hoare semantics, when Condition::Signal() is called on a condition variable with a thread waiting, the thread waiting on that condition variable runs immediately. Under Mesa semantics, when Condition::Signal() is called one of the threads waiting on that condition variable is put on the ready queue (that is it is made ready or unblocked), but the next thread to run is determined by the scheduler. The current thread may or may not yield the processor at your discretion. Note also that the thread that is made ready must reacquire the lock before its call to Condition::Wait() returns.

Although this assignment does not require you to implement Hoare semantics, its worth thinking about what issues would arise in implementing those semantics. It's the sort of thing that would make a good exam question.

Test your code by running this test code. Read the code for the expected behavior. Feel free to create your own test cases if you want to test your code more completely.

We will look at your code. Uncommented code will lose points.

2. Simulating a Doctor's Office (25 points)
   You are to simulate the operation of a doctor's office. Each of the Doctor Office components below is to be simulated through the use of individual threads. Your Doctor's Office is to have the following types of people and resources:
   • Adult Patient - Someone who has come to see a doctor. Adult Patients come to the doctor's office by themselves.
   • Child Patient - Someone who has come to see a doctor. Child Patients cannot go to any room without their parent. They must go together. The Child Patient follows their Parent to the various rooms in the doctor's office.
   • Parent - Bring their child to see the doctor. Escorts their child everywhere.
   • Waiting Room Nurse - Patients register with the Waiting Room Nurse.
   • Nurse - Nurses handle Patients.
   • Xray Technician - Takes xrays of Patients
   • Cashier - Receives money from Patients/Parents
   • Doctors - See Patients in examination rooms

   Patient: Patients show up to the doctor's office and register with the Waiting Room Nurse. After registering, they go wait in the waiting room. They wait until a Nurse comes to the waiting room to escort them to an Examinination Room. Once in the examinination room, the Nurse will take their temperature, take their blood pressure, then ask what symptom they have. Patients can have the following symptoms: pain, nausea, hear alien voices. The symptom has nothing to do with the Doctor's examination. However, you must share the data so that the symptom is "written" on the examination sheet. The patient then waits for the Doctor to come to see them. The Patient/Doctor conversation is described under the Doctor section.

   If a Patient has to have an xray taken, they must wait for a Nurse to escort them to the Xray Room. After the xray has been taken, a nurse takes them back to their examinination room. They wait for the doctor to come back to read the xray.

   After the Doctor says the examination is over, the patient must wait for a Nurse to escort them to the Cashier to pay. Prices are listed in the Cashier section. After paying the Cashier, the Patient leaves the doctor's office.

   Child Patient: A Child Patient must have an accompanying Parent. For Child Patients, the Nurse talks to the Parent, who talks to their child. Nurses cannot escort a Parent anywhere until the Parent has told their child to follow them. Only after a Parent has told their child to follow them, will the Parent follow a Nurse.

   Waiting Room Nurse: The Waiting Room Nurse stays at her desk in the Waiting Room. Their job is to give a form to Patients to fill out. The form requires the patient name and age. The Waiting Room Nurse does not wait for a Patient to fill out the form. The Patient must bring the form back to the Waiting Room Nurse after it is filled out. Once the Waiting Room Nurse has accepted the completed form, they tell the Patient to go back and wait to be called by a Nurse.

   The Waiting Room Nurse create a new Examination Sheet for a registered Patient. The Waiting Room Nurse holds onto all examination sheets for Patients that are in the waiting room. When a Nurse is to escort a Patient to an examination room, they receive the appropriate examination sheet from the Waiting Room Nurse.

   Nurses will tell the Waiting Room Nurse when there is an open examinination room. The Waiting Room Nurse will tell the Nurse if there is a Patient waiting, or not. It is the Nurses job to tell the next waiting Patient to follow them to the examinination room. It is not the Waiting Room Nurses job to do this.

   Cashier: The Cashier is to receive payment from Patients. When a Patient comes up to the Cashier, they hand over their examination sheet. The Cashier will read this and determine the Patient's bill. They then tell the Patient how much they owe. The Patient then "pays" that amount. The Patient then waits for the Cashier to give them a receipt.

   Cashiers cannot start with another Patient until they know the current Patient has left their counter.

   Xray Technicians: Xray Technicians have nothing to do until a Nurse brings a Patient in for an xray. When first arriving, the Nurse gives the Xray Technician the examination sheet for the Patient, or the Patient must wait in line, if the Xray Technician is busy. The nurse then leaves once they've "dropped off" the Patient.. When a Patient has their turn, the Xray Technician tells the Patient to get onto the table. Once the Patient is on the table, the Xray Technician "takes" an Xray. An xray session can require from 1 to 3 xray images to be taken. After each image is taken, the Xray Technician tells the Patient to "move" so the next image can be taken. Once the Patient has moved, the Xray Technician takes the next image. An xray image can either show 'nothing', a 'break', or a 'compound fracture'.

   Once all the xray images are taken, the Xray Technician tells the Patient to wait in the Xray waiting room and puts their examination sheet in a wall pocket for this room. Once the Nurse arrives, the Nurse tells the Patient to follow them. The Xray Technician can work with another Patient once they've put the examination sheet for the just-finished patient in the wall pocket, and that Patient has left the Xray room.

   Doctors: Doctors stay in their office until they are informed by a nurse that there is a Patient ready to be examined. The first time a Doctor sees a Patient, they read the examination sheet. The Doctor will randomly determine if the Patient needs an Xray or a shot. There is a 25% chance that a Patient will need an Xray. If a Patient does need xrays, the Doctor must also determine how many images are to be taken. It is to be from 1 to 3 images. There is a separate 25% chance that a Patient will need a shot. If a Patient does not need an xray, or a shot, then the Doctor determines they are fine and leaves the examination room. If a shot/xray is needed, the Doctor tells the Patient what they must have. The Doctor then leaves the examination room. Upon exiting the examination room, the Doctor gives the examination sheet to a Nurse, if one is currently not busy, or if no Nurse is available, the Doctor puts the examination sheet in the wall pocket right by the examination room door. The Doctor then goes back to their office.

   The second time a Doctor sees a Patient - after xrays - the Doctor reads the xray images and tells the Patient the results. They also note down on the examination form that the Patient has been informed as to the xray results. The Doctor then leaves the examination room, if a Nurse is available, the Doctor gives the Nurse the examination sheet. If no Nurse is available, they put the form in the wall pocket for that examination room.

   Nurses: Nurses escort patients to and from rooms. This includes the Waiting Room, the Xray room, the Cashier, and the Examinination Room. Nurses also take a Patients termperature, blood pressure, and asks for their symptom. Nurses also give shots to Patients.

   When a Nurse has nothing to do, they examine the wall pockets outside of each Examination Room. If the wall pocket is not empty, that means a Doctor is done with the Patient in the room. The Nurse is to read the examination sheet to see if the Patient needs an xray, a shot, or is finished with their examination. Whichever task is needed, the Nurse will escort the Patient to the proper location, handing over the examination sheet to the proper person (unless it is just a shot, in that case they give the shot) and then escort the Patient to the Cashier.

   For a Nurse to give a shot, they must first go to the supply cabinet to get the needed medicine. Only one Nurse can be using the supply cabinet at a time. To actually give a shot, the Nurse must ensure the Patient is ready for the shot. The Patient must wait for the Nurse to give a shot, once the Nurse enters the examination room with the medicine from the supply cabinet. The Nurse must tell the Patient when the shot is over.

   Once a Patient examination is complete - shot given, xrays taken, etc., a Nurse will escort them to the Cashier.

   Examination Sheets: Examination sheets are not to be stored in a single large array. Each examination room has a wall pocket for storing an examination sheet for the Patient in that room. The Waiting Room Nurse holds onto all examination sheets for Patients in the waiting room. The Xray Technicican holds the examination sheet for the Patient that is having xray images taken. Nurses that are escorting Patients, carry their examination sheet with them.

   Number of Entities:

   • There can be from 2 or 3 Doctors
   • There can be from 2 to 5 Nurses
   • There is 1 Waiting Room Nurse
   • There is 1 Cashier
   • There can be from 1 or 2 XRay Technicians
   • There must be at least 30 Patients, but your simulation should run with any number of Patients. This includes Adult, as well as Child, Patients. Every Child Patient must have an associated Parent.
   It is required that your project works with variable number of entities and hence, hardcoding will reduce the credit.
   

   Testing:

   You are to develop repeatable tests for part 2. Repeatable means that when the test is run, the same behavior is produced - like in the test suite we give you for part 1. You must prove the following:

   • Child Patients are never abandoned by their Parent, nor go anywhere without their Parent.
   • Waiting Room Nurses only talk to one Patient/Parent at a time.
   • Cashiers only talk to one Patient/Parent at a time.
   • Patients/Parents never go anywhere without being escorted by a Nurse.
   • All Patients leave the Doctor's Office. No one stays in the Waiting Room, Examination Room, or Xray Room, forever.
   • Two Doctors never examine the same Patient at the same time.

   Specific output guidelines are posted. Please follow the link below.

   Output Guidelines
   

   Your submission should meet these guidelines. Any submission that does not meet these guidelines may be graded down.