TSL instruction and Peterson's algorithm

TSL instruction

TSL (Test and Set Lock) is a hardware instruction TSL RX, LOCK. In one indivisible step it reads the word LOCK into register RX and stores a non-zero value in LOCK. No interrupt or other CPU can intervene, because the memory bus is locked during the instruction.

Use of TSL

It implements mutual exclusion for a critical region:

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 free. A process calls enter_region before and leave_region after its critical section. Only the process that reads 0 enters; the others spin. It works for any number of processes, but uses busy waiting (a spin lock).

Peterson's algorithm

A software solution for mutual exclusion between two processes (0 and 1) with shared variables turn and interested[2].

#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 */
}

Steps:

1. Process sets interested[me] = TRUE and turn = me.
2. It loops while the other is interested and turn is still its own value.
3. If the other is not interested, it enters at once. If both try together, the later write to turn loses: that process waits, and the other enters.
4. On leaving, the process clears its flag, which releases the waiting one.

Properties: mutual exclusion holds (both cannot pass the loop), progress is guaranteed, and each process waits at most one turn (bounded waiting). Limitations: busy waiting and only two processes; on modern CPUs with reordering it needs memory barriers.