闽江学院操作系统课后答案

闽江学院操作系统课后答案 《操作系统,三版,》习解答 第1章习题答案 一、填空 1(计算机系统由 硬件 系统和 软件 系统两大部分组成。 2(按功能划分，软件可分为 系统 软件和 应用 软件两种。 3(操作系统是在 裸机 上加载的第一层软件，是对计算机硬件系统功能的 首次 扩充。 4(操作系统的基本功能是 处理机(包含作业) 管理、 存储 管理、 设备 管理和 文件 管理。 5(在分时和批处理系统结合的操作系统中引入“前台”和“后台”作业的概念，其目的是 改善系统功能，提高处理能力 。 6(分时系统的主要特征为 多路性 、 交互性 、 独立性 和 及时性 。 7(实时系统与分时以及批处理系统的主要区别是 实时性 和 可靠性 。 8(若一个操作系统具有很强的交互性，可同时供多个用户使用，则它应该是 分时 操作系统。 9(如果一个操作系统在用户提交作业后，不提供交互能力，只追求计算机资源的利用率、大吞吐量和作业流程的自动化，则它应该属于 批处理 操作系统。 (采用多道程序技术，能充分发挥 CPU 和 外部设备 并行工作的能力。 10 11. 计算机网络是在 计算机 技术和 通信 技术高度发展基础上相结合的产物。 12. 在计算机网络中，各计算机仍使用 自己的 操作系统，由它管理自身的资源。只有各计算机间进行 信息传递 、以及使用网络中的 可共享资源 时，才会涉及到网络操作系统。 13. 如果一个计算机网络系统，其处理和控制功能被分散在系统的各个计算机上，系统中的所有任务可动态地分配到各个计算机中，使它们并行执行，实现分布处理。这样的系统被称为“ 分布式系统 ”，其上配置的操作系统，被称为“ 分布式操作系统 ”。 二、选择 1(操作系统是一种 B 。 A(通用软件 B(系统软件 C(应用软件 D(软件包 2(操作系统是对 C 进行管理的软件。 A系统软件 B(系统硬件 C(计算机资源 D(应用程序 3(操作系统中采用多道程序设计技术，以提高CPU和外部设备的 A 。 A(利用率 B(可靠性 C(稳定性 D(兼容性 4(计算机系统中配置操作系统的目的是提高计算机的 B 和方便用户使用。 A(速度 B(利用率 C(灵活性 D(兼容性 5( C 操作系统允许多个用户在其终端上同时交互地使用计算机。 A(批处理 B(实时 C(分时 D(多道批处理 6(如果分时系统的时间片一定，那么 D ，响应时间越长。 A(用户数越少 B(内存越少 C(内存越多 D(用户数越多 7. B 不是实时系统的基本特点。 A(安全性 B(公平响应 C(实时性 D(可靠性 三、问答 - 1 - 1(什么是“多道程序设计”技术,它对操作系统的形成起到什么作用, 答:所谓“多道程序设计”技术，即是通过软件的手段，允许在计算机内存中同时存放几道相互独立的作业程序，让它们对系统中的资源进行“共享”和“竞争”，以使系统中的各种资源尽可能地满负荷工作，从而提高整个计算机系统的使用效率。基于这种考虑，计算机科学家开始把CPU、存储器、外部设备以及各种软件都视为计算机系统的“资源”，并逐步设计出一种软件来管理这些资源，不仅使它们能够得到合理地使用，而且还要高效地使用。具有这种功能的软件就是“操作系统”。所以，“多道程序设计”的出现，加快了操作系统的诞生。 2(怎样理解“虚拟机”的概念, 答:拿操作系统来说，它是在裸机上加载的第一层软件，是对计算机硬件系统功能的首次扩充。从用户的角度看，计算机配置了操作系统后，由于操作系统隐蔽了硬件的复杂细节，用户会感到机器使用起来更方便、容易了。这样，通过操作系统的作用使展现在用户面前的是一台功能经过扩展了的机器。这台“机器”不是硬件搭建成的，现实生活中并不存在具有这种功能的真实机器，它只是用户的一种感觉而已。所以，就把这样的机器称为“虚拟机”。 3(对于分时系统，怎样理解“从宏观上看，多个用户同时工作，共享系统的资源;从微观上看，各终端程序是轮流运行一个时间片”, 答:在分时系统中，系统把CPU时间划分成许多时间片，每个终端用户可以使用由一个时间片规定的CPU时间，多个用户终端就轮流地使用CPU。这样的效果是每个终端都开始了自己的工作，得到了及时的响应。也就是说，“从宏观上看，多个用户同时工作，共享系统的资源”。但实际上，CPU在每一时刻只为一个终端服务，即“从微观上看，各终端程序是轮流运行一个时间片”。 4.分布式系统为什么具有健壮性, 答:由于分布式系统的处理和控制功能是分布的，任何站点发生的故障都不会给整个系统造成太大的影响。另外，当系统中的设备出现故障时，可以通过容错技术实现系统的重构，以保证系统的正常运行。这一切都表明分布式系统具有健壮性。 5.为什么嵌入式操作系统必须具有可裁剪性, 答:基于嵌入式应用的多样化，嵌入式操作系统应该面向用户、面向产品、面向应用。它必须有很强的适应能力，能够根据应用系统的特点和要求，灵活配置，方便剪裁，伸缩自如。 第2章习题答案 一、填空 1(进程在执行过程中有三种基本状态，它们是 运行 态、 就绪 态和 阻塞 态。 2(系统中一个进程由 程序 、 数据集合 和 进程控制块(PCB) 三部分组成。 3(在多道程序设计系统中，进程是一个 动 态概念，程序是一个 静 态概念。 4(在一个单CPU系统中，若有5个用户进程。假设当前系统为用户态，则处于就绪状态的用户进程最多有 4 个，最少有 0 个。 注意，题目里给出的是假设当前系统为用户态，这表明现在有一个进程处于运行状态，因此最多有4个进程处于就绪态。也可能除一个在运行外，其他4个都处于阻塞。这时，处于就绪的进程一个也没有。 5(总的来说，进程调度有两种方式，即 不可剥夺 方式和 剥夺 方式。 - 2 - 6(进程调度程序具体负责 中央处理机(CPU)的分配。 7(为了使系统的各种资源得到均衡使用，进行作业调度时，应该注意 CPU忙碌 作业和 I/O忙碌 作业的搭配。 8(所谓系统调用，就是用户程序要调用 操作系统 提供的一些子功能。 9(作业被系统接纳后到运行完毕，一般还需要经历 后备 、 运行 和 完成 三个阶段。 10(假定一个系统中的所有作业同时到达，那么使作业平均周转时间为最小的作业调度算法是 短作业优先 调度算法。 11(进程是程序的 一次执行 过程，程序是进程 赖以存在 的基础。 12. 可以把CPU的指令分为两类，一类是操作系统和用户都能使用的指令，一类是只能由操作系统使用的指令。前者称为“ 非特权 ”指令，后者称为“ 特权 ”指令。 13. 系统调用命令的程序属于操作系统，它应该在 管 态下执行。用户程序只有通过计算机系统提供的“ 访管 ”指令，才能实现由目态转为管态、进而调用这些系统调用命令。 14. 访管指令是一条非特权指令，功能是执行它就会产生一个软中断，促使中央处理机由 目 态转为 管 态，进入操作系统，并处理该中断。 15. 一个进程创建后，系统就感知到它的存在;一个进程撤销后，系统就无法再感知到它。于是，从创建到撤销，这个时间段就是一个进程的“ 生命期 ”。 16. 由于PCB是随着进程的创建而建立，随着进程的撤销而取消的，因此系统是通过PCB来“感知”系统中的进程的，PCB是进程 存在 的唯一。 二、选择 1(在进程管理中，当 C 时，进程从阻塞状态变为就绪状态。 A(进程被调度程序选中 B(进程等待某一事件发生 C(等待的事件出现 D(时间片到 2(在分时系统中，一个进程用完给它的时间片后，其状态变为 A 。 A(就绪 B(等待 C(运行 D(由用户设定 3(下面对进程的描述中，错误的是 D 。 A(进程是动态的概念 B(进程的执行需要CPU C(进程具有生命周期 D(进程是指令的集合 4(操作系统通过 B 对进程进行管理。 A(JCB B(PCB C(DCT D(FCB 5(一个进程被唤醒，意味着该进程 D 。 A(重新占有CPU B(优先级变为最大 C(移至等待队列之首 D(变为就绪状态 6(由各作业JCB形成的队列称为 C 。 A(就绪作业队列 B(阻塞作业队列 C(后备作业队列 D(运行作业队列 7(既考虑作业等待时间，又考虑作业执行时间的作业调度算法是 A 。 A(响应比高者优先 B(短作业优先 C(优先级调度 D(先来先服务 8(作业调度程序从处于 D 状态的队列中选取适当的作业投入运行。 A(就绪 B(提交 C(等待 D(后备 9( A 是指从作业提交系统到作业完成的时间间隔。 A(周转时间 B(响应时间 - 3 - C(等待时间 D(运行时间 10(计算机系统在执行 C 时，会自动从目态变换到管态。 A(P操作 B(V操作 C(系统调用 D(I/O指令 11(进程状态由就绪变为运行，是由于 C 引起的。 A(中断事件 B(进程状态变迁 C(进程调度 D(为作业创建进程 12. 当一个进程处于 D 时，称其为就绪状态。 A(等着读磁盘上的信息 B(等着进入内存 C(等着输入一批数据 D(等着获得CPU的控制权 13. 在操作系统中，处于就绪和阻塞状态的进程都没有占用处理机。当处理机空闲时，正确的操作应该是 B 。 A(就绪和阻塞进程都可以变迁成为运行状态 B(只有就绪进程可以变迁成为运行状态 C(只有阻塞进程可以变迁成为运行状态 D(就绪和阻塞状态的进程都不能变迁成为运行进程 14. 我们把“逻辑上独立的程序，在执行时间上相互重叠，一个程序的执行还没有结束，另一个程序的执行已经开始”的这种特性，称为程序执行的 A 。 A(并发性 B(并行性 C(可执行性 D(可交互性 三、问答 1(在多道程序设计系统中，如何理解“内存中的多个程序的执行过程交织在一起，大家都在走走停停”这样一个现象, 答:在多道程序设计系统中，内存中存放多个程序，它们以交替的方式使用CPU。因此，从宏观上看，这些程序都开始了自己的工作。但由于CPU只有一个，在任何时刻CPU只能执行一个进程程序。所以这些进程程序的执行过程是交织在一起的。也就是说，从微观上看，每一个进程一会儿在向前走，一会儿又停步不前，处于一种“走走停停”的状态之中。 2(什么是“原语”、“特权指令”、“系统调用命令”和“访管指令”,它们之间有无一定的联系, 答:特权指令和访管指令都是CPU指令系统中的指令，只是前者是一些只能在管态下执行的指令，后者是一条只能在目态下执行的指令。原语和系统调用命令都是操作系统中的功能程序，只是前者执行时不能被其他程序所打断，后者没有这个要求。操作系统中有些系统调用命令是以原语的形式出现的，例如创建进程就是一条原语式的系统调用命令。但并不是所有系统调用命令都是原语。因为如果那样的话，整个系统的并发性就不可能得到充分地发挥。 3(操作系统是如何处理源程序中出现的系统调用命令的, 答:编译程序总是把源程序中的系统调用命令改写成为一条访管指令和相应的参数。这样在程序实际被执行时，就通过访管指令进入操作系统，达到调用操作系统功能子程序的目的。 4(系统调用与一般的过程调用有什么区别, 答:系统调用是指在用户程序中调用操作系统提供的功能子程序;一般的过程调用是指在一个程序中调用另一个程序。因此它们之间有如下三点区别。 (1)一般的过程调用，调用者与被调用者都运行在相同的CPU状态，即或都处于目态(用户程序调用用户程序)，或都处于管态(系统程序调用系统程序);但发生系统调用 - 4 - 时，发出调用命令的调用者运行在目态，而被调用的对象则运行在管态，即调用者与被调用者运行在不同的CPU状态。 (2)一般的过程调用，是直接通过转移指令转向被调用的程序;但发生系统调用时，只能通过访管指令提供的一个统一的入口，由目态进入管态，经分析后，才转向相应的操作系统命令处理程序。 (3)一般的过程调用，在被调用者执行完后，就径直返回断点继续执行;但系统调用可能会导致进程状态的变化，从而引起系统重新分配处理机。因此，系统调用处理结束后，不一定是返回调用者断点处继续执行。 5(试述创建进程原语的主要功能。 答:创建进程原语的主要功能有以下三项。 (1)为新建进程申请一个PCB。 (2)将创建者(即父进程)提供的新建进程的信息填入PCB中。 (3)将新建进程设置为就绪状态，并按照所采用的调度算法，把PCB排入就绪队列中。 6(处于阻塞状态的一个进程，它所等待的事件发生时，就把它的状态由阻塞改变为就绪，让它到就绪队列里排队，为什么不直接将它投入运行呢, 答:只要是涉及管理，就应该有管理的，没有规则就不成方圆。如果处于阻塞状态的一个进程，在它所等待的事件发生时就径直将它投入运行(也就是把CPU从当前运行进程的手中抢夺过来)，那么系统就无法控制对CPU这种资源的管理和使用，进而也就失去了设置操作系统的作用。所以，阻塞状态的进程在它所等待的事件发生时，必须先进入就绪队列，然后再去考虑它使用CPU的问题。 (作业调度与进程调度有什么区别, 7 答:作业调度和进程调度(即CPU调度)都涉及到CPU的分配。但作业调度只是选择参加CPU竞争的作业，它并不具体分配CPU。而进程调度是在作业调度完成选择后的基础上，把CPU真正分配给某一个具体的进程使用。 8(系统中的各种进程队列都是由进程的PCB链接而成的。当一个进程的状态从阻塞变为就绪状态时，它的PCB从哪个队列移到哪个队列,它所对应的程序也要跟着移来移去吗,为什么, 答:当一个进程的状态从阻塞变为就绪时，它的PCB就从原先在的阻塞队列移到就绪队列里。在把进程的PCB从这个队列移到另一个队列时，只是移动进程的PCB，进程所对应的程序是不动的。这是因为在进程的PCB里，总是记录有它的程序的断点信息。知道了断点的信息，就能够知道程序当前应该从哪里开始往下执行了。这正是保护现场所起的作用。 9(为什么说响应比高者优先作业调度算法是对先来先服务以及短作业优先这两种调度算法的折中, 答:先来先服务的作业调度算法，重点考虑的是作业在后备作业队列里的等待时间，因此对短作业不利;短作业优先的作业调度算法，重点考虑的是作业所需的CPU时间(当然，这个时间是用户自己估计的)，因此对长作业不利。“响应比高者优先”作业调度算法，总是在需要调度时，考虑作业已经等待的时间和所需运行时间之比，即: 该作业已等待时间 / 该作业所需CPU时间 不难看出，这个比值的分母是一个不变的量。随着时间的推移，一个作业的“已等待时间”会不断发生变化，也就是分子在不断地变化。显然，短作业比较容易获得较高的响应比。这是因为它的分母较小，只要稍加等待，整个比值就会很快上升。另一方面，长作业的分母虽然很大，但随着它等待时间的增加，比值也会逐渐上升，从而获得较高的响应比。根据这种分析，可见“响应比高者优先”的作业调度算法，既照顾到了短作业的利益，也照顾到了 - 5 - 长作业的利益，是对先来先服务以及短作业优先这两种调度算法的一种折中。 10(短作业优先调度算法总能得到最小的平均周转时间吗,为什么, 答:短作业优先调度算法只有在所有作业同时到达后备作业队列时，才能得到最小的平均周转时间。如果各作业不是同时到达，这个结论是不成立的。可以用反例说明，例如，教材上举有如下例子:考虑有5个作业A到E，运行时间分别是2、4、1、1、1;到达时间分别是0、0、3、3、3。按照短作业优先的原则，最初只有A和B可以参与选择，因为其他3 、个还没有到达。于是，运行顺序应该是A、B、C、D、E。它们每个的周转时间分别是2、64、5、6，平均周转时间是4.6。但如果按照顺序B、C、D、E、A来调度，它们每一个的周转时间成为9、4、2、3、4，平均周转时间是4.4。结果比短作业优先调度算法好。之所以会这样，就是因为这5个作业并没有同时到达。 11. 什么是“系统进程”、什么是“用户进程”,它们有何区别, 答:在多道程序设计系统中，既运行着操作系统程序，又运行着用户程序，因此整个系统中存在着两类进程，一类是系统进程，一类是用户进程。操作系统中用于管理系统资源的那些并发程序，形成了一个个系统进程，它们提供系统的服务，分配系统的资源;可以并发执行的用户程序段，形成了一个个用户进程，它们是操作系统的服务对象，是系统资源的实际的享用者。可以看出，这是两类不同性质的进程，主要区别如下。 (1)系统进程之间的相互关系由操作系统负责协调，以便有利于增加系统的并行性，提高资源的整体利用率;用户进程之间的相互关系要由用户自己(在程序中)安排。不过，操作系统会向用户提供一定的协调手段(以命令的形式)。 (2)系统进程直接管理有关的软、硬件资源的活动;用户进程不得插手资源管理。在需要使用某种资源时，必须向系统提出申请，由系统统一调度与分配。 (3)系统进程与用户进程都需要使用系统中的各种资源，它们都是资源分配与运行调度的独立单位，但系统进程的使用级别，应该高于用户进程。也就是说，在双方出现竞争时，系统进程有优先获得资源、优先得以运行的权利。只有这样，才能保证计算机系统高效、有序的工作。 12. 给定n个作业J、J、„„J，它们各自的运行时间为t、t、„„t，且满足关系:12n12nt?t?„„?t，假定这些作业同时到达系统，并在CPU上按单道方式运行。试问: 12n (1)采用何种调度算法，能使平均周转时间为最小, (2)给出这批作业最短平均周转时间的计算式。 答:(1)采用短作业优先调度算法。 (2)这批作业最短平均周转时间的计算式为: T=[T+T+„+T]/=[t+(t+t)+(t+t+t)+„+(t+t+„t+t)]/ 12nn11212312n-1nn 四、计算 1(有三个作业: 作 业 到达时间 所需CPU时间 1 0.0 8 2 0.4 4 3 1.0 1 分别采用先来先服务和短作业优先作业调度算法。试问它们的平均周转时间各是什么,你是否还可以给出一种更好的调度算法，使其平均周转时间优于这两种调度算法, 解:(1)采用先来先服务作业调度算法时的实施过程如下。 - 6 - 作 业 到达时间 开始时间 完成时间 周转时间 所需CPU时间 1 0.0 8 0.0 8.0 8.0 2 0.4 4 8.0 12.0 11.6 3 1.0 1 12.0 13.0 12.0 这时，作业的调度顺序是1?2?3。其平均周转时间为: (8 + 11.6 + 12)/ 3 = 10.53 (2)采用短作业优先作业调度算法时的实施过程如下。 作 业 到达时间 开始时间 完成时间 周转时间 所需CPU时间 1 0.0 8 0.0 8.0 8.0 3 1.0 1 8.0 9.0 8.0 2 0.4 4 9.0 13.0 12.6 这里要注意，在作业1运行完毕进行作业调度时，作业2和3都已经到达。由于是实行短作业优先作业调度算法，因此先调度作业3运行，最后调度作业2运行。所以，这时的作业调度顺序是1?3?2。其平均周转时间为: (8 + 8 + 12.6)/ 3 = 9.53 (3)还可以有更好的作业调度算法，使其平均周转时间优于这两种调度算法。例如，如果知道在作业1后面会来两个短作业，那么作业1到达后，先不投入运行。而是等所有作业到齐后，再按照短作业优先作业调度算法进行调度，具体实施过程如下。 作 业 到达时间 开始时间 完成时间 周转时间 所需CPU时间 3 1.0 1 1.0 2.0 1.0 2 0.4 4 2.0 6.0 5.6 1 0.0 8 6.0 14.0 14.0 这时的作业调度顺序是3?2?1。其平均周转时间为: (1 + 5.6 + 14)/ 3 = 6.87 2(设有一组作业，它们的到达时间和所需CPU时间如下所示。 作业号 到达时间 所需CPU时间 1 9:00 70分钟 2 9:40 30分钟 3 9:50 10分钟 4 10:10 5分钟 分别采用先来先服务和短作业优先作业调度算法。试问它们的调度顺序、作业周转时间以及平均周转时间各是什么, - 7 - 解:(1)采用先来先服务作业调度算法时的实施过程如下。 作业号 到达时间 开始时间 完成时间 周转时间 所需CPU时间 1 9:00 70分钟 9:00 10:10 70分钟 2 9:40 30分钟 10:10 10:40 60分钟 3 9:50 10分钟 10:40 10:50 60分钟 4 10:10 5分钟 10:50 10:55 45分钟 这时，作业的调度顺序是1?2?3?4。其平均周转时间为: (70 + 60 + 60 + 45)/ 4 = 58.75 (2)采用短作业优先作业调度算法时的实施过程如下。 作业号 到达时间 开始时间 完成时间 周转时间 所需CPU时间 1 9:00 70分钟 9:00 10:10 70分钟 4 10:10 5分钟 10:10 10:15 5分钟 3 9:50 10分钟 10:15 10:25 35分钟 2 9:40 30分钟 10:25 10:55 75分钟 这时，作业的调度顺序是1?4?3?2。其平均周转时间为: (70 + 5 + 35 + 75)/ 4 = 46.25 (某系统有三个作业: 3 作业号 到达时间 所需CPU时间 1 8.8 1.5 2 9.0 0.4 3 9.5 1.0 系统确定在它们全部到达后，开始采用响应比高者优先调度算法，并忽略系统调度时间。试问对它们的调度顺序是什么,各自的周转时间是多少, 解:三个作业是在9.5时全部到达的。这时它们各自的响应比如下: 作业1的响应比 =(9.5 – 8.8)/ 1.5 = 0.46 作业2的响应比 =(9.5 – 9.0)/ 0.4 = 1.25 作业3的响应比 =(9.5 – 9.5)/ 1.0 = 0 因此，最先应该调度作业2运行，因为它的响应比最高。它运行了0.4后完成，这时的时间是9.9。再计算作业1和3此时的响应比: 作业1的响应比 =(9.9 – 8.8)/ 1.5 = 0.73 作业3的响应比 =(9.9 – 9.5)/ 1.0 = 0.40 因此，第二个应该调度作业1运行，因为它的响应比最高。它运行了1.5后完成，这时的时间是11.4。第三个调度的是作业3，它运行了1.0后完成，这时的时间是12.4。整个实施过程如下。 - 8 - 作业号 到达时间 开始时间 完成时间 周转时间 所需CPU时间 2 9.0 0.4 9.5 9.9 0.9 1 8.8 1.5 9.9 11.4 2.6 3 9.5 1.0 11.4 12.4 2.9 作业的调度顺序是2?1?3。各自的周转时间为:作业1为0.9;作业2为2.6;作业3为2.9。 第3章习题答案 一、填空 1(将作业相对地址空间的相对地址转换成内存中的绝对地址的过程称为 地址重定位 。 2(使用覆盖与对换技术的主要目的是 提高内存的利用率 。 3(存储管理中，对存储空间的浪费是以 内部碎片 和 外部碎片 两种形式表现出来的。 4(地址重定位可分为 静态重定位 和 动态重定位 两种方式。 (在可变分区存储管理中采用最佳适应算法时，最好按 尺寸 法来组织空闲分区5 链表。 6(在分页式存储管理的页表里，主要应该包含 页号 和 块号 两个信息。 7(静态重定位在程序 装入 时进行，动态重定位在程序 执行 时进行。 8(在分页式存储管理中，如果页面置换算法选择不当，则会使系统出现 抖动 现象。 9(在请求分页式存储管理中采用先进先出(FIFO)页面淘汰算法时，增加分配给作业的块数时， 缺页中断 的次数有可能会增加。 10(在请求分页式存储管理中，页面淘汰是由于 缺页 引起的。 二、选择 1(虚拟存储器的最大容量是由 B 决定的。 A(内、外存容量之和 B(计算机系统的地址结构 C(作业的相对地址空间 D(作业的绝对地址空间 2(采用先进先出页面淘汰算法的系统中，一进程在内存占3块(开始为空)，页面访问序列为1、2、3、4、1、2、5、1、2、3、4、5、6。运行时会产生 D 次缺页中断。 A(7 B(8 C(9 D(10 从图中的“缺页计数”栏里可以看出应该选择D。 1 2 3 4 1 2 5 1 2 3 4 5 6 页面走向? 1 2 3 4 1 2 5 5 5 3 4 4 6 1 2 3 4 1 2 2 2 5 3 3 4 3个内存块? 5 1 2 3 4 1 1 3 1 2 5 缺页计数缺页计数?? ? ? ? ? ? ? ? ? ? ? 3(系统出现“抖动”现象的主要原因是由于 A 引起的。 A(置换算法选择不当 B(交换的信息量太大 - 9 - C(内存容量不足 D(采用页式存储管理策略 4(实现虚拟存储器的目的是 D 。 A(进行存储保护 B(允许程序浮动 C(允许程序移动 D(扩充主存容量 5(作业在执行中发生了缺页中断，那么经中断处理后，应返回执行 B 指令。 A(被中断的前一条 B(被中断的那条 C(被中断的后一条 D(程序第一条 6(在实行分页式存储管理系统中，分页是由 D 完成的。 A(程序员 B(用户 C(操作员 D(系统 7(下面的 A 页面淘汰算法有时会产生异常现象。 A(先进先出 B(最近最少使用 C(最不经常使用 D(最佳 8(在一个分页式存储管理系统中，页表的内容为: 页号 块号 0 2 1 1 2 7 若页的大小为4KB，则地址转换机构将相对地址0转换成的物理地址是 A 。 8192 B(4096 C(2048 D(1024 A( 注意，相对地址0肯定是第0页的第0个字节。查页表可知第0页存放在内存的第2块。现在块的尺寸是4KB，因此第2块的起始地址为8192。故相对地址0所对应的绝对地址(即物理地址)是8192。 9(下面所列的存储管理中， A 实行的不是动态重定位。 A(固定分区 B(可变分区 C(分页式 D(请求分页式 10(在下面所列的诸因素中，不对缺页中断次数产生影响的是 C 。 A(内存分块的尺寸 B(程序编制的质量 C(作业等待的时间 D(分配给作业的内存块数 11.在分段式存储管理中，是由用户实施分段的。因此 B 。 A.段内和各段间的地址都是连续的 B.段内的地址是连续的，各段间的地址可以不连续 C.段内的地址可以不连续，但段间的地址是连续的 D.段内的地址和各段间的地址都是不连续的 12.一个分段式存储管理系统，地址用24位表示，其中8位表示段号。那么每段的最大长度应该是 B 。 2416832 A.2 B.2 C.2 D.2 三、问答 1(什么是内部碎片,什么是外部碎片,各种存储管理中都可能产生何种碎片, 答:所谓“内部碎片”，是指系统已经分配给用户使用、用户自己没有用到的那部分存储空间;所谓“外部碎片”，是指系统无法把它分配出去供用户使用的那部分存储空间。对于教材而言，单一连续区存储管理、固定分区存储管理、分页式存储管理和请求页式存储管理都会出现内部碎片。只是前两种存储管理造成的内部碎片比较大，浪费较为严重;后两种页式存储管理，平均来说每个作业都会出现半页的内部碎片。教材中，只有可变分区存储管 - 10 - 理会产生外部碎片。 2(叙述静态重定位与动态重定位的区别。 答:静态重定位是一种通过软件来完成的地址重定位技术。它在程序装入内存时，完成对程序指令中地址的调整。因此，程序经过静态重定位以后，在内存中就不能移动了。如果要移动，就必须重新进行地址重定位。 动态重定位是一种通过硬件支持完成的地址重定位技术。作业程序被原封不动地装入内存。只有到执行某条指令时，硬件地址转换机构才对它里面的地址进行转换。正因为如此，实行动态重定位的系统，作业程序可以在内存里移动。也就是说，作业程序在内存中是可浮动的。 3(一个虚拟地址结构用24个二进制位表示。其中12个二进制位表示页面尺寸。试问这种虚拟地址空间总共多少页,每页的尺寸是多少, 答:如下图所示，由于虚拟地址中是用12个二进制位表示页面尺寸(即页内位移)，所以虚拟地址空间中表示页号的也是12个二进制位。这样，这种虚拟地址空间总共有: 12 2 = 4096(页) 每页的尺寸是: 12 2 = 4096 = 4K(字节) 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 页号 页内位移 虚拟地址 4(什么叫虚拟存储器,怎样确定虚拟存储器的容量, 答:虚拟存储器实际是一种存储扩充技术。它把作业程序存放在辅助存储器里，运行时只装入程序的一部分。遇到不在内存的程序时，再把所需要的部分装入。这样在内存和辅存之间调入、调出的做法，使用户的作业地址空间无需顾及内存的大小。给用户造成的印象是，无论程序有多大，它在这个系统上都可以运行。这种以辅助存储器作为后援的虚幻存储器，就称为虚拟存储器。虚拟存储器的大小是由系统的地址结构确定的。 (为什么请求分页式存储管理能够向用户提供虚拟存储器, 5 答:请求分页式存储管理的基本思想是:操作系统按照存储块的尺寸，把用户作业地址空间划分成页，全部存放在磁盘上。作业运行时，只先装入若干页。运行过程中遇到不在内存的页时，操作系统就把它从磁盘调入内存。这样一来，用户的作业地址空间无需顾及内存的大小。这与虚拟存储器的思想是完全吻合的。所以，请求分页式存储管理能够向用户提供虚拟存储器。 6(在请求分页式存储管理中，为什么既有页表，又有快表, 答:在分页式或请求页式存储管理中，通常是利用内存储器构成页表的。当CPU执行到某条指令、要对内存中的某一地址访问时，因为这个地址是相对地址，所以先要根据这个地址所在的页号去查页表(访问一次内存)，然后才能由所形成的绝对地址去真正执行指令(第二次访问内存)。可见，由于页表在内存，降低了CPU的访问速度。 为了提高相对地址到绝对地址的变换速度，人们想到用一组快速寄存器来代替页表。这时查页表是以并行的方式进行，立即就能输出与该页号匹配的块号，这样做无疑比内存式的页表要快得多。但是，快速寄存器的价格昂贵，由它来组成整个页表是不可取的。考虑到程序运行时具有局部性，因此实际系统中总是一方面采用内存页表、另一方面用极少几个快速寄存器组成快表来共同完成地址的变换工作。这时的地址变换过程，如教材中的图3-22所示。 7(试述缺页中断与页面淘汰之间的关系。 - 11 - 答:在请求页式存储管理中，当根据虚拟地址查页表而发现所要访问的页不在内存时，就会产生缺页中断。系统响应中断后，就由操作系统到辅存把所需要的页读入内存。这时，内存可能有空闲的块，也可能没有。只有当内存中没有空闲块时，才会出现将内存现有页面淘汰出去的问题，即要进行页面淘汰。所以，缺页中断和页面淘汰之间的关系是:页面淘汰一定是由缺页中断所引起;但缺页中断则不一定引起页面淘汰。 8(试述缺页中断与一般中断的区别。 答:在计算机系统中，由于某些事件的出现，打断了当前程序的运行，而使CPU去处理出现的事件，这称为“中断”。通常，计算机的硬件结构都是在执行完一条指令后，去检查有无中断事件发生的。如果有，那么就暂停当前程序的运行，而让CPU去执行操作系统的中断处理程序，这叫“中断响应”。CPU在处理完中断后，如果不需要对CPU重新进行分配，那么就返回被中断进程的程序继续运行;如果需要进行CPU的重新分配，那么操作系统就会去调度新进程。 由上面的讲述可以看出，缺页中断与一般中断的区别如下。 (1)两种中断产生的时刻不同:缺页中断是在执行一条指令中间时产生的中断，并立即转去处理;而一般中断则是在一条指令执行完毕后，当硬件中断装置发现有中断请求时才去响应和处理。 (2)处理完毕后的归属不同:缺页中断处理完后，仍返回到原指令去重新执行，因为那条指令并未执行;而一般中断则是或返回到被中断进程的下一条指令去执行，因为上一条指令已经执行完了，或重新调度，去执行别的进程程序。 9(怎样理解把相对地址划分成数对:(页号，页内位移)的过程对于用户是“透明”的, 答:在操作系统中，所谓“透明”，即指用户不知道的意思。对于分页式存储管理来说，用户向系统提供的相对地址空间，是一个一维的连续空间。系统接受了这个作业后，在内部把这个相对地址空间划分成若干页。由于这种划分对于用户来说是根本不知道的，所以说把相对地址划分成数对:(页号，页内位移)的过程对于用户是“透明”的。 (做一个综述，说明从单一连续区存储管理到固定分区存储管理，到可变分区存储管10 理，到分页式存储管理和分段式存储管理，再到请求分页式存储管理，每一种存储管理的出现，都是在原有基础上的发展和提高。 单道答:教材共介绍了6种存储管理策略，它们单一连续分区存储管理 适用于不同的场合，如图所示。图中，在单一连固定分区存储管理多道连续续分区存储管理与固定分区存储管理之间画了一可变分区存储管理条线，表明位于线以上的存储管理策略只适用于分页式、分段式存储管理不连续单道程序设计，位于以下存储管理策略都适用于全部多道程序设计;在可变分区存储管理与分页式、请求分页式存储管理分段式存储管理之间画了一条线，表明位于线以部分 上的存储管理策略都要求为进入内存的作业分配各种存储管理策略的适用场合 一个连续的存储区，以下的存储管理策略打破了 连续性的要求;在分页式、分段式存储管理与请求页式存储管理之间画了一条线，表明位于线以上的存储管理策略都要求使作业程序全部进入内存，而以下的存储管理策略打破了全部的要求，只要部分装入内存就可以了。 可见，每一种新存储管理策略的出现，都是在原有存储管理基础上的一次发展和提高。它们从简单到复杂，从不完善到逐渐完善。 11. 利用伙伴系统分配一个1MB的内存区域，存储请求和释放的序列为:请求A(70KB)、请求B(35KB)、请求C(80KB)、释放A、请求D(60KB)、释放B、释放D、释放C。画出类似于图3-20的图。 - 12 - 答:结果如下图所示。 四、计算 1(在可变分区存储管理中，按地址法组织当前的空闲分区，其大小分别为:10KB，4KB，20KB，18KB，7KB，9KB，12KB和15KB。现在依次有3个存储请求为:12KB，10KB，9KB。试问使用最先适应算法时的分配情形如何,那么最佳适应、最坏适应呢, 解:我们用表来说明实行各种分配算法时的情形。 (1)最先适应算法 请求队列 最先适应算法 初始 10K 4K 20K 18K 7K 9K 12K 15K 12K 10K 4K 8K 18K 7K 9K 12K 15K 10K 0 4K 8K 18K 7K 9K 12K 15K 9K 0 4K 8K 9K 7K 9K 12K 15K (2)最佳适应算法 请求队列 最佳适应算法 初始 10K 4K 20K 18K 7K 9K 12K 15K 12K 10K 4K 20K 18K 7K 9K 0 15K 10K 0 4K 20K 18K 7K 9K 0 15K 9K 0 4K 20K 18K 7K 0 0 15K (3)最坏适应算法 请求队列 最坏适应算法 初始 10K 4K 20K 18K 7K 9K 12K 15K 12K 10K 4K 8K 18K 7K 9K 12K 15K 10K 10K 4K 8K 8K 7K 9K 12K 15K 9K 10K 4K 8K 8K 7K 9K 12K 6K 可见，分配算法不同，选择的分配对象也不一样。 2(系统内存被划分成8块，每块4KB。某作业的虚拟地址空间共划分成16个页面。 - 13 - 当前在内存的页与内存块的对应关系如下表所示，未列出的页表示不在内存。 页 号 块 号 页 号 块 号 0 2 4 4 1 1 5 3 2 6 9 5 3 0 11 7 试指出对应于下列虚拟地址的绝对地址: (a)20 (b)4100 (c)8300 解:(a)虚拟地址20对应的页号是0，页内位移是20。用0去查页表，知道第0页现在存放在内存的第2块。由于每块的长度是4KB，所以第2块的起始地址为8192。因此，虚拟地址20所对应的绝对地址是: 8192+20=8212 (b)虚拟地址4100对应的页号是: 4100/4096=1(“/”是整除运算符) 对应的页内位移是: 4100%4096=4(“%”是求余运算符) 用1去查页表，知道第1页现在存放在内存的第1块。第1块的起始地址为4096。因此，虚拟地址4100所对应的绝对地址是: 4096+4=4100 (c)虚拟地址8300对应的页号是: 8300/4096=2(“/”是整除运算符) 对应的页内位移是: 8300%4096=108(“%”是求余运算符) 用2去查页表，知道第2页现在存放在内存的第6块。第6块的起始地址为 6×4K=24576 因此，虚拟地址8300所对应的绝对地址是 24576+108=24684 3(某请求分页式存储管理系统，接收一个共7页的作业。作业运行时的页面走向如下: 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 若采用最近最久未用(LRU)页面淘汰算法，作业在得到2块和4块内存空间时，各会产生出多少次缺页中断,如果采用先进先出(FIFO)页面淘汰算法时，结果又如何, 解:(1)采用最近最久未用(LRU)页面淘汰算法，作业在得到2块内存空间时所产生的缺页中断次数为18次，如图(a)所示;在得到4块内存空间时所产生的缺页中断次数为10次，如图(b)所示。 - 14 - 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 2 3 6 1 页面走向? 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 3 1 2 6 ? 2个内存块1 2 3 4 5 6 2 1 6 3 2 3 1 2 3 7 2 2 1 缺页计数?? 缺页计数? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (a) 2块时的LRU 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页面走向? 1 3 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 2 6 2 2 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 3 1 ? 4个内存块3 1 1 2 3 4 2 1 5 6 6 1 2 3 7 6 2 3 6 1 1 3 4 2 1 5 5 6 1 2 2 7 6 1 6 缺页计数?? 缺页计数? ? ? ? ? ? ? ? ? ? (b) 4块时的LUR 图 LRU时的情形 (2)采用先进先出(FIFO)页面淘汰算法，作业在得到2块内存空间时所产生的缺页中断次数为18次，如图(a)所示;在得到4块内存空间时所产生的缺页中断次数为14次，如图(b)所示。 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 3 2 6 1 页面走向? 1 2 3 4 2 1 5 6 2 1 1 3 7 6 3 2 1 3 6 1 ? 2个内存块1 2 3 4 5 6 2 2 6 3 2 3 2 2 3 7 1 1 1 缺页计数?? 缺页计数? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (a) 2块时的FIFO 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 2 1 3 6 页面走向? 1 3 1 2 3 4 4 4 5 6 2 1 1 3 7 6 6 2 1 3 2 1 1 2 3 3 3 4 5 6 2 2 1 3 7 7 6 2 1 ? 4个内存块6 2 1 2 2 2 3 4 5 6 6 2 1 3 3 7 6 2 7 6 1 1 1 2 3 4 5 5 6 2 1 1 3 7 6 缺页计数?? 缺页计数? ? ? ? ? ? ? ? ? ? ? ? ? (b) 4块时的FIFO 图 FIFO时的情形 关于先进先出(FIFO)页面淘汰算法，在给予作业更多的内存块时，缺页中断次数有可能上升，这是所谓的异常现象。但要注意，并不是在任何情况下都会出现异常。是否出现异常，取决于页面的走向。本题所给的页面走向，在FIFO页面淘汰算法下，并没有引起异常:2块时缺页中断次数为18次，4块时缺页中断次数为14次。 4.有段表如下所示。已知逻辑地址:(1)[0，430];(2)[3，400];(3)[1，10];(4)[2，2500];(5)[4，42];(6)[1，11]。求它们所对应的物理地址。 段号 段长 段基址 0 600 219 1 14 2300 2 100 90 3 580 1327 4 96 1954 解:(1)物理地址为:219+430=649;(2)物理地址为:1327+400=1727; (3)物理地址为:2300+10=2310;(4)第2段的段长为100，现在逻辑地址中的段内位移2500超出段长，发生越界错;(5)物理地址为:1954+42=1996;(6)物理地址为: - 15 - 2300+11=2311。 第4章习题答案 一、填空 1. I/O设备一般由机械和电子两个部分组成。为了使设计更加模块化、更具通用性，也为了降低设计制作的成本，如今常把它们分开来处理:电子部分称作是“ 设备控制器 ”;机械部分被称作是“ 设备 ”。 2(磁带、磁盘这样的存储设备都是以 块 为单位与内存进行信息交换的。 3(以用户作业发出的磁盘I/O请求的柱面位置，决定请求执行顺序的调度，称为 移臂 调度。 4(DMA控制器在获得总线控制权的情况下能直接与 内存储器 进行数据交换，无需CPU介入。 5(在DMA方式下，设备与内存储器之间进行的是 成批 数据传输。 6(通道程序是由 通道 执行的。 7(通道是一个独立于CPU的、专门用来管理 输入/输出操作 的处理机。 8(缓冲的实现有两种方法:一种是采用专门硬件寄存器的硬件缓冲，一种是在内存储器里开辟一个区域，作为专用的I/O缓冲区，称为 软件缓冲 。 (设备管理中使用的数据结构有系统设备表(SDT)和 设备控制块(DCB) 。 9 10(基于设备的分配特性，可以把系统中的设备分为独享、共享和 虚拟 三种类型。 11(引起中断发生的事件称为 中断源 。 二、选择 1(在对磁盘进行读/写操作时，下面给出的参数中， C 是不正确的。 A( 柱面号 B(磁头号 C(盘面号 D(扇区号 2(在设备管理中，是由 B 完成真正的I/O操作的。 A(输入/输出管理程序 B(设备驱动程序 C(中断处理程序 D(设备启动程序 3(在下列磁盘调度算法中，只有 D 考虑I/O请求到达的先后次序。 A(最短查找时间优先调度算法 B(电梯调度算法 C(单向扫描调度算法 D(先来先服务调度算法 4(下面所列的内容里， C 不是DMA方式传输数据的特点。 A(直接与内存交换数据 B(成批交换数据 C(与CPU并行工作 D(快速传输数据 (在CPU启动通道后，由 A 执行通道程序，完成CPU所交给的I/O任务。 5 A( 通道 B(CPU C(设备 D(设备控制器 6(利用SPOOL技术实现虚拟设备的目的是 A 。 A(把独享的设备变为可以共享 B(便于独享设备的分配 C(便于对独享设备的管理 D(便于独享设备与CPU并行工作 7(通常，缓冲池位于 C 中。 A(设备控制器 B(辅助存储器 C(主存储器 D(寄存器 8( B 是直接存取的存储设备。 A(磁带 B(磁盘 C(打印机 D(键盘显示终端 - 16 - 9(SPOOLING系统提高了 A 的利用率。 A(独享设备 B(辅助存储器 C(共享设备 D(主存储器 10(按照设备的 D 分类，可将系统中的设备分为字符设备和块设备两种。 A(从属关系 B(分配特性 C(操作方式 D(工作特性 11. 所谓“设备无关性”，是指 B 。 A(I/O设备具有独立执行I/O功能的特性 B(用户程序中使用的设备名与具体的物理设备无关 C(设备驱动程序与具体的物理设备无关 D(系统能够独立地实现设备共享 三、问答 1(基于设备的从属关系，可以把设备分为系统设备与用户设备两类。根据什么来区分一个设备是系统设备还是用户设备呢, 答:所谓“系统设备”，是指在操作系统生成时就已被纳入系统管理范围的设备;所谓“用户设备”是指在完成应用任务过程中，用户特殊需要的设备。因此，判定一个设备是系统设备还是用户设备，依据是它在系统生成时，是否已经纳入了系统的管理范围。如果是，它就是系统设备;如果不是，它就是用户设备。 2(设备管理的主要功能是什么, 答:设备管理的主要功能是:(1)提供一组I/O命令，以便用户进程能够在程序中提出I/O请求，这是用户使用外部设备的“界面”;(2)记住各种设备的使用情况，实现设备的 )对缓冲区进行管理，解决设备与设备之间、设备与CPU之间的速度匹配分配与回收;(3 问题;(4)按照用户的具体请求，启动设备，通过不同的设备驱动程序，进行实际的I/O操作;I/O操作完成之后，将结果通知用户进程，从而实现真正的I/O操作。 3(试分析最短查找时间优先调度算法的“不公平”之处。比如，例4-1里原来磁臂移到16柱面后，下一个被处理的I/O请求是柱面1。假定在处理16柱面时，到达一个对柱面8的I/O新请求，那么下一个被处理的就不是柱面1而是柱面8了。这有什么弊端存在, 答:最短查找时间优先调度算法，只考虑各I/O请求之间的柱面距离，不去过问这些请求到达的先后次序。这样一来，可能会出现的弊端是磁头总是关照邻近的I/O请求，冷待了早就到达的、位于磁盘两头的I/O请求。这对于它们来说，当然是“不公平”的。 4(总结设备和CPU在数据传输的4种方式中，各自在“启动、数据传输、I/O管理以及善后处理”各个环节所承担的责任。 答:使用“程序循环测试”的方式来进行数据传输，不仅启动、I/O管理和善后处理等工作要由CPU来承担，即使在数据传输时，CPU也要做诸如从控制器的数据寄存器里取出设备的输入信息，送至内存;将输出的信息，从内存送至控制器的数据寄存器，以供设备输出等工作。因此，在这种方式下，CPU不仅要花费大量时间进行测试和等待，并且只能与设备串行工作，整个计算机系统的效率发挥不出来。 使用“中断”的方式来进行数据传输，启动、I/O管理以及善后处理等工作仍然要由CPU来承担，但在设备进行数据传输时，CPU和外部设备实行了并行工作。在这种方式下，CPU的利用率有了一定的提高。 使用“直接存储器存取(DMA)”的方式来进行数据传输，I/O的启动以及善后处理是CPU的事情，数据传输以及I/O管理等事宜均由DMA负责实行。不过，DMA方式是通过“窃取”总线控制权的办法来工作的。在它工作时，CPU被挂起，所以并非设备与CPU在并行工作。因此，在一定程度上影响了CPU的效率。 使用“通道”方式来进行数据传输，在用户发出I/O请求后，CPU就把该请求全部交由 - 17 - 通道去完成。通道在整个I/O任务结束后，才发出中断信号，请求CPU进行善后处理。这时CPU对I/O请求只去做启动和善后处理工作，输入/输出的管理以及数据传输等事宜，全部由通道独立完成，并且真正实现了CPU与设备之间的并行操作。 5(用户程序中采用“设备类，相对号”的方式使用设备有什么优点, 答:在用户程序中采用“设备类，相对号”的方式使用设备的优点是:第一，用户不需要记住系统中每一台设备的具体设备号，这是非常麻烦的事情;第二，在多道程序设计环境下，用户并不知道当前哪一台设备已经分配，哪一台设备仍然空闲。通过“设备类，相对号”来提出对设备的使用请求，系统就可以根据当前的具体情况来分配，从而提高设备的使用效率;第三，用户并不知道设备的好坏情况。如果是用“绝对号”指定具体的设备，而该设备正好有故障时，这次I/O任务就不可能完成，程序也就无法运行下去。但通过“设备类，相对号”来提出对设备的使用请求，系统就可以灵活处理这种情况，把好的设备分配出去。 6(启动磁盘执行一次输入/输出操作要花费哪几部分时间,哪个时间对磁盘的调度最有影响, 答:执行一次磁盘的输入/输出操作需要花费的时间包括三部分:(1)查找时间;(2)等待时间;(3)传输时间。在这些时间中，传输时间是设备固有的特性，无法用改变软件的办法将它改进。因此，要提高磁盘的使用效率，只能在减少查找时间和等待时间上想办法，它们都与I/O在磁盘上的分布位置有关。由于磁臂的移动是靠控制电路驱动步进电机来实现，它的运动速度相对于磁盘轴的旋转来讲较缓慢。因此，查找时间对磁盘调度的影响更为主要。 7(解释“通道命令字”、“通道程序”和“通道地址字”三者的含义。 答:所谓“通道命令字”，是指通道指令系统中的指令。只是为了与CPU的指令相区别，才把通道的指令改称为“通道命令字”。 若干条通道命令字汇集在一起，就构成了一个“通道程序”，它规定了设备应该执行的各种操作和顺序。 通常，通道程序存放在通道自己的存储部件里。当通道中没有存储部件时，就存放在内存储器里。这时，为了使通道能取得通道程序去执行，必须把存放通道程序的内存起始地址告诉通道。存放这个起始地址的内存固定单元，被称为“通道地址字”。 8(何为DMA,通道与DMA有何区别, 答:所谓“DMA”，是指“直接存储器存取”的数据传输方式，其最大特点是能使I/O设备直接和内存储器进行成批数据的快速传输。适用于一些高速的I/O设备，如磁带、磁盘等。通道方式与DMA方式之间的区别如下。 (1)在DMA方式下，数据传输的方向、传输长度和地址等仍然需要由CPU来控制。但在通道方式下，所需的CPU干预大大减少。 (2)在DMA方式下，每台设备要有一个DMA控制器。当设备增加时，多个DMA控制器的使用，显然不很经济;但在通道方式下，一个通道可以控制多台设备，这不仅节省了费用，而且减轻了CPU在输入/输出中的负担。 (3)在DMA方式下传输数据时，是采用“窃取”总线控制权的办法来工作的。因此，CPU与设备之间并没有实现真正的并行工作;在通道方式下，CPU把I/O任务交给通道后，它就与通道就真正并行工作。 9(解释记录的成组与分解。为什么要这样做, 答:往磁带、磁盘上存放信息时，经常是把若干个记录先在内存缓冲区里拼装成一块，然后再写到磁带或磁盘上。存储设备与内存储器进行信息交换时，就以块为单位。这个把记录拼装成块的过程，被称为是“记录的成组”。 从磁带、磁盘上读取记录时，先是把含有那个记录的块读到内存的缓冲区中，在那里面挑选出所需要的记录，然后把它送到内存存放的目的地。这个把记录从缓冲区里挑选出来的 - 18 - 过程，被称为是“记录的分解”。 之所以这样做，一是为了提高存储设备的存储利用率;二是减少内、外存之间信息交换次数，提高系统的效率。 10(试述SPOOL系统中的3个组成软件模块各自的作用。 答:SPOOLING系统中的3个软件模块是预输入程序、缓输出程序和井管理程序。它们各自的作用如下。 (1)预输入程序预先把作业的全部信息输入到磁盘的输入井中存放，以便在需要作业信息以及作业运行过程中需要数据时，可以直接从输入井里得到，而无需与输入机交往，避免了等待使用输入机的情况发生。 (2)缓输出程序总是查看“输出井”中是否有等待输出的作业信息。如果有，就启动输出设备(如打印机)进行输出。因此，由于作业的输出是针对输出井进行的，所以不会出现作业因为等待输出而阻塞的现象。 (3)井管理程序分为“井管理读程序”和“井管理写程序”。当作业请求输入设备工作时，操作系统就调用井管理读程序，把让输入设备工作的任务，转换成从输入井中读取所需要的信息;当作业请求打印输出时，操作系统就调用井管理写程序，把让输出设备工作的任务，转换成为往输出井里输出。 11. 为了能够使CPU与设备控制器中的各个寄存器进行通信，I/O系统常采用哪样的两种方法来实现, 答:为使CPU与设备控制器中的各个寄存器进行通信，I/O系统常采用“单独的I/O空间”和“内存映射I/O”两种方法来实现。在“单独的I/O空间”方法里，设备控制器的每个寄存器都有一个I/O端口号，它们单独组成一个地址空间。这样，计算机系统除了内存空间外，还有一个I/O端口地址空间。CPU将用不同的指令，完成对内存空间和I/O端口地址空间的访问。在“内存映射I/O”方法里，设备控制器里的每个寄存器没有了特定的设备(端口)地址，而是唯一地与一个内存地址相关联，这些地址不会分配作他用。CPU将通过相同的指令，实现对整个内存空间的访问。也就是说，采用内存映射I/O，可以减少CPU中指令类型的数目。 四、计算 1(在例4-1里，对电梯调度算法只给出了初始由外往里移动磁臂的调度结果。试问如果初始时假定是由里往外移动磁臂，则调度结果又是什么, 解:这时调度的顺序是11?9?1?12?16?34?36，总共划过的柱面数是: 2+8+11+4+18+2=45 2(磁盘请求以10、22、20、2、40、6、38柱面的次序到达磁盘驱动器。移动臂移动一个柱面需要6ms，实行以下磁盘调度算法时，各需要多少总的查找时间,假定磁臂起始时定位于柱面20。 (a)先来先服务; (b)最短查找时间优先; (c)电梯算法(初始由外向里移动)。 解:(a)先来先服务时，调度的顺序是20?10?22?20?2?40?6?38，总共划过的柱面数是: 10+12+2+18+38+34+32=146 因此，总的查找时间为:146×6=876ms。 (b)最短查找时间优先时，调度的顺序是20?22?10?6?2?38?40(由于磁臂起始时定位于柱面20，所以可以把后面第20柱面的访问立即进行)，总共划过的柱面数是: - 19 - 2+12+4+4+36+2=60 因此，总的查找时间为:60×6=360ms。 (c)电梯算法(初始由外向里移动)时，调度的顺序是20?22?38?40?10?6?2(由于磁臂起始时定位于柱面20，所以可以把后面第20柱面的访问立即进行)，总共划过的柱面数是: 2+16+2+30+4+4=58 因此，总的查找时间为:58×6=348ms。 3(假定磁盘的移动臂现在处于第8柱面。有如下表所示的6个I/O请求等待访问磁盘，试列出最省时间的I/O响应次序。 序 号 柱 面 号 磁 头 号 扇 区 号 1 9 6 3 2 7 5 6 3 15 20 6 4 9 4 4 5 20 9 5 6 7 15 2 解:由于移动臂现在处于第8柱面，如果按照“先来先服务”调度算法，对这6个I/O的响应次序应该是8?9?7?15?9?20?7;如果是按照“最短查找时间优先”调度算法，对这6个I/O的响应次序可以有两种，一是8?9?7?15?20(到达9时完成1和4的请求，到达7时完成2和6的请求)，二是8?7?9?15?20(到达7时完成2和6的请求，到达9时完成1和4的请求);如果按照“电梯”调度算法，对这6个I/O的响应次序可以有两种，一是8?9?15?20?7(由里往外的方向，到达9时完成1和4的请求，到达7时完成2和6的请求)，二是8?7?9?15?20(由外往里的方向，到达7时完成2和6的请求，到达9时完成1和4的请求);如果按照“单向扫描”调度算法，对这6个I/O的响应次序是8?9?15?20?0?7。对比后可以看出，实行8?7?9?15?20的响应次序会得到最省的时间，因为这时移动臂的移动柱面数是: 1+2+6+5 = 14 第5章习题答案 一、填空 1(一个文件的文件名是在 创建该文件 时给出的。 2(所谓“文件系统”，由与文件管理有关的 那部分软件 、被管理的文件以及管理所需要的数据结构三部分组成。 3( 块 是辅助存储器与内存之间进行信息传输的单位。 4(在用位示图管理磁盘存储空间时，位示图的尺寸由磁盘的 总块数 决定。 5(采用空闲区表法管理磁盘存储空间，类似于存储管理中采用 可变分区存储管理 方法管理内存储器。 6(操作系统是通过 文件控制块(FCB)感知一个文件的存在的。 - 20 - 7(按用户对文件的存取权限将用户分成若干组，规定每一组用户对文件的访问权限。这样，所有用户组存取权限的集合称为该文件的 存取控制表 。 8(根据在辅存上的不同存储方式，文件可以有顺序、 链接和索引三种不同的物理结构。 9(如果把文件视为有序的字符集合，在其内部不再对信息进行组织划分，那么这种文件的逻辑结构被称为“ 流式文件 ”。 10(如果用户把文件信息划分成一个个记录，存取时以记录为单位进行，那么这种文件 ”。 的逻辑结构称为“ 记录式文件 11. 操作系统应该提供一个环境，保证信息使用的私密和共享，这是系统 内部 的安全问题;另一方面，操作系统还需要提供各种手段，防止来自各方的有意或无意的入侵和攻击，这是系统 外部 的安全问题。 12. “文件备份”的含义，就是为系统中的文件建立相应的副本。它通常有两种方法，一是所谓的“ 全量 转储”，一是所谓的“ 增量 转储”。 二、选择 1(下面的 B 不是文件的存储结构。 A(索引文件 B(记录式文件 C(串联文件 D(连续文件 2(有一磁盘，共有10个柱面，每个柱面20个磁道，每个盘面分成16个扇区。采用位示图对其存储空间进行管理。如果字长是16个二进制位，那么位示图共需 A 字。 A(200 B(128 C(256 D(100 (操作系统为每一个文件开辟一个存储区，在它的里面记录着该文件的有关信息。这3 就是所谓的 B 。 A(进程控制块 B(文件控制块 C(设备控制块 D(作业控制块 4(文件控制块的英文缩写符号是 C 。 A(PCB B(DCB C(FCB D(JCB 5(一个文件的绝对路径名总是以 C 打头。 A(磁盘名 B(字符串 C(分隔符 D(文件名 6(一个文件的绝对路径名是从 B 开始，逐步沿着每一级子目录向下，最后到达指定文件的整个通路上所有子目录名组成的一个字符串。 A(当前目录 B(根目录 C(多级目录 D(二级目录 7(从用户的角度看，引入文件系统的主要目的是 D 。 A(实现虚拟存储 B(保存用户和系统文档 C(保存系统文档 D(实现对文件的按名存取 8(按文件的逻辑结构划分，文件主要有两类: A 。 A(流式文件和记录式文件 B(索引文件和随机文件 C(永久文件和临时文件 D(只读文件和读写文件 9(位示图用于 B 。 A(文件目录的查找 B(磁盘空间的管理 C(主存空间的共享 D(文件的保护和保密 10(用户可以通过调用 C 文件操作，来归还文件的使用权。 A(建立 B(打开 C(关闭 D(删除 11. 文件目录采用树型结构而不采用简单的表结构，最主要的原因是 C 。 - 21 - A(解决查询速度 B(方便用户使用 C(解决文件重名 D(便于文件保密 三、问答 1(为什么位示图法适用于分页式存储管理和对磁盘存储空间的管理,如果在存储管理中采用可变分区存储管理方案，也能采用位示图法来管理空闲区吗,为什么, 答:无论是分页式存储管理还是磁盘存储空间的管理，它们面对的管理对象——存储块(内存块或磁盘块)的数量，在系统的运行过程中是固定不变的。因此，可以很方便地用相同数量的二进制位来对应管理它们。但如果在存储管理中采用可变分区存储管理方案，那么在系统运行时，分区的数目是变化的。因此，也就无法用位示图法来管理这些分区的使用情况。 2(有些操作系统提供系统调用命令RENAME给文件重新命名。同样，也可以通过把一个文件复制到一个新文件、然后删除旧文件的方法达到给文件重新命名的目的。试问这两种做法有何不同, 答:使用RENAME命令给文件重新命名时，用户要提供两个参数:旧文件名，新文件名。RENAME命令将根据旧文件名找到文件的目录项，把里面登记的旧文件名改为新文件名。所以，文件重新命名的功能就是修改该文件目录里的文件名，其他特性不变。 后一种方法是先对文件进行复制，为其起一个新的名字，然后再删除旧的文件。这时，复制过程犹如创建一个文件，新文件除了名字与以前不同外，文件的某些特性也改变了，例如存放的地址不同了。所以，采用这种方法虽然也能够达到给文件重新命名的目的，但显得要比前一种方法复杂一些。 3(“文件目录”和“目录文件”有何不同, 答:“文件目录”是指一个文件的目录项，里面存放着文件的有关数据信息。“目录文件”则是指如果文件很多，那么文件目录项的数量也就很多。为此，操作系统经常把这些目录项汇集在一起，作为一个文件来加以管理，这就是所谓的“目录文件”。因此，“文件目录”和“目录文件”是两个不同的概念，不能混为一谈。 4(一个文件的绝对路径名和相对路径名有何不同, 答:在树型目录结构中，用户要访问一个文件，必须使用文件的路径名来标识文件。从根目录出发、一直到所要访问的文件，将所经过的目录名字用分隔符连接起来，所形成的字符串，就是该文件的绝对路径名。如果是从当前目录出发，一直到所要访问的文件，将所经过的目录名字用分隔符连接起来，所形成的字符串，就是该文件的相对路径名。可以看出，绝对路径名是文件的全名，必须从根目录开始。所以，一个文件的绝对路径名是惟一的。相对路径名总是从当前目录往下，所以文件的相对路径名与当前位置有关，是不惟一的。 5(试述“创建文件”与“打开文件”两个系统调用在功能上的不同之处。 答:所谓“创建文件”，表示原先该文件并不存在。所以创建文件时，最主要的功能是在磁盘上为其开辟存储空间，建立起该文件的FCB。文件创建后，有了它的FCB，系统才真正感知到它的存在;“打开文件”是这个文件已经存在，只是它的有关信息不在内存。因此，打开文件最主要的功能是把该文件FCB中的信息复制到内存中，以便为随后对文件的操作带来便利。 6(试述“删除文件”与“关闭文件”两个系统调用在功能上的不同之处。 答:“删除文件”最主要的功能是把该文件的FCB收回。文件没有了FCB，系统也就无法感知到它的存在了。所以，在执行了删除文件的命令后，这个文件就在系统里消失了;而“关闭文件”最主要的功能是把复制到内存活动目录表里的该文件的FCB信息取消。这样一来，在内存活动目录表里没有了该文件的信息，就不能够对这个文件进行读、写了。所 - 22 - 以，关闭一个文件后，这个文件还存在，只是不能对它操作了。如果要操作，就必须再次将它打开(即把FCB里的信息复制到内存的活动目录表)，然后再进行操作。 7(为什么在使用文件之前，总是先将其打开后再用, 答:有关文件的信息都存放在该文件的FCB里，只有找到文件的FCB，才能获得它的一切信息。但FCB是在磁盘里。因此，只要对文件进行操作，就要到磁盘里去找它的FCB。这种做法，无疑影响了文件操作的执行速度。正因为如此，操作系统才考虑在对文件进行操作前，先将其打开，把文件的FCB内容复制到内存中来。这样，查找文件的FCB，就不必每次都要去访问磁盘。 8(如果一个文件系统没有提供显式的打开命令(即没有OPEN命令)，但又希望有打开的功能，以便在使用文件时能减少与磁盘的交往次数。那么应该把这一功能安排在哪个系统调用里合适,如何安排, 答:文件系统中设置打开命令的根本目的，是减少文件操作时与磁盘的交往次数。如果系统没有提供显式的打开命令，但又要能减少与磁盘的交往次数，那么只需把这一功能安排在读或写系统调用命令里。这时，在读、写命令功能前面添加这样的处理:总是先到内存的活动目录表里查找该文件的FCB。如果找到，则表明在此前文件已经被打开，于是就可以立即进行所需要的读、写操作;如果没有找到，那么表明在此前文件还没有打开。于是应该先按照文件名，到磁盘上去查找该文件的FCB，把它复制到内存的活动目录表里，然后再进行对它的操作。 9. 何为“独立磁盘冗余阵列(RAID)”, 答:在磁盘上组织数据时，利用多磁盘的并行访问能力，一方面可以改善磁盘的传输率，另一方面可以利用多磁盘的大容量能力，存储有关数据的额外的信息，它们或是数据本身的备份，或是诸如差错纠正码、奇偶校验码等信息。这样的冗余信息，在系统出错或磁盘损坏时，可以用来进行对数据的纠错，或修复，从而改善磁盘存储的可靠性。也就是说，利用多磁盘阵列，既可以改善磁盘的传输率，也可以增强磁盘的可靠性。当前，将同时具有这两种性能的磁盘阵列称为“独立磁盘冗余阵列(RAID)”。 四、计算 1(我们知道，可以用位示图法或成组链接法来管理磁盘空间。假定表示一个磁盘地址需要D个二进制位，一个磁盘共有B块，其中有F块空闲。在什么条件下，成组链接法占用的存储空间少于位示图, 解:依题意，该磁盘共有B块，这意味采用位示图法来管理磁盘空间时，共需要B个二进制位构成位示图的存储空间;另一方面，现在共有F个空闲块，而表示一个磁盘地址(即一个空闲块)需要D个二进制位。所以在当前条件下，用成组链接法来管理磁盘空间中的F个空闲块时，要用F×D个二进制位的存储空间来管理它们。因此，只要题中所给的D、B、F三者之间满足关系: B>F×D 就可以保证使用成组链接法占用的存储空间少于位示图。 2(假定磁带的存储密度为每英寸800个字符，每个逻辑记录长为160个字符，记录间隙为0.6英寸。现在有1000个逻辑记录需要存储到磁带上。分别回答: (1)不采用记录成组技术，这时磁带存储空间的利用率是多少, (2)采用以5个逻辑记录为一组的成组技术进行存放，这时磁带存储空间的利用率是多少, (3)若希望磁带存储空间的利用率大于50%，应该多少个逻辑记录为一组, 解:(1)如果不采用记录成组技术，存放一个逻辑记录，就要有一个记录间隙。因为磁带的存储密度为每英寸800个字符，每个逻辑记录长为160个字符。所以一个逻辑记录占用 - 23 - 的磁带长度是: 160/800=0.2(英寸) 一个记录间隙所需要的磁带长度为0.6英寸。所以，磁带存储空间的利用率是: 0.2/(0.2+0.6)=0.25=25% (2)采用以5个逻辑记录为一组的成组技术进行存放，表示存放5个逻辑记录后，有一个记录间隙。5个逻辑记录占用的磁带长度是: 0.2×5=1(英寸) 这时一个记录间隙所需要的磁带长度仍为0.6英寸。所以，这时磁带存储空间的利用率是: 1/(1+0.6)=0.625=62.5% (3)若希望磁带存储空间的利用率大于50%，假定应该x个逻辑记录为一组。这就是说，存放x个逻辑记录后，有一个记录间隙。x个逻辑记录占用的磁带长度是:0.2×x(英寸);这时一个记录间隙所需要的磁带长度仍为0.6英寸。所以，磁带存储空间的利用率是: x/(x+0.6)=0.5 解这个一元一次方程式，x=3。也就是说，当把3个以上的逻辑记录组成一组时，磁带存储空间的利用率将大于50%。 3(假定有一个名为MYFILE的文件，共有10个逻辑记录，每个逻辑记录长为250个字节。磁盘块尺寸为512字节，磁盘地址需要2个字节表示。把MYFILE采用链接结构存储在磁盘上。 (1)画出该文件在磁盘上的链接结构图(磁盘块号自定)。 (2)现在用户要读文件上包含第1425个字符的逻辑记录。给出完成这一请求的主要工作步骤。 解:(1)由于每个逻辑记录长为250个字节，磁盘块尺寸为512字节。所以，每个磁盘块里可以存放两个逻辑记录，余下的字节用于存放指针，文件总共需要5块。假定系统分配给该文件的磁盘块号是:25、33、10、56、4。于是，该文件在磁盘上的链接结构图如图5-1所示。 (2)首先要知道包含第1425字节的逻辑记录应该放在链接结构的第几块。因为一个逻辑记录是250个字节，2个逻辑记录放在一个磁盘块里。所以 1425/(250×2)=2(“/”表示整除运算) 即包含第1425字节的逻辑记录应该放在链接结构的第3块(注意，由于是用整除，所以第1块应该是0)。 其次，文件系统沿着指针，把第3块(也就是块号为56的块)读入内存缓冲区中。 最后，由 1425%(250×2)=425 (“%”表示求余运算) 且 250×1<425<250×2 所以把缓冲区里的第2个记录读到用户指定的内存区里。 - 24 - X文件的目录 文件名 首块号 尾块号 X 25 4 块号: 25 33 10 56 4 2个 逻辑记录 指针: 33 10 56 4 –1 计算题3的图示 4. 假设文件W有100个逻辑记录，尺寸为512KB。磁盘块的尺寸与逻辑记录相同。现要求分别用连续文件、串联文件、索引文件的形式来存储它。请: (1)画出这三种文件的物理结构图; (2)若要随机读取记录r7。试问在这三种结构下，分别需要做多少次磁盘读操作，并给出相应说明(记录号与磁盘块号都从0开始)。 解:(1)三种文件的物理结构图如下: (1)连续文件:磁盘块号100199 文件W目录项100r0r99 (2)串联文件:磁盘块号100850350 850200文件W目录项100? r0r1r99 磁盘块号(3)索引文件:记录号磁盘块号r08000800 文件W目录项201350r1350 99450 r99450 (2)若要随机读取记录r7，在连续文件时，只需直接读第107磁盘块，因此只要做一次磁盘读操作。 在串联文件时，先根据目录项的指示，读记录r0所在磁盘块100，从中得到r1所在磁盘块号850，然后读r1所在磁盘块，从中得到r2所在位置，如此等等。因此，要读记录r7，需要做8次读磁盘块操作。 在索引文件时，先根据目录项的指示，读入索引表，从表中查的记录r7所在的磁盘块号，据此读入记录r7。因此，需要进行2次读磁盘的操作。 5. 某文件系统在每个文件的目录项中，开辟出有6个元素的一个一维数组，用以描述文件的物理结构。数组的前4个元素为直接索引表，第5个元素为一级间接索引，第6个元素为二级间接索引。磁盘块尺寸为512字节，记录磁盘块号需要花费2个字节。请回答: (1)该文件系统能建立的最大文件尺寸为多少字节, (2)名为ZONG的文件有268个记录，每个记录尺寸为512个字节，试画出该文件的 - 25 - 物理结构。 解:(1)该文件系统能建立的最大文件尺寸为: 2 (4+256+256) ×512B=65796×512=33687552B (2)文件ZONG有268个记录，每个记录尺寸为512个字节。这时: 268=4+256+8 表明应该用到二级索引，其物理结构为: r0r0所在磁盘块号 r1所在磁盘块号 r2所在磁盘块号 r3r3所在磁盘块号 一次间接索引表一次间接索引磁盘块号r4 二次间接索引磁盘块号 r259 一次间接索引表二次间接索引表r260 r267 第6章习题答案 一、填空 1(信号量的物理意义是当信号量值大于零时表示 可分配资源的个数 ;当信号量值小于零时，其绝对值为 等待使用该资源的进程的个数 。 2(所谓临界区是指进程程序中 需要互斥执行的程序段 。 3(用P、V操作管理临界区时，一个进程在进入临界区前应对信号量执行 P 操作，退出临界区时应对信号量执行 V 操作。 4(有m个进程共享一个临界资源。若使用信号量机制实现对临界资源的互斥访问，则该信号量取值最大为 1 ，最小为 ?(m?1)。 注意，无论有多少个进程，只要它们需要互斥访问同一个临界资源，那么管理该临界资源的信号量初值就是1。当有一个进程进入临界区时，信号量的值就变为0。随后再想进入的进程只能等待。最多的情况是让一个进程进入后，其余(m?1)个进程都在等待进入。于是这时信号量取到最小值:?(m?1)。 5(对信号量S的P操作原语中，使进程进入相应信号量队列等待的条件是 V<0 。 s 6(死锁是指系统中多个 进程 无休止地等待永远不会发生的事件出现。 7(产生死锁的4个必要条件是互斥、非剥夺、部分分配和 循环等待 。 8(在银行家算法中，如果一个进程对资源提出的请求将会导致系统从 安全 的状态进入到 不安全 的状态时，就暂时拒绝这一请求。 9(信箱在逻辑上被分为 信箱头 和 信箱体 两部分。 10(在操作系统中进程间的通信可以分为 低级 通信与 高级 通信两种。 二、选择 - 26 - 1(P、V操作是 A 。 A(两条低级进程通信原语 B(两条高级进程通信原语 C(两条系统调用命令 D(两条特权指令 2(进程的并发执行是指若干个进程 B 。 A(共享系统资源 B(在执行的时间上是重叠的 C(顺序执行 D(相互制约 3(若信号量S初值为2，当前值为?1，则表示有 B 个进程在与S相关的队列上等待。 A(0 B(1 C(2 D(3 4(用P、V操作管理相关进程的临界区时，信号量的初值应定义为 C 。 A(?1 B(0 C(1 D(随意 5(用V操作唤醒一个等待进程时，被唤醒进程的状态变为 B 。 A(等待 B(就绪 C(运行 D(完成 6(若两个并发进程相关临界区的互斥信号量MUTEX现在取值为0，则正确的描述应 该是 B 。 A(没有进程进入临界区 B(有一个进程进入临界区 C(有一个进程进入临界区，另一个在等待进入临界区 D(不定 7(在系统中采用按序分配资源的策略，将破坏产生死锁的 D 条件。 A(互斥 B(占有并等待 C(不可抢夺 D(循环等待 8(某系统中有3个并发进程，都需要4个同类资源。试问该系统不会产生死锁的最少 资源总数应该是 B 。 A(9 B(10 C(11 D(12 9(银行家算法是一种 A 算法。 A(死锁避免 B(死锁防止 C(死锁检测 D(死锁解除 10(信箱通信是进程间的一种 B 通信方式。 A(直接 B(间接 C(低级 D(信号量 三、问答 1(试说出图6-30所给出的监视程序A和计数程序B之间体现出一种什么关系，是“互 斥”还是“同步”,为什么, 程序A: 程序B: while(1) while(1) { { A1: 收到监视器的信号; B1: 延迟半小时; A2: COUNT=COUNT+1; B2: 打印COUNT的值; } B3:COUNT=0; } 图6-30 监视与计数 答:图中所给出的监视程序A和计数程序B之间体现出的是一种互斥关系，因为在监 视程序A里，要对共享变量COUNT进行操作: COUNT=COUNT+1; 在计数程序B里要对共享变量COUNT进行操作: 打印COUNT的值; - 27 - COUNT=0; 这两段程序是不能交叉进行的，不然就会出现与时间有关的错误。 2(模仿教材中的图6-4，画出COPY和PUT之间的直接依赖关系。然后把两个图汇集在一起，体会它们三者之间正确的同步关系。再模仿教材中的图6-9，能用信号量及P、V操作来正确处理GET、COPY和PUT三者之间的协同工作关系吗, 答:下图给出了GET、COPY和PUT三者间正确的同步关系:GET在向COPY发“可以拷贝”的消息后，要等待COPY发来“拷贝结束”的消息。因为这个消息意味着输入缓冲区R已经被COPY腾空，GET可以再次向里面存放从文件F里取出的记录了;COPY在等到GET发来的“可以拷贝”的消息后，才能够把输入缓冲区R里的记录拷贝到输出缓冲区T中。完成这个动作后，表示输入缓冲区R已经被COPY腾空，因此应该立即向GET发消息，告诉它输入缓冲区R又可以使用了。随后，向PUT发送“可以打印”的消息，等待PUT发来“打印结束”的消息;PUT在等到COPY发来“可以打印”的消息后，才能够从输出缓冲区T里取出记录打印。打印完毕后，向COPY发送“打印完毕”的消息。这个消息意味着输出缓冲区T已经被PUT腾空，COPY又可以再次去等待GET发送的“可以拷贝”的消息，从输入缓冲区R里取出记录存入输出缓冲区T了。 GET COPY 1. 1. 从文件F取出一个记 等待GET发送“可以 录送至输入缓冲区R 拷贝”的消息 2. 2. PUT 向COPY发送“可以 将缓冲区R里的记录 1. 拷贝”的消息 拷贝到缓冲区T里 等待COPY发送“可 3. 3. 以打印”的消息 等待COPY发来“拷 向GET发送“拷贝结 2. 贝结束”的消息 束”的消息 将缓冲区T里的数据 4. 打印输出 向PUT发送“可以打 3. 印”的消息 向COPY发送“打印 5. 完毕”的消息 等待PUT发送“打印 完毕”的消息 GET、COPY和PUT三者间的工作关系 于是，GET、COPY和PUT三者间有4个同步问题:在GET的标号为3的地方是一个同步点;在COPY的标号为1和5的地方是两个同步点;在PUT的标号为1的地方是一个同步点。因此，共要设置4个同步信号量: S1——控制COPY与GET取得同步，初值=0; S2——控制GET与COPY取得同步，初值=0; S3——控制PUT与COPY取得同步，初值=0; S4——控制COPY与PUT取得同步，初值=0。 下图表述了用信号量及P、V操作来正确处理GET、COPY和PUT三者之间的协同工作关系。 - 28 - GET COPY 1. 1. P(S1) 从文件F取出一个记 录送至输入缓冲区R 2. PUT 2. 将缓冲区R里的记录 1. V(S1) 拷贝到缓冲区T里 P(S3) 3. 3. 2. V(S2) P(S2) 将缓冲区T里的数据 4. 打印输出 V(S3) 3. 5. V(S4) P(S4) 用P、V操作保证GET、COPY和PUT三者的正确协作 3(在图6-31(a)的GET里，是先安放V(S1)，再安放P(S2)的。能把它们两个的安放顺序颠倒过来变成图6-31(b)吗,为什么, GET COPY GET COPY 1. 1. 1. 1. P(S1) P(S1) 从文件F取出一个记 从文件F取出一个记 录送至输入缓冲区R 录送至输入缓冲区R 2. 2. 2. 2. 将缓冲区R里的记录 将缓冲区R里的记录 V(S1) P(S2) 拷贝到缓冲区T里 拷贝到缓冲区T里 3. 3. 3. 3. P(S2) V(S2) V(S1) V(S2) (a) (b) 图6-31 安放V(S1)和P(S2)的两种方法 答:图6-31(b)里是先安放P(S2), 再安放V(S1)。这种安放顺序是不行的。因为安放P(S2)，表示要在此等待COPY发来的消息(即希望COPY执行V(S2)操作)，在接到了COPY的消息后，才执行V(S1)(即向COPY发消息)。但是，根据COPY的安排，不接到GET发来的消息(即执行P(S1)操作)，是不会向COPY发消息的(即执行V(S2)操作)。于是，GET和COPY就陷入了循环等待:GET等待COPY发消息，COPY等待GET发消息。产生两个死锁了。 4(进程A和B共享一个变量，因此在各自的程序里都有自己的临界区。现在进程A在临界区里。试问进程A的执行能够被别的进程打断吗,能够被进程B打断吗(这里，“打断”的含义是调度新进程运行，使进程A暂停执行), 答:当进程A在自己的临界区里执行时，能够被别的进程打断，没有任何的限制。当进程A在自己的临界区里执行时，也能够被进程B打断，不过这种打断是有限制的。即当进程B执行到要求进入自己的临界区时，就会被阻塞。这是因为在它打断进程A时，A正在临界区里还没有出来，既然A在临界区，B当然就无法进入自己的临界区。 5(信号量上的P、V操作只是对信号量的值进行加1或减1操作吗,在信号量上还能够执行除P、V操作外的其他操作吗, 答:根据信号量的定义可知，P、V操作并非只是对信号量进行减1或加1操作，更重要的是在减1或加1后，还要判断运算的结果。对于P操作，判定后调用进程自己有可能 - 29 - 继续运行，也可能阻塞等待。对于V操作，判定后调用进程自己最后总是继续运行，但之前可能会唤醒在信号量队列上等待的进程。 在信号量上除了能执行P、V操作外，不能执行其他任何操作。 6(系统有输入机和打印机各一台，均采用P-V操作来实现分配和释放。现在有两个进程都要使用它们。这会发生死锁吗,试说明理由。 答:采用信号量上的P、V操作，只能正确地完成对设备的申请与释放，但不能控制进程对设备的申请、释放顺序。因此，当进程申请和释放设备的顺序不当时，仍会发生死锁。例如，进程A使用输入机和打印机的顺序是: 请求打印机(Ar1)?请求输入机(Ar2)?释放打印机(Ar3)?释放输入机(Ar4) 进程B使用输入机和打印机的顺序是: 请求输入机(Br1)?请求打印机(Br2)?释放输入机(Br3)?释放打印机(Br4) 其中圆括号里标注的字母，表示某进程对设备的某种使用。例如，Ar1表示进程A请求打印机。由于A和B都是进程，它们的执行可以交叉进行。执行顺序: Ar1?Ar2?Ar3?Ar4?Br1?Br2?Br3?Br4 或 Ar1?Ar2?Br1?Ar3?Ar4?Br2?Br3?Br4 都是合理的交叉。但是，以Ar1?Br1开始的执行就无法再往下进行了。因为进程A执行了Ar1，表明它占用了打印机。接着进程B执行了Br1，表明它占用了输入机。这样一来，不管后面是执行Ar2(进程A申请输入机)还是执行Br2(进程B申请打印机)，都不可能得到满足，两个进程先后被阻塞:进程A占据着打印机而等待输入机，进程B占据着输入机而等待打印机。这就产生了死锁。 7(现有4个进程A、B、C、D，共享10个单位的某种资源。基本数据如图6-32所示。试问如果进程D再多请求一个资源单位，所导致的是安全状态还是不安全状态,如果是进程C提出同样的请求，情况又会是怎样呢, 进程 最大需求 已有量 进程 最大需求 已有量 A 6 0 A 6 1 B 5 0 B 5 1 C 4 0 C 4 2 D 7 0 D 7 4 系统剩余数:10 系统剩余数:2 (a) (b) 图6-32 基本数据 答:若进程D多请求一个资源，资源的使用情况如图(a)所示。这时，系统剩余1个资源，4个进程各自还需要的资源数是5、4、2、2，资源剩余数无法保证任何一个进程运行结束。所以D多请求一个资源单位，会导致不安全状态。若是进程C提出同样的请求，那么系统资源的使用情况如图(b)所示。这时，整个系统虽然也只剩余1个资源，但却能够保证4个进程都完成。所以，C再多请求一个资源单位，系统将处于安全状态。 进程 最大需求 已有量 还需量 进程 最大需求 已有量 还需量 A 6 1 4 A 6 1 5 B 5 1 5 B 5 1 4 C 4 2 2 C 4 3 1 D 7 5 2 D 7 4 3 系统剩余数:1 系统剩余数:1 (a) (b) 不安全与安全状态示意图 - 30 - 8(一个计算机有6台磁带机，有n个进程竞争使用，每个进程最多需要两台。那么n为多少时，系统才不存在死锁的危险, 答:由于每个进程最多需要两台磁带机，考虑极端情况:每个进程已经都申请了一台。那么只要还有一台空闲，就可以保证所有进程都可以完成。也就是说当有条件:n+1=6(即n=5)时，系统就不存在死锁的危险。 9(考虑教材中的图6-18(d)。如果进程C需要的是资源S，而不是资源R，这会引起死锁吗,如果是既要求资源R又要求资源S，情况会怎样, 答:这时的资源使用序列为:(1)A申请R，C申请T，A申请S，C申请S，A释放R，A释放S;(2)A申请R，C申请T，A申请S，C申请S，C申请R，A释放R，A释放S。分别画出它们的资源分配图，可知，它们都不会引起死锁。 10(假定图6-33里的进程A申请最后一台磁带机，会引起死锁吗, 进程 磁带机 绘图仪 打印机 进程 磁带机 绘图仪 打印机 CD-ROM CD-ROM A 3 0 1 1 A 1 1 0 0 E [ ] 6 3 4 2 (资源总数) B 0 1 0 0 B 0 1 1 2 P [ ] 5 3 2 2 C 1 1 1 0 C 3 1 0 0 (已分配数) D 1 1 0 1 D 0 0 1 0 A [ 1 0 2 0 ] E 0 0 0 0 E 2 1 1 0 (剩余数) (a) (b) (c) 图6-33 多种资源的分配问题 答:进程A申请了最后一台磁带机后，系统资源的使用情况由所给图变为下图。按照多种资源的银行家算法，这时系统资源的剩余数可以满足进程D的要求，于是系统资源剩余数矩阵A变为A [1 1 2 1];这样的剩余数，可以满足进程A的要求，于是系统资源剩余数 C、E三个进程中任何一个的需矩阵A变为A [5 1 3 2];这样的剩余数，可以满足进程B、 要，例如给E。在E完成后，系统资源剩余数矩阵A仍为A [5 1 3 2];再给C，C完成后系统资源剩余数矩阵A变为A [6 2 4 2];再给B，B完成后系统资源剩余数矩阵A变为A [6 3 4 2]，系统收回了所有资源。由此可知，进程A申请最后一台磁带机，不会引起死锁。 磁带机 绘图仪 打印机 进程 磁带机 绘图仪 打印机 进程 CD-ROM CD-ROM A 4 0 1 1 A 0 1 0 0 ] E [ 6 3 4 2 (资源总数) B 0 1 1 2 B 0 1 0 0 ] P [ 6 3 2 2 C 3 1 0 0 C 1 1 1 0 (已分配数) D 0 0 1 0 D 1 1 0 1 0 0 2 0 ] A [ E 2 1 1 0 E 0 0 0 0 (剩余数) (c) (b) (a) 进程A申请了最后一台磁带机后 司机: 售票员: 四、计算 1(在公共汽车上，司机和售票员的工作流程如图6-34所启动车辆 关车门 示。为了确保行车安全，试用信号量及其P、V操作来协调司 机和售票员的工作。 运行 售票 解:从日常生活知识知道，司机和售票员之间的工作有如 下的制约关系存在。 到站停车 开车门 (1)司机必须在得到售票员的“关门完毕”的信号后，才 能启动汽车。这是一个司机要与售票员取得同步的问题。 图6-34 司机与售票员 - 31 - (2)售票员必须在得到司机的“已 司机: 售票员: 经停车”的信号后，才能打开车门。 这是一个售票员要与司机取得同步的关车门 P(S1) (等待售票员发“关门 问题。 完毕”的消息) V(S1) 因此，为了确保行车安全，需要(向司机发“关门 完毕”的消息) 启动车辆 设置两个同步信号量: S1——初值为0，控制司机与售运行 售票 票员取得同步; 到站停车 P(S2) S2——初值为0，控制售票员与(等待司机发“已经 停车”的消息) V(S2) 司机取得同步。 (向售票员发“已经 于是，在加入了信号量上的P、V停车”的消息) 开车门 操作后，图6-34应该变为右图。 2(有一个阅览室共100个座位。加入P、V操作后的司机与售票员 用一张表来管理它，每个表目记录座 号以及读者姓名。读者进入时要先在表上登记，退出时要注销登记。试用信号量及其P、V操作来描述各个读者“进入”和“注销”工作之间的同步关系。 解:分析题意，知道在管理读者“进入”和“注销” 阅览室的工作中，存在这样一些制约关系: (1)100个座位是读者共同使用的资源，因此要用一个资源分配信号量来管理它; (2)读者“进入”阅览室时，要申请座位。只有申请到座位才能进入，否则应该等待到座位的释放; (3)没有读者时，不能做“注销”工作，必须等到有了读者才能做。 因此，可以设置两个信号量: S1——初值为100，管理座位的分配; S2——初值为0，控制“注销”与“进入”间取得同步。 “进入”与“注销”两个进程的流程如图所示。 “进入”进程 信号量: “注销”进程 S1的初值=100 S2的初值=0 P(S1) P(S2) (申请一个座位) (等待“进入”进程消息) 办理阅读手续 办理注销手续 V(S2) V(S1) (向“注销”进程发消息) (向“进入”进程发消息) “进入”与“注销”两个进程 在读者进入时，调用“进入”进程，通过P(S1)来申请座位。如果申请到，就可以办理阅览手续。如果100个座位都申请完毕，那么第101个读者就只有在关于S1的队列上等待，等到有人调用“注销”进程执行V(S1)。在有读者离去时，就调用“注销”进程。 3(今有3个并发进程R、S、T，它们共享一个缓冲区B。进程R负责从输入设备读入信息，每读出一个记录后就把它存入缓冲区B中;进程S利用缓冲区B加工进程R存入的记录;进程T把加工完毕的记录打印输出。缓冲区B一次只能存放一个记录。只有在进程T - 32 - 把缓冲区里的记录输出后，才能再往里存放新的记录。试用信号量及其P、V操作控制这3个进程间的的正确工作关系。 解:3个并发进程R、S、T之间有如下的制约关系: (1)R必须先做，在往缓冲区B里面存入数据后，应该向S发消息，然后等待T打印输出后释放缓冲区B; (2)S应该与R取得同步，在等到R发来的消息(表明B里面有数据)后，取出加工、回存，然后向T发消息; (3)T应该与S取得同步，在等到S发来的消息(表明B里的数据已经加工完毕)后，才取出打印，然后向R发消息，表示缓冲区B又可以使用了。 从这些关系可以看出，这里是3个同步问题:R要与T取得同步;S要与R取得同步;T要与S取得同步。所以，设置3个同步信号量: S1——控制S要与R取得同步; S2——控制T要与S取得同步; S3——控制R要与T取得同步。 下图给出了它们的工作流程示意。 进程R 信号量: 进程S 进程T S1=0 S2=0 S3=0 P(S1) P(S2) 从设备读入数据 (等待R的消息) (等待S的消息) 将数据存入B 对B中数据 数据打印 加工、回存 V(S1) (向S发消息) P(S3) V(S2) V(S3) (等待P的消息) (向T发消息) (向R发消息) R、S、T之间的相互制约关系 4(假定有3个进程R、W1、W2共享一个缓冲区B，B中每次只能存放一个数。进程R从输入设备读入一个数，把它存放到缓冲区B里。如果存入的是奇数，则由进程W1取出打印;如果存入的是偶数，则由进程W2取出打印。规定进程R只有在缓冲区B为空或内容已经被打印后才能进行存放;进程W1和W2不能从空缓冲区里取数，也不能重复打印。试用信号量及其P、V操作管理这3个进程，让它们能够协调地正确工作。 解:这实际上也是最简单“生产者—消费者”奇数 进程W1 问题的变种:进程R是产生者，进程W1、W2是缓冲区B 进程R 两个消费者。只是W1只消费奇数，W2只消费偶进程W2 偶数 数。如图所示的是3个进程的工作示意。 奇数、偶数问题 分析一下题目，知道3个进程间有如下的制 约关系存在: (1)进程R申请使用缓冲区B，释放缓冲区B的权利是由进程W1或W2掌握的; (2)进程W1要等待R往缓冲区B里放入奇数后，才能工作(要与R取得同步)，然后释放缓冲区; (3)进程W2要等待R往缓冲区B里放入偶数后，才能工作(要与R取得同步)，然后释放缓冲区。 - 33 - 因此，应该设置3个信号量: S——初值为1，控制缓冲区B的分配; SO——初值为0，控制W1与R取得同步; SE——初值为0，控制W2与R取得同步。 3个进程的工作流程如图下所示。 进程R 进程W1 进程W2 得到一个数 P(SO) P(SE) P(S) (等待R发消息) (等待R发消息) (申请缓冲区B) 从B中取出奇数 从B中取出偶数 将数存入缓冲区B Y N V(S) V(S) B里是奇数? (释放缓冲区B) (释放缓冲区B) V(SO) V(SE) (向W1发消息) (向W2发消息) W、R1、R2的相互制约关系 这里有3个问题需要解释。 (1)在进程R中，把数存入B之后，应该根据数的奇、偶性，来决定是向进程W1发消息，还是向进程W2发消息。这样，才能给予W1或W2从B里取数的机会。 (2)由于在进程R里已经对数的奇、偶性做了判断，所以进程W1或W2到缓冲区B里取数时，不必对它再行判断，取出的内容肯定是所需要的，不会弄错。 (3)假定在进程R没有执行之前，进程W1和W2都先于它执行了。那么这时由于信号量SO和SE的值都是0，所以它们都无法执行下去，分别在SO和SE的有关队列上等待。当进程R被调度到、判定放入B的数是奇数还是偶数，并向W1或W2发消息后，它们两个中的一个才会被唤醒，才会到B里去取数。 还可以从别的角度出发，去理解本题目中R、W1、W2之间的制约关系，从而得到它的另一种解决办法。下图给出了流程图，只需设置两个信号量: S——初值为1; G——初值为0。 进程R 进程W1 进程W2 P(G) P(G) 得到一个数 (等待R发消息) (等待R发消息) P(S) (申请缓冲区B) N Y N Y B里是 B里是 奇数? 奇数? V(G) V(G) 将数存入缓冲区B 从B中取出奇数 从B中取出偶数 (恢复原样) (恢复原样) V(G) V(S) V(G) (释放缓冲区B) (释放缓冲区B) (向W1或W2发消息) W、R1、R2的另一种相互制约关系 - 34 - 这里有3个问题需要解释。 (1)信号量S用于资源分配。进程R通过P(S)申请使用缓冲区B。申请到后，才向里面存放数，然后就在信号量G上执行一个V操作，笼统地告诉进程W1或W2:缓冲区B里有数可取了。由于并不知道这个数的奇、偶性，所以，它们两个谁去取都是可以的。 (2)这时判断缓冲区B里数的奇、偶性，是在进程W1或W2里进行的。运行W1时，如果判定B里的是奇数，那么进程W1就可以将其取出，然后释放缓冲区B(通过V(S)实现)。如果判定B里的是偶数，那么进程W2就可以将其取出，然后释放缓冲区B(通过V(S)实现)。 (3)要注意的是，如果在进程W1里判定B中的数不是奇数，那么它就不应该取出此数。同样地，如果在进程W2里判定B中的数不是偶数，那么它就不应该取出此数。既然它没有取，表明数还在缓冲区B里。所以要通过V(G)，使信号量G恢复原来的取值(含义是告诉要去取数的进程:B里有数要取)，以便给另一个进程去取的机会。如果不做这一步，那么信号量G的当前值是0，无论进程W1还是W2在它的上面再执行P(G)时，就都无法通过，两个进程就会全被阻塞，进入死锁。所以，第j售票处要订 进程W1和W2里的V(G)是非常重要的。 第i航班的飞机票 5(在飞机订票系统中，假定公共数据区的单 按旅客要求找到Ai 元Ai(i=1，2，3…)里存放着某月某日第i次航 班现有票数。在第j个售票处，利用变量Rj暂存P(S) Ai里的内容。现在为第j个售票处编写代码如图(进入公共数据监界区) 6-35所示。试问它的安排对吗,如果正确，试说 Rj=Ai; 明理由;如果不对，指出错误，并做出修改。 (取出该航班现有票数) 解:从图中可以知道，公共数据区的单元Ai N (i=1，2，3…)里存放的某月某日第i次航班的Rj?1? (还有这个班次的飞机票?) 现有票数，是j(j=1，2，3…)个售票处共享的 Y 打印“票已售完!” 数据。因此，这些售票处对公共数据区的单元AiRj=Rj–1; Ai=Rj; (i=1，2，3…)的操作不能同时进行。正因为如(进行数据修改) 此，图中把对Ai的这些操作，用名为S的信号量 上的P、V操作，保证它们互斥进行。这样处理V(S) (退出公共数据监界区) 都是正确的。 关键是当判定没有第i次航班的机票时，图售出一张飞机票 里仅安排了打印“票已售完～”的动作。这样，第 j售票处只有进入临界区的P(S)，而没有执行退出 临界区的V(S)。它没有退出临界区，别的售票窗图6-35 第j售票处的售票程序 口也就无法再进入这个临界区。所以，这种安排是不对的。应该把所给图改成为下图，这样 就正确了。 - 35 - 第j售票处要订 第i航班的飞机票 按旅客要求找到Ai P(S) (进入公共数据监界区) Rj=Ai; (取出该航班现有票数) N Rj?1? (还有这个班次的飞机票?) Y 打印“票已售完!” Rj=Rj–1; Ai=Rj; (进行数据修改) V(S) (退出公共数据监界区) V(S) (退出公共数据监界区) 售出一张飞机票 正确的第j售票处的售票程序 第7章习题答案 一、填空 1(一个操作系统的可扩展性，是指该系统 能够跟上先进计算技术发展 的能力。 2(在引入线程的操作系统中，线程是进程的一个实体，是 进程 中实施调度和处理机分派的基本单位。 3(一个线程除了有所属进程的基本优先级外，还有运行时的 当前 优先级。 4(在Windows XP中，具有1~15优先级的线程称为 可变型 线程。它的优先级随着时间配额的用完，会被强制降低。 5(Windows XP在创建一个进程时，在内存里分配给它一定数量的页帧，用于存放运行时所需要的页面。这些页面被称为是该进程的“ 工作集 ”。 6(Windows XP采用的是请求调页法和 集群 法相结合的取页策略，把页面装入到内存的页帧里的。 7(分区是磁盘的基本组成部分，是一个能够 被格式化和单独使用 的逻辑单元。 8( MFT是一个数组，是一个以数组元素为 记录 构成的文件。 9(只要是存于NTFS卷上的文件，在MFT里都会有一个 元素 与之对应。 10(在Windows XP的设备管理中，整个I/O处理过程都是通过 I/O请求包(IRP)来驱动的。 二、选择 1(在引入线程概念之后，一个进程至少要拥有 D 个线程。 A( 4 B(3 C(2 D(1 2(在Windows XP中，只有 A 状态的线程才能成为被切换成运行状态，占用处理器执行。 - 36 - A( 备用 B(就绪 C(等待 D(转换 3(Windows XP是采用 C 来实现对线程的调度管理的。 A( 线程调度器就绪队列表 B( 线程调度器就绪队列表、就绪位图 C( 线程调度器就绪队列表、就绪位图、空闲位图 D(线程调度器就绪队列表、空闲位图 4(在Windows XP里，一个线程的优先级，会在 A 时被系统降低。 A( 时间配额用完 B(请求I/O C(等待消息 D(线程切换 5(在单处理机系统，当要在进程工作集里替换一页时，Windows XP实施的是 B 页面淘汰策略。 A( FIFO(先进先出) B(LRU(最近最久未用) C(LFU(最近最少用) D(OPT(最优) 6(在页帧数据库里，处于下面所列 A 状态下的页帧才可以变为有效状态。 A(初始化 B(备用 C(空闲 D(修改 7(当属性值能够直接存放在MFT的元素里时，称其为 B 。 A( 非常驻属性 B(常驻属性 C(控制属性 D(扩展属性 8(在NTFS文件系统中，文件在磁盘上存储时的物理结构是采用 C 的。 A( 连续式 B(链接式 C(索引式 D(组合式 9(在Windows XP的设备管理中，I/O请求包(IRP)是由 D 建立的。 A(用户应用程序 B(文件系统驱动程序 C(设备驱动程序 D(I/O管理器 10(Windows XP处理机调度的对象是 B 。 A(进程 B(线程 C(程序 D(进程和线程 三、问答 1. 用“客户- 服务器”模型构造操作系统的含义是什么, 答:所谓“客户- 服务器”的模型，即是把操作系统分成若干个进程，每个进程完成单一的功能服务。比如完成内存分配的进程、完成创建进程的进程、完成显示输出的进程，如此等等。人们把这样的系统功能进程分别称之为“服务器”，如内存服务器、进程服务器、显示服务器等。 在这种操作系统的管理和控制下，用户应用程序(即客户)为了请求所需要的服务，就向指定的服务器发消息。但发送的消息并不是直接抵达服务器，而是先被运行在核心态的操作系统内核俘获，再由它把消息传递给相应的服务器去进行处理。服务器执行完操作，仍然是通过内核，把回应的消息发还给用户。 可以看出，这时内核的主要功能，是在客户程序和运行在用户空间的各种服务(属系统程序)之间进行通信，客户程序和各种服务之间不会直接交互，必须通过内核的消息交换才能完成相互通信。这就是构造操作系统的“客户- 服务器”模型。 2(何谓操作系统的‘微内核’设计模式, 答:所谓操作系统的‘微内核’设计模式，中心思想是将操作系统划分成两个部分:系统的非基本部分和系统的核心部分。系统的非基本部分以单一功能的进程形式，在用户态下运行;把最为关键的进程管理、内存管理、以及进程通信等功能，留存下来组成系统的内核，在核心态下运行。 3(用微内核模式构造的操作系统，为什么具有可扩展性、可移植性、以及更好的安全性和可靠性, 答:用微内核模式构造操作系统，要增加新的服务时，是增加到用户空间中，而不是修 - 37 - 改内核。当内核确实需要变动时，因为内核本身很小，因此所要做的修改也会很小。所以说，这样的操作系统能够跟上先进计算技术的发展，具有可扩展性;由于很小，因此稍加改动，就能够从一种硬件平台移到另一种硬件平台，从而具有可移植性;再有，绝大多数服务都运行在用户态，不以内核进程的面目出现，即使一种服务失败，也不会导致整个系统的崩溃或瘫痪，因此使内核具有更好的安全性和可靠性。 4(什么是对称多处理器系统(SMP), 答:一个计算机系统是所谓的“对称多处理器系统(SMP)”，即该系统具有多个处理器，每个处理器都运行同一个操作系统的拷贝，这些拷贝根据需要可以互相通信。 5(何谓“处理机饥饿”线程,为何要极大地提升它的优先级, 答:所谓“处理机饥饿”，是指在就绪队列里长期等待而一直没有得到运行机会的那种线程。由于它长时间的等待，得不到CPU，这显然是不公平的。为了平衡线程间的这种关系，Windows XP就专门有一个系统线程，定时检查是否存在这样的线程(比如，它们在就绪队列里已经超过了300个时钟中断间隔，相当3~4秒钟)。如果有，就把该线程的优先级一下提升到15，分配给它长度为正常值两倍的时间配额。在它用完这个时间配额后，其优先级立即衰减到它原来的基本优先级。 6(何为“置页策略”,Windows XP具体是怎么做的, 答:当缺页中断时，系统必须确定把虚拟页面放入到物理内存的什么地方。这就是所谓的“置页策略”。 在Windows XP，内存中可分配的页帧对象，只能从页帧号数据库的初始化帧链表、空闲帧链表、后备帧链表和修改帧链表里得到。具体的做法是: (1)在要求存储分配时，如果需要的是一个零初始化的页帧，那么系统首先试图从初始化帧链表中得到一个可分配的页帧;如果这个链表为空，则从空闲帧链表中选取一帧并将其初始化;如果空闲帧链表也为空，那么就改为从后备帧链表中选取一帧并将其初始化;如此等等。 (2)如果所需要的并不是一个零初始化页帧，那么首先去查看空闲帧链表;如果空，则去查看后备帧链表。在决定要把后备帧链表里记录的一帧分配出去之前，必须从该元素回溯，找到进程页表里相关的表项，清除其里面的“页帧号”，断绝这个页表项与该页帧的联系。这样，才能保证分配的安全。 (3)如果必须要把一个处于修改状态的页帧分配出去，那么首先要将该页帧的内容写入磁盘，然后将它链到后备帧链表里去，以便使用。 7(为什么要把一个磁盘划分为若干个分区, 答:把磁盘格式化为若干个分区，主要的目的有三个:第一，使磁盘初始化，以便将其格式化后用于存储数据;第二，通过一个个分区，可以将不同的操作系统分开，以保证多个操作系统可以在同一个磁盘上得到正常的运行;第三，便于更好地对磁盘进行管理，达到充分利用磁盘空间的目的。 8(什么是NTFS文件系统中的VCN和LCN, 答:在NTFS文件系统中，簇是文件存储的分配单位。系统按照簇的尺寸来划分文件的虚拟空间，这样形成的顺序号，称为虚拟簇号，即VCN;把整个卷中所有的簇从头到尾进行顺序编号，称为逻辑簇号，即LCN。 9(在NTFS文件系统中是如何实现其可恢复性的, 答:为了实现可恢复性，NTFS在主控文件表(MFT)里设置了一个日志文件。在系统运行过程中，随时向日志文件里存储更新记录，定时地向日志文件里存储检查点记录、事务表记录以及脏页表记录。为系统的恢复积累所需要的信息。 在系统崩溃而重新启动时，NTFS将对日志文件进行分析扫描、重做扫描和撤消扫描， - 38 - 完成重做和撤消，使系统能够恢复到发生崩溃之前。 10(Windows XP为什么采用两级中断处理方式, 答:Windows XP采用的是中断服务程序(ISR)和延迟过程调用程序(DPC)两级处理中断。之所以这样，是为了提高系统的并行工作能力，防止因中断服务程序占用较长的处理机时间，引起不必要的阻塞。因此，中断服务程序(ISR)部分执行尽可能少的关键性操作，并运行在高中断请求级上;余下的中断处理部分称为延迟过程调用程序(DPC)，运行在低中断请求级上。 11. 若FAT12在Windows XP中，簇的尺寸被限制在512B与8KB之间。试问该FAT文件系统的卷的最大尺寸为多少, 答:若FAT12在Windows XP中，簇的尺寸在512B与8KB之间，那么可以算出该文件系统卷的最大尺寸为32MB。 四、计算 1(FAT16文件系统的簇号应该用多少个二进制位标识,如果一簇的尺寸最大为16KB，那么这种卷的尺寸最多为多少, 答:由FAT16表明，这种文件系统的簇号应该用16个二进制位来标识。也就是说，这 16种卷最多可以含2(=65536)个簇。题目中给出一个簇的最大尺寸为16KB，因此这种卷 16的最大尺寸为2*16KB=1GB。 第8章习题答案 一、填空 1(Linux中，可以同时并行工作的进程个数，由符号常量 NR_TASKS 所限定。通常，它被定义为512。 2(在Linux中，进程调度被分为 实时进程调度 和非实时进程调度两种。 3(当进程运行时出现了系统调用或中断事件，而要去执行操作系统内核的程序时，进程的运行模式就从用户模式转为 核心 模式。 4(Linux存储管理的特点是采用在 各个分区 里进行分页的存储管理技术。 5(采用在分区里分页的虚拟存储管理技术，有利与实行存储 保护 和共享。 6(Ext2中块组里的索引节点位图，用来管理块组中的 索引节点 ，它占用一个盘块。 7(Ext2中块组里的盘块位图，用来管理块组中的 盘块 ，它占用一个盘块。 8(Linux中的进程描述符，就是通常所说的 进程控制块 。 9(Linux内核中，利用控制寄存器来控制硬设备完成输入/输出任务的软件，叫做设备驱动程序，有时也称为 设备驱动器 。 10(网络是一种经过 网络接口 与主机交换数据的设备。 二、选择 1(下面所列的名称中， B 不是Linux进程的状态。 A( 僵死状态 B(休眠状态 C(可中断状态 D(可运行状态 2(Linux的SCHED_RR调度策略，适合于 C 。 A(运行时间短的实时进程 B(交互式分时进程 C(运行时间长的实时进程 D(批处理进程 3(下面列出的进程间通信方法中， A 不被用来在进程之间传递具体数据。 A( 信号 B(消息队列 C(共享存储区 D(管道 4(Linux在实行虚拟地址转换时，采用的是 B 级页表结构。 - 39 - A( 1 B(2 C(3 D(4 5(在Ext2中，下面的说法， D 是错误的。 A( 每个文件都有一个inode节点 B(目录文件有inode节点 C(特别文件有inode节点 D(打印机没有inode节点 6(在Linux中， A 在文件系统中没有相应的inode节点。 A( 网络设备 B(打印机 C(终端 D(磁盘 7(按照文件的内容，Linux把文件分成 D 三类。 A(系统文件、用户文件、设备文件 B(一般文件、流式文件、记录文件 C(目录文件、流式文件、设备文件 D(普通文件、目录文件、特别文件 8(在Linux中，对于页表，下面的说法里 C 是正确的。 A(页表必须占用连续的内存空间 B(页表必须全部在内存 C(页表不必全部在内存，可以不占用连续的内存空间 D(页表必须全部在内存，但可以不占用连续的内存空间 三、问答 1(何谓在分区里进行分页的虚拟存储管理技术, 答:所谓在分区里进行分页的虚拟存储管理技术，即是把用户程序按照其逻辑结构，把虚拟存储空间划分成若干个分区，然后在分区里面分页。由于通常都是按照程序的逻辑结构来划分分区，因此这种存储管理技术，不仅具有页式存储管理的特点(各页可以存放在内存中不连续的页里)，而且有利于进行存储保护和共享。 2(Linux采用的多级页表技术，有什么优点, 答:按照分页式存储管理，页表必须占据内存的连续存储区。由于Linux提供的虚拟地址空间，最大可以有1M个页面。因此，一个页表最大就可以有一百万个表项。把它存放在一个连续的内存区里，不利于存储空间的充分利用。于是，Linux就将页表也按页来划分，并形成页表的索引。这样，大的页表就不必占用连续的内存空间了，从而提高了内存空间的利用率。 3(如书上的图8-12(a)的位示图里，如果现在第36内存块被释放，那么它是否应该和它前面的第34、35块以及它后面的第37、38、39、40块，合并成为一个大的空闲区,为什么, 答:不应该与它们合并。在伙伴系统里，只有尺寸相同、又相邻接的空闲区才能进行合并。第36内存块是由独个内存块构成的空闲区，第34、35块是由两个块构成的空闲区，第37、38、39、40块是由四个块构成的空闲区。既然它们的尺寸不同，因此不能合并。 4(在Ext2中，若有一个分区大小为8GB，盘块的尺寸是4KB。试问，该文件卷最多有多少磁盘块,最多有多少个块组, 答:由于盘块的尺寸是4KB，共有8*4K=32K个二进制位。这表明，在一个块组里，用一个盘块构成盘块位图时，最多可以管理32K个磁盘块，也就是一个块组里最多可以有32K个磁盘块。现在分区尺寸为8GB，盘块尺寸为4KB，所以整个文件卷有8GB/4KB=2M个盘块;有2M/32K=64个块组。 5(试画出Linux巨型文件的索引结构图。 答:Linux巨型文件的索引结构图如下: - 40 - 6(模仿书上图8-9，画出Linux的三级页表式地址转换过程图。 答:Linux的三级页表式地址转换过程图如下: 7(Linux的每个进程都有若干个VMA，且两个VMA可以不连续。即使两个VMA连续，它们也必须分开管理吗,为什么, 答:即使两个VMA连续，它们也必须分开管理。这是因为两个VMA实施的存储保护可以不同，不可能进行统一的管理。 8(试描述在Linux中，你如何能够根据给出的文件名称，找到该文件具体存放在磁盘的哪些磁盘块上的, 答:首先根据文件名称查文件目录，得到该文件的inode节点编号。再由inode节点编号，在索引节点表里找到该文件的索引节点。最后从索引节点里的i_block[ ]数组，就可以得到该文件具体存放在哪些磁盘块里。 9(模仿书上图8-23所示的字符设备数据结构间的关系，画出块设备管理中blkdevs数组、device_struct结构、block_device_operations结构间的关系示意图。 答:块设备数据结构间的关系示意图如下: - 41 - 四、计算 1(如果在Linux里，某段小于4MB。那么它虚拟空间的页表索引有多少表项,它有多少个页表,构成页表索引和页表，总共需要开销多少内存空间, 答:对于Linux来说，它的页表索引最大有1024个表项，每个表项对应一个页表。每个页表有1024个表项，一个表项描述了虚拟空间中的一页与内存块(4KB)的对应情况。因此，一个页表可以用来描述4MB大小的空间。由于现在已知段的长度小于4MB，即是虚拟地址空间小于4MB。所以，它的页表索引需要有1个表项，这个表项指向唯一的一个页表。 虽然页表索引只有1个表项，但必须占用一页的存储量。另外，一个页表要占用一页的存储量。所以，小于4MB的段，要开销两个块的存储空间。 2(假设页面的尺寸为4KB，一个页表项用4B。若要求用页表来管理地址结构为36位的虚拟地址空间，并且每个页表只占用一页。那么，采用多级页表结构时，需要几级才能达到管理的要求, 36答:36位的虚拟地址空间尺寸为2=16GB。已知页面的尺寸为4KB，一个页表项用4B，10024(=2每个页表只占用一页。这表示一个页表有1024个表项，可以管理1)个页面，即 22管理4M(=2)大小的虚存空间。根据题意，第1级只能是一个页表，它可以管理K个页面(因为一个页表里有1024个表项)。K个页面的存储量是4MB。因此，用一级页表不能管理16GB的虚拟空间。于是进入第2级;第2级有K个页表，可以管理K*K个页面。K*K个页面的存储量是4GB。显然用二级页表不能管理16GB的虚拟空间。于是进入第3级;第3级有K*K个页表，可以管理K*K*K个页面。K*K*K个页面的存储量是超过了16GB，达 4236到了2。因此，本题需要使用三级页表才能够管理2的虚拟空间。 3(Linux的空闲区队列表free_area总共可以有11个队列。试问，在第11个队列里排队的每一个空闲区里，包含有多少个连续的内存块, 答:Linux的空闲区队列表free_area里，排在每个队列里的空闲区中所含连续块的数目，0是按2的次幂递增的。在第1个队列里，空闲区中所含连续块的数目为2;在第2个队列 1里，空闲区中所含连续块的数目为2;在第3个队列里，空闲区中所含连续块的数目为2102;„„。因此，在第11个队列里，空闲区中所含连续块的数目为2。即在这个队列里，每个空闲区中所含连续块的数目为1024块～ 4(Linux的Ext2文件系统，其巨型文件最多可以有多少个磁盘块, 答:Ext2文件系统的巨型文件，最多可以有(b/4)*(b/4)*(b/4)+(b/4)*(b/4)+(b/4)+12个磁盘块。 - 42 -