做信号量满足有界等待

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具有无界的等待时间，甚至可能饥饿，引起新流程的持续进入。