操作系统题库自整理

忘是亡心i 2022-07-16 00:45 197阅读 0赞

**第1章 ****操作系统概论作业**

**一、 ****单项选择题**（请将答案填在题前的括弧内）

（ ）1、操作系统负责为用户程序完成（）的工作。

A、应用无关和硬件相关     B、 应用无关和硬件无关

C、应用相关和硬件相关     D、 应用相关和硬件无关

（  ）2、操作系统是对（）进行管理的软件。

A、硬件   B、软件   C、计算机资源   D、应用程序

（  ）3、用户通过（）来调用操作系统。

A、 跳转指令         B、 子程序调用指令

C、 系统调用指令    D、 以上3种方始都可

（  ）4、所谓（）是指将一个以上的作业放到主存，这些作业共享计算机资源，且同时处于运行开始与运行结束之间。

A、多道   B、批处理   C、分时D、实时

（  ）5、以下下（）不是分时系统的特征。(交互性，多路性，及时性、独立性)

A、交互性   B、多路性   C、及时性 D、同时性

（  ）6、计算机操作系统的功能是（）。

A、把源代码转换成目标代码

B、提供硬件与软件之间的转换

C、提供各种中断处理程序

D、管理计算机资源并提供用户接口

（  ）7操作系统的特征是（）共享、虚拟以及异步

A、并发   B、多道  C、中断  D、实时

（  ）8、处理器将操作系统程序执行的状态与用户程序执行状态称为？

A 屏蔽中断状态和开放中断状态   B 用户态与核心态    C 关闭状态与开放状态

（  ）9、下列什么不是OS关心的主要问题

A、管理计算机裸机

B、设计用户程序与计算机硬件系统的界面

C、管理计算机系统资源

D、高级程序设计语言的编译器

（  ）10、允许多个用户交互方式使用计算机的OS称为（B ）；允许多个用户将作业计算机集中处理的计算机称为（A  ）；计算机系统及时处理过程控制数据并作出响应的OS称为（    D）。

A、批处理OS  B、分时OS  C、多处理器OS  D、实时OS E、网络OS

（ ）11、linux的设计模式属于（A），windows的设计模式属于（bcd）。

A 单核设计模式  B 微核设计模式  C 面向对象的设计模式  D、C/S模式

**二、判断题目**

1、UNIX操作系统是多用户操作系统（ √）

2、windows是多任务操作系统（√ ）

3、用户程序可以通过设置程序状态字进入核心态执行（× ）

4、中断指令是一种特权指令（ √）

5、微内核操作系统提供消息机制，比整体内核执行效率高（ ×）

6、操作系统是计算机系统中的第一层软件（√ ）

7、虚拟是指虚拟存储功能和虚拟文件系统功能（ ×）

**三、填空题**

1、操作系统提供（编程接口）和（命令接口）两种用户接口。

2、负责解释操作系统命令的程序叫（命令解释程序）。Linux的这个程序叫（ shell ）。

3、系统调用是通过（   中断          ）来实现的。当发生系统调用，处理器的状态会从（      用户  ）态变为（  核       ）态。

4、输出重定向的符号是（     “>”   ）。

5、后台执行命令是指（完成命令的进程在低优先级上运行      ）。

**四、问答题**

1、什么是操作系统？有哪些基本功能？

2、单核操作系统与微核操作系统有啥区别？各有什么优缺点？

3、为什么机器要分成至少两种状态：核态和用户态？开机时机器应处于哪种状态？为什么？

4、操作系统提供哪些虚拟技术？

5、什么是并行？什么是并发？

6、简述系统调用的实现过程

用户在需要执行特权指令时，调用系统调用，陷入内核（不同的任务，所对应调用的系统调用号也不同，在调用系统调用陷入内核时，会同时向OS内核传入一个系统调用号i）

进入内核后，根据i查找系统调用表，找到调用号为i的系统调用的处理代码

内核执行完系统调用处理代码后，从核心态返回用户态

五、设有3道程序A、B、C，按照A、B、C次序运行，单处理器，一套I/O设备，是分别画出单道和多道运行的时间关系图，计算二种情况下CPU的利用率。三道程序计算轨迹如下：

A：计算20ms ，I/O30ms，计算10ms

B：计算40ms，I/O20ms，计算10ms

C:计算10ms，I/O30ms，计算20ms

##### 一、填空 #####

1．计算机由 硬件 系统和 软件 系统两个部分组成，它们构成了一个完整的计算机系统。

2．按功能划分，软件可分为 系统 软件和 应用 软件两种。

3．操作系统是在 裸机 上加载的第一层软件，是对计算机硬件系统功能的 首次 扩充。

4．操作系统的基本功能是 处理机（包含作业） 管理、 存储 管理、 设备 管理和 文件 管理。

5．在分时和批处理系统结合的操作系统中引入“前台”和“后台”作业的概念，其目的是 改善系统功能，提高处理能力 。

6．分时系统的主要特征为 多路性 、 交互性 、 独立性 和 及时性 。

7．实时系统与分时以及批处理系统的主要区别是 高及时性 和 高可靠性 。

8．若一个操作系统具有很强的交互性，可同时供多个用户使用，则是 分时 操作系统。

9．如果一个操作系统在用户提交作业后，不提供交互能力，只追求计算机资源的利用率、大吞吐量和作业流程的自动化，则属于 批处理 操作系统。

10．采用多道程序设计技术，能充分发挥 CPU 和 外部设备 并行工作的能力。

##### 二、选择 #####

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．用户数越多

##### 三、问答 #####

1．什么是“多道程序设计”技术？它对操作系统的形成起到什么作用？

答：所谓“多道程序设计”技术，即是通过软件的手段，允许在计算机内存中同时存放几道相互独立的作业程序，让它们对系统中的资源进行“共享”和“竞争”，以使系统中的各种资源尽可能地满负荷工作，从而提高整个计算机系统的使用效率。基于这种考虑，计算机科学家开始把CPU、存储器、外部设备以及各种软件都视为计算机系统的“资源”，并逐步设计出一种软件来管理这些资源，不仅使它们能够得到合理地使用，而且还要高效地使用。具有这种功能的软件就是“操作系统”。所以，“多道程序设计”的出现，加快了操作系统的诞生。

2．怎样理解“虚拟机”的概念？

答：拿操作系统来说，它是在裸机上加载的第一层软件，是对计算机硬件系统功能的首次扩充。从用户的角度看，计算机配置了操作系统后，由于操作系统隐蔽了硬件的复杂细节，用户会感到机器使用起来更方便、容易了。这样，通过操作系统的作用使展现在用户面前的是一台功能经过扩展了的机器。这台“机器”不是硬件搭建成的，现实生活中并不存在具有这种功能的真实机器，它只是用户的一种感觉而已。所以，就把这样的机器称为“虚拟机”。

3．对于分时系统，怎样理解“从宏观上看，多个用户同时工作，共享系统的资源；从微观上看，各终端程序是轮流运行一个时间片”？

答：在分时系统中，系统把CPU时间划分成许多时间片，每个终端用户可以使用由一个时间片规定的CPU时间，多个用户终端就轮流地使用CPU。这样的效果是每个终端都开始了自己的工作，得到了及时的响应。也就是说，“从宏观上看，多个用户同时工作，共享系统的资源”。但实际上，CPU在每一时刻只为一个终端服务，即“从微观上看，各终端程序是轮流运行一个时间片”。

1.操作系统的作用

答：操作系统提供了程序执行的环境。它的职能是管理和控制计算机系统中的所有软硬件资源，合理的组织计算机工作流程，并为用户提供一个良好的工作环境与友好的接口。

2.操作系统包括哪些功能

答：

存储器管理功能，主要包括：内存分配、地址映射、内存保护和内存扩充。

处理机管理功能，其功能包括：作业和进程调度，进程控制和进程通信。

设备管理功能，主要包括：缓冲区管理、设备分配、设备驱动和设备无关性（设备处理）。

文件管理功能，其功能包括：文件存储空间的管理、文件操作的一般管理、目录管理、文件的读写管理，存取控制和保护。

用户接口：命令接口、程序接口、图形接口

3.核心模式和用户模式

答：核心模式一般指操作系统管理程序运行的状态，具有较高的特权级别。

用户模式一般指用户程序运行时的状态，具有较低的特权级别。

当处理器处于管态时全部指令（包括特权指令）可以执行，可使用所有资源，并具有改变处理器状态的能力。当处理器处于用户模式时，就只能执行非特权指令。特权级别不同，可运行指令集合也不同。特权级别越高，可以运行指令集合越大。高特权级别对应的可运行指令集合包含低特权级的。核心模式到用户模式的唯一途径是通过中断。

4.操作系统提供的服务有哪些

答：程序执行、I/O 操作、文件系统处理、通信、错误检测、资源分配、户管理、保护

5.系统调用的工作机制

进入内核后，根据i查找系统调用表，找到调用号为i的系统调用的处理代码

内核执行完系统调用处理代码后，从核心态返回用户态

6操作系统的结构有哪些，各自优缺点

答：1.简单结构 2. 层次化设计3.微内核

要求：能用简单的语言说明不同结构操作系统的特点

7虚拟机的优点

答：虚拟机技术主要有两个优点。

首先，通过完全的保护系统资源，虚拟机提供了一个健壮的安全保护层。

其次，虚拟机允许在不干扰正常的系统操作的情况下进行系统开发。

**第2章  进程管理习题**

**一、选择题（请把答案写在小题前）**

1、在单处理机系统中实现并发技术后，        。

A 、进程在一个时间段内并行运行，CPU与外设间并行工作。

B、进程在一个时刻点上并行运行，CPU与外设间并行工作.

C、进程在一个时间段内并行运行，CPU与外设间串行工作.

D、进程在一个时刻点上并行运行，CPU与外设间串行工作.

2、线程模型中,操作系统分配CPU以外的资源以        为单位.

A、程序  B、 指令  C、 进程  D 、线程

3、操作系统中，当        ，进程从执行状态转为就绪态。

A、进程被进程调度程序选中   B、时间片用完

C、等待某一事件发生          D、等待的事件发生

4、一个进程是

A、协处理器执行的程序           B、一个独立的程序\+数据集

C、PCB结构与程序和数据的集合     D、一个独立的程序

5、操作系统中，当        ，进程从执行状态转为等待态。

A、进程被进程调度程序选中   B、时间片用完

C、等待某一事件发生          D、等待的事件发生

6、n个进程有（）种调度次序。

A、n     B n!    C  1

7、若信号量S的初值为2，当前值为\-1，则表示有      个  
        等待进程？

A、3    B、2    C、1    D、0

8、 下面关于临界资源的论述,正确的是( ).

A  并发执行的程序可以对临界资源实现共享

B为临界资源配上相应的设备控制块后(一种用于设备管理的数据结构),就可以实现共享

C  对临界资源,应该采取互斥访问方式实现共享

D 对临界资源, 应该采取同时访问方式实现共享

9、下面关于临界区的论述正确的是()

A  临界区是指进程中用于实现进程互斥的那段代码

B  临界区是指进程中用于实现进程同步的那段代码

C  临界区是指进程中用于实现进程通讯的那段代码

D  临界区是指进程中用于访问共享资源的那段代码

10、设有6个进程共享一互斥段,若最多允许3个进程进入临界区,则所采用的互斥信号灯的初值为().

A  3    B  6    C  1   D  0

11、有3个进程共享一程序段,而每次最多允许两个进程进入该程序段,则信号量的取值范围是().

A  2,1,0,-1   B  3,2,1,0   C  2,1,0,-1,-2   D  1,0,-1,-2

12、在非剥夺方式下,运行进程执行signal操作后,其状态().

A  不变    B  要变    C   可能变    D   可能不变

13、处于执行状态的进程,执行wait操作后,其值为负,则该状态由执行状态变为().

A  就绪   B   等待    C  就绪或等待

14、n个进程有（）种调度次序。

A、n     B n!    C  1

15、从就绪队列中选一个进程获得CPU的控制权由（）来完成

A、中断处理程序  B、排队程序   C、分派程序

16、在非强占式系统中，发生一个进程从就绪态——>运行态状态变迁的可能原因是（）。

A、另一个进程从运行态——>就绪态

B、另一个进程从等待态——>就绪态

C、一个新的进程被创建

17、以下（）调度算法对CPU繁忙型进程（指占CPU时间比较多）有利。

A、FCFS(有利于长作业)  B、RR   C、多级反馈队列

18、资源的有序分配可以破坏（）条件。

A、互斥    B、请求和保持   C、不剥夺  D、环路等待

19、资源的全部分配可以破坏（）条件。

A、互斥    B、请求和保持   C、不剥夺  D、环路等待

**二、填空题**

1、进程存在的标志是（     PCB           ）。

2、进程至少有三种基本状态（ 就绪      ）、（执行       ）和（阻塞       ）

3、（   用户     ）线程对于内核是透明的。

**三、问答题**

1、 一个CPU，PCB表有100行，任一时刻，最多有多少个进程处于运行态、就绪态、等待状态？如果有n个CPU，请回答同样的问题。

1，99，100

n,99n,100n

2、画出除基本状态外还包含创建、终止状态的变迁图

![20007281_1.png][]![20007281_2.png][]![20007281_3.png][]

3、进程之间通讯的方式有哪几种？

1..共享存储器

2.消息传递

3.管道

四、画出计算(x\*x+1)/(y\*y+1)的进程流图，其中每个操作看成一个进程，并写出同步算法

五、利用信号量写出一个不会死锁的哲学家进餐同步算法

六、独木桥问题。某河只有一座独木桥，过桥时采用如下规则：同一方向的可以连续性过桥，一个方向有人过桥时，另一个方向的人要等待。请用信号量实现这个过桥问题的同步算法。

七、桌子上有一只盘子，每次只能放入一只水果，爸爸专门往盘子里放苹果，妈妈专门往盘子里放橘子，一个儿子专门吃盘子里的橘子，一个女儿专门等吃盘子里的苹果，用信号量实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系

八、考虑3个进程见下表，1的优先级最高，假设忽略进程的调度时间，分析在采用下述几种调度算法下的调度次序以及平均周转时间

** **

（1） 先来先服务

（2） 非剥夺优先级     1->3->2

（3） 剥夺优先级       1->2->3->2->1

（4） 时间片轮转（时间片为3）  1->2->3->1->2->3

九、假设系统中有m个同类的互斥资源，当n个进程共享这m个互斥资源时，每个进程的最大需求数是w。以下什么情况系统不会产生死锁？（n(w-1)+1<=m）

A．m=4，n=3，w=2　　　　　B．m=4，n=2，w=3

C．m=5，n=2，w=3　　　　　D．m=5，n=3，w=2

十、教材p115的22题

选择题：

1.分时系统中进程调度算法通常采用 （）         。

A. 响应比高者优先     B. 时间片轮转法     C. 先来先服务     D. 短作业优先

2.下列进程调度算法中，（     ）可能会出现进程长期得不到调度的情况。

A.非抢占式静态优先权法

B.抢占式静态优先权法

C.时间片轮转调度算法

D.非抢占式动态优先权法

3为了照顾紧迫型作业，应采用（   ）。

A.先来服务调度算法   B.短作业优先调度算法

C.时间片轮转调度算法   D.优先权调度算法

4作业从后备作业到被调度程序选中的时间称为（   ）。

A.周转时间   B.响应时间

C.等待调度时间   D.运行时间

5．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（   ）相同。

A.先来先服务调度算法 B.短作业优先调度算法

C.时间片轮转调度算法     D.长作业优先调度算法

1. 当前运行的进程（     ），将引发系统进行进程调度。

A.执行了一条转移指令

B.要求增加主存空间，经系统调用银行家算法进行测算认为是安全的

C.执行了一条I/O指令

D.执行程序期间发生了I/O完成中断

2.下面所述步骤中， （）不是创建进程所必需的。

A．由调度程序为进程分配CPU     B．建立一个进程控制块

C．为进程分配内存               D．将进程控制块链入就绪队列

3.分配到必要的资源并获得处理机机时的进程状态是  （）        。

A．就绪状态   B．执行状态   C．阻塞状态   D．撤销状态

4.下面对进程的描述中，错误的是          。

A．进程是动态的概念     B．进程执行需要处理机

C．进程是有生命期的     D．进程是指令的集合

5.操作系统中，若进程从执行状态转换为就绪状态，则表示          。

A．时间片到     B．进程被调度程序选中    C．等待某一事件    D．等待的事件发生

6.一个进程被唤醒意味着          。

A．该进程重新占有了CPU

B．它的优先权变为最大

C．其PCB移至等待队列队首

D．进程变为就绪状态

##### 一、填空 #####

1．进程在执行过程中有3种基本状态，它们是 运行 态、 就绪 态和 阻塞 态。

2．系统中一个进程由 程序 、 数据集合 和 进程控制块（PCB） 三部分组成。

3．在多道程序设计系统中，进程是一个 动 态概念，程序是一个 静 态概念。

4．在一个单CPU系统中，若有5个用户进程。假设当前系统为用户态，则处于就绪状态的用户进程最多有 4 个，最少有 0 个。

注意，题目里给出的是假设当前系统为用户态，这表明现在有一个进程处于运行状态，因此最多有4个进程处于就绪态。也可能除一个在运行外，其他4个都处于阻塞。这时，处于就绪的进程一个也没有。

5．总的来说，进程调度有两种方式，即 不可剥夺 方式和 剥夺 方式。

6．进程调度程序具体负责 中央处理机（CPU）的分配。

7．为了使系统的各种资源得到均衡使用，进行作业调度时，应该注意 CPU忙碌           作业和 I/O忙碌 作业的搭配。

8．所谓系统调用，就是用户程序要调用 操作系统 提供的一些子功能。

9．作业被系统接纳后到运行完毕，一般还需要经历 后备 、 运行 和 完成 三个阶段。

10．假定一个系统中的所有作业同时到达，那么使作业平均周转时间为最小的作业调度算法是 短作业优先 调度算法。

二、选择

1．在进程管理中，当 C 时，进程从阻塞状态变为就绪状态。

A．进程被调度程序选中 B．进程等待某一事件发生

C．等待的事件出现 D．时间片到

2．在分时系统中，一个进程用完给它的时间片后，其状态变为 A 。

A．就绪 B．等待 C．运h行 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．响应时间

C．等待时间 D．运行时间

10．计算机系统在执行 C 时，会自动从目态变换到管态。

A．P操作 B．V操作 C．系统调用 D．I/O指令

##### 三、问答 #####

1．在多道程序设计系统中，如何理解“内存中的多个程序的执行过程交织在一起，大家都在走走停停”这样一个现象？

答：在多道程序设计系统中，内存中存放多个程序，它们以交替的方式使用CPU。因此，从宏观上看，这些程序都开始了自己的工作。但由于CPU只有一个，在任何时刻CPU只能执行一个进程程序。所以这些进程程序的执行过程是交织在一起的。也就是说，从微观上看，每一个进程一会儿在向前走，一会儿又停步不前，处于一种“走走停停”的状态之中。

2．什么是“原语”、“特权指令”、“系统调用命令”和“访管指令”？它们之间有无一定的联系？

答：特权指令和访管指令都是CPU指令系统中的指令，只是前者是一些只能在管态下执行的指令，后者是一条只能在目态下执行的指令。原语和系统调用命令都是操作系统中的功能程序，只是前者执行时不能被其他程序所打断，后者没有这个要求。操作系统中有些系统调用命令是以原语的形式出现的，例如创建进程就是一条原语式的系统调用命令。但并不是所有系统调用命令都是原语。因为如果那样的话，整个系统的并发性就不可能得到充分地发挥。

3．操作系统是如何处理源程序中出现的系统调用命令的？

答：编译程序总是把源程序中的系统调用命令改写成为一条访管指令和相应的参数。这样在程序实际被执行时，就通过访管指令进入操作系统，达到调用操作系统功能子程序的目的。

4．系统调用与一般的过程调用有什么区别？

答：系统调用是指在用户程序中调用操作系统提供的功能子程序；一般的过程调用是指在一个程序中调用另一个程序。因此它们之间有如下三点区别。

（1）一般的过程调用，调用者与被调用者都运行在相同的CPU状态，即或都处于目态（用户程序调用用户程序），或都处于管态（系统程序调用系统程序）；但发生系统调用时，发出调用命令的调用者运行在目态，而被调用的对象则运行在管态，即调用者与被调用者运行在不同的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时间

不难看出，这个比值的分母是一个不变的量。随着时间的推移，一个作业的“已等待时间”会不断发生变化，也就是分子在不断地变化。显然，短作业比较容易获得较高的响应比。这是因为它的分母较小，只要稍加等待，整个比值就会很快上升。另一方面，长作业的分母虽然很大，但随着它等待时间的增加，比值也会逐渐上升，从而获得较高的响应比。根据这种分析，可见“响应比高者优先”的作业调度算法，既照顾到了短作业的利益，也照顾到了长作业的利益，是对先来先服务以及短作业优先这两种调度算法的一种折中。

10．短作业优先调度算法总能得到最小的平均周转时间吗？为什么？

答：短作业优先调度算法只有在所有作业同时到达后备作业队列时，才能得到最小的平均周转时间。如果各作业不是同时到达，这个结论是不成立的。可以用反例说明，例如，教材上举有如下例子：考虑有5个作业A到E，运行时间分别是2、4、1、1、1；到达时间分别是0、0、3、3、3。按照短作业优先的原则，最初只有A和B可以参与选择，因为其他3个还没有到达。于是，运行顺序应该是A、B、C、D、E。它们每个的周转时间分别是2、6、4、5、6，平均周转时间是4.6。但如果按照顺序B、C、D、E、A来调度，它们每一个的周转时间成为9、4、2、3、4，平均周转时间是4.4。结果比短作业优先调度算法好。之所以会这样，就是因为这5个作业并没有同时到达。

##### 四、计算 #####

1．有三个作业：

分别采用先来先服务和短作业优先作业调度算法。试问它们的平均周转时间各是什么？你是否还可以给出一种更好的调度算法，使其平均周转时间优于这两种调度算法？

解：（1）采用先来先服务作业调度算法时的实施过程如下。

这时，作业的调度顺序是1→2→3。其平均周转时间为：

（8 + 11.6 + 12）/ 3 = 10.53

（2）采用短作业优先作业调度算法时的实施过程如下。

这里要注意，在作业1运行完毕进行作业调度时，作业2和3都已经到达。由于是实行短作业优先作业调度算法，因此先调度作业3运行，最后调度作业2运行。所以，这时的作业调度顺序是1→3→2。其平均周转时间为：

（8 + 8 + 12.6）/ 3 = 9.53

（3）还可以有更好的作业调度算法，使其平均周转时间优于这两种调度算法。例如，如果知道在作业1后面会来两个短作业，那么作业1到达后，先不投入运行。而是等所有作业到齐后，再按照短作业优先作业调度算法进行调度，具体实施过程如下。

这时的作业调度顺序是3→2→1。其平均周转时间为：

（1 + 5.6 + 14）/ 3 = 6.87

2．设有一组作业，它们的到达时间和所需CPU时间如下所示。

分别采用先来先服务和短作业优先作业调度算法。试问它们的调度顺序、作业周转时间以及平均周转时间各是什么？

解：（1）采用先来先服务作业调度算法时的实施过程如下。

<table style="color:rgb(46,46,46); font-family:&quot;microsoft yahei&quot;,arial,simsun; font-size:16px; line-height:24px; padding:0pt 5.4pt; border-collapse:collapse; margin-left:5.4pt"> 
 <tbody> 
 <tr> 
 <td style="border-width:0.75pt 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:solid; border-right-style:solid"> 作业号 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 到达时间 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 所需CPU时间 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 开始时间 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 完成时间 </td> 
 <td style="border-width:0.75pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 周转时间 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 1 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 9:00 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 70分钟 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 9:00 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:10 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 70分钟 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 2 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 9:40 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 30分钟 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:10 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:40 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 60分钟 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 3 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 9:50 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10分钟 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:40 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:50 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 60分钟 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.75pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 4 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 10:10 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 5分钟 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:50 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:55 </td> 
 <td style="border-width:medium 31.875pt 0.75pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 45分钟 </td> 
 </tr> 
 </tbody> 
</table>

这时，作业的调度顺序是1→2→3→4。其平均周转时间为：

（70 + 60 + 60 + 45）/ 4 = 58.75

（2）采用短作业优先作业调度算法时的实施过程如下。

<table style="color:rgb(46,46,46); font-family:&quot;microsoft yahei&quot;,arial,simsun; font-size:16px; line-height:24px; padding:0pt 5.4pt; border-collapse:collapse; margin-left:5.4pt"> 
 <tbody> 
 <tr> 
 <td style="border-width:0.75pt 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:solid; border-right-style:solid"> 作业号 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 到达时间 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 所需CPU时间 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 开始时间 </td> 
 <td style="border-width:0.75pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 完成时间 </td> 
 <td style="border-width:0.75pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 周转时间 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 1 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 9:00 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 70分钟 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 9:00 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:10 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 70分钟 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 4 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 10:10 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 5分钟 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:10 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:15 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 5分钟 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 3 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 9:50 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10分钟 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:15 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:25 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 35分钟 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.75pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:62.2pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 2 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.2pt; border-right-color:rgb(0,0,0)"> 9:40 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 30分钟 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:25 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:62.15pt; border-right-color:rgb(0,0,0)"> 10:55 </td> 
 <td style="border-width:medium 31.875pt 0.75pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:62.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 75分钟 </td> 
 </tr> 
 </tbody> 
</table>

这时，作业的调度顺序是1→4→3→2。其平均周转时间为：

（70 + 5 + 35 + 75）/ 4 = 46.25

3．某系统有三个作业：

系统确定在它们全部到达后，开始采用响应比高者优先调度算法，并忽略系统调度时间。试问对它们的调度顺序是什么？各自的周转时间是多少？

解：三个作业是在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。整个实施过程如下。

作业的调度顺序是2→1→3。各自的周转时间为：作业1为0.9；作业2为2.6；作业3为2.9。

##### 一、填空 #####

1．信号量的物理意义是当信号量值大于零时表示 可分配资源的个数 ；当信号量值小于零时，其绝对值为 等待使用该资源的进程的个数 。

2．所谓临界区是指进程程序中 需要互斥执行的程序段 。

3．用P、V操作管理临界区时，一个进程在进入临界区前应对信号量执行 P 操作，退出临界区时应对信号量执行 V 操作。

4．有*m*个进程共享一个临界资源。若使用信号量机制实现对临界资源的互斥访问，则该信号量取值最大为 1 ，最小为 *?*（*m**?*1）。

注意，无论有多少个进程，只要它们需要互斥访问同一个临界资源，那么管理该临界资源的信号量初值就是1。当有一个进程进入临界区时，信号量的值就变为0。随后再想进入的进程只能等待。最多的情况是让一个进程进入后，其余（*m**?*1）个进程都在等待进入。于是这时信号量取到最小值：*?*（*m**?*1）。

5 ．对信号量 S 的 P 操作原语中，使进程进入相应信号量队列等待的条件是V s <0 。

6．死锁是指系统中多个 进程 无休止地等待永远不会发生的事件出现。

7．产生死锁的4个必要条件是互斥、非剥夺、部分分配和 循环等待 。

8．在银行家算法中，如果一个进程对资源提出的请求将会导致系统从 安全 的状态进入到 不安全 的状态时，就暂时拒绝这一请求。

9．信箱在逻辑上被分为 信箱头 和 信箱体 两部分。

10．在操作系统中进程间的通信可以分为 低级 通信与 高级 通信两种。

##### 二、选择 #####

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-13（即教材中第2章的图2-2）所给出的监视程序A和计数程序B之间体现出一种什么关系，是“互斥”还是“同步”？为什么？

![20007281_5.png][]

图6-13  对两个程序的描述

答：图6-13（即教材中第2章的图2-2）所给出的监视程序A和计数程序B之间体现出的是一种互斥关系，因为在监视程序A里，要对共享变量COUNT进行操作：

COUNT=COUNT+1;

在计数程序B里要对共享变量COUNT进行操作：

打印COUNT的值;

COUNT=0;

这两段程序是不能交叉进行的，不然就会出现与时间有关的错误。

2．模仿教材中的图6-4，画出COPY和PUT之间的直接依赖关系。然后把两个图汇集在一起，体会它们三者之间正确的同步关系。再模仿教材中的图6-8，能用信号量及P、V操作来正确处理GET、COPY和PUT三者之间的协同工作关系吗？

答：图6-14给出了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了。

![20007281_6.png][]

图6-14  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。

图6-15表述了用信号量及P、V操作来正确处理GET、COPY和PUT三者之间的协同工作关系。

![20007281_7.png][]

图6-15  用P、V操作保证GET、COPY和PUT三者的正确协作

3．在图6-16（a）（即教材中图6-8）GET里，是先安放V(S1)，再安放P(S2)的。能把它们两个的安放顺序颠倒过来变成图6-16（b）吗？为什么？

![20007281_8.png][]

图6-16  安放V(S1)和P(S2)的两种方法

答：图6-16（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操作，判定后调用进程自己有可能继续运行，也可能阻塞等待。对于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-17（即教材中的图6-28）所示。试问如果进程D再多请求一个资源单位，所导致的是安全状态还是不安全状态？如果是进程C提出同样的请求，情况又会是怎样呢？

答：若进程D多请求一个资源，资源的使用情况如图6-18（a）所示。这时，系统剩余1个资源，4个进程各自还需要的资源数是5、4、2、2，资源剩余数无法保证任何一个进程运行结束。所以D多请求一个资源单位，会导致不安全状态。若是进程C提出同样的请求，那么系统资源的使用情况如图6-18（b）所示。这时，整个系统虽然也只剩余1个资源，但却能够保证4个进程都完成。所以，C再多请求一个资源单位，系统将处于安全状态。

![20007281_9.png][]

图6-17  第7题的基本数据

![20007281_10.png][]

图6-18  不安全与安全状态示意图

8．假定图6-19（即教材中的图6-21）里的进程A申请最后一台磁带机，会引起死锁吗？

![20007281_11.png][]

图6-19  多种资源的银行家算法

![20007281_12.png][]

图6-20  进程A申请了最后一台磁带机后

答：进程A申请了最后一台磁带机后，系统资源的使用情况由图6-19变为图6-20。按照多种资源的银行家算法，这时系统资源的剩余数可以满足进程D的要求，于是系统资源剩余数矩阵***A***变为***A ***\[1 1 2 1\]；这样的剩余数，可以满足进程A的要求，于是系统资源剩余数矩阵***A***变为***A ***\[5 1 3 2\]；这样的剩余数，可以满足进程B、C、E三个进程中任何一个的需要，例如给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申请最后一台磁带机，不会引起死锁。

9．一个计算机有6台磁带机，有*n*个进程竞争使用，每个进程最多需要两台。那么*n*为多少时，系统才不存在死锁的危险？

答：由于每个进程最多需要两台磁带机，考虑极端情况：每个进程已经都申请了一台。那么只要还有一台空闲，就可以保证所有进程都可以完成。也就是说当有条件：*n*\+1=6（即*n*=5）时，系统就不存在死锁的危险。

10．考虑教材中的图6-16（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。分别画出它们的资源分配图，可知，它们都不会引起死锁。

##### 四、计算 #####

1．在公共汽车上，司机和售票员的工作流程如图6-21（即教材上的图6-29）所示。为了确保行车安全，试用信号量及其P、V操作来协调司机和售票员的工作。

![20007281_13.png][]解：从日常生活知识知道，司机和售票员之间的工作有如下的制约关系存在。

（1）司机必须在得到售票员的“关门完毕”的信号后，才能启动汽车。这是一个司机要与售票员取得同步的问题。

（2）售票员必须在得到司机的“已经停车”的信号后，才能打开车门。这是一个售票员要与司机取得同步的问题。

因此，为了确保行车安全，需要设置两个同步信号量：

S1——初值为0，控制司机与售票员取得同步；

S2——初值为0，控制售票员与司机取得同步。

于是，在加入了信号量上的P、V操作后，图6-21应该变为图6-22。

![20007281_14.png][]

图6-22  加入P、V操作后的司机与售票员

2．有一个阅览室共100个座位。用一张表来管理它，每个表目记录座号以及读者姓名。读者进入时要先在表上登记，退出时要注销登记。试用信号量及其P、V操作来描述各个读者“进入”和“注销”工作之间的同步关系。

解：分析题意，知道在管理读者“进入”和“注销” 阅览室的工作中，存在这样一些制约关系：

（1）100个座位是读者共同使用的资源，因此要用一个资源分配信号量来管理它；

（2）读者“进入”阅览室时，要申请座位。只有申请到座位才能进入，否则应该等待到座位的释放；

（3）没有读者时，不能做“注销”工作，必须等到有了读者才能做。

因此，可以设置两个信号量：

S1——初值为100，管理座位的分配；

S2——初值为0，控制“注销”与“进入”间取得同步。

“进入”与“注销”两个进程的流程如图6-23所示。

![20007281_15.png][]

图6-23  “进入”与“注销”两个进程

在读者进入时，调用“进入”进程，通过P(S1)来申请座位。如果申请到，就可以办理阅览手续。如果100个座位都申请完毕，那么第101个读者就只有在关于S1的队列上等待，等到有人调用“注销”进程执行V(S1)。在有读者离去时，就调用“注销”进程。

3．今有3个并发进程R、S、T，它们共享一个缓冲区B。进程R负责从输入设备读入信息，每读出一个记录后就把它存入缓冲区B中；进程S利用缓冲区B加工进程R存入的记录；进程T把加工完毕的记录打印输出。缓冲区B一次只能存放一个记录。只有在进程T把缓冲区里的记录输出后，才能再往里存放新的记录。试用信号量及其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取得同步。

图6-24给出了它们的工作流程示意。

![20007281_16.png][]

图6-24  R、S、T之间的相互制约关系

4．假定有3个进程R、W1、W2共享一个缓冲区B，B中每次只能存放一个数。进程R从输入设备读入一个数，把它存放到缓冲区B里。如果存入的是奇数，则由进程W1取出打印；如果存入的是偶数，则由进程W2取出打印。规定进程R只有在缓冲区B为空或内容已经被打印后才能进行存放；进程W1和W2不能从空缓冲区里取数，也不能重复打印。试用信号量及其P、V操作管理这3个进程，让它们能够协调地正确工作。

![20007281_17.png][]解：这实际上也是最简单“生产者—消费者”问题的变种：进程R是产生者，进程W1、W2是两个消费者。只是W1只消费奇数，W2只消费偶数。图6-25所示的是3个进程的工作示意。

分析一下题目，知道3个进程间有如下的制约关系存在：

（1）进程R申请使用缓冲区B，释放缓冲区B的权利是由进程W1或W2掌握的；

（2）进程W1要等待R往缓冲区B里放入奇数后，才能工作（要与R取得同步），然后释放缓冲区；

（3）进程W2要等待R往缓冲区B里放入偶数后，才能工作（要与R取得同步），然后释放缓冲区。

因此，应该设置3个信号量：

S——初值为1，控制缓冲区B的分配；

SO——初值为0，控制W1与R取得同步；

SE——初值为0，控制W2与R取得同步。

3个进程的工作流程如图6-26所示。

![20007281_18.png][]

图6-26  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之间的制约关系，从而得到它的另一种解决办法。图6-27给出了流程图，只需设置两个信号量：

S——初值为1；

G——初值为0。

这里有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)实现）。

![20007281_19.png][]

图6-27  W、R1、R2的另一种相互制约关系

![20007281_20.png][]（3）要注意的是，如果在进程W1里判定B中的数不是奇数，那么它就不应该取出此数。同样地，如果在进程W2里判定B中的数不是偶数，那么它就不应该取出此数。既然它没有取，表明数还在缓冲区B里。所以要通过V(G)，使信号量G恢复原来的取值（含义是告诉要去取数的进程：B里有数要取），以便给另一个进程去取的机会。如果不做这一步，那么信号量G的当前值是0，无论进程W1还是W2在它的上面再执行P(G)时，就都无法通过，两个进程就会全被阻塞，进入死锁。所以，进程W1和W2里的V(G)是非常重要的。

5．在飞机订票系统中，假定公共数据区的单元*Ai*（*i*=1，2，3…）里存放着某月某日第*i*次航班现有票数。在第*j*个售票处，利用变量*Rj*暂存*Ai*里的内容。现在为第*j*个售票处编写代码如图6-28（即教材中的图6-30）所示。试问它的安排对吗？如果正确，试说明理由；如果不对，指出错误，并做出修改。

解：从图6-28可以知道，公共数据区的单元*Ai*（*i*=1，2，3…）里存放的某月某日第*i*次航班的现有票数，是*j*（*j*=1，2，3…）个售票处共享的数据。因此，这些售票处对公共数据区的单元*Ai*（*i*=1，2，3…）的操作不能同时进行。正因为如此，图中把对*Ai*的这些操作，用名为S的信号量上的P、V操作，保证它们互斥进行。这样处理都是正确的。

关键是当判定没有第*i*次航班的机票时，图6-28里仅安排了打印“票已售完！”的动作。这样，第*j*售票处只有进入临界区的P(S)，而没有执行退出临界区的V(S)。它没有退出临界区，别的售票窗口也就无法再进入这个临界区。所以，这种安排是不对的。应该把图6-28改成为图6-29，这样就完全正确了。

![20007281_21.png][]

图6-29  正确的第*j*售票处的售票程序

**第3章   存储管理习题**

姓名:            学号:

**一 选择题**

(  )1 可执行目标程序中的地址为().

A 符号地址    B  相对地址    C  绝对地址

(  )2 在程序执行时进行地址映射称为().

A 绝对装入   B  静态地址重定位    C  动态地址重定位

(  )3 在()存储管理中,必须采用动态地址重定位.

A  可变分区模式    B 单一分区模式    C 页模式

(  )4在下列内存管理方案中,不适合多道程序的是().

A  单一连续模式   B  固定分区模式  C  可变分区模式  D  段页式存储管理模式

(  )5 下面关于虚存的说法正确的是().

A  作业在运行前必须全部装入内存,并且在运行期间必须一直驻留在内存

B  作业在运行前不必全部装入内存,但在运行期间必须一直驻留在内存

C  作业在运行前必须全部装入内存,但在运行期间不必一直驻留在内存

D  作业在运行前不必全部装入内存,并且在运行期间不必一直驻留在内存

(  )6  以下（）不可以提供虚存。

A、可变分区存储管理      B、页式存储管理

C、段式存储管理           D、段页式存储管理

(  )7、虚存的理论基础是（）。

A、程序的局部性理论          B、代码的顺序执行

C、变量的连续访问            D、指令局部性

(  )8**、**虚存空间的最大容量（）。

A、 为内外存容量之和        B、 由CPU与MMU间地址种总线宽度决定

C 、理论上是无限的          D、由程序大小决定

(  )9 内存利用率最高的内存管理模式是（）。

A、页模式  B、段模式  C、段页式模式  D、可变分区

(  )10、以下（）的进程逻辑地址空间是连续编址的。

A、页模式  B、段模式  C、段页式模式  D、稀疏页式

(  )11 下面程序设计技术和数据结构,对于请求分页的环境而言,()最好.

A  栈  B  hash表   C  纯代码  D 间接寻址

（ ）12、一般来说，分配的物理页越多，缺页中断率越低，但是以下（）淘汰算法存在异常现象：对于某种页面流分配的内存越多缺页中断率反而越高。

A  LRU   B  OPT  C  LFU    D  FIFO

二  进程最多分配3个物理页（frame），并且已分配3个物理页面如下所示：

page     frame         装入时间      最近访问时间      访问位       修改位

2        0               60           151                 0            0

1        1              50            160                1             0

0        4              70            120                0            1

当进程访问第3页时，产生缺页中断，如果用FIFO算法，则淘汰的page是    1 ，如果用LRU算法，则淘汰的page是   0  ，如果用NRU算法，则淘汰的page是  2   。

三 进程某时刻的页表如下，页面大小是1KB，虚地址1052和2221对应的页是否在内存？如果在内存，物理地址是多少？

1052/1024=1    有

1052%1024=28     7\*1024+28

2221/1024=2  缺

2221%1024=173

四 一个源程序变成进程到执行要经过那几个阶段？在不同阶段中地址又有哪些变化？

五、对于基本分页系统

a  假设一个页表放在内存，如果一次内存访问用200ns,访问页面一次需要多少时间?

b  如果采用TLB,并且85%的页面引用发生在TLB,内存的有效访问时间是多少?(假设访问TLB占用0时间)

六 对于请求分页系统，假设有下面的页引用序列，1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6，假设分配4个物理页，是分别计算采用FIFO,LRU.页面置换算法的缺页中断率。

七、假设某计算机系统采用段页式管理，实际内存大小为4MB，每个程序地址空间可达64MB，最多可达64段，页长4KB。现有一程序中地址（1，1124）上的一条指令是“将寄存器A的内容送入内存地址（2，4498）”。试分析它的访存过程，并以二进制和十进制方式写出对应的物理地址。进程的段表和页表如下：

（说明：段号、页号、物理页号都从0开始，\-1表示该页不在内存。内存页表用于表示物理页的使用情况，1表示已经分配，0表示空闲，如，内存页表的第一行表示第0个物理页已经分配，以此类推。所有段的页表放在一个页表中，段表中第一行表示第0段的页表从页表的第0行开始，段表的第二行表示第一段的页表从页表的第5行开始，以此类推。）

![20007281_22.png][]1124/(4\*1024)=0

1124%(4\*1024)=1124

16\*4\*1024+1124

4498/(4\*1024)=1 缺页

4498%(4\*1024)=402

5\*4\*1024+402

##### 一、填空 #####

1．将作业相对地址空间的相对地址转换成内存中的绝对地址的过程称为 地址重定位 。

2．使用覆盖与对换技术的主要目的是 提高内存的利用率 。

3．存储管理中，对存储空间的浪费是以 内部碎片 和 外部碎片 两种形式表现出来的。

4．地址重定位可分为 静态重定位 和 动态重定位 两种。

5．在可变分区存储管理中采用最佳适应算法时，最好按 尺寸 法来组织空闲分区链表。

6．在分页式存储管理的页表里，主要应该包含 页号 和 块号 两个信息。

7．静态重定位在程序 装入 时进行，动态重定位在程序 执行 时进行。

8．在分页式存储管理中，如果页面置换算法选择不当，则会使系统出现 抖动 现象。

9．在请求分页式存储管理中采用先进先出（FIFO）页面淘汰算法时，增加分配给作业的块数时， 缺页中断 的次数有可能会增加。

10．在请求分页式存储管理中，页面淘汰是由于 缺页 引起的。

11.产生死锁的基本原因是（系统资源不足）和（进程推进顺序不当）。

##### 二、选择 #####

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

从图3-8中的“缺页计数”栏里可以看出应该选择D。

![20007281_23.png][]

图3-8  选择题2配图

3．系统出现“抖动”现象的主要原因是由于 A 引起的。

A．置换算法选择不当 B．交换的信息量太大

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．在一个分页式存储管理系统中，页表的内容为：

![20007281_24.png][]若页的大小为4KB，则地址转换机构将相对地址0转换成的物理地址是 A 。

A．8192 B．4096

C．2048 D．1024

注意，相对地址0肯定是第0页的第0个字节。查页表可知第0页存放在内存的第2块。现在块的尺寸是4KB，因此第2块的起始地址为8192。故相对地址0所对应的绝对地址（即物理地址）是8192。

9．下面所列的存储管理方案中， A 实行的不是动态重定位。

A．固定分区 B．可变分区 C．分页式    D．请求分页式

10．在下面所列的诸因素中，不对缺页中断次数产生影响的是 C 。

A．内存分块的尺寸 B．程序编制的质量

C．作业等待的时间   D．分配给作业的内存块数

1.某段表内容如下：

一逻辑地址为(2，154)的实际物理地址为多少？

![20007281_25.png][]

答：逻辑地址（2，154）表示段号为2，即段首地址为480k，154为单元号，则实际物理地址为480k+154。

3.在一分页存储管理系统，页面大小为4KB。已知某进程的第0、1、2、3、4页依次存在内存中的6、8、10、14、16物理块号中，现有逻辑地址为12138B, 3A5CH ，分别求其所在的页号、页内相对地址、对应的物理块号以及相应的物理地址。

解：（1）已知页面大小4KB=4096，页号p=INT\[12138/4096\]=2, 页内位移d=12138MOD4096=3946

查页表可知页号2对应物理块号为10。由地址转换原理可得：块内位移等于页内位移。

故物理地址=10\*4096+3946=44906B

2）

已知页面大小4KB=4096，逻辑地址3A5CH=14940。页号p=INT\[14940/4096\]=3, 页内位移d=14940MOD4096=2652，查页表可知页号3对应物理块号为14。由地址转换原理可得：块内位移等于页内位移。

故物理地址=14\*4096+2652=59996D=EA5CH

##### 三、问答 #####

1．什么是内部碎片？什么是外部碎片？各种存储管理中都可能产生何种碎片？

答：所谓“内部碎片”，是指系统已经分配给用户使用、用户自己没有用到的那部分存储空间；所谓“外部碎片”，是指系统无法把它分配出去供用户使用的那部分存储空间。对于教材而言，单一连续区存储管理、固定分区存储管理、分页式存储管理和请求页式存储管理都会出现内部碎片。只是前两种存储管理造成的内部碎片比较大，浪费较为严重；后两种页式存储管理，平均来说每个作业都会出现半页的内部碎片。教材中，只有可变分区存储管理会产生外部碎片。

2．叙述静态重定位与动态重定位的区别。

答：静态重定位是一种通过软件来完成的地址重定位技术。它在程序装入内存时，完成对程序指令中地址的调整。因此，程序经过静态重定位以后，在内存中就不能移动了。如果要移动，就必须重新进行地址重定位。

**动态重定位是一种通过****硬件支持完成的地址重定位技术****。作业程序被原封不动地装入内存。只有到执行某条指令时，****硬件地址转换机构才对它里面的地址进行转换****。正因为如此，实行动态重定位的系统，作业程序可以在内存里移动。也就是说，作业程序在内存中是可浮动的。**

3．一个虚拟地址结构用24个二进制位表示。其中12个二进制位表示页面尺寸。试问这种虚拟地址空间总共多少页？每页的尺寸是多少？

答：如下图所示，由于虚拟地址中是用12个二进制位表示页面尺寸（即页内位移），所以虚拟地址空间中表示页号的也是12个二进制位。这样，这种虚拟地址空间总共有：

212 = 4096（页）

每页的尺寸是：

212 = 4096 = 4K（字节）

![20007281_26.png][]

4．什么叫虚拟存储器？怎样确定虚拟存储器的容量？

答：虚拟存储器实际是一种存储扩充技术。它把作业程序存放在辅助存储器里，运行时只装入程序的一部分。遇到不在内存的程序时，再把所需要的部分装入。这样在内存和辅存之间调入、调出的做法，使用户的作业地址空间无需顾及内存的大小。给用户造成的印象是，无论程序有多大，它在这个系统上都可以运行。这种以辅助存储器作为后援的虚幻存储器，就称为虚拟存储器。虚拟存储器的大小是由系统的地址结构确定的。

5．为什么请求分页式存储管理能够向用户提供虚拟存储器？

答：请求分页式存储管理的基本思想是：操作系统按照存储块的尺寸，把用户作业地址空间划分成页，全部存放在磁盘上。作业运行时，只先装入若干页。运行过程中遇到不在内存的页时，操作系统就把它从磁盘调入内存。这样一来，用户的作业地址空间无需顾及内存的大小。这与虚拟存储器的思想是完全吻合的。所以，请求分页式存储管理能够向用户提供虚拟存储器。

6．在请求分页式存储管理中，为什么既有页表，又有快表？

答：在分页式或请求页式存储管理中，通常是利用内存储器构成页表的。当CPU执行到某条指令、要对内存中的某一地址访问时，因为这个地址是相对地址，所以先要根据这个地址所在的页号去查页表（访问一次内存），然后才能由所形成的绝对地址去真正执行指令（第二次访问内存）。可见，由于页表在内存，降低了CPU的访问速度。

为了提高相对地址到绝对地址的变换速度，人们想到用一组快速寄存器来代替页表。这时查页表是以并行的方式进行，立即就能输出与该页号匹配的块号，这样做无疑比内存式的页表要快得多。但是，快速寄存器的价格昂贵，由它来组成整个页表是不可取的。考虑到程序运行时具有局部性，因此实际系统中总是一方面采用内存页表、另一方面用极少几个快速寄存器组成快表来共同完成地址的变换工作。这时的地址变换过程，如教材中的图3-22所示。

7．试述缺页中断与页面淘汰之间的关系。

答：在请求页式存储管理中，当根据虚拟地址查页表而发现所要访问的页不在内存时，就会产生缺页中断。系统响应中断后，就由操作系统到辅存把所需要的页读入内存。这时，内存可能有空闲的块，也可能没有。只有当内存中没有空闲块时，才会出现将内存现有页面淘汰出去的问题，即要进行页面淘汰。所以，缺页中断和页面淘汰之间的关系是：页面淘汰一定是由缺页中断所引起；但缺页中断则不一定引起页面淘汰。

8．试述缺页中断与一般中断的区别。

答：在计算机系统中，由于某些事件的出现，打断了当前程序的运行，而使CPU去处理出现的事件，这称为“中断”。通常，计算机的硬件结构都是在执行完一条指令后，去检查有无中断事件发生的。如果有，那么就暂停当前程序的运行，而让CPU去执行操作系统的中断处理程序，这叫“中断响应”。CPU在处理完中断后，如果不需要对CPU重新进行分配，那么就返回被中断进程的程序继续运行；如果需要进行CPU的重新分配，那么操作系统就会去调度新进程。

由上面的讲述可以看出，缺页中断与一般中断的区别如下。

（1）两种中断产生的时刻不同：缺页中断是在执行一条指令中间时产生的中断，并立即转去处理；而一般中断则是在一条指令执行完毕后，当硬件中断装置发现有中断请求时才去响应和处理。

（2）处理完毕后的归属不同：缺页中断处理完后，仍返回到原指令去重新执行，因为那条指令并未执行；而一般中断则是或返回到被中断进程的下一条指令去执行，因为上一条指令已经执行完了，或重新调度，去执行别的进程程序。

9．怎样理解把相对地址划分成数对：（页号，页内位移）的过程对于用户是“透明”的？

答：在操作系统中，所谓“透明”，即指用户不知道的意思。对于分页式存储管理来说，用户向系统提供的相对地址空间，是一个一维的连续空间。系统接受了这个作业后，在内部把这个相对地址空间划分成若干页。由于这种划分对于用户来说是根本不知道的，所以说把相对地址划分成数对：（页号，页内位移）的过程对于用户是“透明”的。

![20007281_27.png][]10．做一个综述，说明从单一连续区存储管理到固定分区存储管理，到可变分区存储管理，到分页式存储管理，再到请求分页式存储管理，每一种存储管理的出现，都是在原有基础上的发展和提高。

答：教材共介绍了5种存储管理策略，它们适用于不同的场合，如图3-9所示。图中，在单一连续分区存储管理与固定分区存储管理之间画了一条线，那表明位于线以上的存储管理策略只适用于单道程序设计，以下的适用于多道程序设计；在可变分区存储管理与分页式存储管理之间画了一条线，那表明位于线以上的存储管理策略都要求为进入内存的作业分配一个连续的存储区，以下的存储管理策略打破了连续性的要求；在分页式存储管理与请求页式存储管理之间画了一条线，那表明位于线以上的存储管理策略都要求使作业程序全部进入内存，而以下的存储管理策略打破了全部的要求，只要部分装入内存就可以了。

由此可见，每一种存储管理的出现，都是在原有存储管理基础上的一次发展和提高。它们从简单到复杂，从不完善到逐渐完善。

##### 四、计算 #####

1．在可变分区存储管理中，按地址法组织当前的空闲分区，其大小分别为：10KB，4KB，20KB，18KB，7KB，9KB，12KB和15KB。现在依次有3个存储请求为：12KB，10KB，9KB。试问使用最先适应算法时的分配情形如何？那么最佳适应、最坏适应呢？

解：我们用表来说明实行各种分配算法时的情形。

（1）最先适应算法

<table style="color:rgb(46,46,46); font-family:&quot;microsoft yahei&quot;,arial,simsun; font-size:16px; line-height:24px; padding:0pt 5.4pt; border-collapse:collapse; margin-left:3.3pt"> 
 <tbody> 
 <tr> 
 <td style="border-width:0.75pt 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(255,255,255); padding:0pt 5.4pt; width:55.4pt; border-top-style:solid; border-right-style:solid"> 请求队列 </td> 
 <td colspan="8" style="border-width:0.75pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:319.25pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 最先适应算法 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.4pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 初始 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 20K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:0.5pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:39.95pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.4pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:39.95pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.4pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:39.95pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.75pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.4pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:39.9pt; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 31.875pt 0.75pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:39.95pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 </tbody> 
</table>

（2）最佳适应算法

<table style="color:rgb(46,46,46); font-family:&quot;microsoft yahei&quot;,arial,simsun; font-size:16px; line-height:24px; padding:0pt 5.4pt; border-collapse:collapse; margin-left:1.85pt"> 
 <tbody> 
 <tr> 
 <td style="border-width:0.75pt 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:solid; border-right-style:solid"> 请求队列 </td> 
 <td colspan="8" style="border-width:0.75pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:320.8pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 最佳适应算法 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 初始 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 20K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:0.5pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.15pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 20K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 20K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.75pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 20K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.1pt; border-right-color:rgb(0,0,0)"> 0 </td> 
 <td style="border-width:medium 31.875pt 0.75pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.15pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 </tbody> 
</table>

（3）最坏适应算法

<table style="color:rgb(46,46,46); font-family:&quot;microsoft yahei&quot;,arial,simsun; font-size:16px; line-height:24px; padding:0pt 5.4pt; border-collapse:collapse; margin-left:8.1pt"> 
 <tbody> 
 <tr> 
 <td style="border-width:0.75pt 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:solid; border-right-style:solid"> 请求队列 </td> 
 <td colspan="8" style="border-width:0.75pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:320.3pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 最坏适应算法 </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 初始 </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 20K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:0.5pt 0.5pt 0.5pt medium; border-style:solid solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-top-color:rgb(0,0,0); border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:0.5pt 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.05pt; border-top-style:solid; border-top-color:rgb(0,0,0); border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 18K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.05pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.5pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.5pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 31.875pt 0.5pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.05pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 15K </td> 
 </tr> 
 <tr> 
 <td style="border-width:medium 0.5pt 0.75pt 31.875pt; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-color:rgb(255,255,255); padding:0pt 5.4pt; width:55.25pt; border-top-style:none; border-right-style:solid; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 10K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40pt; border-right-color:rgb(0,0,0)"> 4K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 8K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 7K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 9K </td> 
 <td style="border-width:medium 0.5pt 0.75pt medium; border-style:none solid solid none; border-bottom-color:rgb(0,0,0); padding:0pt 5.4pt; width:40.05pt; border-right-color:rgb(0,0,0)"> 12K </td> 
 <td style="border-width:medium 31.875pt 0.75pt medium; border-bottom-style:solid; border-bottom-color:rgb(0,0,0); border-left-style:none; padding:0pt 5.4pt; width:40.05pt; border-top-style:none; border-right-color:rgb(255,255,255)"> 6K </td> 
 </tr> 
 </tbody> 
</table>

可见，分配算法不同，选择的分配对象也不一样。

2．系统内存被划分成8块，每块4KB。某作业的虚拟地址空间共划分成16个页面。当前在内存的页与内存块的对应关系如下表所示，未列出的页表示不在内存。

试指出对应于下列虚拟地址的绝对地址：

（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次，如图3-10（a）所示；在得到4块内存空间时所产生的缺页中断次数为10次，如图3-10（b）所示。

![20007281_28.png][]

图3-10  LRU时的情形

（2）采用先进先出（FIFO）页面淘汰算法，作业在得到2块内存空间时所产生的缺页中断次数为18次，如图3-11（a）所示；在得到4块内存空间时所产生的缺页中断次数为14次，如图3-11（b）所示。

![20007281_29.png][]

图3-11  FIFO时的情形

关于先进先出（FIFO）页面淘汰算法，在给予作业更多的内存块时，缺页中断次数有可能上升，这是所谓的异常现象。但要注意，并不是在任何情况下都会出现异常。是否出现异常，取决于页面的走向。本题所给的页面走向，在FIFO页面淘汰算法下，并没有引起异常：2块时缺页中断次数为18次，4块时缺页中断次数为14次。

第五章 设备管理

一     选择题

1   通过硬件和软件的扩充，将独占设备改造成共享设备的技术称为（）。

A    SPOOLING技术 B   覆盖技术   C    虚存技术    D     虚拟设备技术

2    磁头从当前位置移动到所访问的驻面所用的时间称为（），磁头等待所访问的扇区转到磁头下所用的时间称为（）。

A  寻道时间     B    传输时间     C     旋转等待时间

3  如果I/O所花费的时间比CPU所花费的时间少，则缓冲区（）

A   不需要    B      用以匹配速度      C几乎无效

4  spooling系统中设计了spooling目录，什么样的程序可以将spooling目录下的内容送入打印机。（）

A    spooling守护进程      B      设备驱动程序        C      用户进程

5    下面哪些算法可以用于设备分配（）

A   FCFS      B    LRU        C  优先级      D  轮转

6    操作系统的设备管理模块通常分为4个层次，缓冲区的管理由（）做

A、中断层    B、驱动层    C、设备无关层    D、用户层

7      通道用于（）之间传送信息

A       主存与外设     B      CPU与外设     C     外设与外设          D    CPU与辅存

8   计算机物理设备直接与()相连

A  外存储器          B    CPU         C    设备控制器

9    为了缓解CPU与外设之间速度上的差异,提高并行操作的程度,专门用于暂时存放I/O数据的内存区域称为().

A  缓冲区        B     虚拟文件        C    虚拟设备

10    在设备管理中,通常采用主设备号和次设备号来表示一台机器,, 主设备号和次设备号分别表示()

A    设备类型和内部标识符      B     设备驱动程序及参数      C     设备名字及其类型

11、以下（）不是设备管理使用的数据结构。

A  JCB     B  DCT        C  COCT    D   CHCT

12、在linux，用户使用I/O设备时通常采用()

A  设备号     B  设备逻辑名     C    设备文件名   D  i节点号

1. 下面关于存储管理的叙述中正确的是          。

A. 存储保护的目的是限制内存分配

B. 在内存为M，由N个用户的分时系统中，每个用户占有M/N的内存空间

C. 在虚拟系统中，只要磁盘空间无限大，程序就成拥有任意大的编址空间

D. 实现虚存管理必须要有相应硬件的支持

2. 在虚拟页式存储管理方案中，下面哪一部分完成将页面调入内存的工作？

A. 缺页中断处理    B. 页面淘汰过程

C. 工作集模型应用    D. 紧缩技术利用

3. 在虚拟页式存储管理方案中，当查找的页面不在那里时，会产生缺页中断？

A. 外存           B. 虚存

C. 内存       D. 地址空间

4. 在虚拟页式存储管理方案中，所谓最近最少使用页面淘汰算法是指          。

A. 将驻留在内存中的页面随即挑选一页淘汰

B. 将驻留在内存中时间最长的一页淘汰

C. 将驻留在内存中使用次数最少的一页淘汰

D. 将驻留在内存中最后一次访问时间距离当前时间间隔最长的一页淘汰

二、填空题

1、通道程序由（       I/O系统             ）编写。

2、设备管理的目标是（ 提高设备利用率   ）和（ I/O速率  ）。

3、一般来说，把设备与主机之间的接口称为（ 设备控制器 ）。

4、磁盘访问的时间由（寻道时间）、（ 旋转延迟时间）和（传输时间）组成。

三、  问答题

1、设备管理完成哪些功能？

缓冲区管理、设备分配，设备处理、虚拟设备、设备独立性

2、I/O软件分哪几个层次，各做什么工作？

用户层：

设备无关层

设备驱动层

中断处理层

3试说明spooling技术的组成。

输入井和输出井、

输入缓冲区和输出缓冲区

输入进程spi和输出进程spo

4、什么是设备的独立性？

应用程序独立于具体使用和物理设备

5、操作系统常用的缓冲技术有哪些？

单缓冲、双缓冲、循环缓冲、缓冲池

6、提高磁盘访问速度的方法有哪些？

1.磁盘高速缓存

2 提前读

3.延迟写

4.优化物理块分布

5.虚拟盘

四、假定磁盘有200个柱面，编号0~199，当前存储臂的位置在143号柱面上，并刚刚完成125号柱面的服务请求。若请求队列的先后顺序是：86,147,91,177,94,150,102,175,130；问，分别使用算法FCFS、SSTF、SCAN、CSCAN存取臂移动的顺序？总量是多少？

##### 一、填空 #####

1．磁带、磁盘这样的存储设备都是以 块 为单位与内存进行信息交换的。

2．根据用户作业发出的磁盘I/O请求的柱面位置，来决定请求执行顺序的调度，被称为 移臂 调度。

3．DMA控制器在获得总线控制权的情况下能直接与 内存储器 进行数据交换，无需CPU介入。

4．在DMA方式下，设备与内存储器之间进行的是 成批 数据传输。

5．通道程序是由 通道 执行的。

6．通道是一个独立与CPU的、专门用来管理 输入/输出操作 的处理机。

7．缓冲的实现有两种方法：一种是采用专门硬件寄存器的硬件缓冲，一种是在内存储器里开辟一个区域，作为专用的I/O缓冲区，称为 软件缓冲 。

8．设备管理中使用的数据结构有系统设备表（SDT）和 设备控制块（DCB） 。

9．基于设备的分配特性，可以把系统中的设备分为独享、共享和 虚拟 三种类型。

10．引起中断发生的事件称为 中断源 。

##### 二、选择 #####

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．快速传输数据

5．在CPU启动通道后，由 A 执行通道程序，完成CPU所交给的I/O任务。

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．键盘显示终端

9．SPOOLING系统提高了 A 的利用率。

A．独享设备  B．辅助存储器 C．共享设备 D．主存储器

10．按照设备的 D 分类，可将系统中的设备分为字符设备和块设备两种。

A．从属关系  B．分配特性 C．操作方式 D．工作特性

##### 三、问答 #####

1．基于设备的从属关系，可以把设备分为系统设备与用户设备两类。根据什么来区分一个设备是系统设备还是用户设备呢？

答：所谓“系统设备”，是指在操作系统生成时就已被纳入系统管理范围的设备；所谓“用户设备”是指在完成应用任务过程中，用户特殊需要的设备。因此，判定一个设备是系统设备还是用户设备，依据是它在系统生成时，是否已经纳入了系统的管理范围。如果是，它就是系统设备；如果不是，它就是用户设备。

2．设备管理的主要功能是什么？

答：设备管理的主要功能是：（1）提供一组I/O命令，以便用户进程能够在程序中提出I/O请求，这是用户使用外部设备的“界面”；（2）记住各种设备的使用情况，实现设备的分配与回收；（3）对缓冲区进行管理，解决设备与设备之间、设备与CPU之间的速度匹配问题；（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就把该请求全部交由通道去完成。通道在整个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．解释记录的成组与分解。为什么要这样做？

答：往磁带、磁盘上存放信息时，经常是把若干个记录先在内存缓冲区里拼装成一块，然后再写到磁带或磁盘上。存储设备与内存储器进行信息交换时，就以块为单位。这个把记录拼装成块的过程，被称为是“记录的成组”。

从磁带、磁盘上读取记录时，先是把含有那个记录的块读到内存的缓冲区中，在那里面挑选出所需要的记录，然后把它送到内存存放的目的地。这个把记录从缓冲区里挑选出来的过程，被称为是“记录的分解”。

之所以这样做，一是为了提高存储设备的存储利用率；二是减少内、外存之间信息交换次数，提高系统的效率。

10．试述SPOOL系统中的3个组成软件模块各自的作用。

答：SPOOLING系统中的3个软件模块是预输入程序、缓输出程序和井管理程序。它们各自的作用如下。

（1）预输入程序预先把作业的全部信息输入到磁盘的输入井中存放，以便在需要作业信息以及作业运行过程中需要数据时，可以直接从输入井里得到，而无需与输入机交往，避免了等待使用输入机的情况发生。

（2）缓输出程序总是查看“输出井”中是否有等待输出的作业信息。如果有，就启动输出设备（如打印机）进行输出。因此，由于作业的输出是针对输出井进行的，所以不会出现作业因为等待输出而阻塞的现象。

（3）井管理程序分为“井管理读程序”和“井管理写程序”。当作业请求输入设备工作时，操作系统就调用井管理读程序，把让输入设备工作的任务，转换成从输入井中读取所需要的信息；当作业请求打印输出时，操作系统就调用井管理写程序，把让输出设备工作的任务，转换成为往输出井里输出。

##### 四、计算 #####

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柱面的访问立即进行），总共划过的柱面数是：

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响应次序。

解：由于移动臂现在处于第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

页式虚拟存储管理采用位示图技术,设主存有16384块，采用32位的512个字作为位示图。若块号、字号、位号（从高到低）分别从1、0、0开始。计算：5998块对应的字号和位号；198字的20位对应哪一块？

32\*512=16384 5998/32=187多，由于字号是0开始的，所以减1为186 187\*32=5984,5998-5984=14，位号由0开始所以减1为13 （198+1）\*32+（20+1）=6389

文件系统

姓名：              学号：

一、选择题

(  )1 文件系统的主要目的是（）

A 实现对文件的按名存储   B 实现虚拟存储

C 提高外设的读取速度 D用于存储文件系统

(  )2 为了对文件进行操作，应该用以下哪些系统调用（）。

A 建立文件   B  打开文件  C 关闭文件   D  申请缓冲区

(  )3文件系统与（）密切相关，它们共同为用户使用文件提供方便。

A   处理器管理  B  设备管理  C  内存管理

(  )4文件系统中文件被按照名字存取是为了（）

A  方便操作系统对文件的管理  B  方便用户使用

C  确定文件的存取权限        D  加强对文件内容的保密

(  )5文件系统采用多级目录后，对于不同用户的文件，其文件名（）

A  应该相同   B   应该不同    C  可以相同，也可以不同

(  )6 在文件系统中可命名的最小数据单位是()

A  字符  B  记录  C  文件  D  文件系统

(  )7 下列()物理结构不利于对文件的随机存取

A 顺序文件  B 链接文件  C  索引文件

(  )8 管理空闲磁盘空间可以用(),它利用二进制的一位来表示一个磁盘块的使用情况

A  空闲区表  B  位示图  C  分组链接

(  )9 文件系统利用()来管理文件.

A 文件名  B 文件描述符  C  目录

A 文件描述符   B  文件指针   C  索引表

（）11、将文件目录分成基本文件目录和符号文件目录的作用是（）

A 层次分明和易于实现     B   提高检索文件速度和便于共享     C  便于文件系统的分层实现

（）12  打开文件操作是对（）的操作

A 目录   B 文件   C  目录和文件

（）13  FAT文件系统支持（）结构

A   顺序文件     B   链接文件    C  索引文件

（）14  EXT2文件系统支持（）结构

A   顺序文件     B   链接文件    C  索引文件

（）15  假设一个扇区大小为512B，1块=1扇区，FAT16可以管理的磁盘空间大小为（）

A   32MB     B   64MB    C    128MB       D   512MB

（）16 linux的VFS的超级块中存放（）信息

A  文件   B   目录      C   文件系统

（）17 假设1块=1扇区=512B，块地址用4B表示，ext2可以管理的最大文件的大小为（）

A  1G        B   16G    C    32G     B  64G

二、使用文件系统时，通常要显示地调用OPEN、CLOSE操作，是否可以不要这种操作？这样做的好处是什么？

三、DOS硬盘的FAT表的大小最大是多少？采用FAT16管理40G的硬盘，一个块要被定义为多大才合适？

1)2^16\*2B

2)40GB/2^16

四、假设某文件为链接文件，由五个逻辑块组成，逻辑块和物理块均为512B，并依次放在50、121、75、80、63号磁盘块上，若要访问该文件的1569B出的信息，问需要访问哪一个磁盘块？

五、一unix文件系统，如果一个盘块大小为1KB,每个盘块号占4B，问若进程要访问偏移量263168B处的数据，要经过几次间接寻址？

六、在文件系统中，为加快文件系统的检索速度，可以“基本目录与符号目录分离”的办法，假设目录文件存放在磁盘上，每个盘块512B。文件描述符占64B，其中文件名占8B，通常将文件描述符分解成两部分：第一部分占10B（包括文件名和文件内部号），第二部分占56B（包括文件内部号和文件其它描述信息）假设某个目录文件共有254个文件描述符，试分别给出分离前后查找该目录文件的某一个文件描述符的平均访磁盘次数。

七、 有一unix系统，每个i结点中的直接索引盘块数为10块，有一、二、三重间接指针，盘块长512B，一个盘块中可放128个地址，试计算：  
（1）文件的最大长度。  
（2）一个长为20MB的文件占用多少个数据盘块和间接盘块？画出该文件的索引结构图。  
（3）有一个文件f长50000B,已经打开（返回值放在fd中）,执行read(fd,12345678B,500B,n)需要访问外存多少次?(写清计算步骤及根据)。

八、某磁盘共有100个柱面，每个柱面8个磁头，每个磁道4个扇区，若逻辑记录与扇区等长，柱面、磁道、扇区均从0开始编址，现用16位的200个字（0~199）的位示图来管理空间，试问

1、 位示图的第15个字的第7位对应的柱面、磁道、扇区是多少？

2、 现回收第56个柱面的第6磁道的第3个扇区，那么要对位示图的第几个字的第几位清零？

##### 一、填空 #####

1．一个文件的文件名是在 创建该文件 时给出的。

2．所谓“文件系统”，由与文件管理有关的 那部分软件 、被管理的文件以及管理所需要的数据结构三部分组成。

3． 块 是辅助存储器与内存之间进行信息传输的单位。

4．在用位示图管理磁盘存储空间时，位示图的尺寸由磁盘的 总块数 决定。

5．采用空闲区表法管理磁盘存储空间，类似于存储管理中采用 可变分区存储管理 方法管理内存储器。

6．操作系统是通过 文件控制块（FCB）感知一个文件的存在的。

7．按用户对文件的存取权限将用户分成若干组，规定每一组用户对文件的访问权限。这样，所有用户组存取权限的集合称为该文件的 存取控制表 。

8．根据在辅存上的不同存储方式，文件可以有顺序、 链接和索引三种不同的物理结构。

9．如果把文件视为有序的字符集合，在其内部不再对信息进行组织划分，那么这种文件的逻辑结构被称为“ 流式文件 ”。

10．如果用户把文件信息划分成一个个记录，存取时以记录为单位进行，那么这种文件的逻辑结构称为“ 记录式文件 ”。

##### 二、选择 #####

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 开始，逐步沿着每一级子目录向下，最后到达指定文件的整个通路上所有子目录名组成的一个字符串。

7．从用户的角度看，引入文件系统的主要目的是 D 。

A．实现虚拟存储 B．保存用户和系统文档

C．保存系统文档 D．实现对文件的按名存取

8．按文件的逻辑结构划分，文件主要有两类： A 。

A．流式文件和记录式文件  B．索引文件和随机文件

C．永久文件和临时文件 D．只读文件和读写文件

9．位示图用于 B 。

A．文件目录的查找 B．磁盘空间的管理

C．主存空间的共享 D．文件的保护和保密

10．用户可以通过调用 C 文件操作，来归还文件的使用权。

A．建立 B．打开 C．关闭 D．删除

##### 三、问答 #####

1．试说出MS-DOS或Windows对文件名的命名规则。举几个例子，说明哪个文件名起得是对的，哪个文件名起得是不符合命名规则的。

答：例如MS-DOS，它的文件名由两部分组成：文件名和扩展名。文件名由1～8个字符组成；在文件名的后面，可以跟随扩展名（可选）。扩展名总是以一个点开始，然后是1～3个字符。组成文件名和扩展名的字符可以如下。

英文字母：A～Z，a～z，共52个（不区分大小写）。

数字符号：0～9。

特殊符号：$、\#、&、@等。

不能使用的字符有\*、？等。

例如：

test.txt abc.obj

等都是正确的文件名；而：

abcdefhgijk.txty

是不正确的文件名。

对于Windows，文件名最多可以有256个字符，其他与MS-DOS类同。

2．试说出在MS-DOS里打印机的文件名。举一个包含有这个名字的MS-DOS命令，它的含义是什么？

答：在MS-DOS里，可以把打印机视为只写文件来处理，这时打印机的文件名是：PRN。例如命令：

COPY  \\USER\\FILE1  PRN

表明是把文件“\\USER\\FILE1”拷贝到文件PRN，也就是把文件“\\USER\\FILE1”在打印机上打印出来。

3．为什么位示图法适用于分页式存储管理和对磁盘存储空间的管理？如果在存储管理中采用可变分区存储管理方案，也能采用位示图法来管理空闲区吗？为什么？

答：无论是分页式存储管理还是磁盘存储空间的管理，它们面对的管理对象——存储块（内存块或磁盘块）的数量，在系统的运行过程中是固定不变的。因此，可以很方便地用相同数量的二进制位来对应管理它们。但如果在存储管理中采用可变分区存储管理方案，那么在系统运行时，分区的数目是变化的。因此，也就无法用位示图法来管理这些分区的使用情况。

4．有些操作系统提供系统调用命令RENAME给文件重新命名。同样，也可以通过把一个文件复制到一个新文件、然后删除旧文件的方法达到给文件重新命名的目的。试问这两种做法有何不同？

答：使用RENAME命令给文件重新命名时，用户要提供两个参数：旧文件名，新文件名。RENAME命令将根据旧文件名找到文件的目录项，把里面登记的旧文件名改为新文件名。所以，文件重新命名的功能就是修改该文件目录里的文件名，其他特性不变。

后一种方法是先对文件进行复制，为其起一个新的名字，然后再删除旧的文件。这时，复制过程犹如创建一个文件，新文件除了名字与以前不同外，文件的某些特性也改变了，例如存放的地址不同了。所以，采用这种方法虽然也能够达到给文件重新命名的目的，但显得要比前一种方法复杂一些。

答：“文件目录”是指一个文件的目录项，里面存放着文件的有关数据信息。“目录文件”则是指如果文件很多，那么文件目录项的数量也就很多。为此，操作系统经常把这些目录项汇集在一起，作为一个文件来加以管理，这就是所谓的“目录文件”。因此，“文件目录”和“目录文件”是两个不同的概念，不能混为一谈。

6．一个文件的绝对路径名和相对路径名有何不同？

答：在树型目录结构中，用户要访问一个文件，必须使用文件的路径名来标识文件。从根目录出发、一直到所要访问的文件，将所经过的目录名字用分隔符连接起来，所形成的字符串，就是该文件的绝对路径名。如果是从当前目录出发，一直到所要访问的文件，将所经过的目录名字用分隔符连接起来，所形成的字符串，就是该文件的相对路径名。可以看出，绝对路径名是文件的全名，必须从根目录开始。所以，一个文件的绝对路径名是惟一的。相对路径名总是从当前目录往下，所以文件的相对路径名与当前位置有关，是不惟一的。

7．试述“创建文件”与“打开文件”两个系统调用在功能上的不同之处。

答：所谓“创建文件”，表示原先该文件并不存在。所以创建文件时，最主要的功能是在磁盘上为其开辟存储空间，建立起该文件的FCB。文件创建后，有了它的FCB，系统才真正感知到它的存在；“打开文件”是这个文件已经存在，只是它的有关信息不在内存。因此，打开文件最主要的功能是把该文件FCB中的信息复制到内存中，以便为随后对文件的操作带来便利。

8．试述“删除文件”与“关闭文件”两个系统调用在功能上的不同之处。

答：“删除文件”最主要的功能是把该文件的FCB收回。文件没有了FCB，系统也就无法感知到它的存在了。所以，在执行了删除文件的命令后，这个文件就在系统里消失了；而“关闭文件”最主要的功能是把复制到内存活动目录表里的该文件的FCB信息取消。这样一来，在内存活动目录表里没有了该文件的信息，就不能够对这个文件进行读、写了。所以，关闭一个文件后，这个文件还存在，只是不能对它操作了。如果要操作，就必须再次将它打开（即把FCB里的信息复制到内存的活动目录表），然后再进行操作。

9．为什么在使用文件之前，总是先将其打开后再用？

答：有关文件的信息都存放在该文件的FCB里，只有找到文件的FCB，才能获得它的一切信息。但FCB是在磁盘里。因此，只要对文件进行操作，就要到磁盘里去找它的FCB。这种做法，无疑影响了文件操作的执行速度。正因为如此，操作系统才考虑在对文件进行操作前，先将其打开，把文件的FCB内容复制到内存中来。这样，查找文件的FCB，就不必每次都要去访问磁盘。

10．如果一个文件系统没有提供显式的打开命令（即没有OPEN命令），但又希望有打开的功能，以便在使用文件时能减少与磁盘的交往次数。那么应该把这一功能安排在哪个系统调用里合适？如何安排？

答：文件系统中设置打开命令的根本目的，是减少文件操作时与磁盘的交往次数。如果系统没有提供显式的打开命令，但又要能减少与磁盘的交往次数，那么只需把这一功能安排在读或写系统调用命令里。这时，在读、写命令功能前面添加这样的处理：总是先到内存的活动目录表里查找该文件的FCB。如果找到，则表明在此前文件已经被打开，于是就可以立即进行所需要的读、写操作；如果没有找到，那么表明在此前文件还没有打开。于是应该先按照文件名，到磁盘上去查找该文件的FCB，把它复制到内存的活动目录表里，然后再进行对它的操作。

##### 四、计算 #####

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个字符。所以一个逻辑记录占用的磁带长度是：

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-4所示。

![20007281_30.png][]

图5-4  计算题3的图示

（2）首先要知道包含第1425字节的逻辑记录应该放在链接结构的第几块。因为一个逻辑记录是250个字节，2个逻辑记录放在一个磁盘块里。所以

1425/（250×2）=2（“/”表示整除运算）

即包含第1425字节的逻辑记录应该放在链接结构的第3块（注意，由于是用整除，所以第1块应该是0）。

其次，文件系统沿着指针，把第3块（也就是块号为56的块）读入内存缓冲区中。

最后，由

1425%（250×2）=425 （“%”表示求余运算）

且

250×1<425<250×2

所以把缓冲区里的第2个记录读到用户指定的内存区里。

[20007281_1.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_1.png
[20007281_2.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_2.png
[20007281_3.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_3.png
[20007281_5.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_5.png
[20007281_6.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_6.png
[20007281_7.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_7.png
[20007281_8.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_8.png
[20007281_9.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_9.png
[20007281_10.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_10.png
[20007281_11.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_11.png
[20007281_12.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_12.png
[20007281_13.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_13.png
[20007281_14.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_14.png
[20007281_15.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_15.png
[20007281_16.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_16.png
[20007281_17.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_17.png
[20007281_18.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_18.png
[20007281_19.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_19.png
[20007281_20.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_20.png
[20007281_21.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_21.png
[20007281_22.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_22.png
[20007281_23.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_23.png
[20007281_24.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_24.png
[20007281_25.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_25.png
[20007281_26.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_26.png
[20007281_27.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_27.png
[20007281_28.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_28.png
[20007281_29.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_29.png
[20007281_30.png]: http://image48.360doc.com/DownloadImg/2011/12/1320/20007281_30.png