做信號量滿足有界等待

Question

信號量滿足有界等待還是隻是爲了提供互斥？

Answer 1

回答

它可能會破壞理論界待機中，你會看到如下。實際上，這在很大程度上取決於使用哪種調度算法。

經典落實wait()和signal()原始是：

//primitive 
wait(semaphore* S) 
{ 
    S->value--; 
    if (S->value < 0) 
    { 
     add this process to S->list; 
     block(); 
    } 
} 

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

當一個進程調用wait()和失敗的「如果」測試，它會把自己變成一個等待名單。如果多個進程在同一個信號量上被阻塞，它們都會被放入這個列表中（或者你可以想象它們以某種方式連接在一起）。當另一個進程離開關鍵部分並調用signal（）時，等待列表中的一個進程將被選中喚醒，準備再次與CPU競爭。但是，調度程序決定從等待列表中選擇哪個進程。例如，如果調度以LIFO（後進先出）方式實現，則某些進程可能處於餓死狀態。

例

T1: thread 1 calls wait(), enters critical section 
T2: thread 2 calls wait(), blocked in waiting list 
T3: thread 3 calls wait(), blocked in waiting list 
T4: thread 1 leaves critical section, calls signal() 
T5: scheduler wakes up thread 3 
T6: thread 3 enters critical section 
T7: thread 4 calls wait(), blocked in waiting list 
T8: thread 3 leaves critical section, calls signal() 
T9: scheduler wakes up thread 4 
.. 

正如你可以看到，儘管你實現/正確地使用信號量，螺紋2具有無界的等待時間，甚至可能飢餓，引起新流程的持續進入。