操作系统 PV操作习题答案

？？？信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。

参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。

V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。

PV操作的物理含义：信号量S值的大小表示某类资源的数量。

当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。

每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。

每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。

无论以上哪种情况，执行V操作的进程都可继续运行。

1、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。

设两个信号量S和C，初值为S＝0；C＝0；司机： L1：正常行车售票员： L2：售票到站停车 P（S）V（S）开车门P（C）关车门启动开车 V（C）GO TO L1 GO TO L22、请用PV操作实现他们之间的同步关系：（1）桌上一个盘子，只能放一只水果。

爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。

（2）桌上一个盘子，只能放一只水果。

操作系统PV操作习题⼀、⽤P、V操作描述前趋关系。

P1、P2、P3、P4、P5、P6为⼀组合作进程，其前趋图如图2．3所⽰，试⽤P、V 操作描述这6个进程的同步。

p23图2．3说明任务启动后P1先执⾏，当它结束后P2、P3可以开始执⾏，P2完成后P4、P5可以开始执⾏，仅当P3、P4、P5都执⾏完后，P6才能开始执⾏。

为了确保这⼀执⾏顺序，设置5个同步信号量n、摄、f3、f4、g分别表⽰进程P1、P2、P3、P4、P5是否执⾏完成，其初值均为0。

这6个进程的同步描述如下：图2．3 描述进程执⾏先后次序的前趋图int f1=0; /*表⽰进程P1是否执⾏完成*／int f2=0; /*表⽰进程P2是否执⾏完成*／int f3=0; /*表⽰进程P3是否执⾏完成*／int f4=0; /*表⽰进程P4是否执⾏完成*／int f5=0; /*表⽰进程P5是否执⾏完成*／main() {cobeginP1( );P2( );P3( );P4( );P5( );P6( );coend}P1 ( ){┇v(f1);v(f1)：}P2 ( ){p(f1);┇v(f2);v(f2);)P3 ( ){p(f1);┇v(f3);}P4( ){p(f2);┇v(f4);}P5 ( ){p(f2);┇v(f5);}P6( ){p(f3);p(f4);p(f5);┇}⼆、⽣产者-消费者问题p25⽣产者-消费者问题是最著名的进程同步问题。

它描述了⼀组⽣产者向⼀组消费者提供产品，它们共享⼀个有界缓冲区，⽣产者向其中投放产品，消费者从中取得产品。

⽣产者-消费者问题是许多相互合作进程的⼀种抽象。

例如，在输⼊时，输⼊进程是⽣产者，计算进程是消费者;在输出时，计算进程是⽣产者，打印进程是消费者。

因此，该问题具有很⼤实⽤价值。

我们把⼀个长度为n的有界缓冲区(n>0)与⼀群⽣产者进程P１、P２、…、Pm和⼀群消费者进程C１、C２、…、Ck 联系起来，如图2．4所⽰。

关于调度算法【例1】下表给出作业l，2，3的提交时间和运行时间。

采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。

）分析解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。

我们用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。

采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。

然后按照“排队买票”的办法，依次选择作业。

其作业执行时间图如下：采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。

其作业执行时间图如下：由于作业1，2，3是依次到来的，所以当开始时系统中只有作业1，于是作业1先被选中。

在8.0时刻，作业1运行完成，这时系统中有两道作业在等待调度，作业2和作业3，按照短作业优先调度算法，作业3只要运行1个时间单位，而作业2要运行4个时间单位，于是作业3被优先选中，所以作业3先运行。

待作业3运行完毕，最后运行作业2。

作业调度的次序是1，3，2。

另外，要记住以下公式：作业i的周转时间T i＝作业完成时间－作业提交时间系统中个作业的平均周转时间，其中Ti为作业i的周转时间。

解：采用先来先服务调度策略，则调度次序为l、2、3。

作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.02 0.4 4.0 8.0 12.0 11.63 1.0 1.0 12.0 13.0 12.0 平均周转时间T＝（8＋11.6＋12）/3＝10.53采用短作业优先调度策略，则调度次序为l、3、2。

作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.03 1.0 1.0 8.0 9.0 8.02 0.4 4.0 9.0 13.0 12.6 平均周转时间T＝（8＋8＋12.6）/3＝9.53思考题1请同学们判断这句话：作业一旦被作业调度程序选中，即占有了CPU。

操作系统PV操作经典例题与答案1. 推广例子中的消息缓冲问题。

消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次若有m个发送进程呢？Send：SB=k; //信号量，标记当前空余缓冲区资源。

i = 0; //标记存放消息的缓冲区位置while (true) {P(SB);往Buffer [i]放消息;V(SM);i = (i+1) % k;};Receive：j = 0; //标记取产品的缓存区位置SM=0；//信号量，标记初始没有消息ReadCount=0；//读进程计数器Mutex =1；//读进程互斥信号量SW=0; //信号量，读进程在此信号量等待while (true) {P(SM);从Buffer[j]取消息;ReadCount++If（ReadCount<n）{< p="">V(SM);P(SW)}else{V(SB);j = (j+1) % k;for(int g=1; g< ReadCount;g++)V(SW);ReadCount=0；}};2.第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）rc=0, //正在读者计数器wc, //写计数器rw, //读等计数器R //等待读信号量W //等待写信号量读者：while (true) {P(mutex);if (wc >0){rw++P (R);}rc++;If（rw>0&&wc=0）{V(R)rw--}V(mutex);读P(mutex);rc --;if (rc==0){If（wc>0）V(w)}V(mutex);};写者：while (true) {P(mutex);wc ++;if((wc >1)||(rc>0)){P(W)}V(mutex);写P(mutex);Wc --;if（wc>0）V(W);Else if(rw>0)V(R)rw--V(mutex);};3.理发师睡觉问题理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉。

第二章进程同步一、选择最合适的答案1. 用P、V操作管理临界区时，信号量的初值一般应定义为（）。

A.–1B.0C.1D.任意值2. 有m个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问，则信号量的变化范围是（）。

A.1至–(m-1)B.1至m-1C.1至–mD.1至m3. 在下面的叙述中，正确的是（）。

A.临界资源是非共享资源B.临界资源是任意共享资源C.临界资源是互斥共享资源D.临界资源是同时共享资源4. 对进程间互斥地使用临界资源，进程可以（）A.互斥地进入临界区B.互斥地进入各自的临界区C.互斥地进入同一临界区D.互斥地进入各自的同类资源的临界区5. 设两个进程共用一个临界资源的互斥信号量mutex，当mutex＝1时表示（）。

A.一个进程进入了临界区，另一个进程等待B.没有一个进程进入临界区C.两个进程都进入了临界区D.两个进程都在等待6. 设两个进程共用一个临界资源的互斥信号量mutex，当mutex＝-1时表示（）。

A.一个进程进入了临界区，另一个进程等待B.没有一个进程进入临界区C.两个进程都进入了临界区D.两个进程都在等待7．当一进程因在记录型信号量S上执行P(S)操作而被阻塞后，S的值为（）。

A.>0B.<0C.≥0D.≤08．当一进程因在记录型信号量S上执行V(S)操作而导致唤醒另一进程后，S的值为（）。

A.>0B.<0C.≥0D.≤09．如果信号量的当前值为-4，则表示系统中在该信号量上有（）个进程等待。

A.4B.3C.5D.010．若有4个进程共享同一程序段，而且每次最多允许3个进程进入该程序段，则信号量的变化范围是（）。

A. 3，2，1，0B. 3，2，1，0，-1C. 4，3，2，1，0D. 2，1，0，-1，-211．若信号S的初值为2，当前值为-1，则表示有( )个等待进程？A.0B.1C.2D.312．如果有三个进程共享同一互斥段，而且每次最多允许两个进程进入该互斥段，则信号量的初值应设置为（）。

关于调度算法【例1】下表给出作业l，2，3的提交时间和运行时间。

采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。

）分析解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。

我们用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。

采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。

然后按照“排队买票”的办法，依次选择作业。

其作业执行时间图如下：采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。

其作业执行时间图如下：由于作业1，2，3是依次到来的，所以当开始时系统中只有作业1，于是作业1先被选中。

在8.0时刻，作业1运行完成，这时系统中有两道作业在等待调度，作业2和作业3，按照短作业优先调度算法，作业3只要运行1个时间单位，而作业2要运行4个时间单位，于是作业3被优先选中，所以作业3先运行。

待作业3运行完毕，最后运行作业2。

作业调度的次序是1，3，2。

另外，要记住以下公式：作业i的周转时间T i＝作业完成时间－作业提交时间系统中个作业的平均周转时间，其中Ti为作业i的周转时间。

解：采用先来先服务调度策略，则调度次序为l、2、3。

作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.02 0.4 4.0 8.0 12.0 11.63 1.0 1.0 12.0 13.0 12.0 平均周转时间T＝（8＋11.6＋12）/3＝10.53采用短作业优先调度策略，则调度次序为l、3、2。

作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.03 1.0 1.0 8.0 9.0 8.02 0.4 4.0 9.0 13.0 12.6 平均周转时间T＝（8＋8＋12.6）/3＝9.53思考题1请同学们判断这句话：作业一旦被作业调度程序选中，即占有了CPU。

11.13 【答】(1)设信号量的初值为：S=1，用于P1进程与P2和P3进程；$2-$3=0，用于表示P1进程存放O或1。

f2)各进程的实现流程如下。

P1进程：L1：P(S)写入二进制if(写入二进制是0) v(s2)else V(S3) ’goto L1 ．P2进程：L2：P(S2)对0计数V(S)goto L2P3进程：L3：P(S3)对1计数V(S)goto L311.14 【答】 设信号量初值为：S=1用于表示子进程与P1进程与P2进程之间的互斥。

信号量初值t Sb=Sh=0表示是白子还是黑子。

取子进程L0：P(S)从盒子中取一子if(取的是白子)v(sb)else V(Sh)goto L0P1进程/*拣白子Ll：P(Sb)拣白子V(S)goto L1P2进程/*拣黑子L2：P(Sh)拣黑子V(S)goto L211.15 【答】 设信号量初值为： Sn=N公共缓冲池中缓冲区的数目 S0=0缓冲池装满同步信号 S2=O P1与P2进程间的同步 S=S I=I互斥信号量设变量初值为： i=0计数P1进程 P2进程L0：生产一数据LI：P(S1)P(S2)P(Sn)P(S0)P(S) P(S)将数据一缓冲区 从缓冲池取一数据i=i+l i=i-1ifi=N ifi=Othen v(s2)then V(S1)goto L0 goto L1else elsev(so) V(Sn)v(s1) V(S2)V(S) V(S)goto LO goto L111.16 【答】 进程间的控制算法如下所示：BEGINInteger rnutex l，mutex2，re；mutexl：=1：mutex2：=l；rc：=0：PARBEG／Nreader：BEGINP(mutexl)；rc：=rc+l；IF rc=l THEN P(mutex2)；V(mutexl)；Reading the file；P(mutexl)；rc：=rc一1；IF rc=0 THEN V(mutex2)V(mutexl)；ENDwirter：BEGINP(mutex2)；Writing the file；V(mutex2)；ENDPARENDEND。

问题1 一个司机与售票员的例子在公共汽车上，为保证乘客的安全,司机和售票员应协调工作：停车后才能开门，关车门后才能行车。

用PV操作来实现他们之间的协调.S1：是否允许司机启动汽车的变量S2：是否允许售票员开门的变量driver(）//司机进程{while （1）//不停地循环{P（S1)；//请求启动汽车启动汽车；正常行车；到站停车；V（S2）; //释放开门变量，相当于通知售票员可以开门}｝busman()//售票员进程｛while（1){关车门；V(S1)；//释放开车变量，相当于通知司机可以开车售票P(S2）；//请求开门开车门;上下乘客；}}注意：busman（）driver（）两个不停循环的函数问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。

要几个程序?有多少个进程？（答：一个程序;为每个读者设一个进程）（1）当图书馆中没有座位时,后到的读者在图书馆为等待（阻塞）（2）当图书馆中没有座位时，后到的读者不等待,立即回家。

解（1 ）设信号量：S=100；MUTEX=1P(S）P(MUTEX）登记V（MUTEX）阅读P（MUTEX）注销解（2）设整型变量COUNT=100;信号量：MUTEX=1;P（MUTEX）;IF (COUNT==0)｛V(MUTEX）；RETURN;｝COUNT=COUNT—1；登记V（MUTEX);阅读P(MUTEX）；COUNT=COUNT+1;V（MUTEX）；RETURN;问题3 有一座东西方向的独木桥;用P,V操作实现：(1）每次只允许一个人过桥；（2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。

（3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人设信号量MUTEX=1P （MUTEX)过桥V （MUTEX）（2)解设信号量: MUTEX=1 （东西方互斥)MD=1 (东向西使用计数变量互斥）MX=1 （西向东使用计数变量互斥)设整型变量：CD=0 （东向西的已上桥人数）CX=0 (西向东的已上桥人数)从东向西：P （MD)IF （CD=0)｛P (MUTEX) ｝CD=CD+1V (MD)过桥P （MD)CD=CD—1IF （CD=0）｛V (MUTEX) ｝从西向东：P (MX）IF （CX=0）{P （MUTEX) ｝CX=CX+1V （MX)过桥P （MX）CX=CX—1IF (CX=0){V （MUTEX) }V （MX)（3）解：从东向西的，和(2）相同;从西向东的和（1）相同。

4有三个并发进程，R负责从输入设备读入信息并传送给M，M将信息加工并传送给P，P将打印输出，写出下列条件下的并发程序：单缓冲区，缓冲区信号量初值mutex1=1; mutex2=1;buffeR-M // R 和M之间的bufbufferM_P // M 和P之间的buf另外R 自己的缓存区data_buf1,另外M 自己的缓存区data_buf2,另外P 自己的缓存区data_buf3,Procedure R：beginwhile true dodata_buf1 = 读入数据P(mutex1);buffeR-M = data_buf1;V(mutex1);endend;Procedure M:beginwhile true doP(mutex2);P(mutex1);Data_buf2 = bufferR_M;处理Data_buf2；BufferM_P = data_buf2V(mutex1);V(mutex2);endend;Procedure P:beginwhile true doP(mutex2);Data_buf3:= BufferM_P;V(mutex2);V(empty);打印输出数据endend;双缓冲区，缓冲区信号量初值mutex1=1; mutex2=1; Empty1 = 2, full1 = 0; empty2=2, full2=0; buffeR-M[2] // R 和M之间的buf，有两个bufferM_P[2] // M 和P之间的buf 有两个另外R 自己有缓存区data_buf1,另外M 自己有缓存区data_buf2,另外P 自己有缓存区data_buf3,var：i,j,k,nProcedure R：beginwhile true dodata_buf1 = 读入数据P(empty1)P(mutex1);buffeR-M[i] = data_buf1;i=(i+1)mod 2;V(mutex1);V(full1)endend;Procedure M:beginwhile true doP(full1);P(mutex1);Data_buf2 = bufferR_M[j];j=(j+1) mod 2V(mutex1);P(empty1);处理Data_buf2；P(empty2);P(mutex2)BufferM_P[k] = data_buf2;k=(k+1) mod 2V(mutex2);V(full2);endend;Procedure P:beginwhile true doP(full2);P(mutex2);Data_buf3:= BufferM_P[n];n=(n+1) mod 2V(mutex2);V(empty2);打印输出数据endend;设有三个进程A、B、C，其中A与B构成一对生产者与消费者（A为生产者，B为消费者），共享一个由n个缓冲块组成的缓冲池；B与C也构成一对生产者与消费者（此时B为生产者，C为消费者），共享另一个由m个缓冲块组成的缓冲池。

1．P、V操作是 A 。

A.两条低级进程通信原语B.两组不同的机器指令C.两条系统调用命令D.两条高级进程通信原语2．设系统中有n（n>2）个进程，且当前不在执行进程调度程序，试考虑下述4种情况，不可能发生的情况是 A 。

A．没有运行进程，有2个就绪进程，n个进程处于等待状态。

B．有1个运行进程，没有就绪进程，n-1个进程处于等待状态。

C．有1个运行进程，有1个就绪进程，n-2个进程处理等待状态。

D．有1个运行进程，n-1个就绪进程，没有进程处于等待状态。

3．若P、V操作的信号量S初值为2，当前值为-1，则表示有 B 等待进程。

A. 0个 B. 1个 C. 2个 D. 3个4．用V操作唤醒一个等待进程时，被唤醒进程的状态变为 B 。

A.等待B.就绪C.运行D.完成5．用P、V操作可以解决 A互斥问题。

A.一切B.某些C.正确D.错误6．多道程序环境下，操作系统分配资源以C 为基本单位。

A.程序B.指令C.进程D.作业7.从下面对临界区的论述中，选出一条正确的论述。

（1）临界区是指进程中用于实现进程互斥的那段代码。

（2）临界区是指进程中用于实现进程同步的那段代码。

（3）临界区是指进程中用于实现进程通信的那段代码。

（4）临界区是指进程中用于访问共享资源的那段代码。

（5）临界区是指进程中访问临界资源的那段代码。

8.（A）是一种只能由wait和signal操作所改变的整型变量，（A）可用于实现进程的（B）和（C），（B）是排他性访问临界资源。

A：（1）控制变量；（2）锁；（3）整型信号量；（4）记录型信号量。

B：（1）同步；（2）通信；（3）调度；（4）互斥。

C：（1）同步；（2）通信；（3）调度；（4）互斥。

9.对于记录型信号量，在执行一次wait操作时，信号量的值应当（A），当其值为（B）时，进程阻塞。

在执行signal操作时，信号量的值应当为（C），当其值为（D）时，应唤醒阻塞队列中的进程。