操作系统原理参考答案

参考答案

第一章习题

1．简述计算机系统的组成。

参考答案：计算机系统就是按人的要求接收和存储信息，自动进行数据处理和计算，并输出结果信息的系统。一个完整的计算机系统是由硬件和软件两大部分组成的。通常硬件是指计算机物理装置本身，是完成系统各项工作的物质基础，主要包括中央处理器（CPU）、存储器和各种输入输出设备（简称I/O设备）；而软件是各种程序和文件，用于指挥和管理整个计算机系统按指定的要求进行工作。

2．什么是操作系统？它在计算机中的地位如何？其功能有哪些？ 参考答案：操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。

操作系统是计算机系统中最靠近硬件的一层软件，它支持和管理硬件，与具体的应用领域无关，在计算机系统的所有软件中，操作系统是基础，其它软件只有在操作系统的支持下，才能发挥作用。它是计算机硬件和其它软件以及计算机用户之间的联系纽带，如果没有操作系统，用户几乎无法使用计算机系统。

从资源管理的观点看，操作系统具有五个方面的功能：处理器管理、存储器管理、设备管理、文件管理和提供用户接口。这五大部分相互配合，协调工作，实现计算机系统的资源管理、控制程序的执行、并为用户提供方便的使用接口。

3．操作系统有哪几种类型？各有什么特点？ 参考答案：操作系统是随着计算机硬件技术的不断发展和用户的使用要求的提高而从无到有不断完善起来的，其主要类型及其特点如下：

（1） 批处理操作系统：具有很高的资源利用率和系统吞吐量，但作业的平均周转时

间较长，也没有交互性。

（2） 分时操作系统：具有多路性、独立性、及时性和交互性特征，而交互性是其最

重要的特征之一。

（3） 实时操作系统：实时操作系统通常是专用的，具有高及时性和高可靠性，但交

互性较弱。

（4） 微机操作系统：是配置在微型计算机上的操作系统，可以是单任务或多任务，

也可以是单用户或多用户系统。

（5） 网络操作系统：是配置在网络中的操作系统，用于管理网络通信和共享资源，

协调各计算机上任务的运行，并向用户提供统一的、有效方便的网络接口。

（6） 分布式操作系统：是配置在分布式处理系统上的操作系统，其最基本的特征是

能实现处理上的分布，而处理分布的实质是资源、功能、任务和控制都是分布的。

（7） 嵌入式操作系统：通常具有以下特点：（1）操作系统规模一般较小。因为通常

相应硬件配置较低，而且对操作系统提供的功能要求也不高。（2）应用领域差别大。对于不同的应用领域其硬件环境和设备配置情况有明显得差别。

4．分时操作系统和实时操作系统各有什么特点？两者有什么区别？

参考答案：分时操作系统具有多路性、独立性、及时性和交互性特征，而实时操作系统

通常是专用的，具有高及时性和高可靠性，但交互性较弱。

两者的主要区别是：从交互性上，分时系统具有很高的交互性，能向终端用户提供数据处理服务、资源共享等服务，而实时系统虽然也具有交互性，但这里人与系统的交互，仅限于访问系统中某些特定的转用服务程序；从及时性上，实时信息系统与分时系统相似，都是以人所能接受的等待时间来确定的，而实时控制系统的及时性则是以控制对象所要求的截止时间来确定的，一般为秒级、百毫秒级直至毫秒级，甚至要低于100微秒；从可靠性上，分时系统虽然也要求系统可靠，但相比之下，实时系统则要求系统高度可靠，因此在实时系统中，往往都采取了多级容错措施来保证系统的安全性及数据的安全性。

5．对于用户来说，分时操作系统与批处理操作系统相比有哪些主要优点？

参考答案：对于用户来说，分时系统让每个用户都拥有一个独立的终端，方便用户随时上机；同时，为用户提供了很好的人机交换能力，使用户能对自己的作业进行直接控制，这对于程序员调试程序尤为重要。

6．什么是多道程序设计技术？它有什么优点？试画出三道作业的运行情况。 参考答案：多道程序设计技术的基本思想是按照一定的算法选择若干个作业同时装入内存，在管理程序的控制下交替执行，共享CPU和系统中的其它各种资源，每当正在运行的程序因某种原因（如等待I/O操作的完成）不能继续运行时，CPU立即转去执行另一道程序。其主要优点是既提高了CPU的利用率，也提高了内存和I/O设备的利用率，同时也大幅增加了系统吞吐量

三道作业的运行情况：

t1CPU设备1设备2三道程序运行情况程序A运行t2t3程序B运行t4程序C运行t5程序A运行t6T程序A进行I/O操作程序B进行I/O操作

7． 现有以下计算机的应用场合，请为其选择适当的操作系统：① 航空航天，核变研 究；② 国家统计局数据处理中心；③ 机房学生上机学习编程；④ 锅炉炉温控制；⑤ 民航机票订购系统；⑥ 两个不同地区之间发送电子邮件；⑦ 产品组装流水线。

参考答案： ① 航空航天，核变研究：配置实时操作系统；② 国家统计局数据处理中心：配置批处理操作系统；③ 机房学生上机学习编程：配置分时操作系统；④ 锅炉炉温控制：配置实时操作系统；⑤ 民航机票订购系统：配置实时操作系统；⑥ 两个不同地区之间发送电子邮件：配置网络操作系统；⑦ 产品组装流水线：配置实时操作系统。

8．操作系统有哪些特征？其最基本的特征是什么？它们之间有什么联系？

参考答案：不同操作系统的特征各不相同，但都具有以下几个基本特征：并发性、共享性、虚拟性和异步性。其中最基本的特征是并发和共享，它们互为存在条件。首先，共享是以并发执行为条件，若系统不支持程序并发执行，则系统中将不存在资源共享；同时，共享也必然会影响程序的并发执行，若资源共享不当，并发性会减弱，甚至无法实现。

9．操作系统一般为用户提供了哪三种使用接口？

参考答案：现代操作系统通常向用户提供以下三种类型的用户接口：

（1） 命令接口：操作系统向用户提供一组键盘操作命令。用户从键盘上输入命令，

命令解释程序接收并解释这些命令，然后调用操作系统内部的相应程序，完成相应的功能。

（2） 程序接口：是操作系统内核与应用程序之间的接口，是为应用程序在执行中访

问系统资源而设置的，通常由一组系统调用组成，每一个系统调用都是一个能完成特定功能的子程序。系统调用只能在程序中调用，不能直接作为命令从键盘上输入执行。

（3） 图形接口：这是为了方便用户使用操作系统而提供的图形化操作界面。用户利

用鼠标、窗口、菜单、图标等图形用户界面工具，可以直观、方便、有效地使用系统服务和各种应用程序及实用工具，而不必象使用命令接口那样去记住命令名及格式。

第二章习题：

1．进程管理主要包括哪些管理功能？

参考答案：进程管理实际上就是对处理器的管理，因为传统的多道程序系统中，处理器的分配和运行都是以进程为基本单位的。主要有以下几方面的功能：进程控制、进程互斥与同步、进程通信、进程调度。

2．什么是进程？进程有哪些特征？其中最基本的特征是什么？ 参考答案：进程是具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位。进程具有动态性、并发性、独立性、异步性、结构性特征，其中最基本的特征是动态性。

3．简述进程与程序的区别和联系。

参考答案：进程与程序是两个不同的概念，它们之间既有区别又有联系。首先程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序，如果没有程序，进程就失去了其存在的意义；反之，如果没有进程，多道程序也不可能并发运行。但进程与程序又有着本质的区别： （1） 程序是静态概念，本身可以作为软件资源长期保存；而进程是程序的一次执行 过程，是动态的，有一定的生命期。

（2） 进程是一个能独立运行的单位，是系统进行资源分配和调度的基本单位，能与其它进程并发执行，而程序则不然。 （3） 程序和进程无一一对应关系。一个程序可由多个进程共享，而一个进程在其运行过程中又可顺序地执行多个程序。例如，在分时系统中多个终端用户同时进行C程序编译，这样，一个C编译程序对应多个用户进程；而对每个用户进程来说，在进行编译的过程中会用到预处理、词法及语法分析、代码生成和优化等几个程序模块。

（4） 各进程在并发执行过程中存在异步性特征，而程序本身是静态的，没有这个特征。

4．进程有哪三种基本状态？试说明引起进程状态转换的典型原因。

参考答案：进程有就绪状态、执行状态、阻塞状态三种状态。引起进程发生状态转换的

典型原因：

（1）就绪→执行：处于就绪状态的进程，当进程调度程序为之分配了处理器后，该进程便由就绪状态转换到执行状态。

（2）执行→就绪：在分时系统中，正在执行的进程如果时间片用完则将暂停执行；在抢占调度方式中，如有更高优先级的进程需要运行，将迫使正在运行的进程让出CPU。 （3）执行→阻塞：正在执行的进程因发生某事件而无法执行，如等待I/O操作的完成或未能申请到所需的系统资源等，则进程转为阻塞状态。

（4）阻塞→就绪：处于阻塞状态的进程，所等待的事情已经发生，如I/O操作已完成或获得了所需的资源，则进程将转变为就绪状态。

5．进程控制块的作用是什么？在进程控制块中主要包括哪些信息？ 参考答案：进程控制块，简称PCB（Process Control Block），是进程实体的重要组成部分，其中记录了用于描述进程情况及控制进程运行所需要的全部信息。通过PCB，使得原来不能并发执行的程序，成为能并发执行的进程。在进程的控制和管理中，随进程的创建而建立PCB；因进程的状态变化而修改PCB的相关内容；当进程被撤销时，系统收回其PCB。可见，系统是根据PCB来感知进程的存在的，PCB是进程存在的唯一标志。

不同的操作系统其PCB所包含的信息会有些不同，但PCB通常都应包含如下基本信息： （1）进程标识符：系统中的每个进程都有唯一的标识符，以标识一个进程，可以用字符串或编号表示。

（2）说明信息：是与进程调度有关的一些信息，包括进程所处的状态、进程优先权、进程等待时间或已执行时间、进程阻塞原因等。

（3）现场信息：主要是由处理器的各个寄存器中的内容组成，包括通用寄存器内容、指令计数器的值、程序状态字内容以及用户栈指针。当执行中的进程因某种原因而暂停时，必须将这些寄存器中的信息保存在PCB中，以便当进程再次获得处理器时，能从PCB中恢复上次断点处的现场信息而正确地继续执行。

（4）管理信息：是进程管理和控制所需要的相关信息，包括程序和数据在内存或外存的地址、进程同步和通信机制、资源清单（记录进程所需的除CPU外的全部资源和已经分配到的资源）、进程队列的链接指针等。

6．进程创建、进程撤销、进程阻塞、进程唤醒几个原语主要应完成哪些工作？ 参考答案：（1）进程创建原语的功能是为新进程申请一个空白PCB，分配必要的资源，并把新进程的相关信息填入PCB中，如进程名、父进程标识符、处理器初始状态、进程状态、进程优先级、进程对应程序入口地址、资源申请和分配情况等。然后将其PCB插入就绪队列等待进程调度。

（2）进程撤消原语的主要功能是收回被撤消进程所占用的系统资源，包括PCB。原语首先检查被撤消进程在系统中是否存在，如果存在，则回收该进程占用的所有系统资源，将其PCB从所在队列中移出。如果该进程还有子进程，则一并予以撤消。最后撤消其PCB。 （3）进程阻塞原语首先停止该进程的执行，将CPU中各寄存器内容填入该进程的PCB中，并将其状态由“执行”改为“阻塞”，然后插入相应的阻塞队列，最后转进程调度程序重新进行调度。

（4）进程唤醒原语首先将被阻塞进程的PCB从所在阻塞队列中移出，并将其PCB中的状态由“阻塞”改为“就绪”，然后插入就绪队列中等待调度。

7．同步机制应遵循的四个准则是什么？ 参考答案：同步机制应遵循的四个准则是：

（1） 空闲让进：当无进程处于临界区时，相应的临界资源处于空闲状态，因而应允

许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用资源。

（2） 忙则等待：当已有进程进入临界区时，表示相应的临界资源正被访问，因而所 有其它试图进入相关临界区的进程必须等待，以保证诸进程互斥访问临界资源。 （3） 有限等待：对要求访问临界资源的进程，应保证该进程能在有限的时间内进入 自己的临界区，以免陷入“永远等待”状态。

（4） 让权等待：当进程不能进入临界区时，应立即释放处理器，以免陷入“忙等”状态。

8．简述进程互斥与同步的概念。

参考答案：多个进程之间彼此无关，它们并不知道其它进程的存在，但由于同处于一个系统中，必然存在着资源共享关系。系统中某些资源一次只允许一个进程使用，这类资源称为临界资源，许多物理设备（如打印机、磁带机等）和许多软件资源（如共享变量、数据、表格、队列等）都属于临界资源。多个进程在共享临界资源时，必须以互斥方式共享。所谓进程同步是指相互合作的进程需按一定的先后顺序执行，以顺利完成某共同任务。具体说，这些进程之间需要交换一定的信息，当某进程未获得其合作进程发来的信息之前，该进程等待，直到接收到相关信息时才继续执行，从而保证诸进程的协调运行。

9．信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。 参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。

V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。

PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。

10． 什么是临界资源？什么是临界区？

参考答案：系统中某些资源一次只允许一个进程使用，这类资源称为临界资源，许多物理设备（如打印机、磁带机等）和许多软件资源（如共享变量、数据、表格、队列等）都属于临界资源。每个进程中访问临界资源的那段代码称为临界区。

11． 在生产者－消费者问题中，如果缺少了V（full）或V（empty），或者将P（full）与P（mutex）互换位置，或者将V（full）与V（mutex）互换位置，结果分别是什么？

参考答案：在生产者－消费者问题中，如果缺少了V（full）或V（empty），系统最终

可能进入死锁状态。将P（full）与P（mutex）互换位置，系统也可能进入死锁状态。将V（full）与V（mutex）互换位置，系统不会出现什么问题，最多只是临界资源的释放推迟。

12． 假设有三个并发进程P，Q，R，其中P负责从输入设备上读入信息并传送给Q，Q将信息加工后传送给R，R则负责将信息打印输出。写出下列条件的并发程序：

（1）进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。

（2）进程P、Q共享一个由m个缓冲区组成的缓冲池，进程Q、R共享另一个由n个缓冲区组成的缓冲池。 参考答案：（1）

第一步：确定进程

3个进程P、Q、R P进程：

? 从输入设备上读入信息 ? 将信息放入缓冲区1 Q进程：

? 从缓冲区1取出信息 ? 将信息放入缓冲区2中 R进程：

? 从缓冲区2取出信息 ? 将信息打印输出

第二步：确定进程的同步、互斥关系

? 同步：P当缓存区1无数据时，才可以向缓冲区1写入信息 ? 同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息 ? 同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息 ? 同步：R当缓存区2有数据时，才可以从缓冲区2读取信息

第三步：设置信号量

? 缓存区1无数据，empty1，初值1 ? 缓存区1有数据，full1，初值0 ? 缓存区2无数据，empty2，初值1 ? 缓存区2有数据，full2，初值0

第四步：用伪代码描述

begin

empty1,empty2,full1,full2：semaphore; empty1 :=1; empty2 :=1; full1 :=0; full2 :=0;

cobegin

P ( ); Q ( );

R ( );

coend;

end;

process P ( )

begin

L1: 从输入设备上读入信息; P（empty1）;

将信息放入缓冲区1； V（full1）; goto L1 end;

process Q ( )

begin

L2:P（full1）;

从缓冲区1取出信息;

V（empty1）; P（empty2）;

将信息放入缓冲区2；

V（full2）; goto L2 end;

process R ( )

begin

L3:P（full2）;

从缓冲区2取出信息;

V（empty2）;

将信息打印输出 ;

goto L3 ; end;

（2）

第一步：确定进程

3个进程P、Q、R P进程：

? 从输入设备上读入信息

? 将信息放入缓冲池1中的一个空缓冲区中 Q进程：

? 从缓冲池1中的一个非空缓冲区中取出信息 ? 将信息放入缓冲池2中的一个空缓冲区中 R进程：

? 从缓冲池2中的一个非空缓冲区中取出信息 ? 将信息打印输出

第二步：确定进程的同步、互斥关系

? 同步：P当缓冲池1中有空的缓冲区时，才可以向缓冲池1写入信息

? 同步：Q当缓冲池1中有非空的缓冲区时，才可以从缓冲池1读取信息 ? 同步：Q当缓冲池2中有空的缓冲区时，才可以向缓冲池2写入信息 ? 同步：R当缓冲池2中有非空的缓冲区时，才可以从缓冲池2读取信息

第三步：设置信号量

? 缓冲池1中的空缓冲区的数量，empty1，初值m ? 缓冲池1中的非空缓冲区的数量，full1，初值0 ? 缓冲池2中的空缓冲区的数量，empty2，初值n ? 缓冲池2中的非空缓冲区的数量，full2，初值0

第四步：用伪代码描述

begin

empty1,empty2,full1,full2：semaphore; empty1 :=m; empty2 :=n; full1 :=0; full2 :=0;

cobegin

P ( ); Q ( );

R ( );

coend;

end;

process P ( )

begin

L1: 从输入设备上读入信息; P（empty1）;

将信息放入缓冲池1中的一个空缓冲区中； V（full1）; goto L1 end;

process Q ( )

begin

L2:P（full1）;

从缓冲池1中的一个非空缓冲区中取出信息;

V（empty1）; P（empty2）;

将信息放入缓冲池2中的一个空缓冲区中；

V（full2）; goto L2 end;

process R ( )

begin

L3:P（full2）;

从缓冲池2中的一个非空缓冲区中取出信息;

V（empty2）;

将信息打印输出 ;

goto L3 ; end;

13． 有四个并发进程：R1，R2，W1和W2，它们共享可以存放一个数的缓冲区。进程R1每次从磁盘读入一个数存放到缓冲区中，供进程W1打印输出；进程R2每次从键盘读一个数存放到缓冲区中，供进程W2打印输出。当缓冲区满时，不允许再向缓冲区中存放数据；当缓冲区空时，不允许再从缓冲区中取出数据打印输出。试用PV操作实现四个进程的协调运行。

参考答案：

第一步：确定进程

4个进程R1、R2、W1、W2 R1进程：

? 从磁盘上读入一个数 ? 将数存放到缓冲区中 W1进程：

? 将R1进程放进缓冲区中的数取出 ? 打印输出 R2进程：

? 从键盘读入一个数 ? 将数存放到缓冲区中 W2进程：

? 将R2进程放进缓冲区中的数取出 ? 打印输出

第二步：确定进程的同步、互斥关系

? 同步：R1当缓存区无数据时，才可以向缓冲区写入数据 ? 同步：R2当缓存区无数据时，才可以向缓冲区写入数据

? 同步：W1当缓存区中是R1写的数据时，才可以将数据从缓冲区中读出 ? 同步：W2当缓存区中是R2写的数据时，才可以将数据从缓冲区中读出

第三步：设置信号量

? 缓存区无数据，empty，初值1

? 缓存区中是R1写的数据，full1，初值0 ? 缓存区中是R2写的数据，full2，初值0

第四步：用伪代码描述

begin

empty, full1,full2：semaphore; empty :=1; full1 :=0; full2 :=0;

end;

cobegin

R1 ( ); R2 ( ); W1 ( ); W2 ( ); coend;

process R1 ( )

begin

L1: 从磁盘上读入一个数； P（empty）;

将数存放到缓冲区中； V（full1）; goto L1 end;

process R2 ( )

begin L2: 从键盘上读入一个数； P（empty）;

将数存放到缓冲区中； V（full2）; goto L2 end;

process W1 ( )

begin

L3:P（full1）;

将缓冲区中的数取出； V（empty）; 打印输出;

goto L3 end;

process W2 ( )

begin

L4:P（full2）;

将缓冲区中的数取出； V（empty）; 打印输出;

goto L4 end;

14． 设公共汽车上，司机的活动顺序是：启动车辆、正常行车、到站停车；售票员的活动顺序是：关车门、售票、开车门。现假设初始状态为：司机和售票员都已经在车上，汽车处于停止状态，车门处于开的状态。在汽车不断地到站、停车、行驶过程中，请用信号量的PV操作实现司机与售票员之间的同步关系。

参考答案：

第一步：确定进程

2个进程 Driver（司机）、Busman（售票员） Driver进程：

? 启动车辆 ? 正常行车 ? 到站停车 Busman进程：

? 关车门 ? 售票 ? 开车门

第二步：确定进程的同步、互斥关系

? 同步：当售票员将车门关上后，司机才可以启动车辆 ? 同步：当司机到站停车后，售票员打开车门

第三步：设置信号量

? 车门关上，close，初值0 ? 到站停车，stop，初值0

第四步：用伪代码描述

begin

close, stop：semaphore; close := 0; stop := 0;

cobegin

Driver ( ); Busman ( ); coend;

end;

process Driver ( )

begin L1: P（close）；

启动车辆；

正常行始； 到站停车； V（stop）； goto L1 end;

process Busman ( )

begin L2: 关车门； V（close）; 售票；

P（stop）; 开车门；

goto L2

end;

15． 哲学家进餐问题：五位哲学家吃面条，只有五根筷子，每个人必须用一双筷子才能吃面条。请用信号量的PV操作描述哲学家之间的关系。 参考答案：错误解法！！！！！！！

第一步：确定进程

5个进程 Pi（i= 0~4） Pi进程：

? 思考

? 拿起左边筷子 ? 拿起右边筷子 ? 吃面条

? 放下右边筷子 ? 放下左边筷子

第二步：确定进程的同步、互斥关系

互斥：筷子是互斥资源， 每个人都只能使用他左右的两根筷子

第三步：设置信号量

? chopstick[5] ：表示5根筷子，初值 1

第四步：用伪代码描述

begin

chopstick[0~4] ：semaphore; chopstick[0~4] := 1;

cobegin

process Pi(i=0,2,…,4) begin

思考；

P（chopstick[i] ）;

P（chopstick[i+1%5] ）; 吃面条；

V（chopstick[i+1%5] ）; V（chopstick[i] ）; end coend;

end;

错误原因：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，都在等待右侧筷

子，无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。 解决方案：

1、 至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他

所使用过的两支筷子,从而可使更多的哲学家进餐。

2、 规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家

则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。

3、 将拿筷子的操作做成原子操作，即当一个哲学家正在拿筷子的时候，其它的哲学家不能

动筷子，当他那好筷子开始吃饭的时候，其它哲学家才可以拿筷子。

这里给出正确解决方案中的第1种方案： 解:

第一步：确定进程

5个进程 Pi（i= 0~4） Pi进程：

? 思考

? 拿起左边筷子 ? 拿起右边筷子 ? 吃面条

? 放下右边筷子 ? 放下左边筷子

第二步：确定进程的同步、互斥关系

互斥：筷子是互斥资源， 每个人都只能使用他左右的两根筷子 同步：只能有四个人同时吃饭

第三步：设置信号量

? chopstick[5] ：表示5根筷子，初值 1 ? num：表示允许吃面的人的个数，初值4

第四步：用伪代码描述

begin

chopstick[0~4] ：semaphore; num : semaphore;

chopstick[0~4] := 1; num := 4;

cobegin

process Pi(i=0,2,…,4) begin

思考； P (num);

P（chopstick[i]）;

P（chopstick[i+1%5] ）; 吃面条；

V（chopstick[i+1%5] ）;

V（chopstick[i] ）; V (num); end coend;

end;

16． 系统中只有一台打印机，有三个进程在运行中都需要使用打印机进行打印输出，问：这三个进程间有什么样的制约关系？试用信号量的PV操作描述这种关系。

参考答案：由于打印机是临界资源，三个进程共享临界资源，是互斥关系。 为临界资源设置互斥信号量s，初始值为1：

begin

s ：semaphore; s := 1;

cobegin

process Pi(i=0,1,2) begin

其他工作； P (s); 打印； V (s); end coend;

end;

17． 根据例2.5，把题目修改为以下几种情况，请用PV操作实现他们之间的同步关系：

（1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。

（2）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。 参考答案：

第一步：确定进程

4个进程Father（爸爸）、Mother（妈妈）、Son（儿子）、Daughter（女儿） Father进程：

? 将苹果放入盘中 Mother进程：

? 将桔子放入盘中 Son进程：

? 从盘中取出桔子 ? 吃桔子 Daughter进程：

? 从盘中取出苹果 ? 吃苹果

第二步：确定进程的同步、互斥关系

? 同步：Father当盘中无水果时，才可以将苹果放入盘中 ? 同步：Mother当盘中无水果时，才可以将桔子放入盘中 ? 同步：Son当盘中有桔子时，才可以从盘中取出桔子

? 同步：Daughter当盘中有苹果时，才可以从盘中取出苹果

第三步：设置信号量

? 盘中无水果，Sp，初值1 ? 盘中有桔子，So，初值0 ? 盘中有苹果，Sa，初值0

第四步：用伪代码描述

begin

Sp,So,Sa：semaphore; Sp :=1; So :=0; Sa :=0;

cobegin

Father ( ); Mother ( ); Son ( );

Daughter ( ); coend; end;

process Father ( ) begin

L1: P（Sp）;

将苹果放入盘中； V（Sa）; goto L1; end;

process Mother ( ) begin

L2: P（Sp）;

将桔子放入盘中； V（So）; goto L2; end;

process Son ( ) begin

L3: P（So）;

从盘中取出桔子； V（Sp） 吃桔子；

goto L3； end;

process Daughter ( ) begin

L4: P（Sa）;

从盘中取出苹果； V（Sp） 吃苹果； goto L4； end;

（2）

第一步：确定进程

3个进程Father（爸爸）、Mother（妈妈）、Son（儿子） Father进程：

? 将苹果放入盘中 Mother进程：

? 将桔子放入盘中 Son进程：

? 从盘中取出水果（桔子或苹果） ? 吃水果（桔子或苹果）

第二步：确定进程的同步、互斥关系

? 同步：Father当盘中无水果时，才可以将苹果放入盘中 ? 同步：Mother当盘中无水果时，才可以将桔子放入盘中

? 同步：Son当盘中有水果（桔子或苹果）时，才可以从盘中取出水果

第三步：设置信号量

? 盘中无水果，empty，初值1 ? 盘中有水果（桔子或苹果），full，初值0

第四步：用伪代码描述

begin

empty, full：semaphore; empty:=1; full :=0;

cobegin

Father ( ); Mother ( ); Son ( ); coend; end;

process Father ( ) begin

L1: P（empty）; 将苹果放入盘中； V（full）; goto L1; end;

process Mother ( ) begin

L2: P（empty）; 将桔子放入盘中； V（full）; goto L2; end;

process Son ( ) begin

L3: P（full）; 从盘中取出水果; V（empty）; 吃水果; goto L3； end;

18． 有一个阅览室，共有100个座位。读者进入阅览室时必须在入口处进行登记；离开阅览室时必须进行注销。试用PV操作描述读者进入/离开阅览室的同步与互斥关系。

参考答案：

第一步：确定进程

可以进入阅览室的读者可以有很多，这里设为n，即

n个Reader（读者）进程 Reader进程：

? 登记

? 进入阅览室 ? 读书

? 离开阅览室 ? 注销

第二步：确定进程的同步、互斥关系

? 同步：当教室内有空座位时，读者才可以登记，并进入阅览室 ? 互斥：同时只能有一个读者在入口处进行登记 ? 互斥：同时只能有一个读者在出口处进行注销

第三步：设置信号量

? 教室内空座位数量，seat，初值100

? 为入口处进行登记设置互斥信号量Sin，初值 1，表示当前可用 ? 为出口处进行注销设置互斥信号量Sout，初值 1，表示当前可用

第四步：用伪代码描述

begin

Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1;

cobegin

process Reader-i ( i = 1,2,…,n ); begin

P(seat); P(Sin);

登记; V(Sin); 进入阅览室; 读书;

离开阅览室; P(Sout); 注销;

V(Sout);

V（seat）; end coend; end;

19． 某工厂有一个可以存放设备的仓库，总共可以存放10台设备。生产的每一台设备都必须入库，销售部门可从仓库提出设备供应客户。设备的入库和出库都必须借助运输工具。现只有一台运输工具，每次只能运输一台设备。请设计一个能协调工作的自动调度管理系统。

参考答案：

第一步：确定进程

可以为入库（Pin）和出库（Pout）各设置一个进程 Pin进程：

? 生产了一台设备 ? 使用运输工具入库 Pout进程：

? 使用运输工具出库 ? 提出设备供应客户

第二步：确定进程的同步、互斥关系

? 同步：当仓库中有空余位置存放设备时，设备才可以入库 ? 同步：当仓库中有存放的设备时，设备才可以出库 ? 互斥：运输工具是临界资源，要互斥访问

第三步：设置信号量

? 仓库中有空余位置数量，empty，初值10 ? 仓库中有存放的设备数量，full，初值 0

? 为运输工具设置互斥信号量S，初值 1，表示当前可用

第四步：用伪代码描述

begin

empty, full, S：semaphore; empty := 10;

full := 0; S := 1; cobegin Pin (); Pout (); coend; end;

process Pin ( ) begin

L1: 生产了一台设备 ;

P（empty）;

P (S);

使用运输工具入库; V （S）;

V（full）; goto L1; end;

process Pout ( ) begin

L2: P（full）;

P (S);

使用运输工具出库; V （S）; V（empty）;

提出设备供应客户;

goto L2; end;

20． 进程通信主要有哪几种类型？

参考答案：进程通信的类型主要有：共享存储器系统、消息传递系统以及管道通信系统。

21． 高级调度与低级调度的主要任务是什么？为什么要引入中级调度？ 参考答案：高级调度又称作业调度，其任务是从外存上的后备队列中按照一定的原则选择若干个作业调入内存，为他们创建进程，分配必要的资源，如内存、外设等，并将新创建的进程插入就绪队列，准备执行。低级调度通常又称为进程调度，其任务是决定就绪队列中的哪个进程获得处理器，然后由分派程序把处理器分配给该进程，为它恢复运行现场，让其运行。引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。

22． 引起进程调度的原因有哪些？ 参考答案：引起进程调度的原因有：（1）正在执行的进程执行完毕，或因发生某事件而不能再继续执行；（2）执行中的进程因提出I/O请求而暂停执行；（3）在进程通信或同步过程中执行了某种原语操作；（4）当采用基于优先权的强占式调度算法时，就绪队列中出现优先级比当前正在执行的进程优先级更高的进程时；（5）当采用时间片轮转调度算法时，当前进程的时间片用完了。

23． 选择进程调度算法的原则有哪些？ 参考答案：一个操作系统如何选择调度方式和算法，在很大程度上取决于操作系统的类型和目标，通常应尽量遵循以下几方面的原则： （1） 周转时间短。从作业提交开始到作业完成为止的时间间隔称为周转时间，它包

括作业等待进入内存、进程在就绪队列中等待、进程在CPU上执行和完成I/O操作所花费的时间总和。它主要用于评价批处理系统。为了能更准确地评价系统的性能，引入了另一个指标：带权周转时间，即作业的周转时间与系统实际为其提供的服务时间之比。 （2） 响应时间快。从用户通过键盘提交一个请求开始，直至系统首次产生响应为止

的时间间隔称为响应时间，主要用于评价分时系统。

（3） 要保证截止时间。所谓截止时间，是指某任务必须开始执行的最迟时间，或必

须完成的最迟时间，主要用于评价实时系统。

（4） CPU利用率高。 当CPU的价格非常昂贵时，希望尽可能使它得到充分利用。

CPU的利用率可从0％到100％，但在实际系统中，一般是在40％～90％之间。 （5） 系统吞吐量高。 所谓系统吞吐量，是指单位时间内系统所完成的作业数量，

主要用于评价批处理系统。

24． 批处理操作系统、分时操作系统和实时操作系统常用哪些进程调度算法？ 参考答案：批处理操作系统常用的进程调度算法有：先来先服务调度算法、短进程优先调度算法、高优先权优先调度算法、高响应比优先调度算法；分时操作系统常用的进程调度算法有：时间片轮转调度算法、多级反馈队列调度算法；实时操作系统常用的进程调度算法主要有：高优先权优先调度算法。

25． 什么是静态优先权和动态优先权？各有何优缺点？ 参考答案：静态优先级是在进程创建时根据进程的类型、进程对资源的需求以及用户的要求而确定的，在进程的整个运行期间保持不变。对于动态优先级，也是在创建进程时为进程赋予一个初始优先级，以后在进程的运行过程中随着进程特性的变化，不断修改优先级，如随着进程在就绪队列中等待时间的增长，可提高进程的优先级；随着进程连续占用CPU时间的增长，可降低其优先级，防止一个进程长期垄断CPU等。

26． 设有五个进程，它们到达就绪队列的时刻和运行时间如表2－5所示。若分别采用先来先服务算法和短进程优先算法，试给出各进程的调度顺序以及平均周转时间。

表2－5 各进程到达就绪队列的时刻、运行时间

进程 P1 P2 P3 到达时刻 10.1 10.3 10.4 运行时间 0.3 0.9 0.5

P4 P5 10.5 10.8 0.1 0.4 参考答案：

(1)先来先服务（FCFS） 调度顺序 1 2 3 4 5 进程 P1 P2 P3 P4 P5 到达时刻 10.1 10.3 10.4 10.5 10.8 运行时间 0.3 0.9 0.5 0.1 0.4 开始时间 10.1 10.4 11.3 11.8 11.9 完成时间 10.4 11.3 11.8 11.9 12.3 周转时间 0.3 1.0 1.4 1.4 1.5 平均周转时间：T＝（0.3 + 1.0 + 1.4 + 1.4 + 1.5）/ 5 = 1.12 (2) 短进程优先（SPF） 调度顺序 1 2 3 4 5 进程 P1 P3 P4 P5 P2 到达时刻 10.1 10.4 10.5 10.8 10.3 运行时间 0.3 0.5 0.1 0.4 0.9 开始时间 10.1 10.4 10.9 11.0 11.4 完成时间 10.4 10.9 11.0 11.4 12.3 周转时间 0.3 0.5 0.5 0.6 2.0 平均周转时间：T＝（0.3 + 0.5 + 0.5 + 0.6 + 2.0）/ 5 = 0.78

27． 设有四个进程，它们到达就绪队列的时刻、运行时间及优先级（此处优先级1为最低优先级，优先级4为最高优先级）如表2－6所示。若分别采用非抢占式优先级调度算法和可抢占式优先级调度算法，试给出各进程的调度顺序以及平均周转时间。

表2－6 各进程到达就绪队列的时刻、运行时间及优先级

进程 P1 P2 P3 P4 到达时刻 0 1 2 3 运行时间 8 3 7 12 优先级 1 3 2 4 参考答案：

(1) 非抢占式优先级调度算法 调度顺序 1 2 3 4 进程 P1 P4 P2 P3 优先级 1 4 3 2 到达时刻 0 3 1 2 运行时间 8 12 3 7 开始时间 0 8 20 23 完成时间 8 20 23 30 周转时间 8 17 22 28 平均周转时间：T＝（8 + 17 + 22 + 28）/ 4 = 18.75

(2) 抢占式优先级调度算法 调度 顺序 1 进程 P1 优先级 1 到达 时刻 0 剩余运行时间 8 开始 时间 0 停止 时间 1 共完成时间 1 状态 未完成 周转 时间 2 3 4 5 6 P2 P4 P2 P3 P1 3 4 3 2 1 1 3 1 2 0 3 12 1 7 7 1 3 15 16 23 3 15 16 23 30 2 12 3 7 8 未完成 完成 完成 完成 完成 12 15 21 30 平均周转时间：T＝（12 + 15 + 21 + 30）/ 4 = 19.5

28． 什么是死锁？产生死锁的原因和必要条件是什么？处理死锁的基本方法有哪些？

参考答案：若系统中存在一组进程（两个或两个以上），它们中的每一个都占用了某些资源而又都在等待其中另一个进程所占用的资源，这种等待如果没有外力作用，将永远不会结束，这就是“死锁”，或说这一组进程处于“死锁”状态。

产生死锁的原因主要有两个：一是多个进程竞争资源，二是进程请求和释放资源的时机不对。

产生死锁的必要条件有：互斥条件、占有且等待条件、不可剥夺条件、循环等待条件。处理死锁的基本方法有：预防死锁、避免死锁、检测和解除死锁。

29． 什么是线程？简述与进程的区别和联系。

参考答案：线程是进程中的一个实体，是CPU调度和分派的基本单位。

线程具有许多传统进程的特征，故又称为轻型进程。传统的进程称为重型进程，相当于只有一个线程的任务。在引入线程的操作系统中，通常一个进程拥有若干个线程，至少也有一个线程。下面从调度、并发性、拥有资源和系统开销几个方面对线程和进程进行比较。

（1）调度。在传统的操作系统中，进程既是资源分配和拥有的基本单位，又是独立调度和执行的基本单位。而在引入线程后，则把线程作为调度和执行的基本单位，把进程作为资源分配和拥有的基本单位，把传统进程的两个属性分开，使线程轻装运行，从而显著提高系统的并发程度。同一进程中两个线程的切换不会引起进程切换，但由一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换。

（2）并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行，因而使系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。

（3）拥有资源。不论是传统的操作系统，还是引入线程的操作系统，进程都是拥有资源的独立单位。线程基本上不拥有资源（只有一点运行时必不可少的资源），但它可以访问其所属进程的全部资源。亦即一个进程的代码段、数据段以及系统资源（如已打开的文件、I/O设备等），可供该进程的所有线程共享。

（4）系统开销。系统在创建或撤消进程时，都要为之分配或回收资源，如内存空间、I/O设备等，因此系统所付出的开销将显著地大于创建或撤消线程的开销。同样，在进行进程切换时，需要保存当前进程的执行环境，设置和恢复被调度进程的执行环境，而线程切换只需保存和设置少量寄存器的内容，不涉及存储管理方面的操作，因而进程切换的开销也远大于线程切换的开销。

第三章习题

1．什么叫重定位？它有哪两种方式？这两种方式有什么区别？

参考答案：当程序装入内存时，操作系统将为该程序分配一个合适的内存空间，由于程序的逻辑地址与所分配到内存的物理地址不一致，而CPU执行指令时是按物理地址进行的，为使程序能正确运行，必须将用户程序中的逻辑地址转换成内存中的物理地址，这个地址转换过程就称为“重定位”，又称为“地址映射”。它有静态重定位和动态重定位两种方式。

两者的区别是：静态重定位是当用户程序被装入内存时，由装入程序一次性地把逻辑地址转换成物理地址，以后不再转换，它不需要增加硬件地址转换机构，但程序在内存中需占据一片连续区域，并且在重定位之后就不能再移动位置。动态重定位是把程序装入内存后，并不立即将程序中的逻辑地址转换为物理地址，而是在CPU执行每一条指令时进行地址转换，程序装入内存后可移动位置，不必连续存放在一起，但是需要硬件地址变换机构的支持。

2．在动态分区分配方式中，若采用最先适应算法，应如何回收内存？

参考答案：在动态分区分配方式中，若采用最先适应算法，则在回收一块内存空间时，首先根据回收区的始址在空闲分区链中查找插入点，找到后，按照下面四种情况进行回收：

（1）回收分区（记为R）与其前面的空闲分区（记为F1）邻接：合并R与F1，修改

空闲分区表中F1的大小，即加上R的大小，始址不变。

（2）回收分区（记为R）与其后面的空闲分区（记为F2）邻接：合并R与F2，修改

空闲分区表中F2的大小，即加上R的大小，始址不变。

（3）回收分区（记为R）与其前后的空闲分区（分别记为F1和F2）均邻接：合并R

与F1、F2，修改空闲分区表中F1的大小，即加上R与F2的大小，始址不变。 （4）回收分区（记为R）与其前后的空闲分区（分别记为F1和F2）均不邻接：在空

闲分区表中增加一条记录，该空闲分区的始址和大小，即为R的始址和大小。

3．动态分区分配的常用算法有哪些？各有什么特点？ 参考答案：动态分区分配的常用的内存分配算法

（1）最先适应算法。该算法要求空闲分区表按各分区起始地址递增的顺序排列。每次分配时，总是从第一条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割该空闲区，一部分分配给作业，余下部分仍为空闲区。该算法可能将大的空闲分区分割成多个小分区，从而使系统产生很多小得无法再用的“碎片”。

（2）最优适应算法。从所有空闲分区中挑选一个大小能满足作业要求的最小分区，这样可以保证不去分割一个更大的分区，使装入大作业时比较容易得到满足。为提高查找效率，将空闲分区表按各分区大小递增的顺序排列，分配时，顺序查找空闲分区表，直到找到一个大小满足作业要求的分区为止。

（3）最坏适应算法。与最优适应算法相反，该算法要求将空闲分区表按各分区大小递减的顺序排列，每次分配时从所有空闲分区中挑选一个最大的分区，分割一部分给作业使用，使剩下的部分不至于太小，仍可供使用，但不容易保留下大的空闲分区，不利于大作业的内存分配。

4． 在可变分区存储管理中，设作业A（30KB），作业B（70KB），作业C（50KB）依次请求内存分配，内存现有两个空闲区：F1（100KB）和F2（50KB），如图3－18所示。若分别采用最先适应算法、最优适应算法和最坏适应算法，画出内存分配情况图。

已分配 F1（100KB） 已分配 F2（50KB） 图3－18 内存使用情况示意图

参考答案：

（1） 采用最先适应算法分配：

已分配 作业A（30KB） 作业B（70KB） 已分配 作业C（50KB）

（2） 采用最优适应算法分配： 已分配 作业B（70KB） F1（30KB） 已分配 作业A（30KB） F2（20KB） 作业C没有足够的空闲分区分配，只有等待系统回收到足够空闲内存后再装入内存。 （3） 采用最坏适应算法分配：

已分配 作业A（30KB） 作业B（70KB） 已分配 作业C（50KB）

5．什么是对换？为什么要引入对换？ 参考答案：对换就是把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程或进程所需要的程序和数据，换入内存。引入对换的目的是为了提高内存的利用率。

6．简述分页系统的地址变换过程。 参考答案：在系统中设置了一个页表寄存器，用于存放当前执行进程的页表在内存的始址和页表长度。进程未执行时，其页表始址和页表长度存放在它的PCB中；当进程被调度执行时，这两个数据就被装入页表寄存器中。每当CPU要访问内存时，地址变换机构会自动将逻辑地址分为页号和页内地址两部分，然后将页号与页表长度进行比较，若页号不小于页表长度，说明本次所访问的地址已超越进程的地址空间，产生“地址越界”中断，并停止执行该指令。若未出现越界错误，则用页号检索页表，找到对应的表项后，从中得到该页面在内存的块号，并将块号送入物理地址寄存器中。与此同时，将逻辑地址中的页内地址直接送入物理地址寄存器的块内地址字段中，便得到了物理地址。整个地址转换过程如图3－10所示（图中页面大小为1KB）。可根据下式由块号计算出物理地址：

物理地址＝块号×块长（即页面大小）＋ 页内地址

7．分页和分段存储管理有何区别？ 参考答案：（1）页是信息的物理单位，分页是为实现离散分配方式，以减少内存的外零头，提供内存的利用率。段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地满足用户的需要。

（2）页的大小固定且由系统决定，是由机器硬件实现的；而段的长度却不固定，决定

于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

（3）分页的作业地址空间是一维的，即单一的线性地址空间；而分段的作业地址空间

是二维的，由段名（或段号）和段内地址构成。

8．简述分段系统的地址变换过程。 参考答案：分段系统的地址转换采用动态重定位方式。在系统中设置了一个段表寄存器，用于存放当前执行进程的段表在内存的始址和段表长度。每当CPU要访问内存时，地址变换机构就将逻辑地址中的段号与段表长度进行比较，若段号不小于段表长度，产生“地址越界”中断，停止执行该指令。若未越界，则用段号检索段表，找到对应的表项后，从中得到该段的基址和段长，然后检查段内地址是否超出该段的段长，若超出，则发出“地址越界”中断，停止执行该指令。若未越界，就用基址加上段内地址，得到访存的物理地址。

9． 在一分页系统中，页面大小为4KB，某个已装入内存的作业的页表如表3－3所示。请计算下列逻辑地址所对应的物理地址：378，15034，5700，30000。

表3－3 作业页表 表3－4 作业段表 表3－5 作业页表

页号 0 1 2 3 4 块号 3 9 10 6 15

段号 0 1 2 3 4 段始址 2100 3500 200 1200 5400 段长 630 180 150 300 1120

页号 0 1 2 3 4 块号 15 20 33 － － 状态 1 1 1 0 0 参考答案：（1）逻辑地址378： 页号＝378/4096＝0

页内地址＝378MOD4096＝378

用页号0查找页表，找到对应的块号为3，则物理地址为： 物理地址＝块号×页面大小＋页内地址＝3×4096＋378＝12666 （2）逻辑地址15034：

页号＝15034/4096＝3

页内地址＝5700MOD4096＝2746

用页号3查找页表，找到对应的块号为6，则物理地址为：

物理地址＝块号×页面大小＋页内地址＝6×4096＋2746＝27322 （3）逻辑地址5700：

页号＝5700/4096＝1

页内地址＝5700MOD4096＝1604

用页号1查找页表，找到对应的块号为9，则物理地址为：

物理地址＝块号×页面大小＋页内地址＝9×4096＋1604＝38468

（4）逻辑地址30000：

页号＝30000/4096＝7

页内地址＝30000MOD4096＝1328

用页号3查找页表，发现越界，发出越界中断信号，终止程序运行。

10． 在一分段系统中，某个已装入内存的作业的段表如表3－4所示。计算下列逻辑地址所对应的物理地址：（0，311），（1，120），（2，230），（4，800）。

参考答案：（1）逻辑地址（0，311） 使用段号0查找段表，找到对应的表项后，用段内地址311与段长进行比较，没有越界，计算物理地址＝段始址＋段内地址＝2100＋311＝2411 （2）逻辑地址（1，120）

使用段号1查找段表，找到对应的表项后，用段内地址120与段长进行比较，没有越界，计算物理地址＝段始址＋段内地址＝3500＋120＝3620 （3）逻辑地址（2，230）

使用段号2查找段表，找到对应的表项后，用段内地址230与段长进行比较，发现越界，发出越界中断信号，终止程序运行。 （2）逻辑地址（4，800）

使用段号4查找段表，找到对应的表项后，用段内地址800与段长进行比较，没

有越界，计算物理地址＝段始址＋段内地址＝5400＋800＝6200

11． 简述段页式系统的地址变换过程。

参考答案：为实现地址转换，系统设置了一个段表寄存器，用于存放当前执行进程的段表始址和段表长度。进行地址转换时，首先检查段号是否超出段表长度，如果是，产生越界中断；否则，使用段号检索段表，找到对应的段表项后，从中得到该段的页表始址和页表长度，再检查页号是否超出页表长度，如果是，产生越界中断；否则，使用页号检索页表，找到对应的页表项后，从中得到该页对应的物理块号，再与页内地址一起组成物理地址。

12． 什么叫虚拟存储器？它有哪些特征？

参考答案：所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。从用户角度看，该系统所具有的内存容量比实际内存容量大得多，但这只是用户的一种感觉，是虚的，故而得名虚拟存储器。 虚拟存储器的特征有：虚拟扩充、部分装入、多次对换。

13． 在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？

参考答案：在请求分页系统中，页表应包括：页号、物理块号、状态位、访问位、修改位、外存地址。其中“状态位”表示该页是否在内存；“访问位”表示该页调入内存后是否被访问过以及被访问的情况；“修改位”表示该页调入内存后是否被修改过；“外存地址”指出该页在外存上的地址，通常是盘块号。

14． 在请求分页系统中，常用的页面置换算法有哪些？各有何特点？ 参考答案：在请求分页系统中，常用的页面置换算法及其特点描述如下：

（1） 先进现出（FIFO）页面置换算法：这是一种最简单的置换算法，它总是淘汰最

先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法虽

然实现容易，但由于没有考虑页面调入内存后被访问的情况，使其性能较差，故很少单独使用。

（2） 最近最久未使用（LRU）置换算法：LRU置换算法是根据页面调入内存后的使

用情况来选择淘汰页的，即它总是选择最近一段时间内最长时间没有被访问的页面予以淘汰。LRU置换算法考虑了页面调入内存后的使用情况，具有较好的性能，但要快速的找出最近最久未被使用的页面，却要花费巨大的系统开销，往往需要较多的硬件支持，因此在实际系统中往往使用其近似算法。

（3） 最近未使用（NUR）置换算法：该算法又被称为Clock置换算法，是LRU算法

的近似算法。它总是选择最近一段时间内未被访问的页面予以淘汰。

（4） 最少使用（LFU）置换算法：该算法是LRU算法的近似算法。它选择过去一段

时间里被访问次数最少的页面予以淘汰。

15． 在一个请求分页系统中，内存容量为1MB，被划分为256块，每块为4KB。有一作业，其页表如表3－5所示。（1）计算逻辑地址9016所对应的物理地址；（2）对逻辑地址12300，试给出其物理地址的转换过程。

参考答案：（1）逻辑地址9016： 页号＝9016/4096＝2

页内地址＝9016MOD4096＝824

用页号2查找页表，找到对应的块号为33，则物理地址为：

物理地址＝块号×页面大小＋页内地址＝33×4096＋824＝135992

（2）逻辑地址12300：

页号＝12300/4096＝3

页内地址＝12300MOD4096＝12

用页号3查找页表，发现该页还在内存，发生缺页中断，等把页面调进内存后

再重新进行地址转换工作。

16． 在一个请求分页系统中，假设一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，若分配给该作业的物理块数为4，假设当前没有任何页面在内存，分别采用FIFO和LRU页面置换算法，试计算在运行过程中发生的缺页次数和缺页率，并比较所得结果。

参考答案：（1）采用FIFO页面置换算法： 访问4 页面 缺页 是 内 存 块 4 换页 3 是 4 3 2 是 4 3 2 1 是 4 3 2 1 4 否 4 3 2 1 3 否 4 3 2 1 5 是 5 3 2 1 4 4 是 5 4 2 1 3 3 是 5 4 3 1 2 2 是 5 4 3 2 1 1 是 1 4 3 2 5 5 是 1 5 3 2 4 缺页次数是：10次，缺页率＝缺页次数/访问次数＝10/12＝83.3% （2）采用LRU页面置换算法：

访问4 页面 缺页 是 内 存 块 4 换页 3 是 4 3 2 是 4 3 2 1 是 4 3 2 1 4 否 4 3 2 1 3 否 4 3 2 1 5 是 4 3 5 1 2 4 否 4 3 5 1 3 否 4 3 5 1 2 是 4 3 5 2 1 1 是 4 3 1 2 5 5 是 5 3 1 2 4 缺页次数是：8次，缺页率＝缺页次数/访问次数＝8/12＝66.7%

17． 提高内存利用率的途径有哪些？ 参考答案：提高内存利用率的途径有： （1）改连续分配方式为离散分配方式； （2）增加对换和覆盖机制； （3）引入动态链接机制； （4）引入虚拟存储器机制； （5）引入存储器共享机制。

第四章习题

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

参考答案：设备管理的主要功能是：设备分配、缓冲管理、设备处理。

2． 按工作特性可把设备分为哪几种类型？按设备的共享属性可把设备分为哪几种类型？

参考答案：按工作特性可把设备分为存储设备和I/O设备，按设备的共享属性可把设备分为独享设备、共享设备和虚拟设备。

3． 什么是设备独立性？引入设备独立性有什么好处？

参考答案：用户在编程时使用的设备与程序运行时实际使用的设备无关，称为“设备独立性”，设备独立性能提高系统进行设备分配时的适应性和灵活性。

4． 设备控制器的主要功能有哪些？

参考答案：作为CPU与设备间的接口，设备控制器通常具有如下功能：①接收和识别由CPU发来的各种命令，并对这些命令进行译码；②实现CPU与控制器、控制器与设备之间的数据交换和数据缓冲；③将设备和控制器当前所处的状态提供给CPU；④实现CPU和设备之间的通信控制，进行端口地址译码。

5． I/O控制方式有哪几种？各有什么特点？ 参考答案：I/O控制方式包括：

（1） 程序直接控制方式，用于早期没有中断硬件技术的系统中，其缺点是CPU与

设备完全串行工作，而设备的速度远低于CPU，致使CPU大部分时间处于等待状态，严重降低了CPU的利用率。

（2） 中断驱动控制方式，它使CPU和设备可以并行工作，显著提高了CPU的利

（3）

（4）

用率，至今仍然是字符设备的I/O控制方式。

DMA方式，主要用于块设备的I/O控制。该方式的最大特点是数据传送直接在设备与内存之间进行，整块数据的传送是由DMA控制器完成的，仅在数据传送开始和结束时才需CPU干预，较之中断驱动控制方式，进一步减少了CPU对I/O操作的干预。

通道控制方式，通道控制方式与DMA方式类似，也是一种以内存为中心，实现设备与内存直接进行数据交换的控制方式。与DMA方式相比，CPU对I/O控制的干预更少，从而进一步减轻了CPU的负担。

6． 简述独占设备的分配过程。

参考答案：独占设备分配一般分为三个步骤：分配设备、分配控制器、分配通道。 （1）分配设备。根据进程所请求的设备类型，检索系统设备表，找到第一个该类设备的控制表，从其“状态”字段可知设备忙闲情况。若设备忙，则查找第二个该类设备的控制表，仅当所有该类设备都忙时，才把进程插入该类设备的等待队列上。只要有一个该类设备空闲，就可以分配给进程。

（2）分配控制器。当系统把设备分配给进程后，从该设备的控制表中找到与此设备相连的控制器的控制表，从其“状态”字段可知该控制器是否忙碌。若控制器忙，将该进程插入控制器等待队列；否则，将该控制器分配给进程。

（3）分配通道。当把控制器分配给进程后，从该控制器的控制表中找到与其相连的通道的控制表，从其“状态”字段可知该通道是否忙碌。若通道忙，将进程插入通道等待队列；否则将该通道分配给进程。

当进程分配到设备、控制器和通道后，就可以进行数据传输工作了。

7． 简述设备驱动程序的特点和功能。 参考答案：设备驱动程序最大的特点是与硬件特性紧密相关，它包括了所有与设备相关的代码，因而其中的部分代码必须用汇编语言编写。每个设备驱动程序只处理一种设备，或者一类紧密相关的设备，因而对不同类型的设备应配置不同的驱动程序。例如，可以为相同的多个终端配置一个驱动程序。但有时即使是同一类型的设备，由于其生产厂家不同，也可能不完全兼容，此时也必须为它们配置不同的驱动程序。另外，驱动程序与设备所采用的I/O控制方式紧密相关，如常用的中断驱动方式和DMA方式的驱动程序就明显不同。

设备驱动程序的主要功能是从与设备无关的软件中接收抽象的请求并执行，具体包括以下几个方面：①将接收到的抽象要求转化为具体要求；②检查用户I/O请求的合法性，了解设备的状态，传递有关参数，设置设备的工作方式；③发出I/O命令，启动分配到的I/O设备，完成指定的I/O操作；④及时响应由控制器或通道发来的中断请求，并调用相应的中断处理程序进行中断处理；⑤对于设置有通道的计算机系统，驱动程序还应能根据用户的I/O请求，自动地构成通道程序。

8． 为什么要引入缓冲？简述缓冲池的实现机制。 参考答案：引入缓冲的主要目的是：

（1）缓和CPU与I/O设备间速度不匹配的矛盾，提高它们之间的并行性。 （2）减少对CPU的中断频率，放宽CPU对中断响应时间的限制。 缓冲池的实现机制：

缓冲池由多个缓冲区组成，这些缓冲区可供多个进程共享，既能用于输入，也能用于输出。为管理方便，将所有缓冲区组织成三个队列：①空缓冲队列：由空缓冲区组成；②输入

队列：由装满输入数据的缓冲区组成；③输出队列：由装满输出数据的缓冲区组成。

各进程在使用缓冲池中的缓冲区时，通常有下面四种情况：①当输入进程需要输入数据时，便从空缓冲队列的队首摘下一空缓冲区，把数据输入其中，装满后将其挂到输入队列末尾。②当计算进程需要输入数据进行计算时，便从输入队列取得一个缓冲区，从中提取数据进行计算，数据用完后再将其挂到空缓冲队列末尾。③当计算进程需要输出数据时，便从空缓冲队列的队首摘下一个空缓冲区，将数据输出到其中，当缓冲区装满输出数据后，再将它挂到输出队列末尾。④当输出进程要输出时，便从输出队列取得一个装满输出数据的缓冲区，输出其中的数据，数据输出完后，再将其挂到空缓冲队列末尾。

9． 什么是设备虚拟技术？以共享打印机的实现为例，说明SPOOLing系统是如何实现设备虚拟的？

参考答案：为提高独占设备的利用率和系统效率，人们使用共享设备来模拟独占设备，将独占设备改造成共享设备，这种技术称为设备虚拟技术。

共享打印机是SPOOLing技术的典型应用。当用户进程请求打印输出时，SPOOLing系统为其做两件事：①由“输出井写”程序将用户进程要打印的数据存放到输出井中；②为用户进程申请一张空白的请求打印表，并填入用户的打印要求，然后将其挂到请求打印队列上。如果还有其他用户进程请求打印输出，系统仍可接收该请求，同样为该进程做上述两件事。

如果打印机空闲，缓输出程序就从请求打印队列的队首取出一张请求打印表，根据表中的打印要求从输出井中取出待打印数据，由打印机进行打印。重复上述过程，直到请求打印队列为空，缓输出程序就阻塞等待新的打印请求。

10． 简述SPOOLing系统的组成。 参考答案：

SPOOLing系统包括输入井和输出井、预输入程序和缓输出程序、井管理程序几个部分，如图4－6所示。

输入设备输出设备预输入程序作业执行缓输出程序主机系统输出井磁盘输入井

图4－6 SPOOLing系统的组成

（1）输入井和输出井。这是在磁盘上开辟的两个大的存储区，输入井用于预先存放从I/O设备输入的各作业的全部信息，输出井用于暂时存放各运行作业的输出信息。

（2）预输入程序和缓输出程序。预输入程序的任务是预先把作业的全部信息输入到磁盘上的输入井中保存，作业执行时只需从输入井中读入相关信息，而不必启动输入设备。缓输出程序的任务是启动输出设备对输出井中等待输出的作业信息进行输出。

（3）井管理程序。它又分为“输入井读”和“输出井写”两个程序。当要求读信息时，由输入井读程序从输入井中找出作业所需信息并传送给作业；当作业要求输出信息时，由输出井写程序把输出信息存放到输出井中。

11． 磁盘访问时间包括哪三个部分？

参考答案：磁盘访问时间包括以下三个部分：

（1）寻道时间Ts：是指把磁头从当前位置移动到指定磁道所需要的时间，它是影响磁盘数据传输率的重要参数，与磁头移过的磁道数量成正比，一般磁盘为5～15ms。

（2）旋转延迟时间Tr：是指定扇区旋转到磁头下面所需要的时间，与磁盘转速有直接关系，设r为磁盘转速，则Tr平均＝1/(2r)。若r＝7200转/分钟，则Tr为4.05ms。

（3）传输时间Tt：把数据从磁盘读出或向磁盘写入所需要的时间，它与磁盘的转速以及要读/写的字节数有关。

综上所述，可将磁盘访问时间Ta表示为：

Ta＝寻道时间Ts＋旋转延迟时间Tr＋传输时间Tt

第五章习题

1．什么是文件？什么是文件系统？文件系统有哪些功能？ 参考答案：

文件是具有符合名的、在逻辑上有完整意义的信息项的有序集合。所谓文件系统是指被管理的文件、对文件进行管理的一组软件以及实现管理功能所需要的数据结构的总体。

文件系统的功能：文件存储空间的管理、文件目录管理、文件读写管理、文件共享与保护。

2．什么是文件的逻辑结构？文件的逻辑结构有哪些？ 参考答案：文件的逻辑结构是从用户观点出发所观察到的文件结构，它独立于文件的物理特性，用户也是按照逻辑结构来使用文件的。文件的逻辑结构可分为有结构文件和无结构文件两大类。

3．什么是文件的物理结构？文件的物理结构有哪些？各有什么特点？ 参考答案：文件的物理结构又称为文件的存储结构，是指文件在外存上的存储组织形式，它与存储介质的物理特性、文件的存取方法以及所采用的存储空间的分配方式都有关。

文件的物理结构及其特点如下：

（1）连续文件：连续文件又称为顺序文件，它是把逻辑文件中的信息顺序地存放到一组邻接的物理盘块中而形成的物理文件。显然，这种文件结构保证了文件中逻辑记录的顺序与外存中文件占用盘块的顺序的一致性。连续文件的最大优点是顺序存取速度快，其缺点是由于存储文件要求有连续的存储空间，不便于文件的动态增长，且容易使外存产生碎片，降低了外存的利用率。

（2）链接文件：把一个逻辑上连续的文件分散存放在多个不要求连续的盘块中，再使用链接指针将这多个可能不连续的盘块链接起来，这样形成的物理文件称为链接文件。链接文件消除了外存的碎片，提高了外存的利用率，同时使文件很容易实现动态增长。根据对链接指针处理方式的不同，链接文件又可分为隐式链接和显示链接两种。

（3）索引文件：仍然是把一个逻辑上连续的文件分散存放在多个不要求连续的盘块中，并为该文件建立一张索引表，每个逻辑块占一个表项，按逻辑块号排列，表项内容为该逻辑块所对应的物理盘块号。然后再把索引表本身存放在另一个盘块中，把这个存放索引表的盘块称为索引块，并把索引块的盘块号作为文件的物理地址填入文件目录项中。

4．文件控制块中主要包括哪些内容？ 参考答案：

虽然不同的系统，其文件控制块的内容和格式不完全相同，但通常都包括以下三类信息：基本信息、存取控制信息和使用信息。

（1）基本信息。包括文件名、用户名、文件类型、文件的物理地址、文件长度、文件的逻辑结构和物理结构等。其中用户名主要是指文件主和授权用户；而物理地址的内容通常与文件的物理结构有关，对于连续文件和链接文件，应说明起始盘块号，而对于索引文件，应给出其索引块号。

（2）存取控制信息。分别给出文件主、伙伴用户、一般用户的存取权限。

（3）使用信息。包括文件的建立日期及时间、上次存取文件的日期及时间、当前的使用信息等。

5．什么是文件目录？系统对目录管理的要求有哪些？ 参考答案：系统中所有文件控制块的有序集合构成文件目录，一个文件控制块就是一个目录项，文件目录存放在磁盘上。

操作系统对文件目录管理通常有以下几方面的要求： （1）实现“按名存取”。即用户只需提供文件名，就可对文件进行存取。这是目录管理最基本的功能，也是文件系统向用户提供的最基本的服务。

（2）提高目录的检索速度。合理地组织目录结构，可加快目录的检索速度，从而提高文件的存取速度。对于大中型文件系统来说，这是一个很重要的设计目标。

（3）允许文件重名。为了便于用户按照自己的习惯来命名和使用文件，文件系统应该允许对不同的文件取相同的名字。

（4）允许文件共享。在多用户系统中，应该允许多个用户共享一个文件，这样，就只需在外存上保留一份该文件的副本，从而节省大量的存储空间，并方便用户共享文件资源。

6．目前常用的目录结构是哪种结构？它有什么优点？

参考答案：目前常用的目录结构是多级目录，或称树型目录。与单级和两级目录结构相比，多级目录结构具有以下优点：

（1）层次清楚。系统或用户可以把不同类型的文件放置在不同的子目录下，便于查找；同时不同层次和不同用户的文件可以被赋予不同的存取权限，有利于文件的保护。

（2）解决了文件重名问题。在多级目录结构中，不仅允许不同用户可以使用相同的名字去命名不同的文件，而且允许同一用户在自己的不同子目录中使用相同的文件名。

（3）便于实现文件共享。允许不同的用户按自己的命名习惯为共享文件赋予不同的名字，即不同的用户可使用不同的文件名访问同一个共享文件。

（4）搜索速度快。由于对多级目录的查找每次只查找目录的一个子集，因此其搜索速度较单级、两级目录更快。

7．某文件是链接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小一致，均为512B，依次存放在25，30，32，60，78号盘块上。若要存取文件的第1518逻辑地址处的信息，需要访问哪一个磁盘块？

参考答案： 逻辑盘块号 = 1518 MOD 512 = 2

块内地址 = 494

逻辑盘块号2对应的物理盘块号为32，所以需要访问32这个磁盘块。 8．文件存储空间有哪些管理方法？各适用于什么物理文件？Unix系统采用哪种方法？ 参考答案：目前常用的磁盘空间的管理方法有空闲表法、空闲块链表法、位示图法和成组链接法。其中空闲表法适用于连续文件，空闲块链表法、位示图法和成组链接法可适用于链接文件、索引文件。Unix系统采用成组链接法。

9．有一磁盘组共有10个盘面，每个盘面上有120个磁道，每个磁道有20个扇区。假定分配以2KB为单位，若使用位示图管理磁盘空间，则位示图需要占用多少空间？

参考答案：

盘块数 = 磁盘组的总空间大小/ (字节数/盘块)

= (盘面数 × 磁道数/盘面 × 扇区数/磁道 × 字节数/扇区) / (字节数/盘块)

= 10 × 120 × 20 × 512 / (2 × 1024) = 6000

所以位示图共占用6000bit（750B）。 10．比较目前常用的几种文件共享方式。你认为哪种文件共享方式同时适合本地文件共享和远程文件共享？

参考答案：目前常用的文件共享的方法有基于索引节点的共享方式和利用符号链实现文件共享。采用基于索引节点的共享方式，只有链接计数等于1时，文件主才能删除文件。而利用符号链实现文件共享就解决了这个问题，利用符号链实现文件共享，只有文件主才拥有指向索引节点的指针，而共享该文件的其他用户，只有该文件的路径名，没有指向其索引节点的指针，这样，当文件主删除一共享文件后，所有共享该文件的用户目录项中不会留下悬空指针。利用符号链实现文件共享同时适合本地文件共享和远程文件共享

11．有哪些文件保护方法？各有何优缺点？

参考答案：通常有口令保护、加密保护、为文件设置使用权限等方法。口令保护是实现文件保护的一种简单方法，缺点是对文件不能控制存取权限，所有知道口令的用户都具有与文件主相同的存取权限。加密保护适用于数量较少的比较重要的文件的保护，但会增加系统开销，降低文件读写速度，知道密码的用户都具有与文件主相同的存取权限。为文件设置使用权限，可对不同用户设置不同的文件使用权限，使文件的保护级别更灵活。

本文来源：https://www.bwwdw.com/article/qheo.html