信号量(编程)

2020-11-03 13:55:59

跳转到导航跳转在计算机科学中，信号量是一种变量或抽象数据类型，用于控制并发系统(如多任务操作系统)中的多个进程对公共资源的访问。信号量只是一个变量。此变量用于解决多处理环境中的临界区问题和实现进程同步。普通信号量是一个普通变量，可以根据程序员定义的条件进行更改(例如，递增、递减或切换)。

将信号量视为在真实世界系统中使用的一种有用的方式是将特定资源的多少个单元可用的记录与在单元被获取或变为空闲时安全地调整该记录(即，避免竞争条件)的操作相结合，并且如果需要，则等待直到资源的单元变为可用。

信号量是防止争用条件的有用工具；但是，使用信号量并不能保证程序不会出现这些问题。允许任意资源计数的信号量称为计数信号量，而限制为值0和1(或锁定/解锁、不可用/可用)的信号量称为二进制信号量，用于实现锁定。

信号量的概念是由荷兰计算机科学家Edsger Dijkstra在1962年或1963年发明的，当时Dijkstra和他的团队正在为Electrlogica X8开发操作系统。该系统最终被称为多道程序设计系统。

假设一个图书馆有10个相同的自习室，每次供一个学生使用。如果学生想使用自习室，他们必须向前台申请房间。如果没有空余的房间，学生们在桌子旁等待，直到有人让出房间。当学生使用完一个房间后，他必须回到课桌前，并指出有一个房间是空闲的。

在最简单的实现中，前台的办事员只知道可用的空房数量，只有当所有学生在签约时确实使用了他们的房间，并在他们使用完毕后归还房间时，他们才能正确地知道这一点。当学生要求房间时，办事员会减少这个数字。当学生腾出房间时，办事员会增加这个数字。房间可以用多久就用多久，所以不可能提前订房。

在此场景中，前台计数持有者代表计数信号量，房间是资源，学生代表进程/线程。在这个场景中，信号量的值最初是10，所有房间都是空的。当一名学生请求房间时，他们将被授予访问权限，信号量的值被更改为9。在下一名学生到来后，信号量将降至8，然后是7，依此类推。如果有人请求房间，并且信号量的当前值为0，[3]他们将被迫等待，直到房间被释放(当计数从0增加时)。如果其中一个房间被腾出，但有几个学生在等待，那么可以使用任何方法来选择将占用该房间的人(如FIFO或抛硬币)。当然，学生只有在真正离开房间后才需要通知工作人员释放他们的房间，否则，当学生在离开房间的过程中(他们正在收拾课本等)时，可能会出现尴尬的情况。另一个学生在他们离开之前进入了房间。

当用于控制对资源池的访问时，信号量只跟踪有多少资源是空闲的；它不会跟踪哪些资源是空闲的。可能需要一些其他机制(可能涉及更多信号量)来选择特定的空闲资源。

该范例特别强大，因为信号量计数可以用作许多不同操作的有用触发器。上面的图书管理员可以在没有学生的时候关掉自习室的灯，或者在大部分房间都被占满的时候放一个牌子，说明房间很忙。

该协议的成功需要应用程序正确遵循它。公平和安全很可能会受到损害(这实际上意味着程序可能运行缓慢、不稳定、挂起或崩溃)，即使只有一个进程运行不正确。这包括：

即使所有进程都遵循这些规则，当存在由不同信号量管理的不同资源时，以及当进程需要一次使用多个资源时，仍可能发生多资源死锁，如进餐哲学家问题所示。

计数信号量配备了两个操作，历史上分别表示为P和V(有关替代名称，请参阅§“操作名称”)。运算V递增信号量S，运算P递减它。

信号量S的值是当前可用的资源单位数。P操作浪费时间或休眠，直到受信号量保护的资源变为可用，此时该资源被立即认领。V操作与之相反：它使资源在进程使用完毕后再次可用。信号量S的一个重要属性是，除了使用V和P操作外，它的值不能更改。

WAIT：将信号量变量的值减1。如果信号量变量的新值为负，则阻塞执行WAIT的进程(即，添加到信号量的队列中)。否则，进程在使用了一个资源单元后继续执行。

Signal：将信号量变量的值递增1。递增后，如果预增量值为负(表示有进程在等待资源)，它会将阻塞的进程从信号量的等待队列转移到就绪队列。

许多操作系统提供当信号量递增时解锁等待进程的有效信号量原语。这意味着进程不会不必要地浪费时间检查信号量的值。

可以扩展计数信号量的概念，使其能够从信号量中声明或返回一个以上的单元，这是Unix中实现的一项技术。修改后的V和P操作如下，使用方括号表示原子操作，即从其他进程的角度看是不可分割的操作：

函数V(信号量S，整数I)：[s←S+I]函数P(信号量S，整数I)：重复：[If S≥I：s←S−I Break]。

但是，除非另有说明，否则本节的其余部分指的是具有一元V和P运算的信号量。

为了避免饥饿，信号量有一个关联的进程队列(通常使用FIFO语义)。如果进程对值为零的信号量执行P操作，则该进程将被添加到信号量的队列中，并挂起其执行。当另一个进程通过执行V操作来递增信号量时，如果队列中有进程，则从队列中删除其中一个进程并恢复执行。当进程具有不同的优先级时，可以按优先级对队列进行排序，从而首先从队列中取出最高优先级的进程。

如果实现不能确保递增、递减和比较操作的原子性，则存在忘记递增或递减或信号量值变为负值的风险。原子性可以通过使用能够在单个操作中读取、修改和写入信号量的机器指令来实现。在没有这样的硬件指令的情况下，可以通过使用软件互斥算法来合成原子操作。在单处理器系统上，可以通过暂时挂起抢占或禁用硬件中断来确保原子操作。这种方法在多处理器系统上不起作用，在多处理器系统中，共享一个信号量的两个程序可能同时在不同的处理器上运行。要在多处理器系统中解决此问题，可以使用锁定变量来控制对信号量的访问。使用test-and-set-lock命令操作锁定变量。

考虑变量A和布尔变量S。只有当S标记为真时，才能访问A。因此，S是A的信号量。

可以想象，就在火车站(A)前面有一个红绿灯信号(S)。在这种情况下，如果信号是绿色的，那么就可以进入火车站。如果是黄色或红色(或任何其他颜色)，则不能进入火车站。

假设一个系统只能支持10个用户(S=10)。每当用户登录时，将调用P，将信号量S减去1。每当用户注销时，将调用V，将S递增1，表示已变为可用的登录槽。当S为0时，任何希望登录的用户都必须等到S>；0并且登录请求排入FIFO队列；互斥用于确保请求按顺序排队。只要S大于0(可用的登录槽)，登录请求就会出列，并且允许拥有该请求的用户登录。

在生产者-消费者问题中，一个进程(生产者)生成数据项，另一个进程(消费者)接收并使用它们。它们使用最大大小为N的队列进行通信，并受以下条件的限制：

如果队列是空的，消费者必须等待生产者生产产品；

如果队列已满，生产者必须等待消费者消费一些东西。

生产者-消费者问题的信号量解决方案使用两个信号量跟踪队列的状态：emptyCount(队列中的空位数)和fullCount(队列中的元素数)。为了保持完整性，emptyCount可能低于队列中的实际空位数(但从不高于)，fullCount可能低于(但从不高于)队列中的实际项目数。空位置和项代表两种资源，空箱和满箱，信号量emptyCount和fullCount维护对这些资源的控制。

二进制信号量useQueue确保队列本身的状态完整性不会受到损害，例如，两个生产者试图同时将项添加到空队列，从而破坏其内部状态。或者，可以使用互斥锁来代替二进制信号量。

几位制片人进入制片人临界区。由于EmptyCount限制其进入临界区，不能超过N个生产者进入其临界区。

生产者，一次一个，通过useQueue获得对队列的访问，并将项目存放在队列中。

一旦第一个生产者退出其临界区，fullCount就会递增，从而允许一个使用者进入其临界区。

请注意，EmptyCount可能比队列中的实际空位数低得多，例如，在许多生产者已将其递减但在填充空位之前等待轮到useQueue的情况下。请注意，当且仅当没有生产者或消费者执行其临界区时，EmptyCount+FullCount≤N始终保持相等。

规范名称V和P来自荷兰语单词的首字母。V通常解释为马鞭草("；增加"；)。已经为P提供了几种解释，包括proberen("；测试"；或"；尝试"；)、[4]passeren("；pass"；)和pakken("；Grab&34；)。Dijkstra关于这一主题的最早的论文[2]给出了Passering(通过)作为P的含义，vrijget(释放)作为V的含义。它还提到这个术语取自铁路信号中使用的术语。Dijkstra随后写道，他打算用P来代表合成词Promanteau Prolaag，[5]是ProBeer te verlagen的缩写，字面意思是尽量减少，或者平行于另一种情况下使用的术语，尽量减少。[6][7][8]。

在Linux内核ALGOL 68中，[9]和一些英语教科书中，V和P运算分别称为向上和向下。在软件工程实践中，它们通常称为Signal and Wait、[10]Release和Acquisition[10](标准Java库[11]使用)，或者POST和Pend。有些文本[12][13]称它们为“腾空”和“追求”，以便与荷兰语原文的首字母相匹配。

互斥是一种锁定机制，有时使用与二进制信号量相同的基本实现。它们之间的不同之处在于它们的使用方式。虽然二进制信号量可能俗称为互斥锁，但真正的互斥锁有更具体的用例和定义，因为只有锁定互斥锁的任务才能解锁它。此约束旨在处理使用信号量的一些潜在问题：

优先级反转：如果互斥体知道是谁锁定了它，并且应该解锁它，那么每当更高优先级的任务开始等待互斥体时，就有可能提升该任务的优先级。

任务过早终止：Mutexes还可以提供删除安全性，其中保存互斥锁的任务不会被意外删除。[需要引用]。

终止死锁：如果持有互斥锁的任务因任何原因终止，操作系统可以释放该条件下的互斥锁和信号等待任务。

递归死锁：允许任务在解锁可重入互斥锁相同次数时多次锁定该互斥锁。

意外释放：如果释放任务不是其所有者，则在释放互斥锁时引发错误。

书名/作者Dejkstra，Edsger W.Over Seinpalen(EWD-74)(PDF)。E.W.迪克斯特拉档案馆。德克萨斯大学奥斯汀分校美国历史中心。(抄本)。

A b Dijkstra，Edsger W.Over de Sequentialiteit van Procedesbeschrijvingen(EWD-35)(PDF)。E.W.迪克斯特拉档案馆。德克萨斯大学奥斯汀分校美国历史中心。(抄本)(未注明日期，1962年或1963年)。

书名/作者Dejkstra，Edsger W.EWD-74(PDF)。E.W.迪克斯特拉档案馆。德克萨斯大学奥斯汀分校美国历史中心。(抄本)。

^Dijkstra，Edsger W.MULTIPROGAMMERING EN DE X8(EWD-51)(PDF)。E.W.迪克斯特拉档案馆。德克萨斯大学奥斯汀分校美国历史中心。(抄本)(荷兰语)。

^Dijkstra自己的翻译是Try-and-Reduce&34；，尽管对于那些没有意识到口语中的Try-and……的人来说，这个短语可能会让人感到困惑。

^(补丁程序1/19)MUTEX：介绍简单互斥实现Linux内核邮件列表，2005年12月19日。