总是说当信号量计数为0时，请求信号量的进程被阻塞并添加到等待队列中。
当某个进程释放信号量并且计数从0-> 1增加时，会激活阻塞进程。这可以是从被阻止的进程中随机挑选的任何进程。调度等待信号量的进程
现在我的问题是：
如果它们被添加到队列中，为什么激活阻塞进程不是按照FIFO的顺序？我认为从队列中选择下一个进程将比较容易，而不是随机选择一个进程并授予信号量。如果这个随机逻辑背后有一些想法，请解释一下。另外，内核如何从队列中随机选择一个进程？ 从队列中获取一个随机过程，就队列数据结构而言，这是一件复杂的事。
标签：各种操作系统每个有内核通常写在C++和互斥股类似的概念
这并不是说不能做到先进先出;事实上，我敢打赌，许多实现都只是因为你说的原因。规范并不是说这个过程是随机选择的;它是没有指定的，所以你的程序不应该依赖它以任何特定的方式被选择。 （它可以随机选择;仅仅因为它不是最快的方法并不意味着它不能完成。）
这就是我所关心的。如果有人写内核，做一个随机拾取，他的思想和他的策略，数据结构等后面可以有什么动机。 不确定信号量，但是，如果是互斥量，线程会随机唤醒。他们都会分享我猜想的模拟逻辑。所以我缺少一些东西。 它使我认为一些进程会继续检查，然后如果它发现信号量val> 0，它会得到它，其他人将被阻止，这与理论所说的相反，我在这里寻求极客的帮助这里8-） – Abhinav 2012-01-05 19:14:39
并不是有人写了一个使用rand（）选择要释放的线程的信号量。那将是疯狂。就是有一堆东西在继续，你看不到它看起来是随机的。例如，假设线程是按FIFO顺序释放的，但量子在ret返回到您的代码之前结束，而另一些线程在您重新计划之前运行。这使得它看起来是随机的，即使内核仍在使用FIFO。 – Stewart 2012-01-09 14:00:59
进程调度算法非常专用于系统功能和操作系统设计。这个问题很难给出很好的答案。如果我在一般的个人电脑上，我想要一些吞吐量和平均等待/响应时间的东西。如果我在一个系统中知道我所有工作的优先级，并且知道我绝对希望我的所有高优先级任务先运行（并且不关心抢先/匮乏），那么我需要优先级算法。
就随机选择而言，动机可能是由于各种原因。一种是如上所述的吞吐量良好等等。然而，这将是非确定性的（假设）并且不可能证明。这个属性可能是对概率的利用（随机样本等），但是，再次，证据只能基于经验数据是否真的有效。
FIFO是系统 中等待列表的最简单的数据结构，它不支持优先级，但它不是绝对回答 。根据所选择的调度算法，不同的线程可能具有不同的绝对优先级，或某种类型的衰减优先级可能有效，在这种情况下，操作系统可能会选择 在某些先前的时间间隔中CPU时间最少的线程。 由于这种策略被广泛使用（特别是后者），所以通常的规则是考虑你不知道（尽管绝对优先级为绝对的，它将是具有最高优先级的线程之一）。
当一个进程“随机”调度时，并不是随机选择一个进程;这是选择过程不可预测的。
Windows内核使用的算法是有一个线程队列（Windows调度“线程”，而不是“进程”）等待信号量。当信号被释放时，内核调度在队列中等待的下一个线程。但是，调度线程并不会立即使该线程开始执行;它只是使线程能够通过将其放入等待运行的线程队列中来执行。直到CPU没有更高优先级的线程执行时，线程才会真正运行。
当线程在调度队列中等待时，实际执行的另一个线程可能会等待相同的信号量。在传统的队列系统中，新的线程将不得不停止执行并进入队列末尾等待信号量的队列。
但是，在最近的Windows内核中，新线程不必停下来等待该信号量。如果已分配信号量的线程仍在运行队列中，则信号量可能会重新分配给旧线程，导致旧线程返回等待信号量。
这样做的好处是，线程即将在队列中等待信号量，然后在队列中等待运行将不必等待。缺点是你无法预测下一个线程是否会实际获得信号量，这是不公平的，因此等待信号量的线程可能会挨饿。
这里所有其他的答案是基本问题的巨大描述 - 尤其是在线程的优先级和就绪队列。另一件要考虑的事情是IO。我只是在这里谈论Windows，因为它是我知道的唯一一个权威平台，但其他内核可能有类似的问题。
在Windows上，当IO完成时，称为内核模式APC（异步过程调用）的内容会针对启动IO的线程排队，以便完成它。如果线程恰好等待调度程序对象（例如您的示例中的信号量），那么线程将从该对象的等待队列中删除，导致（内部内核模式）等待（类似于）STATUS_ALERTED等待。现在，由于这些内核模式的APC是一个实现细节，并且您无法从用户模式看到它们，所以WaitForMultipleObjects的内核实现将重新启动等待，这会导致您的线程被推送到队列的后面。从内核模式的角度来看，队列仍然是FIFO的顺序，因为底层的等待API的第一个调用者仍然在队列的头部，但从你的角度来看，在用户模式下，你只是被推到队列的后面由于你没有看到，很可能无法控制。这使得队列顺序在用户模式下显示为随机。这个实现仍然是一个简单的FIFO，但是由于IO的存在，它看起来不像更高层次的抽象。
我在这里猜测了一下，但我原以为类似unix的操作系统在信号传递和内核需要劫持进程以在其上下文中运行的地方有类似的约束。
现在这并不总是会发生，但文档必须是保守的，除非顺序明确保证是FIFO（如上所述 - 对于Windows至少 - 它不能），那么排序是在文档中描述为“随机”或“无证”或某事，因为随机过程控制它。它也让操作系统供应商在稍后改变排序。
您似乎正在交替使用“Q”和“队列”。也许这就是你混乱的根源。 – Gabe 2012-01-05 19:15:22
Q队列在这里 – Abhinav 2012-01-05 19:17:33