Semaphore

Introduction

Semaphore 是 integer variable，初始化後只能透過 atomic wait() 與 signal() 存取。

wait() 也叫 P operation；signal() 也叫 V operation。

wait(S) {
    while (S <= 0)
        ;
    S--;
}
 
signal(S) {
    S++;
}

Binary semaphore 只有 0 / 1，可像 mutex lock 一樣提供 mutual exclusion。

Counting semaphore 用值表示有限資源剩餘數量。若有 5 個相同資源，初始化 S = 5；使用前 wait(S)，釋放後 signal(S)。當 S == 0，新 process 必須等待。

Semaphore 也可強制兩段 code 的順序。若 $P_{2}$ 的 S2 必須在 $P_{1}$ 的 S1 之後：

// P1
S1;
signal(synch);
 
// P2
wait(synch);
S2;

synch 初始化為 0，所以 P2 會等到 P1 signal。

OS 可把等待者放進 semaphore waiting queue，避免在 application level 長時間 spin。

typedef struct {
    int value;
    struct process *list;
} semaphore;

wait(S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        sleep();
    }
}

signal(S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

在此版本中，S->value < 0 的 magnitude 表示有多少 process 正在等待。

wait() / signal() 本身仍需要 CAS、spinlock 或 interrupt disabling 保證 atomicity。