セマフォは有界待ちを満たす

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（）を呼び出すと、待機リストの1つのプロセスが起床し、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は、新しいプロセスの連続のように入力して生じた、でもおそらく飢餓、無制限の待機時間があります。