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);
}