Process synchronization, Peterson, TSL

Why synchronization is needed

Processes that share data (a variable, file or buffer) must be synchronized because the result of their execution would otherwise depend on the exact order in which the CPU schedules them.

• Avoid race conditions: if two processes read-modify-write the same shared variable at the same time, one update can be lost and the data becomes inconsistent.
• Mutual exclusion: only one process may be inside its critical section (the code that touches shared data) at a time.
• Ordering and cooperation: a consumer must wait until the producer has put data in the buffer; a producer must wait when the buffer is full.
• Avoid deadlock and starvation while sharing resources.

Example: two processes execute counter++. Each loads counter (5) into a register, adds 1 and stores back. If a switch occurs after the load, both store 6 and one increment is lost (expected 7).

Peterson's solution

Peterson's algorithm is a software solution for two processes (P0, P1) using busy waiting. It uses two shared variables: turn (whose turn it is to enter) and interested[2] (a flag per process).

#define N 2                  /* two processes: 0 and 1 */
int turn;                    /* whose turn is it? */
int interested[N];           /* all FALSE at start */

void enter_region(int process) {
    int other = 1 - process;
    interested[process] = TRUE;   /* I want to enter */
    turn = process;               /* but let the other go first if it wants */
    while (turn == process && interested[other] == TRUE)
        ;                         /* busy wait */
}
void leave_region(int process) {
    interested[process] = FALSE;  /* I have left the critical region */
}

How it works:

1. A process sets its flag and writes its own number in turn (politely offering the other process priority). It then waits only while the other process is interested and turn still holds its own number.
2. If only one process wants to enter, the other flag is FALSE, so it enters at once.
3. If both arrive together, both set turn; the one that wrote turn last is the one whose condition stays true, so it waits and the other enters. Then the waiting process enters after leave_region.

It satisfies mutual exclusion, progress and bounded waiting, without special hardware. Its drawbacks are busy waiting (wasted CPU) and that it works for two processes only.

TSL (Test and Set Lock) instruction

TSL is a hardware instruction TSL RX, LOCK. It reads the memory word LOCK into register RX and stores a non-zero value in LOCK, as one indivisible (atomic) operation; the memory bus is locked for other CPUs meanwhile.

enter_region:
    TSL REGISTER, LOCK   | copy LOCK to REGISTER, set LOCK = 1
    CMP REGISTER, #0     | was LOCK zero?
    JNE enter_region     | if not zero, lock was set: loop again
    RET                  | LOCK was 0, now 1: enter critical region

leave_region:
    MOVE LOCK, #0        | store 0 in LOCK
    RET                  | return to caller

• LOCK = 0 means the critical region is free; any process may enter by executing TSL.
• If TSL returns 0, the caller has acquired the lock (LOCK is now 1) and enters. If it returns 1, someone else holds it and the caller loops (spin lock).
• Works for any number of processes and on multiprocessors, but it also wastes CPU in busy waiting and may suffer priority inversion.