信号量排队

Question

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

我知道信号量通过阻塞正在等待它的线程来调用sem_wait()而另一个线程当前已将其锁定.然后阻塞该线程,然后将其放入该信号量的等待列表中.

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

谢谢!

Answer 1

要解除阻塞的下一个线程sem_wait()将是操作系统决定的下一个上下文切换到的线程.没人保证订购; 这取决于您的操作系统的调度策略.它可能是已经脱离CPU最长的线程,或者已经分配了最高"优先级"的线程,或者历史上具有某些资源使用统计信息的线程,或者其他什么.

最有可能的是,您当前的线程(被调用的线程sem_post())将继续运行一段时间,直到它开始等待用户输入,阻塞另一个信号量,或者耗尽其os分配的时间片.然后,操作系统将切换一些完全不相关的进程运行几分之一秒(可能是Firefox或其他东西),然后关闭并处理一些网络流量,让自己喝杯茶,最后,当它到处走动时对它来说,选择你感觉到的其他线程,基于过去的历史是否感觉特定线程更多CPU或I/O限制.

在许多操作系统中,优先考虑I/O绑定的进程,这些进程已经存在很长时间.理论上说,新的过程可能是短暂的(如果它已经存在了五个小时,很可能在接下来的1ms内不会完成),所以我们不妨将它们结束.I/O绑定进程可能继续受I/O限制,这意味着他们很可能在等待其他资源时很快关闭CPU.基本上,操作系统希望找到能够尽快完成的过程,因此它可以回过头来喝茶并运行恶意软件.

Answer 2

信号量有两个操作:

1. P()获取信号量(你似乎称之为sem_wait)
2. V()释放信号量(你似乎称之为sem_post)

信号量还有一个与之关联的整数,这是允许传递P()而不阻塞的并发线程数.对P()的其他调用将阻塞,直到调用V()来释放点.

这是信号量的经典定义.

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