Lab: Synchronization

CSC 213 - Operating Systems and Parallel Algorithms - Weinman



Summary:
By enforcing a system of synchronized locks, you will protect animal caretakers and keep the animals healthy.
Assigned:
Tuesday 16 October
Due:
10:30 PM Monday 29 October
Objectives:
Practice using pthreads for applications with independent components and gain familiarity with pthreads synchronization primitives.
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.

Background

An animal clinic cares for some ferocious but endangered animals. The animals are allowed to wander between an enclosed building and an open yard. As part of their recovery efforts, the caretakers need to enter the yard from time to time. However the animals are so ferocious that caretakers should only enter the yard when it is free of animls. Furthermore, because we want to preserve the wild nature of the animals, only one caretaker can be allowed in the yard at one time.
You are tasked with writing a software system that will help manage this animal yard by blocking animals from entering when a caretaker is present, blocking a caretaker from entering until all animals have left, and ensuring only one caretaker is in the yard at one time.

Task details

Write a program
clinic numAnimals numCaretakers
in which the parent spawns numAnimals threads to represent the animals, and numCaretakers threads to represent the caretakers. Though an animal thread will of course look different from a caretaker thread, each thread should run an infinite loop like the following:
while (1)
{
    // Enter the yard (or attempt and wait, subject to constraints)
    // Sleep for a random time
    // Exit the yard
    // Sleep for a random time
}

Part A: Planning and thinking

Write pseudocode for the animal and caretaker loop bodies. You may use any combination of mutex, condition, and semaphore variables that you wish.
Clearly explain and justify (i.e., prove) what deadlock or starvation preventing properties your solution has (or lacks). You should explain what variables are used and what the purpose of each is, 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 practically pseudocode is actually Python code.)

Part B: Execution

Implement your program in file clinic.c.
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.

Evaluation

Assuming the general guidelines for lab exercises are met, the following guidelines will provide the basis for evaluation and grading:
Prevents deadlock:
Satisfactory ("C")
Prevents caretaker starvation:
Ensures at least one caretaker gets to enter if waiting. Good ("B")
Caretaker priority:
Prevents animals from entering while any caretaker is waiting. Excellent ("A")
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. Given that the entire lab is due the Monday after break, I strongly recommend you make as much progress as possible on it before leaving. Specifically, an implemented version that you believe prevents deadlock and compiles.
  3. You can sleep a random amount of time with something like the following:
     usleep( random() % 2e6 ); // Sleep up to two seconds
    It is up to you how long to make the bounds for each of the four sleep periods.
  4. 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).
  5. 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, but may help convince you of correctness (despite your written argument).

What to turn in

Extra credit

Either (or both) extra credit opportunities need to be accompanied by an annotated pseudocode solution that explains and justifies their correctness (as in Part A above).

Opportunity 1

For the animal's safety, we sometimes must limit the number allowed in the yard. Add a third command-line parameter limit to indicate how many animals are allowed at one time, and enhance your synchronizations to enforce the limit.

Opportunity 2

Even an excellent solution that prevents caretakers from "starvation" may starve animals from the yard. Create a solution that guarantees no caretaker or animal thread is ever susceptible to starvation.
Copyright © 2012 Jerod Weinman.
ccbyncsa.png
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.