Lab: Synchronization

CSC 213 - Operating Systems and Parallel Algorithms - Weinman



Summary:
By enforcing a system of synchronized locks, you will protect healthcare workers and the general population.
Assigned:
Monday 27 October
Due:
11:30 PM Monday 3 November
Objectives:
 
Collaboration:
You will complete this lab in teams as assigned by the instructor.
Resources:
In addition to the POSIX Threads Programming tutorial, the man pages for sem_init(3), sem_post(3), and sem_wait(3) will be helpful.
You are welcome to link and use fail-fast versions of the pthread and semaphore routines, which both check for success and handle errors.

Background

An important health clinic with a single doctor cares for a local population that suffers from regular disease outbreaks. Because the methods for treatment are sometimes experimental, observers often visit to watch the proceedings. In order to contain any potential epidemic, when a doctor enters the treatment area no other doctors, patients, or observers are allowed to enter. Of course, because their exposure to others puts them at risk of infection (if they were not already), once patients enter they are not allowed to leave until they receive treatment. In contrast, the present observers, often called to other treatment areas, may leave the segregated observation bay.
The doctor must wait for all the patients who have entered to complete a registration process before administering treatment. Once they all have registered, the doctor administers a respiratory medicine to the entire group of patients. Once the treatment is administered, the patients receive a voucher testifying to their temporary immunity to further infection. The doctor then leaves at some point after the treatment, allowing new observers and patients to enter. Patients may leave after receiving their vouchers. To summarize: We could add one additional ("optional") constraint. Namely, to prevent patients from being stuck and wasting medicine with a second treatment, all treated patients must exit before a doctor can enter again

Task details

Write a program
clinic numDoctors numPopulation numObservers
in which the master thread spawns numDoctors threads to represent the doctors who can give treatments, numPopulation threads to represent the infectable population, and numObservers threads to represent visiting caretakers. Each individual in the population has a life story like the following
while (1)
{
 // Sleep for a random time
 // (Get infected) enter the clinic
 // Register
 // Receive treatment
 // Pick-up voucher
 // Exit the clinic
}
while doctors endlessly visit the clinic for treatment
while (1)
{
 // Enter the clinic
 // Treat the patients
 // Exit the clinic
 // Sleep for a random time
}
and observers have an easy life
while (1)
{
 // Sleep for a random time
 // Enter the clinic observatory
 // Observe for a random time
 // Leave
}

Part A: Planning and thinking

Write complete pseudocode for the patient, doctor, and observer loop bodies. Declare and document the initial states of any combination of mutex, condition, and semaphore variables you wish.
Clearly explain and justify (i.e., "prove") what deadlock or starvation preventing properties your solution has (or lacks). Explain each variable and its purpose as well as the interleaving properties of the threads as they relate to the synchronizations.
Here is a nice example for the dining philosophers problem. (Though the "pseudocode" is actually Python.)

Part B: Execution

Implement your program in file clinic.c.

Evaluation

Assuming the general guidelines for lab exercises are met, the following guidelines will provide the basis for evaluation and grading:
Prevents deadlock:
Good ("B+")
Prevents waste:
Ensures all patients leave before another doctor enters. Excellent ("A+")
If you make incremental attempts (which I recommend), only submit the version you wish to be graded. For instance, the output might look something like this. If you spend any time studying that output, you will realize the importance of making sure treated patients have exited before the next doctor may enter. A revised program output (obeying the last constraint) might look like this.
The more complex your solution is (i.e., the more cases it can handle) the more comprehensive your explanation needs to be. Conversely, it becomes ever more important that your explanation exhibit great clarity.

Tips

  1. I highly recommend you start by thinking about your solution incrementally. That is, start with a solution that meets the minimal requirements specified in the "Background" section and otherwise merely prevents deadlock. Once you have that working, then see whether you can successfully and successively make enhancements.
  2. You can sleep a random amount of time with something like the following:
    usleep( random() % 2e6 ); // Sleep up to two seconds
    usleep( random() % 5e5 ); // Sleep up to one-half second
    It is up to you how long to make the bounds for each of the sleep periods.
  3. Note that PTHREAD_MUTEX_INITIALIZER is a macro, not a constant, and can only be used with a variable declaration. If you wish to make an assignment separate from the declaration, you'll need to use the procedure pthread_mutex_init(3).
  4. If you really want the output to look like the example, you'll probably need to introduce an extra mutex on stdout and utilize fflush(3). This is not required as part of the assignment, but may help convince you of correctness (despite your written argument).
  5. To keep the main thread's termination from also terminating the process, you will need to conclude main with a call to pthread_exit(3).

What to turn in

Extra credit

For the patient's safety, we sometimes must limit the number allowed in the clinic. Add a command-line parameter limit to indicate how many patients are allowed at one time, and enhance your synchronizations to enforce the limit. Included annotated pseudocode that explains and justifies correctness (as in Part A above).
Copyright © 2012, 2014 Jerod Weinman.
ccbyncsa.png
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.