Semaphore operations with pseudocode

A semaphore is a synchronization variable (an integer with an associated queue of blocked processes), introduced by E. W. Dijkstra, which can be accessed only through two atomic operations. It is used to protect critical sections and to synchronize processes without busy waiting.

Major operations

1. Initialisation: the semaphore is given a non-negative value (1 for a mutex, N for N resources).
2. down (P, wait): tries to decrement the value; if the value is 0, the process is blocked.
3. up (V, signal): increments the value or wakes up a blocked process.

Pseudocode

typedef struct {
    int value;                 /* count */
    struct process *list;      /* queue of blocked processes */
} semaphore;

void down(semaphore *S) {      /* P operation */
    S->value = S->value - 1;
    if (S->value < 0) {
        add this process to S->list;
        block();               /* sleep */
    }
}

void up(semaphore *S) {        /* V operation */
    S->value = S->value + 1;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

(The simple version is: down(S): while (S <= 0) wait; S--; and up(S): S++;. The blocking version above avoids busy waiting.) Both procedures execute as indivisible actions, with interrupts disabled or with a TSL lock, so two processes cannot change S simultaneously.

Use for mutual exclusion

semaphore mutex = 1;
down(&mutex);
   /* critical section */
up(&mutex);

A binary semaphore takes only the values 0 and 1; a counting semaphore takes any non-negative value. Semaphores are also used for synchronization (producer-consumer, dining philosophers, readers-writers).