操作系统试题库

1、200353. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。   Cobegin PROCESS Pi(i=1,2,)       Begin      进入售

2、票厅；购票；退出；End;   Coend(3)若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。此题答案为：售票厅问题解答如下：（1）定义一信号量S，初始值为20。    S>0  S的值表示可继续进入售票厅的人数；    S=0  表示售票厅中已有20名购票者；    S<0  |S|的值为等待进入售票厅中的人数。（2）上框为P(S)，下框为V(S)。（3）S的最大值为20，S的最小值为20N，N为某一时刻需要进入售票厅的

3、最多人数。  此题难度等级为：A200354. 已经系统中有四个缓冲池M0，M1，M2，M3。其容量分别为3、2、3、2，现各缓冲区分别存在0、1、0、2个数据。现同时有四个进程P0、P1、P2、P3分别在各缓冲区间不断地移动数据（见图3.5）。例如，P0进程从M0向M1移动数据。试用信号量及其P、V（或signal，wait）操作及类Pasic/C语言描述各进程之间的同步关系，并给出各信号量的含义和初值。 此题答案为：缓冲池各问题解答如下： （1）互斥信号量和初值M(0)=1，M(1)=1，M(2)=1，M(3)=1， （2）同步信号量  &

4、#160;   Full(i)表示buffer(i)是否有数据；      初值为full(0)=0，full(1)=1，full(2)=0，full(3)=2；      Empty(i)表示buffer(i)是否有空间；      初值为empty(0)=3，empty(1)=1，empty(2)=3，empty(3)=0（3）进程i的程序     Process Proc(i)&#

5、160;          p(full(i);            p(empty(i+1) mod 5);            p(m(i);            move;

6、60;           v(m(i);            v(m(full(i+1) mod 5);            v(empty (i);          此题难度等级为：A200

7、356. 设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值均为0。试问P1、P2并发执行结束后，x=?,y=?,z=? <进程P1>    Y:=1;    Y:=y+2;    V(S1);    Z:=y+1;    P(S2);    Y:=z+y;  进程P2    X:=1;    X:=x+

8、1;    P(S1);    X:=x+y;    V(S2);    Z:=x+z;此题答案为：答：因为P1和P2是两个并发进程，所以进程调度程序调度P1 和P2的顺序是不确定的。  这里不妨假设P1先执行。进程P1执行到语句P(S2)时，S21，进程P1阻塞。此时y=3,z=4。当进程调度程序调度到进程P2时，由于进程P1已执行了V(S1)，进程P2在执行P(S1)时并未阻塞而继续执行，当执行到 V(S2)时，将P1唤醒，然后执行最后一个语句z:=x+z，此时

9、x=5,z=9。当进程P1再次被调度时，继续执行P1的最后一个语句，此时y=12，最终结果是：x=5,y=12,z=9。   如果当P2进程执行到 V(S2)时，将P1唤醒，然后P2进程被中断，此时x=5,y=3,z=4。P1进程开始执行然后执行最后一个语句y:=z+y，此时x=5,y=3,z=7。然后P2进程被调度，执行z:=x+z，此时x=5,y=3,z=12。   如果P2先执行，则执行结果与上面相同。  此题难度等级为：D200362. 在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？此题答案为：答：（1）批处理系

10、统中的作业调度算法有：先来先服务算法（FCFS）、短作业优先算法（SJF）、优先级调度算法（HPF）和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）、短进程优先算法（SPF）、优先级调度算法（HPF）和高响应比优先算法（RF）。（2）分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。（3）实时系统中只设有进程（不设作业调度），其进程调度算法调度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。注意，一个

11、纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序的道数，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序道数，使优先级低的作业呆在外存的后备队列上。  此题难度等级为：A200372. 假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。     表1 进程到达

12、和需要服务时间  进程     到达时间     服务时间   A          0            3   B          2   

13、         6   C          4            4   D          6       

14、     5   E          8            2                      

15、0; 表2 进程的完成时间和周转时间             进程       A      B        C       D      E    

16、;    平均FCFS        完成时间                       周转时间                   带

17、权周转时间       SPF(非抢占) 完成时间                       周转时间                   带权周转时间  &

18、#160;    SPF(抢占)   完成时间                       周转时间                   带权周转时间   &#

19、160;  此题答案为：                        表2 进程的完成时间和周转时间                  进程    

20、     A      B        C       D       E        平均  FCFS          完成时间 &

21、#160;     3      9       13      18       20                   周转时间   

22、    3      7        9      12       12       8.6            带权周转时间   &

23、#160;   1.00   1.17    2.25    2.40    6.00      2.56  SPF(非抢占)   完成时间       3      9       15  

24、0;   20       11                   周转时间       3      7       11    

25、60; 14       3        7.6            带权周转时间      1.00   1.17    1.75    2.80    1.50  

26、0;    1.84  SPF(抢占)     完成时间       3      15      8       20      10          &#

27、160;         周转时间       3      13      4       14       2        7.2   

28、;         带权周转时间      1.00    2.16   1.00    2.80    1.00       1.59  此题难度等级为：A200377. 一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。问：（1）有效的逻辑地址由多少

29、位？（2）有效的物理地址由多少位？此题答案为：答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。6426，则：（1）逻辑地址有16位。（2）物理地址有15位。说明：解此题的关键是要知道在分页管理中，"页"和"块"是一样大小的，这样才知道物理存储器是32KB。  此题难度等级为：B200380. 在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。（1）CPU的利用率为15%，磁盘利用率为95%。（2）CPU的利用率为88%，磁盘利用率为3%。（3）CPU的利用率为13%，磁盘利用率为5%

30、。此题答案为：答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下：（1）可能已出现了抖动现象，应减少系统的进程数。（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。（3）CPU和磁盘的利用率都较低，必须增加并发进程数。  此题难度等级为：A200381. 对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO和LRU替换算法的缺页次数。结果说明了什么？此题答案为：答：首先采用FIFO，当m=3时，缺页次数9，当m=4时，缺页次数10。采用LRU算法，当m=3时，缺页次数10；当m=4时，缺

31、页次数8。结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。  此题难度等级为：C200389. 一个分页存储器的页表存放在内存。（1）若内存的存取周期为0.6ms，则CPU从内存取一条指令（或一个操作数）需多少时间？（2）若使用快表且快表的命中率为75%，则内存的平均存取周期为多少？此题答案为：答：一个分页存储器的页表存放在内存  （1）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需0.6ms×2=1

32、.2ms的时间。  （2）这里家假设访问快表的时间忽略不计，命中快表时，取数只要一次访问，故此时的平均存取周期为0.6ms×0.75+1.2ms×(1-0.75)=0.75ms  此题难度等级为：A200392. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：解：   访问过程中缺页情况（M=3）    

33、;    页面走向                   4   3   2   1   4   3   5   4   3   2   1   5  

34、 最近最长时间未使用的页面                4   3   3   2   4   3   5   4   3   2           

35、60;                           4   3   2   1   4   3   5   4   3   2  

36、1   最近刚使用过的页面              4   3   2   1   4   3   5   4   3   2   1   5       

37、缺页                                                    当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。 &

38、#160;       访问过程中缺页情况（M=4）        页面走向                    4   3   2   1   4   3   5&#

39、160;  4   3   2   1   5   最近最长时间未使用的页面                     4   3   2   1   1   1   5&

40、#160;  4   3                                            4  

41、3   2   1   4   3   5   4   3   2                                

42、          4   3   2   1   4   3   5   4   3   2   1   最近刚使用过的页面             

43、0; 4   3   2   1   4   3   5   4   3   2   1   5        缺页                &

44、#160;                                          当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。   可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。 

45、 此题难度等级为：A200394. 对于一个使用快表的页式虚存，设快表的命中率为70%，内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns，问可接受的最大缺页率是多少？此题答案为：答：设可接受的最大缺页率位p，则有1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns即       0.7+

46、0.6-2p+3200p+12000p=2          15198p=0.7          P=0.000046  此题难度等级为：A200396. 在分页存储管理系统中，存取一次内存的时间是8ns，查询一次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内

47、存。现在开始执行一作业，系统连续对作业的2，4，5，2，7，6，4，8页面的数据进行一次存取，如分别采用FIFO算法和最优页面置换算法，求每种上存取这些数据需要的总时间。此题答案为：答：（1）FIFO         第2页面：208×3         第4页面：208×3         第5页面：208×3 &#

48、160;       第2页面：81         第7页面：208×3         第6页面：208×3         第4页面：208×3         第8页面：208

49、15;3   因此总的时间是（208×3）×7（81）ns(2) OPT         第2页面：208×3         第4页面：208×3         第5页面：208×3         第2页

50、面：81         第7页面：208×3         第6页面：208×3         第4页面：81         第8页面：81   因此总的时间是（208×3）×5（81）×3ns

51、0; 此题难度等级为：A200532. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：解：   访问过程中缺页情况（M=3）        页面走向              

52、;     1   3   2   1   1   3   5   1   3   2   1   5   最近最长时间未使用的页面                1&#

53、160;  3   3   2   1   3   5   1   3   2                             &#

54、160;         1   3   2   2   1   3   5   1   3   2   1   最近刚使用过的页面              1

55、0;  3   2   1   1   3   5   1   3   2   1   5        缺页                 

56、60;                                         当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。         访问过程中缺页情况（M

57、=4）        页面走向                    1   3   2   1   1   3   5   1   3   2 &#

58、160; 1   5   最近最长时间未使用的页面                                 2   2   2   5   5 

59、;  3                                            1   3   3

60、60;  2   1   3   5   1   3   2                                    

61、;       1   3   2   2   1   3   5   1   3   2   1   最近刚使用过的页面               1 &#

62、160; 3   2   1   1   3   5   1   3   2   1   5        缺页                  &

63、#160;                             当M=4时，缺页次数为4次，缺页率为4/12=0.33=33%。   可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。   此题难度等级为：A200592. 在一个请求分页系统中，采用OPT页面置换算法时，假如一个作业的页面走向为4、3

64、、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：解：   访问过程中缺页情况（M=3）        页面走向              4   3   2   1   4 

65、  3   5   4   3   2   1   5   最近最长时间未使用的页面           2   1   1   1   5   4  4/3 3/2 1/2     

66、60;                            3   3   3   4   3   3   5      最近刚使用过的页面  &#

67、160;      4   4   4   4   3   4   4   3   5   5   5        缺页             &

68、#160;                                     当M=3时，缺页次数为7次，缺页率为7/12=0.583=58.3%。         访问过程中缺页情况（M=4）    &

69、#160;   页面走向             4   3   2   1   4   3   5   4   3    2     1   5   最近最长时间未使用的页面 &

70、#160;            1   1   1   5   4  4/3 4/3/2 1/3/2                         

71、;            2   2   2   2   2   5                            

72、60;      3   3   3   4   3   3   2   5       最近刚使用过的页面        4   4   4   4   3   4 &

73、#160; 4   3   2    5     5           缺页                              &

74、#160;                       当M=4时，缺页次数为8次，缺页率为6/12=0.5=50%。   可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。   此题难度等级为：A200593. 在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理

75、内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：解：   访问过程中缺页情况（M=3）        页面走向                   4   3   2   1   4 &

76、#160; 3   5   4   3   2   1   5   最近最长时间未使用的页面                4   3   2   1   4   4   4 &#

77、160; 3   5   5                                       4   3   2 &#

78、160; 1   4   3   3   3   5   2   2   最近刚使用过的页面              4   3   2   1   4   3   5 

79、0; 5   5   2   1   1        缺页                                      &#

80、160;            当M=3时，缺页次数为9次，缺页率为9/12=0.75=75%。         访问过程中缺页情况（M=4）        页面走向                  

81、;  4   3   2   1   4   3   5   4   3   2   1   5   最近最长时间未使用的页面                  

82、0;  4   4   4   3   2   1   5   4   3                             

83、0;              4   3   3   3   2   1   5   4   3   2                &

84、#160;                         4   3   2   2   2   1   5   4   3   2   1 

85、60; 最近刚使用过的页面               4   3   2   1   1   1   5   4   3   2   1   5        缺页&#

86、160;                                                     当M=4时，缺页次数为10次，缺页率为10/12=0.8

87、6=83%。   可见，增加分配给作业的内存块数并不能减少缺页次数，降低缺页率，这种现象叫抖动现象（Belady）。  此题难度等级为：A200594. 利用信号量机制描述前趋关系：S=S1,S2,S3,S4,S5,S6,S7=(S1,S2),(S1,S3),(S2,S4),(S2,S5),(S3,S5),(S3,S6),(S4,S7),(S5,S7),(S6,S7)此题答案为：解：Var a,b,c,d,e,f,g,h,i,:semaphore:=0,0,0,0,0,0,0,0,0,0;      &#

88、160;      Begin     Parbegin       Begin S1;signal(a);signal(b);end;      Begin wait(a);S2;signal(c);signal(d);end;      Begin wait(b);S3;signal(e);signal(f);end;    

89、;  Begin wait(c);S4;signal(g);end;      Begin wait(d);wait(e);S5;signal(h);end;      Begin wait(f);S6;signal(i);end;      Begin wait(g);wait(h);wait(i);S7;end;          &

90、#160;                 Parendend  此题难度等级为：A200596. 利用记录型信号量解决经典同步问题：生产者消费者此题答案为：解：  Var mutex,empty,full:semaphore:=1,n,0;     buffer:array0,.,n-1 of item;     in,out:integer:=

91、0,0;     begin       parbegin         proceducer:           begin             repeat  

92、0;             .              producer an item nextp;                .     

93、         wait(empty);              wait(mutex);              buffer(in):=nextp;        

94、60;     in:=(in+1) mod n;              signal(mutex);              signal(full);           

95、0; until false;           end         consumer:           begin             repeat   

96、           wait(full);              wait(mutex);              nextp:=buffer(out);      

97、60;       out:=(out+1) mod n;              signal(mutex);              signal(empty);         &

98、#160;    consumer the item in nextc;             until false;           end       patend     end  此题难度等级为：A200597. 利用记录型

99、信号量解决经典进程同步问题：读者写者此题答案为：解：  Var rmutex,wmutex:semaphore:=1,1;      Readcount:integer:=0;      Begin        parbegin           Reader:    

100、60;        begin               repeat                wait(rmutex)         &

101、#160;      if Readcount=0 then wait(wmutex);                Readcount:=Readcount+1;                signal(rmutex)  

102、              .                perform read operation;                .  &#

103、160;             wait(rmutex);                Readcount:=Readcount-1;                if Re

104、adcount=0 then signal(wmutex);                signal(rmutex);              until false;            

105、end           Writer:              begin                repeat        

106、          wait(wmutex);                  perform write operation;                  si

107、gnal(wmutex);                until false              end          parend      End  此

108、题难度等级为：A200598. 有一个车间不断取A和B进行装配，每次各取一个。为避免零件锈蚀，遵循先入库者先出库的原则。有两组供应商分别不断供应A和B（每次1个）。为保证齐套和合理库存，当某种零件的数量比另一种零件的数量多得超过n（n<m）时，暂停对数量大的零件的供货，集中补充数量少的零件。  试用Wait和Signal原语正确实现。此题答案为：解： var mutex,emptya,emptyb,fulla,fullb,sa,sb:semaphore:=1,m,m,0,0,n,n;    Begin   &

109、#160;  cobegin        provider_A();        provider_B();        assembiling_shop();      coend      provider_A()    

110、0;   begin          repeat             wait(emptya);             wait(sa);        

111、60;    wait(mutex);             put A into the storehouse;             signal(mutex);             signal(

112、fulla);             signal(sb);          until false;        end      provider_B()        begin 

113、;         repeat             wait(emptyb);             wait(sb);             wai

114、t(mutex);             put B into the storehouse;             signal(mutex);             signal(fullb);   

115、          signal(sa);          until false;        end     asemmbling_shop()        begin     &

116、#160;    repeat             wait(fulla);             wait(fullb);             wait(mutex);  

117、60;          asemmbling A and B;             signal(mutex);             signal(emptya);        

118、     signal(emptyb);          until false;        end    corend    End  此题难度等级为：A200599. 一个主修动物行为学，辅修计算机科学的学生参加了一个课题，调查花果山的猴子能否被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这些

119、猴子就可以攀登着绳索跨过峡谷。只要它们朝着相同的方向，同一时刻可以有多个猴子通过。但是如果在相反方向商同时有猴子通过则会发生死锁（这些猴子卡在绳子中间，假设这些猴子无法在绳索商从另一只猴子身上翻过去）。如果一只猴子想跨越峡谷，他必须看当前是否有别的猴子在逆向通过。请使用信号量写一个避免思索的程序来解决该问题。此题答案为：解：  Begin    var Smutex,Nmutex,SMonkeyCount,NMonkeyCount:Semaphore;        SMonkeyCo

120、unt:=0;        NMonkeyCount:=0;        Smutex:=1;        Nmutex:=1;        mutex:=1;        ParBegin    &

121、#160;     Southi(i=1,2,3,.)          Begin             wait(Smutex);             if SMonkeyCount=0 then wait(mutex)

122、;             SMonkeyCount:=SMonkeyCount+1;             signal(Smutex);             Cross the cordage;   

123、          wait(Smutex);             SMonkeyCount:=SMonkeyCount-1;             if SMonkeyCount=0 then signal(mutex);   &#

124、160;         signal(Smutex);          End          Northi(i=1,2,3,.)          Begin       

125、      wait(Smutex);             if NMonkeyCount=0 then wait(mutex);             NMonkeyCount:=NMonkeyCount+1;       

126、0;     signal(Nmutex);             Cross the cordage;             wait(Nmutex);             NMonkeyC

127、ount:=NMonkeyCount-1;             if NMonkeyCount=0 then signal(mutex);             signal(Nmutex);          End    

128、;    parEnd  End  此题难度等级为：A200600. 设有两个生产者进程A和B和一个销售进程C，它们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品销售。如果不允许同时入库，也不允许同时出库；而且要求生产和销售A产品和B产品数量都满足以下关系：-n<=A的件数-B的件数<=m，其中n，m是正整数。请用信号量机制写出A，B，C三个进程的工作流程。此题答案为：解：  Var difference:integer:=0;   

129、   SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,0,0,0,1;      Begin        parbegin           process A:              begin

130、                repeat                  wait(SAB);               

131、   produce a product A;                  signal(SBA);                  wait(mutex);      &

132、#160;           add the product A to the storehouse;                  signal(mutex);             

133、60;    signal(SA);                  signal(S);                until false;        

134、60;     end            process B:              begin                repeat  

135、;                wait(SBA);                  produce b product B;            

136、60;     signal(SAB);                  wait(mutex);                  add the product B to the storehouse; 

137、                 signal(mutex);                  signal(SB);            

138、60;     signal(S);                until false;            process C:              beg

139、in                repeat                  wait(S);               

140、   if difference<=-n then                     begin                       

141、60;wait(SA);                        wait(mutex);                       

142、; take a product A from storehouse;                        signal(mutex);                  

143、0;     difference:=difference+1;                     end                  elseif difference>

144、=m then                     begin                        wait(SB);   &

145、#160;                    wait(mutex);                        take a product B from storeho

146、use;                        signal(mutex);                        diff

147、erence:=difference-1;                     end                  else        

148、             wait(mutex);                     take a product A or B from storehouse;         &#

149、160;           signal(mutex);                     if (product_type=A) then            

150、0;            begin                            wait(SA);         

151、                   difference:=difference+1;                         end    

152、;                  else                         begin       

153、                     wait(SB);                            difference:=difference-1;                         end