信号量是否满足有界等待或只是提供互斥?
回答
从理论上讲,它可能会破坏有界等待条件,如下所示。实际上,这严重依赖于使用哪种调度算法。
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()
并失败了“if”测试时,它会将自己放入等待列表中。如果有多个进程在同一信号量上被阻塞,它们都会被放入这个列表中(或者像你想象的那样链接在一起)。当另一个进程离开关键区域并调用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具有无限等待时间,甚至可能由于不断进入新进程而导致饥饿。