操作系统大题

3．某一系统进程的资源分配“瞬间状态”为已分配资源矩阵最多资源矩阵可用资源向量P0001200121520P110001750P213542356P306320652P400140656使用银行家算法回答：系统是否安全？如果进程P1要求(0，4，2，0)，系统能否立即满足进程的要求？解：利用安全算法对该时刻资源分配情况进行分析，如下图所示：WorkNeedAllocationWork+AllocationFinishP01520000000121532trueP21532100213542886trueP3288600200632214118trueP4214118064200142141212trueP12141212075010003141212true由以上分析可知，在该时刻存在着一个安全序列{P0，P2，P3，P4，P1}，故系统是安全的。如果进程P1要求（0，4，2，0），系统假定可为P1分配资源，由此形成的资源变化情况如图示：已分配资源矩阵需求资源矩阵最多资源矩阵可用资源向量P11420033017501100利用安全算法对该时刻资源分配情况进行分析，如下图所示：WorkNeedAllocationWork+AllocationFinishP01100000000121112trueP21112100213542466trueP324660020063221098trueP421098064200142101012trueP12101012033014203141212true用信号量和P，V操作描述读者-写者问题：即允许多个读者同时读一个共享对象，但绝不允许一个写者和其它进程同时访问共享对象。(答案写在答卷纸相应位置上)。解：varrmutex,wmutex:semaphore:=1,1;

readcount:integer:=0;writer:

begin

repeat

wait(wmutex);

performwriteoperation;

signal(wmutex);

untilfalse;

end

reader:

begin

repeat

wait(rmutex);

ifreadcount=0thenwait(wmutex);

readcount:=readcount+1;

signal(rmutex);

┇

Performreadoperation;

┇

wait(rmutex);

readcount:=readcount-1;

ifreadcount=0thensignal(wmutex);

signal(rmutex);

untilfalse;

end已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（5分）（2）LRU替换算法（5分）解：（1）FIFO算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：01420265123212621362000222555333211100011166644466622211缺页率=13/20=65%（2）LRU算法是最近最久未使用的页面予以淘汰。算法如图所示：01420265123212621362000222215363331110055111112444666222266缺页率=14/20=70%1．什么是死锁？死锁预防的措施有哪些？为什么？解：所谓死琐，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。死锁预防的措施有：（1）屏弃“请求和保持”条件，优点是简单、易于实现且很安全；（2）屏弃“不剥夺”条件，在采用这种方法预防死锁时，进程是在需要资源时才提出请求。这样，一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。这种预防死锁方法，实现起来比较复杂，且要付出很大代价。（3）摒弃“环路等待”条件，在这种方法中规定，系统将所有的资源按类型进行线形排队，并赋予不同的序号。这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量，都有较明显的改善。三个进程A、B、C，共享两个缓冲区B1和B2。缓冲区B1中可存放n件产品，缓冲区B2中可存放m件产品。进程A每次生产一件产品并将其存入缓冲区B1中；进程B每次从缓冲区B1中取出一件产品后再把它送到缓冲区B2中；进程C每次从缓冲区B2中取出一件产品去消费。为防止把产品存入已满的缓冲区，或从空的缓冲区取产品、或重复取产品，试用PV操作实现它们之间的制约。解：A（R）、B（C）、C（P）。

（1）进程间关系为：A→B1→B→B2→C

A受B制约：当B未把B1信息取走，A不能输入下一信息。

C受B制约：当B未把B1信息送入B2，C不能打印B2信息。

B同时受A、C约束：把A未把信息写入B1；C未把B2信息印出，则B不能把B1信息送至B2。

（2）设四个信号量。它们初值均为零

A私用信号量S1空。（为“0”表示B1空）

B私用信号量S1满。（为“1”表示B1满）

B私用信号量S2空。（为“0”表示B2空）

C私用信号量S2满。（为“1”表示B2满）

PV原语同步算法如下：

A：输入到B1→V（S1满）→P（S1空）过程循环往复

B：P（S1满）→B1的信息送入B2→V（S1空）→V（S2满）→P（S2空）过程循环往复

C：P（S2满）→B2的信息被打印→V（S2空）过程循环往复状态转换图如下：桌子上有一只盘子，每次只能放入一只水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个儿子专等吃盘中的桔子，一个女儿专等吃盘中的苹果。请利用P、V操作实现他们之间的同步。解：在本题中，应设置三个信号量s、so、sa，信号量s表示盘子是否为空，其初值为1；信号量so表示盘中是否有桔子，其初值为0；信号量sa表示盘中是否有苹果，其初值为0。同步描述如下：ints=1;intsa=0;intso=0;main(){cobeginfather();son();daughter();coend}father(){p(s);将水果放入盘中；if(放入的是桔子)v(so);elsev(sa);}son(){p(so);从盘中取出桔子；v(s);吃桔子；}daughter(){p(sa);从盘中取出苹果；v(s);吃苹果；}三进程量缓冲区问题semaphoresa,sb,sc,sd=1,0,1,0;/*sa表示buffer1是否可以放入数据，初值为1表示buffer1为空可以放入。*//*sb表示buffer1是否有数据可供取出计算，初值为0表示没有新数据可供取出*//*sc表示buffer2是否可以放入数据，初值为1表示buffer1为空可以放入。*//*sd表示buffer2是否有数据可供取出计算，初值为0表示没有新数据可供取出*/voidInput(){do{produceaniteminn;wait(sa);/*buffer1是否可以放入数据*/buffer1=n;/*把数据放入buffer1中*/signal(sb);/*告诉compute进程buffer1中有了新数据*/}while(TRUE);}voidCompute(){do{wait(sb);/*buffer1是否有数据可供取出计算*/m=buffer1;/*从buffer1中取出数据*/signal(sa);/*告诉Input进程buffer1可以放入新数据*/处理m，生成新数据mm；wait(sc);/*buffer2是否可以放入数据*/buffer2=mm;/*把新数据mm放入buffer2中*/signal(sd);/*告诉Outpu