第一章.操作系统引论

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环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序，则被安排在外环上。在环系统中，程序的访问和调用应遵循以下规则：

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