Practice synchronization problems

If you want some practice before the midterm on synchrnoization problems, try the following:

1. Use semaphores to solve the Cigarette Smoker Problem.
   There are three smokers, and one agent. Each smoker has one of the three ingredients necessary for smoking; one has matches, one has tabacco, and one has paper. Smokers continuously roll a cigarettes and smoke it, but they first need all three ingredients to do so. The agent places two of the three ingredients on the table, and the smoker with the remaining ingredient picks them up and smokes. Write a solution to synchronize the agent and the smokers.

2. Use monitors to solve a different version of the Readers-Writers problem
   In this problem there are multiple reading and writing process that are trying to access a shared buffer. Multiple readers can simultaneously read the buffer, but only a single writer can write at a time (and no readers can read while a writer is writing).

   You should solve a slightly different version of the Readers-Writers problem then we solved in class. In this version a reader must block if a writer is waiting (even if currently there are other readers reading). When it is safe for a reader to read, it can wake up any other readers that have been waiting to read too, but if a writer comes along while these readers are reading, then any subsequent reader trying to read must wait because there is now a writer now waiting. In this version starvation of readers or writers is not possible.

   Hint: think about boundary cases, does the first reader need to do anything differently than subsequent readers, or does the last reader need to do anything differently than the first to stop reading, does the writer need to do anything special before or after it writes?

3. Use semaphores to solve the Sleeping Barber Problem. Use your monitor solution to this as a guide for solving this using semephores.

   The Sleeping Barber Problem

   In this problem you are to synchronize the actions of a barber and some number of customers. The barber can only cut one customer's hair at a time. A barber shop has one barber, one barber chair, and N chairs for waiting customers. If there are no customers the barber sits in the barber chair and falls asleep. When a customer arrives he/she has to wake up the sleeping barber. If a customers arrives while the barber is cutting hair, then if there is a free chair the customer sits down and waits, otherwise the customer leaves. Program the barber and the customers using semaphores to synchronize their actions. Your solution should be live, safe, and deadlock free. A couple suggestions: (1) I think it is easier to write the customer code first; (2) think about who can wake up whom (this will help you determine how many semaphores you need for your solution).

4. Any problem we solved in class using monitors or semaphores can be solved using the other synchronization primative, so you could try solving some of those problems using the other primative.