Bathroom Synchronization Solutions: Section 2

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.