操作系统学位考复习

《操作系统学位考复习》由会员分享，可在线阅读，更多相关《操作系统学位考复习（23页珍藏版）》请在装配图网上搜索。

1、一、填空题1. 分时操作系统的特征：多路性、交互性、独占性。2. 信号量的物理意义：当信号量0时，表示 可用资源的数目。当信号量（逻辑上）0时，其绝对值表示 因请求该资源而被阻塞的进程数目。3. 进程系统中，各进程之间逻辑上的相互制约关系称为进程同步。4. 在多道程序系统中，进程之间存在着两种不同的制约关系 同步和互斥。同步：是指进程间具有一定的逻辑关系。互斥：进程间在使用共享资源方面的约束关系。5. 将作业地址空间中的逻辑地址转换为储存中的物理地址称为 地址重定位（映射，地址变换）6. 分区管理中，采用首次适应分配算法时，应将空闲区按 地址递增次序排队，登记在空闲区表中。7. 在请求页式管理

2、中，常用的页面淘汰算法有：最佳置换算法：选择淘汰永不再使用或在最长时间不再被访问的页面；先进先出（FIFO）算法：选择淘汰最先进入存的页面，即在存中逗留时间最长的页面；最近最久未使用算法：选择淘汰在离当前时刻最近一段时间使用最少的页面。8. 实时操作系统与分时操作系统的主要区别：及时性、高可靠性9. 临界资源的概念：一次仅允许一个进程访问的资源。临界区：指进程中访问临界资源的那段程序代码。若一个进程已进入临界区，其他欲进入临界区的进程必须等待。10. 程序顺序执行时有三个特点：顺序性、封闭性、可再线性。11. 分区分配中的存储保护通常采用界线寄存器和起址线长寄存器。12. 页表表目的主要容包括

3、：页号和块号。13. 在请求页式存储管理中采用FIFO（先进先出）页面淘汰算法，当分配的页面数增加时，缺页中断的页数 可能增加也可能减少。14. 采用多道程序设计技术能充分的发挥 CPU 与外设并行工作的能力。15. 进程在运行过程中有三种基本状态： 运行状态、就绪状态、等待状态。16. 将进程的 PCB 在一起，就形成了进程队列。17. 由n个进程共享同一个临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化围是 +1 -（n-1） 18. 把逻辑地址转化为物理地址，称为地址映射（重定位）。19. 静态重定位是在程序装入存时进行。动态重定位是在程序执行时进行。20. 最短寻道

4、时间优先算法 是指选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。21. 操作系统的主要性能参数指标有吞吐量和利用率。吞吐量 是指单位时间系统处理的作业量。利用率 是指 在一个给定时间，系统的一个指定成分被使用的时间比例。22. 进程主要有程序段、数据段、 PCB 三部分容组成。其中PCB是进程存在的唯一标志，而程序段部分可以为其他进程共享。23. 用PV操作管理临界区时，任何一个进程在进入临界区之前应调用 P 操作，退出临界区时应调用 V 操作。24. 在一个单处理机系统中，若有5个用户进程，且假设当前时刻为用户态，则处于就绪状态的用户进程，最多有 4个，最少有 0 个。25. 重

5、定位的方式有：静态重定位、动态重定位。26. 在断页式存储管理系统中，每道程序都有一个断表和一组页表27. 从用户的观点出发所看到的文件的组织形式称为文件的逻辑结构。从实现的观点出发文件在外存上的有效组织形式称为文件的物理结构。28. 操作系统有四个模块组成：处理机管理功能，存储器管理功能，设备管理功能，文件管理功能。29. 进程是程序的一次执行。二、选择题1. 从用户的观点看，操作系统是A 。A 用户与计算机之间的接口B 控制和管理计算机资源的软件C 合理地组织计算机工作流程的软件D 由若干层次的程序按一定的结构组成的有机体2. 所谓 B 是指将一个以上的作业放入主存，并且同时处于运行状态，

6、这些作业共享处理机的时间和外围设备等其他资源。A多重处理B多道程序设计C实进处理D共行执行3. 如果分时操作系统的时间片一定，那么 B ，则响应时间越长。A 用户数越少B 用户数越多C 存越少D 存越多4. 若把操作系统看作计算机系统资源的管理者，下列的D 不属于操作系统所管理的资源。A 程序B 存C CPUD 中断5. 在分时操作系统环境下运行的作业通常称为 C 。A 后台作业B 长作业C 终端型作业D 批量型作业6. 作业的四种状态：提交，后备，运行，完成。作业调度程序从处于 D 状态的队列中选取适当的作业投入运行。A 运行B 提交C 完成D 后备7. OS是对 C 进行管理的。A 软件B

7、 硬件C 计算机资源D 应用程序8. 用户使用操作系统通常有三种手段，它们是终端命令、系统调用命令和 C 。A 计算机高级指令B 宏命令C 作业控制语言D 汇编语言9. 既考虑作业等待时间，又考虑作业执行时间的调度算法是 A 。A 响应比高者优先B 短作业优先C 优先级调度D 先来先服务10. 分时操作系统通常采用 B 策略为用户服务。A 可靠性和灵活性B 时间片轮转C 时间片加权分配D 短作业优先11. 在进程管理中，当 C 时，进程从阻塞状态变为就绪状态。A 进程被进程调度程序选中B 等待某一事件C 等待的事件发生D 时间片用完12. P、V操作是A 。A 两条低级进程通信原语B 两组不同

8、的机器指令C 两条系统调用命令D 两条高级进程通信原语1. 存储管理2. 多道程序3. 时间片轮转4. 等待时间发生时5. 有一个等待。？6. 就绪状态（时间片用空）7. PCB8. 作业控制块9. 周转时间10. 处理机管理进程调度11. 利用率12. 通道？中是从中断机构发展起的13. 执行状态，就绪运行被进程调度程序选中14. 短作业优先15. OS是针对16. PV操作是两条低级通信原语17. OS允许在一台主机的多个终端18. 实时操作作出响应三、解析题1.分时操作系统和实时操作系统进行比较。(1)多路性 实时信息处理系统与分时系统一样具有多路性。系统按分时原则为多个终端用户服务；而

9、对实时控制系统，其多路性则主要表现在经常对多路的现场信息进行采集以及对多个对象或多个执行机构进行控制。(2)独立性 实时信息处理系统与分时系统一样具有独立性。每个终端用户在向实时系统提出服务请求时，是彼此独立地操作，互不干扰；而在实时控制系统息的采集和对对象的控制，也都是彼此互不干扰。(3)及时性 实时信息系统对实时性的要求与分时系统类似，都是以人所能接受的等待时间来确定；而实时控制系统的及时性，则是以控制对象所要求的开始截止时间或完成截止时间来确定的，一般为秒级、百毫秒级，甚至有的要低于100微秒。(4)交互性 实时信息处理系统虽也具有交互性，但这里人与系统的交互，仅限于访问系统中某些特定的

10、专用服务程序。它不象分时系统那样能向终端用户提供数据处理服务、资源共享等服务。(5)可靠性 分时系统虽然也要求系统可靠，相比之下，实时系统则要求系统高度可靠。因为任何差错都可能带来巨大的经济损失、甚至无法预料的灾难性后果。因此，在实时系统中，往往都采取了多级容错措施，来保证系统及数据的安全。2.进程与程序的主要区别是什么?答:1. 进程是一次执行的过程,是动态概念;程序是一组有序指令的集合,是静态概念 2. 一个进程可执行一个或多个程序;反之,一个程序也可由一个或多个进程来完成 3.程序可永远保存,进程具有生命周期. 4.进程是一个独立的运行单位,是提供资源利用和资源分配的独立单位,进程具有独

11、立性,但有时有些进程之间又具有互相制约的关系,而程序不具有这种特性.或:（试从动态性、并发性和独立性上比较进程和程序）？答:（1）动态性：进程既然是进程实体的执行过程，因此，动态性是进程最基本的特性。动态性还表现为：“它由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤消而消亡”。可见，进程有一定的生命期。而程序只是一组有序指令的集合，并存放在某种介质上，本身并无运动的含义，因此，程序是个静态实体。（2）并发性：所谓进程的并发，指的是多个进程实体，同存于存中，能在一段时间同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也正是为了使其程序能和其它进程的程序并发

12、执行，而程序是无法并发执行的。（3）独立性：进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位。凡未建立进程的程序，都不能作为作为一个独立的单位参加运行3. 文件管理系统为什么要设置打开文件、关闭文件命令？操作系统需要大量的用户文件，而访问一个文件需要查询目录，有时甚至需要多次查询目录。由于文件目录与文件一起放置在辅存上，当存许文件时，必须到辅存上读取文件目录信息，从中获得文件存放的地址，然后再去存取文件。这样一来，文件信息的存取将花费很很多时间。如果将整个文件容放入虽然可以提高读取速度，但这要占用大量主存空间，显然这也是不可取的。实际上在一段时间，使用文件的数量总

13、是有限的。因此只要将目录当前要使用的那些文件目录表复制到存中就可以了。这样，既不占用太多的主存空间，又可显著提高查阅文件的速度。因此，大多数操作系统中，设置了打开文件、关闭文件这两个操作。打开文件完成的功能，是将文件的有关目录信息复制到主存的活动目录表中，以建立用户和这个文件的联系。关闭文件完成的功能，用户宣布这个文件当前不再使用，系统将其在主存中相应目录信息删除。因而，也就切断了用户和这个文件的联系。4. 什么是虚拟设备？为什么要在操作系统中引入虚拟设备？虚拟设备是指通过虚拟技术，将一台独占设备变为若干台虚拟设备，供若干个用户进程同时使用，通常把这种通过虚拟技术处理后的设备称为虚拟设备。在操

14、作系统中，引入虚拟设备是为了克服独占设备速度较慢，降低设备资源利用率的缺点，从而提高了设备利用率。6为什么说采用有序资源分配法不会产生死锁？答:系统将所有的资源按类型进行线性的排队，并且给于不同序号，所有的进程对资源的请求必须严格按照资源序号递增的次序，这样所形成的资源分配图不可能出现环路。总有一个进程占有较高的序号资源，他继续请求的资源必然时空闲的，因此进程可继续推进，从而避免死锁发生。答:假设系统中有m类资源、n个进程，分别用R1、R2、Rm（1、2、m可看作资源编号）和P1、P2、Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序进行，即任何进程在占有了Ri类资源后，

15、再申请的资源Rj的编号j一定大于i。因此在任一时刻，系统中至少存在一个进程Pk，它占有了较高编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它所占有的所有资源；在Pk完成之后，剩下的进程集合中同样会存在一个进程，它占有了较高编号的资源，且它继续请求的资源必然是空闲的，因而它可以向前推进直至完成；以此类推，所有进程均可运行完成，故不会发生死锁。7一个操作系统有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某进程获得它所需要的全部资源，则立即归还所有资源，每个进程最多使用3个资源。若仅考虑这类资源，该系统有无可能产生死锁，为

16、什么？【解】若仅考虑同一类资源的分配，则不会产生死锁。因为死锁产生的原因有两点： （1）竞争资源，当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；（2）进程推进顺序非法，进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。产生死锁的必要条件：a互斥条件(进程对所分配到的资源进行排他性使用，即在一段时间某资源只由一个进程占有。如果此时还有其他进程要求该资源，要求者只能阻塞，直到占有该资源的进程用毕释放。)b请求和保持条件(进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其他进程占有，此时请求进程阻塞，但又对已经获得的其他资源保

17、持不放。)c不剥夺条件(进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完后由自己释放。)d环路等待条件(在发生死锁时，必然存在一个进程资源的环形链。即进程集合P0,P1,P2,Pn中的P0正在等待一个P1占用的资源； P1正在等待一个P2占用的资源；， Pn正在等待一个P0占用的资源。)在本题介绍的系统中，进程所需要的最大资源数为：20*3=60，而系统中共有该类资源65个，其资源数目已足够系统的各进程使用，因此绝不可能发生死锁。8试述分页系统和分段系统的主要区别。书P160（1）页是信息的物理单位，段是信息的逻辑单位。（2）页的大小固定且由系统确定，段的长度却不固定。（3）分页的作

18、业地址空间是一维的。分段的作业地址空间是二维的。9、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。解：设置3个信号量S、SO、SA，信号量S表示盘子是否为空，其初值为1；信号量SO表示盘中是否有桔子，其初值为0；信号量SA表示盘中是否有苹果，其初值为0。同步描述：int S=1;/表示盘子是否为空int SO=0;/表示是否有橘子int SA=0;/表示是否有苹果main()cobeginfather()while(1)p(S);/

19、盘子是否空将水果放入盘中;if(放入的是桔子)v(SO);else v(SA)son()while(1)p(SO);/盘子中有无桔子从盘中取出桔子;v(S);吃桔子;daughter()while(1)p(SA);/盘子中有无苹果从盘中取出苹果;v(S);吃苹果;coend丙丁甲乙叉2刀1叉1刀2食品bb10、哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论问题；在讨论的间隙4位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如图。请用信号量及P、V操作说明这4位哲学家的同步、互斥过程。解：在本题中，应设置4个信号量fork1、fork2、knife1、knife2，其

20、初值均为1，分别表示资源叉1、叉2、刀1、刀2是否可用。同步描述如下：int fork1=1;int fork2=1;int knife1=1;int knife2=1;main()cobeginPa()while(1)p(knife1);p(fork1);进餐；v(knife1);v(fork1);讨论问题；Pb()while(1)p(knife2);p(fork1);进餐；v(knife2);v(fork1);讨论问题；Pc()while(1)p(knife2);p(fork2);进餐；v(knife2);v(fork2);讨论问题；Pd()while(1)p(knife1);p(fork

21、2);进餐；v(knife1);v(fork2);讨论问题；coend11、设公共汽车上，司机和售票员的活动分别为：司机的活动：启动车辆；正常行车；到站停车；售票员活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现他们的同步。解：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。设置2

22、个信号量：s1、s2，s1表示是否允许司机启动汽车，其初值为0；s2表示是否允许售票员开门，其初值为0。用P、V原语描述如下：int s1=0;/是否允许司机启动汽车int s2=0;/是否允许售票员开门main()cobegindriver()while(1)p(s1);/刚开始肯定阻塞，等BUSMAN进程释放！启动汽车；正常行车；到站停车；v(s2);/通知售票员开门busman()while(1)关车门；v(s1);/通知司机可以开车了售票；p(s2);/判断是否可以开门开车门；上下乘客；coend12、图给出了4个进程合作完成某一任务的前驱图，试说明这4个进程间的同步关系，并用P、V操

23、作描述它。S2S1S4S3解：图说明任务启动后S1先执行。当S1结束后，S2、S3可以开始执行。S2、S3完成后，S4才能开始执行。进程同步描述如下：定义信号量：a2=0;/表示S2能否开始b2=0;/表示S2是否结束a3=0;/表示S3能否开始b3=0;/表示S3是否结束main()cobeginS1()S1v(a2);v(a3);S2()p(a2);S2v(b2);S3()p(a3);S3v(b3); S4()p(b2);p(b3);S4Coend13、.设有4道作业，它们的提交时间及执行时间如下：作业号提交时间执行时间18020283053850149004试计算在单道环境下，采用先进先

24、服务调度算法(FCFS)和最短作业优先调度算法(SJF)时的平均周转时间和平均带权周转时间并指出它们的调度顺序，（时间单位：小时，以十进制进行计算）完成时间=开始时间+运行时间，等待时间=开始时间-提交时间，周转时间=等待时间+运行时间=完成时间-提交时间，带权周转时间=周转时间/运行时间，响应比时间=（等待时间+运行时间）/运行时间解：若采用先来先服务调度算法作业号提交时间执行时间开始时间完成时间周转时间带权周转时间180208010020102830510010522443850110510621210490041061102050调度顺序为1，2，3，4平均周转时间： T=（2.0+2.

25、2+2.1+2.2）/4=2.075平均带权周转时间: W=(1.0+4.4+21.0+5.0)/4=7.25若采用短作业优先调度算法作业号提交时间执行时间开始时间完成时间周转时间带权周转时间18.02.08.010.02.01.028.30.510.511.02.75.438.50.110.010.11.616.049.00.410.110.51.53.75调度顺序为1，3，4，2平均周转时间： T=（2.0+2.7+1.6+1.5）/4=1.95平均带权周转时间: W=(1.0+5.4+16.0+3.75)/4=6.5375结论：SJF的平均周转时间和平均带权周转时间都比FCFS低。若采用

26、响应比高者优先调度算法作业号提交时间执行时间开始时间完成时间周转时间带权周转时间18.02.08.010.02.01.028.30.510.110.62.34.638.50.110.010.11.616.049.00.410.611.02.05.0调度顺序为1，3，2，4平均周转时间： T=（2.0+2.3+1.6+2.0）/4=1.975平均带权周转时间: W=(1.0+4.6+16+5.0)/4=6.6514、今有三个批处理作业，第一个作业10：10到达，需要执行2小时；第 二个作业在10：10到达，需要执行1小时；第三个作业10：25到达，需要执行25分钟。分别采取如下三种作业调度算法：

27、（老师给的最后的一组数字中需要执行时间为20分钟）调度算法1：作业号到达时间开始执行时间执行结束时间110：0010：0012：00210：1012：0013：00310：2513：0013：25调度算法2：作业号到达时间开始执行时间执行结束时间110：0011：5013：50210：1010：5011：50310：2510：2510：50调度算法3：作业号到达时间开始执行时间执行结束时间110：0010：0012：00210：1012：2513：25310：2512：0012：25（1）计算各调度算法下的作业平均周转时间。（2）调度算法1、3分别是什么作业调度算法？解：（1）采用调度算法1时

28、：作业1的周转时间为2小时作业2的周转时间为2.83小时作业3的周转时间为3小时平均周转时间为：（2+2.83+3）/ 3 =2.61小时采用调度算法2时：作业1的周转时间为3.83小时作业2的周转时间为1.67小时作业3的周转时间为0.42小时平均周转时间为：（3.83+1.67+0.42）/ 3 =1.97小时采用调度算法3时：作业1的周转时间为2小时作业2的周转时间为3.25小时作业3的周转时间为2小时平均周转时间为：（2+3.25+2）/ 3 =2.42小时（2）调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法（FCFS）；调度算法3是按照作业执行时间从短到长的次序

29、执行的，所以它是短作业优先调度算法（SJF）。15、表5.2给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？表5.2 空闲分区表分区号大小起始地址（递增）132K100K210K150K35K200K4218K220K596K530K解：（1）若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大小一致，应从空间分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中

30、4号分区，分配后剩下18K。显然采用最佳适应算法进行存分配，可以满足该作业序列的需求。为作业序列分配了存空间后，空闲分区表如表5.3（a）所示。（2）采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分区还剩下122K；接着申请20K时，选中1号分区，分配后剩下12K；最后申请200K，现有的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进行存分配，无法满足该作业序列的需求。这时的空闲分区表如表5.3（b）所示。表5.3（a）空闲分区表分区号大小起始地址112K100K(120?)210K150K35K200K418K220K(420?)表5.3（b）空闲分区表

31、分区号大小起始地址112K100K210K150K35K200K4122K220K596K530K16、某系统的进程状态转换图，请说明：/新颖！执行就绪阻塞2314（1） 引起各种状态转换的典型事件有哪些？（2） 当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一进程作一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换1？（3） 试说明是否会发生下述因果转换：a) 21 b）32 c）41解：（1） 当进程调度程序从就绪队列中选取一个进程投入运行时引起转换1；正在执行的进程如因时间片用完而被暂停执行就会引起转换2；正在执行的进程因等待的事件尚未

32、发生而无法执行（如进程请求完成I/O）则会引起转换3；当进程等待的事件发生时（如I/O完成）则会引起转换4。（2） 如果就绪队列非空，则一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的进程由执行状态变为阻塞状态，这时处理机空闲，进程调度程序必然会从就绪队列中选取一个进程并将它投入运行，因此只要就绪队列非空，一个进程的转换3能立即引起另一个进程的转换1。（3） 所谓因果转换指的是有两个转换，一个转换的发生会引起另一个转换的发生，前一个转换称为因，后一个转换称为果，这两个转换称为因果转换。当然这种因果关系并不是什么时候都能发生，而是在一定条件下才会发生。a)

33、 21：当某进程发生转换2时，就必然引起另一进程的转换1。因为当发生转换2时，正在执行的进程从执行状态变为就绪状态，进程调度程序必然会从就绪队列中选取一个进程投入运行，即发生转换1。b) 32：某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前执行进程从执行状态变为阻塞状态，不可能又从执行状态变为就绪状态。c) 41：当处理机空闲且就绪队列为空时，某一进程发生转换4，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入运行。17、已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给该作业分配2个物理块，当采用FIF

34、O页面淘汰算法时缺页率为多少？假设现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率为多少？解：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下：页面走向12131242134物理块111123122413物理块22231244134缺页缺缺缺缺缺缺缺缺缺从上述页面置换图可以看出：页面引用次数为11次，缺页次数为9次，所以缺页率为9/11。若采用后一种页面淘汰策略，其页面置换情况如下：页面走向12131242134物理块111222111222物理块22131242134缺页缺缺缺缺缺缺缺缺从上述页面置换图可以看出：

35、页面引用次数为11次，缺页次数为8次，所以缺页率为8/11。18、一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。（物理快为4的不做要求）（1） 最佳置换淘汰算法（理论算法）（2） 先进先出淘汰算法（3） 最近最久未使用淘汰算法解：（1）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：走向432143543215块1块2块3缺页4缺43缺432缺431缺435缺235缺215缺缺页率为：7/12走向432143

36、543215块1块2块3块4缺页4缺43缺432缺4321缺4325缺1325缺缺页率为：6/12由上述结果可以看出，增加分配给作业的存块数可以降低缺页率。（2）根据所给页面走向，使用先进先出页面淘汰算法时，页面置换情况如下：走向432143543215块1块2块3缺页4缺43缺432缺321缺214缺143缺435缺352缺521缺缺页率为：9/12走向432143543215块1块2块3块4缺页4缺43缺432缺4321缺3215缺2154缺1543缺5432缺4321缺3215缺缺页率为：10/12由上述结果可以看出，对先进先出算法而言，增加分配给作业的存块数反而使缺页率上升，这种异常现

37、象称为Belady现象。（3）根据所给页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况如下：走向432143543215块1块2块3缺页4缺43缺432缺321缺214缺143缺435缺354543432缺321缺215缺缺页率为：10/12走向432143543215块1块2块3块4缺页4缺43缺432缺4321缺321421431435缺135415435432缺4321缺3215缺缺页率为：8 /12由上述结果可以看出，增加分配给作业的存块数可以降低缺页率。19、设一计算机系统有输入机一台，打印机两台，现有两道程序，同时投入运行，且程序A先开始运行，程序B后运行，程序A的运行轨迹

38、为：计算50ms,打印100ms,计算50ms,打印100ms;程序B的运行轨迹为：计算50ms，输入数据80ms,再计算方法100ms结束。要求：（1） 用图画出这两道程序并发执行时的工作情况（2） 说明在两道程序运行时，CPU有无空闲等待？若有，在哪段时间有等待？为什么会空闲等待？（3） 程序A、B运行时，有无等待现象？在什么时候会发生等待现象？解：（1） PA PB PA PBCPU 50 50 100输入机 80打印机 100 100（2）CUP有空闲等待，当PB让出CPU进行输入时，PA尚未打印完毕（3）PB有等待现象，当PB输入完毕，此时PA 尚未计算完毕，PB只得等待20、有一页

39、式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，存总共有8个存储块，试问逻辑地址至少应为多少位？存空间有多大？解：（1） 本题中，每页2048字节，所以页位移部分地址需要占据11个二进制位；逻辑地址空间最大为16页，所以页号部分地址需要占据4个二进制位。故逻辑地址至少应为15位。（2） 由于存共有8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等，因此，存空间为8页*2048字节=16K。21、一请求分页存储管理系统，页面大小为每页100字节。有一个5050的整型数组按行连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下：int a5050;int

40、i,j;for (i=0;i=49;i+) for (j=0;j=49;j+)aij=0;若在程序执行时存中只有一个存储块用来存放数组信息，试问该程序执行时将产生多少次缺页中断？解：由题目可知，该数组中有2500个整数，每个整数占用2个字节，共需存储空间5000个字节；而页面大小为每页100字节，数组占用空间50页。假设数据从该作业的第m页开始存放，则数组分布在第m页到第m+49页中，它在主存中的排列顺序为：a00,a01,a049 第m页a10,a11,a149 第m+1页a490,a491,a4949 第m+49页由于该初始化程序是按行进行的，因此每次缺页中断调进一页后，位于该页的数组元素

41、全部赋予0值，然后再调入下一页，所以涉及的页面走向为m，m+1，m+49，故缺页次数为50次。23.若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011、2148、3000、4000、5012转化为相应的物理地址。页号块号01232316分析及相关知识在页式存储管理系统中，当进程要访问某个逻辑地址中的数据时，分页地址变换机构自动地将逻辑地址分为页号和页位移两部分，再以页号为索引去检索页表。在执行检索之前，先将页号与页表长度进行比较，如果页号超过了页表长度，则表示本次所访问的地址已超越进程的地址空间，系统产生地址越界中断。如果页访问合法，则由页表始地址

42、和页号计算出相应页表项的位置，从中得到该页的物理块号，并将它装入物理地址寄存器的块号部分。与此同时，再将逻辑地址寄存器中的页地址直接送入物理地址寄存器的块地址部分，这样便完成了从逻辑地址到物理地址的变换。解：本题中，为了描述方便，设页号为P，页偏移为W，逻辑地址为A，页面大小（页长）为L，则p=int(A/L)w=A mod L（1）对于逻辑地址1011p=int(1011/1024)=0w=1011 mod 1024=1011查页表第0页在第2块，所以物理地址为2*1024+1011=3059（2）对于逻辑地址2148p=int(2148/1024)=2w=2148 mod 1024=100

43、查页表第2页在第1块，所以物理地址为1*1024+100=1124。（3）对于逻辑地址3000p=int(3000/1024)=2w=3000 mod 1024=952查页表第2页在第1块，所以物理地址为1*1024+952=1976（4）对于逻辑地址4000p=int(4000/1024)=3w=4000 mod 1024=928查页表第3页在第6块，所以物理地址为6*1024+928=7072。（5）对于逻辑地址5012p=int(5012/1024)=4w=5012 mod 1024=916因页号超过页表长度，该逻辑地址非法。24、有如下请求磁盘服务的队列，要访问的磁道分别是23、376

44、、205、132、19、61。现在磁头在100道上，分别按FCFS，最短优先，扫描算法，磁头的平均移动道数是多少？解：（1）FCFS： 寻道顺序： 23 376 205 132 19 61平均磁头移动道数：（+77 +353 +171 +73 +113 +42）/ 6 =138.17（2）最短优先： 寻道顺序： 132 61 23 19 205 376平均磁头移动道数：（+38 +171 +186 +32 +4 +71）/ 6 =83.67（3）扫描算法： 寻道顺序： 132 205 376 61 23 19平均磁头移动道数：（+38 +171 +73 +32 +4 +315）/ 6 =105

45、.56、画出下面5条语句的前趋图：S1：a=6+x；S2：b=a-x；S3:c=4*x； S4:d=b+c；S5:e=d+3。试利用Bernstein 条件证明题中的S2和S3语句是可以并发执行的，而S3和S4语句是不能并发执行的？S1S4S5S3S2解：前趋图如下： （1）R(S2) W( S3)=；W(S2) R(S3)=；W(S2) W(S3)=；R(S2) W( S3) W(S2) R(S3) W(S2) W(S3)=S2、S3可以并发执行（2） R(S3) W( S4)=；W(S3) R(S4)=c；W(S3) W(S4)=;R(S3) W( S4) W(S3) R(S4) W(S3

46、) W(S4)=c不是空集S3，S4不能并发执行22某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K回答下列问题：（1） 采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？（2） 采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？（3） 如再申请100K，针对（1）和（2）各有什么结果？分析及相关知识为描述方便起见，本题用“（分区首址，分区长度

47、）”的形式描述系统中的分区。由题中所给条件可知，最初系统中只有一个空闲区，大小为512K，始址为0，即（0，512K）。操作已分配空间空闲块初始无（0，512K）申请300K（0，300K）（300K，212K）申请100K（0，300K）（300K，100K）（400K，112K）释放300K（300K，100K）（0，300K）（400K，112K）申请150K（0，150K）（300K，100K）（150K，150K）（400K，112K）申请30K（0，150K）（150K，30K）（300K，100K）（180K，120K）（400K，112K）申请40K（0，150K）（150K，

48、30K）（180K，40K）（300K，100K）（220K，80K）（400K，112K）申请60K（0，150K）（150K，30K）（180K，40K）（220K，60K）（300K，100K）（280K，20K）（400K，112K）释放30K（0，150K）（180K，40K）（220K，60K）（300K，100K）（150K，30K）（280K，20K）（400K，112K）采用最佳适应算法时的操作流程：操作已分配空间空闲块初始无（0，512K）申请300K（0，300K）（300K，212K）申请100K（0，300K）（300K，100K）（400K，112K）释放300K（

49、300K，100K）（0，300K）（400K，112K）申请150K（0，150K）（300K，100K）（150K，150K）（400K，112K）申请30K（0，150K）（300K，100K）（400K，30K）（150K，150K）（430K，82K）申请40K（0，150K）（300K，100K）（400K，30K）（430K，40K）（150K，150K）（470K，42K）申请60K（0，150K）（150K，60K）（300K，100K）（400K，30K）（430K，40K）（210K，90K）（470K，42K）释放30K（0，150K）（150K，60K）（300K，1

50、00K）（430K，40K）（210K，90K）（400K，30K）（470K，42K）（1）采用首次适应算法，在完成了题目所给的系列申请及释放存操作后，存分配情况如图5.11所示（用阴影表示空闲空间），空闲分区表如下所示。图5.11采用首次适应算法的存分配情况150K作业40K作业60K作业100K作业0150K180K220K280K300K400K512K-1分区大小起始地址01230K20K112150K280K400K150K作业60K作业100K作业40K作业0150K210K300K400K430K470K512K-1采用最佳适应算法，完成了题目所给的系列申请及释放存操作后，存分配情况如图5.12所示（用阴影表示空闲空间），空闲分区表如下：图5.12 采用最佳适应算法的存分配情况分区大小起始地址01230K42K90K400K470K210K如再申请100K空间，由上述结果可知，采用首次适应算法后剩下的空闲分区能满足这一申请要求；而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。23 / 23