2022年操作系统习题课 2.pdf

《2022年操作系统习题课 2.pdf》由会员分享，可在线阅读，更多相关《2022年操作系统习题课 2.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统习题课1.何谓操作系统？配置操作系统的主要目的是什么？答：操作系统是管理系统资源、控制程序执行，改善人机界面，提供各种服务，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一种系统软件。配置操作系统的主要目标可归结为：1方便用户使用：OS 通过提供用户与计算机之间的友善接口来方便用户使用。2扩大机器功能：OS 通过扩充改造硬件设施和提供新的服务来扩大机器功能。3管理系统资源：OS 有效管理好系统中所有硬件软件资源，使之得到充分利用。4提高系统效率：OS 合理组织好计算机的工作流程，以改进系统性能和提高系统效率。5构筑开放环境：OS 遵循有关国际标准来设计和构造，以构筑出一个开

2、放环境。其含义主要是指：遵循有关国际标准（如开放的通信标准、开放的用户接口标准、开放的线程库标准等）；支持体系结构的可伸缩性和可扩展性；支持应用程序在不同平台上的可移植性和可互操作性。2.操作系统的主要特性有哪些？答：1并发性。并发性（concurrence）是指两个或两个以上的事件或活动在同一时间间隔内发生。操作系统是一个并发系统，并发性是它的重要特征，操作系统的并发性指它应该具有处理和调度多个程序同时执行的能力。多个 I/O 设备同时在输入输出；设备I/O 和CPU计算同时进行；内存中同时有多个系统和用户程序被启动交替、穿插地执行，这些都是并发性的例子。发挥并发性能够消除计算机系统中部件和

3、部件之间的相互等待，有效地改善系统资源的利用率，改进系统的吞吐率，提高系统效率。例如，一个程序等待 I/O 时，就出让 CPU，而调度另一个程序占有CPU 执行运行。这样，在程序等待I/O时，CPU 便不会空闲，这就是并发技术。并发性虽然能有效改善系统资源的利用率，但却会引发一系列的问题，使操作系统的设计和实现变得复杂化。如：怎样从一个运行程序切换到另一个运行程序？以什么样的策略来选择下一个运行的程序?怎样将各个运行程序隔离开来，使之互不干扰，免遭对方破坏？怎样让多个运行程序互通消息和协作完成任务？怎样协调多个运行程序对资源的竞争？多个运行程序共享文件数据时，如何保证数据的一致性？操作系统必须

4、具有控制和管理程序并发执行的能力，为了更好的解决上述问题，操作系统必须提供机制和策略来进行协调，以使各个并发进程能顺利推进，并获得正确的运行结果。另外，操作系统还要合理组织计算机工作流程，协调各类硬软件设施工作，充分提高资源的利用率，充分发挥系统的并行性，这些也都是在操作系统的统一指挥和管理下进行的。采用了并发技术的系统又称为多任务系统（multitasking system），计算机系统中，并发实际上是一个物理CPU 在若干道程序之间多路复用，这样就可以实现运行程序之间的并发，以及 CPU 与I/O 设备、I/O 设备与 I/O 设备之间的并行，并发性的实质是对有限物理资源强制行使多用户共享

5、以提高效率。在多处理器系统中，程序的并发性不仅体现在宏观上，而且体现在微观上（即在多个CPU 上）也是并发的，又称并行的。并行性（parallelism）是指两个或两个以上事件或活动在同一时刻发生。在多道程序环境下，并行性使多个程序同一时刻可在不同CPU 上同时执行。而在分布式系统中，名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 15 页 -多台计算机的并存使程序的并发性得到了更充分的发挥。可见并行性是并发性的特例，而并发性是并行性的扩展。由于并发技术的本质思想是：当一个程序发生事件（如等待I/O）时出让其占用的CPU 而由另一个程序运行，据此不难看出，实现并发技术的关键之一是

6、如何对系统内的多个运行程序（进程）进行切换的技术。2共享性(sharing)。共享性是操作系统的另一个重要特性。共享指操作系统中的资源（包括硬件资源和信息资源）可被多个并发执行的进程共同使用，而不是被一个进程所独占。出于经济上的考虑，一次性向每个用户程序分别提供它所需的全部资源不但是浪费的，有时也是不可能的。现实的方法是让操作系统和多个用户程序共用一套计算机系统的所有资源，因而，必然会产生共享资源的需要。资源共享的方式可以分成两种：第一种是互斥访问。系统中的某些资源如打印机、磁带机、卡片机，虽然它们可提供给多个进程使用，但在同一时间内却只允许一个进程访问这些资源，即要求互相排斥地使用这些资源。

7、当一个进程还在使用该资源时，其他欲访问该资源的进程必须等待，仅当该进程访问完毕并释放资源后，才允许另一进程对该资源访问。这种同一时间内只允许一个进程访问的资源称临界资源，许多物理设备，以及某些数据和表格都是临界资源，它们只能互斥地被共享。第二种是同时访问。系统中还有许多资源，允许同一时间内多个进程对它们进行访问，这里“同时”是宏观上的说法。典型的可供多进程同时访问的资源是磁盘，可重入程序也可被同时访问。与共享性有关的问题是资源分配、信息保护、存取控制等，必须要妥善解决好这些问题。共享性和并发性是操作系统两个最基本的特性，它们互为依存。一方面，资源的共享是因为程序的并发执行而引起的，若系统不允许

8、程序并发执行，自然也就不存在资源共享问题。另一方面，若系统不能对资源共享实施有效管理，必然会影响到程序的并发执行，甚至程序无法并发执行，操作系统也就失去了并发性，导致整个系统效率低下。3异步性(asynchronism)。操作系统的第三个特性是异步性，或称随机性。在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到底，而是“走走停停”。例如，一个进程在CPU 上运行一段时间后，由于等待资源满足或事件发生，它被暂停执行，CPU 转让给另一个进程执行。系统中的进程何时执行？何时暂停？以什么样的速度向前推进？进程总共要化多少时间执行才能完成？这些都是不可预知

9、的，或者说该进程是以异步方式运行的，其导致的直接后果是程序执行结果可能不唯一。异步性给系统带来了潜在的危险，有可能导致进程产生与时间有关的错误，但只要运行环境相同，操作系统必须保证多次运行进程，都会获得完全相同的结果。操作系统中的随机性处处可见，例如，作业到达系统的类型和时间是随机的；操作员发出命令或按按钮的时刻是随机的；程序运行发生错误或异常的时刻是随机的；各种各样硬件和软件中断事件发生的时刻是随机的等等，操作系统内部产生的事件序列有许许多多可能，而操作系统的一个重要任务是必须确保捕捉任何一种随机事件，正确处理可能发生的随机事件，正确处理任何一种产生的事件序列，否则将会导致严重后果。4虚拟性

10、(virtual)。虚拟性是指操作系统中的一种管理技术，它是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。显然，前者是实际存在的而后者是虚构假想的，采用虚拟技术的目的是为用户提供易于使用、方便高效的操作环境。例如，在多道程序系统中，物理CPU 可以只有一个，每次也仅能执行一道程序，但通过多道程序和分时使用CPU 技术，宏观上有多个程序在执行，就好像有多个CPU 在为各道程序工作一样，物理上的一个CPU 变成了逻辑上名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 15 页 -的多个 CPU。Spooling 技术可把物理上的一台独占设备

11、变成逻辑上的多台虚拟设备；窗口技术可把一个物理屏幕变成逻辑上的多个虚拟屏幕；通过时分或频分多路复用技术可以把一个物理信道变成多个逻辑信道；IBM 的VM 技术把物理上的一台计算机变成逻辑上的多3.当进程对信号量S 执行 P、V 操作时，S 的值发生变化，当S0、S=0、和 S0 时 S表示可使用的资源数或表示可使用资源的进程数；S=0 时 S表示无资源可供使用或表示不允许进程再进入临界区；S0 时 S表示等待使用资源的进程个数或表示等待进入临界区的进程个数。4.作业调度和进程调度各自的主要功能是什么？答：作业调度的主要功能是：记录系统中各个作业的情况；按照某种调度算法从后备作业队列中挑选作业；

12、为选中的作业分配内存和外设等资源；为选中的作业建立相应的进程；作业结束后进行善后处理工作。进程调度的主要功能是：保存当前运行进程的现场；从就绪队列中挑选一个合适进程；为选中的进程恢复现场。5.有三个用户进程A、B 和 C，在运行过程中都要使用系统中的一台打印机输出计算结果。(1)试说明 A、B、C 进程之间存在什么样的制约关系？(2)为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V 操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。答：(1)A、B、C 三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。(2)mut

13、ex：用于互斥的信号量，初值为1。各进程的代码如下：进程 A 进程 B 进程 C.P(mutex)P(mutex)P(mutex)申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机V(mutex)V(mutex)V(mutex)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 15 页 -6.设有一台计算机，有两条I/O 通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1 中，加工处理后再搬到缓冲区B2 中，并在打印机上打印结果（假定缓冲区仅能容纳一张卡片信息）。问：系统要设几个进程来完成这个任务？各自的工作是什么？这些进程间有什么样的相互制约关

14、系？用 P、V 操作写出这些进程的同步算法。分析 我们画一个草图来帮助我们理解这道题：从图中可以看出，从“卡片机”到“打印机”共需要 3个操作，即输入、处理、输出。这 3个动作就是完成任务的 3个进程。下面我们看看这些进程之间有什么样的制约关系。可以看出，这3个进程之间是同步关系，合作完成从输入到输出的工作任务。对其中任何一个进程，要处理好与其关联的两端设备的协调工作。以“输入进程”为例，它与卡片机和缓冲区B1关联，将卡片机的卡片输入到缓冲区B1，在不考虑卡片机的情况下，就要考虑缓冲区的情况，即是满还是空，是空缓冲区，输入进程就可以输入信息，如果缓冲区满，则要等待“处理进程”将B1中的信息取走

15、，使之为空，输入进程才能继续工作。依此类推，可以找出另外2个进程的制约关系。一般来说，处理进程同步需要2个信号量，“输入进程”和“处理进程”同步，需要2个信号量，解决缓冲区 B1的协调操作问题；而“处理进程”和“输出进程”同步，还需要 2个信号量，解决缓冲区 B2的协调操作问题。因此，共需要4个信号量。本题中“处理进程”的算法有一些难度，因为它需要协调两个缓冲区的工作，考虑的因素比较多，算法复杂些。答案系统可设三个进程来完成这个任务：Input进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；Process 进程负责从缓冲区 B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；Pr

16、int进程负责从缓冲区 B2中取出信息，并在打印机上印出。Input进程受 Process 进程影响，B1放满信息后 Input进程要等待：等 Process进程将其中信息全部取走，才能继续读入信息；Process 进程受 Input进程和Print进程的约束：B1中信息放满后 Process 进程才可从中取出它们，且B2被取空后，Process 进程才可将加工结果送入其中；Print进程受 Process 进程的约束：B2中信息放满后 Print进程才可从中取出它们,进行打印。信号量含义及初值：B1full 缓冲区 B1满，初值为 0；B1empty缓冲区 B1空，初值为 1；B2full

17、缓冲区 B2满，初值为 0；B2empty缓冲区 B2空，初值为 1；Input：while(1)卡片机缓冲区 B1 打印机缓冲区 B2 输入处理输出名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 15 页 -wait(B1empty);读卡片中的信息，并将其放入缓冲区1中;signal(B1full);Process:while(1)wait(B1full);从缓冲区 1中取走数据，存放在临时变量tmp中;signal(B1empty);处理tmp中的数据，将处理结果存放在变量result中;wait(B2empty);将result中的结果放入缓冲区 2;signal(B2f

18、ull);Print:while(1)wait(B2full);从缓冲区 2中取走数据，存放在临时变量tmp中;signal(B2empty);打印tmp中的数据;注：如果改变缓冲区的数量或者改变缓冲区的大小，题目的答案要做相应地变化：假定缓冲区 B1的大小为 m，缓冲区 B2的大小为 n。则上述问题就演变为同步互斥问题了。B1full 缓冲区 B1满，初值为 0；B1empty 缓冲区 B1空，初值为 m；B2full 缓冲区 B2满，初值为 0；B2empty 缓冲区 B2空，初值为 n；mutex1-缓冲区 B1的互斥信号量，初值为 1；mutex2-缓冲区 B2的互斥信号量，初值为 1

19、；名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 15 页 -Input：while(1)wait(B1empty);wait(mutex1);读卡片中的信息，并将其放入缓冲区1中;signal(mutex1);signal(B1full);Process:while(1)wait(B1full);wait(mutex1);从缓冲区 1中取走数据，存放在临时变量tmp中;signal(mutex1);signal(B1empty);处理tmp中的数据，将处理结果存放在变量result中;wait(B2empty);wait(mutex2);名师资料总结-精品资料欢迎下载-名师精心

20、整理-第 6 页，共 15 页 -将result中的结果放入缓冲区 2;signal(mutex2);signal(B2full);Print:while(1)wait(B2full);wait(mutex2);从缓冲区 2中取走数据，存放在临时变量tmp中;signal(mutex2);signal(B2empty);打印tmp中的数据;7.对于如图所示的交通图，驳船在运河里单向航行，汽车在公路上也是单向行驶。由于汽车要两次跨越运河。为了让汽车和驳船能正常地行驶，在运河上架设了两座吊桥，当汽车要跨越运河时，吊桥必须放下；而当驳船要航行时，吊桥必须吊起。试设计一种方案，保证汽车和驳船均能正常行

21、驶。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 15 页 -答：根据题目告诉我们的条件，可以画出这个交通系统如下图所示的一种通行状态。在这种状态下，吊桥A 吊起，驳船正在通过吊桥A，船头已抵达吊桥B。由于吊桥 B 上正有汽车通行，因此驳船等待吊桥B 上的汽车下桥。而公路上的汽车又在等待驳船通过吊桥A，这时吊桥 B 上的汽车处于等待吊桥A 放下的状态。由此可见，此时驳船和汽车相互等待对方所占用的资源，显然是发生了死锁。用信号量的办法可以有效地解决这个交通系统的死锁问题。这里，首先将驳船和汽车抽象为并发进程，吊桥A、B 是并发进程所共享的资源。为吊桥A、B分别设置一个信号量，信号

22、量的值为 1 表示吊桥未被占用；信号量的值为 0 表示吊桥上正有汽车通行，或吊桥正被吊起、桥下有驳船通过。具体的解决方案有多种，其中最简单的是当并发进程要通过吊桥时，首先检测这两个信号量是否同时为 1，若是的话，则将这两个信号量同时获取，通过两座吊桥，然后将两个信号量释放。如果进程检测到两个信号量不同时为1，则等待，直至它们的值同时都为 1。这个简单方法能有效地解决死锁问题，但并不能保证这个交通系统具有高的通行效率。对于这个交通系统，人们实际上通常采用的调度方法是：当船首接近吊桥 A 时鸣笛，这时要通过吊桥A、但还未上桥的汽车不再上桥，等桥上的汽车下桥后，吊桥 A 吊起，让驳船通过。当船首接近

23、吊桥B 时，同样应先鸣笛，如吊桥 B 上没有汽车，吊桥B 吊起，让驳船通过。对于汽车来说，在接近吊桥B 时，应判断吊桥B 是否处于放下状态，如果是的话，还应进一步判断吊桥A是否是吊起的。如果吊桥A 是处在放下状态，那么整条公路是通畅的，因此汽车可以上桥。如果此时吊桥A 吊起，则应判断运河对岸的公路上是否已经排满了汽车，如果是的话，则汽车不能上桥，原因在于如果汽车上了桥，由于前面的公路上已经塞满了汽车在等待吊桥A 放下，因此汽车上了吊桥B 后将无法下桥，此时会发生死锁。我们根据这样的调度方法写出如下程序。/*program BargeAndAutomobile*/int bridge_A_up=

24、0,bridge_A_up=0;/起先吊桥 A、B 都是放下的semaphore mutex_A=1,mutex_B=1;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 15 页 -semaphore load_num=K;/两桥之间的公路上最多能容纳K 辆汽车void barge(int i)/驳船的程序 Approaching Bridge A;/驳船驶近吊桥 A Blowing a whistle;/鸣笛P(mutex_A);if(bridge_A_up=0)bridge_A_up=1;/吊桥 A 吊起Approaching Bridge B;/驳船驶近吊桥 B Blowi

25、ng a whistle;/鸣笛P(mutex_B);if(bridge_B_up=0)bridge_B_up=1;/吊桥 B 吊起barge passing Bridge A;/驳船通过吊桥 A V(mutex_A);barge passing Bridge B;/驳船通过吊桥 B V(mutex_B);void automobile(int i)/汽车 i 的程序 Approaching Bridge B;/汽车驶近吊桥 B P(load_num);P(mutex_B);if(bridge_B_up=1)/若吊桥 B 吊起bridge_B_up=0;/吊桥 B 放下Go on to bri

26、dge B;/汽车驶上吊桥 B Pass bridge B;/汽车驶过吊桥 B V(mutex_B);Go ahead;P(mutex_A);if(bridge_A_up=1)/若吊桥 A 吊起bridge_A_up=0;/吊桥 A 放下Go on to bridge A;/汽车驶上吊桥 A V(load_num);Pass bridge A;/汽车驶过吊桥 A V(mutex_A);void main()parbegin(barge(1),barge(2),automobile(1),automobile(2),);8.下表给出作业 l，2，3 的提交时间和运行时间。采用先来先服务调度算法和

27、短名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 15 页 -作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）作业号提交时间运行时间1 2 3 0.0 0.4 1.0 8.0 4.0 1.0 分析 解此题关键是要清楚系统中各道作业随时间的推进情况。我们用一个作业执行时间图来表示作业的执行情况，帮助我们理解此题。采用先来先服务调度策略，其作业执行时间图如下：采用短作业优先调度策略，其作业执行时间图如下：另外，作业 i 的周转时间 Ti作业完成时间作业提交时间系统中 n 个作业的平均周转时间nTTnii1)(1，其中 Ti 为作业 i

28、的周转时间。解：采用先来先服务调度策略，则调度次序为l、2、3。作业号 提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.0 2 0.4 4.0 8.0 12.0 11.6 3 1.0 1.0 12.0 13.0 12.0 平均周转时间 T（811.612）/310.53 采用短作业优先调度策略，则调度次序为l、3、2。作业号 提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.0 3 1.0 1.0 8.0 9.0 8.0 2 0.4 4.0 9.0 13.0 作业作业 3 作业 2 作业 1 0 0.4 1.0 8.0 12.0 1

29、3.0 时间作业提交时间各作业陆续完成时间作业作业 3 作业 2 作业 1 0 0.4 1.0 8.0 9.0 13.0 时间作业提交时间各作业陆续完成时间名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 15 页 -12.6 平均周转时间 T（8812.6）/39.53 9.今有三个批处理作业。第一个作业 10:00到达，需要执行 2小时；第二个作业在10:10到达，需要执行 1小时；第三个作业在 10:25到达，需要执行 25分钟。分别采取如下两种作业调度算法：调度算法 1：作业号到达时间开始执行时间执行结束时间1 2 3 10:00 10:10 10:25 10:00 12

30、:00 13:00 12:00 13:00 13:25 调度算法 2：作业号到达时间开始执行时间执行结束时间1 2 3 10:00 10:10 10:25 11:50 10:50 10:25 13:50 11:50 10;50（1）计算各调度算法下的作业平均周转时间。（2）调度算法 1 是什么作业调度算法？分析作业的周转时间作业完成时间作业提交时间。以调度算法 1 的作业 2 为例，其周转时间=作业完成时间 13:00作业提交时间 10:10，得到结果为 2 小时 50 分钟，转换为小时为2.83 小时。转换的目的是为了方便计算平均周转时间。解：（1）采用调度算法 1 时：作业 1 的周转时间

31、为 2 小时；作业 2 的周转时间为 2.83 小时；作业 3 的周转时间为 3 小时；平均周转时间为：（22.833）32.61小时。采用调度算法 2 时：作业 1 的周转时间为 3.83 小时；作业 2 的周转时间为 1.67小时；作业 3 的周转时间为 0.42 小时；平均周转时间为：（3.83l.670.42）3l.97 小时。（2）调度算法 1 是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。10.考虑一个由 8 个页面，每页有1024 个字节组成的逻辑空间，把它装入到有32 个物理块的存储器中，问：（1）逻辑地址需要多少二进制位表示？（2）物理地址需要多少二进制位表示？

32、解 因为页面数为 8=23，故需要 3 位二进制数表示。每页有1024 个字节，1024=210，于是页内地址需要10 位二进制数表示。32 个物理块，需要5 位二进制数表示（32=25）。（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。分析 在分页存储管理中，逻辑地址结构如下图所示。页号 p 页内地址 d 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 15 页 -它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页内位移）d。页号的地址位数

33、决定了页的多少，假设页号有20 位，则地址空间中最多可容纳的页面数为220，即 1MB 个页面。页内地址位数确定了每页的大小，若页内地址为12 位，则每页大小为212，即 2KB。同理，物理地址中块号的地址位数决定了块的多少，由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。11.若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012 转化为相应的物理地址。页号块号0 1 2 3 2 3 1 6 解 本题中，为了描述方便，设页号为p，页内位移为 d，则：（1）对于逻辑地址

34、 1011，pint（1011/1024）0，d1011 mod 1024 1011。查页表第 0 页在第 2 块，所以物理地址为1024 210113059。（2）对于逻辑地址 2148，pint（2148/1024）2，d2148 mod 1024 100。查页表第 2 页在第 1 块，所以物理地址为10241001124。（3）对于逻辑地址 4000，pint（4000/1024）3，d4000 mod 1024 928。查页表第 3 页在第 6 块，所以物理地址为1024 69287072。（4）对于逻辑地址 5012，pint（5012/1024）4，d5012 mod 1024 9

35、16。因页号超过页表长度，该逻辑地址非法。12考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 当内存块数量分别为3 时，试问 FIFO、LRU、OPT 这三种置换算法的缺页次数各是多少？解 使用 FIFO 算法，缺页次数是16；使用 LRU 算法，缺页次数是15；使用 OPT 算法，缺页次数是11。分析 所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。当内存块数量为 3 时：FIFO 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 块 1 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6

36、 块 2 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1 块 3 3 3 3 5 5 5 1 1 1 6 6 6 3 3 缺页因此，FIFO 算法发生缺页中断的次数为16。在 FIFO 算法中，先进入内存的页面被先换出。例如，当页6 要调入时，内存的状态为 4、1、5，考查页 6 之前调入的页面，分别为5、1、2、4、，可见4 为最先进入内存的，本次应换出，然后把页6调入内存。LRU 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 15 页 -块 1 1 1 1 4 4 5 5 5 1

37、1 7 7 2 2 2 块 2 2 2 2 2 2 6 6 6 3 3 3 3 3 3 块 3 3 3 1 1 1 2 2 2 2 6 6 1 6 缺页因此，LRU 算法发生缺页中断的次数为15。在 LRU 算法中，最近最少使用的页面被先换出。例如，当页6 要调入时，内存的状态为 5、2、1，考查页 6 之前调入的页面，分别为5、1、2、，可见2 为最近一段时间内使用最少的，本次应换出，然后把页6 调入内存。OPT 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 块 1 1 1 1 1 1 1 3 3 3 3 6 块 2 2 2 2 2 2 2 7 2 2 2

38、块 3 3 4 5 6 6 6 6 1 1 缺页因此，OPT 算法发生缺页中断的次数为11。在OPT算法中，在最远的将来才被访问的页面被先换出。例如，当页6要调入时，内存的状态为 1、2、5，考查页 6后面要调入的页面，分别为2、1、2、，可见5为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。13.假设一个磁盘有 200 个磁道，编号从 0199。当前磁头正在 143 道上服务，并且刚刚完成了 125 道的请求。如果寻道请求队列的顺序是：86,147,91,177,94,150,102,175,130 问：为完成上述请求，下列算法各自磁头移动的总量是多少？FCFS SSTF 电梯法

39、答案 FCFS为 565；SSTF为 162；电梯法为 125。分析 磁头在 143道上，下一个请求为 86，采用先来先服务磁盘调度算法FCFS，按照请求到来的次序依次响应，于是磁头从143 道移动到 86 道上，移动磁道数为 143-86=57。再从 86 道移动到 147道，依此类推，进行调度的情况为：下一磁道移动磁道数86 147 91 177 57 61 56 86 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 15 页 -94 150 102 175 130 83 56 48 73 45 磁头移动总量为 565。采用最短寻道时间优先磁盘调度算法SSTF，当前磁头在

40、143道上，选择的下一个请求距当前磁头所在位置应具有最小的寻道时间。比较离 143 道最近的两个请求：130和 147，可知，从 143 道移动到 147 道花费的时间最短，仅为4，于是磁头移动到 147 道上。依此类推，进行调度的情况为：下一磁道移动磁道数147 150 130 102 94 91 86 175 177 4 3 20 28 8 3 5 89 2 磁头移动总量为 162。采用电梯磁盘调度算法，要按照磁头移动的方向对请求进行扫描法，一侧的所有请求完成后，才掉头回扫。题中的条件“当前磁头正在 143 道上服务，并且刚刚完成了 125 道的请求”说明磁头移动的方向是从125 道到 143 道。根据电梯法，磁头要继续向数大的方向扫描下去，于是先遇到 147 道的请求，然后是150 道，直到 177 道请求处理完，这时这一侧的请求全部完成了。于是磁头名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 15 页 -掉头回扫，首先碰到130 道的请求，最后处理的是 86 道的请求。具体的调度情况为：下一磁道移动磁道数147 150 175 177 130 102 94 91 86 4 3 25 2 47 28 8 3 5 磁头移动总量为 125。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 15 页 -