TSL; semaphore operations as class

TSL

TSL (Test and Set Lock) is an atomic hardware instruction TSL RX, LOCK: it copies the memory word LOCK into register RX and then sets LOCK to a non-zero value, with no interrupt or other CPU able to intervene between the two steps.

Why it is used

It is used to implement mutual exclusion (a lock) for a critical region on single and multiprocessor systems:

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

A process enters only if it reads LOCK = 0; otherwise it spins. It is simple and works for many processes, but it uses busy waiting.

Semaphore operations

A semaphore (Dijkstra) is an integer variable accessed only through two atomic operations:

• wait / down / P(S): if S > 0, decrement S and continue; otherwise block the process in the semaphore's queue.
• signal / up / V(S): if some process is blocked on S, wake one; otherwise increment S.

A binary semaphore (0 or 1) gives mutual exclusion; a counting semaphore controls access to a pool of resources.

class Semaphore {
    int value;                 // semaphore value
    queue<Process*> waiting;   // blocked processes
public:
    Semaphore(int v) { value = v; }
    void wait() {              // P / down  (executed atomically)
        value--;
        if (value < 0) {
            waiting.push(current_process());
            block();           // sleep
        }
    }
    void signal() {            // V / up    (executed atomically)
        value++;
        if (value <= 0) {
            Process* p = waiting.front(); waiting.pop();
            wakeup(p);
        }
    }
};

Atomicity is obtained by disabling interrupts or using TSL around these short operations. Usage: Semaphore mutex(1); mutex.wait(); /* critical section */ mutex.signal();