软考必考题型之PV操作

素颜马尾好姑娘i 2022-02-28 11:58 727阅读 0赞

#### 概念： ####

信号量 ： 信号量(Semaphore)，以下简写为S，有时被称为信号灯，是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用。

*  `当S>0时，表示当前可用资源的数量。`
 *  `当S<0时，其绝对值表示等待使用该资源的进程个数。`
 *  `注意，信号量的值仅能由PV操作来改变。`

PV操作： PV操作与信号量的处理相关，P表示通过的意思，V表示释放的意思。PV原语中P是荷兰语的Passeren，相当于英文的pass， V是荷兰语的Verhoog，相当于英文中的increment。

*      P操作可以看作是获得或者请求、消耗一个信号量。
    
     *  `将信号量S的值减1，即S=S-1；`
     *  `如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。`
 *      V操作可以看作是释放或者发送一个信号量。
    
     *  `将信号量S的值加1，即S=S+1；`
     *  `如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。`

下面来看几道例题：

1.  （2016年下半年例题）假设系统中有n个进程共享3台扫描仪，并采用PV操作实现进程同步与互斥。若系统信号量S的当前值为-1，进程P1、P2又分别执行了一次P(S)操作，那么信号量S的值应为\_\_\_。  
    ***解答：***  
    根据PV操作概念中P操作公式，S=S-1，这里发生两次P操作，那么当前S的值应该为-1减2次操作后等于-3。
2.  （2016年上半年例题) 进程P1、P2、P3、P4和P5的前趋图如下图所示：  
    ![前趋图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70]  
    若用PV操作控制进程P1、P2、P3、P4和P5的并发执行过程，则需要设置5个信号量S1、S2、S3、S4和S5，且信号量S1～S5的初值都等于零。下图中a和b处应分别填入\_\_\_;c和d处应分别填入\_\_\_;e和f处应分别填入\_\_\_。  
    ![进程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70 1]  
    ***解答：***  
    根据前趋图，P1进程执行完需要通知P2和P3进程，所以需要利用V(S1)和V(S2)操作通知P2和P3进程，所以空a应该填V(S1)和V(S2)，P2进程执行完要通知P4进程，所以空b应该填V(S3)。P3进程运行前需要等待P1进程的结果，所以执行程序前要先利用1个P操作，所以空c应该填P(S2)，而P3进程运行结束需要利用一个V操作通知P5进程，所以空d应该填V(S4)。P4进程执行结束需要利用一个V操作通知P5进程，所以空e处应该填V(S5)，P5进程执行前需要等待P3和P4进程的结果，所以空f处需要两个P操作，那应该填P(S4)和P(S5)。
3.  (2015年下半年例题) 某企业的生产流水线上有2名工人P1和P2，1名质检员P3。P1将初步加工的半成品放入半成品箱B1；P2从半成品箱B1取出继续加工，加工好的产品放入成品箱B2；P3从成品箱P2取出产品检验。假设B1可存放n件半成品，B2可存放m件产品，并设置6个信号量S1、S2、S3、S4、S5和S6，且S3和S6的初值都为0。采用PV操作实现P1、P2和P3的同步模型如下图所示，则信号量S1和S5初始值分别为\_\_\_，S2、S4的初始值分别为\_\_\_。  
    ![流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70 2]  
    ***解答：***  
    根据题意可以看出这是一道很典型的生产者消费者问题，P1为生产者，P2即是消费者又是生产者，P3为消费者，B1和B2为缓存区。  
    因为信号量S1是一个互斥信号量，表示半成品箱B1当前有无生产者使用，所以初值为1。信号量S5也是一个互斥信号量，表示成品箱B2当前有无生产者使用，所以初始值为1。  
    信号量S2表示半成品箱B1的容量，所以S2的初值为n。当生产者P1不断将半成品放入B1时，应该先测试B1是否有空位，所以生产者P1使用P(S2)，当消费者P2从B1取出一件半成品时，B1就空出一个空位，所以消费者P2使用V(S2)释放空间。  
    同理，信号量S4表示半成品箱B2当容量，所以S4的初值为m。当生产者P2完成一件产品放入B2时，应先测试B2是否有空位，所以生产者P2使用P(S4)，当消费者P3从B2取出一件产品时，B2就空出一个空位，所以消费者P3使用V(S4)释放空间。  
    程序执行图如下所示：  
    ![解析图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70 3]

先到这里，后面补充以代码示例，可以参考经典问题，如：生产者与消费者，哲学家进餐，读者与作家等等。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70]: /images/20220228/80a81e05004a4f03bff4572db474c9f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70 1]: /images/20220228/e8eb024f69c149b7bfce682410ea871b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70 2]: /images/20220228/2466c27b2c6343aaa84f1cd5277f75ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70 3]: /images/20220228/bb2dccba0fc9418f8edae642e13028b1.png