Operating Systems
This problem is from Andrews’s Concurrent Programming .
A tribe of savages eats communal dinners from a large pot that can hold M servings of stewed missionary7. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the pot is empty, the savage wakes up the cook and then waits until the cook has refilled the pot.
Any number of savage threads run the following code:
while True:
getServingFromPot()
eat()
And one cook thread runs this code:
while True:
putServingsInPot(M)
The synchronization constraints are:
Savages cannot invoke getServingFromPot if the pot is empty.
The cook can invoke putServingsInPot only if the pot is empty.
Add code for the savages and the cook that satisfies the synchronization constraints.
William Stallings presents a more complicated version of the barbershop problem, which he attributes to Ralph Hilzer at the California State University at Chico.
Our barbershop has three chairs, three barbers, and a waiting area that can accommodate four customers on a sofa and that has standing room for additional customers. Fire codes limit the total number of customers in the shop to 20.
A customer will not enter the shop if it is filled to capacity with other customers. Once inside, the customer takes a seat on the sofa or stands if the sofa is filled. When a barber is free, the customer that has been on the sofa the longest is served and, if there are any standing customers, the one that has been in the shop the longest takes a seat on the sofa. When a customer’s haircut is finished, any barber can accept payment, but because there is only one cash register, payment is accepted for one customer at a time. The barbers divide their time among cutting hair, accepting payment, and sleeping in their chair waiting for a customer.
In other words, the following synchronization constraints apply:
Customers invoke the following functions in order: enterShop, sitOnSofa, sitInBarberChair, pay, exitShop.
Barbers invoke cutHair and acceptPayment.
Customers cannot invoke enterShop if the shop is at capacity.
If the sofa is full, an arriving customer cannot invoke sitOnSofa until one of the customers on the sofa invokes sitInBarberChair.
If all three barber chairs are busy, an arriving customer cannot invoke sitInBarberChair until one of the customers in a chair invokes pay.
The customer has to pay before the barber can acceptPayment.
The barber must acceptPayment before the customer can exitShop.
One difficulty with this problem is that in each waiting area (the sofa and the standing room), customers have to be served in first-in-first-out (FIFO) order. If our implementation of semaphores happens to enforce FIFO queueing, then we can use nested multiplexes to create the waiting areas. Otherwise we can use Fifo objects as defined in Section [Fifo].
Write code that enforces the synchronization constraints for Hilzer’s barbershop.
This problem is from William Stallings’s Operating Systems , but he attributes it to John Trono of St. Michael’s College in Vermont.
Stand Claus sleeps in his shop at the North Pole and can only be awakened by either (1) all nine reindeer being back from their vacation in the South Pacific, or (2) some of the elves having difficulty making toys; to allow Santa to get some sleep, the elves can only wake him when three of them have problems. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop’s door, along with the last reindeer having come back from the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready. (It is assumed that the reindeer do not want to leave the tropics, and therefore they stay there until the last possible moment.) The last reindeer to arrive must get Santa while the others wait in a warming hut before being harnessed to the sleigh.
Here are some addition specifications:
After the ninth reindeer arrives, Santa must invoke prepareSleigh, and then all nine reindeer must invoke getHitched.
After the third elf arrives, Santa must invoke helpElves. Concurrently, all three elves should invoke getHelp.
All three elves must invoke getHelp before any additional elves enter (increment the elf counter).
Santa should run in a loop so he can help many sets of elves. We can assume that there are exactly 9 reindeer, but there may be any number of elves.
This problem has been a staple of the Operating Systems class at U.C. Berkeley for at least a decade. It seems to be based on an exercise in Andrews’s Concurrent Programming .
There are two kinds of threads, oxygen and hydrogen. In order to assemble these threads into water molecules, we have to create a barrier that makes each thread wait until a complete molecule is ready to proceed.
As each thread passes the barrier, it should invoke bond. You must guarantee that all the threads from one molecule invoke bond before any of the threads from the next molecule do.
In other words:
If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.
If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.
We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. The key is just that threads pass the barrier in complete sets; thus, if we examine the sequence of threads that invoke bond and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.
Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.
This is from a problem set written by Anthony Joseph at U.C. Berkeley, but I don’t know if he is the original author. It is similar to the H2O problem in the sense that it is a peculiar sort of barrier that only allows threads to pass in certain combinations.
Somewhere near Redmond, Washington there is a rowboat that is used by both Linux hackers and Microsoft employees (serfs) to cross a river. The ferry can hold exactly four people; it won’t leave the shore with more or fewer. To guarantee the safety of the passengers, it is not permissible to put one hacker in the boat with three serfs, or to put one serf with three hackers. Any other combination is safe.
As each thread boards the boat it should invoke a function called board. You must guarantee that all four threads from each boatload invoke board before any of the threads from the next boatload do.
After all four threads have invoked board, exactly one of them should call a function named rowBoat, indicating that that thread will take the oars. It doesn’t matter which thread calls the function, as long as one does.
Don’t worry about the direction of travel. Assume we are only interested in traffic going in one of the directions.
This problem is from Andrews’s Concurrent Programming , but he attributes it to J. S. Herman’s Master’s thesis.
Suppose there are n passenger threads and a car thread. The passengers repeatedly wait to take rides in the car, which can hold C passengers, where C < n. The car can go around the tracks only when it is full.
Here are some additional details:
Passengers should invoke board and unboard.
The car should invoke load, run and unload.
Passengers cannot board until the car has invoked load
The car cannot depart until C passengers have boarded.
Passengers cannot unboard until the car has invoked unload.
Write code for the passengers and car that enforces these constraints.
This solution does not generalize to the case where there is more than one car. In order to do that, we have to satisfy some additional constraints:
Only one car can be boarding at a time.
Multiple cars can be on the track concurrently.
Since cars can’t pass each other, they have to unload in the same order they boarded.
All the threads from one carload must disembark before any of the threads from subsequent carloads.
modify the previous solution to handle the additional constraints. You can assume that there are m cars, and that each car has a local variable named i that contains an identifier between 0 and m − 1.
This website is provided under a CC BY-SA license by the
The Berea CS Department.
Fall 2013 offering of taught by Matt Jadud