第一章

1. 设计现代OS的主要目标是什么？

（1）方便性使得计算机更易于使用

（2）有效性提高资源利用效率，使系统的吞吐量更大

（3）可扩充性方便增加新的功能和模块，以适应计算机硬件、体系结构和应用发展的要求

（4）开放性遵循世界标准规范，使得系统之间能彼此兼容方便互联

2. OS的作用可以表现在哪几个方面？

（1）操作系统是用户与计算机硬件系统之间的接口

（2）操作系统是计算机资源的管理者

（3）操作系统实现了对计算机资源的抽象

还是计算机工作流程的组织者，负责在众多作业之间切换处理机并且协调他们的推进速度，从而进一步提高系统的性能。

3. 为什么说操作系统实现了对计算机资源的抽象？

对于一台完全没有软件的计算机系统来说，它给用户提供的只是硬件接口，所以为了方便用户使用I/O设备，人们在裸机上覆盖了一层I/O设备管理软件，用它来对I/O设备进行操作，并向上将I/O设备抽象为一组数据结构以及一组操作命令，然后用户就可以通过这些数据结构和操作命令来实现数据的输入输出和其他操作，而并不用关心I/O设备具体是怎么实现的。

换言之，在裸机上铺设的I/O软件隐藏了I/O设备的具体细节，向上提供了一组抽象的I/O设备。

4. 推动多道批处理系统形成和发展的主要动力是什么？

（1）不断提高计算机资源利用率

（2）方便用户

（3）器件的不断更新换代

（4）计算机体系结构的不断发展

（5）不断提出新的应用需求

5. 什么是脱机I/O和联机I/O？

脱机I/O就是事先将装有用户程序和数据的纸袋装入纸袋输入机，在一台外围机的控制下，把纸袋上的数据出入到磁盘，当CPU需要这些程序和数据时，再从磁带上高速地调入内存。程序的输入和输出都是在外围机的控制下完成，或者说都是在脱离主机的情况下完成。

反之在主机的直接控制下进行输入/输出的方式称为联机输入/输出模式。

6. 说明推动分时系统形成和发展的动力

推动分时系统形成和发展的主要动力，是为了满足用户对人-机交互的需求，由此形成一种新型OS。用户的需求表现在①人-机交互 ②共享主机

7. 实现分时系统的关键问题是什么？如何解决？

（1）及时接收多个用户键入的命令或数据

解决：在系统中配置一个多路卡，实现分时多路复用。主机以很快的速度周期性地扫描各个终端，在每个终端停留很短的时间。为了从终端上输入的数据被依次逐条处理，还要为每个终端配置一个缓冲区，暂存用户键入的命令。

（2）及时处理对用户输入的指令及时地实施控制或者修改。

解决：①作业直接进入内存②采用轮转运行方式

8. 为什么要引入实时操作系统？

如果嵌入式系统的功能比较复杂，需要网络功能、存储器管理、进程/线程管理等，则通过嵌入式操作系统的帮助，可加快嵌入式系统软件的开发进度和可靠性。

实时操作系统是指系统能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。

9. 什么是硬实时任务和软实时任务？举例说明

硬实时任务是指系统必须满足任务对截止时间的要求，否则出现难于预测的后果。比如导弹发射

软实时任务也与时间有关联，但是并不严格，偶尔错过了任务的截止时间，对系统产生的影响也不会很大。例如12306没有实时更新座位信息。

10. 从多路性、独立性、及时性、交互性、以及可靠性方面将分时系统与实时系统进行比较

（1）多路性都表现为系统按分时原则为多个终端用户服务。实时系统则是系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制。

（2）独立性每个终端用户在于系统交互时，彼此相互独立互不干涉，在实时系统中对信息的采集和对对象的控制也是彼此互不干扰。

（3）及时性实时系统的实时性是控制对象所要求的截至时间来确定，一般为秒级到毫秒级。

（4）交互性分时系统中人与系统的交互性仅限于访问系统中某些特定的专用服务程序。而实时系统能向终端用户提供数据处理、资源共享等服务。

（5）可靠性分时系统要求系统可靠，实时系统要求系统高度可靠。实时系统中往往采取多级容错措施来保障系统的安全性和数据的安全性。

11. OS有哪几大特征？最基本的特征是什么？

（1）并发并发性是指两个或多个事件在同一时间间隔内发生。一段时间内宏观上有多个程序在同时运行，但在单处理机系统中每一时刻仅有一个能执行，微观上是分时交替执行。（并行性是指两个或多个事件在同一时刻发生）

（2）共享系统中的资源可以供内存中多个并发执行的进程共同使用

（3）虚拟通过某种技术把一个物理实体变为若干个逻辑上的对应物的功能

（4）异步多道程序环境下，程序允许多个进程并发执行。在单处理环境下，由于系统只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。非“一气呵成”而是“走走停停”。

12. 多道程序技术的OS环境下的资源共享与一般情况下的资源共享有何不同？对独占资源应该采取何种共享方式？

一般情况下的共享说明某种资源能被大家所使用，通过适当安排，用户之间不会产生对资源的竞争，此情况下资源管理相对简单。

而OS环境下的资源共享指系统中的资源可供内存多个并发执行的进程共同使用。宏观上限定了时间也限定了地点。

采用互斥共享方式而非同时访问方式。

13. 什么是时分复用技术？举例能提高资源利用率的根本原因是什么？

计算机领域内广泛利用时分复用技术来实现虚拟处理机、虚拟设备等，使资源的利用率得以提高。

根本原因在于它利用某设备为一用户服务的空闲时间又转去为其他用户服务，从而使设备得到最充分的利用。（渣男技术）

举例：虚拟处理机技术：利用多道程设计技术，为每道程序建立至少一个进程，让多道程序并发执行。

14. 什么原因使操作系统具有异步性特征？

单处理机模式下，系统中只有一台处理机，每次只允许一个进程执行，其余进程只能等待。

对于内存中的每个进程，在何时能获得处理机运行，何时又因提出某种资源请求而暂停，以及资源以怎样的速度推进，每道程序需要多少时间才能完成都是不可预知的。或者说进程是以人们不可预知的速度向前推进的此即进程的异步性。

15. 处理机管理有哪些主要功能？主要任务是什么？

处理机管理的主要功能有:创建和撤消进程,对诸进程的运行进行协调,实现进程之间的信息交换,以及按照一定的算法把处理机分配给进程。

（1）进程控制为作业创建进程、撤销已结束的进程以及控制进程在运行过程中的状态转换。

（2）进程同步为多个进程的运行进行协调（进程互斥方式和进程同步方式）

（3）进程通信实现相互合作进程之间的信息交换

（4）调度

①作业调度从后备队列中按照一定的算法选择出若干个作业为他们分配运行所需的资源，调入内存后分别为他们建立进程

②进程调度从进程的就绪队列中按照一定的算法选出一个进程，将处理机分配给他并设置运行现场，使其投入执行。

16. 内存管理有哪些主要功能？其主要任务是什么？

存储器管理的主要任务,是为多道程序的运行提供良好的环境,提高存储器的利用率, 方便用户使用,并能从逻辑上扩充内存。

（1）内存分配（静态分配和动态分配方式）

①为每道程序分配运行空间，“各得其所”

②提高存储器的利用率

③允许正在进行的程序申请附加内存空间以适应数据动态增长的需要

（2）内存保护

①确保每道用户程序都仅在自己的内存空间内运行，互不干扰

②决不允许用户程序访问操作系统的程序和数据，也不允许用户程序转移到非共享的其他用户程序中去执行。

（3）地址映射将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。

（4）内存扩充借助虚拟存储技术从逻辑上扩充内存数量。

①请求调入功能 ②置换功能

17. 设备管理有哪些主要功能？其主要任务是什么？

设备管理的主要任务如下: (1)完成用户进程提出的I/O请求,为用户进程分配所需的I/O 设备,并完成指定的I/O 操作, (2)提高CPU和IO设备的利用率,提高I/O速度,方便用户使用I/O设备。为实现上述任务,设备管理应具有缓冲管理、设备分配和设备处理以及虚拟设备等功能。

（1）缓冲管理缓和CPU和I/O设备速度不匹配的矛盾，提高CPU利用率，提高系统吞吐量。

（2）设备分配根据用户进程的I/O请求，系统现有资源情况以及按照某种设备分配策略，为之分配所需的设备。

（3）设备处理实现CPU和设备控制器之间的通信。

18. 文件管理有哪些主要功能？其主要任务是什么？

对用户文件和系统文件进行管理以方便用户使用,并保证文件的安全性。

（1）文件存储空间的管理为每个文件分配必要的外存空间，提高外存的利用率，进而提高文件系统的存、取速度。

（2）目录管理为每个文件建立目录项

（3）文件的读/写管理和保护

19. 推动传统OS演变为现代OS的主要因素是什么？

（1）系统安全（2）网络的功能和服务（3）支持多媒体

20. 什么是微内核OS？

微内核OS即现代结构的OS

（1）足够小的内核

（2）基于客户/服务器模式

（3）应用“机制与策略分离”原理

（4）采用面向对象技术

21. 微内核操作系统具有哪些优点？为何能有这些优点？

微内核OS是建立在模块化、层次化的基础上的，采用了客户/服务器模式和面向对象的程序设计技术。

（1）提高了系统的可扩展性.

（2）增强了系统的可靠性

（3）可移植性强

（4）提供了对分布式系统的支持

（5）融入了面向对象技术

22. 现代操作系统较之传统操作系统又增加了哪些功能和特征？

（1）进程管理（2）低级存储器管理（3）中断和陷入管理

23. 在微内核OS中，为什么要采用客户/服务器模式？

具有传统集中模式无法比拟的优点

（1）数据的分布处理和存储

（2）便于集中管理

（3）灵活性和可扩充性

（4）易于改编应用软件

24. 基于微内核结构的OS中，应用了哪些新技术？

面向对象的程序设计技术

25. 何为微内核技术？在微内核技术中通常提供了哪些功能？

把操作系统中更多的成分和功能放到更高的层次去运行，而留下一个尽量小的内核，用它来完成操作系统中最基本的核心功能。

进程管理；低级存储器管理；中断和陷入管理等功能

第二章

1. 什么是前趋图？为什么要引入前趋图？

为了更好的描述程序的顺序和并发执行情况，引入用于描述程序执行先后顺序的前趋图。

前趋图是指一个有向无环图，可记为DAG，用于描述进程之间执行的先后顺序。图中的每一根结点可以用来表示一个进程或者程序段，乃至一条语句，节点间的有向边则表示两个结点之间存在的偏序4或者前趋关系。

2. 画出下面四条语句的前趋图：

S1: a=x+y;

S2: b=z+1;

S3: c=a-b;

S4: w=c+1;

3. 为什么程序并发执行会产生间断性特征？

引入了程序间的并发执行功能之后，虽然提高了系统的吞吐量和资源利用率，但是由于他们共享系统资源，以及他们为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。相互制约将导致并发程序具有“执行-暂停-制约”这种间断性的活动规律。

4. 程序并发执行时为什么会失去封闭性和可再现性？

当系统中存在多个可以并发执行的程序时，系统中的各种资源将为他们所共享，而这些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其他程序必须等待，显然程序的运行失去了封闭性。

程序在并发执行时，由于失去了封闭性，计算结果必将与并发程序的执行速度有关，从而使程序的执行失去了可再现性，换言之，程序经过多次执行后，虽然执行的环境和初始条件相同，但得到的结果却各不相同。

5. 在操作系统中为什么要引入进程的概念？会产生什么样的影响？

通常的程序不能参与并发执行，否则程序的运行就失去了意义，为了使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。

影响：使得程序能够并发执行并可以对并发执行的程序加以描述和控制

6. 试从动态性、并发性和独立性上比较进程和程序

进程具有程序没有的PCB结构

动态性：进程的实质是进程实体的执行过程，是进程的最基本的特征。进程实体有一定的生命期，而程序则是一组有序指令的集合，并存放于某种介质上，本身不具有活动的意义，因而是静态的。

并发性：多个进程实体共存于内存中且能在一段时间内同时运行。而程序时不能参与并发执行的。

独立性：独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。

7. 试说明PCB的作用具体表现在哪几个方面，为什么说PCB是进程存在的唯一标志？

PCB-进程控制块：为使参与并发执行的每个程序能独立的运行，在操作系统中必须为之配备一个专门的数据结构，称为进程控制块。系统利用PCB来描述进程的基本情况和活动情况，进而控制和管理进程。

PCB的作用是使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的过程。

（1）作为独立运行基本单位的标志

（2）能实现间断性运行方式

（3）提供进程管理所需要的信息

（4）提供进程调度所需要的信息

（5）实现与其他进程的同步与通信

系统创建一个新进程时，为他建立了一个PCB，进程结束时又收回PC版，进程随之消亡。系统是通过PCB感知进程的存在与否。

8. PCB提供了进程管理和进程调度所需要的哪些信息？

进程管理：当调度程序调度到某进程运行时，PCB中记录的程序和数据在内存或外存中的初始指针，找到相应的程序和数据；在进程运行过程中，当需要访问文件系统中的文件或I/O设备时，也需要借助于OCB中的信息。还可以根据PCB中的资源清单了解到该进程所需的全部资源。

进程调度：PCB提供了进程处于何种状态的信息。只有处于就绪状态才会被调度执行。

9. 进程控制块的组织方式有哪几种？

（1）线性方式将系统中的所有的PCB都组织在一张线性表中

（2）链接方式把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。系统根据所有进程状态的不同，建立几张索引表。

（3）索引方式系统根据所有进程状态的不同，建立几张索引表

10. 何为操作系统内核？内核的主要功能是什么？

将一些与硬件紧密相关的模块，各种常用设备的驱动程序以及运行频率最高的模块，安排在紧靠硬件的软件层次中，将他们常驻内存，通常被称为OS内核。

主要功能：①支撑功能 ②资源管理功能

11. 试说明进程在三个基本状态之间转换的典型原因

处于就绪态的进程，在调度程序为之分配了处理机之后便可执行，相应的其状态就由就绪态转变为执行态；

正在执行的进程如果因为分配给他的时间片已完而被剥夺处理机暂停执行时，其状态就由执行转为就绪；

如果因发生某事件，致使当前进程的执行受阻使之无法继续执行，则该进程状态由执行变为阻塞。

12. 为什么要引入挂起状态？该状态有哪些性质？

引入挂起操作的原因，是基于系统和用户的需要：

（1）终端用户的需要

（2）父进程请求

（3）负荷调解的需要

（4）操作系统的需要

性质：此时此进程处于静止状态，暂不被处理机调度。

13. 在进行进程切换时，所要保存的处理机状态信息有哪些？

（1）通用寄存器

（2）指令计数器

（3）程序状态字PSW

（4）用户栈指针

14. 试说明引起进程创建的主要事件

（1）用户登录

（2）作业调度

（3）提供服务

（4）应用请求

15. 试说明引起进程被撤销的主要事件

（1）正常结束，表示进程的任务已经完成，准备退出运行。

（2）异常结束，进程在运行时发生了某种异常实践，使程序无法继续运行。

（3）外界干预，进程应外界请求而终止运行。

16. 在创建一个进程时所要完成的主要工作是什么？

（1）申请空白PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。

（2）为新进程分配其运行所需的资源，包括各种物理和逻辑资源。

（3）初始化进程控制块（PCB）。

（4）如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

17. 在撤销一个进程时所要完成的主要工作是什么？

（1）根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。

（2）若被终止进程正处于执行状态，应该立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应该重新调度。

（3）若该进程还有子孙进程，还应将所有子孙进程予以终止，以防他们成为不可控的进程。

（4）将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统。

（5）将被终止进程从所在队列中移出，等待其他程序来收集信息。

18. 试说明引起进程阻塞或被唤醒的主要事件是什么？

（1）向系统请求共享资源失败

（2）等待某种操作的完成

（3）新数据尚未到达

（4）等待新任务的到达

19. 为什么要在OS中引入线程？

进入进程的目的是为了使多个程序能够并发执行，以提高资源利用率和系统吞吐量。

进入线程的目的是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

20. 试说明线程具有哪些属性？

扩展：进程的两个属性：

（1）进程是一个可拥有资源的独立单位

（2）进程同时又是一个可独立调度和分派的基本单位

线程的属性：作为调度和分派的基本单位，能独立运行的基本单位、轻型实体、可以并发执行、可共享所属进程的资源

21. 试从调度性、并发性、拥有资源及系统开销方面对进程和线程比较

调度性：传统的OS中，进程是作为独立调度和分派的基本单位，因而进程是能独立运行的基本单位。而在引入线程的OS中，把线程作为调度和分派的基本单位，因而线程使能独立运行的基本单位。

并发性：引入线程的OS中，不仅进程之间可以并发执行，在一个进程中的多个线程之间也可以并发执行，还允许在一个进程中的所有的线程都能够并发执行，同样，不同进程中的线程也能并发执行。使得OS有很好的并发性，从而更加有效提高系统资源的利用率和系统的吞吐量。

拥有资源：进程可以拥有资源，作为系统中拥有资源的一个基本单位，然而线程本身不拥有系统资源，而是仅有一点必不可少、能保证独立运行的资源。线程除了拥有自己少量的资源外，还允许多个线程共享该进程所拥有的资源。

独立性：统一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。

系统开销：创建或者撤销进程时，系统都要位置分配和回首进程控制块、分配或回首其他资源。OS位置付出的开销明显大于线程创建或撤销时付出的开销。

22. 线程控制块TCB中包含了哪些内容？

（1）线程控制符

（2）一组寄存器

（3）线程运行状态

（4）优先级

（5）线程专有存储区

（6）信号屏蔽

（7）堆栈指针

23. 何谓用户级线程和内核支持线程？

用户级线程：用户级线程实在用户空间内实现的。对线程的创建、撤销、同步与通信等功能都无需内核的支持，即用户级线程与内核无关，内核不知道用户级线程的存在。

内核支持线程：无论是系统进程还是用户进程，都是在操作系统内核的支持下运行的，与内核紧密相关，内核支持线程的创建、阻塞、撤销和切换也都是在内核空间实现的。

24. 试说明用户级线程的实现方法

用户级线程实在用户空间实现的，所有的用户级线程都具有相同的结构，都运行在一个中间系统上，即运行时系统和内核控制线程。

25. 试说明内核支持线程的实现方法

系统在创建一个新进程时，便为它分配一个任务数据区PTDA，其中包括若干个线程控制块TCB空间，每当进程要创建一个线程时，便为新线程分配一个TCB，将有关信息填入该TCB中，并为之分配必要的资源。

当PTDA中所有的TCB空间用完之后，而进程又要创建新的线程，只要其创建的线程数目未超过系统的允许值，系统可以为之再分配新的TCB空间；在撤销一个线程时，也应回收该线程的所有资源和TCB。

26. 多线程模型有哪几种类型？多对一模型有何优缺点？

一对一、多对一、多对多

多对一模型：即将用户线程映射到一个内核控制线程。

优点是线程管理的开销小，效率高；

缺点是如果一个线程在访问内核时发生阻塞，整个进程就会被堵塞，此外在任一时刻只有一个线程能够访问内核，多个线程不能同时在多个处理机上运行。

第三章

1. 高级调度与低级调度的主要任务是什么？为什么要引入中级调度？

高级调度的调度对象是作业。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为他们创建进程、分配必要的资源并把他们放入就绪队列。（外存—>内存）

低级调度又称为进程调度，调度的对象是进程或内核级线程，主要功能是根据某种算法决定就绪队列中的哪个进程获得处理机，由分派程序将处理机分配给被选中的进程，是最基本的一种调度。（进程和处理机的调度）

中级调度又称为内存调度，引入中级调度的目的就是提高内存利用率和系统吞吐量。把那些暂时不能运行的进程调至外存等待。已具备运行条件且内存又稍有空闲时由中级调度决定把外存上那些已具备运行条件的就绪进程再重新调入内存。（外存和内存的相互调度）

2. 处理机调度算法的共同目标是什么？批处理系统的调度目标又是什么？

处理机调度算法的共同目标：

（1）资源利用率

（2）公平性诸进程都获得合理的CPU时间，不会发生进程饥饿现象

（3）平衡性保持系统资源使用的平衡性

（4）策略强制执行只要需要，就予以准确执行

批处理系统的调度目标：

（1）平均周转时间短

（2）系统吞吐量高

（3）处理机利用率高

分时系统的目标：①响应时间快②均衡性

实时系统的目标：①截止时间的保证②可预测性

3. 何谓作业、作业步和作业流？

作业：是一个比程序更为广泛的概念，不仅包含了通常的程序和数据，还配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。批处理系统中，是以作业为基本单位从外存调入内存的。

作业步：作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得出结果，每一个加工步骤成为一个作业步。

作业流：在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。

4. 在什么情况下需要使用作业控制块JCB,其中包含了哪些内容？

为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块JCB，保存了系统对作业进行管理和调度所需的全部信息。

通常JCB中包含的内容有：作业标识、阳湖名城、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等

一个作业进入系统时,便由"作业注册"程序为该作业建立一个作业控制块JCB。再根据作业类型,将它放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度它们,被调度到的作业将被装入内存。在作业运行期间,系统就按照JCB中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态时,系统负责回收已分配给它的资源,撤销该作业控制块。

5. 作业调度中应如何确定接纳多少个作业和接纳哪些作业？

（1）接纳多少个作业

每一次进行作业调度时，应当从后备队列中选取多少作业调入内存，取决于多到程序度，即允许多少个作业同时在内存中运行。

多道程序度的确定是根据计算机的系统规模、运行速度、作业大小、以及能否获得较好的系统性能等情况做出适当的抉择的。

（2）接纳那些作业

取决于所采用的调度算法。最常用的是先来先调度算法，另一种是基于作业基于优先级的调度算法。

6. 什么要引入高响应比优先调度算法？它有何优点？

先来先服务调度算法系统按照作业到达的先后次序来进行调度；

短作业优先调度算法是以作业长短来计算优先级，作业越短优先级越高；

优先级调度算法基于作业的紧迫程度根据优先级进行调度；

批处理系统中,FCFS 算法所考虑的只是作业的等待时间,而忽视了作业的运行时间。而SJF 算法正好与之相反,只考虑作业的运行时间,而忽视了作业的等待时间。

高响应比优先调度算法既考虑了作业的等待时间，又考虑了作业运行时间的调度算法，既照顾了短作业又不致使长作业的等待时间过长，从而改善了处理机调度的性能。

实现：为每个作业引入一个动态优先级，随着时间延长而增加，将使长作业的优先级在等待期间不断增加，等到足够的时间后，必然有机会获得处理机。

7. 试说明低级调度的主要功能。

根据某种算法，决定就绪队列中的哪个进程获得处理机，并由分派程序将处理机分配给选中的进程。

保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程

8. 在抢占调度方式中,抢占的原则是什么？

（1）优先权原则

（2）短进程优先原则

（3）时间片原则

9. 在选择调度方式和调度算法时,应遵循的准则是什么？

（1）面向用户的准则：周转时间短、响应时间快、截止时间的保证、优先权准则

（2）面向系统的准则：系统吞吐量高、处理机利用率好、各类资源的平衡利用

10. 在批处理系统、分时系统和实时系统中,各采用哪几种进程(作业)调度算法？

批处理系统：短作业优先、优先权、高响应比优先、多级反馈队列调度算法

分时系统中最简单最常用的是基于时间片的轮转调度算法，让就绪队列上的每个进程每次仅运行一个时间片。

实时系统：最早截止时间优先（EDF）、最低松弛度优先算法（LIF）

11. 何谓静态和动态优先级?确定静态优先级的依据是什么？

优先级调度算法是把处理机分配给就绪队列中优先级最高的进程。优先级调度算法的关键在于，应如何确定进程的优先级，以及确定是使用静态优先级还是动态优先级。

静态优先级是在创建进程时确定的在进程的整个运行期间保持不变。

动态优先级是指在创建进程之初先赋予一个优先级，然后其值随着进程的推进或等待时间的增加而改变，以便获得更好的调度性能。

确定静态优先级的依据：

（1）进程类型（2）进程对资源的需求（3）用户要求

12. 试比较FCFS和SJF 两种进程调度算法。

先来先服务调度算法FCFS，既可以用于作业调度，也可以用于进程调度。作业调度采用该算法时，系统按照作业到达的先后顺序来进行调度，优先考虑在系统中等待时间最长的作业。当进程调度采用该算法时，每次调度从就绪的进程队列中选择一个最先进入该队列的进程为之分配处理机投入运行。

短作业优先SJF，是以作业的长短来计算优先级，作业越短，优先级越高。作业的长短是以作业所要求的运行时间来衡量的。用于作业调度时将外存的作业后备队列中选择若干个估计运行时间最短的作业调入内存运行。

相比于FCFS，SJF有不容忽视的缺点：

（1）必须预知作业的运行时间

（2）对长作业运行不利，周转时间会明显增长

（3）采用FCFS算法时，人机无法实现交互

（4）未考虑作业的紧迫程度，不能保证紧迫性作业得到及时处理

13. 在时间片轮转法中,应如何确定时间片的大小？

常用于分时系统中的基于时间片的轮转调度算法。

时间片小，意味着会频繁地执行进程调度和进程上下文的切换，无疑会增加系统的开销。时间片太长，为使得每个进程都能在一个时间片内完成，轮转调度算法RR会退化成FCFS算法，无法满足短作业和交互式用户的需求。

一个较为可取的时间片大小是略大于一个典型的交互所需要的世界，使得大多数交互式进程能够在一个时间片内完成，从而可以获得很小的响应时间。

14. 通过一个例子来说明通常的优先级调度算法为什么不能适用于实时系统？

优先级调度算法是把处理机分配给就绪队列中优先级最高的进程。实时系统的调度算法很多，主要是基于任务的开始截止时间和任务松弛程度的任务优先级调度算法，通常的优先级调度算法不能满足实时系统的调度实用性要求而不适用。

15. 为什么说多级反馈队列调度算法能较好地满足各方面用户的需要？

多级反馈队列调度算法不必事先知道各种进程所需的执行时间，还可以较好地满足各种进程的需要。如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好的满足各种类型用户的需要。

终端型用户。此用户提交的作业多属于交互性作业，通常较小，系统只要能在第一队列规定的时间片内完成，便可使得用户满意。

短批处理用户。如果能在第一队列中执行完成，便获得与终端型作业一样的响应时间，对于稍长的短作业，也只需在第二和第三队列各执行一时间片完成，周转时间仍然很短。

长批处理作业用户。对于长作业，一次在第1,2，…n个队列中运行，然后再轮转方式运行，用户不必担心作业长期得不到处理。

16. 为什么说传统的几种调度算法都不能算是公平调度算法？

传统的几种调度算法所保证的只是优先运行，如果优先级算法是优先级最高的作业优先运行，但并不保证作业占用了多少的处理机时间，也没有考虑到调度的公平性。

17. 保证调度算法是如何做到调度的公平性的？

它向用户保证的不是优先运行，而是明确的性能保证，可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有n个相同类型的进程同时运行，公平起见须保证每个进程都获得相同的处理机时间1/n。

18. 公平分享调度算法又是如何做到调度的公平性的？

在该调度算法中，调度的公平性主要是针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例。调度又是以进程为基本单位，必须考虑到每一个用户所拥有的进程数目。

19. 为什么在实时系统中,要求系统(尤其是CPU)具有较强的处理能力？

在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过来，而致使某些实时任务不能得到及时处理，从而导致难以预料的后果。

20. 按调度方式可将实时调度算法分为哪几种？

（1）根据实时任务性质分为①硬实时调度算法②软实时调度算法

（2）根据调度方式分为①非抢占调度算法②抢占调度算法

21. 什么是最早截止时间优先调度算法？举例说明之。

根据任务的截止时间确定任务的优先级，任务的截止时间越早，优先级越高，且具有最早截止时间的任务排在队列的对首。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机。最早截止时间优先算法既可用于抢占式调度方式中，也可用于非抢占式调度方式中。

22. 什么是最低松弛度优先调度算法？举例说明之。

该算法在确定任务的优先级时，根据的是任务的紧急（或松弛）程度。任务紧急程度越高，赋予该任务的优先级就越高，以使之优先执行。例如，一个任务在200ms 时必须完成,，而它本身所需的运行时间是100ms，因此调度程序必须在100ms 之前调度执行，该任务的紧急程度（松弛程度)为100ms。又如另一任务在400ms 时必须完成,它本身需要运行 150ms,则其松弛程度为250ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在最前面，调度程序选择队列中的对首任务执行。

23. 何谓"优先级倒置"现象,可采取什么方法来解决？

当前OS广泛采用优先级调度算法和抢占方式，然后在系统中存在着影响进程运行的资源而产生“优先级倒置”的现象，即高优先级进程被低优先级进程延迟或堵塞。

解决方法：

（1）进程进入临界区之后所占用的处理机就不允许被抢占。

（2）建立在动态优先级继承基础上，当优先级高的进程A被阻塞在资源X的临界区外时，已分配到资源X、优先级低的进程B自动继承A的高优先级，能尽早运行完毕，尽早释放资源X，使得A尽快有机会运行。

24. 试分别说明可重用资源和可消耗资源的性质。

可重用资源是一种可供用户重复多次使用多次的资源。

（1）每一个可重用资源中的单元只能分配给一个进程使用，不允许多个进程共享。

（2）进程在使用可重用资源时，按照①请求资源②使用资源③释放资源的顺序。

（3）系统中的每一类可重用资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除。

可消耗性资源又称为临时性资源，他是在进程运行期间，由进程动态地创建和消耗的。

（1）每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，可以有很多，有时可能为0；

（2）进程在运行过程中，可以不断地创造可消耗性资源的单元，将他们放入该资源类的缓冲区中，以增加该资源类的单元数目。

（3）进程在运行过程中，可以请求若干个可消耗性资源单元用于进程自己的消耗，不再将他们返回给该资源类中。

可消耗性资源通常是由生产者进程创建，由消费者进程消耗。

25. 试举例说明竞争不可抢占资源所引起的死锁。

不可抢占资源是把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放，例如当一个进程已经开始刻录光盘，如果突然将刻录机分配给另外一个进程，其结果必然是损坏正在刻录的光盘，因此只能等刻好光盘后由进程自己释放刻录机。另外磁带机、打印机等也都是属于不可抢占性资源。

26. 为了破坏"请求和保持"条件而提出了两种协议,试比较这两种协议

第一种协议：所有进程再开始运行之前，必须一次性的申请其在整个运行过程中所需要的全部资源。该进程在整个运行期间不会再提出资源要求，从而破坏了“请求”条件。优点是简单、易行且安全，缺点是资源背严重浪费，资源利用率低；使得进程通常会发生饥饿现象。

第二种协议：允许一个进程只获得运行初期所需要的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。优点是可以使进程更快的完成任务，提高设备的利用率，还能减少进程发生饥饿的几率。

27. 何谓死锁？产生死锁的原因和必要条件是什么？

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

死锁金晨中的每一个进程，都在等待另一个死锁进程所占有的资源。或者说每个进程所等待的事件是该组中其他进程释放所占有的资源。但由于所有这些进程都已无法运行，因此他们谁也不能释放资源，致使没有任何一个进程可以被唤醒。那么这组进程只能无限期等待下去。

必要条件：

（1）互斥条件进程对分配到的资源进程排他性使用

（2）请求和保持条件进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有。

（3）不可抢占条件进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。

（4）循环等待条件发生死锁时，必然存在一个进程----资源的循环链。

28. 在解决死锁问题的几个方法中,哪种方法最易于实现？哪种方法使资源利用率最高？

（1）预防死锁最简单和直观的事先预防方法。通过设置某些限制条件，去破坏产生死锁四个必要条件的一个或几个来预防产生死锁，较易实现，广泛使用。

（2）避免死锁不是事先采取各种限制措施去破坏四个必要条件，而是在资源的动态分配过程中，用某种方法防治系统进入不安全状态，从而可以避免发生死锁。

（3）检测死锁通过检测机构及时检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。

（4）解除死锁检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤销一些进程，回首他们的资源，将他们分配给已处于阻塞状态的进程，使其能继续运行。资源利用率最高。

29. 请详细说明可通过哪些途径预防死锁。

预防死锁的方式是通过破坏死锁的四个必要条件中的一个或几个，以避免发生死锁。

（1）破坏“请求和保持”条件。系统必须做到当一个进程在请求资源时，他不能持有不可抢占资源。实现方式：①第一种协议 ②第二中协议（习题3-26）

（2）破坏“不可抢占”条件。当一个已经保持了某些不可被抢占资源的进程时，提出新的资源请求而不能得到满足时，必须释放已保持的所有资源，待以后需要时在重新申请。

（3）破坏“循环等待”条件。对系统所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按序号递增的顺序请求资源。

30. 在银行家算法的例子中,如果P发出的请求向量由Request(O,2,0)改为Request(O, 1,0),问系统可否将资源分配给它？

（1）request（0,1,0）<need（7,4,3）

（2）request（0,1,0）<available（2,3,0）

（3）系统暂时可以先假定可以为P0分配资源，并修改有关数据，如下图

（4）再利用安全性算法检查此时系统是否安全

由此，可以找到一个安全序列{1 3 4 0 2}，系统是安全的，可以将资源分配给他。

（这个题序列答案不唯一，1 3 0 2 4也可以，看过很多答案感觉都不太对，work应该与上一层的Work+Allocation一致，仅供参考）

31. 在银行家算法中，若出现下述资源分配情况，试问：

（1）该状态是否安全

（2）若进程P2提出请求Request（1,2,2，2）后，系统能否将资源分配给它？

（1）状态安全，因为存在着一个安全序列{P0，P3，P1，P4，P2}，故系统是安全的。（答案不唯一，P0，P3，P4，P1，P2也可以）

（2）系统不能将资源分配给他，若分配给进程P2，此时资源还剩（0，4，0，0）此时系统中的资源将不能满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。

第四章

1. 为什么要配置层次式存储器？

（1）设置多个存储器可以使存储器两端的硬件能并行工作。

（2）采用多级存储系统，特别是Cache技术，是一种减轻存储器带宽对系统性能影响的最佳结构方案。

（3）在微处理机内部设置个各种缓冲处理器，以减轻对存储器存取的压力。增加CPU中寄存器的数量，也可大大减缓对存储器的压力。

2. 可采用哪几种方式将程序装入内存？它们分别适用于何种场合？

（1）绝对装入方式用于计算机系统很小，仅能运行单道程序时，适用于单道程序环境，完全有可能知道程序将驻留在内存的什么位置。用户程序经编译后，将产生绝对地址的目标代码。绝对装入程序便可按照装入模块中的地址与实际内存地址完全相同，不需要对程序和数据的地址进行修改。

（2）可重定位装入方式。在多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处。可以根据内存的具体情况将装入模块装入到内存的适当位置。

（3）动态运行时的装入方式。在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换成物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。因为装入内存后的所有地址仍是逻辑地址。

3. 何谓静态链接？静态链接时需要解决两个什么问题？

在程序运行之前，先将各目标模块及他们所需的库函数链接成一个完整的装配模块，以后不再拆开。这种事先链接的方式称为静态链接方式。

（1）对相对地址进行修改。在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的。在链接成一个装入模块后，原模块B和C在装入模块的起始地址不再是0，而是L+M，所以此时需修改模块B和C的相对地址。

（2）变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址。

4. 何谓装入时动态链接？装入时动态链接方式有何优点？

指将用户源程序编译后得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部调用模块事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存。

（1）便于修改和更新。

（2）便于实现对目标模块的共享。OS很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。

5. 何谓运行时动态链接？运行时动态链接方式有何优点？

对某些模块的链接推迟到程序执行时才进行，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，将其链接到调用者模块上。凡在执行过程中未被用到的目标模块都不会被调入内存和被链接到装入模块上。

不仅能加快程序的装入过程，而且可节省大量的内存空间。

6. 在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链？

为了实现对空闲分区的分配和链接，在每个分区的起始地址部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的向前指针，在分区尾部则设置一向后指针。通过前、后向链接指针，可将所有空闲分区链接成一个双向链。

7. 为什么要引入动态重定位？如何实现？

动态运行时候装入的方式中，作业装入内存后的所有地址仍然都是相对（逻辑）地址，而将相对地址转换为绝对（逻辑）地址的工作被推迟到程序指令要真正执行时进行。程序在执行时真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。

8. 什么是基于顺序搜索的动态分区分配算法？它可分为哪几种？

为了实现动态分区分配，将系统中的空闲分区链接成一个链。所谓顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。基于顺序搜索的动态分区分配算法有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法。

9. 在采用首次适应算法回收内存时，可能出现哪几种情况？应怎样处理这些情况？

首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找出一个大小能满足要求的空闲分区为之，然后再按照作业的大小从该分区中划出一块内存空间，分配给请求者，余下的空闲分区扔留在空闲链中。

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区表中找到相应的插入点。

（1）回收区与插入点的前一个空闲分区F1相邻接。此时应将回收区与插入点的前一分区合并。

（2）回收分区与插入点的后一空闲分区F2相紧接。此时可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为二者之和。

（3）回收区同时与插入点前、后两个分区链接，此时将三个分区合并，使用F1的表项和首址，大小为三者之和。

（4）回收区既不与F1邻接，又不与F2邻接，这时为回收区单独建立一个新表项，填写回收区的首址和大小并根据其首址插入到空闲链中的适当位置。

10. 什么是基于索引搜索的动态分区分配算法？它可分为哪几种？

把空闲分区按照某种属性分类，把每一类都链接起来形成一个链表，建立一个表把每类链表的相关信息写进去以供索引，按照这个数据分配空闲分区的算法叫做基于索引搜索的分区算法。

（1）快速适应算法 （2）伙伴系统 （3）哈希算法

11.令 buddy(x)为大小为2的k次方、地址为x的块的伙伴系统地址，试写出buddy(x)的通用表达式。

12.分区存储管理中常用哪些分配策略？比较它们的优缺点。

（1）固定分区存储管理。基本思想是将内存划分为若干固定大小的分区，每个分区最多只能装入一个作业。当作业申请内存时系统按照一定的算法为其选择一个适当的分区并装入内存运行，由于分区是事先固定好的因而可容纳作业的大小受到限制而且当用户作业的地址空间小于分区的存储空间时造成存储空间浪费。

（2）可变分区存储管理。不是预先将内存划分分区，而是在作业装入内存时建立分区使分区大小正好与作业要求的存储空间相等。

这种处理方式使内存分配有较大的灵活性也提高了内存利用率，但是随着对内存不断地分配、释放操作会引起存储碎片的产生。

13.为什么要引入对换？对换可分为哪几种类型？

在多道程序环境下，一方面在内存中的某些进程由于某事件尚未发生而被阻塞运行，但是却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而无可运行之进程，迫使CPU停止下来等待的情况；另一方面有许多作业因内存空间不足一直驻留在外存上而不能进入内存运行使得系统吞吐量下降。为了解决这一问题，在系统中又增设了对换设施。所谓对换，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存，以腾出足够的内存空间再把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是改善内存利用率的有效措施，可以提高处理机的利用率和系统吞吐量。

（1）整体对换。处理机中级调度实际上就是存储器的对换功能，以整个进程为单位。

（2）页面（分段）对换。对换是以进程的一个“页面”或者“分段”为单位进行的。

14.对文件区管理的目标和对对换空间管理的目标有何不同？

在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区两部分。

（1）对文件区管理的主要目标。文件区占用磁盘空间的大部分用于存放各类文件，对文件区管理的主要目标是提高文件存储空间的利用率，然后才是提高对文件的访问速度。

（2）对对换空间管理的主要目标。对换空间只占用磁盘空间的小部分用于存放从内存换出的进程，由于进程在对换区中驻留的时间是短暂的，而兑换操作的频率却较高，故对对换空间管理的主要目标市提高进程换入和换出的速度，然后才是提高文件存储空间的利用率。

15.为实现对换，系统应具备哪几方面的功能？

对对换空间的管理、进程的换出、进程的换入

16.在以进程为单位进行对换时，每次是否都将整个进程换出？为什么？

对换进程在实现进程换出时，是将内存中的某些进程调出对换区，以便腾出内存空间。

在选择换出进程后，在对进程换出时，只能换出非共享的程序和数据段，而对于那些共享的程序和数据段，只要有进程需要他，就不能被换出。在进行换出时，应先申请对换空间，若申请成功就启动磁盘将该进程的程序和数据传输到磁盘的对换区上，若传送过程未出现失误便可回收该进程所占用的内存空间，并对该进程的进程控制块和内存分配表等数据结构做相应的修改。

17.基于离散分配时所用的基本单位不同，可将离散分配分为哪几种？

（1）分页存储管理方式

（2）分段存储管理方式

（3）段页式存储管理方式

18.什么是页面？什么是物理块？页面的大小应如何确定？

（1）页面。分页存储管理将进程的逻辑地址空间分成若干个页，并为各页加以编号，相应地也把内存的物理地址空间分成若干个块，同样加以编号。

（2）物理块。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。

（3）页面大小。在分页系统中若选择过小的页面大小，虽然可以减小内存碎片起到减少内存碎片总空间的作用，有利于内存利用率的提高，但另一方面会造成每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存。此外还会降低页面换进换出的效率，然而如果选择的页面过大，虽然可以减少页表的长度，提高页面换进换出的速度但会使页内碎片增大，因此页面的大小应该选择适中且页面大小应该是2的幂，通常为1KB-8KB。

19.什么是页表？页表的作用是什么？

在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程扔能够正常地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面印象表，简称页表。

在进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。在配置了页表后，进程执行时，通过查找页表即可找到每页在内存中的物理块号，页表的作用是实现从页号到物理块号的地址映射。

20.为实现分页存储管理，需要哪些硬件支持？

具有页表机制、地址变换机构的硬件支持

21.在分页系统中是如何实现地址变换的？

当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动的将有效地址分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行监视之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址超越了进程的地址空间，这一错误被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项的乘积相加变得到该表项在页表中的位置，于是可从中得到该页的物理块号将之装入物理地址寄存器中。于此同时再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中，便完成了从逻辑地址到物理地址的变换。

22.具有快表时是如何实现地址变换的？

在CPU给出有效地址后，由地址变换机构自动地将页号P送入告诉缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在块表中，于是可直接从块表中读出该页所对应的物理块号并送到物理地址寄存器中。如在块表中未找到对用的页表项则还需再访问内存中的页表找到后把从页表项中读出的物理块号送往地址寄存器。同时再将此页表项存入块表的一个寄存器单元中，亦即重新修改块表。如果联想寄存器已满则OS必须找到一个老的且已被认为是不再需要的页表项将它换出。

23.较详细地说明引入分段存储管理是为了满足用户哪几方面的需要。

（1）方便编程

（2）信息共享

（3）信息保护

（4）动态增长

（5）动态链接

24.在具有快表的段页式存储管理方式中，如何实现地址变换？

在段页式系统中为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL，进行地址变换时，首先利用段号S将它与段长TL进行比较。若S<TL，表示未越界，于是利用段表始址和断号求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再理由块号b和页内地址来构成物理地址。

25.为什么说分段系统比分页系统更易于实现信息的共享和保护？

在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分页系统中的“页”只是存放信息的物理单位，并无完整的逻辑意义。这样一个可被共享的过程往往可能需要占用数十个页面，这就为实现共享增加了困难。而段可以是信息的逻辑单位，因此可以为该被共享过程建立一个独立的段，就极大简化了共享的实现。

信息保护同样是以信息的逻辑单位为基础的，且经常是以一个过程、函数或文件为基本单位进行保护的。

分页系统的每个页面是分散存储的，为了实现信息共享和保护，页面直接需要一一对应，为此需要建立大量的页表项；而分段系统的每个段都是从0开始编址并采取一段连续的地址空间，在实现共享和保护时，只需要为共享和保护的程序设置一个段表项，将其中的基址与内存地址一一对应就能够实现。

26.分页和分段存储管理有何区别

两者都采用离散分配方式且都是通过地址映射机构来实现地址变换。

（1）页是信息的物理单位。采用分页存储管理方式是为了实现离散分配方式，以消减内存的外零头提高内存的利用率。分页仅仅是系统管理上的需要完全是系统的行为，对用户是不可见的。分段存储管理方式中的段则是信息的逻辑单位，通常包含的是一组意义相对完整的信息。分段的目的在于更好满足用户的需要。

（2）页的大小固定且由系统决定。在采用分页存储管理方式的系统中，在硬件结构上就把用户程序的逻辑地址划分为页号和页内地址两部分，也就是说直接由硬件实现的，因而在每个系统中只能有一种大小的页面。而段的长度却不固定决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

（3）分页的用户程序地址空间是一维的。分页完全是系统的行为，故在分页系统中用户程序的地址是属于单一的线性地址空间，程序员只需利用一个记忆符即可表示一个地址。而分段是用户的行为，故在分段系统中用户程序的地址空间是二维的，程序员在标识一个地址时，既需给出段名又需给出段内地址。

27.试全面比较连续分配和离散分配方式

连续分配是指一个用户程序分配一个连续的地址空间，包括单一连续分配方式和分区式分配方式，前者将内存分为系统区和用户区，系统区供操作系统使用，用户区供用户使用，是最简单的一种存储方式，但只能用于单用户单任务的操作系统中；分区式分配方式分为固定分区和动态分区，固定分区是最简单的多道程序的存储管理方式，由于每个分区的大小固定必然会造成存储空间的浪费；动态分区是根据进程的实际需要动态地为之分配连续的内存空间常用三种分配算法：①首次适应算法，容易留下许多难用的小空闲分区，加大查找开销②循环首次适应算法，该算法能使内存中的空闲分区分布均匀但是致使缺少大的空闲分区③最佳适应算法，也容易留下许多难以利用的小空闲区

离散分配方式基于将一个进程直接分散地分配到许多不相邻的分区中的思想，分为分页式存储管理、分段式存储管理和段页式存储管理；①分页式存储管理旨在提高内存利用率，满足系统管理的需要；②分段式存储管理旨在满足哟用户的需要在实现共享和保护方面优于分页式存储；③段页式存储则是将两者结合起来取长补短即具有分段系统便于实现、可共享易于保护，可动态链接等优点，又能像分页系统那样很好的解决外部碎片的问题，以及为各个分段可离散分配内存等问题，显然是一种比较有效的存储管理方式。

综上，连续分配方式和离散分配方式各有各自优点应根据实际情况加以改进和利用。

第五章

1.常规存储器管理方式具有哪两大特征？它对系统性能有何影响？

（1）一次性。是指作业必须一次性的全部装入内存后方能开始执行。在传统存储器管理方式中要求先将作业全部装入内存后方能运行。导致大作业无法在小内存中运行以及无法进一步提高系统的多道程序度，直接限制了对处理机的利用率和系统的吞吐量的提高。

（2）驻留性。作业背装入内存后整个作业都一直驻留在内存中，其中任何部分都不会被换出，直至作业运行结束。导致占用宝贵的内存资源。

上述的一次性以及驻留性特征使得许多在程序运行时不用或暂时不用的程序占据了大量的内存空间，而一些需要运行的作业又无法装入运行，这是在浪费宝贵的内存资源。

2.什么是程序运行时的时间局限性和空间局限性？

程序运行时存在的局部性现象，即程序在执行过程中将呈现出局部性规律，在较短的时间内程序的执行仅局限于某个部分，相应的他所访问的存储空间也局限于某个区域。

（1）时间局限性。如果程序中的某条指令为执行，则不久后该指令可能再次执行；如果某数据被访问过，不就后该数据可能再次被访问，产生时间局限性的典型原因是在程序中存在着大量的循环操作。

（2）空间局限性。一旦程序访问了某个存储单元，在不就之后附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

3.虚拟存储器有哪些特征？其中最本质的特征是什么？

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度。

（1）多次性。多次性是相对于传统存储器管理方式的一次性而言的，是指一个作业中的程序和数据无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可。

（2）对换性。对换性是指相对于传统存储器管理方式的常驻性而言，是指一个作业中的程序和数据无需在作业运行时一直常驻内存，而是允许在作业的运行过程中进行换进、换出，待以后需要时再讲他们从外存调入内存。

（3）虚拟性。虚拟性是指能从逻辑上扩充内存容量，使用户所看到的的内存容量远大于实际内存容量。虚拟性是以多次性和对换性为基础的。

4.实现虚拟存储器需要哪些硬件支持？

（1）分页请求系统：

①请求分页的页表机制 ②缺页中断机构 ③地址变换机构

（2）请求分段系统：

①请求分段的段表机制 ②缺页中断机构 ③地址变换机构

5.实现虚拟存储器需要哪几个关键技术？

（1）在分页请求系统中是在分页的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。允许只装入少数页面的程序及数据，便启动运行。

（2）在请求分段系统中是在分段系统的基础上增加了请求调段及分段置换功能后形成的段氏虚拟存储系统。允许只装入少数段而非所有段的用户程序和数据，即可启动运行。

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

（1）状态位P：由于在请求分页系统中，只将应用程序的一部分调入内存，还有一部分仍在外存磁盘上，故需在页表中增加一个存在位字段。用于指示该页是否已调入内存，供程序访问时参考。

（2）访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，提供给置换算法在选择换出页面时参考。

（3）修改位M：标识该页在调入内存后是否被修改过。M位供置换页面时参考。

（4）外存地址：用于指出该页在外存上的地址，通常是物理块号供调入该页时参考。

7.试比较缺页中断机构与一般的中断，它们之间有何明显的区别？

在请求分页系统中，每当要访问的页面不在内存时，便产生缺页中断，请求OS将所缺之页调入内存。

（1）在指令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后才检查是否有中断请求到达。若有便去响应否则继续执行下一条指令。然鹅缺页中断实在指令执行期间若要发现所要访问的指令或数据不在内存时，便立即产生和处理缺页中断信号，以便能及时将所缺之页面调入内存。

（2）一条指令在执行期间可能产生多次缺页中断，基于此系统中硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。

8.试说明请求分页系统中的地址变换过程。

在进行地址变换时，首先检索快表，试图从中找到所要访问的页，若找到便修改页表项中的访问位，供置换算法选换出页面时参考，对于写指令还需将修改位置成“1”，表示该页在调入内存后已被修改。然后利用页表项给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。

如果在块表中未找到该页的页表项，则应到内存中去查找页表，再从找到的页表项中的状态位P来了解该页是否已调入内存。若以调入内存，这时应该将该页的页表项写入块表。块表已满时，则应先调出按照某种算法所确定的页的页表项，然后再写入该页的页表项；若该页尚未调入内存应产生缺页中断，请求OS从外存把该页调入内存。

9.何谓固定分配局部置换和可变分配全局置换的内存分配策略？

所谓固定分配，是指为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。所谓局部变换是指如果进程在运行中发现缺页，则只能从分配给该进程的n个页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。

可变分配全部置换。所谓可变分配，是指先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。所谓全局置换，是指如果进程在运行中发现缺页，则将OS所保留的空闲物理块取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入。

10.在请求分页系统中，应从何处将所需页面调入内存？

将请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常对换区是采用连续分配方式，文件区是采用离散分配方式。

（1）系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此在进程运行之前，需将于该进程有关的文件从文件区拷贝到对换区。

（2）系统缺少足够的对换区空间，这时凡是不会被修改的文件都直接从文件区调入；当换出这些页面时由于他们未被修改不必再将他们重写到磁盘，以后再调入时，仍从文件区直接调入。

（3）UNIX方式。由于与进程有关的文件都放在文件区，但凡是未运行过的页面都应该从文件区调入，而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时应从对换区调入。由于UNIX系统允许页面共享，因此某进程所请求的页面有可能已被其他进程调入内存，此时也就无需再从对换区调入。

11.试说明在请求分页系统中页面的调入过程。

每当程序要访问的页面未在内存时，便向CPU发出缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。该程序通过查找页表得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O，将所缺之页调出内存，然后修改页表。如果内存已满则需先按照某种置换算法从内存中钻出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改必须将它写会磁盘然后再把所缺的页调入内存，并修改页表中的相应表项置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后利用修改后的页表形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程度用户是透明的。

12.在请求分页系统中，常采用哪几种页面置换算法？

（1）最佳置换算法 （2）先进先出页面置换算法

（3）最近最久未使用 （4）最少使用置换算法

（5）Clock置换算法 （6）页面缓冲算法

13.在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果。

M=3时，采用FIFO页面置换算法的缺页次数为9次，缺页率为75%；M=4时，采用FIFO页面置换算法的缺页次数为10次，缺页率为83%。

由此可见，增加分配给作业的内存块数，反而增加了缺页次数，提高了缺页率，这种现象被称为是Belady现象。

14.实现LRU算法所需的硬件支持是什么？

最近最久未使用LRU算法是根据页面调入内存后的使用情况做出决策的，是选择最近最就未使用的页面予以淘汰。

（1）寄存器。记录某进程在内存中各页的使用情况。

（2）栈。保存当前使用的各个页面的页面号。

15.试说明改进型Clock置换算法的基本原理。

在将一个页面换出时如果该页以被修改过，便需将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。

因为修改过的页面在换出时付出开销比未被修改过的页面大，在改进型Clock算法中，既考虑页面的使用情况，还要增加置换代价的因素；在选择页面作为淘汰页面时，把同时满足未使用过和未修改过作为首选淘汰页面。

16.影响页面换进换出效率的若干因素是什么？

（1）页面置换算法。一个好的页面置换算法可使进程在运行过程中具有较低的缺页率，从而减少页面换进换出的开销。

（2）写回磁盘的频率。如果在系统中建立一个已修改换出页面的链表，则对每一个要被换出的页面系统可以暂时不把他们写会磁盘而是挂在已修改换出页面的链表上，页面数目达到一定值时，再将他们一起写回到磁盘上。

（3）读入内存的频率。在设置了已修改换出页面链表后，在该链表上暂时有一批装有数据的页面，有进程再次访问时就不需要从外存上调入而是从已修改换出页面链表中获取。

17.页面缓冲算法的主要特点是什么？它是如何降低页面换进、换出的频率的？

（1）显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少，减少了页面换进、换出的开销。

（2）正是由于换入换出的开销大幅减少才能使其采用一种较简单的置换策略，不需要特殊硬件的支持实现起来非常简单。

如何降低？

在该系统中，内存分配策略丧采用了可变分配和局部置换方式，系统为每个进程分配一定数目的物理块，系统自己保留一部分空闲物理块。为了能显著降低页面换进、换出的频率，在内存中设置了两个链表：

（1）空闲页面链表。是系统掌握的空闲物理块，用于分配给频繁发生缺页的进程以降低该进程的缺页率。当这样的进程需要读入一个页面时，便可利用空闲物理块链表中的第一个物理块来装入此页。

（2）修改页面链表。是已修改的页面形成的链表。设置该链表的目的是为了减少已修改页面换出的次数。当进程需要将一个已修改的页面换出时，系统并不立即把他换出到外存上而是将它所在的物理块挂在修改页面链表的末尾。这样做的目的是降低将已修改页面写回磁盘的频率，降低将磁盘内容读入内存的频率。

18.在请求分页系统中，产生"抖动"的原因是什么？

同时在系统中运行的进程太多，由此分配给每一个进程的物理快太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进、调出的进程数目增加，显然对磁盘的有效访问时间也随之增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，导致发生处理机的利用率急剧下降并趋于0的情况，此时的进程是出于“抖动”状态。

19.何谓工作集？它是基于什么原理确定的？

工作集是指在某段时间间隔△内，进程实际所要访问页面的集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了反之系统出现抖动现象需要选择合适的工作集大小。

让操作系统跟踪每个进程的工作集并为进程分配大于其工作集的物理块，如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，操作系统会暂停一个进程将其页面调出并且将物理块分配给其他进程，防止出现抖动现象。正确选择工作集大小对存储器的利用率和系统吞吐量的提高都产生重要影响。

20.当前可以利用哪几种方法来防止"抖动"？

（1）采取局部置换策略。当某进程发生缺页时，只能在分配给自己的内存空间内进行置换，不允许从其他进程去获得新的物理块。

（2）把工作集算法融入到处理机调度。试图从外存调入一个新作业进入内存，来改善处理机的利用率。如果在调度中融入了工作集算法，则在调度程序从外存调入内存之前必须检查每个进程在内存的驻留页面是否足够多。

（3）利用“L=S”准则调节缺页率。L是缺页之间的平均时间，S是平均缺页服务时间即用于置换一个页面所需要的时间。L>S说明很少缺页，磁盘的能力尚未得到充分的利用。反之说明频繁发生缺页，缺页的速度超过磁盘的处理能力，只有二者接近时磁盘和处理机都可达到他们的最大利用率。

（4）选择暂停的进程。应基于某种原则选择暂停某些当前活动的进程，将他们调出到磁盘上，以便把腾出的内存空间分配给缺页率发生偏高的进程。

21.试说明如何利用"L=S"准则来调节缺页率，以避免"抖动"的发生。

L是缺页之间的平均时间，S是平均缺页服务时间即用于置换一个页面所需要的时间。L>S说明很少缺页，磁盘的能力尚未得到充分的利用。反之说明频繁发生缺页，缺页的速度超过磁盘的处理能力，只有二者接近时磁盘和处理机都可达到他们的最大利用率。

22.为了实现请求分段式存储管理，应在系统中增加配置哪些硬件机构？

（1）请求段表机制。在请求分段式管理中所需的主要数据结构是请求段表。在该表中除了具有请求分页机制中有的访问字段A、修改位M、存在位P和外存始址外，还增加了存取方式字段和增补位。

（2）缺断中断机构。在请求分段系统中采用的是请求调段策略，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段信号。进入OS后由缺段终端处理程序将所需的段调入内存。与缺页中断机构类似，缺段中断机构同样需要在一条指令的执行期间产生和处理中断，以及在一条指令执行期间可能产生多次缺页中断。但是由于分段是信息的逻辑单位，因而不可能出现一条指令在被分割在两个页面中，和一组信息被分割在两个分段中的情况。

（3）地址变换机构。请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存并修改段表，然后才能再利用段表进行地址变换，为此，在地址变换机构中又增加了某些功能，如缺页中断的请求及处理。

23.在请求段表机制中，应设置哪些段表项？

（1）段名 （2）段长 （3）段基址

（4）存取方式

（5）访问字段A。记录该段被访问的频繁程度

（6）修改位M，表示进入内存后是否已被修改过，供置换页面时参考。

（7）存在位。指示本段是否已调入内存

（8）递补位。表示本段在运行过程中是否做过动态增长。

（9）外存始址。指示本段在外存中的起始地址。

24.说明请求分段系统中的缺页中断处理过程。

（1）根据当前执行指令中的逻辑地址查页表判断该页是否在主存储器中。

（2）该页标志为“0”形成缺页中断，中断装置通过交换PSW让操作系统的中断处理程序占用处理器；

（3）操作系统处理缺页中断的办法是查主存分配表找一个空闲的主存快，插页表找出该页在磁盘上的位置，启动磁盘读出该页信息。

（4）把从磁盘上读出的信息装入到找到的主存快中。

（5）当页面住处被装入主存后，应修改页表中对应的表目填上该页所占用的主存快把标志置为1，表示该页已在主存储器中。

（6）由于产生缺页中断时的那条指令并没有执行完，所以把页面装入之后应重新执行被中断指令。

25.请对共享段表中的各项作简要说明。

为了实现分段共享，可以在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。在表项的上面记录了共享段的段号、段上、内存始址、状态位、外存始址以及共享计数等信息。

（1）共享进程技术Count。非共享段仅为一个进程所需要。当进程不再需要该段时，可立即释放该段，并由系统回收该段所占用的空间，而共享段是为多个进程所需要的，为记录有多少个进程正在共享该分段，需要设置共享进程计数count，当某进程不在需要而释放他时，系统并不立即回收该段所占内存区，而是检查count是否为0.

（2）存取控制字段。对于一个共享段应为不同的进程赋予不同的存取权限。

（3）段号。对于一个共享段，在不同的进程中可以具有不同的段号，每个进程可用自己进程的段号去访问该共享段。

26.如何实现共享分段的分配和回收

（1）共享的分配。由于共享段是供多个进程所共享的。因此对共享段的内存分配方法，与费共享段的内存分配方法有所不同。在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享区调入该区，同时将该区的始址填入请求进程的段表的相应项中，还需要在共享段表中增加一表项，填写请求使用该共享段的进程名、段号和存取控制等有关数据，把count置为1.当又有其他进程需要调用该共享段时，由于该共享段已被调入内存，此时无需在为该段分配内存，只需在调用进程的段表中增加一表项填写共享段的物理地址。在共享段的段表中增加一个表项填上调用进程的进程名、该共享段在本进程中的段号、存取控制等，再执行count=count+1，以表明有两个进程共享该段，以后凡是进程需要访问此共享段的都按照上述方式在共享段的段表中增加一个表项。

（2）共享段的回收。当共享此段的某进程不需要该段时，应将该段释放，包括撤销在该段进程段表中共享段所对应的表项，以及执行count-=1，若结果Wie0，则须有系统回收该共享段的物理地址以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则只是取消调用者进程在共享段表中的有关记录。

第六章

1.试说明IO系统的基本功能。

（1）隐藏物理设备的细节。为他们配置相应的设备控制器。I/O系统必须通过对设备加以适当的抽象，以隐藏掉物理设备的实现细节，仅向上层进程提供少量的、抽象的读写命令。

（2）与设备的无关性。用户不仅可以使用抽象的I/O命令还可以使用抽象的逻辑设备名来使用设备，也可以高效的提高OS的可移植性和易适应性。

（3）提高处理机和I/O设备的利用率。尽可能的让处理机和I/O设备尽快地运行起来以提高他们的利用率。也应尽量减少在每个I/O设备运行时处理机的干预时间。

（4）对I/O设备进行控制。

（5）确保对设备的正确共享。

（6）错误处理。对于错误的处理应该尽可能在接近硬件的层面上进行，即在低层软件能够解决的错误就不向上层报告。

2.简要说明I/O软件的四个层次的基本功能。

（1）用户层I/O软件，实现与用户交互的接口，用户可直接调用该层所提供的的、与I/O操作有关的库函数对设备进行操作。

（2）设备独立性软件，用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。

（3）设备驱动程序，与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。

（4）中断处理程序，用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断的现场后，返回到被中断的进程。

3. IO系统接口与软件/硬件(RW/HW)接口分别是什么接口？

I/O系统接口。他是I/O系统与上层系统之间的接口，向上层提供对设备进行操作的抽象I/O命令，以方便高层对设备的使用。有不少OS在用户层提供了与I/O操作有关的库函数，供用户使用，在上层系统中有文件系统、虚拟存储器系统以及用户进程等。

软件/硬件接口。他的上面是中断处理程序和用于不同设备的设备驱动程序，下面是各种设备的控制器。

4. 与设备无关性的基本含义是什么？为什么要设置该层？

设备独立性软件。现代OS中的I/O系统基本上都实现了与设备无关性，也成为了与设备无关的软件。基本含义是：I/O软件独立于具体使用的物理设备。由此带来的好处是提高了I/O系统的可适应性和可扩展性。使他们能应用于许多类型的设备，而且在每次增加新设备或者替换老设备时，都不需要对I/O软件进行修改，这样就方便了系统的更新和扩展。设备独立性软件的内容包括设备命名、设备分配、数据缓冲和数据高速缓冲一类软件。

5. 试说明设备控制器的组成。

由于设备控制器为与CPU和设备之间，既要与CPU通信，又要与设备通信，还要具有按照CPU所发来的命令去控制设备工作的功能。

（1）设备控制器与处理机的接口。该接口用于实现CPU与设备控制器之间的通信，在该接口中中有三类信号线：数据线、地址线和控制线。

（2）设备控制器与设备的接口。在一个设备控制器上可以连接一个或多个设备。相应的在控制器中边有一个或多个设备接口。在每个接口中都存在数据、控制和状态三种类型的信号。控制器中的I/O逻辑根据处理机发来的地址信号去选择一个设备接口。

（3）I/O逻辑。I/O逻辑用于实现对设备的控制。他通过一组控制线与处理机交互，处理机利用该逻辑向控制器发送I/O 命令。每当CPU要启动一个设备时，一方面将启动命令发送给控制器，另一方面又同时通过地址线把地址发送给控制器，由控制器的I/O逻辑对收到的地址进行译码，再根据所译出的命令对所选设备进行控制。

6.为了实现CPU与设备控制器间的通信,设备控制器应具备哪些功能？

设备控制器的主要功能是控制一个或多个IO设备，已实现IO设备和计算机之间的数据交换，他是CPU与IO设备之间的接口，接收从CPU发来的命令去控制IO设备的工作，使处理机能从频繁的设备控制事物中解脱出来。

（1）接受和识别功能。设备存储器能接收并识别处理机发来的多种命令。

（2）数据交换。设备控制器可实现CPU与控制器之间、控制器与设备之间的数据交换。

（3）标识和报告设备的状态。控制器应记下设备的状态供CPU了解。

（4）地址识别。设备控制器必须能够识别其所控制的每个设备的地址。

（5）数据缓冲区。输出时用此缓冲区暂存由诸暨高速传来的数据然后菜才与IO设备所匹配的速率将缓冲器中的数据传送给IO设备。输入时，缓冲区则用于暂存从IO设备送来的数据，带接受到一批数据后，再将缓冲区中的数据高速的传送给主机。

（6）差错控制。若发现传送中出现了错误，通常是将差错检测码置位并向CPU报告，于是CPU将本次传送来的数据作废，并重新进行一次传送。

7.什么是内存映像IO？它是如何实现的？

驱动程序将抽象IO命令转换出的一系列具体的命令、参数等数据装入设备控制器的相应寄存器，由控制器来执行这些命令，具体实施对IO设备的控制。

（1）利用特定的IO指令。为实现CPU和设备控制器之间的通信，为每个控制寄存器分配一个IO端口，还设置了一些特定的IO指令。

（2）内存映像IO。在编制上不再区分内存单元地址和设备控制器中的寄存器地址，都采用k。

8.为什么说中断是OS赖以生存的基础？

中断在操作系统中有着特殊重要的地位，他是多道程序得以实现的基础，没有中断就不能实现多到程序，因为进程之间的切换时通过中断了来完成的，另一方面中断也是设备管理的基础，为了提高处理机的利用率和实现CPU与IO设备并行运行，也必须有中断的支持。中断处理程序是IO系统中最低的一层，他是整个IO系统的基础。

9.对多中断源的两种处理方式分别用于何种场合？

对应多中断源的情况，当处理机正在处理一个中断时，又来一个新的中断请求，这时应如何处理。

（1）屏蔽中断，当处理机正在处理一个中断时，将屏蔽掉所有的中断，即处理机对任何信道的中断请求都暂时不予理睬而让他们等待。知道处理机已经完成本次中断的处理后，处理机再去检查是否有中断发生。若有再去处理新到的中断，若无则但会被中断的程序。在该方法中所有中断都将会按照顺序依次处理。

（2）嵌套中断，在设置了中断优先级的系统中，通常按照如下的规则来进行优先级控制：

①当同时有多个不同优先级的中断请求时，CPU优先响应最高优先级的中断请求；

②高优先级的中断请求可以抢占正在运行时的低优先级中断的处理机。

10.设备中断处理程序通常需完成哪些工作？

（1）唤醒被阻塞的驱动程序进程

（2）对被中断进程的CPU环境进行保护

（3）分析中断原因，转入相应的中断处理程序

（4）恢复被中断进程的现场

（5）返回被中断的进程，继续执行

11.简要说明中断处理程序对中断进行处理的几个步骤。

当一个进程请求IO操作时，该进程将被挂起，直到IO设备完成IO操作后，设备控制器便向CPU发送一个中断请求，CPU相应后便转向中断处理程序，中断处理程序执行相应的处理，处理完后接触相应进程的阻塞状态。

（1）测定是否有未响应的中断信号。

（2）保护被中断进程的CPU环境。

（3）转入相应的设备处理程序

（4）中断处理

（5）恢复CPU的现场并退出中断

12.试说明设备驱动程序具有哪些特点。

设备驱动程序属于低级的系统例程，他与一般的应用程序及系统程序之间有下述明显差异：

（1）驱动程序是实现在与设备无关的软件和设备控制器之间通信和转换的程序，具体说，他将抽象的IO请求转换成具体的IO操作后传送给控制器。又把控制器中所记录的设备状态和IO操作完成情况及时地反映给请求IO的进程。

（2）驱动程序与设备控制器以及IO设备的硬件特性紧密相关，对于不同类型的设备应配置不同的驱动程序。但可以为相同的多个终端设置一个终端驱动程序。

（3）驱动程序与IO设备所采用的IO控制方式紧密相关，常用的IO控制方式是中断驱动和DMA方式。

（4）由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写。

（5）驱动程序应允许可重入，一个正在运行的驱动程序常会在一次调用完成前被再次调用。

13.设备驱动程序通常要完成哪些工作？

（1）接收由与设备无关的软件发来的命令和参数，并将命令中的抽象要求转换为与设备相关的低层操作序列。

（2）检查用户IO请求的合法性，了解IO设备的工作状态，传递与IO设备操作有关的参数设置设备的工作方式。

（3）发出IO命令，如果设备空闲便立即启动IO设备完成指定的IO操作，如果设备忙碌则将请求者的请求快挂在设备队列上等待。

（4）及时响应由设备控制器发来的中断请求，并根据其中断类型，调用响应的中断处理程序进行处理。

14.简要说明设备驱动程序的处理过程可分为哪几步。

设备驱动程序的主要任务是启动指定设备，完成上层指定的IO工作，但在启动之前应先完成必要的准备工作，如检测设备状态是否为“忙”，在完成所有的准备工作后才向设备控制器发送一条启动命令。

（1）将抽象要求转换为具体要求。通常在每个设备控制器中都含有若干个寄存器，分别用于暂存命令、参数和数据等。由于用户及上层软件对设备控制器的具体情况毫无了解，因而只能发出命令，而这些命令是无法传送给设备控制器的，因此就需要将这些抽象要求转换为具体要求。

（2）对服务请求进行校验。驱动程序在启动IO设备之前，必须先检查该用户的IO请求是不是该设备能够执行的。

（3）检查设备的状态。启动某个设备进行IO操作，其前提条件应该是该设备正处于就绪状态，为此在每个设备控制器中都有一个状态寄存器。驱动程序在启动设备之前要把状态寄存器中的内容读入到CPU的某个寄存器中，通过测试寄存器的不同位来了解设备的状态。

（4）传送必要的参数。在确定设备处于接收就绪状态后便可以向控制器的相应寄存器传送数据以及与控制本次数据传输有关的参数。

（5）启动IO设备，驱动程序向控制器中的命令寄存器传送相应的控制命令。对于字符设备若发出的是写命令，驱动程序便把一个字符传送给控制器，若发出的读命令则驱动程序等待接受数据，并通过读入控制器的状态寄存器中状态字的方法来确定数据是否到达。

在多道程序系统中，驱动程序一旦发出IO命令启动了一个IO操作后，驱动程序便把控制返回给IO系统，把自己阻塞起来，指导中断到来时再被唤醒。具体的IO操作是在设备控制器的控制下进行的，因此在设备忙于传送数据时，处理机又可以去干其他的事情，实现了处理机与IO设备的并行操作。

15.试说明推动I/O控制发展的主要因素是什么。

16.有哪几种I/O控制方式？各适用于何种场合？

（1）使用轮询的可编程IO方式。处理机向控制器发出一条IO指令，启动输入设备输入数据时，要同时把状态寄存器的忙/闲标志busy置为1，然后不断地循环测试busy。用于早期

（2）使用可中断的可编程IO方式。某进程要启动某个IO设备工作时，便由CPU向相应的设备控制器发出一条IO指令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定IO设备。此时CPU与IO设备并行操作。当前广泛采用。

（3）直接存储器访问方式

17.试说明DMA的工作流程。

当CPU要从磁盘读入一块数据块时，便向磁盘控制器发出一条读命令。该命令被送入命令寄存器CR中。同时，需要将本次要读入数据在内存中的起始目标送入内存地址寄存器MAR中，将要读数据的字数送入数据计数器DC中。还需将磁盘中的源地址直接送到DMA控制器的IO控制逻辑上。然后启动DMA控制器进行数据传送。以后CPU便可去处理其他任务，整个数据传送过程由DMA控制器进行控制。当DMA控制器已从磁盘读入一个字的数据并送入数据寄存器DR后，再挪用一个存储器周期，将该字传送到MAR所指示的内存单元中。然后便对MAR内容加q，将DC内容减1，若减1后DC内容不为0，表示传递未完，便继续传送下一个子，否则由DMA控制器发出中断请求。

18.为何要引入与设备的无关性？如何实现设备的独立性？

为了方便用户和提高OS的可适应性和可扩展性，在现代OS的IO系统中，都增加了与设备无关的IO软件，以实现设备独立性，也称为设备无关性。基本含义是应用程序中所用的设备，不局限于使用某个具体的物理设备。为每个设备所配置的设备驱动程序是与硬件紧密相关的软件。

为了实现设备独立性，必须再在设备驱动程序之上设置一层软件，称为与设备无关的IO软件或设备独立性软件。

19.与设备的无关的软件中,包括了哪些公有操作的软件？

与设备无关的软件是IO系统的最高层软件，在他下面的是设备驱动程序，其间的界限因操作系统和设备的不同而有所差异。

（1）设备驱动程序的统一接口。一方面要求每个设备驱动程序与OS之间都有着相同的接口或者相近的接口，这样会使增添一个新的设备驱动程序便的容易，方便开发人员对设备驱动程序的编制。另一方面要将抽象的设备名映射到适当的驱动程序上，或者说将抽象的设备名转换为具体的物理设备名并进一步可以找到相应物理设备的驱动程序入口。

（2）缓冲管理。为了缓和CPU和IO设备之间的矛盾提高CPU的利用率在现代OS中分别为字符设备和块设备配置了相应的缓冲区。

（3）差错控制。①暂时性错误 ②持久性错误

（4）对独立设备的分配与回收。

（5）独立于设备的逻辑数据块。

20.在考虑到设备的独立性时,应如何分配独占设备？

当某进程提出IO请求后，系统的设备分配程序可按照下述步骤进行设备分配：

（1）分配设备。根据IO请求中的物理设备名查找系统设备表SDT，从中找出该设备的DCT，再根据DCT中的设备状态字段，可知该设备是否正忙。若忙便将请求IO的进程的PCB挂在设备队列上；否则按照一定的算法计算本次设备分配的安全性，如果不会导致系统进入不安全状态，便将设备分配给请求进程，分否则仍将其PCB插入设备等待队列。

（2）分配控制器。在系统把设备分配给请求IO的进程后，再到其DCT中找出与该设备连接的控制器的COCT，从COCT的状态字段中可知该控制器是否忙碌。若忙便将请求IO进程的PCB挂在该控制器的等待队列上，否则便将该控制器分配给进程。

（3）分配通道。在该COCT中又可找到与该控制器连接的通道的CHCT，再根据CHCT内的状态信息可知该通道是否忙碌，若忙，便将请求IO的进程挂在该通道的等待队列上；否则将该通道分配给进程，只有在设备、控制器和通道三者都分配成功时，这次的设备分配才算成功，然后便可以启动该IO设备进行数据传送。

21.何谓设备虚拟？实现设备虚拟时所依赖的关键技术是什么？

通过虚拟技术可以将一台独占设备变换成若干台逻辑设备，供若干个用户同时使用，通常把这种经过虚拟技术处理后的设备成为虚拟设备。

其实现所依赖的关键技术是Spooling技术。

22.在实现后台打印时，SPOOLing系统应为请求IO的进程提供哪些服务？

（1）由输出进程在输出井中为之申请一快空闲盘快区，并将要打印的数据送入其中。

（2）输出进程再为用户申请一张空白的用户打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。

（3）一旦打印机空闲，输出进程便从请求打印队列的对首取出一张请求打印表，根据表中的要求将要打印的数据从输出井传送到内存缓冲区再由打印机进行打印。

23.假脱机系统向用户提供共享打印机的基本思想是什么？

对于每个用户而言，系统并非即时执行其程序输出数据的真实打印操作，而只是即时将数据输出到缓冲区，这时候数据并未真正被打印，只是让用户感觉系统已经为他打印；真正的打印操作，是在打印机空闲且该打印任务在等待队列中已排到对首时进行的，而且打印操作本事也是利用CPU的一个时间片，没有使用专门的外围及；以上的过程是对用户屏蔽的，用户是不可见的。（）

24.引入缓冲的主要原因是什么？

（1）缓和CPU和IO设备间速度不匹配的矛盾

（2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制

（3）解决数据粒度不匹配的问题

（4）提高CPU和IO设备之间的并行性

25.在单缓冲情况下,为什么系统对一块数据的处理时间为max(C,T)＋M？

在单缓冲情况下，每当用户进程发出一IO请求时操作系统便在主存中为之分配一缓冲区。在块设备输入时，假定从磁盘把一块数据输入到缓冲区的时间为T，OS将该缓冲区中的数据传送到用户区的时间为M，而CPU对这一块数据处理的时间为C，由于T和C是可以并行的，当T>C时，系统对每一块的数据的处理时间为M+T，反之则为M+C，故可以把系统对每一块数据的处理时间表示未Max（C,T）+M。

26.为什么在双缓冲情况下,系统对一块数据的处理时间为maxCT,C？

为了加快输入和输出的速度，提高设备利用率，又引入了双缓冲机制，也称为缓冲对换。在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据并送入用户进程。接着由CPU对数据进行计算。在双缓冲时，系统处理一块数据的时间可以粗略的认为是Max（C，T），如果C<T，便使块设备连续输入，如果C>T，则可使CPU不必等待设备输入，对于字符设备若采用行输入方式，则采用双缓冲通常能消除用户的等待时间，即用户在输入玩第一行后，在CPU执行第一行的命令时，用户可继续向第二缓冲区输入下一行数据。

27.试绘图说明把多缓冲用于输出时的情况。

28.试说明收容输入工作缓冲区和提取输出工作缓冲区的工作情况

（1）收容输入。输入进程可调用Getbuf（emq）过程，从空缓冲队里emq的队首摘下一空缓冲区，把它作为收容输入工作缓冲区hin。然后把数据输入其中，装满后再调用Putbuf（inq，hin）过程，将它挂在输入队列inq队列上。

（2）提取输出。计算进程可以调用Getbuf（inq）过程，从输入队列inq的队首取得以缓冲区，作为提取输入工作缓冲区（sin），计算进程从中提取数据。计算进程用完该数据后，再调用Putbuf（emq，sin）过程，将它挂到空缓存冲队列emq上。

29.何谓安全分配方式和不安全分配方式？

安全分配方式是指每当进程发出IO请求后，便进入阻塞状态，直到其完成IO操作完成时才被唤醒。一旦进程已经获得某种设备资源后便阻塞，使他不可能再请求任何资源，而在他运行时又不保持任何资源，这种分配方式已经摒弃了造成死锁的请求和保持条件，分配是安全的。缺点是进程进展缓慢，CPU与IO设备串行工作。

不安全分配方式是指进进程发出IO请求后仍继续执行，需要时又可以发出第二个、第三个IO请求。仅当程序请求的设备已被另一个进程占有时，进程才进入阻塞状态。

30.磁盘访问时间由哪几部分组成？每部分时间应如何计算？

磁盘设备在工作时以恒定速率旋转，为了读或写，磁头必须能移动到所指定的磁道上，并等待所指定的扇区的开始位置旋转到磁头下，然后再考试读或写数据，故可以把对磁盘的访问时间分成三部分：

（1）寻道时间T。把磁头移动到指定磁道上所经历的世界，该时间是启动磁壁的时间s与磁头移动n条磁道所花费的时间之和。T=m*n+s

（2）旋转延迟时间T。这是指定扇区移动到磁头下面所经历的世界，不同的磁盘类型中旋转速度至少相差一个数量级。

（3）传输时间T。这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。T的大小与每次所读写的字节数b和旋转速度有关。T =b/rN, 其中r为次哦按每秒钟的转数，N为一条磁道上的字节数，当一次读写的字节数相当于半条磁道上的字节数时，T与T相同，因此访问时间T表示为：T=T+1/2r+b/rN。

31.目前常用的磁盘调度算法有哪几种？每种算法优先考虑的问题是什么？

（1）早期的磁盘调度算法

①先来先服务。他根据进程请求访问磁盘的先后次序进行调度。

②最短寻道时间优先。要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。

（2）基于扫描的磁盘调度算法

①扫描（SCAN）算法。实质是基于优先级的调度算法，不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。

②循环扫描算法。CSCAN算法规定磁头单项移动，例如只是有里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。采用循环草莓方式后，上述请求进程的请求延迟从原来的2T减为T+Smax，T为有里向外或由外向里单项扫描玩要访问的磁道所需的寻道时间，而Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道的寻道时间（或相反）。

③NSetpSCAN和FSCAN算法。

第七章

1. 何谓数据项、记录和文件？

在文件系统中，数据项是最低级的数据组织形式，可把他分为以下两种类型：

（1）基本数据项。用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，又称为字段。

（2）组合数据项。是由若干个基本数据项组成的，简称组项。

基本数据项除了数据名之外还应该有数据类型。

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。

在诸多记录中，为了能够唯一的标识一个记录，必须在一个记录的各个数据项中确定出一个或者几个数据项，他们的集合成为关键字。

文件是由创建者所定义的、具有文件名的一组相关元素的集合，可以分为有结构文件和无结构文件两种。文件在文件系统中是一个最大的数据单位，他描述了一个对象集。文件属性可以包括：（1）文件类型（2）文件长度（3）文件的物理位置（4）文件的建立时间

2. 文件系统的模型可分为三层,试说明其每一层所包含的基本内容。

（1）对象及其属性

①文件。各种不同类型的文件都作为文件管理的直接对象

②目录。每个目录项必须含有文件名、对文件属性的是说明以及该文件所在的物理地址。

③磁盘存储空间。

（2）对对象进行操纵和管理的软件集合

该层是文件管理系统的核心部分，文件管理的功能大多都是这一层实现的，包括①对文件存储空间的管理②对文件目录的管理③用于将文件的逻辑地址转换为物理地址的机制④对文件读和写的管理⑤对文件的共享与保护等功能

（3）文件系统提供给用户的接口

为了方便用户的使用，文件系统以接口的形式提供了一组对文件和记录操作的手法和手段。

①命令接口。作为用户与文件系统直接交互的接口，用户可以通过键盘中断键入命令取得文件系统的服务。

②程序接口。作为用户程序与文件系统的接口，用户程序可以通过系统调用取得文件系统的服务。

3. 与文件系统有关的软件可分为哪几个层次？

（1）IO控制层。文件系统的最底层，主要由磁盘驱动程序等组成

（2）基本文件系统层。用于处理内存与磁盘之间数据块的交换

（3）基本IO管理程序。用于完成与磁盘IO有关的事务

（4）逻辑文件系统。用于处理与记录文件相关的操作。

4. 试说明用户可以对文件施加的主要操作有哪些。

（1）最基本的文件操作

①创建文件②删除文件③读文件④写文件⑤设置文件的读写位置

（2）文件的打开与关闭操作。

当用户第一次请求对某文件进行操作时，需先利用open系统调用将文件打开。打开就是在用户和指定文件之间建立起一个连接，也可利用关闭系统调用来关闭此文件。

（3）其他文件操作

OS为用户提供了一系列文件操作的系统调用，最常用的一类是有关对文件属性的操作，即允许用户直接设置和获得文件的属性。另一类是有关目录的操作，此外还有用于实现文件共享的系统调用，以及用于对文件系统进行操作的系统调用。

5.为什么在大多数OS中都引入了"打开"这一文件系统调用？打开的含意是什么？

当用户要求对一个文件实施多次读写或其他操作时，每次都要从检索目录开始。为了避免多次重复的检索目录，在大多数OS中都引入了打开这一文件系统调用，当用户第一次请求对某文件进行操作时，需要先利用open系统调用将该文件打开。所谓“打开”就是系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号返回给用户。换言之“打开”就是在用户和指定文件之间建立起一个连接。此后用户可以通过该连接直接得到文件信息，从而避免了再次通过目录检索文件，即当用户再次向系统发出文件请求时，系统根据用户提供的索引号可以直接打开文件表中查找到文件信息。这样不仅节省了大量的检索开销也显著提高了对文件的操作速度。如果用户不再需要对该文件实施相应的操作，可以利用“关闭”系统调用来关闭此文件，即断开此连接，OS将会把该文件从打开文件表中的表目上删除掉。

6.何谓文件的逻辑结构？何谓文件的物理结构？

文件的逻辑结构，是从用户观点出发所观察到的文件组织形式，即文件是由一系列的殴记录组成的，是用户可以直接处理的数据及其结构，他独立于文件的物理特征，又称为文件组织。

文件的物理结构，又称为文件的存储结构。这是指系统将文件存储在外存上所形成的一种存储组织形式，是用户看不到的。文件的物理结构不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关，无论是文件的逻辑结构还是物理结构都会影响对文件的检索速度。

7.按文件的组织方式可将文件分为哪几种类型？

（1）顺序文件。指由一系列记录按照某种顺序排列所形成的文件，其中的记录是可以定长记录或可变长记录。

（2）索引文件，指为可变长记录建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。

（3）索引顺序文件。这是顺序文件和索引文件相结合的产物，这里为每个文件建立一张索引表时，并不是为每一个记录建立一个索引表，而是为一组记录中的第一个记录建立一个索引表项。

8.如何提高对变长记录顺序文件的检索速度？

为变长记录文件建立一张索引表，为主文件中的每个记录在索引表中分别设置一个表项，记录指向记录的指针（即记录在逻辑地址空间的首址）以及记录的长度L，索引表按关键字排序，因此其本身也是一个定长记录的顺序文件，这样就把对变长记录顺序文件的顺序检索转变为对定长记录索引文件的随机检索，从而加快对记录检索记录的速度，实现直接存取。

9.通过哪两种方式来对固定长记录实现随机访问？

显式址方式可用于对定长记录的文件实现直接或随机访问，因为任何记录的位置都很容易通过记录长度来计算出来。

（1）通过文件中记录的位置。此时在文件中的每一个记录可从0-N-1的整数来唯一标识一个记录。对于定长记录文件，若要查找的第i个记录可以获得第i个记录相对于第一个记录首址的地址：Ai=i*L。

（2）利用关键字。此时用户必须指定一个字段作为关键字，通过指定的关键字来查找该记录，当用户给出要检索记录的关键字时，系统将利用该关键字顺序地从第一个记录开始，与每一个记录的关键字进行比较，直到找到匹配的记录。

10.可以采取什么方法来实现对变长记录文件进行随机检索？

为变长记录文件建立一张索引表，为主文件中的每个记录在索引表中分别设置一个表项，记录指向记录的指针（即记录在逻辑地址空间的首址）以及记录的长度L，索引表按关键字排序，因此其本身也是一个定长记录的顺序文件，这样就把对变长记录顺序文件的顺序检索转变为对定长记录索引文件的随机检索，从而加快对记录检索记录的速度，实现直接存取。

11.试说明索引顺序文件的几个主要特征。

索引顺序文件是对顺序文件的一种改进，基本上客服了变长记录的顺序文件不能随机访问，以及不便于记录的删除和插入的缺点。但他保留了顺序文件的关键特征，即记录是按关键字的顺序组织起来的，又增加了两个新特征：一是引入了文件索引表，通过该表可以实现对索引顺序文件的随机访问；二是增加了溢出文件，用它来记录新增加的、删除的和修改的记录。可见顺序索引文件是顺序文件和索引文件相结合的产物，能有效客服变长记录文件的缺点，而且付出的代价也不算太大。

12.试说明对索引文件和索引顺序文件的检索方法。

在对索引文件进行检索时，可以根据用户提供的关键字利用折半查找法去检索索引表，从中找到相应的表项，再利用该表项中给出的指向记录的指针值去访问所需的记录，每当要向索引文件中增加一个新记录时，便需要对索引表进行修改，由于索引文件可能有较快的检索速度，故他主要用于对信息处理的及时性要求较高的场合。

在对索引顺序文件进行检索时，首先也是利用用户所提供的关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组的第一个记录在主文件中的位置，然后再利用顺序查找法去查找主文件，从中找到所要求的的记录。

13.试从检索速度和存储费用两方面来比较两级索引文件和索引顺序文件。

两级索引文件：检索速度快，存储费用高

索引顺序文件：检索速度慢，存储费用低

14.对目录管理的主要要求是什么？

文件管理也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用，对目录管理的要求如下：

（1）实现“按名存取”。用户只需向系统提供所需访问文件的名字，便能快速准确地找到指定文件在外存上的存储位置。

（2）提高对目录的检索速度。通过合理的组织目录结构加快对目录的检索速度从而提高对文件的存取速度。

（3）文件共享。在多用户系统中应允许多个用户共享一个文件。

（4）允许文件重名。系统应该允许不同用户对不同文件采用相同的名字。

15.采用单级目录能否满足对目录管理的主要要求？为什么？

每当要建立一个新文件时，必须先检索所有的目录项，以保证新文件名在目录中是唯一的，然后再从目录表中找出一个空白目录项，填入新文件的文件名及其其他说明信息，并置状态位为1，删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空间然后再清除该目录项。

单级文件目录的优点是简单，但他只能实现目录管理中最基本的功能—按名存取，不能满足对文件目录的其他三方面的要求：

（1）查找速度慢。

（2）不允许重名。

（3）不便于实现文件共享。

16.目前广泛采用的目录结构形式是哪种？它有什么优点？

在现代OS中，最通用且最实用的文件目录无疑是树形结构目录，可以明显提高对目录的检索速度和文件系统的性能。主目录被称为根目录，在每个文件目录中只能有一个根目录，每个文件和每个目录都只能有一个父目录。把数据文件称为树叶，其他的目录均作为树的结点或称为子目录。

17.何谓路径名和当前目录？

路径名。在树形结构目录中，从根目录到任何数据文件都只有一条唯一的通路。在该路径上从树的根目录开始，把全部目录文件名与数据文件名依次地用“/”链接起来，构成该数据文件唯一的路径名。

当前目录。进程对各文件的访问都相对于“当前目录”而进行。此时各文件所使用的路径名只需要从当前目录开始，逐级经过中间的目录文件，最后到达要访问的数据文件，把这一路径上的全部目录文件名与数据文件名用“/”连接形成路径名。这样把从当前目录开始直到数据文件为止所构成的路径名称为相对路径名。

18.Hash检索法有何优点？又有何局限性？

建立一张Hash索引文件目录，便可利用Hash方法进行查询，即系统利用用户提供的文件名，并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，这样将显著提高检索速度。

局限性：对于使用了通配符的文件名，此时系统便无法利用H撒谎法检索目录，因此系统还是需要利用线性查找法查找目录。

19.在Hash检索法中,如何解决"冲突"问题？

在进行文件名的转换时，有可能把n个不同的文件名转换为相同的Hash值，即出现了所谓的“冲突”。一种处理此“冲突”的有效规则是：

（1）在利用Hash法索引查找目录时，如果目录表中相应的目录项为空，则表示系统中并无指定文件。

（2）如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。

（3）如果在目录表的相应项中的文件名与指定文件名并不匹配，则表示发生了“冲突”此时需将其Hash值再加上一个常数形成新的索引值，再返回到第一步重新开始查找。

20.试说明在树形目录结构中线性检索法的检索过程,并给出相应的流程图。

线性检索法又称为顺序检索法。在单极目录中利用用户提供的文件名，用顺序查找法直接从文件目录中找到指明文件的目录项。在树形目录中用户提供的文件名是由多个文件分量名组成的路径名。假定用户给定的文件路径名是/usr/sat/mbox，则查找/usr/ast/mbox文件的过程如下：

首先，系统应先读入第一个文件分量名usr，用它与根目录文件中各目录项中的文件名顺序的比较，从中找出匹配者，并得到匹配项的索引结点号6，再从6号索引结点中得知use目录文件放在132号盘中，将该盘块内容读入内存。

其次，系统再将路径名中的第二个分量名sat读入，用它与放在132号盘块中的第二级目录文件各目录项的文件名顺序进行比较，又找到匹配项，从中找到ast的目录文件放在26号索引结点中，再从26号索引结点中得知/usr/ast存放在496号盘块中，再读入496号盘块。

然后，系统又将该文件的第三分量名mbox读入，用它与第三级目录文件在/usr/ast中各目录项中的文件名进行比较，最后得到/usr/ast/mbox的索引结点号为60，即在60号索引结点中存放了指定文件的物理地址。目录查询操作到此结束，如果在顺序查找过程中，发现有一个文件分量名未能找到，应停止查找，并返回“文件未找到”信息。

21.基于索引结点的文件共享方式有何优点？

引用索引结点，即诸如文件的物理地址及其他的文件属性等信息，不再是存放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。此时由任何用户对共享文件所进行的操作和修改都将引起其相应结点的内容的改变，这些改变是其他用户可见的，从而也就能提供给其他用户来共享。在索引结点在中还应有一个链接计数count，用于标识链接到本索引结点上的用户目录项的数目，count=3时，表示有三个用户目录项连接到本文件上，或者说有三个用户共享此文件。

优点是建立新的共享链接时，不改变文件的拥有者关系，仅仅把索引结点共享计数器加1，系统便可获悉了由多少个目录项指向该文件。缺点是拥有者不能删除自己的文件否则会出错。

22.什么是主父目录和链接父目录？如何利用符号链实现共享？

主目录被称为根目录，在每个文件目录中只能有一个根目录，每个文件和每个目录都只能有一个父目录，把数据文件成为树叶，其他的目录均作为树的结点，或称为子目录。

利用符号链接实现文件共享的基本思想是允许一个文件或子目录有多个父目录，但其中仅有一个作为主父目录，其他的几个父目录都是通过符号链接方式与之相链接的，简称链接父目录。

为使链接父目录F5能共享文件，可由系统创建一个LINK类型的文件，也取名为F，并将F写入链接父目录D5中，以实现D5与文件F8的链接。在新文件F中只包含被链接文件F8的路径名。这样的链接方式被称为符号链接。新文件F中的路径名则只被看做是符号链。当用户D5访问被链接的文件F8，且正要读LINK类新文件时，此要求将被OS截获，OS根据新文件中的路径名去找到文件F8，然后对他进行读（写），这样就实现了用户B对文件F的共享。

23.基于符号链的文件共享方式有何优点？

再利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。

当文件的拥有者把一个共享文件删除后，如果其他用户又试图通过符号链去访问一个已被删除的共享文件，则会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。

24.什么是保护域？进程与保护域之间存在着的动态联系是什么？

为了对系统中的资源进行保护而引入了保护域的概念，简称“域”。是进程对一组对象访问权的集合，进程只能在指定域内执行操作。“域”也就规定了进程所能访问的对象和能执行的操作。

在进程和域之间，也可以是一对多的关系，即一个进程可以联系着多个域。在此情况下可将进程的运行分为若干个阶段，其每个阶段联系着一个域，这样便可以根据运行的实际需要来规定在进程运行的每个阶段中所能访问的对象。

25.试举例说明具有域切换权的访问控制矩阵。

为了实现在进程和域之间的动态联系，应该能够将进程从一个保护域切换到另一个保护域。为了能对进程进行控制，同样应将切换作为一种权利，仅当进程有切换权时，才能进行这种切换。为此在访问矩阵中又增加了几个队形，分别把它们作为访问矩阵中的几个域；当且进的Switch属于access（i，j）时，才允许进程从域i切换到域j。

例如，由于域D1和D2所对应的项目中有一个S即Switch，故而允许在域D1中的进程切换到D2中。类似的在域D2和对象D3所对应的项中也有S，这表示在D2域中运行的进程可以切换到域D3中，但不允许该进程再从域D3返回到D1。

26.如何利用拷贝权来扩散某种访问权？

可以利用拷贝权将在某个域中所拥有的访问权扩展到同一列的其他域中，亦即为进程在其他的域中也赋予对同一对象的访问权。

凡是在访问权（access（i，j））上加星号者，都表示在i域中运行的进程能将其对对象j的访问权复制成在任何域中对同一对象的访问权。

例如在域D2中对文件F2的读访问权上加*，表示运行在D2域中的进程可以将其对文件F2的读访问权扩展到D3中去。又如在域D1中对文件F3的写访问权加上*后，使运行在域D1中的进程可以将其对文件F3的写访问权扩展到域D3中去，使在域D3中运行的进程也具有对文件F3的写访问权。

27.如何利用拥有权来增、删某种访问权？

可以利用拷贝权将在某个域中所拥有的访问权扩展到同一列的其他域中，亦即为进程在其他域中也赋予对同一对象的访问权。

同时利用所有权来实现增加某种访问权或者能删除某些访问权。如果在access（i,j）中包含所有访问权，则在域Di上运行的进程可以增加或删除其在j列上任何项中的访问权。换言之进程可以增加或删除在任何其他域中运行的进程对对象j的访问权。例如在域D1中运行的进程是文件F1的所有者，他能增加或删除在其他域中的运行进程对文件F1的访问权。

28.增加控制权的主要目的是什么？试举例说明控制权的应用。

拷贝权和所有权都是用于改变矩阵内同一列的各项访问权，或者是说用于改变在不同域中运行的进程对同一对象的访问权的。控制权则可以用于改变矩阵内同一行中的各项访问权，亦即，用于改变在某个域中运行的进程对不同对象的访问权。

如果在access（i，j）中包含了控制权，则在域Di中运行的进程可以删除在域Dj中运行的进程对各对象的任何访问权。例如在access（D2，D3）中包括了控制权，则一个在域D2中运行的进程能够改变对域D3内各项的访问权。

29.什么是访问控制表？什么是访问权限表？

这是指对访问矩阵按列（对象）划分，为每一列建立一张访问控制表ACL，在该表中已把矩阵中属于该列的所有空项删除，此时的访问控制表是由一有序对所组成的。

如果把访问矩阵按行（域）划分，便可由每一行构成一张访问权限表，换言之这是由一个域对每一个对象可以执行的一组操作所构成的表，表中的每一项即为该域对某对象的访问权限，当域为用户、对象为文件时，访问权限表便可用来描述一个用户对每一个文件所能执行的一组操作。

30.系统如何利用访问控制表和访问权限表来实现对文件的保护？

访问控制表也可用于定义缺省的访问权集，即在该表中列出了各个域对某对象的缺省访问权集。在系统中配置了这种表后，当某用户要访问某资源时，通常是首先由系统到缺省的访问控制表中，去查找该用户是否具有对指定资源进行访问的权利，如果找不到再到相应对象的访问控制表中去查找。

大多数系统都同时采用访问控制表和访问权限表，在系统中为每个对象配置一张访问控制表。当一个进程第一次试图去访问一个对象时，必须先检查访问控制表，检查进程是否具有该对象的访问权。如果无权访问便由系统来拒绝进程的访问，并构成一例外事件，否则便允许进程对该对象进行访问，并未该进程建立一访问权限，将之链接到该进程。以后该进程便可直接利用这一返回的权限去访问该对象，这样便可以快速的验证其访问的合法性。当进程不再需要对该对象进行访问时，便可撤销该访问权限。