#6–6 作業系統

Semaphores

Semaphores的定義

訊號S是一個整數
有兩個atomic operations
分別是wait() & signal()
以下是定義，實作的話不是長這樣

wait()

wait(S){
    while( S<=0 ){
                    //busy waiting
    }
    S--;
}

signal()

signal(S){
    S++;
}

而Semaphores又分成兩種
分別是Binary semaphores & Counting semaphores

Binary Semaphores

訊號S的值只會是0或1
其實跟Mutex Lock沒什麼差別

Counting Semaphores

訊號S的值並沒有限制
「0」代表沒有人可以進去Critical Section
「-x」代表有x個人在等
「+x」代表可以有x個人同時進去
通常初始值為有限資源的數量(+x)

Q1：如何解決CS的問題？
（用Binary Semaphore來舉例，mutex=1）

A1：

while(true){
    wait(mutex);
    //Critical Section
    signal(mutex);
    //Remainder Section
}

Q2：如果要讓Process2在Process1之後執行，要怎麼達成？

A2：

將synch初始化為0
process1;       //先執行process1  
signal(synch);  //synch = 1
--------------
wait(synch);    //synch = 0
process2;       //等wait完，再執行process2

Semaphores的實作

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

wait()

wait(semaphore *S){
    S->value--;
    if(S->value < 0){
        //把這個process 加到 S->list (也就是等待的佇列)
        sleep(); //一定會發生context switch
    }
}

signal()

signal(semaphore *S){
    S->value++;
    if(S->value <= 0){
        //把一個process 從 S->list裡面拿出來
        wakeup(P);  //不一定會發生context switch
    }
}

優點：在等待的時候，不會一直跑迴圈，CPU可以去做其他事情
缺點：會context switch

如果程式執行時間短，就乾脆用busy waiting
反之，則用Semaphore