信号量队列

Question

我正在扩展信号量的功能。当我意识到我不知道实际信号量的实现时，我遇到了一个障碍，为了确保我的代码正确运行，我需要知道这一点。

我知道一个信号量的工作原理是当它们调用sem_wait()时阻塞等待它的线程，而另一个线程目前已经锁定了它。然后阻塞该线程，然后将其放入该信号量的等待列表中。

我的问题与sem_post()上发生的事情有关。是否将下一个线程从等待列表中拉出，设置为锁定线程，并允许解除阻塞？或者是发帖的方案完全不同？

谢谢!

Answer 1

Semaphores有两个操作：

获取信号量的

1. P() (您似乎调用此sem_wait)
2. V()来释放信号量(您似乎将其称为sem_post)

信号量也有一个与之相关的整数，这是允许不阻塞地通过P()的并发线程的数量。对P()的其他调用将被阻塞，直到调用V()来释放斑点。

这是信号量的经典定义。

编辑：信号量不保证顺序。它们实际上不必使用队列或其他FIFO结构。当一次只允许一个线程时，当它调用V()时，另一个(可能是随机的)线程将从它的P()调用返回并继续。

Answer 2

在它的sem_wait()上解锁的下一个线程将是操作系统决定的下一个要切换到的线程。没有人能保证排序；这取决于你的操作系统的调度策略。它可能是离开CPU时间最长的线程，也可能是分配了最高“优先级”的线程，也可能是历史上具有某些资源使用统计信息的线程，等等。

最有可能的是，当前线程(调用sem_post()的线程)将继续运行一段时间，直到它开始等待用户输入、阻塞另一个信号量或耗尽操作系统分配的时间片。然后，操作系统将切换到一些完全不相关的进程中运行一小段时间(可能是Firefox或其他什么)，然后关闭并处理一些网络流量，给自己倒一杯茶，最后，当它找到它时，根据过去的历史是否感觉到特定线程更受CPU或I/O限制，选择其他线程中感觉像的任何线程。

在许多OSes中，优先考虑存在时间不长的受I/O限制的进程。理论上说，新的进程可能是短暂的(如果它已经存在了5个小时，很可能不会在接下来的1毫秒内完成)，所以我们不妨把它们完成。受I/O限制的进程可能会继续受I/O限制，这意味着它们可能很快就会关闭CPU，同时等待其他资源。基本上，操作系统想要找到它将能够尽快完成的进程，这样它就可以重新开始品尝自己的茶并运行你的恶意软件。