Interprocessor synchronization

Interprocessor synchronization is the coordination of processors that share data or resources, to make sure that the order of operations is right. Mutual exclusion is needed so that only one processor uses a shared resource (a critical section) at a time. It is implemented with a binary semaphore (a variable in shared memory: 0 = free, 1 = in use).

Mechanism: test-and-set (TSL) instruction

The processor reads the semaphore and sets it to 1 in one indivisible (atomic) memory cycle, locking out other processors from the memory during it:

TSL SEM:   R <- M[SEM] ;  M[SEM] <- 1      (atomic)

Entry:     TSL SEM          ; test and set
           CMP R, #0        ; was it free?
           BNE Entry        ; no, loop (busy wait)
           ... critical section ...
Exit:      CLR SEM          ; M[SEM] <- 0 releases the lock

Example

Processors P1 and P2 both want to update a shared counter. P1 executes TSL: R = 0, the semaphore becomes 1, so P1 enters the critical section. P2 executes TSL: R = 1, so it keeps looping. When P1 finishes, it clears the semaphore to 0. P2's next TSL gets R = 0 and then P2 enters. This prevents both from updating the counter at the same time.