2.2.5 信号量机制
在解决并发进程的同步和互斥问题的过程中,人们经过了许多尝试和探讨,在总结这些探讨的基础上,1965年荷兰学者Dijkstra提出了信号量(Semaphores)机制,该机制可以很容易地被用户进程使用,是现代操作系统在进程之间实现互斥与同步的基本工具。它的基本原理是:两个或多个进程可以通过简单的信号进行合作,一个进程可以被迫在某一位置停止,直到它接收到一个特定的信号。任何复杂的合作需求都可以通过适当的信号结构得到满足,目前使用的是一种特殊的数据结构——信号量。
信号量是一个数据结构,它由一个信号量变量以及对该变量进行的原语操作组成,操作系统利用信号量实现进程同步与互斥的机制称为信号量机制。根据数据结构中定义的变量类型的不同,信号量也有不同的类型,这里主要讲整型信号量和记录型信号量。
1.整型信号量机制
整型信号量机制中的数据结构——整型信号量由1个整型变量和3个操作组成,3个操作如下。
①初始化操作:可以将信号量变量初始化为非负整数。
②原语操作P(P操作):判断信号量值,如果为0,忙等待(判断-空操作),否则将信号量值减1。
③原语操作V(V操作):将信号量值加1。
P、V操作的算法描述如下。
P、V操作都是原语操作,因此在运行过程中不能被中断。使用P、V操作作为进入临界区的入口控制代码和出口控制代码,可以有效实现临界资源的互斥使用。
【例2-3】两个进程P1、P2,共享临界资源CR,同类临界区为CS1、CS2。使用P、V操作作为CS1、CS2的入口和出口控制代码,二者共享信号量mutex,进程算法如图2-16所示。
图2-16 使用整型信号量控制互斥
分析两个进程的一种极端推进顺序,如图2-17所示。
图2-17 两个临界区的一种推进顺序
两个进程进入临界区前都要执行P操作,先执行P操作的进程将信号量减1,进入临界区;后执行P操作的进程判断信号量时已经为0,只能不断检查信号量值,在P操作中忙等待,直到进入临界区的进程,访问临界资源结束,退出临界区时,执行V操作,将信号量值加1,等待的进程此时判断信号量值为1,将其减1,进入临界区;如果有多个进程想要进入临界区,都会在P操作中忙等待。
2.记录型信号量机制
整型信号量机制成功地控制了进程对临界资源的互斥访问,但是当进程在P操作中等待的过程中,虽然进程没有实质上的运行进展,但是却在执行语句while,这个语句每次也需要占用处理机,这就浪费了宝贵的处理机资源,因此产生了记录型信号量机制。
在记录型信号量机制的数据结构中,除了一个整数变量外,还加了一个指针队列,用以记录等待进程,变量组成如下。
记录型信号量的操作仍然为3个。
①初始化:将记录型信号量结构变量中的整型变量初始化为非负整数。
②原语操作Wait:Wait操作带有参数S,即记录型信号量变量。原语首先将整型值value减1,之后判断value值是否小于0,如果小于0,调用block原语,将自己阻塞。Wait操作算法描述如下。
其中:block是操作系统进程控制机制的阻塞原语,block(S,L)是将调用此原语的进程挂在(阻塞在)L队列中,等待资源为S的信号量。
③原语操作Signal:Signal操作带有参数S,即记录型信号量变量。原语首先将整型值value加1,之后判断value值是否小于等于0,如果小于等于0,调用wakeup原语,将因等待S信号量而挂在(阻塞在)L队列上的进程唤醒。Signal操作算法描述如下。
其中:wakeup是操作系统进程控制机制的唤醒原语,wakeup(S,L)将因等待S信号量的、挂在(阻塞在)L队列中的进程唤醒。
类似之前P、V操作的作用,现在仍然可以用Wait、Signal操作作为临界区的入口、出口控制码,此时,先执行Wait操作的进程仍然将信号量值减1,直接进入临界区,只是其后执行Wait操作的进程,将信号量值减1后,发现无法进入临界区,则调用阻塞原语将自己阻塞,并将自己挂在等待该临界资源的队列L中,等待唤醒。谁来唤醒它呢?就是从临界区出来的进程,执行Signal操作,当发现S.value值小于等于0时,说明有进程等待该临界资源,则调用wakeup原语从队列中唤醒阻塞进程。
例2-3的两个进程的一种极端推进顺序,如图2-18所示。
图2-18 例2-3运行顺序示例
从图2-18中可以看出,等待的进程被阻塞,不再参与资源分配。
本书后续使用的信号量机制都是记录型信号量机制,不再特意说明。
3.利用信号量实现进程互斥
有了信号量机制,用户可以方便地解决进程的互斥和同步问题。
使用信号量互斥访问临界资源,需要设置一个互斥信号量,其初值必须为1,然后以Wait操作作为临界区入口控制码,Signal操作作为临界区出口控制码,如图2-19所示。
图2-19 使用记录型信号量控制互斥
4.利用信号量实现进程同步
信号量机制也可以用来解决同步问题。
【例2-4】假设有4个程序协作完成一项任务,它们的运行逻辑关系如图2-20所示。4个程序可以并发执行,同时申请系统资源。为了确保进程间的同步,在存在直接关系的进程间各设一个同步信号量,如图2-20所示。
图2-20 例2-4进程逻辑顺序及信号量设置
信号量m1-2控制进程S1和S2之间的同步;信号量m1-3控制进程S1和S3之间的同步;信号量m2-4控制进程S2和S4之间的同步;信号量m3-4控制进程S3和S4之间的同步。注意,这4个同步信号量初值设为0。
4个进程的同步形式如图2-21所示。
图2-21 信号量机制解决同步问题
4个进程执行过程如下。
①如果S1先得到处理机,它可以运行,因为它是执行逻辑的第1个进程;但是运行结束后要通知等待它运行结果的S2和S3,这种通知靠对进程间的信号量的Signal操作完成。
②如果S2先得到处理机,它要等待S1的运行结果,因此,它要先执行Wait(m1-2)操作,如果S1没有执行完毕,S2进程将自己阻塞,等待S1的Signal操作唤醒;并且S2操作执行完毕,要通知等待它的S4进程,执行Signal(m2-4),唤醒S4。
③S3与S2运行过程相同,不再赘述。
④进程S4运行需要S2和S3两个进程的运算结果,因此进程的入口执行Wait(m2-4)和Wait(m3-4),分别等待两个进程的唤醒;S4作为整项任务的结束,不需要唤醒其他进程,因此不再有出口码。
值得注意的是,若Wait操作和Signal操作使用不当,仍然会出现与时间有关的错误。当使用多个Wait操作时,一定要注意它们的使用顺序,这个在下一小节会详细介绍。
在长期且广泛的应用中,信号量机制得到了很大发展,它从整型信号量经记录型信号量,进而发展为“信号量集”机制,已被广泛用于单处理机和多处理机以及计算机网络环境的进程通信中。