Operating Systems #5 — Process Synchronization

Synchronization is about how several processes or threads running at once can reach the data they share safely.

Race conditions

When several processes or threads read and modify shared data at the same time, the final value can end up unintentionally wrong. If one process reads and writes and then another reads, nothing goes wrong. The trouble is overlap.

That situation — several processes reaching shared data at once and trying to change it — is a race condition. Depending on which process finishes last, there's a possibility of a wrong result. What prevents it is synchronization. Things that have nothing to do with you don't need synchronizing, because no race condition can arise.

Increment once and decrement once and the original value should survive; if the two proceed separately, only the increment or only the decrement may land. The cause is interleaved execution — the technique of making several tasks appear simultaneous by having one CPU alternate between them, the opposite of serializable execution. It's everywhere in multitasking and multithreading.

The critical section problem

Formalized: n processes share data, and each has a code segment that touches that data — its critical section. While one process is executing its critical section, the others must be prevented from executing theirs. How you prevent it is the solution.

To count as a solution, all three conditions must hold.

• Mutual exclusion — while process Pi executes its critical section, no other process may execute its own.
• Progress — if no process is in a critical section and some process wants in, that process must not be made to wait indefinitely. "Nobody is inside, but I still can't get in" must not happen.
• Bounded waiting — one particular process must not be left waiting forever. There's a bound on the wait.

You might think mutual exclusion alone is enough, but excessive blocking kills throughput. The other two exist to block without wrecking performance.

A process with a critical section must have an entry section (check whether it may enter) and an exit section (announce that it's done). Those sections hold the variables through which processes share their state.

The software attempts

Algorithm 1 — turn only

A shared variable turn: turn = 0 means it's P0's turn, turn = 1 means P1's.

Mutual exclusion holds, since turn can only hold one value at a time. But progress fails. If P1 has finished and is waiting in while(turn != 0) while P0 is in its remainder section, nobody is in a critical section and yet nobody can enter. The two processes are forced to strictly alternate (swap turn).

Algorithm 2 — flag only

Express the intent to enter with a flag. true means "I want in," and you go in when the other party doesn't. No swap turn, and mutual exclusion holds.

But progress still fails. With both flags true, each defers to the other and nobody enters.

Peterson's algorithm — combine them

Algorithm 1 failed by telling a process that didn't want to enter to enter (no flag). Algorithm 2 failed when both wanted to enter (no turn to break the tie). So combine them.

In the entry section, express the intent (flag = true) and yield the turn to the other. Then spin while the other party wants in and it is simultaneously their turn. That is, either the other having no intent, or the turn being yours, is enough to break out. (Careful: the condition is and, not or.)

No swap turn either — a process in its remainder section has flag = false and no intent, so the other process can enter.

It is a correct solution. But there's a better one, because two things are unsatisfying:

• Busy waiting — you wait by spinning in a while loop, burning CPU.
• The entry section is long. This code has to go into every process that touches the shared data, which makes the code messy.

Locks

The better idea is a lock. The process that gets the lock may execute its critical section; the others wait. Returning it lets a waiting process take it. You only call two simple functions to take and return it, which is much nicer to write against.

For a locking system to work, three things must hold:

1. Only one process may hold the lock at a time.
2. A process trying to take a held lock must wait.
3. Only the process holding the lock may return it.

Disabling interrupts

How do you make sure only one process gets the lock? If P0 ran straight through and then P1 ran straight through, there'd be no problem at all — the critical sections would never overlap. The reason it doesn't work that way on a single core is that CPU scheduling produces interleaved execution.

So on a single core, just prevent CPU scheduling. Once a process enters its critical section, don't let scheduling happen until it's out. Scheduling occurs when the time quantum expires and the CPU has to be handed over (we took it that critical sections don't issue I/O), and the timer, an I/O device, sends the interrupt when the quantum ends. So disable the timer interrupt. Disable it before the critical section and no other process will execute a critical section during it.

The problem: this doesn't work on multicore, only on a uniprocessor.

Atomic hardware — TAS and Swap

The general solution is to be given atomic hardware — circuitry that guarantees the operation isn't interrupted partway. Run the function and it runs to completion in one go. The instructions built this way are Test-and-Set and Swap.

Test and Set (TAS) returns the target's original value while setting the target to true. It's atomic, so no other process can cut in during the call.

// conceptually
boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

// usage
while (TestAndSet(&lock)) ;   // entry section
//   critical section
lock = false;                 // exit section

lock starts false. The first process's TAS sets it true but returns false, so it passes the while. lock stays true throughout its critical section. Another process calling TAS gets true back and spins. The exit section clears lock to false and the spinner gets out.

If TAS weren't atomic, two or more processes could call it while rv = false and all receive false, breaking mutual exclusion.

Swap uses a local variable key. lock is shared as before, and key means "I want in." Swap exchanges lock and key. Whoever got in first sees lock false and key true and passes; anyone arriving mid-way sees both true and stays in the loop.

Semaphores

To solve this in software without hardware help, use a semaphore. Again the goal is a primitive for entry and exit sections. It uses one integer semaphore variable and two functions over it.

• P(S) (wait) — if S is 0 or less, wait. When S goes above 0, subtract 1 and return.
• V(S) (signal) — add 1 to S and return.

This works without atomic hardware because P and V are themselves atomic functions. But how do you get atomicity in software alone? On one core, disable and re-enable interrupts around the bodies of P and V. On several cores, use Peterson's algorithm — the semaphore variable is itself shared data, so apply Peterson inside P and V. Build it once and you never have to build it again.

If P and V weren't atomic, two or more processes could enter P's while loop at the same time and pass it together.

Block/wakeup semaphores

The semaphore still has busy waiting inside it. Instead of spinning in P's while loop, put the process to sleep.

Make the semaphore variable a struct rather than an int. The original integer goes into int value, and a pointer to struct proc is added — which makes a linked list.

• If the condition isn't met inside P, block (sleep) and append to the list.
• On the way out of the critical section, wake one of them up.

S.value starts at 1. The first process drives it to 0 and passes straight through. Once it goes negative, the caller is appended and blocked. |S.value| is the queue length. When the first process leaves the critical section and calls V, value goes up by 1; if it isn't 1, someone is waiting, so wakeup is called and the head of the queue is released. If it is 1, nobody is waiting.

A semaphore that expresses the number of waiting processes is an integer semaphore; one that only says whether anyone waits is a binary semaphore.

With no while loop there's no wasted CPU. But it isn't free: blocking a process, appending it to the list, and waking it are all overhead. If the critical section is short, spinning may actually be faster. So a developer picks a plain semaphore when the section is guaranteed short, and a block/wakeup semaphore otherwise. With many processes running at once, block/wakeup beats having them all spin.

On performance alone, atomic hardware beats semaphores. If the hardware offers atomic instructions, use a locking system; if not, use semaphores.

Locks versus semaphores

From the lab — one question asked what a race condition is and why locks and semaphores are needed, and another asked for the difference between the two.

A race condition is when several processes or threads touching the same shared resource run interleaved and can produce a different result than they would serially. Locks and semaphores exist to prevent that inside critical sections.

The difference: a lock lets exactly one process reach the shared resource, while a semaphore's count lets you admit several. Once a lock is handed out nobody else gets in until it's returned, but setting an integer semaphore to 2 admits up to two.

The analogy I settled on at the time was a rollercoaster. Only one person sits in a seat, but many people ride the same coaster. The seat is the lock; the coaster is the semaphore.

Producer-consumer

Another question gave source code and asked us to find the critical section, explain why, and propose a fix. It was producer-consumer code.

If num_items is 0 and the consumer slips past the if, the index advances but nothing leaves the buffer. Conversely, if num_items equals the buffer size and the producer slips past its if, the index advances anyway — so fewer than the intended 50,000 items get produced and consumed.

The fix is condition variables: the consumer waits while the buffer is empty and is signalled once the producer produces, and the producer waits while the buffer is full and is signalled once the consumer consumes.

// consumer
while (num_items == 0)
    pthread_cond_wait(&not_empty, &mutex);

// producer
while (num_items == BUFFER_SIZE)
    pthread_cond_wait(&not_full, &mutex);

One thing this question taught me: a race condition can come from somewhere other than the code you're staring at.

Critical sections inside the OS

Kernel code touches shared data itself. Three cases.

(1) While running interrupt handling code

Kernel code does count++ — read, increment, store. If an interrupt arrives before the increment, control jumps to the handler, and the handler is kernel code too, so it can touch the kernel variable count. It decrements, finishes, and control returns to complete the increment — and the result isn't what was intended. Adding interrupt disable/enable around it fixes this.

(2) Through scheduling between processes

If scheduling happens partway through a system call, another process's kernel code can touch the same variable. UNIX's approach is to prevent CPU scheduling while a system call is executing.

(3) When there are several CPUs

On a multiprocessor, disabling interrupts doesn't help — it blocks interrupts on one CPU and has no effect on the others.

One approach is to treat the whole kernel as one giant critical section: while one CPU is in kernel mode, no other CPU may enter kernel mode. One system call at a time. A process running on another CPU that calls a system call can't proceed. That's a serious performance problem, and adding CPUs doesn't buy proportional gains because of all the blocking.

The other approach is to apply synchronization tools to individual kernel variables. More complicated, but faster. Which one to use is up to the OS vendor.

sleep and spinlocks in xv6, and deadlock

From the lab — one question asked why xv6's sleep needs a spinlock struct.

If sleep changed the state to sleeping without taking the lock, the process could get picked out of the ptable and run while it's in the middle of going to sleep. Hence the lock.

acquiresleep and releasesleep are needed to stop another process from touching the shared resource this process uses while it sleeps. If process i, using shared resource A, goes to sleep and process j sharing it changes the value, the value i was working with no longer holds.

Deadlock

The same lab gave code containing a deadlock and asked how it was removed and to explain it against the deadlock conditions.

send and recv share the mutex resource; it can't be taken away by force (no preemption), whoever holds it doesn't release it (hold and wait), and only one of them can use it (mutual exclusion) — so you get circular wait. The fix is to not hold and wait: if you can't use it, let it go.