CS 450 Update Log

The solutions to this assignment must be typed up, printed, and submitted by July 6th at the beginning of lecture. Internet students should submit their work via Blackboard by the same date.

Coded solutions must be properly formatted and indented.

1. Deadlock in the barrier non-solution

On page 25 of The Little Book of Semaphores (TLBoS) (in listing 3.4), a non-working solution to the barrier pattern is presented in which deadlock is likely to occur. It is, however, possible — though unlikely — that the code could be executed by multiple threads in such a way as to avoid deadlock. Describe such a path through the given barrier code for 5 threads.

2. Completing the Generalized Smokers Solution

The generalized solution for the smokers problem, as presented on page 119 of TLBoS (in listing 4.46), is incomplete — in addition to Pusher A, which is woken when tobacco is placed on the table, and the smoker holding tobacco (shown in listing 4.44), we need the code for Pushers B and C, and the smokers holding paper and matches to complete the solution.

Write up the code for Pushers B and C and the aforementioned smokers — you should adhere to the semaphore names and conventions established by the existing code.

3. The Dance Mixer Problem

At the Willowbrook Ballroom, the band is always playing a Waltz, a Tango, or a Foxtrot, and there is at all times a group of dancers (men and women) on hand, each of whom can dance two of these three dances.

Each dancer waits in a gender appropriate line for the dance he/she is capable of dancing until the corresponding music is played by the band. When the music starts playing, he/she waits to be paired up with a dancer of the opposing gender also waiting for the same dance. After they complete the dance, each dancer lines up for the next dance they are capable of dancing — the band continues to play the music until there are no couples on the dance floor. At this point the band starts to play music for the next dance, and the affair starts over again.

Implement a semaphore based solution (that avoids deadlock and race conditions) for the Dance Mixer problem.

Be sure to first list the variables used in your solution (names, types, and values), and then your coded solution. You should clearly identify each thread and what it represents (dancer, band, etc.) Comment the code to your satisfaction.

4. The Gaming Lab Problem

Bowing to popular demand, the residence hall association has invested in a “lab” consisting of 5 high-performance gaming PCs. Usage of the game lab is restricted, however, to students belonging to the Rho-Theta-Sigma (RTS), Rho-Pi-Gamma (RPG), and Phi-Pi-Sigma (FPS) fraternities.

At any given moment, the lab may be occupied by a group of no more than 5 students from a single fraternity, and as other students from the various fraternities arrive at the door they form separate lines waiting to enter the room. When the current group of students finishes their game and exits, another group of students formed from one of the lines enters. If the selected line has fewer than 5 students, all the students in that line will enter as a group, otherwise a group of 5 will be selected to enter.

Note that once a group of students enters the lab, no additional students may enter the room, regardless of the size of the group or which fraternity they belong to. It is also important to guarantee that no single fraternity is starved of the game lab — e.g., if RTS is currently using the lab and there is a mile-long line for RTS but one waiting student from RPG, the latter group will be allowed to enter.

Implement a semaphore based solution for the Gaming Lab problem.

Be sure to first list the variables used in your solution (names, types, and values), and then your coded solution. You should clearly identify each thread and what it represents (dancer, band, etc.) Comment the code to your satisfaction.