仓库地址： 仓库

第一章.操作系统引论

1.1操作系统的目标和作用

1.1.1操作系统的目标

• 有效性：提高系统资源利用率和系统吞吐量
• 方便性：提供用户操作接口
• 可扩充性：方便增加新的功能和模块
• 开放性：遵循国际标准，便于相互兼容

1.1.2操作系统的作用

• OS作为用户与计算机硬件系统之间的接口：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统；用户在OS帮助下，能够方便、快捷、安全、可靠地操纵计算机硬件和运行自己的程序；OS是一个系统软件，因而这种接口是软件接口。
• OS作为计算机系统资源的管理者：在一个计算机系统中，通常都含有各种各样的硬件和软件资源。归纳起来可将资源分为四类：处理器、存储器、I/O设备、信息(数据和程序)。相应地，OS的主要功能也正是针对这四类资源进行有效的管理。
• OS实现了对计算机资源的抽象：对于一台完全无软件的计算机系统(即裸机)，即使其功能再强，也必定是难于使用的。在裸机上覆盖上一层I/O设备管理软件,将是一台比裸机功能更强、使用更方便的机器。通常把覆盖了软件的机器称为扩充机器或虚机器。

1.1.3推动操作系统发展的主要动力

• 不断提高计算机资源利用率：充分利用有限的硬件资源
• 方便用户：简化操作
• 器件的不断更新换代：为软件的发展提供了基础
• 计算机体系结构的不断发展：功能逐步强大

1.2 操作系统的发展过程

1.2.1无操作系统的计算机系统

• 人工操作方式
• 脱机输入/输出(Off-Line I/O)方式

1.2.2单道批处理系统

• 单道批处理系统
• 单道批处理系统的特征：自动性、顺序性、单道性

1.2.3多道批处理系统

• 基本概念：为了进一步提高资源的利用率和系统吞吐量，60年代中期引入了多道程序设计技术，形成了多道批处理系统。在该系统中， 用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
• 优势：提高CPU利用率；可提高内存和I/O设备利用率；增加系统吞吐量
• 多道批处理系统的优缺点：资源利用率高；系统吞吐量大；平均周转时间长；无交互能力。
• 多道批处理系统需要解决的问题：处理机管理问题；内存管理问题；I/O设备管理问题；文件管理问题；作业管理问题。
• 操作系统的定义：是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户的程序集合。

1.2.4分时系统

• 定义：分时操作系统是使一台计算机采用时间片轮转的方式同时为几个、几十个甚至几百个用户服务的一种操作系统。
• 产生原因：推动多道批处理系统形成和发展的主要动力，是提高资源利用率和系统吞吐量;推动分时系统形成和发展的主要动力，则是用户的需求；与多道批处理系统之间有截然不同的性能差别。
• 用户需求：人—机交互；共享主机；便于用户上机。
• 现实中的关键问题：及时接收；及时处理。
• 特征：多路性；独立性；及时性；交互性。

1.2.5实时系统

应用需求：实时控制、实时信息处理

实时任务

• 按照执行任务的周期性(周期性实时任务、非周期性实时任务)
• 按照截止时间的要求(硬实时任务、软实时任务)

实时系统与分时系统特征的比较

• 分时系统：多路性、独立性、交互性
• 实时系统：可靠性、及时性

1.2.6微机操作系统的发展

• 单用户单任务操作系统
• 单用户多任务操作系统
• 多用户多任务操作系统

1.3操作系统的基本特性

1.3.1并发(Concurrence)

并行与并发

• 并行性：两个或多个事件在同一时刻发生；
• 并发性：两个或多个事件在同一时间间隔内发生。
• 进程：通常的程序是静态实体(Passive Entity)，在多道程序系统中，它们是不能独立运行的，更不能和其它程序并发执行。在操作系统中引入进程的目的，就是为了使多个程序能并发执行。
• 线程：通常在一个进程中可以包含若干个线程，它们可以利用进程所拥有的资源。在引入线程的OS中，通常都是把进程作为分配资源的基本单位，而把线程作为独立运行和独立调度的基本单位。并把它视作现代操作系统的一个重要标致。

1.3.2共享(Sharing)

概念：系统中的资源可供内存中多个并发执行的进程(线程)共同使用

资源共享方式的分类

• 互斥共享方式：规定在一段时间内只允许一个进程(线程)访问该资源。
• 同时访问方式：允许在一段时间内由多个进程“同时”对它们进行访问。

并发和共享

• 临界资源/独占资源：在一段时间内只允许一个进程访问的资源。
• 操作系统的2个最基本特征：并发和共享是操作系统的两个最基本的特征，它们又是互为存在的条件。

1.3.3虚拟技术

概念

• 操作系统中的所谓“虚拟”，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。

分类

• 时分复用技术：虚拟处理机技术；虚拟设备技术
• 空分复用技术：虚拟磁盘技术；虚拟存储器技术

1.3.4异步性

1.4操作系统的主要功能

1.4.1处理剂管理功能

进程控制

• 为作业创建进程；
• 撤消已结束的进程；
• 控制进程在运行过程中的状态转换。

进程同步

• ① 进程互斥方式， 这是指诸进程(线程)在对临界资源进行访问时， 应采用互斥方式；
• ② 进程同步方式，指在相互合作去完成共同任务的诸进程(线程)间，由同步机构对它们的执行次序加以协调。

进程通信

• 由源进程利用发送命令直接将消息挂到目标进程的消息队列上，以后由目标进程利用接收命令从其消息队列中取出消息。

调度

• 作业调度的基本任务：从后备队列中按照一定的算法，选择出若干个作业，为它们分配其必需的资源(首先是分配内存)。 在将它们调入内存后，便分别为它们建立进程，使它们都成为可能获得处理机的就绪进程，并按照一定的算法将它们插入就绪队列。
• 进程调度的任务：从进程的就绪队列中选出一新进程，把处理机分配给它，并为它设置运行现场， 使进程投入执行。值得提出的是，在多线程OS中，通常是把线程作为独立运行和分配处理机的基本单位，为此，须把就绪线程排成一个队列，每次调度时，是从就绪线程队列中选出一个线程，把处理机分配给它。

1.4.2存储器管理功能

存储器管理的2种方式

• 静态：每个作业的内存空间在作业装入时确定；装入后不允许再申请新的内存空间，不允许 “移动”；
• 动态：每个作业所要求的基本内存空间在装入时确定，但允许在运行过程中，继续申请新的附加内存空间，也允许在内存中“移动”。

内存分配的机制中应具有这样的结构和功能：

• ① 内存分配数据结构， 该结构用于记录内存空间的使用情况， 作为内存分配的依据；
• ② 内存分配功能，系统按照一定的内存分配算法， 为用户程序分配内存空间；
• ③ 内存回收功能，系统对于用户不再需要的内存，通过用户的释放请求，去完成系统的回收功能。

地址映射

• 存储器管理必须提供地址映射功能，以将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。

内存扩充

• 请求调入功能
• 置换功能

1.4.3设备管理功能

主要任务

• 完成用户进程提出的I/O请求
• 为用户进程分配其所需的I/O设备
• 提高CPU和I/O设备的利用率
• 提高I/O速度
• 方便用户使用I/O设备

功能

• 缓冲管理：在I/O设备和CPU之间引入缓冲，可有效地缓和CPU和I/O设备速度不匹配的矛盾，提高CPU的利用率，进而提高系统吞吐量。常见的缓冲区机制有单缓冲机制、双缓冲机制，公用缓冲池机制。
• 设备分配：基本任务：根据用户进程的I/O请求、系统的现有资源情况以及按照某种设备分配策略，为之分配其所需的设备。如果在I/O设备和CPU之间，还存在着设备控制器和I/O通道时，还须为分配出去的设备分配相应的控制器和通道。设备使用完后，应立即由系统回收。
• 设备处理：设备处理程序又称为设备驱动程序。基本任务是实现CPU和设备控制器之间的通信，即由CPU向设备控制器发出I/O命令，要求它完成指定的I/O操作；反之由CPU接收从控制器发来的中断请求，并给予迅速的响应和相应的处理。

1.4.4文件管理功能

文件储存空间的管理

目录管理

文件的读/写管理和保护

• 文件的读/写管理
• 文件保护：① 防止未经核准的用户存取文件； ② 防止冒名顶替存取文件； ③ 防止以不正确的方式使用文件。

1.4.5用户接口

命令接口

• 联机用户接口
• 脱机用户接口

程序接口

图形接口

1.5OS结构设计

1.5.1传统的操作系统结构

• 操作系统是一个十分复杂的大型软件。为了控制该软件的复杂性，在开发OS时，先后引入了分解、模块化、 抽象和隐蔽等方法。开发方法的不断发展，促进了OS结构的更新换代。这里，我们把第一代至第三代的OS结构， 称为传统的OS结构，而把微内核的OS结构称为现代OS结构

无结构操作系统

• 在早期开发操作系统时，注意力放在功能的实现和获得高的效率上，缺乏首尾一致的设计思想。 此时的OS是为数众多的一组过程的集合，各过程之间可以相互调用，在操作系统内部不存在任何结构，也有人把它称为整体系统结构。

模块化OS结构

• 模块化结构：是基于“分解”和“模块化”原则来控制大型软件的复杂度的。将OS按其功能划分为若干个具有一定独立性和大小的模块。每个模块具有某方面的管理功能，如进程管理模块、存储器管理模块、I/O设备管理模块和文件管理模块等，并规定好各模块间的接口，使各模块之间能通过该接口实现交互，再进一步将各模块细分为若干个具有一定管理功能的子模块。
• 优点:提高了OS设计的正确性、 可理解性和可维护性;增强了OS的可适应性;加速了OS的开发过程。
• 缺点:在开始设计OS时，对模块的划分及对接口的规定并不精确，还可能存在错误，因而很难保证设计出的模块会完全正确， 这将使在把这些模块装配成OS时发生困难；从功能观点来划分模块时，未能将共享资源和独占资源加以区别 ，会使模块间存在着复杂的依赖关系,使OS结构变得不清晰。

分层式OS结构

• 有序分层的基本原则：每一层都仅使用其底层所提供的功能和服务，这样可使系统的调试和验证都变得容易 。
• 层次的设置：程序嵌套、运行频率、公用模块、用户接口

1.5.2客户/服务模式 C/S模式

客户/服务器模式的组成

• 客户机
• 服务器
• 网络系统

客户/服务器之间的交互

• 客户发送请求消息
• 服务器接收消息
• 服务器回送消息
• 客户机接收消息

客户/服务器模式的优点

• 数据的分布处理和存储。
• 便于集中管理。
• 灵活性和可扩充性。
• 易于改编应用软件。　

1.5.3微内核OS结构

微内核操作系统的基本概念

• 提供各种服务的一组服务器(进程)
• 内核

特点

• 足够小的内核：① 实现与硬件紧密相关的处理；② 实现一些较基本的功能；③ 负责客户和服务器之间的通信。
• 基于客户/服务器模式
• 应用“机制与策略分离”原理：微内核操作系统中，通常将机制放在OS的微内核中。正因为如此，才有可能将内核做得很小。
• 采用面向对象技术

微内核的基本功能

• 进程(线程)管理
• 低级存储器管理
• 中断和陷入处理

微内核操作系统的优点

• 提高了系统的可扩展性
• 增强了系统的可靠性
• 可移植性
• 提供了对分布式系统的支持
• 融入了面向对象技术

微内核系统存在的问题

• 较之早期OS，微内核OS的运行效率有所降低

本章小结

• 1.操作系统的作用是什么？
• 2.操作系统的设计目标是什么？
• 3.脱机I/O方式与人工操作方式有什么进步？
• 4.什么是批处理？多道批处理与单道批处理相比有什么好处？
• 5.多道批处理需要解决哪些问题？为什么？
• 6.什么是分时系统？与批处理系统有什么差别？
• 7.什么是实时系统？与分时系统有什么差别？
• 8.微机操作系统经过哪几个阶段？WINDOWS是属于哪一种？
• 9.什么是进程？并发与并行有什么不同？
• 10.什么是共享？有哪两种共享方式？
• 11.为什么说并发和共享是操作系统的基本特征？
• 12.模块化操作系统有什么优缺点？
• 13.什么是客户/服务器模式？
• 14.微内核操作系统有哪两部分构成？功能是什么？
• 15.微内核的基本功能是什么？
• 16.微内核操作系统有什么优缺点？

第二章 进程管理

2.1进程的基本概念

2.1.1程序的顺序执行及其特征

• 程序的顺序执行：仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。
• 程序顺序执行时的特征：顺序性、封闭性、可在线性。

2.1.2前驱图

2.1.3程序的并发执行及其特征

程序的并发执行

程序并发执行时的特征

• 间断性：相互制约导致并发程序具有“执行－暂停－执行”的规律
• 失去封闭性：因为共享资源，程序相互间会产生影响
• 不可再现性：因为失去了封闭性，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果可能不同。

2.1.4进程的特征与状态

进程的特征和定义(通常的程序不能参与并发，因此引入进程概念 )

• 结构特征：程序段、相关数据段、PCB构成进程实体
• 动态性：进程实体有一定的生命期
• 并发性：多个进程实体同存于内存中，在一段时间里同时进行。
• 独立性：独立运行、独立分配资源和独立接收调度的基本单位。
• 异步性：按各自独立的、不可预知的速度推进。

进程的定义

• 进程是程序的一次执行。
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
• 传统OS进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的三种基本状态

• 就绪(Ready)状态：只要获得CPU就可执行
• 执行状态：占用CPU
• 阻塞状态：正在执行的进程由于发生某种事件而暂时无法执行时，便放弃CPU而处于暂停状态.

挂起状态(三种状态以外的新状态)

引入挂起状态的原因

引入挂起状态的原因
终端用户的请求。
父进程请求。
负荷调节的需要。
操作系统的需要。

进程状态的转换

• 活动就绪→静止就绪。
• 活动阻塞→静止阻塞。
• 静止就绪→活动就绪。
• 静止阻塞→活动阻塞。

创建状态/终止状态

• 创建状态：创建过程一般包括两个步骤：为一个新进程创建PCB和填写必要的管理信息；把该进程转成就绪状态并插入就绪队列中。当新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必须的资源和其他信息，如主存资源尚未分配等。此时，进程已经拥有了自己的PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行。该状态即为创建状态。
  2.终止状态：进程的终止包括两个步骤：首先等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返回系统。如果进程到达了自然结束点，或出现了无法克服的错误，或被操作系统所终结，或被其他有终止权的进程所终结，经进入终止状态。虽然进入终止状态的进程不能再执行，但是在操作系统中依然保留一个记录，其中保持状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。

2.1.5进程控制块

进程控制块的作用

• 使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。
• OS是根据PCB来对并发执行的进程进行控制和管理的。

进程控制块中的信息

• 进程标识符：内部标识符、外部标识符
• 处理器状态
• 进程调度信息
• 进程控制信息

进程控制块的组织方式

• 链接方式
• 索引方式

2.2进程控制

• 基本功能：创建进程、终止进程、进程状态转换
• 由OS内核中的原语来实现
• 原语：由若干条指令构成，称原子操作，不可被打断。在管态下运行，常驻内存。

2.2.1进程的创建

进程图

引起创建进程的事件

• 用户登录：分时系统，用户键入登录命令。
• 作业调度：批处理系统，某作业被调度。
• 提供服务：操作系统为满足用户进程的需求。
• 应用请求：由用户进程自己创建新进程，并发执行，以提高效率。

进程的创建(Creation of Progress)

• 申请空白PCB。
• 为新进程分配资源。
• 初始化进程控制块。
• 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列。

2.2.2进程的终止

引起进程终止(Termination of Process)的事件

• 正常结束
• 异常结束：越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障
• 外界干预：操作员或操作系统干预、父进程请求、父进程终止

进程终止的过程

• 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
• 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
• 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。
• 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。
• 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。

2.2.3进程的阻塞和唤醒

引起进程阻塞和唤醒的事件

• 请求系统服务：系统不能立即满足进程要求，进入阻塞，满足后唤醒
• 启动某种操作：进程必须等该操作完成后才能继续执行，进入阻塞，完成后唤醒
• 新数据尚未到达：未到达阻塞，到达后唤醒
• 无新工作可做：无工作阻塞，新工作出现后唤醒

进程的阻塞过程

• 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。 最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。

进程的唤醒过程

• 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。

2.2.4进程的挂起与激活

• 进程的挂起：当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起， 系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。
• 进程的激活过程：当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。 激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。

2.3进程同步

2.3.1进程同步的基本概念

• 同步：并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。

两种形式的制约关系

• 资源共享关系：（进程间接制约）：需互斥地访问临界资源。
• 相互合作关系：（进程直接制约）

临界资源：（一次仅允许一个进程访问的资源）

• 引起不可再现性是因为临界资源没有互斥访问。

producer()
{
    produce an item in nextp;
    while(counter==n) do no-op;
     buffer[in] = nextp;
     in = （in + 1）% n;
     counter++；         
}
consumer()
{
    while(counter==0) do no-op;
    nextc = buffer[out];
    out = （out + 1）% n;
    counter--;
    consumer the item in nextc;
}

临界区(critical section)

同步机制应遵循的规则

• 空闲让进
• 忙则等待
• 有限等待：应保证为有限等待，不会产生死等。
• 让权等待：不能进入临界区的执行进程应放弃CPU执行权。

2.3.2信号量机制

1.整型信号量

• 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为：

        wait(S): while S≤0 do no-op
        S∶=S-1;
        signal(S):         S    ∶=S+1;

2.记录型信号量

    在整型信号量机制中的wait操作，只要是信号量S≤0， 就会不断地测试。因此，该机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：

typedef struct{
    int value;
    struct process_control_block *list;
} semaphore;

相应地，wait(S)和signal(S)操作可描述为：

wait(semaphore *s)
{
     s->value--;
     if(s->value < 0)
          block(s->list);
}
signal(s)
{
    s->value++;
    if(s->value<=0)
        wakeup(s->list);
}

在记录型信号量机制中，s->value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为s->value ∶= s->value -1； 当s->value ＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表s->l中。可见，该机制遵循了“让权等待”准则。 此时s->value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故s->value ∶ = s->value +1操作表示资源数目加1。 若加1后仍是s->value ≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将s->l链表中的第一个等待进程唤醒。如果s->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量

3.AND型信号量

在两个进程中都要包含两个对Dmutex和Emutex的操作，即

process A:           process B:
wait(Dmutex);    wait(Emutex);
wait(Emutex);   wait(Dmutex);

若进程A和B按下述次序交替执行wait操作：

process A: wait(Dmutex); 于是Dmutex=0
process B: wait(Emutex); 于是Emutex=0
process A: wait(Emutex); 于是Emutex=-1 A阻塞
process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。 由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作， 即Swait(Simultaneous wait)定义如下：

Swait(S1, S2, …, Sn)
    if Si≥1 and … and Sn≥1 then
        for i∶ =1 to n do
        Si∶=Si-1;
        endfor
    else
     place the process in the waiting queue associated with the first Si found   with Si＜1, and set the program count of this process to the beginning of Swait operation
    endif
Ssignal(S1, S2, …, Sn)
      for i∶   =1 to n do
      Si=Si+1;
      Remove all the process waiting in the queue associated with Si into the ready queue.
  endfor; 

2.3.3信号量的应用

利用信号量实现进程互斥

利用信号量实现进程互斥的进程可描述如下：

process1(){
    while(…)    {
           wait(mutex);
           critical section;
           signal(mutex);
           remainder seetion;
     }
}
process2(){
    while(…)    {
           wait(mutex);
           critical section;
           signal(mutex);
           remainder seetion;
     }
}
main(){
semaphore mutex = 1;
cobegin
 process1(); process2();
coend;
}

利用信号量实现前驱关系

 P1{S1;signal(a); signal(b); }
 P2{S2;wait(a); signal(c); signal(d); }
 P3{wait(b); S3; signal(e); }
 P4{wait(c); S4; signal(f);}
 P5{wait(d); S5; signal(g); }
 P6{wait(e); wait(f); wait(g); S6; }
main(){
semaphore a=0,b=0,c=0,d=0,e=0,f=0,g=0;
cobegin
   P1(); P2(); P3(); P4(); P5(); P6();
coend;
}

2.4经典的进程同步问题

2.4.1生产者-消费者问题

利用记录型信号量解决生产者—消费者问题

const int n = 20;
semaphore mutex =1, empty=n,full = 0;
item  buffer[n];
int int=0,out =0;
proceducer()
{
     while(…)
     {
         producer an item nextp;
         wait(empty);
         wait(mutex);
         buffer[in] = nextp;
         in = (in + 1)%n;
         signal(mutex);
         signal(full);
     }     
}
consumer()
{
     while(…)
     {
        wait(full);
         wait(mutex);
         nextc  = buffer[out] ;
         out = (out + 1)%n;
         signal(mutex);
         signal(empty);
     }     
}
main(){
cobegin
   consumer(); proceducer(); 
coend;
}

2. 利用AND信号量解决生产者—消费者问题

const int n = 20;
semaphore mutex =1, empty=n,full = 0;
item  buffer[n];
int int=0,out =0;
proceducer()
{
     while(…)
     {
         producer an item nextp;
         Swait(empty,mutex);
         wait(mutex);
         buffer[in] = nextp;
         in = (in + 1)%n;
         Ssignal(full,mutex);
      }     
}
consumer()
{
     while(…)
     {
        Swait(full,mutex);
         nextc  = buffer[out] ;
         out = (out + 1)%n;
         Ssignal(empty,full);
       }     
}
main(){
cobegin
   consumer(); proceducer(); 
coend;
}

2.4.2哲学家进餐问题

1.利用记录型信号量解决哲学家进餐问题

所有信号量均被初始化为1， 第i位哲学家的活动可描述为：     
      while(…)
        {
     wait(chopstick［i］);
        wait(chopstick［(i+1) mod 5］);
            …
     eat;
                             …
     signal(chopstick［i］);
     signal(chopstick［(i+1) mod 5］);
                    …
     think;
         }

问题：所有哲学家同时都拿起左边的筷子，将出现死锁。

2.利用AND信号量机制解决哲学家进餐问题

Var chopsiick array ［0, …, 4］ of semaphore∶   =(1,1,1,1,1);
 semaphore chopsiick[5] = {1,1,1,1,1};
    while(…)
    {
        think;
        Sswait(chopstick［(i+1) mod 5］, chopstick ［i］);
        eat;
        Ssignal(chopstick ［(i+1) mod 5］, chopstick ［i］);
     }

2.4.3读者-写者问题

• 一个数据文件或记录可被多个进程共享。
• 只要求读文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。
• 允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象
• “读者—写者问题”是保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。

利用记录型信号量解决读者-写者问题

读者-写者问题可描述如下：
semaphore rmutex = 1, wmutex = 1;
int readcount = 0;
Reader(){
       wait(rmutex)
       if(readcount==0)
             wait(wmutex);
       readcount++;
       signal(rmutex);
       perform read operation;
       wait(rmutex);
       readcount--;
        if(readcount==0)
             signal (wmutex);
        signal(rmutex);
}
Writer(){
       wait(wmutex);
        perform write operation;
        signal(wmutex);
}

利用记录型信号量解决读者-写者问题

Var RN integer;
    L, mx:semaphore∶   =RN,1;
   begin
    parbegin
     reader:begin
        repeat
         Swait(L,1,1);
         Swait(mx,1,0);
           …
         perform read operation;
           …
Ssignal(L,1);
        until false;
       end
     writer:begin
         repeat
          Swait(mx,1,1; L,RN,0);
          perform write operation;
          Ssignal(mx,1);
        until false;
       end
    parend
  end 

2.5 管程机制

2.5.1管程的定义

• 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

2.5.2管程的组成

• ①管程的名称；
• ② 局部于管程内部的数据结构的说明；
• ③ 对该数据结构进行操作的一组过程；
• ④ 对局部于管程的共享数据设置初始值的语句。

2.5.3管程的特点

• 模块化:一个管程是一个基本程序单位，可以单独编译
• 抽象数据类型:管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码
• 信息掩蔽:管程是半透明的，管程中的过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的

2.5.4管程和进程的区别

• 1.进程定义自己的PCB，管程定义公共数据结构
• 2.进程执行自己的操作，管程执行同步操作
• 3.设置进程是为并发执行，设置管程是为共享资源的互斥访问。
• 4.进程为调用者，管程为被调用者，即服务者。
• 5.进程之间可并发，管程和调用者不能并发。
• 6.进程可以创建、消亡，管程是系统管理模块，不会消亡。

2.5.5条件变量

• Wait操作 阻塞 如X.wait用来将执行进程挂到与条件变量x相应的等待队列上。
• Signal操作 唤醒 如X.signal用来唤醒与条件变量x相应的等待队列上的一个进程。

2.5.6利用管程解决生产者-消费者问题

• put(item)过程。 生产者利用该过程将自己生产的产品投放到缓冲池中， 并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。
• get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品， 消费者应等待。

void producer()
{
          produce an item in nextp;
           PC.put(item);
}
void  consumer()
{
          PC.get(item);
           consume the item in nextc;
}

2.6 进程通信

2.6.1进程通信的类型

• 进程通信可以在进程之间传送大量的数据。
• 信号量方式：低级通信
• 进程通信：高级通信

1. 共享存储器系统(Shared-Memory System)

• 基于共享数据结构的通信方式。
• 基于共享存储区的通信方式。

2.消息传递系统(Message passing system)

• 不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。

3.管道(Pipe)通信

• 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。

2.6.2消息传递通信的实现方法

直接通信方式

• 这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：
• Send(Receiver, message); 发送一个消息给接收进程；
• Receive(Sender, message); 接收Sender发来的消息；

间接通信方式

• 可以实现非实时通信
• 优点：在读/写时间上的随机性
• 写进程――> 信箱（中间实体）――>读进程
• 信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱， 还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。
• 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。

         Send(mailbox, message); 将一个消息发送到指定信箱；
         Receive(mailbox, message); 从指定信箱中接收一个消息； 

信箱的分类

• 私用信箱：用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。 当拥有该信箱的进程结束时，信箱也随之消失。
• 公用信箱：它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。
• 共享信箱：它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。

信箱通信存在的关系

• (1) 一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。
• (2) 多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/server interaction)。
• (3) 一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。
• (4) 多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。

2.6.3消息传递系统实现中的若干问题

通信链路(communication link)

根据通信链路的连接方法，又可把通信链路分为两类：

• ① 点—点连接通信链路，这时的一条链路只连接两个结点(进程)；
• ② 多点连接链路，指用一条链路连接多个(n＞2)结点(进程)。

而根据通信方式的不同，则又可把链路分成两种：

• ① 单向通信链路，只允许发送进程向接收进程发送消息；
• ② 双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。

消息的格式

进程同步方式

• 1.发送和接收进程阻塞（汇合）：用于紧密同步，无缓冲区时。
• 2.发送进程不阻塞，接收进程阻塞（多个）：相当于接收进程（可能是多个）一直等待发送进程，如：打印进程等待打印任务。
• 3.发送/接收进程均不阻塞：一般在发、收进程间有多个缓冲区时。例如，进程之间的消息队列，发送进程可连续的向消息队列发消息，接收进程可连续地从消息队列接收消息。

2.6.4 消息缓冲队列通信机制

消息缓冲队列通信机制中的数据结构

消息缓冲队列通信机制中的数据结构

• 消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：

type message buffer=record
               sender; 发送者进程标识符
       size; 消息长度
               text; 消息正文
               next; 指向下一个消息缓冲区的指针
         end 

• PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCB中应增加的数据项可描述如下：

                type processcontrol block=record
                                                    …
                        mq; 消息队列队首指针
                        mutex; 消息队列互斥信号量
                        sm; 消息队列资源信号量
                     …
                        end 

发送原语

 procedure send(receiver, a)
     begin
        getbuf(a.size,i);                         根据a.size申请缓冲区；
        i.sender∶   =a.sender;  将发送区a中的信息复制到消息缓冲区之中；
        i.size∶   =a.size;
        i.text∶   =a.text;
        i.next∶   =0;
       getid(PCB set, receiver.j);   获得接收进程内部标识符；
       wait(j.mutex);
       insert(j.mq, i);   将消息缓冲区插入消息队列；
       signal(j.mutex);
       signal(j.sm);
    end 

接收原语描述如下：

procedure receive(b)
   begin
    j∶   =internal name; j为接收进程内部的标识符；
    wait(j.sm);
    wait(j.mutex);
    remove(j.mq, i); 将消息队列中第一个消息移出；
    signal(j.mutex);
    b.sender∶   =i.sender; 将消息缓冲区i中的信息复制到接收区b;
    b.size∶   =i.size;
    b.text∶   =i.text;
  end

2.7 线程

2.7.1线程的基本概念

线程的引入

• 减少并发执行时的时空开销，进程的创建、撤消、切换较费时空，因它既是调度单位，又是资源拥有者。
• 线程是系统独立调度和分派的基本单位，其基本上不拥有系统资源，只有少量资源（IP，寄存器，栈），但共享其所属进程所拥有的全部资源。

线程和进程的比较

• 线程具有许多传统进程具有的特征，所以，又称为轻型进程或进程元，相应地把传统进程称为重型进程，传统进程相当于只有一个线程的任务。在引入了线程的操作系统中，通常一个进程都拥有若干个线程，至少也有一个线程。
• 【调度】在传统的操作系统中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位,把传统进程的两个属性分开，使线程基本上不拥有资源，这样线程便能轻装前进，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。
• 【并发性】在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可以并发执行，使得操作系统具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量。
• 【拥有资源】不论是传统的操作系统，还是引入了线程的操作系统，进程都可以拥有资源，是系统中拥有资源的一个基本单位。一般而言，线程自己不拥有系统资源（也有一点必不可少的资源），但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O设备等，可以提供该进程中的所有线程所共享。
• 【系统开销】在创建或撤销进程时，系统都要为之创建和回收进程控制块，分配或回收资源，如内存空间和I/O设备等，操作系统所付出的开销明显大于线程创建或撤销时的开销。类似地，在进程切换时，涉及到当前进程CPU环境的保存及新被调度运行进程CPU环境的设置，而线程的切换则仅需要保存和设置少量寄存器内容，不涉及存储器管理方面的操作，所以就切换代价而言，进程也是远高于线程的。此外，由于一个进程中的多个线程具有相同的地址空间，在同步和通信的实现方面线程也比进程容易。在一些操作系统中，线程的切换、同步和通信都无须操作系统内核的干预。

线程的属性

• 轻型实体
• 独立调度和分派的基本单位
• 可并发实体
• 共享进程资源

线程的状态

• 状态参数：寄存器状态、堆栈、运行状态、优先级、线程专有存储器、信号屏蔽
• 线程的运行状态：运行、就绪和阻塞

线程的创建和终止

• 每一个进程至少有一个主执行线程。用户根据需要在应用程序中创建其它线程，多个线程并发地运行于同一个进程中。一个进程中的所有线程使用该进程的系统资源，所以线程间的通讯非常方便。
• 终止：操作结束、错误终止。不立即释放资源，可恢复执行。

多线程OS中的进程

• 拥有系统资源的基本单位
• 可包括多个线程
• 不再是一个可执行的实体。成为线程的容器。

第三章 处理剂调度与死锁

3.1处理剂调度的层次

3.1.1高级调度

作业和作业步

• 作业(Job)：包含通常的程序和数据，配有一份作业说明书，系统根据说明书来对程序的运行进行控制。
• 作业步(Job Step)：把每一个加工步骤称为一个作业步。例如，一个作业可分成3个作业步：① “编译”作业步，通过执行编译程序对源程序进行编译，产生若干个目标程序段；② “连结装配”作业步，将“编译”作业步所产生的若干个目标程序段装配成可执行的目标程序；③ “运行”作业步，将可执行的目标程序读入内存并控制其运行。
• 作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，形成了处理作业流。

作业控制块JCB(Job Control Block)

• 是作业在系统中存在的标志，保存了系统对作业进行管理和调度所需的全部信息。包含：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。

作业调度

• 决定接纳多少个作业
• 决定接纳那些作业

3.1.2低级调度

功能

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

进程调度中的三个基本机制

• 排队器：将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地找到它。
• 分派器(分派程序)：把由进程调度程序所选定的进程，然后进行上下文切换，将处理机分配给它。
• 上下文切换机制：当处理机进行切换时，会发生对上下文的切换操作。

进程调度方式

• 非抢占方式(Nonpreemptive Mode)：这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。在要求比较严格的实时系统中，不宜采用这种调度方式。
• 抢占方式(Preemptive Mode)：优先权原则(允许优先权高的新到进程抢到站当前进程的处理机)、短作业优先原则(转作业可以抢占当前教程作业的处理机)、时间片原则(各进城安时间片轮流运行，当一个时间用完后便停止该进程的执行而重新进行的度)。

可能引起进程调度的因素可归结为如下几个

• 正在执行的进程执行完毕，因发生某事件而不能再继续执行；
• 执行中的进程因提出I/O请求而暂停执行；
• 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语

3.1.3中级调度

• 目的：主要目的是为了提高内存利用率和系统吞吐量。

3.2调度队列模型和调度准则

3.2.1调度队列模型

仅有进程调度的调度队列模型：每个进程执行时可能出现的三种情况

• 任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态
• 任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾
• 在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列

具有高级和低级调度的调度队列模型：与上一模型存在如下区别

• 就绪队列的形式：最常用的就绪队列形式是优先权队列。
• 设置多个阻塞队列：对于小型系统，可以只设置一个阻塞队列。在大、中型系统中设置若干个阻塞队列，每个队列对应某一种进程阻塞事件。

同时具有三级调度的调度队列模型

3.2.2选择调度方式和调度算法的若干准则

面向用户的准则

• 周转时间(从作业被提交给系统开始，到作业完成为止的这段时间间隔，包括在后备队列等待调度时间、在就绪队列上的等待时间，在CPU上的执行时间、I/O操作完成时间)短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。
• 响应时间快：常把响应时间的长短用来评价分时系统的性能，这是选择分时系统中进程调度算法的重要准则之一。
• 截止时间的保证，评价实时系统性能的重要指标
• 优先权准则：在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。

面向系统准则

• 系统吞吐量高：用于评价批处理系统性能的另一个重要指标，因而是选择批处理作业调度的重要准则。
• 处理机利用率好。
• 各类资源的平衡利用。

3.3调度算法

3.3.1 先来先服务和短作业(进程)优先调度算法

先来先服务调度算法 FCFS

* 特点：有利于长作业（进程），而不利于短作业（进程）

短作业(进程)优先调度算法 SJ(P)F

特点：是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
缺点：对长作业不利，没有考虑作业的紧迫程度，不一定能真正做到短作业优先调度

3.3.2高优先权优先调度算法

优先权调度算法

• 非抢占式：主要用于批处理系统中；也可用于对实时性要求不严的实时系统中。
• 抢占式：执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。

优先权的类型

静态优先权(创建进程时确定，在运行期间保持不变)，依据

• 进程类型
• 进程对资源的需求
• 用户要求

动态优先权

高响应比优先调度算法

• 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
• 当要求服务的时间相同时，作业的优先权决定于等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
• 对于长作业，优先级可以随等待时间的增加而提高，当等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。

3.3.3 基于时间片的轮转调度算法

• 时间便轮转法：可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。
• 多级反馈队列调度算法(不必预先知道进程执行的所需时间)

多级反馈队列调度算法的性能

• 终端型作业用户。作业较小，基本在第一时间片完成。
• 短批处理作业用户。 周转较短。
• 长批处理作业用户。不必担心长期得不到处理。

3.4实时调度

3.4.1实现实时调度的基本条件

• 提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级。
• 系统处理能力强
• 采用抢占式调度机制：当一个优先权更高的任务到达使允许将当前任务暂时挂起，而令优先权更高的任务立即投入运行。
• 具有快速切换机制：对外部中断快速响应能力、快速的任务分配能力

3.4.2实时调度算法的分类

非抢占式调度算法

• 非抢占式轮转调度算法 !
• 非抢占式优先调度算法

抢占式调度算法

• 基于始终中断的抢占式优先权调度算法
• 立即抢占(Immediate Preemption)的优先权调度算法

3.4.3常用的几种实时调度算法

最早截止时间优先即EDF算法

• 非抢占式调度方式用于非周期实时任务
• 抢占式调度方式用于周期实时任务
• 详细描述：有两个周期性任务，任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0、20、40、…；任务A的最后期限为20、40、60、…；任务B的到达时间为0、50、100、…；任务B的最后期限为50、100、150、…(注：单位皆为ms)。

最低松弛度优先即LLF(Least Laxity First)算法

• 该算法主要用于可抢占调度方式中。
• 详细描述：该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级.例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，调度程序必须在100 ms之前调度执行，该任务的松弛度为100 ms。又如，另一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。

3.4.4优先级倒置

问题由来

• 首先假设现在有三个任务P1， P2， P3（优先级分别是：３,２,１）；他们的优先级关系是：P3 ＜P2＜P1并且P1和P3需要访问共享资源。当一个P1任务通过互斥机制（mutex）访问共享资源时，如果该mutex已被一个低优先级任务（任务P3）占用（lock），那么P1也只好阻塞了 。
• 这个P3任务正在访问共享资源时,可能又被其他一些中等优先级的任务（任务P2）抢先了，只有等待P2执行结束，P3才能执行，释放共享资源，然后P1再执行。任务P1（优先级比任务P2高）除了需要的共享资源外运行任务的条件都满足了，却因为P2的运行被阻塞。这样系统的实时性得不到保证，这就是优先级倒置问题。

解决方法

• 方法1：将程序代码进行适当的组织安排，避免优先级倒置的发生。
• 方法2：将占有互斥体的进程优先级提升到所有正在等待该互斥体的进程优先级的最高值。
• 方法3：每个互斥体都被分配一个优先级，该优先级通常与所有可以拥有该互斥体的进程中的最高优先级相对应。当优先级较低的进程占有互斥体后，该进程的优先级被提升到该互斥体的优先级。

3.5产生死锁的原因和必要条件

3.5.1产生死锁的原因

竞争资源

• 1) 可剥夺和非剥夺性资源。可剥夺：可被优先级高的剥夺。
• 2) 竞争非剥夺性资源。
• 3) 竞争临时性资源

进程推进顺序不当引起死锁

3.5.2产生死锁的必要条件

• 互斥条件 ：某资源只能由一个进程占用。
• 请求和保持条件：占有一个资源，请求新资源，但不放弃占有的资源，而新资源已被其它进程占用。
• 不剥夺条件 ：已获得的资源不能被剥夺，只能靠自己释放。
• 环路等待条件 ：存在一个进程—资源的环形链。

3.5.3处理死锁的基本方法

• (1) 预防死锁：通过破坏死锁的四个必要条件中的一个或多个，来预防死锁。
• (2) 避免死锁：在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁。
• (3) 检测死锁：通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。
• (4) 解除死锁：当检测机构检测到系统中发生死锁时，将进程从死锁中解脱出来。

3.6预防死锁的方法

3.6.1预防死锁：使上述条件中的2、3、4有一个不成立即可

摈弃“请求和保持“条件

• 优点：简单，易于实现且很安全
• 缺点：资源严重被浪费。
• 实现原理：系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。若申请的某类资源足够，则把所有资源分配给该进程，这样摒弃了“请求”条件。若资源不够，即使其它资源空闲，也不分配该进程，而让进程等待。由于在该进程等待期间，它并未占任何有资源，因而也摒弃了“保持”条件。

摒弃“不剥夺”条件

• 缺点：实现复杂，延长了进程的周转时间，增加了系统开销，降低了系统的吞吐量。
• 实现原理：在采用这种方法时，进程逐个地提出对资源的要求。当一个已经保持了某些资源的进程，再提出新的资源请求而不能得到满足时，必须释放它已经保持了的所有资源，待以后需要时再申请，从而摒弃了“不剥夺”条件。

摒弃“环路等待”条件

• 优点：资源利用率，系统吞吐量比较高。
• 缺点：限制了新类型设备的增加；有时造成资源浪费；增加了限制条件，影响用户简单、自主地编程。
• 在这种方法中，系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号的次序提出申请。这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待条件”。

3.6.2系统安全状态

安全状态

• 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。
• 若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。

由安全状态向不安全状态的转换

• 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

3.6.2利用银行家算法避免死锁

银行家算法中的数据结构

• 可用资源向量Available
• 最大需求矩阵Max
• 分配矩阵Allocation
• 需求矩阵Need

银行家算法

• 设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
• 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
• 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]=Available[j]-Requesti[j];
Allocation[i,j]=Allocation[i,j]+Requesti［j］;
Need［i,j］=Need［i,j］-Requesti［j］;

• 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法

• 设置两个向量：① 工作向量Work: 表示系统可供进程继续运行所需的各类资源数目,它有m个元素，开始时，Work=Available; ② Finish: 表示系统是否有足够的资源分配给进程，使之运行完成。开始时,Finish[i]=false; 当有足够资源分配给进程时， 再令Finish[i]=true。
• 从进程集合中找到一个能满足下述条件的进程：① Finish[i]=false; ② Need[i,j]≤Work[j]；若找到，执行步骤(3)， 否则，执行步骤(4)。
• 当进程Pi获得资源后，可顺利执行至完成，并释放分配给它的资源，故应执行：

Work［j］=Work［j］+Allocation［i,j］;
Finish［i］=true;
go to step 2; 

• 所有进程的Finish[i]=true，表示系统处于安全状态；否则，系统处于不安全状态。

3.7死锁的检测与解除

3.7.1死锁的检测

• ①保存有关资源的请求和分配信息。
• ②提供一种算法，以利用这些信息来检测系统是否已进入死锁。

资源分配图(Resource Allocation Graph)

死锁定理

• 在资源分配图中，找出一个既不阻塞又非独立的进程Pi，在顺利的情况下，Pi可获得所需资源而继续执行，直至完成，再释放占有的全部资源。相当于消去Pi的请求边和分配边。
• P1释放资源后，可使P2获得资源而继续运行。直至进程P2完成，释放全部资源。
• 在一系列的简化后，若能消去所有的边，使所有的进程节点都成为孤立节点，则称该图是可完全简化的。
• 否则不是完全简化的。

死锁检测中的数据结构

1. 死锁检测中的数据结构
2. 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。
3. 把不占用资源的进程记入L表中,即Li∪L。
4. 从进程集合中找Requesti≤Work的进程，做如下处理：将其资源分配图简化，释放出资源，增加工作向量Work=Work+Allocationi，并将它记入L表中。若不能把所有进程都记入L表中， 便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。

3.7.2死锁的解除

剥夺资源

撤销进程

第四章 存储器管理

4.1存储器的层次结构

4.1.1多级存储器结构

CPU寄存器

4.1.2主存储器与寄存

• 主存储器：用来存放进程运行时的程序和数据。
• 寄存器：CPU中的部件，用来存放运算器的中间结果，容量很小，速度最快。一般只有几十个到上百个。

4.1.3高速缓存和磁盘缓存

• 高速缓存：根据程序执行的局部性原理（即程序在执行将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分），将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可提高程序执行速度。
• 磁盘缓存：由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。

4.2程序的装入和链接

4.2.1程序的装入

绝对装入方式(Absolute Loading Mode)

可重定位装入方式(Relocation Loading Mode)

动态运行时装入方式(Denamle Run-time Loading)

4.2.2程序的链接

静态链接方式(Static Linking) 需解决的问题

• 对相对地址进行修改。
• 变换外部调用符号。

装入时动态链接(Loadtime Dynamic Linking) 优点

• 便于修改和更新
• 便于实现对目标模块的共享

运行时动态链接(Run-time Dynamic Linking)

4.3连续分配方式

4.3.1单一连续分配

• 局限性：单用户、单任务

4.3.2固定分区分配

划分分区的方法

• 特点：有n个分区，可以同时装入n个作业/任务
• 分区大小：相等(缺乏灵活性)、不相等(利用率更高)
• 内存分配：蒋分区的大小排序，并将其地址、分配标识符作记录
• 特点：简单、有碎片

内存分配

4.3.3动态分区分配

分区分配中的数据结构

分区分配算法

首次适应算法FF

• 要求：分区按低址――高址链接
• 特点：找到第一个大小满足的分区，划分出一块给申请者，余下的仍留空闲链中。低址内存使用频繁。

循环首次适应算法

• 从1中上次找到的空闲分区的下一个开始查找，并循环查找。
• 特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。

最佳适应算法

• 该算法总是把既能满足要求，又是最小的空闲分区分配给作业。该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。但每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。

最坏适应算法

• 按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中分配（不能满足需要则不分配）。很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。

##### 快速适应算法
将空闲分区按大小分类，为大小相同的分区建立空闲分区链表； 建立一张管理索引表，指向不同类型空闲分区链表的表头指针； 查找能满足进程需求的最小空闲区链表，取下第一块空闲区整体分配；
特点：能保留大的空闲区；分类搜索算法，存在多个空闲分区链表 以空间换时间，但是分区回收时较复杂。

分区分配操作

1）分配内存

2）回收内存

• 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一：
• 回收区与插入点的前一个分区相邻接，此时应将回收区与插入点的前一分区合并，不再为回收分区分配新表项，而只需修改F1区的大小；
• 回收分区与插入点的后一分区F2相邻接。此时也将两区合并形成新的空闲区，但用回收区的首址作为新空闲区的首址，大小为两者之和；
• 回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的首址，取消F2的表项；
• 回收区既不与F1邻接，也不与F2邻接，这时应为回收区单独建立一新表项。填写回收区的首址和大小，并根据其首址，插入到空闲链中的适当位置。

4.3.4伙伴系统

• 分区大小为2^k(l≤ k ≤ m)，2^l表示最小分区大小， 2^m表示最大分区大小(初始为整个可分配内存的大小)；

4.3.5哈希算法

• 构造哈希函数，建立分区大小与空闲区表表头指针之间的对应关系，形成哈希表；
• 分区分配时，根据所需分区的大小，通过哈希函数的计算，得对应空闲区表的头指针，实现最佳分配。

4.3.6可重定位分区分配

动态重定位的引入

• 在连续分配方式中，必须把一个系统顺序或用户程序，装入到一连续的内存空间中。如果在系统中有若干个小的分区，其总容量要装入的程序，但由于他们不相邻接，使该程序不能被装入内存。紧凑后，须对移动后的程序和数据进行重定位

动态重定位的实现

• 在该方式中，将程序中的相对地址转换为物理地址的工作，被推迟到程序指令真正要执行时进行。因此，允许作业在运行过程中在内存中移动的技术，必须获得硬件地址变换机构的支持。即在系统中一个重定位寄存器，用它来装入（存放）程序在内存中的起始地址。

动态重定位分区分配算法

• 动态重定位分区分配算法与动态分区分配算法基本上相同；差别仅在于：在这种分配算法中，增加了“紧凑”功能，通常是在找不到足够大的空闲分区来满足用户需求时，进行紧凑。

4.3.7对换(Swapping)

对换

• 内容：是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存
• 作用：对换是提高内存利用率的有效措施。

对换需要系统实现的功能

• 对对换空间的管理；
• 进程的换出；
• 进程的换入。

对换空间的管理

• 配置相应的数据结构，以记录外存的使用情况

进程的换出与换入

进程的换出

• 原因：每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。
• 过程：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。

进程的换入

• 系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。

4.4基本分页存储管理方式

4.4.1页面和页表

页面与页表

• 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0＃块、1＃块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。
• 页表的结构：分页转换功能由驻留在内存中的表来描述，该表称为页表（page table），存放在物理地址空间中。页表可看做简单的若干个物理地址数组。线性到物理地址的映射功能可以简单地看做进行数组查找。线性地址的高位构成这个数组的索引值，用于选择对应页面的物理（基）地址。线性地址的低位给出了页面中的偏移量，加上页面的基地址最终形成对应的物理地址。
• 页面大小：在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B~8 KB。

地址结构

页表的功能

4.4.2地址变换机构

基本的地址变换机构

具有快表的地址变换机构

4.4.3两级和多级页表

现代计算机的页表过大的解决方法

• ①采用离散分配方式来解决难以找到一块连续的大内存空间的问题
• ②只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。

多级页表

4.5基本分段存储管理方式

4.5.1分段存储管理方式的引入的原因

• 方便编程
• 信息共享
• 信息保护
• 动态增长
• 动态链接

4.5.2分段系统的基本原理

分段地址的结构

段表

地址变换机构

分页和分段的主要区别

• 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头， 提高内存的利用率。或者说， 分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。
• 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
• 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名， 又需给出段内地址。

4.5.3信息共享

• 分段系统的一个突出的优点，便是易于实现段的共享，即允许若干个进程共享一个或多个段，而且对段的保护也十分简单易行。如果代码是可重入的（允许多个进程同时访问的代码，不允许任何进程在执行过程中对其有任何改变），则无论是在分页系统还是在分段系统中，该代码都能被共享。
• 以分时系统的多个用户共享文本编辑程序为例，在分页系统中，为实现代码的共享，应在每个进程的页表中，建立40个页表项，还需为自己的数据区建立页表项，而分段系统只需为文本编辑程序设置一个段表项。

4.5.4段页式存储管理方式

地址变换过程

4.6虚拟存储器的基本概念

4.6.1虚拟存储器的引入

引入原因

• 大作业所需空间超过内存空间
• 内存容量不足以容纳所有要运行的作业

常规存储管理方式的特征

• 一次性：作业在运行前，需要一次性装入内存
• 驻留性：阻塞或已运行过不在运行的程序在结束前一直驻留内存

局部性原理(1968年 Denning.P)

• 程序执行时， 除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。
• 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域， 但经研究看出，过程调用的深度在大多数情况下都不超过5。
• 程序中存在许多循环结构， 这些虽然只由少数指令构成， 但是它们将多次执行。
• 程序中还包括许多对数据结构的处理， 如对数组进行操作， 它们往往都局限于很小的范围内。

局限性表现的两个具体方面

• 时间局限性。如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。
• (2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

虚拟存储器定义

• 具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。

4.6.2虚拟存储器的实现方法

分页请求系统

• 硬件支持：① 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；② 缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存；③ 地址变换机构， 它同样是在纯分页地址变换机构的基础上发展形成的。
• 实现请求分页的软件

请求分段系统

• （1）请求分段的段表机制。这是在纯分段的段表机制基础上，增加若干项而形成的；
• （2）缺段中断机构。每当用户程序所要访问的段尚未调入内存时，产生一缺段中断，请求OS将所缺的段调入内存；
• （3）地址变换机构：实现分页请求和请求分段的请求调页或段和置换功能都需要得到OS的支持。

4.6.3虚拟存储器的特征

• 离散性
• 多次性
• 对换性
• 虚拟性

4.7请求分页存储管理方式

4.7.1请求分页中的硬件支持

• 页表机制
• 分页中断机构
• 地址变换机构

4.7.2内存分配策略和分配方法

最小物理块数的确定

• 进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、 功能和寻址方式

物理块的分配策略

• 1) 固定分配局部置换(Fixed Allocation, Local Replacement)：为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变，只能从该进程在内存的n个页面中选出一页换出，然后再调入一页以保证分配给该进程的内存空间不变
• 2) 可变分配全局置换(Variable Allocation, Global Replacement)：系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。
• 3) 可变分配局部置换(Variable Allocation, Local Replacemen)：进程分配一定数目的内存空间，但当某种进程发生缺页时，只允许从该进程在内存页面中选出一页换出，若某进程频繁地发生缺页中断，为该进程分配若干个附加的物理块，缺页率减低到适当程度为止。若某进程缺页率较低，适当减少分配给该进程的物理块。总之维持一个适当的缺页率。

物理块分配算法

• 平均分配算法
• 按比例分配算法
• 考虑优先权的分配算法

4.7.3调页策略

何时调入页面

• 预调页策略：采用一种以预测为基础的预调页策略；预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存，目前预调页的成功率仅约50%。这种策略主要用于进程首次调入时，由程序员指出应该先调入哪些页。
• 请求调页策略：当进程在运行中需要访问某部分程序的数据时，发现其所在的页面不在内存，需立即提出请求，由系统将其所需页面调入内存。由请求调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。
• 确定从何处调入页面： 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前， 便须将与该进程有关的文件，从文件区拷贝到对换区。 (2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此， 某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。

页面调入过程

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

4.8页面置换算法

4.8.1最佳置换算法和先进先出置换算法

最佳(Optimal)置换算法

• 原理：其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。
• 局限性：采用最佳置换算法可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不在被访问的，因而该算法也是无法实现的，但是可利用该算法去评价其它算法。

先进先出(FIFO)页面置换算法

• 原理：选择在内存中的驻留时间最久的页面予以淘汰。
• 优点：该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老页面
• 缺点：与进程实际运行的规律不相适应，有些页面经常被访问，含有全局变量、常用函数、例程等的页面，FIFO置换算法并不能保证这些页面不被淘汰。

4.8.2最近最久未使用(LRU)置换算法

4.8.3Clock置换算法

• (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。
• (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
• (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

4.8.4其他置换算法

• 最少使用(LFU： Least Frequently Used)置换算法
• 页面缓冲算法(PBA： Page Buffering Algorithm)

4.9请求分段存储管理方式

4.9.1 请求分段中的硬件支持

• 段表：在段表项中， 除了段名(号)、 段长、 段在内存中的起始地址外， 还增加了以下诸项：（1）存取方式。 00(可执行)；01(可读)；11(可写)；(2) 访问字段A。被访问次数 (3) 修改位M。是否被修改过(4) 存在位P。 是否已调入内存(5) 增补位。 运行过程中是否增长过(6) 外存始址。硬盘的块号 （如果在硬盘上）

4.9.2分段的共享与保护

共享段段分配和回收

• 共享段的分配：在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段。
• 共享段的回收：当共享此段的某进程不再需要该段时，应将该段释放， 包括撤消在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项， 表明此时已没有进程使用该段；否则(减1结果不为0)， 则只是取消调用者进程在共享段表中的有关记录。

分段保护

越界检查

• 在段表寄存器中放有段表长度信息，同样，在段表中也为每个段设置有段长字段。在进行存储访问时，首先，将逻辑地址空间的段号与段表长度进行比较，如果段号等于或大于段表长度，将发出地址越界中断信号；其次，还要检查段内地址是否等于或大于段长，若是大于段长，将产生地址越界中断信号，从而保证了每个进程只能在自己的地址空间内运行。

存取控制检查：在段表的每个表项中，都设置了一个“存取控制”字段，用于规定对该段的访问方式。通常的访问方式有：

• 只读。只允许程序对该段中的程序或数据进行读访问；
• 只执行。只允许程序调用该段去执行，但不准读该段的内容，也不允许对该段执行写操作；
• 读/写。允许程序对该段进行读写访问。

环保护机构：一种功能较完善的保护机构。在该机制中规定：低编号的环具有高优先权，OS核心处于0环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序，则被安排在外环上。在环系统中，程序的访问和调用应遵循以下规则：

• 一个程序可以访问驻留在相同环或较低特权环中的数据。
• 一个程序可以调用驻留在相同环或较高特权环中的服务。

第五章

5.1I/O系统的功能、模型和接口

• 管理对象：I/O设备和相应的设备控制器

5.1.1I/O系统的基本功能

• 隐藏物理设备的细节：I/O设备的类型非常多，且彼此间在多方面都有差异，I/O系统必须通过对设备加以适当的抽象，隐藏物理设备的实现细节，仅向上层进程提供少量、抽象的读写命令。
• 与设备的无关性：隐藏物理设备的细节，可方便用户对设备的使用。无关性不仅可以让用户使用抽象的I/O命令，还可使用抽象的逻辑设备名来使用设备，并可以有效地提高OS的可移植性和易适应性。
• 提高处理机和I/O设备的利用率：尽可能地让处理机和I/O设备并行操作，以提高它们的利用率。
• 对I/O设备进行控制：目前对I/O设备有四种控制方式：① 采用轮询的可编程I/O方式；② 采用中断的可编程I/O方式；③ 直接存储器访问方式；④ I/O通道方式。
• 确保对设备的正确共享：从设备的共享属性上，可将系统中的设备分为如下两类：(1) 独占设备，进程应互斥地访问这类设备。　　(2) 共享设备，是指在一段时间内允许多个进程同时访问的设备。典型的共享设备是磁盘，当有多个进程需对磁盘执行读、写操作时，可以交叉进行，不会影响到读、写的正确性。
• 错误处理：大多数的设备都包括了较多的机械和电气部分，运行时容易出现错误和故障。　

5.1.2I/O系统的层次结构和模型

6.1.3I/O系统接口

• 块设备接口：块设备、隐藏了磁盘的二维结构、将抽象命令映射为低层操作。
• 流设备接口：流设备接口是流设备管理程序与高层之间的接。
• 网络通信接口

5.2I/O设备和设备控制器

5.2.1I/O设备

两种分类模式

• 按使用特性分类
• 按传输速率分类

设备与控制器之间的接口

• 数据信号线
• 控制信号线
• 状态信号线

5.2.2设备控制器

设备控制器的基本功能

• 接收和识别命令
• 数据交换
• 标识和报告设备的状态
• 地址识别
• 数据缓冲区
• 差错控制

设备控制器的组成

• 设备控制器与处理机的接口
• 设备控制器与设备的接口
• I/O逻辑

5.2.3I/O通道

引入原因

• 当主机所配置的外设很多时，CPU的负担仍然很重

通道类型

• 字节多路通道(Byte Multiplexor Channel)
• 数组选择通道(Block Selector Channel)
• 数组多路通道(Block Multiplexor Channel)

瓶颈问题

* 由于通道价格昂贵，致使机器中所设置的通道数量势必较少，这往往又使它成了I/O的瓶颈，进而造成整个系统吞吐量的下降

5.3中断机构和中断处理程序

• 中断的重要性：进程之间的切换、中断是设备管理的基础

5.3.1中断简介

• 中断：由外部设备引起的，CPU对I/O设备发来的中断信号的响应
• 陷入：由CPU内部事件引起的中断，如运算出现上溢或下溢、程序出错等，称内中断或陷入
• 中断向量表：为每种设备配以相应的中断处理程序，将该程序的入口地址放在中断向量表的一个表项中，为每个设备的中断请求规定一个中断号，对应于中断向量表的一个表项。
• 中断优先级：根据每个中断源对服务要求的紧急程度，分别规定不同的优先级。
• 对中断源的处理方式：屏蔽(禁止)中断、嵌套中断

5.3.2中断处理程序

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

5.4设备驱动程序

• 主要任务：接收上层软件发来的抽象I/O要求，把它转换为具体要求后，发送给设备控制器，启动设备去执行。

5.4.1设备驱动程序概述

设备驱动程序的功能

• 接收由与设备无关的软件发来的命令和参数，并将命令中的抽象要求转换为与设备相关的低层操作序列。
• 检查用户I/O请求的合法性，了解I/O设备的工作状态，传递与I/O设备操作有关的参数，设置设备的工作方式。
• 发出I/O命令，如果设备空闲，便立即启动I/O设备，完成指定的I/O操作；如果设备忙碌，则将请求者的请求块挂在设备队列上等待。
• 及时响应由设备控制器发来的中断请求，并根据其中断类型，调用相应的中断处理程序进行处理。

设备驱动程序的特点(与一般应用程序、系统程序的差异)

• 驱动程序是实现在与设备无关的软件和设备控制器之间通信和转换的程序，具体说，它将抽象的I/O请求转换成具体的I/O操作后传送给控制器。又把控制器中所记录的设备状态和I/O操作完成情况，及时地反映给请求I/O的进程。
• 驱动程序与设备控制器以及I/O设备的硬件特性紧密相关，对于不同类型的设备，应配置不同的驱动程序。
• 驱动程序与I/O设备所采用的I/O控制方式紧密相关，常用的I/O控制方式是中断驱动和DMA方式。
• 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写。目前有很多驱动程序的基本部分已经固化在ROM中。
• 驱动程序应允许可重入。一个正在运行的驱动程序常会在一次调用完成前被再次调用。

5.4.2设备驱动程序的处理过程

• 将抽象要求转换为具体要求→对服务请求进行校验→检查设备的状态→传送必要的参数→启动I/O设备

5.4.3对I/O设备的控制方式

• 使用轮询的可编程I/O方式
• 使用中断的可编程I/O方式

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

特点

• 数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块。
• 所传送的数据是从设备直接送入内存的，或者相反。
• 仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。

DMA

• 接存储器访问方式的引入
• DMA控制器的组成：主机与DMA控制器的接口；DMA控制器与块设备的接口；I/O控制逻辑
• DMA工作过程

I/O通道的控制方式

• 引入原因：而当我们需要一次去读多个数据块且将它们分别传送到不同的内存区域，或者相反时，则须由CPU分别发出多条I/O指令及进行多次中断处理才能完成。
• 通道程序：通道是通过执行通道程序并与设备控制器共同实现对I/O设备的控制的。通道程序是由一系列通道指令(或称为通道命令)所构成的。

5.5与设备无关的I/O软件

5.5.1与设备无关软件的基本概念

• 以物理设备名使用设备
• 引入逻辑设备名
• 逻辑设备名称到物理设备名称到转换

5.5.2与设备无关的软件

• 设备驱动程序的统一接口：为了使所有的设备驱动程序有着统一的接口，一方面，要求每个设备驱动程序与OS之间都有着相同的接口，或者相近的接口，这样会使添加一个新的设备驱动程序变得很容易，同时在很大程度上方便了开发人员对设备驱动程序的编制。另一方面，要将抽象的设备名映射到适当的驱动程序上，或者说，将抽象的设备名转换为具体的物理设备名，并进一步可以找到相应物理设备的驱动程序入口。
• 缓冲管理：无论是字符设备还是块设备，它们的运行速度都远低于CPU的速度。为了缓和CPU和I/O设备之间的矛盾、提高CPU的利用率，在现代OS中都无一例外地分别为字符设备和块设备配置了相应的缓冲区。缓冲区有着多种形式，如单缓冲区、双缓冲区、循环缓冲区、公用缓冲池等，以满足不同情况的需要。
• 差错控制：由于设备中有着许多的机械和电气部分，因此，它们比主机更容易出现故障，这就导致I/O操作中的绝大多数错误都与设备有关。
• 对独立设备的分配与回收：在系统中有两类设备：独占设备和共享设备。对于这两类设备的分配方式不同。
• 独立于设备的逻辑数据块：不同类型的设备，其数据交换单位是不同的，读取和传输速率也各不相同，如字符型设备以单个字符(字)为单位，块设备是以一个数据块为单位。设备独立性软件应能够隐藏这些差异而被逻辑设备使用，并向高层软件提供大小统一的逻辑数据块。

5.5.3设备分配

设备分配中的数据结构

• 设备控制表DCT
• 控制器控制表COCT、通道控制表CHCT和系统设备表SDT

设备分配时应考虑的因素

• 设备的固有属性：独占设备的分配策略、共享设备的分配策略，虚拟设备的分配策略
• 设备分配算法：先来先服务、高优先级者优先
• 设备分配中的安全性：安全分配方式、不安全分配方式

独占设备分配程序

• 基本设备分配程序：分配设备、分配控制器、分配通道
• 设备分配程序的改进：在上面的例子中，进程是以物理设备名提出I/O请求的。如果所指定的设备已分配给其它进程，则分配失败。或者说上面的设备分配程序不具有与设备无关性。为获得设备的独立性，进程应使用逻辑设备名请求I/O。

5.5.4逻辑设备名到物理设备名映射到实现

• 逻辑设备表LUT(Logical Unit Table)逻辑设备名、物理设备名、逻辑驱动程序入口地址
• 逻辑设备表的设置问题：整个系统只设置一个LUT、每个用户设置一张LUT
  

5.6用户层的I/O软件

5.6.1系统调用与库函数

• 系统调用：一方面，为使诸进程能有条不紊地使用I/O设备，且能保护设备的安全性，不允许运行在用户态的应用进程去直接调用运行在核心态(系统态)的OS过程。但另一方面，应用进程在运行时，又必须取得OS所提供的服务，否则，应用程序几乎无法运行。为了解决此矛盾，OS在用户层中引入了一个中介过程——系统调用，应用程序可以通过它间接调用OS中的I/O过程，对I/O设备进行操作。
• 库函数：在C语言以及UNIX系统中，系统调用(如read)与各系统调用所使用的库函数(如read)之间几乎是一一对应的。而微软定义了一套过程，称为Win32 API的应用程序接口(Application Program Interface)，程序员利用它们取得OS服务，该接口与实际的系统调用并不一一对应。用户程序通过调用对应的库函数使用系统调用，这些库函数与调用程序连接在一起，被嵌入在运行时装入内存的二进制程序中。

5.6.2·假脱机(Spooling)系统

• 假脱机技术：在20世纪50年代，为了缓和CPU的高速性与I/O设备低速性间的矛盾，而引入了脱机输入/输出技术。该技术是利用专门的外围控制机，先将低速I/O设备上的数据传送到高速磁盘上，或者相反。这样当处理机需要输入数据时，便可以直接从磁盘中读取数据，极大地提高了输入速度。反之，在处理机需要输出数据时，也可以很快的速度把数据先输出到磁盘上，处理机便可去做自己的事情。
• SPOOLing的组成：输入井和输出井，输入缓冲区和输出缓冲区、输入进程和输出进程、井管理程序
• SPOOLing系统的特点：提高了I/O的速度、将独占设备改造为共享设备、实现了虚拟设备功能。
• 假脱机打印机系统：磁盘缓冲区、打印缓冲区、假脱机管理进程和假脱机打印进程
  

5.7缓冲区管理

5.7.1缓冲的引入

• 缓和CPU与I/O设备间速度不匹配的矛盾
• 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
• 解决数据粒度不匹配的问题
• 提高CPU和I/O设备之间的并行性

5.7.2单缓冲区和双缓冲区

• 单缓冲区(Single Buffer)：在单缓冲情况下，每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区
• 双缓冲区(Double Buffer)：由于缓冲区是共享资源，生产者与消费者在使用缓冲区时必须互斥。如果消费者尚未取走缓冲区中的数据，即使生产者又生产出新的数据，也无法将它送入缓冲区，生产者等待。如果为生产者与消费者设置了两个缓冲区，便能解决这一问题。

5.7.3环形缓冲区

• 环形缓冲区的组成：多个缓冲区、多个指针
• 环形缓冲区的使用：Getbuf过程、Releasebuf过程
• 进程之间的同步问题：Nexti指针追上Nextg指针、Nextg指针追上Nexti指针

5.7.4·缓冲池(Buffer Pool)

• 空白缓冲队列emq
• 输入队列inq
• 输出队列outq

5.8磁盘存储器的性能和调度

5.8.1磁盘性能简述

• 磁盘设备是一种相当复杂的机电设备，在此仅对磁盘的某些性能，如数据的组织、磁盘的类型和访问时间等方面做扼要的阐述。
• 数据的组织和格式：·磁盘设备可包括一个或多个物理盘片，每个磁盘片分一个或两个存储面(Surface，每个盘面上有若干个磁道(Track)，磁道之间留有必要的间隙(Gap)。为使处理简单起见，在每条磁道上可存储相同数目的二进制位
• 磁盘的类型：硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头(移动头)磁盘
• 磁盘访问时间：磁盘设备在工作时以恒定速率旋转。为了读或写，磁头必须能移动到所指定的磁道上，并等待所指定的扇区的开始位置旋转到磁头下，然后再开始读或写数据
• 磁盘访问时间包括：寻道时间、旋转延迟时间、传输时间

5.8.2早起磁盘调度算法

• 先来先服务(FCFS)：这是最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。
  
• 最短寻道时间优先(SSTF)：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短。
  

5.8.3基于扫描的磁盘调度算法

• 扫描(SCAN)算法：SSTF算法的实质是基于优先级的调度算法，因此就可能导致优先级低的进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必然优先满足。扫描算法（SCAN）不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。当磁头正在由里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样由里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向，由外向里移动。这时，同样也是每次选择在当前磁道之内，且距离最近的进程来调度。
  
• 循环扫描(CSCAN)算法：SCAN算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大、中、小型机器和网络中的磁盘调度。但也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完处于外面的所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。
  
• NStepSCAN算法：在SSTF、SCAN及CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”(Armstickiness)。在高密度磁盘上容易出现此情况。NStepSCAN算法是将磁盘请求队列分成若干长度为N的子队列，按FCFS算法依次处理这些子队列。
• FSCAN调度算法：FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个是在扫描期间，将新出现的所有请求磁盘I/O的进程放入等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。

• 第六章 文件管理

6.1文件和文件系统

6.1.1文件、记录、数据项

数据项

• 基本数据项：原子数据，数据元素，字段
• 组合数据项：由若干个基本数据项组成

记录

• 定义：一些有关数据项的集合，描述对象在某方面的属性
• 关键字：唯一能够标志一个记录的数据项

文件

• 有结构文件中，有若干个相关记录组成
• 无结构文件：一个字符流
• 文件是文件系统中最大的数据单位
• 文件必须有文件名，由ASCII码或者汉子组成
• 文件类型：源文件、目标文件
• 文件长度：块、字、字节
• 物理位置：指示文件在哪一个设备上以及在该设备的哪个位置的指针
• 建立时间：文件的最后一次修改时间

6.1.2文件类型

• 按用途分三类：系统，用户，库文件
• 按文件中数据的形式：源，目标以及可执行文件
• 按存取控制属性：只执行，只读，读写

6.1.3文件系统的层次模型

• 对象：文件、目录、磁盘存储空间
• 对对象操纵和管理的软件集合。核心部分包括：文件存储空间的管理，文件目录的管理，逻辑地址与物理地址转换机制，文件读写管理，文件共享与保护等。
• 文件系统的接口：命令(终端键入命令)和程序(系统调用)

6.1.4文件操作

• 最基本的文件操作有：创建文件（分配外存，建立目录项）、删除文件（置空目录项）、读文件、写文件、截断文件（原有文件长度置0）和设置文件的读／写位置（改变始终从始端开始读/写操作）
• 文件的“打开”和“关闭”操作：“打开”(open)，是指系统将指名文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引）返回给用户。 “关闭”（close）系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉。
• 其它文件操作：对文件属性的操作，改变文件名、改变文件的拥有者，查询文件的状态等

6.2文件的逻辑结构

• 文件由记录构成
• 文件存在两种形式的结构：逻辑结构、物理结构

6.2.1文件逻辑结构类型

有结构文件：记录式文件

• 顺序文件
• 索引文件
• 顺序索引文件

无结构文件：字符流

• 流式文件，长度以字节为单位
• UNIX系统中，所有文件都是流式文件

6.2.2顺序文件

逻辑记录的排序

• ①串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列
• ②顺序结构，指文件中的所有记录按关键字排列

顺序文件的优缺点

优点:

• (1)对顺序文件的存取效率是所有逻辑文件中最高的
• (2)只有顺序文件才能存储在磁带上，并能有效地工作

缺点:

• (1)在交互应用的场合，如果用户（程序）要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。
• (2)如果想增加或删除一个记录，都比较困难。

6.2.3记录寻址

• 定长记录的顺序文件：如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。在读一个文件时，可设置一个读指针Rptr。令它指向下一个记录的首地址，每当读完一个记录时，便执行:Rptr：=Rptr十L （L为记录长度）
• 变长记录的顺序文件：在每次读或写完一个记录后，须将读或写指针加上Li。Wptr：=Wptr十Li（Li 是刚读或刚写完的记录的长度）

6.2.4索引文件

• 原因：对于定长记录，可方便地实现直接存取。对于变长记录就较难实现直接存取，为了解决这一问题，为变长记录文件建立一张索引表，索引表是按键排序的，可以方便地实现直接存取。

6.2.5索引顺序文件

• 索引顺序文件:将顺序文件中的所有记录分为若干个组, 为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。
  
• 文件检索过程：在对索引顺序文件进行检索时，首先也是利用用户(程序)所提供的关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置；然后，再利用顺序查找法去查找主文件，从中找到所要求的记录。

6.2.6直接文件和哈希文件

• 直接文件：对于直接文件，可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这种由记录 键值到记录物理地址的转换被称为键值转换。
• 哈希（Hash）文件：利用Hash函数，可将记录键值转换为相应记录的地址。为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。

6.3文件目录

• 目录管理的要求：实现“按名存取”、提高对目录的检索速度、文件共享、允许文件重名

6.3.1文件控制块和索引结点

文件控制块

• 文件控制块：为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块（FCB）”
• 基本信息：①文件名；②文件物理位置；③文件逻辑结构（表明文件是流式还是记录式，定长还是变长等）；④文件物理结构（顺序文件，链式还是索引文件）
• 存取控制信息类：存取权限
• 使用信息类：文件的简历日期和时间

索引节点

• 索引结点的引入：文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点。在文件目录中的每个目录项，仅由文件名和指向该文件所对应的i结点的指针所构成。
• 磁盘索引结点包括以下内容：文件主标识符，文件类型，存取权限，文件物理地址，文件长度，文件连接计数（系统中所有指向该文件名的指针计数），文件存取时间。
• 内存索引结点包括以下内容：索引结点编号，状态，访问计数，文件所属文件系统的逻辑设备号，链接指针。

6.3.2目录结构

单级目录结构

• 优点：是简单且能实现目录管理的基本功能——按名存取
• 缺点：查找速度慢、不允许崇明、不便于文件共享只适合单用户环境

两级目录结构

• 实现方法：为每一个用户建立一个单独的用户文件目录UFD，再建立一个主文件目录MFD。在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针
• 优点：提高了检索目录的速度、在不同的用户目录中，可以使用相同的文件名、不同用户还可使用不同的文件名来访问系统中的同一个共享文件
  

6.3.3树形目录结构

目录结构：主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点
路径名：从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名（path name），系统中的每一个文件都有惟一的路径名。
当前目录：为每个进程设置一个“当前目录”，又称为“工作目录”进程对各文件的访问都相对于“当前目录”而进行。
增加目录：在用户要创建一个新文件时，只需查看在自己的UFD及其子目录中，有无与新建文件相同的文件名。若无，便可在UFD或其某个子目录中增加一个新目录项
* 删除目录：不删除非空目录、可删除非空目录

6.3.4目录查询技术

线性检索法

• ①在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。
• ②在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找。

Hash方法

• Hash方法: 建立了一张Hash索引文件目录，系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找。
• 优点：Hash方法将显著地提高检索速度。
• 局限性：在文件名中使用了通配符“* ”、“？”等，系统便无法利用Hash法检索目录，因此，需要利用线性查找法查找目录。
• Hash查找过程：①在利用Hash值查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。②如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。③如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“Hash冲突”。
• 解决Hash冲突的方法 ：将其Hash值再加上一个常数（该常数应与目录的长度值互质），形成新的索引值，再返回到第一步重新开始查找。

6.4文件共享

• 基于索引结点的共享方式
• 利用符号链实现文件共享

6.4.1基于索引结点的共享方式

6.4.2利用符号链接实现文件共享

• 为使B能共享C的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F并将F写入B的目录中，以实现B的目录与文件F的链接；在新文件中只包含被创文件F的路径名。这样的链接方法被称为符号链接
• 新文件中的路径名，则只被看作是符号链。当B要访问被链接的文件F且正要读LINK类新文件时，将被OS截获，OS根据新文件中的路径名去读该文件，于是就实现了用户B对文件F的共享
• 在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针，而共享该文件的其它用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。
• 符号链方式优点：能连接任何机器上的文件。
• 每增加一个连接，就增加一个文件名，各用户使用自己的名字去共享文件。
• 缺点：备份是可能会产生多个拷贝。

6.5文件保护

• 安全性的影响因素：人为因素、系统因素、自然因素
• 采取的措施：存取控制、系统容错技术、建立后备系统

6.5.1保护域

访问权

• 对象：硬件、软件
• 对对象施加的操作：读、写、执行
• 访问权：一个进程能对某对象执行操作的权力，用一个有序对（对象名，权集）表示；（F1，{R/W})表示某进程对文件F1执行读和写操作的权力

保护域

• “保护域”简称“域”，是进程对一组对象访问权的集合，进程只能在指定域内执行操作。

进程和域之间的静态联系

• 一一对应，一个进程只联系一个域

进程和域间的动态联系

• 一对多，进程的运行分为若干个阶段，每个阶段联系一个域

6.5.2访问矩阵

基本访问矩阵

• 用一个矩阵来描述系统的访问控制，行代表域，列代表对象
• 访问权由资源的拥有者或者管理者决定

具有域切换权的访问矩阵

• 切换作为一种权力，仅当进程有切换权时，才能进行切换
• 增加几个对象作为域，当S∈ACCESS(i，j）时，才允许从i切换到j.

6.5.3访问矩阵的修改

• 拷贝权
• 所有权
• 控制权

6.5.4访问矩阵的实现

• 访问控制表：对访问矩阵按列划分，为每一列建立一张访问控制表ACL、删除空项
• 访问权限表：对访问矩阵按行划分，为每一行建立一张访问权限表、一个域对每一个对象可以执行的一组操作所构成的表