Homework 3: Concurrency

  1. The following is one attempt to solve the Critical Section problem. Can mutual exclusion be guaranteed? Why?

Global variable flag[0] and flag[1], initially flag[0] and flag[1] are both false

P0:

Prefix0

While (flag[1]) do {}

flag[0]=true

CS0

flag[0]=false

suffix0

P1:

Prefix1

While (flag[0]) do {}

flag[1]=true

CS1

flag[1]= false

suffix1

  1. Define the Test-and-Set instruction and show how it can be used to solve the Mutual Exclusion problem. Use Test-and-Set to solve the ticket reservation: Ticket agent i(process i) will check the #-of-seats. If it is greater than 0, he will grab a seat and decrement #-of-seats by 1. Use global variable NumOfSeat to represent the number of total available seats.
  1. Question on the textbook Page 202: 11. The Sleeping-Barber Problem.

A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber.

(1) Write a Pseudo-code(DO NOT WRITE PROGRAM) to coordinate the barber and the customers.

(2) Extra Credit:Consider the Sleeping-Barber Problem with the modification that there are k barbers and k barber chairs in the barber room, instead of just one. Write a program(Pseudo-code) to coordinate the barbers and the customers.

  1. Question on the textbook Page 202: 12.The Cigarette-Smokers Problem.

Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobaccor, 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 materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats.

Write Pseudo-code(DO NOT WRITE PROGRAM) to synchronize the agent and the smokers.