作业一：进程同步与互斥

作业一：进程同步与互斥一、选择题1．任何两个并发进程之间存在着（）的关系。A．各自完全独立B．拥有共享变量C．必须互斥D．可能相互制约2．并发进程执行时可能会出现“与时间有关的错误”，这种错误是由于并发进程（）引起的。A．使用共享资源B．执行的顺序性C．要求计算时间的长短D．程序的长度3．用来实现进程同步与互斥的PV操作实际上是由（）过程组成的。A．一个可被中断的B．一个不可被中断的C．两个可被中断的D.两个不可被中断的6．进程从运行态变为等待态可能由于（）。A．执行了V操作B．执行了P操作C．时间片用完D．有高优先级进程就绪7．用PV操作管理互斥使用的资源时，信号量的初值应定义为（）。A．任意正整数B．1C．0D．-18．现有n个具有相关临界区的并发进程，如果某进程调用P操作后变为等待状态，则调用P操作时信号量的值必定为（）。A．≤0B．1C．n-1D．n10．用PV操作管理临界区时把信号量的初值定义为1，现已有一个进程在临界区，但有n个进程在等待进人临界区，这时信号量的值为（）。A．-1B．1C．-nD．n11．用V操作唤醒一个等待进程时，被唤醒进程的状态应变成（）状态。A．执行B．就绪C．运行D．收容12．进程间的同步是指进程间在逻辑上的相互()关系。A．间接B．制约C．继续D．调用13．对于两个并发进程，设互斥信号量为mutex，若mutex=0，则________A．表示没有进程进入临界区B．表示有一个进程进入临界区C．表示有一个进程进入临界区，另一个进程等待进入D．表示有两个进程进入临界区14．设系统中有n（n2）进程，且当前不在执行进程调度程序，试考虑下述4种情况哪种不能发生：A．没有运行进程，有2个就绪进程，n-2个进程处于等待状态。B．有1个运行进程，没有就绪进程，n-1个进程处于等待状C．有1个运行进程，有1个就绪进程，n-2个进程处于等待状态D．有1个运行进程，有n-1个就绪进程，没有进程处于等待状态15．有m个进程共享同一临界资源，若使用信号量机制实现对资源的互斥访问，则信号量值的变化范围是_(1-m)~1_________16.设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是_1,2___二、分析题1、下面是两个进程P0、P1互斥是用临界区的解决方法，能否达到互斥的目的？设变量是flag[2]，且初值为：flag[0]=flag[1]=0;进程Pi:/*i=0或1*/flag[i]=1;while(flag[(i+1)%2]==1);Pi的临界区代码；flag[i]=0;解答：考虑下列事件序列：P0、P1在while语句上无限循环，都不能进入临界区。故上述算法不能用来实现互斥。三、应用题1.若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D只从盘中取梨子。试用P、V操作写出同步算法。semaphoreempty,apple,pear;itemplate;empty.value=1,apple.value=pear.value=0parbeginprocessPA{wait(empty);plate=apple;signal(apple);}processPB{wait(empty);plate=pear;signal(pear);}processPC{wait(apple);apple=plate;signal(empty);}processPD{wait(pear);pear=plate;signal(empty);}parend2.三个进程P1、P2、P3互斥使用一个包含N(N0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某个单元中；P2每次用getodd()从缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。semaphoreempty,fullodd,fulleven;itembuffer[N];empty.value=N;fullodd.value=0;fulleven.value=0;parbeginprocessp1{number=produce();wait(empty);wait(mutex)put();if(numberisodd)signal(fullodd);elsesignal(fulleven);signal(mutex);}processp2{wait(fullodd);wait(mutex)getodd();Countodd()++;signal(mutex)signal（fullodd）;};processp3{wait(fulleven);wait(mutex)geteven();counteven()++;signal(mutex);signal(fulleven);}parend3.哲学家就餐问题：有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子，他们的生活方式是交替地进行思考和进餐。平时，每个哲学家进行思考，饥饿时便试图拿起其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。下图是其示意图。（思考题，选做）4.理发师问题描述如下：理发店包含一间接待室和一间工作室，接待室内有n(n≥1)把椅子，而工作室只有1把椅子。如果没有顾客，理发师就去睡觉；如果来时所有椅子都有人，那么顾客离去；如果理发师在忙且接待室有空闲椅子，那么此顾客会坐在其中1把空闲的椅子上等待；如果理发师在睡觉；则顾客会唤醒他。请采用信号量机制解决该理发师问题(可用伪代码描述)。（思考题，选做）解：引入3个信号量和1个控制变量：（1）控制变量count用来记录等待理发的顾客数，初值为0；当count=n时，新来的顾客离去。（2）信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；（3）信号量barbers用来记录等候顾客的理发师数，并用作阻塞顾客进程，初值为0；（4）信号量mutex用于对共享变量count的互斥访问，初值为1。BEGINvarbarbers,customers,mutex:semaphore;count:integer;barbers:=customers:=0;mutex:=1;count:=0;COBEGINprocessbarbers:beginwhile(true){P(customers);//是否有顾客，没有就睡觉P(mutex);//进程互斥访问countcount:=count-1;V(barbers);//通知customers进程V(mutex);//开放临界区cut_hair();//给顾客理发{processcustomers:beginP(mutex);//进程互斥if(countn){count:=count+1;V(customers);//必要的话唤醒理发师V(mutex);//开放临界区P(barbers);//无理发师，顾客坐等get_cuthair();//该顾客坐下来理发}else{V(mutex);exit();//人满了，走吧endCOENDEND`