操作系统PV操作习题(46页).doc

《操作系统PV操作习题(46页).doc》由会员分享，可在线阅读，更多相关《操作系统PV操作习题(46页).doc（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-操作系统PV操作习题-第 45 页一、用P、V操作描述前趋关系。P1、P2、P3、P4、P5、P6为一组合作进程，其前趋图如图23所示，试用P、V操作描述这6个进程的同步。p23 图23说明任务启动后P1先执行，当它结束后P2、P3可以开始执行，P2完成后P4、P5可以开始执行，仅当P3、P4、P5都执行完后，P6才能开始执行。为了确保这一执行顺序，设置5个同步信号量n、摄、f3、f4、g分别表示进程P1、P2、P3、P4、P5是否执行完成，其初值均为0。这6个进程的同步描述如下： 图23 描述进程执行先后次序的前趋图 int f1=0; /*表示进程P1是否执行完成* int f2=0;

2、/*表示进程P2是否执行完成* int f3=0; /*表示进程P3是否执行完成* int f4=0; /*表示进程P4是否执行完成* int f5=0; /*表示进程P5是否执行完成* main() cobegin P1( ); 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); 二、生产者

3、-消费者问题 p25 生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。生产者-消费者问题是许多相互合作进程的一种抽象。例如，在输入时，输入进程是生产者，计算进程是消费者;在输出时，计算进程是生产者，打印进程是消费者。因此，该问题具有很大实用价值。 我们把一个长度为n的有界缓冲区(n0)与一群生产者进程P、P、Pm和一群消费者进程C、C、Ck联系起来，如图24所示。假定这些生产者和消费者是互相等效的。只要缓冲区未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲区未空，消费者便可以从缓冲区中取走物

4、品并消耗它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。 图24 生产者-消费者问题 为解决这一类生产者-消费者问题，应该设置两个同步信号量，一个说明空缓冲单元的 数目，用empty表示，其初值为有界缓冲区的大小n，另一个说明满缓冲单元的数目，用 full表示，其初值为0。在本例中有P、P、Pm个生产者和C、C、Ck个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需设置一个互斥信号量mutex，其初值为1。生产者-消费者问题的同步描述如下： int full=O; /*满缓

5、冲单元的数目* int empty=n; /*空缓冲单元的数目* int mutex=1; /*对有界缓冲区进行操作的互斥信号量* main() cobegin produceri();/*i=1，2，m;j=l，2，k* consumerj(); coend produceri() /*i=1，2，m* while(生产未完成) 生产一个产品; p(empty); p(mutex); 送一个产品到有界缓冲区; v(mutex); v(full); consumerj() /*j=1，2，k* while(还要继续消费) p (full); p(mutex); 从有界缓冲区中取产品; v (m

6、utex); v (empty); 消费一个产品; 三、在操作系统中，进程是一个具有一定独立功能的程序在某个数据集上的一次 。 A等待活动 B运行活动 C单独操作 D关联操作 答：B 四、多道程序环境下，操作系统分配资源以为基本单位。 A程序 B指令 C进程 D作业 答：C 五、对于两个并发进程，设互斥信号量为mutex，若mutex=O，则。 A.表示没有进程进入临界区 B.表示有一个进程进入临界区 C.表示有一个进程进入临界区，另一个进程等待进入 D.表示有两个进程进入临界区 答：B 六、两个进程合作完成一个任务。在并发执行中，一个进程要等待其合作伙伴发来消 息，或者建立某个条件后再向前执

7、行，这种制约性合作关系被称为进程的。 A.同步 B互斥 C. 调度 D执行 答：A 七、为了进行进程协调，进程之间应当具有一定的联系，这种联系通常采用进程间交换数据的方式进行，这种方式称为。 A.进程互斥 B进程同步 C进程制约 D进程通信 答：D 八、在测量控制系统中，数据采集任务把所采集的数据送入一单缓冲区;计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。P33 分析及相关知识 在本题中采集任务与计算任务共用一个单缓冲区当采集 任务采集到一个数据后，只有当缓冲区为空时才能将数据送入缓冲区中存放，否则应等待缓冲区腾空;当缓冲区中有数据时，计算任务才

8、能从缓冲区中取出数据进行计算，否则也应等待。 本题实际上是一个生产者消费者问题。将生产者消费者问题抽象出来，以另外 一种形式描述是一种常见的试题形式只要对生产者消费者问题有了深入的理 解，就不难解决此类试题。 解;在本题中，应设置两个信号量Sf,Se，信号量Sf表示缓冲区中是否有可供打印的计算结果，其初值为0;信号量Se用于表示缓冲区有无空位置存放新的信息，其初值为1。 本题的同步描述如下： int Se=l; int Sf=0; main() cobegin get(); compute(); coend get() while (采集工作未完成) 采集一个数据： p(Se); 将数据送入缓

9、冲区中; v(Sf); compute() while(计算工作未完成) p(Sf); 从缓冲区中取出数据; v(Se); 进行数据计算; 九、图27给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。P35 图27 四个合作进程的前趋图 解：图27说明任务启动后S1先执行。当S1结束后，S2、S3可以开始执行。S2、S3 完成后，S4才能开始执行。为了确保这一执行顺序，设三个同步信号量b2、b3、b4分别 表示进程S2、S3、S4是否可以开始执行，其初值均为0。这四个进程的同步描述如下： int b2=0; /*表示进程S2是否可以开始执行* int

10、b3=0; /*表示进程S3是否可以开始执行* int b4=0; /*表示进程S4是否可以开始执行* main() cobegin S1 ( ); S2 ( ); S3 ( ); S4 ( ); coend S1 ( ) v(b2); v(b3); S2 ( ) p(b2); v(b4); S3 ( ) p(b3)： v(b4); S4 ( ) p(b4); p(b4); /*因在S2及S3完成时均对b4做了v操作，因此这里要用两个p操作* 十、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃

11、者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。P37 分析及相关知识 在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待;若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。 解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值 为1;信号量So表示盘中是否有桔子，其初值为0;信号量Sa表示盘中是否有苹果，其初 值为0。同步描

12、述如下： int S=1; int Sa=O： int So=O： main( ) cobegin father(); son(); daughter()： coend father() while (1) p(S); 将水果放入盘中; if(放入的是桔子) v(So)： else v(Sa); son( ) while(1) p(So); 从盘中取出桔子; v(S); 吃桔子; daushter() while(1) p(Sa); 从盘中取出苹果; v(S)： 吃苹果; 答十一、(华中理工大学1999年试题)设公共汽车上，司机和售票员的活动分别是：p41 司机的活动：启动车辆： 正常行车;

13、到站停车; 售票员的活动：关车门; 售票： 开车门; 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系?用信号量和P、 V操作实现它们的同步。 解;在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后， 向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司机停车取得同步。 在本题中，应设置两个信号量：s1、s2，s1表示是否允许司机启动汽车，其初值为0; s2表示是否允许售票员开门，其初值为0。用P、V原语

14、描述如下： int s1=O; int s2=O; main() cobegin driver(); busman(); coend driver() while(1) p(s1); 启动车辆; 正常行车; 到站停车; v(s2); busman() while(1) 关车门; v(s1); 售票; p(s2); 开车门; 上下乘客; 用P、V操作来控制现实生活中的操作流程是一类常见的试题。这类试题要求解题者 能将生活中的控制流程用形式化的方式表达出来。 十二、设有一个发送者进程和一个接收者进程，其流程图如图210所示。s是用于实现进程同步的信号量，mutex是用于实现进程互斥的信号量。试问流

15、程图中的A、B、C、D四框中应填写什么?假定缓冲区有无限多个，s和mutex的初值应为多少? p42 分析及相关知识 由图210可以看出，发送者进程与接收者进程之间的同步关系是：发送者进程生成的信息送入消息链中，接收者进程从消息链中接收信息;由于发送者进程产生一个消息并链入消息链后用V操作增加消息计数并唤醒接收者进程，这表示发送者进程和接收者进程是通过信号量s实现同步的，因此接收者进程应该在取信息之前先使用一个P操作来查看消息链上是否有消息，若无消息则阻塞自己;另外，发送者和接收者对消息链的访问应使用信号量进行互斥，即在访问前使用P操作，在访问后使用V操作。 图210 发送者及接收者工作流程图

16、 解：由上述分析可知，A、B、C、D四框应分别填入： A框 P(mutex) B框 V(mutex) C框 P(s) D框 P(mutex)开始时，消息链上没有可供接收的信息，所以s的初值为0;互斥信号量mutex的初值应为1。 十三、(北京大学1990年试题)p46 写出P、V操作的定义。 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存 的缓冲区1，每执行一次读一个记录;PB将缓冲区1的内容复制到缓冲区2，每执行一次 复制一个记录：PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。 分析及相关

17、知识 信号量是一个确定的二元组(s，q)，其中s是一个具有非负初值的整型变量，q是一个与s相关联的初始状态为空的队列整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目; 当其值小于0时，其绝对值表示系统中因请求谊类资源而被阻塞的进程数目除信号量的初值外，信号量的值仅能由P操作和V操作改变。 解：P、V操作是两条原语，它们的定义如下： P操作 P操作记为P(S)，其中S为一信号量，它执行时主要完成下述动作： S=S-1 若S0，则进程继续运行。 若S0，则进程继续执行。 若S0，则从信号量等待队列中移出队首进程，使其变为就绪状态。 在本题中，进程PA、PB、PC之间

18、的关系为：PA与pB共用一个单缓冲区，而PB 又与PC共用一个单缓冲区，其合作方式可用图212表示。当缓冲区1为空时，进程PA可将一个记录读入其中;若缓冲区1中有数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中;若缓冲区2中有数据，则进程PC可以打印记录。在其他条件 下，相应进程必须等待。事实上，这是一个生产者-消费者问题。 图212 进程间的合作方式 为遵循这一同步规则。应设置四个信号量emptyl、empty2、full1、full2，信号量emptyl 及empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1;信号量full1及full2分别表示缓冲区1及缓冲区2是否

19、有记录可供处理，其初值为0。其同步描述如下： int emptyl=l; int empty2=l; int fulll=O; int full2=O; main() cobegin PA ( ); PB ( ); PC ( ); coend PA ( ) while (1) 从磁盘读一个记录： p(emptyl); 将记录存入缓冲区1; v(fulll)： PB ( ) while(1) p(fulll); 从缓冲区1中取出记录; v(emptyl); p(empty2); 将记录存入缓冲区2; v(full2); PC ( ) while(1) p(full2); 从缓冲区2中取出记录;

20、v(empty2); 打印记录; 本题也是一个典型的生产者。消费者问题。其中的难点在于PB既是个生产者又是一个消费者。 十四、设有8个程序progl、prog2、prog8。它们在并发系统中执行时有如图213所示的制约关系，试用P、V操作实现这些程序间的同步。P48 解：由图213表明开始时，progl及prog2先执行。当progl和prog2都执行完后，prog3、 prog4、prog5才可以开始执行。prog3完成后，prog6才能开始执行。prog5完成后，prog7 才能开始执行。prog6、prog4、prog7都结束后，prog8才可以开始执行。为了确保这一执行顺序，设7个同步

21、信号量f1、f7分别表示程序progl、prog7是否执行完，其初值均为0。这8个进程的同步描述如下： int fi=0; /*表示程序progl是否执行完* int f2=0; int f3=0： int f4=O; int f5=0; int f6=0; int f7=0; main() cobegin progl(); prog2(); prog3(); prog4(); prog5(); prog6(); prog7(); prog8(); coend progl() v(f1); v(f1); v(f1); prog2() v(f2); v(f2); v(f2); prog3() p

22、(f1); p(f2); v(f3); prog4() p(f1); p(f2); v(f4); prog5() p(f1); p(f2); v(f5); prog6() p(f3); v(f6); prog7() p(f5); v(f7); prog8() p(f4); p(f6); p(f7); 十五、(北京大学1991年试题)有一个仓库，可以存放A和B两种产品，但要求： (1)每次只能存入一种产品(A或B);p50 (2)-N(A产品数量一B产品数量)M。 其中，N和M是正整数。试用P、V操作描述产品A与产品B韵入库过程。 分析及相关知识 本题给出的第一个条件是临界资源的访问控制，可用一

23、个互斥信号量解决该问题。第二个条件可以分解为： -NA产品数量一B产品数量 A产品数量一B产品数量M 也就是说，A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上 解;在本题中，我们可以设置两个信号量来控制A、B产品的存放数量，sa表示当前 允许A产品比B产品多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允 许sa个A产品入库;sb表示当前允许B产品比A产品多入库的数量，即在当前库存量和 A产品不入库的情况下，还可以允许sb个B产品入库。初始时，sa为M一1，sb为N一1， 当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一

24、个B产品时，则允许存入A产品的数量也增加1。 产品A、B的入库过程描述如下： int mutex=1; /*互斥信号量* int sa=M-1; int sb=N-1; main( ) while(1) 取一个产品; if(取的是A产品) p(sa); p(mutex); 将产品入库; v(mutex); v(sb)： else /*取的产品是B* p(sb); p(mutex); 将产品入库; v(mutex); v(pa); 从本题的解法可以看出，当有比较复杂条件出现时，可以把复杂条件分解成一组简单条件，这样就能很容易地写出对应的程序流程了。 十六、(南开大学1997年试题)在南开大学和天

25、津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但其中有一个小的安全岛M(同时允许两辆自行车停留)，可供两辆自行车已从两端进入小路情况下错车使用，如图214所示。试设计一个算法使来往的自行车均可顺利通过。p53 错 分析及相关知识 在本题中，需要控制路段T到L，路段S到K及安全岛M的使用。路段T到L及路段S到K同时只允许一辆自行车通过，而安全岛M允许两辆自行车使用，因此可以用三个信号量来管理它们。另一方面，同一方向上的自行车最多只能有一辆通过这段路(两个方向上有两辆)，因此还应该用两个信号量来控制 解：在本题中，应设置5个信号量ST，TS，K，L，M，信号量ST表示是否

26、允许自行 车从南开大学去天津大学，其初值为1;信号量TS表示是否允许自行车从天津大学去南开 大学，其初值为1;信号量K表示是否允许自行车通过路段S到K，其初值为1;信号量L表示是否允许自行车通过路段T到L，其初值为1;信号量M表示安全岛上还可停放自行车的数目，其初值为2。其控制过程描述如下： int ST=1; int TS=1; int K=1; int L=1; int M=2; totian( ) /*从南开大学去天津大学* p(ST); p(K); 从S走到K; p(M); 进入安全岛; v(K); p(L); 从L走到T; v(M); v(L); v(ST); tonan() /*从

27、天津大学去南开大学* p(TS); p(L); 从T走到L; p(M); 进入安全岛; v(L); p(K); 从K走到S; v(M); v(K); v(TS); 另一题 在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M(同时允许两辆自行车停留)，可供两辆自行车已从两端进入小路情况下错车使用，如图3-28所示。试设计一个算法使来往的自行车均可顺利通过。L3.46 p129 正确 解答 由于小路中间的安全岛M仅允许两辆自行车停留，本应该作为临界资源而设置信号量， 但仔细分析可以发现：在任何时刻进入小路的自行车最多不会超过两辆(南开

28、和天大方向各一辆)，因此，无需为安全岛M设置信号量。在路口S处，南开出发的若干自行车应进行进入小路权的争夺，以决定谁能够进入小路SK段，为此，设置信号量S(初值为1)来控制南 开路口资源的争夺。同理，设置信号量T(初值为1)来控制天大路口资源的争夺。此外， 小路SK段仅允许一辆自行车通过，所以设置信号量SK(初值为1)来进行控制，而对于LT 段则设置信号量LT(初值为1)进行控制。 begin S：=1；T：=1； SK：=1；LT：=1； cobegin 进程i (i为南开方向的自行车，i=1，2，)： begin P(S)； /*与其他南开方向的自行车争夺路口S的使用权* P(SK)； /

29、*同对面(天大)来的自行车争夺SK路段的使用权* 通过SK路段； 进入安全岛M； V(SK)； /*一旦进入安全岛M便可释放路段SK的使用权* P(LT)； /*同对面(天大)来的自行车争夺LT路段的使用权* 通过LT路段： V(LT)； *已通过LT路段，释放路段LT的使用权* V(S) /*已经通过小路，则允许在路口S等待的自行车争夺再次进入S的 使用权* end； 进程j (j为天大方向的自行车，j=1，2，)： begin P(T)； /*与其他天大方向的自行车争夺路口T的使用权* P(LT)； /*同对面(南开)来的白行车争夺LT路段的使用权* 通过LT路段； 进入安全岛M； V(L

30、T)： /*旦进入安全岛M便可释放路段LT的使用权* P(SK)： *同对面(南开)来的自行车争夺SK路段的使用权* 通过SK路段： V(SK)； /*已通过SK路段，释放路段SK的使用权* V(T) /*已经通过小路，则允许在路口 T等待的臼行车争夺再次进 入T的使用权* end coend end； 注意：如果在进程i进入安全岛M后，在释放路段SK的同时释放了路口S，而此时进程i 也进入安全岛，同样在释放路段LT的同时释放路口T，那么，南开、天大方向将各有一自行车又进入路段SK和路段LT，这使得在安全岛M中的两辆自行车都无法继续前进，而在SK路段和LT路段的自行车也无法进入安全岛M，从而造

31、成死锁。因此，进程i在进入安全岛M后是为对面天大)来的自行车释放路段SK的使用权，而进程j在进入安全岛M后也是为对面(南开)来的自行车释放路段LT的使用权。 十七、(中国科学院软件研究所1995年试题)多个进程共享一个文件，其中只读文件的 称为读者，只写文件的称为写者。读者可以同时读，但写者只能独立写。请： 说明进程间的相互制约关系，应设置哪些信号量? 用P、V操作写出其同步算法。 修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者必须等 待。而无论是否有读者在读文件。 解：本题前两问是经典读者写者问题，第三问对读者写者问题加了一些限制，即使算 法对写者优先。 进程间的相互制约

32、关系有三类：一是读者之间允许同时读;二是读者与写者之间须 互斥;三是写者之间须互斥。 为了解决读者、写者之间的同步，应设置两个信号量和一个共享变量;读互斥信号量 rmutex，用于使读者互斥地访问共享变量count，其初值为1;写互斥信号量wmutex，用于实现写者与读者的互斥及写者与写者的互斥，其初值为1;共享变量count，用于记录当前正在读文件的读者数目，初值为0。 进程间的控制算法如下所示： int rmutex=l; int wmutcx=l; int count=0; main( ) cobegin reader( ); writer( ); coend reader( ) whi

33、le (1) p(rmutex); if(count=0) p(wmutex); /*当第一个读者读文件时，阻止写者写* count+; v(rmutex); 读文件; p(rmutex); count -; if(coun=)v(wmutex); /*当最后一个读者读完文件时，允许写者写* v(rmutex); writer( ) while(1) p(wmutex); 写文件; v(wmutex); 为了提高写者的优先级，增加一个信号量s，用于在写进程到达后封锁后续的读者。 其控制流程如下： int rmutex=1; int wmutex=l; int count=0; int s=1;

34、 main() cobegin reader(); writer(); coend reader() while (1) p(s); p(rmutex); if(coun=0) p(wmutex); /*当第一个读者读文件时，阻止写者写* count+; v(rmutex); v(s); 读文件; p(rmutex); count-; if(count=0)v(wmutex); /*当最后一个读者读完文件时，允许写者写* v(rmutex); writer() while(1) p(s); p(wmutex); 写文件; v(wmutex); v(S); 十八、既考虑作业等待时间，又考虑作业执

35、行时间的调度算法是 。 A. 响应比高者优先 B短作业优先 p91 C优先级调度 D先来先服务 答：A 十九、是指从作业提交给系统到作业完成的时间间隔。p91 A周转时间 B响应时间 C. 等待时间 D运行时间 答：A 二十、作业从进入后备队列到被调度程序选中的时间间隔称为。p91 A周转时间 B响应时间 C. 等待时间 D触发时间 答：C 二十一、假设下述四个作业同时到达，当使用最高优先数优先调度算法时，作业的平均周转时间为小时。 P91 作业 所需运行时间 优先数 1 2 4 2 5 9 3 8 1 4 3 8 A4.5 B10.5 C4.75 D10.25 答：D 二十二、系统在，发生从

36、目态到管态的转换。P92 A. 发出P操作时 B发出V操作时 C执行系统调用时 D. 执行置程序状态字时 答：C 二十三、操作系统为用户提供两个接口。一个是，用户利用它来组织和控制作业的执行或管理计算机系统。另一个是，编程人员使用它们来请求操作系统提供服务。p92 答：命令接口 程序接口 二十四、设有一组作业，它们的提交时间及运行时间如下：p93 作业号 提交时间 运行时间(分钟) 1 9:00 70 2 9:40 30 3 9:50 10 4 10:10 5 在单道方式下，采用短作业优先调度算法，作业的执行顺序是。 答：1、4、3、2 二十五、设有4道作业，它们的提交时间及执行时间如下：p93 作业号 提交时间 执行时间 1 10.0 2.0 2 10.2 1.0 3 10.4 0.5 4 10.5 0.3 试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。(时间单位：小时，以十进制进行计算。) 解：若采用先来先服务调度算法，则其调度顺序为1、2、3、4。 作业号 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间 1 10.0 2.0 10.0 12.0