等待信号量的进程调度

Question

通常说，当信号量的计数为0时，请求信号量的进程将被阻塞并添加到等待队列中。

当某些进程释放信号量，计数从0->1增加时，阻塞进程将被激活。这可以是任意进程，从阻塞的进程中随机选择。

现在我的问题是：

如果将它们添加到队列中，为什么阻塞进程的激活不符合FIFO顺序？我认为从队列中选择下一个进程将是很容易的，而不是随机地捡起一个进程并授予它信号量。如果这个随机逻辑背后有什么想法，请解释。另外，内核是如何从队列中随机选择进程的呢?对于队列数据结构而言，从队列中获得一个随机进程也是一件复杂的事情。

标记：各种OSes，因为每个都有一个内核，通常用C++编写，mutex共享类似的概念。

Answer 1

FIFO是不支持优先级的系统中等待列表的最简单的数据结构，但它不是绝对的答案。根据所选择的调度算法，不同的线程可能具有不同的绝对优先级，或者某种衰减的优先级可能生效，在这种情况下，操作系统可能选择在前一段时间内CPU时间最少的线程。由于这些策略被广泛使用(特别是后者)，通常的规则是考虑您不知道(尽管具有绝对优先级，但它将是具有最高优先级的线程之一)。

Answer 2

当一个进程被“随机”排定时，并不是说一个进程是随机选择的，而是选择过程是不可预测的。

Windows内核使用的算法是，在信号量上有一个线程队列(Windows调度“线程”，而不是“进程”)。当信号量释放时，内核会调度队列中等待的下一个线程。但是，调度线程不会立即使线程开始执行；它只是通过将线程放在等待运行的线程队列中来使线程能够执行。在CPU没有更高优先级的线程执行之前，线程将不会实际运行。

当线程在调度队列中等待时，另一个实际正在执行的线程可能会在同一个信号量上等待。在传统的队列系统中，这个新线程必须停止执行，然后进入排队等待信号量的队列的末尾。

然而，在最近的Windows内核中，新线程不必停止等待信号量。如果分配给信号量的线程仍然处于运行队列中，则信号量可能被重新分配到旧线程，从而导致旧线程再次返回等待信号量。

这样做的好处是，要在队列中等待信号量，然后在队列中等待才能运行的线程将根本不必等待。缺点是您无法预测下哪个线程将实际获得信号量，这是不公平的，因此等待信号量的线程可能会饿死。

Answer 3

这并不是说它不可能是FIFO；事实上，我敢打赌很多实现都是这样的，只是因为您所述的原因。规范并不是进程是随机选择的，而是它没有被指定，所以您的程序不应该依赖于以任何特定的方式选择它。(它可以随机选择；仅仅因为它不是最快的方法，并不意味着它无法完成。)