考研全真试题分类解析(答案)

1、操作系统硕士研究生入学考试全真试题分类解析一、与时间有关错误类二、进程管理及调度类三、同步和互斥类四、死锁问题类五、存储管理类六、文件管理类七、设备管理类一、 与时间有关错误类北航 2001 与时间有关错题有两个优先级相同的进程 P1和 P2，各自执行的操作如下， 信号量 S1 和 S2 初值均为 0。试问 P1、P2 并发执行后， x、y、z 的值各为多少P1：P2：beginbeginy:=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+yz:=z+x;end.end.答：现对进程语句进行编号，以方便描述。P1

2、：beginP2begin：y:=1;y:=y+2;x:=1;x:=x+1;V(S1);P(S1);z:=y+1;x:=x+y;P(S2);V(S2);y:=z+yz:=z+x;end.end.、和是不相交 句，可以任何次序交 行，而 果是唯一的。接着无 系 如何 度 程并 行，当 行到 句 ，可以得到 x=5，y=3。按 Bernstein 条件， 句的 行 果不受 句的影响，故 句 行后得到 z=4。最后， 句和并 行，最后 果 ： 句先 行，再 行：x=5，y=7，z=9。 句先 行，再 行：x=5 ，y=12，z=9。 中科技大 2000、国防科大 1999 与 有关 程 P0，P1

3、共享 量 flag 和 turn 。若 flag 和 turn 单元内容的修改和 是互斥的，它 如下 入 界区：var flag:array01 of Boolean;turn:01;flag0:=flag1:=false;turn:=0;process i (i=0 or 1)while truedo beginflagi:=true;.while turni .do beginwhile flagj=falsedo skip;turn:=i .end; 界区 ;flagi:=false;出 界区 ;end. 算法能正确 互斥 如何修改解：不能。若 P0 行到， flag0:=true;这时

4、 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 0while truedo beginflag0:=true;turn:=1;while flag1 and turn=1 do ski

5、p;临界区 ;flag0:=false;出临界区 ;end;process 1while truedo beginflag1:=true;turn:=0;while flag0 and turn=0 do skip;临界区 ;flag1:=false;出临界区 ;end;此算法能保证互斥，讨论： 1 没有进程在临界区，显然，任一进程能进入。2有一个进程己在临界区，另一个必将在while flagk andturn=k (k=0 or 1)上做空操作等待进入。3进程交叉执行时，有一个也必将在whileflagkand turn=k(k=0 or 1)上做空操作等待进入。复旦大学 1999、浙江大

6、学 1997 与时间有关错题下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥” (mutual exclusion) 、“空闲让进” (progress) 、“有限等待” (bounded waiting) 等三方面讨论它的正确性。 如果它是正确的，则证明之；如果它不正确，请说明理由。program attemp;var c1,c2:integer;procedure p1;(/*beginrepeatRemain Section 1;repeatc1:=1-c2until c20;对第一个进程p1 */)Critical Section;(/*临界区*/)c1:=1until f

7、alseend;procedure p2;(/*对另一个进程 p2 */)beginrepeatRemain Section 2;repeatc2:=1-c1until c10;Critical Section;(/*临界区 */)c2:=1until falseend;begin(/*主程序 */)c1:=1;c2:=1;cobeginp1;p2(/*两进程 p1, p2 开始执行 */)coendend.答： (1) 互斥己知 c1和c2的初值为 1，若进程 P1执行到 c1:=1-c2 时，进程 P2也同时执行 c2:=1-c1 。这样一来， c1和c2的值都变为 0。于是， P1和P2

8、会同时进入临界区，不满足互斥条件。(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 与时间有关错举例说明 P，V 操作为什么要

9、用原语实现操作系统如何实现这种原语操作解：信号量 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=recordvalue:integer;queue: list of pr

10、ocess;endprocedure P(var s:semaphore);begin:= 1;/*把信号量减去1 */if TCPU 利用率 =T/ （T+S）下面一种情况， SQ T，也就是说，进程完成任务运行过程中共切换了 T/Q 次，浪费时间为S(T/Q) 。故 CPU利用率 =T/(T+ S (T/Q) ，化简后得到：3）TQS CPU利用率 =Q/（Q+S）南京大学本课生进程管理及调度习题有一个四道作业的操作系统，若在一段时间内先后到达6 个作业，它们的提交和估计运行时间由下表给出：作业提交时间估计运行时间 ( 分钟 )18： 006028： 203538： 252048： 302

11、5系统采用 SJF 调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占。 (1) 分别给出 6 个作业的执行时间序列、 即开始执行时间、 作业完成时间、 作业周转时间。 (2) 计算平均作业周转时间。解：作业提交需运行开始运行被抢占还完成周转号时间时间时间需运行时间时间时间J18:00608:004010:35155J28:20358:20309:5595J38:25208:258:4520J48:30259:00259:2555J58:3558:458:5015J68:40108:509:0020说明 :(1) 采用 SJF,J2 到达时抢占 J1；J3 到达时抢占 J

12、2。(2) 但 J4 到达时，因不满足 SJF，故 J4 不能被运行， J3 继续执行5 分钟。(3) 注意，是 4 道的作业系统， 故后面作业不能进入主存而在后备队列等待。(4) 根据进程调度可抢占原则， J3 第一个做完。而这时 J5 可进入主存。(5)因 J5 最短，故它第二个完成。这时J6 可进入主存。(6) 因 J6 最短，故它第三个完成。(7) 然后是 :J4 、J2 和 J1(8) T=608:008:208:258:308:358:408:458:509:009:259:55J1CPU就绪队列CPUJ2CPU就绪队列CPUCPUJ3就绪队列CPUJ4后备队列CPUJ5后备队列C

13、PU三、 同步和互斥类求解同步互斥问题的一些规律：(1) 进程同步问题中，管理共享资源常常设两个信号量，而进程互斥问题中仅需设立一个信号量。(2) P、V 操作要成对调用， 在进程互斥中是针对同一个信号量进行。而在进程同步问题中， 进入临界区前后 P、V 操作是针对不同的信号量的(3) 至少有一个信号量初值大于等于1( 一般指管理共享资源的信号量 ) ，否则进程无法被启动运行。(4) 若有多个 (k) 共享资源，则某信号量初值可设为 k。北京大学 1991 年同步与互斥题有一个仓库，可以存放 A 和 B 两种产品，但要求：（ 1）每次只能存入一种产品（ A 或 B）；（ 2）N A 产品数量

14、-B 产品数量 M。其中， N和 M是正整数。 试用 P、V 操作描述产品 A 与产品 B 的入库过程。分析及相关知识 本题给出的第一个条件是临界资源的访问控制，可用一个互斥信号量解决该问题。第二个条件可以分解为：NA 产品数量 B 产品数量A产品数量 B 产品数量 M也就是说， A 产品的数量不能比 B 产品的数量少 N个以上， A产品的数量不能比 B 产品的数量多 M个以上。解：在本题中，可以设置两个信号量来控制 A、B 产品的存放数量， sa 表示当前允许 A 产品比 B 产品多入库的数量，即在当前库存量和 B 产品不入库的情况下，还可以允许 sa 个 A 产品入库；sb 表示当前允许

15、B 产品比 A 产品多入库的数量，即在当前库存量和 A 产品不入库的情况下，还可以允许 sb 个 B 产品入库。初始时， sa 为 M1，sb 为 N1。当往库中存放入一个 A 产品时，则允许存入 B 产品的数量也增加 1；当往库中存放入一个 B产品时，则允许存入 A 产品的数量也增加 1。var mutex ：semaphore=1;/* 互斥信号量 */sa，sb：semaphore；sa=M-1; sb=N-1;mian( )while (1) 取一个产品；if(取的是 A 产品 )P(sa);P(mutex);将 A 产品入库；V(mutex);V(sb);else/*取的产品是B*/

16、P(sb);P(mutex);将 B 产品入库；V(mutex);V(sa);北京大学 1994 年同步与互斥 程 A1，A2，An1通 m个 冲区向 程 B1，B2， Bn2不断地 送消息。 送和接收工作遵循如下 ：每个 送 程一次 送一个消息， 写入一个 冲区， 冲区大小等于消息 度； 每一个消息， B1，B2，Bn2 都 各接收一次， 入各自的数据区内； m个 冲区都 ， 送 程等待；没有可 的消息 ，接收 程等待。 用 P、 V 操作 正确的 送和接收工作。分析及相关知 本 是生 者消 者 的一个 形，一 生 者 A1，A2， An1 和一 消 者 B1，B2，Bn2 共用 m个 冲区

17、，每个 冲区只要写一次，但需要 n2 次。因此，可以把 一 冲区看成 n2 冲区，每个 送者需要同 写 n2 冲区中相 的 n2 个 冲区，而每一个接收者只需 它自己 的那 冲区中的 元。解：在本 中， 置一个信号量mutex 程 冲区的互斥访问；两个信号量数组emptyn2和fulln2描述n2 组缓冲区的使用情况。mutex的初始值为1； empty 中的元素初值为m；数组full中的元素初值为0。其同步关系描述如下：var mutex,emptyn2,fulln2：semaphore;int i;mutex=1;for(i=0;i=n2-1;i+)emptyi=m;fulli=0;mai

18、n ()cobeginA1( );A2( );An1 ()B1 ();B2 ();Bn2( );coendsend ( )/*发送消息 */ int i;for (i=0;i=n2-1;i+)p(emptyi);p(mutex);将消息放入缓冲区；V （mutex）; for(i=0;i=n2-1;i+)V(fulli);receive(i)/*进程 Bi 接收消息 */p(fulli);p(mutex);将消息从缓冲区取出；V(mutex);V(emtpyi);Ai ( )/*因 送 程 A1,A2, An1 的程序 似， 里只 出 程 Ai 的描述 */while (1)send ( );

19、Bi ( )/*因接收 程 B1,B2, Bn2 的程序 似， 里只 出 程 Bi 描述 */while (1)receive(i);北大 1995 年同步与互斥题有一个仓库可存放 A、B 两种零件，最大库容量各为 m个。生产车间不断地取 A 和 B 进行装配， 每次各取一个。 为避免零件锈蚀， 按先入库者先出库的原则。 有两组供应商分别不断地供应 A 和 B，每次一个。为保证配套和合理库存， 当某种零件比另一种零件超过 n(nm)个时，暂停对数量大的零件的进货， 集中补充数量少的零件。 试用信号量与P、V 操作正确地实现它们之间的同步关系。答：按照题意，应满足以下控制关系： A 零件数量 -

20、 B 零件数量 n；B零件数量 - A 零件数量 n；A 零件数量 m；B 零件数量 m。四个控制关系分别用信号量 sa、sb、empty1 和 empty2 实施。为遵循先入库者先出库的原则， A、B 零件可以组织成两个循形队列，并增加入库指针 in1 、in2 和出库指针 out1 、out2 来控制顺序。并发程序编制如下：var empty1 ，empty2，full1，full2：semaphore；mutex，sa，sb：semaphore；in1，in2，out1 ，out2 ：integer；buffer1，buffer2：array 0.m-1 of item；empty1：=

21、empty2：=m；sa：=sb：=n；in1：=in2 ：=out1 ：=out2 ：=0；cobeginprocess producerA repeatP(empty1) ；P(sa)；P(mutex)；buffer1in1：=A 零件；in1：=(in1+1) mod m ；V(mutex)；V(sb)；V(full1)；untile false；process producerB repeat P(empty2) ；P(sb)；P(mutex)；Buffer2in2：=B 零件；in2：=(in2+1) mod m ；V(mutex)；V(sa)；V(full2)；untile fal

22、se；process take repeat P(full1) ；P(full2)；P(mutex) ；Take from buffer1out1 and buffer2out2中的 A、B零件；out1 ：=(out1+1) mod m ；out2 ：=(out2+1) mod m ；V(mutex) ；V(empty1) ；V(empty2) ；把 A 和 B 装配成产品；until falsecoend.北大 1997 年同步与互斥题某高校开 网 程并安排上机 ，如果机房共有2m台机器，有2n 个学生 ， 定： (1) 每两个学生分成一 ，并占用一台机器， 同完成上机 ； (2) 当一

23、两个学生到 ，并且机房机器有空 ， 学生才能 机房； (3) 上机 由一名教 ， 完 ，一 学生同 离开机房。 用信号量和 P、V 操作模 上机 程。答 1：var mutex,enter:semaphore;mutex:=1;enter:=0;finish,test,rc,computercounter:integer;finish:=test:=rc:=0;computercounter:=2m;cobeginprocess studenti(i=1，2， )beginP(computercounter);/*申 算机P(mutex);rc:=rc+1;/*学生互斥 数if rc=1 thenV(mutex);P(enter);/*若只来一个学生， 在 enter 上等待elserc:=0; V(mutex);V(enter); /*到达一 中第二个学生， rc 清 0 是为下一组计数用学生进入机房 , 上机实习 ;V(finish);/*P(test);/*V(computercounter);/*告诉老师，实习结束等待老师检查实习结果归还计算机endprocess teacherbeginP(finish);P(finish);/*/*等第一