等待信号量的进程的调度
人们总是说，当信号量的计数为 0 时，请求该信号量的进程将被阻塞并添加到等待队列中。
当某个进程释放信号量并且计数从0增加到>1时，阻塞进程被激活。这可以是从被阻止的进程中随机挑选的任何进程。
现在我的问题是：
如果将它们添加到队列中，为什么阻塞进程的激活不按 FIFO 顺序？我认为从队列中选择下一个进程比随机选择一个进程并为其授予信号量要容易。如果这个随机逻辑背后有一些想法，请解释一下。另外，内核如何从队列中随机选择一个进程？ 就队列数据结构而言，从队列中获取随机过程也是一件复杂的事情。
标签：各种操作系统，因为每个操作系统都有一个内核，通常用C++编写，并且互斥共享相似的概念
It is always said when the count of a semaphore is 0, the process requesting the semaphore are blocked and added to a wait queue.
When some process releases the semaphore, and count increases from 0->1, a blocking process is activated. This can be any process, randomly picked from the blocked processes.
Now my question is:
If they are added to a queue, why is the activation of blocking processes NOT in FIFO order? I think it would be easy to pick next process from the queue rather than picking up a process at random and granting it the semaphore. If there is some idea behind this random logic, please explain. Also, how does the kernel select a process at random from queue? getting a random process that too from queue is something complex as far as a queue data structure is concerned.
tags: various OSes as each have a kernel usually written in C++ and mutex shares similar concept
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
FIFO 是系统中等待列表的最简单的数据结构
这不支持优先级，但这不是绝对的答案
否则。根据选择的调度算法不同，
线程可能有不同的绝对优先级，或者某种
优先级衰减可能会生效，在这种情况下，操作系统可能会选择
在之前的某个时间间隔内拥有最少 CPU 时间的线程。
由于此类策略被广泛使用（尤其是后者），
通常的规则是认为你不知道（尽管绝对
优先级，它将是具有最高优先级的线程之一）。
A FIFO is the simplest data structure for the waiting list in a system
that doesn't support priorities, but it's not the absolute answer
otherwise. Depending on the scheduling algorithm chosen, different
threads might have different absolute priorities, or some sort of
decaying priority might be in effect, in which case, the OS might choose
the thread which has had the least CPU time in some preceding interval.
Since such strategies are widely used (particularly the latter), the
usual rule is to consider that you don't know (although with absolute
priorities, it will be one of the threads with the highest priority).
当“随机”调度一个进程时，并不是随机选择一个进程；而是“随机”地调度一个进程。而是选择过程是不可预测的。
Windows 内核使用的算法是有一个线程队列（Windows 调度“线程”，而不是“进程”）等待信号量。当信号量被释放时，内核调度队列中等待的下一个线程。然而，调度线程并不立即使该线程开始执行；它只是通过将线程放入等待运行的线程队列中来使线程能够执行。直到 CPU 没有更高优先级的线程可以执行时，该线程才会真正运行。
当线程在调度队列中等待时，实际正在执行的另一个线程可能会等待同一个信号量。在传统的队列系统中，新线程必须停止执行并转到队列末尾排队等待该信号量。
然而，在最近的 Windows 内核中，新线程不必停止并等待该信号量。如果已分配该信号量的线程仍然位于运行队列中，则该信号量可能会被重新分配给旧线程，导致旧线程再次返回等待信号量。
这样做的好处是，原本要在队列中等待信号量然后在队列中等待运行的线程将根本不用等待。缺点是您无法预测哪个线程将真正获得下一个信号量，并且这是不公平的，因此等待信号量的线程可能会饿死。
When a process is scheduled "at random", it's not that a process is randomly chosen; it's that the selection process is not predictable.
The algorithm used by Windows kernels is that there is a queue of threads (Windows schedules "threads", not "processes") waiting on a semaphore. When the semaphore is released, the kernel schedules the next thread waiting in the queue. However, scheduling the thread does not immediately make that thread start executing; it merely makes the thread able to execute by putting it in the queue of threads waiting to run. The thread will not actually run until a CPU has no threads of higher priority to execute.
While the thread is waiting in the scheduling queue, another thread that is actually executing may wait on the same semaphore. In a traditional queue system, that new thread would have to stop executing and go to the end of the queue waiting in line for that semaphore.
In recent Windows kernels, however, the new thread does not have to stop and wait for that semaphore. If the thread that has been assigned that semaphore is still sitting in the run queue, the semaphore may be reassigned to the old thread, causing the old thread to go back to waiting on the semaphore again.
The advantage of this is that the thread that was about to have to wait in the queue for the semaphore and then wait in the queue to run will not have to wait at all. The disadvantage is that you cannot predict which thread will actually get the semaphore next, and it's not fair so the thread waiting on the semaphore could potentially starve.
并不是说它不能是先进先出（FIFO）；而是说它不能是先进先出（FIFO）。事实上，我敢打赌许多实现都是如此，正如您所说的原因。规范并不是随机选择过程；而是随机选择过程。这是因为它没有被指定，所以你的程序不应该依赖于以任何特定方式选择它。 （它可以随机选择；仅仅因为它不是最快的方法并不意味着它不能完成。）
It is not that it CAN'T be FIFO; in fact, I'd bet many implementations ARE, for just the reasons that you state. The spec isn't that the process is chosen at random; it is that it isn't specified, so your program shouldn't rely on it being chosen in any particular way. (It COULD be chosen at random; just because it isn't the fastest approach doesn't mean it can't be done.)
这里的所有其他答案都很好地描述了基本问题 - 特别是围绕线程优先级和就绪队列。然而，另一个需要考虑的事情是 IO。我在这里只讨论 Windows，因为它是我所知道的唯一具有任何权威的平台，但其他内核可能也有类似的问题。
在 Windows 上，当 IO 完成时，称为内核模式 APC（异步过程调用）的东西会针对启动 IO 的线程排队以完成它。如果线程碰巧正在等待调度程序对象（例如示例中的信号量），则该线程将从该对象的等待队列中删除，这会导致（内部内核模式）等待完成并出现（类似）STATUS_ALERTED。现在，由于这些内核模式 APC 是一个实现细节，并且您无法从用户模式看到它们，因此 WaitForMultipleObjects 的内核实现会在此时重新启动等待，这会导致您的线程被推到队列的后面。从内核模式的角度来看，队列仍然按照 FIFO 顺序，因为底层等待 API 的第一个调用者仍然位于队列的头部，但是从您的角度来看，在用户模式下，您只是被推到了由于您没有看到并且很可能无法控制的事情而排在队列后面。这使得队列顺序在用户模式下显得随机。其实现仍然是一个简单的 FIFO，但由于 IO，它看起来不像是更高抽象级别的 FIFO。
我在这里猜测更多，但我认为类 UNIX 操作系统在信号传递和内核需要劫持进程以在其上下文中运行的位置方面具有类似的限制。
现在这种情况并不总是发生，但文档必须保守，除非明确保证顺序是 FIFO（如上所述 - 至少对于 Windows - 不可能），然后文档中描述了顺序被称为“随机”或“无证”或其他东西，因为随机过程控制它。它还为操作系统供应商提供了稍后更改顺序的自由。
All of the other answers here are great descriptions of the basic problem - especially around thread priorities and ready queues. Another thing to consider however is IO. I'm only talking about Windows here, since it is the only platform I know with any authority, but other kernels are likely to have similar issues.
On Windows, when an IO completes, something called a kernel-mode APC (Asynchronous Procedure Call) is queued against the thread which initiated the IO in order to complete it. If the thread happens to be waiting on a scheduler object (such as the semaphore in your example) then the thread is removed from the wait queue for that object which causes the (internal kernel mode) wait to complete with (something like) STATUS_ALERTED. Now, since these kernel-mode APCs are an implementation detail, and you can't see them from user mode, the kernel implementation of WaitForMultipleObjects restarts the wait at that point which causes your thread to get pushed to the back of the queue. From a kernel mode perspective, the queue is still in FIFO order, since the first caller of the underlying wait API is still at the head of the queue, however from your point of view, way up in user mode, you just got pushed to the back of the queue due to something you didn't see and quite possibly had no control over. This makes the queue order appear random from user mode. The implementation is still a simple FIFO, but because of IO it doesn't look like one from a higher level of abstraction.
I'm guessing a bit more here, but I would have thought that unix-like OSes have similar constraints around signal delivery and places where the kernel needs to hijack a process to run in its context.
Now this doesn't always happen, but the documentation has to be conservative and unless the order is explicitly guaranteed to be FIFO (which as described above - for windows at least - it can't be) then the ordering is described in the documentation as being "random" or "undocumented" or something because a random process controls it. It also gives the OS vendors lattitude to change the ordering at some later time.
进程调度算法对于系统功能和操作系统设计来说是非常具体的。这个问题很难给出一个好的答案。如果我使用的是普通 PC，我想要具有良好吞吐量和平均等待/响应时间的东西。如果我所在的系统知道所有作业的优先级，并且知道我绝对希望所有高优先级作业首先运行（并且不关心抢占/饥饿），那么我需要一个优先级算法。
就随机选择而言，动机可能有多种原因。如上所述，其中之一是尝试获得良好的吞吐量等。然而，它是不确定的（假设性的）并且无法证明。这个属性可能是对概率的利用（随机样本等），但是，同样，证明只能基于关于这是否真的有效的经验数据。
Process scheduling algorithms are very specific to system functionality and operating system design. It will be hard to give a good answer to this question. If I am on a general PC, I want something with good throughput and average wait/response time. If I am on a system where I know the priority of all my jobs and know I absolutely want all my high priority jobs to run first (and don't care about preemption/starvation), then I want a Priority algorithm.
As far as a random selection goes, the motivation could be for various reasons. One being an attempt at good throughput, etc. as mentioned above above. However, it would be non-deterministic (hypothetically) and impossible to prove. This property could be an exploitation of probability (random samples, etc.), but, again, the proofs could only be based on empirical data on whether this would really work.