《操作系统全真试题分类解析(答案)》由会员分享,可在线阅读,更多相关《操作系统全真试题分类解析(答案)(79页珍藏版)》请在金锄头文库上搜索。
1、操作系统硕士研究生入学考试全真试题分类解析一、 与时间有关错误类二、 进程管理及调度类三、 同步和互斥类四、 死锁问题类五、 存储管理类六、 文件管理类七、 设备管理类一、 与时间有关错误类北航2001与时间有关错题有两个优先级相同的进程P1和P2,各自执行的操作如下,信号量S1和S2初值均为0。试问P1、P2并发执行后,x、y、z的值各为多少?P1: P2:begin begin y:=1; x:=1; y:=y+2; x:=x+1; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.答:现对进程语句进行编
2、号,以方便描述。P1: P2:begin begin y:=1; x:=1; y:=y+2; x:=x+1; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.、和是不相交语句,可以任何次序交错执行,而结果是唯一的。接着无论系统如何调度进程并发执行,当执行到语句时,可以得到x=5,y=3。按Bernstein条件,语句的执行结果不受语句的影响,故语句执行后得到z=4。最后,语句和并发执行,最后结果为:语句先执行,再执行:x=5,y=7,z=9。语句先执行,再执行:x=5 ,y=12,z=9。华中科技大2000
3、、国防科大1999与时间有关错题进程P0,P1共享变量flag和turn。若flag和turn单元内容的修改和访问是互斥的,它们如下进入临界区:var flag:array01 of Boolean; turn:01;flag0:=flag1:=false;turn:=0;process i (i=0 or 1) while truedo begin flagi:=true; . while turni . do begin while flagj=false do skip; turn:=i . end; 临界区; flagi:=false; 出临界区; end.该算法能正确实现互斥吗?应如
4、何修改?解:不能。若P0执行到,flag0:=true;这时P0被打断,P1开始执行,首先执行.,使得flag1的值为true。接着执行,由于turn的初值为0,故进入内循环时turn置为1。这时调度转向P0,P0也进入内循环,由于flag1的值己为true,故P0再次把turn值置为0。重复上述两个操作,没有进程能进临界区。修改算法如下:var flag:array01 of Boolean; turn:01;flag0:=flag1:=false;turn:=0 or 1;process 0 while truedo begin flag0:=true; turn:=1; while fl
5、ag1 and turn=1 do skip; 临界区; flag0:=false; 出临界区; end;process 1 while truedo begin flag1:=true; turn:=0; while flag0 and turn=0 do skip; 临界区; flag1:=false; 出临界区; end;此算法能保证互斥,讨论:1 没有进程在临界区,显然,任一进程能进入。 2 有一个进程己在临界区,另一个必将在while flagk and turn=k (k=0 or 1)上做空操作等待进入。 3 进程交叉执行时,有一个也必将在while flagk and turn
6、=k (k=0 or 1)上做空操作等待进入。复旦大学1999、浙江大学1997与时间有关错题下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥”(mutual exclusion)、“空闲让进”(progress)、“有限等待”(bounded waiting)等三方面讨论它的正确性。如果它是正确的,则证明之;如果它不正确,请说明理由。program attemp; var c1,c2:integer;procedure p1; (/* 对第一个进程p1 */) beginrepeat Remain Section 1;repeat c1:=1-c2until c20;Critic
7、al Section; (/* 临界区 */)c1:=1 until false end;procedure p2; (/* 对另一个进程p2 */) beginrepeat Remain Section 2;repeat c2:=1-c1until c10;Critical Section; (/* 临界区 */)c2:=1 until false end; begin (/* 主程序 */)c1:=1;c2:=1;cobegin p1;p2 (/* 两进程p1, p2开始执行 */)coend end.答:(1)互斥己知c1和c2的初值为1,若进程P1执行到c1:=1-c2时,进程P2也同
8、时执行c2:=1-c1。这样一来,c1和c2的值都变为0。于是,P1和P2会同时进入临界区,不满足互斥条件。(2) 有空让进设开始无进程在临界区中,进程P1执行了c1:=1-c2,由于c2的初值为1,这使得c1的值变为0但c2仍为1,从而保证了P1进入临界区。当P1退出临界区时,执行了c1:=1,使得P2就可进入临界区。进程P2先执行的情况相似,能保证有空让进的原则。(3) 有限等待不一定能实现。假定进程P1离开临界区,进程P2申请进入临界区,但还未来得及执行c2:=1-c1时,进程P1又再次执行c1:=1-c2,抢先进入临界区。因而,造成饥饿现象。北京大学1993、国防科大2001与时间有关
9、错举例说明P,V操作为什么要用原语实现?操作系统如何实现这种原语操作?解:信号量S是P,V均要操作的共享变量,每次它们有对S的加或减1操作。若不把P,V设计成原语,则它们交替在同一信号量上操作时会造成S值不惟一,更为严重的会造成某些进程处于永远等待状态。例如,若S当前值为1,第一个P操执行后,进程是不会阻塞的。但若在第一个P操作执行 if S0 then之前,有另一个进程的P操作抢先执行S:=S-1,这时S=-1,而第一个执行P操作的进程被阻塞了。这是不符合P,V原定义的含义的。附:type semaphore=record value:integer; queue: list of proc
10、ess; end procedure P(var s:semaphore); begin s.value:= s.value 1;/* 把信号量减去1 */ if s.value 0 then W(s.queue);/* 若信号量小于0,则执行P(s)的进程调用 W(s.queue) 进行自我封锁,被置成等待信号量s的状态,进入信 号量队列queue*/ end; procedure V(var s:semaphore); begin s.value:= s.value + 1; /* 把信号量加1 */if s.value 0 then R(s.queue); /* 若信号量小于等于0,则调
11、用R(s.queue) 从信号量s队列queue中释放一个等待信号量s的进程并置成就绪态*/ end;二、 进程管理与调度类中山大学1996进程管理题在UNIX系统中运行以下程序,最多可产生出多少进程?画出进程家属树。main( ) fork( ); /*pc(程序计数器),进程A fork( ); fork( );解:首先采用fork( )创建的子进程,其程序是复制父进程的;其次,父、子进程都从调用后的那条语句开始执行。当进程A执行后,派生出子进程B,其程序及状态如下:main( ) main( ) fork( ); fork( ); fork( ); /*pc(程序计数器),进程A fork( ); /*pc(程序计数器),进程Bfork( ); fork( );