Operating Systems
This problem was inspired by a problem proposed by Kenneth Reek . Imagine a sushi bar with 5 seats. If you arrive while there is an empty seat, you can take a seat immediately. But if you arrive when all 5 seats are full, that means that all of them are dining together, and you will have to wait for the entire party to leave before you sit down.
write code for customers entering and leaving the sushi bar that enforces these requirements.
Max Hailperin wrote this problem for his textbook Operating Systems and Middleware . At a child care center, state regulations require that there is always one adult present for every three children.
Write code for child threads and adult threads that enforces this constraint in a critical section.
One feature of this solution is that an adult thread waiting to leave can prevent child threads from entering.
Imagine that there are 4 children and two adults, so the value of the multiplex is 2. If one of the adults tries to leave, she will take two tokens and then block waiting for the third. If a child thread arrives, it will wait even though it would be legal to enter. From the point of view of the adult trying to leave, that might be just fine, but if you are trying to maximize the utilization of the child care center, it’s not.
write a solution to this problem that avoids unnecessary waiting.
Hint: think about the dancers in Section [dancers].
I wrote this problem while I was at Colby College. One semester there was a controversy over an allegation by a student that someone from the Dean of Students Office had searched his room in his absence. Although the allegation was public, the Dean of Students wasn’t able to comment on the case, so we never found out what really happened. I wrote this problem to tease a friend of mine, who was the Dean of Student Housing.
The following synchronization constraints apply to students and the Dean of Students:
Any number of students can be in a room at the same time.
The Dean of Students can only enter a room if there are no students in the room (to conduct a search) or if there are more than 50 students in the room (to break up the party).
While the Dean of Students is in the room, no additional students may enter, but students may leave.
The Dean of Students may not leave the room until all students have left.
There is only one Dean of Students, so you do not have to enforce exclusion among multiple deans.
write synchronization code for students and for the Dean of Students that enforces all of these constraints.
This problem was originally based on the Senate bus at Wellesley College. Riders come to a bus stop and wait for a bus. When the bus arrives, all the waiting riders invoke boardBus, but anyone who arrives while the bus is boarding has to wait for the next bus. The capacity of the bus is 50 people; if there are more than 50 people waiting, some will have to wait for the next bus.
When all the waiting riders have boarded, the bus can invoke depart. If the bus arrives when there are no riders, it should depart immediately.
Write synchronization code that enforces all of these constraints.
This problem was written by Grant Hutchins, who was inspired by a friend who took her Oath of Citizenship at Faneuil Hall in Boston.
“There are three kinds of threads: immigrants, spectators, and a one judge. Immigrants must wait in line, check in, and then sit down. At some point, the judge enters the building. When the judge is in the building, no one may enter, and the immigrants may not leave. Spectators may leave. Once all immigrants check in, the judge can confirm the naturalization. After the confirmation, the immigrants pick up their certificates of U.S. Citizenship. The judge leaves at some point after the confirmation. Spectators may now enter as before. After immigrants get their certificates, they may leave.”
To make these requirements more specific, let’s give the threads some functions to execute, and put constraints on those functions.
Immigrants must invoke enter, checkIn, sitDown, swear, getCertificate and leave.
The judge invokes enter, confirm and leave.
Spectators invoke enter, spectate and leave.
While the judge is in the building, no one may enter and immigrants may not leave.
The judge can not confirm until all immigrants who have invoked enter have also invoked checkIn.
Immigrants can not getCertificate until the judge has executed confirm.
This problem was written by Jon Pollack during my Synchronization class at Olin College.
Students in the dining hall invoke dine and then leave. After invoking dine and before invoking leave a student is considered “ready to leave”.
The synchronization constraint that applies to students is that, in order to maintain the illusion of social suave, a student may never sit at a table alone. A student is considered to be sitting alone if everyone else who has invoked dine invokes leave before she has finished dine.
write code that enforces this constraint.
The Dining Hall problem gets a little more challenging if we add another step. As students come to lunch they invoke getFood, dine and then leave. After invoking getFood and before invoking dine, a student is considered “ready to eat”. Similarly, after invoking dine a student is considered “ready to leave”.
The same synchronization constraint applies: a student may never sit at a table alone. A student is considered to be sitting alone if either
She invokes dine while there is no one else at the table and no one ready to eat, or
everyone else who has invoked dine invokes leave before she has finished dine.
write code that enforces these constraints.
This website is provided under a CC BY-SA license by the
The Berea CS Department.
Fall 2013 offering of taught by Matt Jadud