Bathroom Synchronization: 11/29

Ah, the bathroom. Does anything deserve more careful consideration? Is anything more suitable for poop jokes? In today’s exercise, you will gain experience with synchronization primitives through a series of bathroom-themed conceptual exercises.

Enter your solutions here.

The primitives

Recall that we are dealing with two main primitives, mutexes and condition variables.

A mutex can be in two states, “unlocked” (the initial state) and “locked by thread T”. A mutex has the following operations:

lock (e.g., pthread_mutex_lock(&m)): Block until the mutex is unlocked, then atomically lock it (set its state to “locked by this thread”).
unlock (e.g., pthread_mutex_unlock(&m)): The mutex must be locked by this thread. The call unlocks the mutex (sets its state to “unlocked”).
trylock (e.g., pthread_mutex_trylock(&m)): Locks the mutex if it isn’t currently locked, otherwise returns an error. The pthread version returns 0 on success (the mutex is now locked by this thread), EBUSY on error (the mutex was locked by a different thread). Never blocks.

A condition variable’s state consists of a set of waiting threads. A condition variable has the following operations:

wait (e.g., pthread_cond_wait(&cv, &m)): The mutex must be locked by this thread. The call atomically unlocks the mutex and adds the current thread to the CV’s wait set. Once it’s woken up, the thread re-locks the mutex before returning from wait.
signal (e.g., pthread_cond_signal(&cv)): Wake up one thread in the CV’s wait set. It is not an error if no threads are waiting on the CV.
broadcast (e.g., pthread_cond_broadcast(&cv)): Wake up all threads in the CV’s wait set (if any).

A condition variable is usually associated with some predicate or condition: a boolean expression, such as “value is greater than 5,” where a thread waits on the condition variable because it wants the predicate to come true. The predicate should be covered by the CV’s associated mutex, meaning that changes to the predicate’s value require holding that mutex. A thread that makes the predicate become true should call signal or broadcast to inform any waiting threads. However, due to race conditions, it is almost always possible for the condition to become false again in between the signal and the moment when the waiting thread wakes up. (For example, another thread could sneak in.) For this reason, wait is almost always called in a loop that checks the condition. Similarly, signal and broadcast calls are often performed by threads that recently locked the CV’s associated mutex.

Stall privacy

The setting is a bathroom with K stalls numbered 0 through K–1. A number of users enter the bathroom; each has a preferred stall. Each user can be modeled as an independent thread running this code:

void user(int preferred_stall) {
    poop_into(preferred_stall);
}

You probably can intuitively smell that this bathroom model has a synchronization problem.

Q1. What synchronization property is missing?

Q2. Where is the critical section in user, and when do two users conflict?

Q3. Provide synchronization using a single mutex, i.e., using coarse-grained locking. You can use pthread syntax for this mutex, or make up your own syntax (as long as the meaning is clear). Your solution should be correct (it should avoid gross conditions*), but it need not be efficient. Your solution will consist of (1) a definition for the mutex, which must be a global variable, and (2) new code for user().

*Tip: A “gross condition” is a race condition in the context of a bathroom-themed synchronization problem.

Q4. Provide synchronization using fine-grained locking. Your solution should be more efficient than the Q3 solution. Specifically, it should allow the bathroom to achieve full utilization: it should be possible for all K stalls to be in use at the same time. You will need to change both the global mutex—there will be more than one global mutex—and the code for user().

Check your work

Stall choice

The setting is the same, except that users have no preferred stall:

void user(void) {
    int preferred_stall = random() % K;
    poop_into(preferred_stall);
}

Q5. Adapt this function to use your synchronization solution from Q4.

Q6. As written, the user code picks a preferred stall and then waits for that stall to become available. This isn’t as efficient as possible, since multiple users might pick the same stall by chance. Write a synchronization solution where each user chooses any available stall. First, use a single mutex coupled with a global data structure representing stall occupancy.

Any correct solution will contain at least two different calls to lock (or trylock) functions and two different calls to unlock functions. A solution with only one lock call has either a race condition, a deadlock, or underutilization (at most one user in the bathroom at a time).

Q7. Second, repeat your solution using multiple mutexes and no additional global variables.

Q8. Compare these solutions in terms of the number of synchronization calls made per user.

Check your work

Bathroom capacity

Your solution in Q8 allows an arbitrary number of users to wait in the bathroom for a stall. The fire marshal says no no: at most K + 4 occupants are allowed at a time (one per stall, plus 4 using the sink). We want a user model like this:

void user(void) {
    while (1) {
        if (the bathroom has fewer than `*`K`*`+4 occupants) {
            enter bathroom;
            poop in empty stall;
            leave bathroom;
            return;
        }
    }
}

Q9. Which parts of this user model must be executed atomically to avoid race conditions where the bathroom has more than K+4 occupants? That is, which critical section avoids overoccupancy?

Q10. Write a synchronization solution that avoids both overoccupancy and gross conditions. Use only one or more mutexes—no condition variables. Tell us what global state you use.

As synchronization problems get more complicated, more code is required to solve them. You may want to sketch pseudocode or copy and paste working code from earlier exercises.

Q11. Is your solution blocking or polling?

Q12. Improve your solution’s “CPU usage” by adding one or more condition variables. In your solution, a user thread should block until there’s a very good chance that the bathroom has fewer than K+4 occupants. Say what predicate is associated with each condition variable.

Plumbing protection

Q13. Harvard has old plumbing, and if more than 3 users flush at the same time, the bathroom will explode. Write code that avoids this gross condition, starting from your solution to Q12. Your user threads should block until they have a chance to flush, and it should be possible for 3 users to flush simultaneously. This will involve another condition variable (why?).

void user(void) {
    while (1) {
        if (the bathroom has fewer than K+4 occupants) {
            enter bathroom;
            poop in empty stall;
            while (3 or more users are flushing)
                block; // heh
            flush;
            leave bathroom;
            return;
        }
    }
}

Poopers and cleaners

Bathrooms sometimes need to be cleaned. In this version of the synchronization problem, there are two kinds of users, poopers and cleaners. A bathroom may have one or more poopers in it, or one or more cleaners, but it should never have both a pooper and a cleaner. The threads can be modeled this way:

void pooper(void) {
    while (1) {
        if (the bathroom has no cleaners) {
            enter bathroom;
            poop;
            leave bathroom;
            return;
        }
    }
}

void cleaner(void) {
    while (1) {
        if (the bathroom has no poopers) {
            enter bathroom;
            clean;
            leave bathroom;
            return;
        }
    }
}

For simplicity’s sake we’ve dropped most of the earlier parts (stall synchronization, bathroom capacity, and plumbing protection).

Q14. Write a solution for this problem that involves mutexes only. As usual, this solution will cause some users to poll.

Q15. Write a solution for this problem involving one condition variable. A user should block until they have some chance to enter the bathroom. However, since you have only one condition variable, your solution will necessarily involve false wakeups (you may wake up a user who cannot enter the bathroom yet).

Q16. Your solution for Q15 should involve the broadcast operation. What could go wrong if you used signal?

Q17. Write a solution for this problem involving two condition variables. This solution should have fewer false wakeups.

Pooping philosophers

To facilitate the communal philosophical life, Plato decreed that philosophy should be performed in a bathroom with K thrones and K curtains, arranged like so:

Each philosopher sits on a throne with two curtains, one on each side. The philosophers normally argue with one another. But sometimes a philosopher’s got to poop, and to poop one needs privacy. A pooping philosopher must first draw the curtains on either side; philosopher X will need curtains X and (X+1) mod K. For instance, here, philosophers 0 and 2 can poop simultaneously:

But philosopher 4 cannot poop until philosopher 0 is done (because philosopher 4 needs curtain 0), and philosopher 1 cannot poop until philosophers 0 and 2 are both done.

Q18. In high-level terms, what is the mutual exclusion problem here—that is, what resources are subject to mutual exclusion?

Q19. A philosopher could be described like so:

void philosopher(int x) {
    while (1) {
        argue();
        draw curtains `*`x`*` and (`*`x`*` + 1) % `*`K`*`;
        poop();
        release curtains `*`x`*` and (`*`x`*` + 1) % `*`K`*`;
    }
}

Write a correctly-synchronized version of this philosopher. Your solution should not suffer from deadlock, and philosophers should block (not poll) when they are waiting to poop.