搜索
**进程同步互斥问题*进程调度问题*死锁避免问题*存储器管理地址装换问题*虚拟存储器页面置换问题*磁盘调度问题**信号量类型:整型(忙等待)、记录型、AND型、一般信号量集解决的问题：1、描述前趋关系：*根据前趋图，各边分别设置信号量，初值为0；*若某边从某节点出发，在此节点操作后，对该边对应信号量作signal操作；*若某边指向某节点，在此节点操作前，对该边对应信号量作wait错作；Vara,b,c,d,e,f,g,h,i,j:semaphore:=0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);signal(f);end;beginwait(c);S4;signal(g);end;beginwait(d);S5;signal(h);end;beginwait(e);S6;signal(i);end;beginwait(f);S7;signal(j);end;beginwait(g);wait(h);wait(i);wait(j);S8;end;parendendabcdefghij2、进程互斥问题（资源共享）*根据临界资源的种类设置信号量的个数，初值为各临界资源的可用数量；*在访问临界资源前，对对应信号量作wait操作；在访问结束后作signal操作，即将临界区放在wait和signal之间。3、进程同步（相互合作）*为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)；*同步双方任一进程在进入临界区之前，应先对自己的信号量执行wait(己方信号量)操作，以测试是否有自己可用的资源。若有资源可用，则进入临界区，否则阻塞；*同步双方任一进程离开临界区后，应对合作方(对方)的信号量执行signal(对方信号量)操作，以通知(若对方处于阻塞状态，则唤醒它)对方已有资源可用(对方已可进入临界区)。有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一个座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试用wait,signal原语描述各个进程之间的同步互斥关系。Vars,mutax:semaphore:=100,1;Reader：BeginRepeatWait(s);Wait(mutex);登记；Signal(mutex);阅览图书；Wait(mutex);取消登记；Signal(mutex);Signal(s);Untilfasleend桌上有一个盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，爸爸妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出他们四人之间的同步关系程序。VARs,so,sa:semaphore:=1,0,0;//s表示盘空，so表示橘子，sa表示苹果。parbeginFather:beginrepeatwait(s);putapple();signal(sa);untilfalseendMother:beginrepeatwait(s);putorange();signal(so);untilfalseend桌上有一个盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，爸爸妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出他们四人之间的同步关系程序。Son:beginrepaetwait(so);eatorange();signal(s);untilfalseenddaughter:beginrepeatwait(sa);eatapple();signal(s);untilfalseendparend2．设公共汽车上有一位司机和一位售票员，它们的活动如下：司机：启动车辆，行车，到站停车，售票员：售票；到站开门，关门请分析司机与售票员之间的同步关系，如何用PV操作实现。答：为了安全起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下：司机：P（S1）；启动车辆；正常行车；到站停车；V（S2）；售票员：售票；P（S2）；开车门；关车门；V（S1）；2020/1/1010生产者消费者问题三个进程两个缓冲区俩俩合作（下页）；设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作。1、系统中有是三个进程GET，PRO和PUT，共用两个缓冲区BUF1和BUF2。假设BUF1中最多可放8个信息，BUF2中最多可放5个信息。GET进程负责不断地将信息送入BUF1中，PRO进程负责从BUF1中取出信息进行处理，并将处理结果送到BUF2中，PUT进程负责从BUF2中读取结果并输出。试用wait、signal原语（P、V操作）实现GET，PRO，PUT进程之间的同步算法。1、var：mutex1，mutex2，empty1，empty2，full11，full2：=1，1，8，5，0，0；GET:begin（repeatwait(empty1);wait(mutex1);送入BUF1；;signal(mutex1);signal(full);untilfalseendPRO:beginrepeatwait(full1);wait(mutex1);从BUF1中取信息加工;signal(mutex1);signal(empty1);wait(empty2);wait(mutex2);将加工后的信息放入BUF2;signal(mutex2);signal(full2);untilfalseendPUT:beginrepeatwait(full2);wait(mutex2);从BUF2中取信息输出;signal(mutex2);signal(empty2);untilfalseend2020/1/1012★信号量Aempty表示货架A的空位数，其初值为8；★信号量Afull表示货架A上存放的车架数，其初值为0；★信号量Bempty表示货架B的空位数，其初值为20；★信号量Bfull表示货架B上存放的车轮数，其初值为0；★信号量mutex用于互斥（初值为1）。【分析】设置资源信号量和互斥信号量如下：2020/1/1013VarAempty,Afull,Bempty,Bfull,mutex:semaphore;Aempty.value:=8;Afull.value:=0;Bempty.value:=20;Bfull.value:=0;mutext.value:=1;wheelcount:integer:=0;Beginparbeginworker1:beginrepeat生产一个车架；wait(Aempty);//看看货架A上是否有空位置车架放到货架A上；signal(Afull);//货架A上的车架数增1，并通知工人4untilfalse;end2020/1/1014Worker2，3:beginrepeat生产一个车轮；wait(Bempty);//看看货架B上是否有空位置wait(mutex);将车轮放到货架B上；signal(mutex);signal(Bfull);//货架B上的车轮数增1，并通知工人4untilfalse;endWorker4:beginrepeatwait(Afull);wait(Bfull);wait(Bfull);取一个车架和两个车轮；signal(Aempty);signal(Bempty);signal(Bempty);组装一辆自行车；untilfalseendparendend*哲学家就餐问题（非死锁算法）（1）varchopstick:array[0,…,4]ofsemaphore:=1,1,1,1,1;Sm:semaphore:=4;beginrepeatwait(Sm);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5);signal(Sm);think;untilfalseEnd（2）varchopstick:array[0,…,4]ofsemaphore:=1,1,1,1,1;beginrepeatswait(chopstick[i]，chopstick[(i+1)mod5]);eat;ssignal(chopstick[i]，chopstick[(i+1)mod5);think;untilfalseendvarchopstick:array[0,…,4]ofsemaphore:=1,1,1,1,1;beginrepeatifimod2=0thenbeginwait(chopstick[i]);wait(chopstick[(i+1)mod5]);end;elsebeginwait(chopstick[(i+1)mod5]);wait(chopstick[i]);end;eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5);think;untilfalseEnd读者写者问题及变形---独木桥问题假定有如下独木桥问题：过桥时，同一方向的行人可连续过桥，当某一方有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。试用信号量机制解决。答案：(1)将独木桥的两个方向分别标记为A和B。用整型变量countA和countB分别表示A、B方向上已在独木桥上的行人数。初值为0。需要设置三个初值都为1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现对独木桥的互斥使用。(2)A方向行人过桥：BeginP(SA);countA=countA+1;if(countA==1)P(mutex);V(SA);过桥；(SA);countA=countA-1;if(countA==0)V(mutex);V(SA);EndB方向行人过桥：BeginP(SB);countB=countB+1;if(countB==1)P(mutex);V(SB);过桥；P(SB);countB=countB-1;if(countB==0)V(mutex);V(SB);End2、在一个请求页式存储管理系统中，进程P共有5页，页号为0至4。若对该进程页面的访问序列为3，2，1，0，3，2，4，3，2，1，0，4，试用LRU置换算法和FIFO置换算法，计算当分配给该进程的物理块数为3时，访问过程中发生的缺页次数和缺页率。2、假设一个磁盘的每个盘面上有200个磁道，现有多个进程要求对存储在该盘面上的数据进行访问，按照这些请求到达的先后次序，它们的访问位置分别处于54、57、39、18、90、162、154、38、180号磁道上。假定当前磁头在100号磁道上。请给出按“先来服务（FCFS）”、“最短寻道时间优先(SSTF)”和“扫描（SCAN）”算法进行磁盘调度时各自实际的访问次序，并计算它们的平均寻道长度。(注：当采用扫描算法时，规定当前磁头正在向磁道号增加的方向上移动)、FCFS算法访问次序:54、