TSL; producer-consumer using monitors

TSL instruction and its use

TSL (Test and Set Lock) is a hardware instruction, TSL REGISTER, LOCK, which atomically reads the memory word LOCK into a register and then stores a non-zero value in LOCK. No other CPU can access that memory word until the instruction is finished (the memory bus is locked). It is used to implement mutual exclusion for a critical region without disabling interrupts, even on multiprocessors:

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, so loop
    RET                    ; return, now in the critical region

leave_region:
    MOVE LOCK, #0          ; store 0 in LOCK
    RET

A process calls enter_region before and leave_region after its critical region. Because the test and set are indivisible, only one process can see LOCK = 0; this removes the race condition of simple lock variables. It uses busy waiting (a spin lock).

Producer-consumer using monitors

A monitor is a collection of procedures, variables and data structures grouped in a special module; only one process can be active inside a monitor at a time (the compiler enforces mutual exclusion). Condition variables, with the operations wait and signal, are used for synchronization.

monitor ProducerConsumer
    condition full, empty;
    integer count;                       { items in buffer }

    procedure insert(item: integer);
    begin
        if count = N then wait(full);    { buffer full: sleep }
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty); { wake consumer }
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);   { buffer empty: sleep }
        remove := remove_item;
        count := count - 1;
        if count = N - 1 then signal(full); { wake producer }
    end;
begin
    count := 0;
end monitor;

procedure producer;
begin
    while true do begin
        item := produce_item;
        ProducerConsumer.insert(item)
    end
end;

procedure consumer;
begin
    while true do begin
        item := ProducerConsumer.remove;
        consume_item(item)
    end
end;

Since only one process can be inside the monitor, the buffer is never accessed simultaneously, so no mutex is needed. wait blocks the caller and releases the monitor; signal wakes a waiting process. The programmer need not manage mutual exclusion, so errors like wrong down order cannot occur.