pv原语例题

PV原语稍微详细点的表⽰⽅法

PV原语的边界条件写的太精简，所以我稍微详细点的表⽰。

PV原语

P原语：P是荷兰语Proberen（测试）的⾸字母。为阻塞原语，负责把当前进程由运⾏状态转换为阻塞状态，直到另⼀个进程唤醒它。具体操作为：申请⼀个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞。V原语：V是荷兰语Verhogen（增加）的⾸字母。为唤醒原语，负责把⼀个被阻塞的进程唤醒，他有⼀个参数表，存放着等待被唤醒的进程信息。具体操作为：释放⼀个被占⽤的资源（把信号量加1），如果发现有被阻塞的进程，则选择⼀个唤醒。

表⽰⽅法P(S)：表⽰将信号量S的值减⼀，即S=S-1；如果S>=0，则该进程继续执⾏，否则该进程置为等待状态，排⼊等待队列（队列Q）。

V(S)：表⽰将信号量S的值加⼀，即S=S+1；如果S>0，则该进程继续执⾏，否则释放队列（Q）中第⼀个等待信号量的进程。

我的稍微详细点表⽰⽅法P(S)：表⽰将信号量S的值减⼀，即S1= S; S2=S1-1；如果S2>=0，也就是S1>=1,说明有现成的资源直接可以⽤，不⽤等！，则该进程继续执⾏，否则（也就是S2<0变成负数）该进程置为等待状态，排⼊等待队列（队列Q）。V(S)：表⽰将信号量S的值加⼀，即S1=S; S2=S1+1；如果S2>0，也就是S1>-1也就是S1>=0，也就是说明V操作之前S1不是负数，说明根本不存在等待资源的进程，等待队列是空的！，则该进程继续执⾏，否则（也就是V操作之后释放了⼀个资源，⼜有⾄少⼀个正在等待资源的进程，那就去唤醒这个进程）释放队列（Q）中第⼀个等待信号量的进程。

进程的互斥和同步

进程同步：主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。如：相互合作的两个进程之间需要在某些确定点协调它们的工作，一个进程到达了该点后，除非另一进程已经完成了某些操作，否则就不得不停下来，等待这些操作的完成。这就是进程间的同步。

进程互斥：主要源于资源共享，是进程之间的间接制约关系。在多道系统中，两个进程由于不能同时使用同一临界资源，只能在一个进程使用完了，另一进程才能使用，这种现象称为进程间的互斥。

同步的主要特征是：一个进程在某一点上等待另一进程提供信息，两进程之间存在直接制约关系，其表现形式为进程—进程。

互斥的主要特征是争用资源，两进程间存在间接制约关系，其表现形式是进程—资源—进程

设备同步：概括来讲，就是有两个数据源，最初它们的数据都是一样的。若一个数据源的数据经过添加、修改、删除等操作发生了改变，那么为了使两个数据源的数据保持一致，即让一个数据源数据的改变反映到另一个上，就必须进行一个让两个数据源的数据保持一致的操作，这个操作就叫“同步”。同步操作结束之后，两个设备上的数据就完全一致了，处于“同步”状态。

进程同步是进程之间直接的相互作用，是合作进程间有意识的行为。典型的例子是公共汽车上司机与售票员的合作。

只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。

信号量是最早出现的用来解决进程同步与互斥问题的机制， 包括一个称为信号量的变量及对它进行的两个原语操作。

每个信号量至少须记录两个信息：信号量的值和等待该信号量的进程队列。

对一个信号量变量可以进行两种原语操作：p操作和v操作。

p操作和v操作是不可中断的程序段，称为原语。如果将信号量看作共享变量，则pv操作为其临界区，多个进程不能同时执行。 由此也可以看到，信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点。 一个信号量只能置一次初值，以后只能对之进行p操作或v操作。 其基本思路是用信号量（semaphore）来记录当前可用资源的数量。信号量sem是一整数，sem大于等于零时代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。

PV操作的例题

一、线程是进程的一个组成部分，一个进程可以有多个线程，而且至少有一个可执行线程。进程的多个线程都在进程的地址空间内活动。

资源是分给进程的，而不是分给线程的，线程需要资源时，系统从进程的资源配额中扣除并分配给它。处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。线程在执行过程中，需要同步。

二、在计算机操作系统中，PV操作是进程管理中的难点。

首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

P（S）：①将信号量S的值减1，即S=S-1；

②如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；

②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。

一般来说，信号量S>=0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S?0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

利用信号量和PV操作实现进程互斥的一般模型是：

进程P1 进程P2 …… 进程Pn

例 某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。

 ①所用信号量设置如下：

 Ⅰ）互斥信号量S，初值为50，用以保证最多可以有50个购物者同时进入超市。

 Ⅱ）互斥信号量mutex1、 mutex2，初值为1，用以保证同时只能有一个购物者进程进入出、入口拿起篮子或者结帐后放下篮子。

 ②用信号量机制给出的每个购物者购物过程的算法描述如下：

购物者进程：

 P（S）；

 P（mutex1）；

 从入口处进超市，并取一只篮子；

 V（mutex1）；

 进超市内选购商品；

 P（mutex2）；

 到出口结帐，并归还篮子；

 V（mutex2）；

 从出口离开超市；

 V（S）

例 桌上有个只能盛得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和P、V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。

Ⅰ）爸爸进程的同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。

Ⅱ）儿子进程的同步信号量orange，初值为0，表示爸爸尚未把桔子放入盘中。

Ⅲ）女儿进程的同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。

 爸爸进程（P）： 儿子进程（C1）： 女儿进程（C2）：

 P（empty）； P（orange ）； P（apple）；

 将水果放入盘中； 从盘中取出桔子； 从盘中取出苹果；

 若放入的是桔子， V（empty）； V（empty）；

 则V（orange）； 吃桔子； 吃苹果；