信号量、PV操作及软考高级试题解析

信号量

在并发系统中，信号量是用于控制公共资源访问权限的变量。信号量用于解决临界区问题，使得多任务环境下，进程能同步运行。此概念是由荷兰计算机科学家Dijkstra在1962年左右提出的。信号量仅仅跟踪还剩多少资源可用，不会跟踪哪些资源是可用的。

信号量机制，处理进程同步和互斥的问题。信号量的一大特征就是它的值不能通过PV操作以外的方式更改，只能被两个标准的原语wait(s)和signal(s)访问，也可记为P(s)和V(s)。信号量数值为负时，表明有进程在等资源。

信号量提供一种很方便的方法来确保对共享变量的互斥访问。基本思想是将每个共享变量与一个信号量s（初值为1）联系起来，然后用P(s)和V(s)操作将相应的临界区包围起来。以这种方式来保护共享变量的信号量叫做二元信号量，因为它的值总是0和1。一个被用作一组可用资源的计数器的信号量被称为计数信号量。

PV操作

计数信号量（Counting Semaphores）通常有两种操作，记做P和V，P操作减少信号量S，V操作增加信号量S：

P操作：P(s)，wait，申请资源，信号量数值减一并且立即返回，S -= 1。S>=0，此进程执行；S<0，此进程置为阻塞（等待、挂起）状态直到s变为非0，将其插入阻塞队列。进入临界区时执行P操作
V操作：V(s)，signal，释放资源，信号量数值加一，S += 1。S>0，此进程继续执行；S<=0，从阻塞队列唤醒一个，并插入就绪队列。退出临界区时执行V操作

在这里插入图片描述
P、V都来源自荷兰语，V通常解释为verhogen、increase。P则有多种解释：proberen、to test、to try、passeren、pass、pakken、grab。

在Dijkstra最早的论文中，P表示passering（passing），V表示vrijgave（release）。

应用场景：

生产者-消费者问题
哲学家就餐问题

实战

信号量

假设系统中有n个进程共享3台打印机，任一进程在任一时刻最多只能使用1台打印机。若用PV操作控制n个进程使用打印机，则相应信号量S的取值范围为（）；若信号量S的值为-3，则系统中有（）个进程等待使用打印机。

解析：
假设系统中有n个进程共享3台打印机，意味着每次只允许3个进程进入互斥段，则信号量的初值应为3，最小值为-(n-3)，因此取值范围：3, 2, 1, 0, -1, ..., -(n-3)。

信号量S的值为-3，则系统中有3个进程等待使用打印机。

信号量S的物理意义为：当S>0时，表示资源可用数；当S<0时，其绝对值表示等待资源的进程数。

PV操作

进程P1、P2、P3、P4和P5的前趋图如下：
在这里插入图片描述
若用PV操作控制进程P1〜P5并发执行的过程，则需要设置5个信号S1、S2、S3、S4和S5，进程间同步所使用的信号量标注在上图中的边上，且信号量S1〜S5的初值都等于零，初始状态下进程P1开始执行。下图中a、b和c处应分别填写（），d和e处应分别填写（），f和g处应分别填写（）。
在这里插入图片描述
解析：

因为P1是P2和P3的前驱，当P1执行完应通知P2和P3，应采用V(S1)V(S2)操作分别通知P2和P3，故a处应填写V(S1)V(S2)；
因为P2是P1的后继，当P2执行前应测试P1是否执行完，应采用P(S1)操作测试P1是否执行完，故b处应填写P(S1)；
P2是P4和P5的前驱，当P2执行完应通知P4和P5，应使用V(S3)V(S4)操作分别通知P4和P5，故c处应填写V(S3)V(S4)；
P3是P1的后继，当P3执行前应测试P1是否执行完，应采用P(S2)操作测试P1是否执行完，故d应填写P(S2)；
P3是P5的前驱，当P3执行完应通知P5，应采用V(S5)操作通知P5，故e处应填写V(S5)
P4是P2的后继，当P4执行前应测试P2是否执行完，应采用P(S3)操作分别测试P2是否执行完，故f处应填写P(S3)；
P5是P2和P3的前驱，当P5执行前应测试P2和P3是否执行完，应采用P(S4)P(S5)操作分别测试P2和P3是否执行完，故g处应填写P(S4)P(S5)。

投机取巧：
如果实在是不懂不会不明白，则记住：
上面的填P，下面的填V。

机票

某航空公司机票销售系统有n个售票点，该系统为每个售票点创建一个进程 $P_i(i=1,2,…,n)$ 管理机票销售。假设 $T_j(j=1,2,…,m)$ 单元存放某日某航班的机票剩余票数，Temp为 $P_i$ 进程的临时工作单元，x为某用户的订票张数。初始化时系统应将信号量S赋值为（）。 $P_i$ 进程的工作流程如下图所示，若用P操作和V操作实现进程间的同步与互斥，则图中空（a），（b），（c）处应分别填入（）。
在这里插入图片描述
解析：
公共数据单元是一个临界资源，最多允许1个终端进程使用，因此需要设置一个互斥信号量S，初值等于1。