CSC 325 Operating Systems with an Emphasis on UNIX
Teamwork 6
Organize yourselves into groups of two or three students. Discuss the following
problems in your group. Elect one person to be group scribe to type up your
team's answers.
- Readers and Writers Problem
In 1971 Courtois et al posed and solved the following famous problem which has since become the standard for modeling access to a database with many competing processes wishing to read from and write to it, such as an airline reservation system. It is acceptable to have multiple processes reading the database at the same time, but if one process is writing, they must be ensured exclusive access, even from readers. The problem is how to program the readers and writers and how priority should be handled. Your text provides a deadlock-free solution which gives priority to readers but in which writers may starve, and describes a deadlock-free solution which gives priority to writers but in which readers may starve. Describe how a deadlock-free solution in which there is no starvation might be achieved, explaining your assumptions about priority.
- The Sleeping Barbers Problem
A Barbershop has a waiting room with n chairs as well as the cutting room which contains the barber's chair. If there are no customers waiting to be served, the barber falls asleep. If a customer enters the barbershop and all of the chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits on one of the free chairs. If the barber is asleep, the customer wakes the barber and sits in the barber's chair. Write C++-like pseudo-code to coordinate the barber and the customers. Explain whether or not your code prevents against starvation of the waiting customers. Explain whether or not your code prevents against deadlock. List your assumptions about priority.
- The Cigarette Smoker's Problem
A system has three smoker processes and one agent process. Each smoker continuously rolls cigarettes and smokes them. To roll and smoke a cigarette, the smoker needs three things: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinite supply of all three types of materials. The agent places two of the ingredients on the table. The smoker who has the third ingredient then makes and smokes a cigarette, and signals the agent upon completion. The cycle repeats. Write C++-like pseudo-code to synchronize the agent and the smokers. Explain whether or not your code prevents against starvation of the waiting customers. Explain whether or not your code prevents against deadlock. List your assumptions about priority.
- The Dining Philosopher's Problem
In 1965, Dijkstra posed and solved the following problem which has since become a standard abstraction for modeling processes competing for exclusive access to a limited number of resources such as I/O devices. Five Philosophers are seated around a round table. Each philosopher has a plate of spaghetti which requires two chopsticks to eat. Between each two philosophers is one chopstick. The life of a philosopher requires periods of eating and periods of thinking. When a philosopher gets hungry, s/he attempts to acquire two chopsticks to eat. The problem is how to code this without starvation or deadlock. Your textbook offers a deadlock-free but not starvation-free solution to this problem. Write a solution in C++-like pseudo-code which is both starvation-free and deadlock-free. Hint: You might consider adding semaphores to their solution.
Save your text file as yourlastnameT6.txt.