操作系统考研综合应用题分析

PV原语题利用信号量实现互斥：对每一临界资源（区）设一信号量S，初值=1。（此时S相当于此临界资源的使用许可证）进程1：{……P(s)临界区;V(s)……}进程2：{……P(s)临界区;V(s)……}在实现互斥时应注意wait(mutex)和signal(mutex)必须成对地出现。缺wait(mutex)将会引起系统混乱，不能保证对临界资源的互斥访问缺signal(mutex)将会使该临界资源永久不被释放用信号量描述同步：有一个同步条件设一S，初值S=0。（S为可用资源个数）实现：A进程已执行过程序段1，B进程才能执行程序段2。设一信号量S，初值为0。A进程程序段1L1：V(s);B进程L2：P(s);程序段2……………………•利用信号量实现前驱关系（同步例子）P1P2设置一个信号量S，其初值为0,P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2例：在公共汽车上，司机和售票员各司其职。司机：正常行车、到站停车、启动开车；售票员：售票、开车门、关车门。司机和售票员之间应该密切配合，协调一致，以确保行车安全。请用PV操作实现司机和售票员之间的同步。司机：while(1){正常行车；到站停车；signal(open)；wait(run)；启动开车；}售票员：While(1){售票；wait(open)；开车门；关车门；signal(run)；}用2个私有信号量open、run分别表示可以开门和可以开车．由于初始状态是汽车行车和售票员售票，所以初值应该都为0，到站后才会有司机发消息让开门．例：桌子上有一只盘子，每次只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。fathermothersondaughtersemaphoreempty=1,orange=0,apple=0；orange是son的私有信号量，表示盘子中是否放入橘子。empty是father、mother的私有信号量，表示盘子是否为空。apple是daughter的私有信号量，表示盘子中是否放入苹果。father(){while(1){P(empty);向盘子中放苹果；V(apple);}Daughter(){while(1){P(apple);从盘子中取苹果；V(empty);}Mother(){while(1){P(empty);向盘子中放橘子；V(orange);}son(){while(1){P(orange);从盘子中取橘子；V(empty);取动物问题题目：有一只铁笼子，每次只能放入一只动物，猎人向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪。试用P、V操作写出能同步执行的程序。分析：四者之间的关系：1.猎人和农民要互斥使用笼子，所以两者之间是互斥关系；2.猎人放老虎，动物园取老虎，所以两者是同步关系；3.农民房猪，饭店取猪，所以两者也是同步关系。semaphoreS_EmptyCage=1,S_Tiger=0,S_Pig=0;voidhunter()//猎人进程{while(1){P(S_EmptyCage);往笼子里放入一只老虎；V(S_Tiger);}}voidfarmer()//农民进程{while(1){P(S_EmptyCage);往笼子里放入一只猪；V(S_Pig);}}voidzoo()//动物园进程{while(1){P(S_Tiger);从笼子里取出一只老虎；V(S_EmptyCage);；}}voidrestaurant()//饭店进程{while(1){P(S_Pig);从笼子里取出一只猪；V(S_EmptyCage);；}}例：三个进程P1、P2、P3互斥使用一个包含N（N0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。semahporeempty=N,even=0,odd=0,mutex=1;P1():while(1){x=produce();wait(empty);wait(mutex);put(x);ifx%2==0signal(even);elsesignal(odd);signal(mutex);}P2():while(1){wait(odd);wait(mutex);getodd();countodd();signal(mutex);signal(empty);}P3():while(1){wait(even);wait(mutex);geteven();counteven();signal(mutex);signal(empty);}例4：一个供应商用汽车给某超市送货，并把汽车上的货物用超市的三轮车运到仓库中。超市的工作人员也用三轮车从仓库中取货去出售。假设共有3辆三轮车，仓库中只能容纳10辆三轮车的货物，且每次从汽车上取货只能供给一辆三轮车，仓库也只能容纳一辆三轮车进入。考虑相关信号量的定义及初值，并写出用P、V操作实现向仓库中送货及从仓库中取货的同步算法。信号量定义及初始值：S=3(控制三轮车数量)mutex1=1（控制互斥访问汽车）mutex2=1（控制互斥访问仓库）empty=10（仓库容量）full=0（仓库现有库存量，供给超市）从汽车到仓库进程：P(empty);P(S);P(mutex1);从汽车上取货；V(mutex1);去仓库；P(mutex2);入仓库装货；V(mutex2);V(S);V(full);从仓库到超市进程：P(full);P(S);P(mutex2);从仓库取货；V(mutex2);V(empty);去超市；V(S);例5：a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。解析：读者－写着问题的变形。我们设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入的车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入的车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1。两个共享变量ab和ba的初值分别为0、0voidPab(){while(1){wait(S1);if(ab==0)wait(Sab);ab=ab+1;signal(S1);车辆从a点驶向b点;wait(S1);ab=ab-1;if(ab==0)signal(Sab);signal(S1);}}voidPba(){while(1){wait(S2);if(ba==0)wait(Sab);ba=ba+1;signal(S2);车辆从b点驶向a点;wait(S2);ba=ba-1;if(ba==0)signal(Sab);signal(S2);}}已知一个求值公式（A2+3B）/(B+5A),若A,B已赋值，试画出该公式求值过程的前趋图，并用信号量解决公式的求解过程。S1:x1=A*AS2:x2=3*BS3:x3=5*AS4:x4=x1+x2S5:x5=B+x3S6:x6=x4/x5开始结束S1S4S6S5S3S2S1S4S6S5S3S2structsemaphorea,b,c,d,e,=0,0,0,0,0;cobegin{S1;V(a);}{S2;V(b);}{S3;V(c);}{P(a);P(b);S4;V(d)}{P(c);S5;V(e);}{P(d);P(e);S6);}coendacbde某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。应首先考虑清楚本题需要几个进程。从井中取水后向缸中倒水此为连续动作，可算同一进程，从缸中取水为另一进程。在考虑信号量，有关互斥的资源有水井（一次仅一个水桶进出），水缸（一次如水取水时均为一桶），分别为之设置信号量mutex1,mutex2控制互斥；另有同步问题存在：三个水桶无论从井中取水还是入出水缸都是一次一个，应为之设信号量count，抢不到水桶的进程只好等待；还有水缸满时，不可入水，设信号量empty,控制入水量，水缸空时不可出水，设信号量full,控制出水量。mutex1:=1;mutex2:=1;empty:=10;full:=0;count:=3;cobegin小和尚打水:beginL1:P(empty);P(count);P(mutex1);从井中取水；V(mutex1);P(mutex2);送入水缸；V(mutex2);V(count);V(full);GotoL1:end;老和尚取水：beginL2:P(full);P(count);P(mutex2);从缸中取水；V(mutex2);V(empty);V(count);GotoL2end;coend.某工厂有两个生产车间，两个生产车间分别生产A，B两种零件，装配车间的任务是把A，B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1，F2上，F1存放零件A，F2存放零件B，F1和F2的容量均为可以存放10个零件。装配工人每次从货架上取一个A零件和一个B零件然后组装成产品。请用PV操作进行正确管理。该题是生产者消费者的变形，可以认为一个消费者（装配工人）同两个生产者（A，B车间）互斥试用两个缓冲区（F1，F2），可设mutex1，mutex2（初值为1）控制进程对F1，F2的互斥操作，另设empty1，empty2（初值均为10），full1，full2（初值均为0）。过程如下：CobeginA车间：Begin生产一个产品；P（empty1）；P（mutex1）；放入F1；V（mutex1）；V（full）；End装配工人：BeginP(full1);P(full2);P(mutex1);P(mutex2);取A和B；V(mutex1);V(mutex2);V(empty1);V(empty2);EndB车间Begin生产一个产品；P(empty2);P(mutex2);放入F2；V(mutex2);V(full2);End例.某银行提供1个服务窗口和10个供顾客等待的坐位，顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：CobeginProcess营业员{Process顾客;{WhileCTRUE){从取号机获取一个号码;{叫号;等待叫号;为顾客服务;获取服务;}}}}coend请添加必要的信号量和P,V(或wait()、signal())操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。Semaphoreseets=10;//表示空余座位数量的资源信号量，初值为10Semaphoremutex=1;//管理取号机的互斥信号量，初值为1，表示取号机空闲Semaphorecustom=0;//表示顾客数量的资源信号量，初值为0Process顾客{P(seets);//找个空座位先P(mut