操作系统习题解析.ppt

《操作系统习题解析.ppt》由会员分享，可在线阅读，更多相关《操作系统习题解析.ppt（57页珍藏版）》请在三一办公上搜索。

1、习题选讲与解析,一、选择题1.在计算机系统中配置操作系统的主要目的是（A）。操作系统的主要功能是管理 计算机系统中的（B），其中包括（C）、（D），以及文件和设备。这里的（C）管 理主要是对进程进行管理。A：（1）增强计算机系统的功能；（2）提高系统资源的利用率；（3）提高系统的运行速度；（4）合理组织系统的工作流程，以提高吞吐量。B：（1）程序和数据；（2）进程；（3）资源；（4）作业；（5）软件；（6）硬件。C，D：（1）存储器；（2）虚拟存储器；（3）运算器；（4）处理机；（5）控制器。2.操作系统有多种类型：允许多个用户以交互方式使用计算机的操作系统称为（A）；允许多个用户将若干个作业

2、提交给计算机系统集中处理的操作系统称为（B）；在（C）的控制下，计算机系统能及时处理由过程控制反馈的数据，并做出响应；在IBMPC机上的操作系统称为（D）。A，B，C，D：（1）批处理操作系统；（2）分时操作系统；（3）实时操作系统；（4）微机操作系统；（5）多处理机操作系统。,A:2 B:3 C:4 D:1,A:2 B:1 C:3 D:4,3.在设计分时操作系统时，首先要考虑的是（A）；在设计批处理操作系统时，先要考虑的是（B）；在设计实时操作系统时，首先要考虑的是（C）。A，B，C：（1）灵活性和可适应性；（2）交互性和响应时间；（3）周转时间和系统吞吐量；（4）实时性和可靠性。4.分时系

3、统的响应时间（及时性）主要是根据(A)确定的，而试试系统的响应时间则是由（B）确定的。A，B：（1）时间片大小；（2）用户数目；（3）计算机运行速度；（4）用户所能接受的等待时间；（5）控制对象所能接受的时延；（6）实时调度。5.采用（A）结构时，将OS分成用于实现OS最基本功能的内核和提供各种服务的服务器两个部分。通常，下列模块中必须包含在操作系统内核中的是（B）模块。A：（1）整体式；（2）模块化；（3）层次式；（4）微内核。B：（1）内存分配；（2）中断处理；（3）文件处理；（4）命令处理。,A:4 B:2,A:4 B:5,A:2 B:3 C:4,6.在3.X版本以前的MSDOS是（A）

4、操作系统，Windows95是（B）操作系统，WindowsXP是（C）操作系统，它们都是由（D）开发的。A，B，C：（1）单用户单任务；（2）单用户多任务；（3）多用户单任务；（4）多用户多任务。D：（1）IBM公司；（2）Microsoft公司；（3）Microsoft和IBM联合；（4）Bell实验室；7.下面8个系统中，必须是实时操作系统的有（）A计算机辅助设计系统；B 航空定票系统；C 过程控制系统；D 机器翻译系统；E 办公自动化系统；F 计算机激光照排系统；G情报检索系统；H导弹的制导系统二、简答题在操作系统中实现虚拟的关键技术是什么？并加以说明。操作系统中所谓的”虚拟“，是指通

5、过某种技术把一个物理实体变为若干个逻辑上的对应物，相应的用于实现虚拟的技术称为虚拟技术。在操作系统中利用了多种虚拟技术分别用来实现虚拟处理机、虚拟内存、虚拟外设和虚拟信道等。虚拟的实现主要是通过分时技术，例如，多道程序系统中，通过分时技术来实现虚拟处理机；将一台物理处理机虚拟为多台逻辑上的处理机，是靠多道程序分时地使用同一台物理处理机来实现的。微观上，该处理机在每一时刻只运行一道程序，它们分时地运行；然而在宏观上，系统中确有几道程序在同时运行，从而给用户的感觉是系统中同时同时有多台处理机在为其中的每一道程序服务，显然用户所感觉到的处理机并不实际存在。,A:1 B:2 C:4 D:2,ABCGH

6、,试从交互性、及时性以及可靠性三个方面，比较分时系统与实时系统。P11,已知一个求值公式（A2+3B）/(B+5A),若A,B已赋值，试画出该公式求值过程的前趋图，并用信号量解决公式的求解过程。,S1:x1=A*A,S2:x2=3*B,S3:x3=5*A,S4:x4=x1+x2,S5:x5=B+x3,S6:x6=x4/x5,开始,结束,struct semaphore a,b,c,d,e,=0,0,0,0,0;cobegin S1;V(a);S2;V(b);S3;V(c);P(a);P(b);S4;V(d)P(c);S5;V(e);P(d);P(e);S6);coend,a,c,b,d,e,吃

7、水果问题问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用P、V操作实现四人正确活动的程序。,void son(void)while(TRUE)P(so);get an orange;V(s);eat an orange;void daught(void)while(TRUE)P(sp);get an apple;V(s);eat an apple;coend,struct semaphore s

8、,sp,so=1,0,0;cobegin void father(void)while(TRUE)have an apple;P(s);put an apple;V(sp);void mother(void)while(TRUE)have an orange;P(s);put an orange;V(so);,Plate 1爸私 applempty 盘中无苹果 1女私applefull盘中有苹果0妈私orangempty无桔子1儿私orangefull有桔子0,爸p(plate);P(applempty);放苹果；V(applefull);V(plate);,女p(applefull);P(p

9、late);取苹果；V(applempty);,儿p(orangefull);P(plate);取桔子；V(plate);V(orangempty);,母p(plate);P(orangempty);放桔子；V(orangefull);V(plate);,mutex 盘子a表示爸爸是否在盘中放入苹果b 女儿是否可吃苹果c表示妈妈是否在盘中放桔子d为儿子是否可吃桔子,p(a);p(mutex);放入苹果；v(b);p(b);取走苹果；v(a);v(mutex);p(c);p(mutex);放入桔子；v(d);p(d);取走桔子;v(c);v(mutex),初值？,mutex 盘子1appfull

10、苹果个数0avail 盘中空位个数初值为norgfull 桔子的个数0,dadP(avail);P(mutex);put an apple;V(appfull);V(mutex);,momP(avail);P(mutex);put an orange;V(orgfull);V(mutex);,sonP(orgfull);P(mutex);get an apple;V(avail);V(mutex);,dauP(appfull);P(mutex);get an apple;V(avail);V(mutex);,注意初值avail的设置，n不正确,BeginP(apple);P(pan)V(app

11、le);V(pan);P(orange);P(pan);V(orange);V(pan);,P(pan);P(apple);V(apple);V(apple);V(pan);P(pan);P(orange);V(orange);V(pan);,四人动作未分开，apple和orange变量的含义不明确,empty=1;apple=0;orange=0;,S1：parbegin P(empty);count:=count+1;V(apple);do sth elseparend,S2：parbegin P(empty);count:=count+1;V(orange);do sth elsepar

12、end,S3：parbegin P(orange);count:=count-1;If(count=0)V(empty);do sth elseparend,S4：parbegin P(apple);count:=count-1;If(count=0)V(empty);do sth elseparend,父,子,女,母,count=0;,struct semphore plate,platempty,orange,apple=1,1,0,0;,cobeginmother(void)beginP(platempty);P(plate);桔子放入盘中；V(orange)；V(plate)；end,

13、son(void)beginP(orange);P(plate);吃桔子；V(platempty)；V(plate)；end,mother(void)beginP(apple);P(plate);吃苹果；V(platempty)；V(plate)；endcoend,father(void)beginP(platempty);P(plate);放苹果；V(apple)；V(plate)；end,设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆 上下乘客 正常行车 关车门 到站停车 售票 开车门 上下乘客 在汽车不断到站，停车，行驶过程中，这两个活动的同步关系。,struct sem

14、aphore s1,s2=0,0;cobegin void driver(void)while(TRUE)p(s2);启动车辆;正常行车;到站停车;V(s1);,void conductor(void)while(TRUE)上、下乘客；关车门；V(s2);售票；P(s1);开车门;上、下乘客;coend,S1是否可以开车门S2是否可以发动车辆,struct semaphore s1,s2=1,0;cobegin void driver(void)while(TRUE)P(s2);启动车辆;正常行车;到站停车;V(s1);void conductor(void)while(TRUE)P(s1);

15、开车门;上、下乘客;关车门;V(s2);售票；coend,司机-售票员问题另解：,S1是否可以开车门1S2是否可以发动车辆0,1.在某系统中，三个进程共享四台设备资源，这些资源一次只能一台地为进程服务和释放，每个进程最多需要二台设备资源，试问在系统中是否会产生死锁？,答：不会。若所有的资源都被占用，而占用者又都不满足必须的全部资源，此时就有一个或几个进程无限期地等待更多的资源，系统就会出现死锁。本题中若4 台设备资源都被占用，则其中一定有一个进程获得2台设备资源(满足其最大的需求量)，这个进程必然会在有限的时间内完成其工作，并释放其所占用的2台资源，这样也就能满足其它二进程对设备资源的要求，继

16、续完成它们各自的工作。,某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。,应首先考虑清楚本题需要几个进程。从井中取水后向缸中倒水此为连续动作，可算同一进程，从缸中取水为另一进程。在考虑信号量，有关互斥的资源有水井（一次仅一个水桶进出），水缸（一次如水取水时均为一桶），分别为之设置信号量mutex1,mutex2控制互斥；另有同步问题存在：三个水桶无论从井中取水还是入出水缸都是一次一个，应为之设信号量cou

17、nt，抢不到水桶的进程只好等待；还有水缸满时，不可入水，设信号量empty,控制入水量，水缸空时不可出水，设信号量full,控制出水量。,mutex1:=1;mutex2:=1;empty:=10;full:=0;count:=3;cobegin 小和尚打水:beginL1:P(empty);P(count);P(mutex1);从井中取水；V(mutex1);P(mutex2);送入水缸；V(mutex2);V(count);V(full);Goto L1:end;,老和尚取水：begin L2:P(full);P(count);P(mutex2);从缸中取水；V(mutex2);V(emp

18、ty);V(count);Goto L2 end;coend.,在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M（同时允许两辆自行车停留），可供两辆自行车已从两端进入小路情况下错车使用，如图所示。试设计一个算法来使来往的自行车均可顺利通过。,M,K,S,T,L,南开大学,天津大学,本题是一个利用P、V操作控制一个任务流程的问题。这类问题较常见。分析的时候主要是列出所需控制的对象，以及其控制关系，对于本题来说，所需控制对象，以及其控制关系。对于本题来说，所需控制的对象是由T到L这一段路的使用，由S到K这一段路的使用以及M这个“安全

19、岛”的使用。路段T至L及路段S至K同时只允许一个进程（一辆自行车）使用，对于它们，我们可以分别用3个信号量来管理。最后，由于同时最多只能由一个方向的一辆自行车通过（两个方向共两辆自行车），因此，对每个方向上的自行车还应用一个信号量来控制对临界资源的访问。,解答：对于两个方向的自行车，我们用两个进程bikeT2N和bikeN2T来表示。BikeT2N为从天津大学向南开大学行驶的自行车，bikeN2T为从南开大学向天津大学行驶的自行车。其控制流程如下：BEGIN Integer T2N,N2T，L，M，K；T2N：1；N2T：1；L：1；K：1；M：2;BEGINPROCEDURE bikeT2N

20、()P(T2N)；P（L）；go through T to L;P(M);Go into M;V(L);P(K);go through K to S;V(M);V(K);V(T2N);,PROCEDURE bikeN2T()P(N2T);P(K);go through S to K;P(M);go into M;V(K);P(L);go through L to T;V(M);V(L);V(N2T);END,某工厂有两个生产车间，两个生产车间分别生产A，B两种零件，装配车间的任务是把A，B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1，F2上，F1存放零件

21、A，F2存放零件B，F1和F2的容量均为可以存放10个零件。装配工人每次从货架上取一个A零件和一个B零件然后组装成产品。请用PV操作进行正确管理。,该题是生产者消费者的变形，可以认为一个消费者（装配工人）同两个生产者（A，B车间）互斥试用两个缓冲区（F1，F2），可设mutex1，mutex2（初值为1）控制进程对F1，F2的互斥操作，另设empty1，empty2（初值均为10），full1，full2（初值均为0）。过程如下：,Cobegin A车间：Begin生产一个产品；P（empty1）；P（mutex1）；放入F1；V（mutex1）；V（full）；EndB车间Begin生产一个

22、产品；P(empty2);P(mutex2);放入F2；V(mutex2);V(full2);End,装配工人：BeginP(full1);P(full2);P(mutex1);P(mutex2);取A和B；V(mutex1);V(mutex2);V(empty1);V(empty2);End,假定系统中有五个进程P0、P1、P2、P3、P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图请找出该表中T0时刻以后存在的安全序列（至少2种）,资源情况,进程,AllocationA B C,MaxA B C,NeedA B C,AvailableA B

23、C,P0P1P2P3P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,6 0 0,0 1 1,4 3 1,3 3 2,7 5 3,（中国科学院计算技术研究所1999年试题）一系统具有150个存储单元，在T0时刻下表所示分配给3个进程。进程 Maximum demand Current allocation P1 70 25 P2 60 40 P3 60 45对下列请求应用银行家算法分别分析判定是否安全？（1）第4个进程P4到达，最大需求60个存储单元，当前请求分配25个单元；（2）第4个进程P4到达，最大需

24、求50个存储单元，当前请求分配35个单元；如果是安全的，情给出一个可能的安全执行序列；如果是不安全的，请说明原因。,该题的两个问题都是问当P4当前的需求是否可以满足。对于P4来说关键不在其最大的需求量是多少，而是其当前需求量是多少；系统在此时剩余资源数是40个；（1）P4的最大需求量为60，当前请求分配25个，计算是否安全，应在假设分配之后看是否找到安全序列。结果是至少可以找到一个安全序列，答案不唯一。（2）P4得到35个单元后，系统剩余资源数为5，此时4个进程的剩余量需求量均无法满足，为不安全状态，因为找不到安全序列。,设系统中有3种类型的资源（A，B，C)和5个进程（P1,P2,P3,P4

25、,P5)，A资源的数量为17，B资源的数量为5，C资源的数量为20，在T0时刻系统状态见下表。进程 最大资源数量 已分配资源数量 剩余资源数量 A B C A B C A B C P1 5 5 9 2 1 2 2 3 3 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4系统采用银行家算法实施死锁避免策略。（1）T0时刻是否为安全状态？若是，请给出安全序列（2）在T0时刻若进程P4请求（0，3，4），是否能实施资源分配？为什么？（3）在（2）的基础上，若进程P4请求资源（2，0，1）是否能实施资源分配？为什么？（4）在（3）

26、的基础上，若进程P1请求资源（0，2，0），是否能实施分配？为什么？,判断是否为安全状态，关键在于能否找到一个安全序列。这与进程剩余需求量有关，列表如下,资源情况,进程,NeedA B C,workA B C,WorkAllocationA B C,AllocationA B C,P4P2P3P5P1,finish,2 3 3 2 2 1 2 0 4 4 3 7 true,4 3 7 1 3 4 4 0 2 8 3 9 true,8 3 9 0 0 6 4 0 5 12 3 14 true,12 3 14 1 1 0 3 1 4 15 4 18 true,15 4 18 3 4 7 2 1 2

27、 17 5 20 true,进程 最大资源数量 已分配资源数量 还需要资源数量 剩余资源数量 A B C A B C A B C A B C P1 5 5 9 2 1 2 3 4 7 2 3 3 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 2 0 4 2 2 1 P5 4 2 4 3 1 4 1 1 0,（2）Request4（0，3，4）Available（2，3，3），系统不能给予满足。（3）a：Request4（2，0，1）Need4（2，2，1）b：Request4（2，0，1）Available（2，3，3）c：系统试探将R

28、equest4（2，0，1）分配出去并修改数据结构的值,进程 最大资源数量 已分配资源数量 还需要资源数量 剩余资源数量 A B C A B C A B C A B C P1 5 5 9 2 1 2 3 4 7 0 3 2 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 4 0 5 0 2 0 P5 4 2 4 3 1 4 1 1 0,此时可以寻找到安全序列,此次请求可以分配（4）a：Request1（0，2，0）Available(0,3,2)b:Request1(0,2,0)Need(3,4,7)c:试探分配，此时系统中的情况如下表所

29、示：,进程 最大资源数量 已分配资源数量 还需要资源数量 剩余资源数量 A B C A B C A B C A B C P1 5 5 9 2 3 2 3 2 7 0 1 2 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 4 0 5 0 2 0 P5 4 2 4 3 1 4 1 1 0,d:剩余资源不足，所以不存在安全序列。此次分配不予满足。,试化简图中的进程资源图，并利用死锁定理给出相应的结论,P0,P1,P2,P3,P4,R0,R1,R2,R3,R4,R1,R2,R3,R4,R0,P0,P1,P2,P3,P4,根据死锁定理，资源分配图

30、不能完全化简，系统中潜在死锁，产生死锁的进程是P1，P3，P4,R1,R2,R3,R4,化简如下所示的资源分配图，并判断系统中是否存在死锁,R2,P1,P4,P2,P3,R1,R3,一个四道作业的操作系统中，设在一段时间内先后到达6个作业，它们的提交时间和运行时间见表,作业号 提交时间 运行时间,JOB1JOB2JOB3JOB4JOB5JOB6,8:008:208:258:308:358:40,60352025 510,系统采用短作业优先的调度算法，作业被调度进入运行后不再退出，但当一作业进入运行时，可以调整运行的优先次序。1 按照所选择的调度算法，请分别给出上述6个作业的执行时间次序2 计算

31、在上述调度算法下作业的平均周转时间,作业号 提交时间 运行时间 开始时刻 完成时刻 周转时间,JOB1JOB2JOB3JOB4JOB5JOB6,（时）,（分钟）,（时）,（时）,（分钟）,8：00 60 8：00 9：00 608：20 35 10：00 10：35 1358：25 20 9：15 9：35 708：30 25 9：35 10：00 908：35 5 9：00 9：05 308：40 10 9：05 9：15 35,作业号 提交时间 运行时间,JOB1JOB2JOB3JOB4JOB5JOB6,8:008:208:258:308:358:40,60352025 510,一个具有两

32、道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，如下表的作业序列（表中所有作业优先数即为进程优先数，数值越小优先级越高）。1 列出所有作业进入内存时间及结束时间2 计算平均周转时间,作业的执行时间,作业名 到达时间 估计运算时间 优先数,A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6,作业名 到达时间 估计运算时间 优先数,A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6,各作业进入内存的时间和结束时间见表,作业进入内存的时间和结束

33、时间,作业名 进入内存时间 结束时间,ABCD,10：0010：2011：1010：50,11：1010：5012：0012：20,2 各作业执行时间的周转时间为作业A 70分钟作业B 30分钟作业C 90分钟作业D 90分钟作业的平均周转时间为T70（min）,有5个批处理作业（A、B、C、D、E）几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8、10分钟，它们的优先数分别为1，2，3，4，5（1为最低优先级），对下面的每种调度算法，分别计算作业的平均周转时间。1 最高优先级先2 时间片轮转（时间片为2分钟）3 FIFO（作业到达顺序为C、D、B、E、A）4 短作业优先,(1)对

34、最高优先级优先算法,E D C B A,0 10 18 24 28 30,t,平均周转时间110/5=22分钟,（2）对时间片轮转算法,A B C D E B C D F C D E D E E,0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30,平均周转时间=90/5=18,(3)对FIFO算法,C D B E A,0 6 14 18 28 30,（4）对短作业优先算法,0 6 14 18 28 30,A B C D E,平均周转时间96/5=19.2,平均周转时间70/5=14,在一个批处理系统中，有两个作业进程。有一作业序列，其到达时间及估计运行时间如下

35、表,作业 到达时间 估计运行时间（分钟）,10：00 352 10：10 303 10：15 454 10：20 205 10：30 30,系统采用最高响应比优先的作业调度算法（响应比等待时间/估计运行时间）。作业进程的调度采用短作业优先的抢占调度算法。1、列出各作业的执行时间2、计算这批作业的平均周转时间,作业 到达时间 估计运行时间（分钟）,10：00 352 10：10 303 10：15 454 10：20 205 10：30 30,各作业的执行时间序列为：作业10:00-10:10,11:00-11:25(结束)作业210:10-10:40(结束)作业311:55-12:40(结束)

36、作业410:40-11:00(结束)作业511:25-11:55(结束)各作业执行的周转时间为：作业：分钟；作业：分钟；作业：分钟；作业：分钟；作业：分钟。平均周转时间为：分钟。,解2：各作业的执行时间序列为：75分钟,某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选课（m，n均大于等于1），规定：1，每两个学生组成一组，各占一台机器，协同完成上机实习；2，只有一组两个学生到齐，并且此时机房有空闲机器时，该组学生才能进入机房；3，上机实习由一名教师检查，检查完毕，一组学生同时离开机房试用P、V操纵模拟上机实习过程。,解答：上机实习过程如下：BEGINInteger

37、 student,puter,enter,finish,check;Student:=0;Computer:=2m;Enter:=0;Finish:=0;Check:=0;COBEGINStudent:BEGIN V(student);表示有学生到达 P(puter);获取一台计算机 P(enter);等待允许进入 Do it with parter;V(finish);表示实习完成 P(check);等待教师检查 V(puter);释放计算机资源END,Teacher:BEGINL1:P(finished);等待学生实习完成 P(finished);等待另一学生实习完成 Check the

38、work;V(check);表示检查完成 V(check);表示检查完成 Goto L1；ENDMonitor：BEGIN L2：P（student）；等待学生到达 P（student）；等待另一学生到达 V（enter）；允许学生进入 V（enter）；允许学生进入ENDCOEND,3.仅涉及一个进程的死锁有可能存在吗?为什么?不可能。这可直接从死锁的必要条件之一“请求和保持(部分分配)”可得。4.设计一个不可能出现饥饿现象和死锁的过河算法。答：利用红绿灯和一个计数器。当有人开始过河时，计数器增值，当过河后该计数器减值，（但任何一个方向都有时间限制，如分钟），仅当计数器值为0时，才开绿灯既允

39、许另一方向的人过河。5.设系统中仅有一类独占资源,进程一次只能申请一个资源.系统中多个进程竞争该类资源.试判断下述那些情况会发生死锁?为什么?1,资源数为4,进程数为3,每个进程最多需要2个资源2,资源数为6,进程数为2,每个进程最多需要4个资源3,资源数为8,进程数为3,每个进程最多需要3个资源4,资源数为20,进程数为8,每个进程最多需要2,1.什么是虚拟存储器？它有哪些基本特征？答：在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。实际上虚拟存储器是为扩大主存而采用的一种设计技巧，虚拟存储器的容量于主存大小没有直接关系，

40、而受限于计算机的地址结构及可用的辅助存储器的容量。虚拟存储器有以下特征：1、多次性；2、对换性；3、虚拟性；,2.考虑下面的存储访问序列，该程序大小为460个字：10，11，104，170，73，309，185，245，246，434，458，364 设页面大小是100字，请给出该访问序列的页面走向。又设该程序基本可用内存是200字，采用FIFO置换算法，求出其缺页率。如果采用LRU置换算法，缺页率是多少？,答：页面走向是0、0、1、1、0、3、1、2、2、4、4、3,FIFO算法：,0 0 1 1 0 3 1 2 2 4 4 3,1 1 1 1 1 2 2 2 2 3,0 0 0 0 0 3

41、 3 3 3 4 4 4,缺 缺 缺 缺 缺 缺,LRU算法：,0 0 1 1 0 3 1 2 2 4 4 3,1 1 0 3 1 2 2 4 4 3,0 0 0 0 1 0 3 1 1 2 2 4,缺 缺 缺 缺 缺 缺 缺,6/1250,7/1258.3,3.考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6；当内存块数量分别为3和5时，试问LRU，FIFO，OPT三种置换算法的缺页次数各是多少？（初始所有内存块都是空的）三页：FIFO 16次 LRU 15次 OPT 11次五页：FIFO 10次 LRU 8次 OPT 7次,段表始址 段表长度

42、,控制寄存器,0 430,段号 位移量W,649,段号 基址 段长,物理地址,0,1,2,3,4,219,2300,90,1327,1952,600,14,100,580,96,段号,基址,长度,0,1,2,3,4,219,2300,90,1327,1952,600,14,100,580,96,已知段表如下所示,下述逻辑地址的物理地址是什么？并画出基本分段的地址变换过程（0，430）、（1，10）、（1，11），（2，500），（3，400），（4，112）,（0，430）的物理地址是649（1，10）的物理地址是2310（1，11）的物理地址是2311（2，500）地址非法，产生越界中断（3

43、，400）的物理地址是1727（4，112）地址非法，产生越界中断,5.进程资源的使用情况和可用情况如下表所示，请画出资源分配图，并判断该状态是否会产生死锁？进程 当前分配数 待分配的请求 可用资源 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 0 1 1 0 0 0 0 P2 3 1 0 0 0 0 P3 1 3 0 0 0 1 P4 0 1 1 0 1 0,P1,P2,P3,P4,R1,R2,R3,P1,P2,P3,P4,R1,R2,R3,P1,P2,P3,P4,R1,R2,R3,P1,P2,P3,P4,R1,R2,R3,P1,P2,P3,P4,R1,R2,R3,根据

44、死锁定理，资源分配图可完全化简系统中不存在死锁,6.吸烟者问题：三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴、供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把另外两样东西放在桌子上，唤醒另一个吸烟者。试采用信号量和P、V操作编写他们同步工作的程序。,烟草,1,2,3,烟草、纸、火柴,香烟提供者,a b c,a,b,c,a代表烟草、b代表纸，c代表火柴；我们设初始状态为老板先出售b，c

45、（即a的初值为0；b，c初值为1）设mutex1，mutex2，mutex3（初值均为1）作为互斥信号量，用来控制对三组变量（b，c），（a，c），（a，b）的访问；再设信号量buy1，buy2，buy3，sale用来吸烟者同老板之间的同步控制，其中buy1初值为1，其它初值为0；因此我们设置的初始状态为老板可向第一个对列出售他们需要的两种物品,struct semaphore mutex1，mutex2，mutex3，buy1，buy2，buy3，sale1，1，1，1，0，0，0；int a，b，c0，1，1；,P1：Begin P(buy1);P(mutex1);b:=b-1;c:=c-

46、1;V(mutex1);吸烟；V（sale）；End,P2：BeginP(buy2);P(mutex2);a:=a-1;c:=c-1;V(mutex2);吸烟；V（sale）；End,P3：BeginP(buy3);P(mutex3);a:=a-1;b:=b-1;V(mutex3);吸烟；V（sale）；End,P4：Cobegin begin P(sale);P(mutex1);b:=b+1;c:=c+1;V(mutex1);V（buy1）；End begin P（sale）；P(mutex2)a:=a+1;c:=c+1;V(mutex2);V(buy2);end,beginP(sale);

47、P(mutex3);a:=a+1;b:=b+1;V(mutex3);V(buy3);End;Cobegin,7.某多道程序设计系统供用户使用的主存为100KB，磁带机2台，打印机1台。采用可变分区内存管理，采用静态分配外围设备，忽略用户作用I/O时间，现有作业序列如下：作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU时间。现求（1）作业被调度的先后次序？（2）全部作业运行结束的时间？（3）作业平均周转时间为多少？,作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机需求,1 8：00 25分钟 15KB 1 1 2 8：20 10分钟

48、 30KB 0 1 3 8：20 20分钟 60KB 1 0 4 8：30 20分钟 20KB 1 0 5 8：35 15分钟 10KB 1 1,作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机需求,1 8：00 25分钟 15KB 1 1 2 8：20 10分钟 30KB 0 1 3 8：20 20分钟 60KB 1 0 4 8：30 20分钟 20KB 1 0 5 8：35 15分钟 10KB 1 1,0 15K 75K100K-1,剩余磁带 打印机 完成,8：20作业2到达但因缺少打印机无法装入内存；等待,1 0(1)8：30,8：00作业1进入内存占用15K内存,8：20

49、作业3到达满足资源要求装入内存 0 0占用60K和磁带机1个 作业1已经运行了20分钟作业1剩余5分钟，和作业3共享CPU时间，因此作业1还需10分钟（作业3运行5分钟）结束8：30作业1完成，释放内存及资源 1 1,8:30作业4到达资源满足装入内存 0 1作业2因系统剩余内存不足仍无法装入内存因此是作业3和4同时在内存作业3需还有15分钟，但与作业4平分cpu时间因此需要30分钟可完成(其中作业4占15分钟）因此作业3完成时间是9：00(3)9：008:35作业5到达因磁带机无法满足等待9:00作业3释放60K和磁带机1 剩余资源为 1 1,0 15K 75K100K-1,作业号 进入输入

50、井时间 运行时间 主存需求量 磁带需求 打印机需求,1 8：00 25分钟 15KB 1 1 2 8：20 10分钟 30KB 0 1 3 8：20 20分钟 60KB 1 0 4 8：30 20分钟 20KB 1 0 5 8：35 15分钟 10KB 1 1,0 15K 75K100K-1,剩余磁带 打印机 完成,9:00作业3释放60K和磁带机1 剩余资源为 1 1作业2先于作业5到达，系统满足作业2需求讲作业2装入内存 1 0作业5因打印机资源不足无法装入内存作业4（还剩5分钟）和作业2共享内存作业4还需10分钟结束此时作业2运行了（5分钟）(4)9:10,0 75K100K-1,30K