Bathroom Synchronization Solutions: Section 1
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 test (“bathroom has fewer than K+4 occupants”) and the entry (“enter bathroom”).
Q10. Several solutions are possible; here’s one, based on Q7.
mutex stall[K], occupants;
int noccupants;
void user(void) {
int entered = 0;
while (!entered) {
lock(&occupants);
if (noccupants < K + 4) {
++noccupants;
entered = 1;
}
unlock(&occupants);
}
enter_bathroom();
int preferred_stall = random() % K;
while (1) {
if (trylock(&stall[preferred_stall])) {
poop_into(preferred_stall);
unlock(&stall[preferred_stall]);
break;
}
preferred_stall = (preferred_stall + 1) % K;
}
leave_bathroom();
lock(&occupants);
--noccupants;
unlock(&occupants);
}
Q11. Polling. Any correct mutex-only solution will involve polling.
Q12.
cond space_available; // condition: noccupants < K + 4
mutex occupants;
int noccupants;
mutex stall[K];
void user(void) {
lock(&occupants);
while (noccupants >= K + 4)
wait(&space_available, &occupants);
++noccupants;
unlock(&occupants);
enter_bathroom();
int preferred_stall = random() % K;
while (1) {
if (trylock(&stall[preferred_stall])) {
poop_into(preferred_stall);
unlock(&stall[preferred_stall]);
break;
}
preferred_stall = (preferred_stall + 1) % K;
}
leave_bathroom();
lock(&occupants);
--noccupants;
unlock(&occupants);
signal(&space_available);
}
Plumbing protection
cond space_available; // condition: noccupants < K + 4
mutex occupants;
int noccupants;
cond flush_available; // condition: nflushers < 3
mutex flushers;
int nflushers;
mutex stall[K];
void user(void) {
lock(&occupants);
while (noccupants >= K + 4)
wait(&space_available, &occupants);
++noccupants;
unlock(&occupants);
enter_bathroom();
int preferred_stall = random() % K;
while (1) {
if (trylock(&stall[preferred_stall])) {
poop_into(preferred_stall);
lock(&flushers);
while (nflushers < 3)
wait(&flush_available, &flushers);
++nflushers;
unlock(&flushers);
flush();
lock(&flushers);
--nflushers;
unlock(&flushers);
signal(&flush_available);
unlock(&stall[preferred_stall]);
break;
}
preferred_stall = (preferred_stall + 1) % K;
}
leave_bathroom();
lock(&occupants);
--noccupants;
unlock(&occupants);
signal(&space_available);
}