Bathroom Synchronization Solutions
Stall privacy
Q1. Mutual exclusion!
Q2. The critical section is the poop_into call. Two users
conflict when they have the same preferred_stall.
Q3.
mutex bathroom;
void user(int preferred_stall) {
lock(&bathroom);
poop_into(preferred_stall);
unlock(&bathroom);
}
At most one user can use the bathroom at a time.
Q4.
mutex stall[K];
void user(int preferred_stall) {
lock(&stall[preferred_stall]);
poop_into(preferred_stall);
unlock(&stall[preferred_stall]);
}
Stall choice
Q5.
mutex stall[K];
void user(void) {
int preferred_stall = random() % K;
lock(&stall[preferred_stall]);
poop_into(preferred_stall);
unlock(&stall[preferred_stall]);
}
Q6.
mutex bathroom;
int stall[K]; // initially 0
void user(void) {
while (1) {
int preferred_stall = -1;
lock(&bathroom);
for (int i = 0; i < K; ++i) {
if (!stall[i]) {
stall[i] = 1; // must be in critical section!
preferred_stall = i;
break;
}
}
unlock(&bathroom);
if (preferred_stall >= 0) {
poop_into(preferred_stall);
lock(&bathroom);
stall[preferred_stall] = 0;
unlock(&bathroom);
return;
}
}
}
Q7.
mutex stall[K];
void user(void) {
int preferred_stall = random() % K;
while (1) {
if (trylock(&stall[preferred_stall])) {
poop_into(preferred_stall);
unlock(&stall[preferred_stall]);
return;
}
preferred_stall = (preferred_stall + 1) % K;
}
}
Q8. The Q7 solution may perform more synchronization calls, because it may make a synchronization call on many locked stalls before finding an unlocked stall. But the Q6 solution performs a minimum of 4 synchronization calls, while the Q7 solution performs a minimum of 2.
Bathroom capacity
Q9. The if statement that checks current capacity and the code
to enter the bathroom (which includes incrementing the occupancy) must
be executed atomically, such that the condition is still true upon
entering the bathroom.
Q10.
mutex stall[K];
mutex bathroom;
int occupancy = 0;
void user(void) {
while (1) {
lock(&bathroom);
if (occupancy < K + 4) {
occupancy++;
unlock(&bathroom);
use_stall();
lock(&bathroom);
occupancy--;
unlock(&bathroom);
return;
} else {
unlock(&bathroom);
}
}
}
void use_stall(void) {
int preferred_stall = random() % K;
while (1) {
if (trylock(&stall[preferred_stall])) {
poop_into(preferred_stall);
unlock(&stall[preferred_stall]);
return;
}
preferred_stall = (preferred_stall + 1) % K;
}
}
Q11. use_stall() is polling, as the thread uses trylock(),
but user() is blocking because it calls lock()
Q12.
mutex stall[K];
mutex bathroom;
cond under_capacity;
int occupancy = 0;
void user(void) {
lock(&bathroom);
while (occupancy >= K + 4) {
wait(&under_capacity, &bathroom);
}
++occupancy;
unlock(&bathroom);
use_stall();
lock(&bathroom);
--occupancy;
if (occupancy < K + 4) { // will always be true!
broadcast(&under_capacity);
}
unlock(&bathroom);
return;
}
// void use_stall(void) remains the same as in Q10
Plumbing protection
Q13.
mutex stall[K];
mutex bathroom;
cond under_capacity;
int occupancy = 0;
mutex attempt_flush;
cond can_flush;
int n_flushing = 0;
// void user(void) remains the same as in Q12
void use_stall(void) {
int preferred_stall = random() % K;
while (1) {
if (trylock(&stall[preferred_stall])) {
poop_into(preferred_stall);
lock(&attempt_flush);
while (n_flushing >= 3) {
wait(&can_flush, &attempt_flush);
}
++n_flushing;
unlock(&attempt_flush);
flush_toilet();
lock(&attempt_flush);
--n_flushing;
broadcast(&can_flush);
unlock(&attempt_flush);
unlock(&stall[preferred_stall]);
return;
}
preferred_stall = (preferred_stall + 1) % K;
}
}
Poopers and cleaners
Q14.
mutex bathroom;
int n_poopers = 0;
int n_cleaners = 0;
void pooper(void) {
while (1) {
if (trylock(&bathroom)) {
if (n_cleaners == 0) {
++n_poopers;
unlock(&bathroom);
poop();
lock(&bathroom);
--n_poopers;
unlock(&bathroom);
return;
} else {
unlock(&bathroom);
}
}
}
}
void cleaner(void) {
while (1) {
if (trylock(&bathroom)) {
if (n_poopers == 0) {
++n_cleaners;
unlock(&bathroom);
clean();
lock(&bathroom);
--n_cleaners;
unlock(&bathroom);
return;
} else {
unlock(&bathroom);
}
}
}
}
Q15.
mutex bathroom;
cv empty_bathroom;
int n_poopers = 0;
int n_cleaners = 0;
void pooper(void) {
lock(&bathroom);
while (n_cleaners > 0) {
wait(&empty_bathroom, &bathroom);
}
++n_poopers;
unlock(&bathroom);
poop();
lock(&bathroom);
--n_poopers;
if (n_poopers == 0) {
broadcast(&empty_bathroom);
}
unlock(&bathroom);
}
void cleaner(void) {
lock(&bathroom);
while (n_poopers > 0) {
wait(&empty_bathroom, &bathroom);
}
++n_cleaners;
unlock(&bathroom);
clean();
lock(&bathroom);
--n_cleaners;
if (n_cleaners == 0) {
broadcast(&empty_bathroom);
}
unlock(&bathroom);
}
Q16. If we were to call signal() instead, we would only wake up
the first thread on the queue. Given our solution above, this would mean
that if (say) 3 cleaners were waiting, they would enter the bathroom
only one at a time, rather than in parallel.
Q17.
mutex bathroom;
cond no_poopers;
cond no_cleaners;
int n_poopers = 0;
int n_cleaners = 0;
void pooper(void) {
lock(&bathroom);
while (n_cleaners > 0) {
wait(&no_cleaners, &bathroom);
}
++n_poopers;
unlock(&bathroom);
poop();
lock(&bathroom);
--n_poopers;
if (n_poopers == 0) {
broadcast(&no_poopers);
}
unlock(&bathroom);
}
void cleaner(void) {
lock(&bathroom);
while (n_poopers > 0) {
wait(&no_poopers, &bathroom);
}
++n_cleaners;
unlock(&bathroom);
clean();
lock(&bathroom);
--n_cleaners;
if (n_cleaners == 0) {
broadcast(&no_cleaners);
}
unlock(&bathroom);
}
Pooping philosophers
Q18. The mutual exclusion problem here is that each philosopher must have 2 curtains in order to poop, and a curtain can only be held by one philosopher at a time.
Q19. One way to accomplish this is by introducing a condition variable / mutex / counter that allows only K-1 philosophers to attempt to draw curtains at any point. This means that even if all the philosophers who are attempting to poop draw their left curtain at the same time, there will be one curtain left over such that one philosopher can poop and then release their curtains, allowing the next one to poop, and so on. We still need to include a lock for each individual curtain to maintain the mutual exclusivity of the resources.
mutex curtain[K];
mutex attempt_draw;
cond can_draw;
int n_drawing;
void philosopher(int x) {
while (1) {
argue();
lock(&attempt_draw);
while (n_drawing >= K) {
wait(&can_draw, &attempt_draw);
}
n_drawing++;
unlock(&attempt_draw);
lock(&curtain[x]);
lock(&curtain[(x + 1) % K]);
poop();
unlock(&curtain[(x + 1) % K]);
unlock(&curtain[x]);
lock(&attempt_draw);
n_drawing--;
if (n_drawing < K) {
broadcast(&can_draw);
}
unlock(&attempt_draw);
}
}
Another way to solve this problem with no deadlock is to impose a “lock order” on the curtains.
mutex curtain[K];
void philosopher(int x) {
int curtain1 = x, curtain2 = (x + 1) % K;
if (curtain1 > curtain2) {
curtain2 = x, curtain1 = (x + 1) % K;
}
while (1) {
argue();
lock(&curtain[curtain1]);
lock(&curtain[curtain2]);
poop();
unlock(&curtain[curtain2]);
unlock(&curtain[curtain1]);
}
}