操作系统概念 学习笔记

目录

第一章、导论

1.1 操作系统

1.计算机系统四个组成部分

计算机硬件、操作系统、系统程序和用户程序、用户。

硬件为系统提供了基本的计算资源。应用程序规定了用户按何种方式使用这些资源，操作系统不过提供了一个方便其它程序做有用工作的环境。

1.1.1 用户视角

1.1.2 系统视角

操作系统看作资源分配器。

• 操作系统管理这些资源
• 面对冲突的资源请求，操作系统必须决定如何为各个程序和用户分配资源，以便计算机系统能有效而公平的运行。

操作系统是 控制程序 ，管理用户程序的执行防止计算机资源的错误使用或使用不当。

1.1.3 定义操作系统

操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度，以及方便用户的程序集合。

3.操作系统的目标

执行用户程序，更容易地解决用户问题。

使计算机系统使用方便。

有效地使用计算机硬件。

1.2 计算机系统组织

1.2.1 计算机系统操作

现代通用计算机系统由一个或多个CPU和若干 设备控制器 通过共同的总线相连而成。

打开电源或重启——运行 初始化程序 （引导程序）——定位操作系统并将其装入内存——执行第一个进程

引导程序 ：通常位于ROM或者EEPROM，称为计算机硬件中的固件。用来初始化系统的所有部分（CPU寄存器，设备控制器和内存）。

中断 ：硬件可随时通过系统总线向CPU发出信号，出发中断。软件通过系统调用（或者其他特别操作）触发中断。

发生中断——调用一个通用子程序检查中断信息——使用中断处理指针表（ 中断向量 ）——间接调用中断处理子程序

现在的操作系统都是以 中断 为驱动的。

1.2.2 存储结构

内存是处理器可以直接访问的唯一的大容量存储区域

辅存 ：一般是磁盘。（因为内存太小，而且是易失性存储设备。）

各种存储系统的差别主要是速度、价格、大小和易失性。

易失性 ：断电时，会丢失内容

价格逐渐降低，大小逐渐增大，速度逐渐减慢，主存以上易失，

1.2.3 I/O结构

DMA（直接内存访问）

用于高速I/O设备，能够以接近内存速度传送信息。

设备控制器无需CPU干预直接将数据块从缓冲存储器直接传输到主存。

每个块只产生一个中断，而不是每个字节的一个中断。

1.3 计算机系统体系结构

单处理器系统、多处理器系统、集群系统

多处理器系统（并行系统、紧耦合系统）

定义：多处理器系统有多个紧密通信的CPU，它们共享计算机总线，有时还有时钟、内存和外设等。

优点：

增加吞吐量、规模经济、增加可靠性。

分类：

非对称多处理：每个处理器都有各自特定的任务。一个主处理器控制系统，其他处理器或者向主处理器要任务或做预先定义的任务。

对称多处理：每个处理器都要完成操作系统中的所有任务。所有处理器对等，处理器之间没有主-从关系。

集群系统

定义：与多处理器系统一样，集群系统将多个CPU集中起来完成计算任务。然而，集群系统与多处理器系统不同，它是由两个或多个独立的系统耦合起来的。集群计算机共享存储并通过局域网络连接或更快的内部连接。

1.4 .操作系统结构

操作系统最重要的一点是要有多道程序处理能力。多道程序设计通过组织作业（编码或数据）使CPU总有一个作业在执行，从而提高了CPU的利用率。

13.操作系统的三种基本类型

• Batch systems（批处理系统）
• Time-sharingsystems（分时系统）
• Real timesystems（实时系统）

批处理系统

工作方式：

用户将作业交给系统操作员，系统操作员将许多用户的作业组成一批作业(jobs)之后输入到计算机中，在系统中形成一个自动转接的连续的作业流，系统自动、依次执行每个作业。最后由操作员将作业结果交给用户。操作系统：自动将控制从一个任务转到下一个任务。

分类：单道批处理系统、多道批处理系统

批处理操纵系统优点：

作业流程自动化、效率高、吞吐量高。

批处理操纵系统缺点：

无交互手段、调试程序困难。

分时系统- 交互式计算

分时系统（或多任务）是 多道程序 设计的延伸。

共享需要一种交互计算机系统，它能提供用户与系统之间的直接通信。响应时间短（通常小于一秒钟）。

允许多用户共享计算机。由于每个动作或命令都较短，每个用户只需少量CPU时间，用户之间切换时间短，所以用户会感觉整个系统为自己所用。

实时系统

定义：实时操作系统是保证在一定时间限制内完成特定功能的操作系统。

分类：

硬实时系统：硬实时要求在规定的时间内必须完成操作，这是在操作系统设计时保证的。

软实时系统：软实时则只要按照任务的优先级，尽可能快地完成操作即可。

1.5 操作系统操作

1.5.1 操作系统的双重模式操作

为了区分操作系统代码和用户定义代码的执行，至少需要两种独立的操作模式 ：用户模式、监督程序模式 （管理模式、系统模式、特权模式）。

将能引起损害的机器指令作为 特权指令 。用户模式下想要执行特权指令，硬件不会执行，会认为是非法指令，并以陷阱的形式通知操作系统。

系统引导时，硬件开始处于 内核模式。 接着，装入操作系统，开始进入用户模式。出现陷阱或中断，会进入内核模式。

转换到用户模式就是一个特权指令。

1.5.2 定时器

防止用户进入死循环或不调用系统服务。定时器在给定时间后中断计算机。操作系统将控制权交给用户之前，设置 定时器。 修改定时器的操作就是特权指令。

第二章 操作系统结构

2.1 操作系统服务

用户界面（一种是命令行界面；另一种是批界面，最为常用的是图形用户面）、程序执行、I/O操作、文件系统操作、通信、错误检测、资源分配、统计、保护和安全。

2.2 操作系统的用户界面

命令解释程序（CLI）被成为外壳（shell）、图形用户界面（GUI）

命令解释程序主要作用

获取并执行用户指定的下一条指令。

2.3 系统调用（System Call）

系统调用 提供了操作系统提供的有效服务界面。

操作系统内核提供一系列预定功能，通过一组称为系统调用的接口呈现给编程人员，系统调用把应用程序的请求传给内核，系统调用相应的内核函数完成所需的处理，将处理结果返回给应用程序。

向操作系统传递参数的三种方法

• 通过寄存器来传递参数。
• 若参数数量比寄存器多，参数通常存在内存的块和表中，并将块的地址通过寄存器来传递。
• 参数也可以通过程序放在或压入堆栈中，并通过操作系统弹出。

2.4 系统调用类型

进程控制、文件管理、设备管理、信息维护和通信

2.5 系统程序分类

文件管理、状态信息、文件修改、程序语言支持、程序装入和执行、通信。

2.6 操作系统设计和实现

设计目标需求： 用户目标和系统目标

用户目标 ：更容易学习，容易使用，可靠，安全和快速

系统目标 ：容易设计、实现和维护。灵活、可靠、高效且没有错误。

机制和策略 ：机制决定如何做，策略决定做什么

实现 ：用高级语言的缺点仅仅在于降低了速度和增加了存储要求

2.7 操作系统结构

简单结构、分层方法、微内核、模块、虚拟机.

2.7.1 简单结构

MS-DOS、原始的UNIX操作系统

2.7.2 分层方法

定义 ：操作系统分成若干层（级）。最底层（层0）为硬件，最高层（层N）为用户接口。每层只考虑较低层的功能和服务。

优点：

• 每层都是利用较低层所提供的功能实现的，并为叫高层隐藏了一定的数据结构、操作和硬件的存在

缺点：

• 分层法的主要困难涉及对层的详细定义
• 与其它方法相比效率较差

2.7.3 微内核

微内核方法将所有非基本部分从内核中移走，并将它们实现为系统或用户程序，这样得到了更小的内核。

微内核的主要功能是使客户程序和运行在用户空间的各种服务之间进行通信。

优点：

• 便于扩充操作系统
• 很容易从一种硬件平台设计移植到另一种硬件平台设计
• 更安全、可靠

缺点：

由于系统功能总开销的增加而导致系统性能的下降。

2.7.4 模块

大多数现代操作系统实现内核模块：

采用面向对象的方法

每个核心组件是分开的

每部分与已知接口的其他部分通信

每部分根据需要加载到内核

总之，类似于层，但更灵活。

2.8 虚拟机

虚拟机（VirtualMachine）指通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的完整计算机系统。

第三章 进程

3.1 进程概念

3.1.1 进程

进程包含了程序代码和当前活动（其中当前活动通过程序计数器和处理器寄存器的内容表示）两个部分，进程是执行中的程序。具体有：

• 文本段（代码段）
• 数据段（全局变量）
• 栈（stack）（包含临时数据、函数参数、返回地址、局部变量）
• 堆（heap）（进程运行期间动态分配的内存）
• 程序计数器

注意 ： 程序是被动实体，进程是活动实体（其中当前活动通过程序计数器和处理器寄存器的内容表示）

两个进程可以与同一程序联系，虽然文本段相同。但是数据段、堆栈段不同

3.1.2 进程状态

进程有5种状态，包括：

• New（新的）
• Running（运行）
• Waiting（等待）
• Ready（就绪）
• Terminated（终止）

注意：一次只有一个进程能在一个处理器上运行（Running态），但在处理器上运行的时候，其他进程可以进行IO操作（想一下DMC模式）

3.1.3 进程控制块（PCB）

每一个进程都需要分配一定的信息，这些信息的仓库就叫做PCB，PCB有以下功能：

系统利用PCB 控制 和 管理 进程

PCB是进程存在的唯一标志

操作系统通过PCB感知进程的存在

PCB中包含以下内容（信息）：

进程状态（如上所述）

程序计数器：表示进程要执行的下个指令的地址

CPU寄存器：与程序计数器一起，在出现中断时状态信息需要保存，使进程能够正确执行

CPU调度信息：包括优先级、调度队列的指针等（见第五章）

内存管理信息：（见第八章）

记账信息：包括CPU时间、实际使用时间、时间界限、记账数据、作业和进程数量等

IO状态信息：分配给进程的IO设备列表，打开的文件列表等

3.2、进程调度

目的：使CPU的利用率最大化，需要优化进程调度的方法

进程调度程序选择一个进程到CPU上执行（一个CPU一个时间段只能执行一个程序，其余程序需要等待CPU空闲重新调度）

3.2.1 调度队列

作业（Job）队列 ：包含了系统中所有的进程

就绪（Ready）队列 ：包含了系统中，驻留在 内存 中就绪的，准备运行的进程

该队列通常用链表实现，头结点指向第一个和最后一个PCB块的指针，每个PCB块包括指向下一个PCB的指针域

设备（Device）队列 ：包含了等待特定IO设备的进程列表

进程可能会有IO请求，请求时可能IO设备在处理其他请求，所以该进程需要等待。

讨论进程调度的常用方法是队列图

其中包括了就绪队列和设备队列（可能有多个设备队列）

3.2.2 调度程序

通常对于批处理系统，进程更多的是被提交、放到大容量存储设备的缓冲池中，保存在那里以便之后执行，在这之后，需要通过调度程序来选择缓冲池中的进程装入内存，并执行

进程选择由相应的调度程序执行，有两类调度程序：

长期调度程序（long-term schedule） / 作业调度程序（job schedule） ：负责从缓冲池中选择进程，装入内存以便执行

短期调度程序（short-term schedule） / CPU调度程序（CPU schedule） ：从执行的进程中选择进程，并为之分配CPU

有的系统，如分时系统，加入了中期调度程序（medium-term schedule），其核心思想是能将进程从内存（或CPU竞争中）移出，从而降低多道程序设计的难度，之后，进程可被重新调入内存，并从中断处执行。通过中期调度程序，进程可换出，并在之后换入，这种方案称为交换

各类进程调度的特点：

长期调度程序执行的不频繁（进程创建期间可能间隔数分钟）

短期调度程序执行的非常频繁（毫秒级），因此需要程序执行的速度非常快

长期调度程序控制多道程序（multiprogramming）设计的程度，在稳定情况下，创建进程的速度应该等于进程离开系统的平均速度

进程的类型

IO为主（就是操作主要是IO传输）

CPU为主（就是操作主要是各种运算）

3.2.3 上下文切换

中断使CPU从当前任务改变为运行内核子程序。当发生一次中断的时候，系统需要保存当前 程序的上下文 ，在恢复程序时需要恢复程序的上下文。

将CPU切换到另一个进程需要保存当前程序的状态并恢复另一个程序的状态，这个任务叫做 上下文切换

进程的上下文也就是进程的PCB ，上文提到过它的组成

上下文切换的类型：

状态保存 （state save）：保存当前CPU的状态（不论是内核模式还是用户模式）

状态恢复 （state restore）：重新开始之前保存的状态

上下文切换是额外开销，切换时系统不能做其他任何有用的工作。其消耗的时间为几毫秒，具体的时间消耗和硬件支持密切相关

有的操作系统提供了多组寄存器集合，上下文切换只需要简单改变当前寄存器组的指针。

3.3 进程操作

绝大多数系统内的进程能够并发执行，并动态的创建和删除，因此操作系统应该提供一种机制来 创建 / 终止 进程（即进程操作）

3.3.1 进程创建

进程树：进程在执行过程中，能够继续创建进程（系统调用），创建进程的进程为 父进程 ，被创建的进程是 子进程 ，以此类推，形成了进程树

一般系统都有一个 根进程 ，负责创建其他所有的进程，这样一个系统的进程树只有一棵

进程是需要一定的资源的（CPU时间，内存，文件，IO设备），在一个进程创建子进程的时候， 在父进程和子进程之间需要分配 / 共享资源，有以下几种情况：

• 从操作系统哪里获取资源
• 从父进程中获取资源（限制子进程只能从父进程中获取资源能防止创建过多的进程导致系统超载）

在进程创建时，该进程会得到：

• 各种物理和逻辑资源
• 父进程传递来的初始化数据或输入
• 通常子进程会返回给父进程自身的标识符（系统中唯一标识进程身份的id）

在进程执行时，有以下几种情况：

• 父进程和子进程并发执行
• 父进程等待，直到子进程执行完毕

创建的新进程的地址空间有两种可能 ：

• 子进程是父进程的复制品（有相同的程序和数据）
• 子进程内装入另一个新程序

关于fork()和exec()：

• fork命令创建一个新的进程
• exec命令在fork命令后执行，用于将新的程序装入进程的内存空间

3.3.2 进程终止

进程终止的时间：

• 执行完最后语句，并使用系统调用exit()请求操作系统删除自身。
• 一个进程通过适当的系统调用终止另一个进程（通常这个进程需要是被终止进程的父进程，并且这需要知道被终止进程的标识符）

父进程终止子进程的原因一般有：

• • 子进程使用的资源超过了父进程分配的资源
• • 分配给子进程的任务不再需要
• • 父进程退出，在这种情况下，操作系统不允许子进程继续.有些系统如果一个进程终止，那么它所有的子进程都终止。这叫做 级联终止。 通常有操作系统进行

进程终止后：

进程会返回状 **态值（通常为整数）到父进程

所有进程资源会被操作系统释放**

如果父进程终止，那么其所有子进程会以init进程作为父进程。因此，子进程仍然有一个父进程来收集状态和执行统计

3.4 进程间通信

并发执行的进程有两类，一类是 独立进程 ，不能影响其他进程并且不被其他进程影响。

另一类是 协作进程 ，能影响其他进程或被其他进程影响

允许进程协作的优点：

• 信息共享
• 提高运算速度
• 模块化
• 方便

因此协作进程需要一种进程间通信机制（IPC）来允许进程相互交换数据与信息。有 共享内存和信息传递 两种类型

共享内存系统

比消息传递更快

只在建立共享内存区时需要系统调用

消息传递：

不需要避免冲突

通常需要系统调用实现，需要更多的内核介入的时间消耗

第四章 线程

4.1 概述

线程是CPU使用的基本单元，由 线程ID ， 程序计数器 ， 寄存器集 合和 栈 组成。它与属于同一进程的其他线程 共享代码段，数据段和其他操作系统资源。

4.1.1 多线程编程的优点

1. 响应度高：一个多线程的程序即使部分阻塞，其他部分仍能运行，从而增加了对用户的响应程度。
2. 资源共享
3. 经济：创建和切换线程比创建进程更节省资源和时间
4. 多处理器体系结构的利用：多线程能充分利用多处理器体系

4.2 多线程模型

提供多线程支持有两种方式： 用户线程 和 内核线程

• 用户线程受内核支持，无须内核管理
• 内核线程由操作系统支持和管理

在用户线程和内核线程之间存在一定的关系，即 多线程模型 ，以下讨论三种常用的关系：多对一，一对一，多对多

4.2.1 多对一模型

多个用户线程映射到一个内核线程

• 优点：线程管理由线程库在用户空间完成，效率比较高
• 缺点：如果一个线程阻塞，整个进程就会阻塞；且多个线程无法并行运行在多处理器上

4.2.2 一对一模型

每个用户线程映射到一个内核线程上

• 优点：比多对一模型更好的并发功能；一个线程阻塞时，其他线程能够继续调用；多个线程能够并发运行在多处理器
• 缺点：创建内核线程的开销会影响应用程序的功能

4.2.3 多对多模型

• 多对一模型可以创建任意多的用户线程，但是只能没有增加并发性
• 一对一模型增强了并发性，但开发者要小心不能在应用程序中创建太多的进程

多对多模型没有上述的所有缺点，它多路复用了许多用户线程到同样数量或更小数量的内核线程上

4.3 线程库

在用户空间中提供一个没有内核支持的库

执行一个由操作系统直接支持的内核级的库

4.4 多线程问题

4.4.1 系统调用fork()和exec()

在多线程程序中，系统调用fork()和exec()的语义有所改变。

如果程序中一个进程调用fork()，那么新进程会复制所有线程，还是新进程只有单个线程？有的UNIX系统有两种形式的fork()， 一种复制所有线程，另一种只复制调用了系统调用fork()的线程。

Exec()工作方式：如果一个线程调用系统调用exec()，那么exec()参数所指定的程序会替换整个进程，包括所有线程。

如果调用fork()之后立即调用exec()，那么没有必要复制所有线程，因为exec()参数所指定的程序会替换整个进程。在这种情况下，只复制调用线程比较适当。不过，如果在fork()之后另一进程并不调用exec(),那么另一进程就应复制所有进程。

4.4.2 取消

线程取消（thread cancellation）是在线程完成之前来终止线程的任务。

要取消的线程通常称为 目标线程 。目标线程的取消可在如下两种情况下发生：

一是 异步取消 （asynchronous cancellation）：一个线程立即终止目标线程。

二是 延迟取消 （deferred cancellation）：目标线程不断地检查它是否应终止，这允许目标线程有机会以有序方式来终止自己。

如果资源已经分配給要取消的线程，或者要取消的线程正在更新与其他线程所共享的数据，那么取消会有困难，对于异步取消尤为麻烦。操作系统回收取消线程的系统资源，但是通常不回收所有资源。因此，异步取消线程并不会使所需的资源空闲。相反采用延迟取消时，允许一个线程检查它是否是在安系统资源空闲全的点被取消，pthread称这些点为 取消点 （cancellation point）。

4.4.3 信号处理

信号处理：信号在Unix中用来通知进程某个特定时间已发生了，信号可以同步或异步接收。所有有信号具有同样的模式：

（1）信号有特定事件的发生所产生

（2）产生的信号要发送到进程

（3）一旦发送，信号必须交易处理。

同步信号的例子包括访问非法内存或被0除。在这种情况下，如果运行程序执行这些动作，那么就产生信号，同步信号发送到执行操作而产生信号的同一进程（同步的原因）。

当一个信号由运行进程之外的事件产生，那么进程就异步接收这一信号。这种信号的例子包括使用特殊键（Ctrl + C）或者定时器到期。通常，异步信号被发送到另一个进程。

每个信号可能由两种可能的处理程序中的一种来处理：

（1）默认信号处理程序

（2）用户定义的信号处理程序

每个信号都有一个默认信号处理程序，当处理信号是在内核中运行的，这种默认动作可以用用户定义的信号处理程序来改写。信号可以按照不同的方式处理。有的信号可以简单的忽略（如改变窗口大小），有的需要终止程序来处理（非法内存访问）

单线程程序的信号处理比较直接，信号总是发送给 进程 。

当多线程时，信号会

（1）发送信号到信号所应用的线程

（2）发送信号到进程内的每个线程

（3）发送信号到进程内的某些固定线程

（4）规定一个特定线程以接收进程的所有信号。

发送信号的方法依赖于信号的类型。

4.4.4 线程池

多线程服务器有一些潜在问题：第一个是关于处理请求之前用以创建线程的时间，以及线程在完成工作之后就要被丢弃这一事实。第二个，如果允许所有并发请求都通过新线程来处理，那么将没法限制在系统中并发执行的线程的数量。无限制的线程会耗尽系统资源。解决这一问题是使用 线程池 。

线程池的思想是在进程开始时创建一定数量的线程，并放入到池中以等待工作。当服务器收到请求时，他会唤醒池中的一个线程，并将要处理的请求传递给他，一旦线程完成了服务，它会返回到池中在等待工作。如果池中没有可用的线程，那么服务器会一直等待直到有空线程为止。

线程池的优点：

（1）通常用现有线程处理请求要比等待创建新的线程要快

（2）线程池限制了在任何时候可用线程的数量。

线程池中的线程数量由系统CPU的数量、物理内存的大小和并发客户请求的期望值等因素决定。比较高级的线程池能动态的调整线程的数量，以适应具体情况。

4.4.5 线程特定数据

同属一个进程的线程共享进程数据。

在某些情况下每个线程可能需要一定数据的自己的 副本 ，这种数据称为 线程特定数据 。可以让每个线程与其唯一的标识符相关联。

第五章 CPU调度

5.1 基本概念

多道程序操作系统的基础。通过在进程之间切换CPU，操作系统可以提高计算机的吞吐率。

对于单处理器系统，每次只允许一个进程运行：任何其他进程必须等待，直到CPU空闲能被调度为止。

5.1.1 CPU-I/O 区间周期

CPU的成功调度依赖于进程的如下属性：

进程执行由 CPU执行周期 和 I/O等待周期 组成。进程在这两个状态之间切换(CPU burst—I/O bust)。

进程执行从CPU区间（CPU burst）开始，在这之后是I/O区间（I/O burst）。接着另外一个CPU区间，然后是另外一个I/O区间，如此进行下去，最终，最后的CPU区间通过系统请求中止执行。

经过大量CPU区间的长度的测试。发现具有大量短CPU区间和少量长CPU区间。I/O约束程序通常具有很多短CPU区间。CPU约束程序可能有少量的长CPU区间。这种分布有助于选择合适的CPU调度算法。

5.1.2 CPU程序调度

每当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行。进程选择由短期调度程序（short-term scheduler）或CPU调度程序执行。调度程序从内存中选择一个能够执行的进程，并为之分配CPU。

就绪队列不必是先进先出（FIFO）队列，也可为优先队列、树或简单的无序链表。不过队列中所有的进程都要排队以等待在CPU上运行。队列中的记录通常为进程控制块（PCB）。

5.1.3 抢占调度

CPU调度决策可在如下4种情况环境下发生：

（1）当一个进程从运行切换到等待状态（如：I/O请求，或者调用wait等待一个子进程的终止）

（2）当一个进程从运行状态切换到就绪状态（如：出现中断）

（3）当一个进程从等待状态切换到就绪状态（如：I/O完成）

（4）当一个进程终止时

对于第1和4两种情况，没有选择而只有调度。一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。对于第２和第３两种情况，可以进行选择。

当调度只能发生在第1和4两种情况下时，称调度是非抢占的（nonpreemptive）或协作的（cooperative）；否则，称调度方案为 抢占的 （preemptive）。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。

抢占调度对访问共享数据是有代价（如加锁）的，有可能产生错误，需要新的机制（如，同步）来协调对共享数据的访问。

抢占对于操作系统内核的设计也有影响。在处理系统调用时，内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据(如I/O队列)。

因为根据定义中断能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。操作系统需要在任何时候都能够接收中断，否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问，在进入时就要禁止中断，而在退出时要重新允许中断。

5.1.4 分派程序

分派程序（ dispatch）是一个模块，用来将CPU的控制交给由短期调度程序选择的进程。

其功能包括 ：

切换上下文

切换到用户模式

跳转到用户程序的合适位置，以重新启动程序。

分派程序停止一个进程而启动另一个所花的时间成为 分派延迟 。

5.2 调度准则

为了比较CPU调度算法所提出的准则：

CPU使用率

需要使CPU尽可能忙

吞吐量

指一个时间单元内所完成进程的数量

周转时间 : 从进程提交到进程完成的时间段称为周转时间，周转时间是所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行

等待时间

在就绪队列中等待所花费时间之和

响应时间

从提交请求到产生第一响应的时间

需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。绝大多数情况下需要优化平均值，有时需要优化最大值或最小值，而不是平均值。

5.3 调度算法

5.3.1 先到先服务调度(First-Come，First-Served scheduling)

最简单的CPU调度算法是先到先服务算法（First-Come，First-Served scheduling）：先请求CPU的进程先分配到CPU。FCFS策略可以用FIFO队列来容易实现。当一个进程进入就绪队列，其PCB链接到队列的尾部。当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。

FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。当进程CPU区间时间变化很大，平均等待时间会变化很大。

比如以下例子

进程     区间时间

P1     24

P2     3

P3     3

如果按照P1 P2 P3

顺序到达，Gantt图如下:

平均等待时间：0+24+273=17

如果按P2 P3 P1

顺序到达，

平均等待时间：0+3+63=3

另外考虑在动态情况下的性能，假设有一个CPU约束进程和许多I/O约束进程，CPU约束进程会移回到就绪队列并被分配到CPU。再次所有I/O进程会在就绪队列中等待CPU进程的完成。由于所有其他进程都等待一个大进程释放CPU，这称之为 护航效果 （convoy effect）。与让较短进程最先执行相比，这样会导致CPU和设备使用率变的很低。

FCFS调度算法是 非抢占 的。对于分时系统（每个用户需要定时的等待一定的CPU时间）是特别麻烦。允许一个进程保持CPU时间过长是个严重错误。

5.3.2 最短作业优先调度(shortest-job-first scheduling,SJF)

将每个进程与下一个CPU区间段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，那么可以使用FCFS调度来处理。注意，一个更为适当地表示是最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。

比如以下例子

进程     区间时间

P1     6

P2     8

P3     7

P4     3

SJF = 0+3+9+164=7

FCFS = 0+6+14+214=10.25

SJF算法的平均等待时间最小。SJF算法的真正困难是如何知道 下一个CPU区间的长度 。对于批处理系统的长期（作业）调度，可以将用户提交作业时间所制定的进程时间极限作为长度。SJF调度经常用于 长期调度 。

它不能在短期CPU调度层次上加以实现。我们可以预测下一个CPU区间。认为下一个CPU区间的长度与以前的相似。因此通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU区间的进程来运行。 下一个CPU区间通常可预测为以前CPU去剪的测量长度的指数平均 （exponential average）。

SJF算法可能是 抢占的或非抢占的 。抢占SJF算法可抢占当前运行的进程，而非抢占的SJF算法会允许当前的进程先完成其CPU区间。抢占SJF调度有时称为 最短剩余时间优先调度（ shortest-remaining-time-first scheduling）。

比如以下例子

进程     到达时间     区间时间

P1     0     ８

P2     1     ４

P3     2     ９

P4     3     ５

根据Gantt图：

平均等待时间：

0+0+(5−3)+(10−1)+(17−2)4=264=6.5

非抢占SJF:

0+(8−1)+(12−3)+(17−2)4=7.75

5.3.3 优先级调度(priority scheduling algorithm)

SJF算法可作为通用的优先级调度算法的一个特例。每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。SJF，其优先级（p）为下一个CPU区间的倒数。CPU区间越大，则优先级越小，反之亦然。

优先级通常是固定区间的数字，如０～７，但是数字大小与优先级的高低没有定论。

对于下例，假设数字越小优先级越高

进程     区间时间     优先级

P1     10     ３

P2     1     １

P3     2     ４

P4     1     ５

P5     5     ２

平均等待时间为：

0+1+6+16+185=8.2

优先级可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。外部优先级是通过操作系统之外的准则来定义，如进程重要性等。

优先级调度可以是抢占的或非抢占的。

优先级调度算法的一个重要问题是 无限阻塞（indefinite blocking）或饥饿 （starvation）。可以运行但缺乏CPU的进程可认为是阻塞的，它在等待CPU。优先级调度算法会使某个有低优先级无穷等待CPU。

低优先级进程务求等待问题的解决之一是 老化 （aging）。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。

5.3.4 轮转法调度(round-robin,RR)

专门为分时系统设计。它类似于FCFS调度，但是 增加了抢占以切换进程 。定义一个较小的时间单元，称为 时间片 （time quantum，or time slice）。将就绪队列作为 循环队列 。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片段的CPU。

新进程增加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分派该进程。接下来将可能发生两种情况。进程可能只需要小于时间片的CPU区间。对于这种情况，进程本身会自动释放CPU。调度程序接着处理就绪队列的下一个进程。否则，如果当前运行进程的CPU区间比时间片要长，定时器会中断产生操作系统中断，然后进行上下文切换，将进程加入到就绪队列的尾部，接着CPU调度程序会选择就绪队列中的下一个进程。

RR策略的平均等待时间通常较长

比如以下例子,使用４ms时间片

进程     区间时间

P1     24

P2     3

P3     3

画出Gantt图：

平均等待时间：

0+4+7+(10−4)3=5.66

如果就绪，那么每个进程会得到1n

的CPU时间，其长度不超过q时间单元。每个进程必须等待CPU时间不会超过(n−1)×q

个时间单元，直到它的下一个时间片为止。

RR算法的性能很大程度上依赖于时间片的大小。在极端情况下，如果时间片非常大，那么RR算法与FCFS算法一样。如果时间片很小，那么RR算法称为处理器共享，n个进程对于用户都有它自己的处理器，速度为真正处理器速度的1/n。小的时间片会增加上下文切换的次数，因此，希望时间片比上下文切换时间长，事实上，绝大多数现代操作系统，上下文切换的时间仅占时间片的一小部分。周转时间也依赖于时间片的大小。

5.3.5 多级队列调度(Multilevel Queue Scheduling)

前台（交互）进程和后台（批处理）进程。这两种不同各类型的进程具有不同响应时间要求，也有不同调度需要。与后台进程相比，前台进程要有更高（或外部定义）的优先级。

多级队列调度算法将就绪队列 分成多个独立队列 。根据进程的属性，如内存大小等，一个进程被永久地分配到一个队列(低调度开销但是不够灵活)，每个队列有自己的调度算法。前台队列可能采用RR算法调度，而后台调度可能采用FCFS算法调度。

另外，队 列之间必须有调度 ，通常采用固定优先级抢占调度，例如前台队列可以比后台队列具有绝对优先值。另一种可能在队列之间划分时间片例如，前台队列可以有80%的时间用于在进程之间进行RR调度，而后台队列可以有20%的CPU时间采用FCFS算法调度进程。

5.3.6 多级反馈队列调度(Multilevel Feedback-Queue Scheduling)

与多级队列调度相反，多级反馈队列调度允许进程在队列之间移动。主要思想是根据不同CPU区间的特点以区分进程。如果进程使用过多CPU时间，那么它可能被转移到较低优先级队列。这种方案将I/O约束和交互进程留在更高优先级队列。此外，在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列。这种形式的老化组织饥饿的发生。

通常，多级反馈队列调度程序可由下列参数来定义：

• 队列数量。
• 每个队列的调度算法。
• 用以确定何时升级到更高优先级队列的方法。
• 用以确定何时降级到更低优先级队列的方法。
• 用以确定进程在需要服务时应进入哪个队列的方法。

第六章 进程同步

6.1 背景

互相协作的进程之间有 共享的数据 ，于是这里就有一个并发情况下，如何确保有序操作这些数据、维护一致性的问题，即 进程同步。

从底层到高级应用，同步机制依次有临界区、信号量、管、原程子事务。

多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称之为 竞争条件 （race condition）。

6.2 临界区（critical section）

每个进程有一个代码段（code segment）称为 临界区 （critical section），在该区中进程可能改变共同变量、更新一个表或写一个文件等。这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行。

临界资源 （Critical resource）每次只能被一个进程访问。而 临界区则是能够访问临界资源的代码片段 。

临界区问题（critical-section problem）是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区。实现请求的代码段称为进入区（entry section），临界区之后可有退出区（exit section），其他代码段成为剩余区（remainder section）。

一个典型进程Pi的通用结构：

do{
进入区
    临界区
退出区
    剩余区
}while(TRUE)

临界区问题的解答必须满足三项要求：

（1） 互斥 （mutual exclusion）：

如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行；

（2） 前进 （progress）：

如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那么不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟；

（3） 有限等待 （bounded waiting）：

从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区内的次数有上限。

一个操作系统，在某个时刻，可同时存在有多个处于内核模式的活动进程，因此实现操作系统的内核代码，会存在竞争条件。内核开发人员有必要确保其操作系统不会产生竞争条件。

有两种方法用于处理操作系统内的临界区问题：

抢占内核（preemptive kernel）与非抢占内核 （nonpreemptive kernel）：

抢占内核允许处于内核模式的进程被抢占。

非抢占内核不允许内核模式的进程被抢占。

非抢占内核的内核数据结构从根本上不会导致竞争条件，对于抢占内核需要认真设计以确保其内核数据结构不会导致竞争条件。

但抢占内核更受欢迎，因为抢占内核更适合实时编程，因为它能允许实时进程抢占处于内核模式运行的其他进程。再者，抢占内核的响应更快，因为处于内核模式的进程在释放CPU之前不会运行过久。

6.3 Peterson算法

Peterson算法是一种经典的基于 软件 的临界区问题算法，可能现代计算机体系架构基本机器语言有些不同，不能确保正确运行。

Peterson算法适用于两个进程在临界区与剩余区间交替执行,为了方便，当使用Pi时，Pj来标示另一个进程，即j=i−1。Peterson算法需要在两个进程之间共享两个数据项：

int turn;
boolean flag[2];

变量turn表示哪个进程可以进入其临界区，即如果turn==i，那么进程Pi允许在其临界区内执行。

数组flag表示哪个进程想要进入临界区，如果flag[i]为true，即Pi想进入其临界区。

//进程Pi的Peterson算法

do{

   flag[i]=TRUE;
   turn=j;
   while(flag[j]&&turn==j);

       临界区

   flag[i]=FALSE;

       剩余区

}while(TRUE)

可以证明，满足三项要求。

Peterson算法实际上是一种谦让的过程，即：

Pi：我已经准备好了，但是我让这次一次的turn=j，看看Pj是否要运行，如果是的话，我就让Pj先运行。

Pj也是这样的情况。

6.4 硬件同步

通过要求临界区用锁来防护，就可以避免竞争条件，即一个进程在进入临界区之前必须得到锁，而其退出临界区时释放锁。

do{
请求锁
    临界区
释放锁
    剩余区
}while(TRUE)

硬件特性能简化编程任务且提高系统效率。

对于单处理器环境，临界区问题可简单地加以解决：在修改共享变量时要禁止中断出现。这样其他指令不可能执行，所以共享变量也不会被意外修改。这种方法通常为抢占式内核所采用。

在多处理器环境下，这种解决方法是不可行的，低效且影响系统时钟。

特殊硬件指令以允许能 原子地（ 不可中断的）检查和修改字的内容或交换两个字的内容。如TestAndSet()，当两个指令同时执行在不同的CPU上，那么它们会按任意顺序来顺序执行。

TestAndSet指令定义：

boolean TestAndSet(boolean *target)
{
  boolean rv=*target;
  *target=TRUE;
  return rv;
}

使用TestAndSet的互斥实现,声明一个Boolean变量lock，初始化为false

do{
    while(TestAndSetLock(&lock))
        ;//do nothing
        //critical section
    lock=FALSE;
        //remainder section
}while(TRUE);

Swap指令的定义：

void Swap(boolean *a,boolean *b)
{
  booleab temp=*a;
  *a=*b;
  *b=temp;
}

使用Swap的互斥实现：key为每个进程局部变量，lock为全局变量,初始化为false

do{

key=TRUE;

while(key==TRUE)

Swap(&lock,&key);

//critical section

lock=FALSE;

//remainder section

}while(TRUE);

这些算法解决了互斥，但是并没有解决有限等待要求，因为所有的程序执行都是随机执行的问题。

下面介绍的使用TestAndSet的算法，该算法满足所有的临界区的三个要求。

公用的数据结构如下

boolean waiting[i] = TRUE;

boolean lock;

初始化均为false。

do{
  waiting[i]=TRUE;
  key=TRUE;
  while(waiting[i]&&key)
    key=TestAndSet(&lock);
  waiting[i]=FALSE;
    //critical section
  j=(i+1)%n;
  while((j!=i)&&!waiting[j])
    j=(j+1)%n;
  if(j==i)
    lock=FALSE;
  else
    waiting[j]=FALSE
    //remainder section
}while(TRUE);

为了满足有限等待，当一个进程退出其临界区时，它会循环地扫描数组waiting[i]并根据这一顺序而指派第一个等待进程作为下一个进入临界区的进程。因此，任何等待进入临界区的进程只需要等待n−1次。

然而，对于硬件设计人员，在多处理器上实现原子指令TestAndSet并不简单。

6.5 信号量(semaphore)

应用层面解决临界区问题： 信号量

信号量S是个整数变量，除了初始化外，它只能通过两个标准原子操作： wait()和signal()来访问。即P和V 。

wait()就是等待资源的过程，定义可表示为：

wait(S)
{
  while(S<=0)
    ;//no-op
  S--;
}

signal()就是释放资源的过程，定义可表示为：

signal(S)
{
  S++;
}

在wait()和signal()操作中，对信号量整型值的修改必须不可分地执行。即当一个进程修改信号量值时，不能有其他进程同时修改同一信号量的值。另外，对于wait(S)，对于S的整数值测试(S≤0)和对其可能的修改(S–)，也必须不被中断地执行。

6.5.1 用法

通常操作系统区分 计数信号量 和 二进制信号量 。计数信号量的值域不受限制，而二进制信号量的值只能为0或1,有的系统，将二进制信号量成为 互斥锁 。

由于二进制信号量是互斥的，因而可以将其应用于处理多进程的临界区问题：这n个进程共享信号量mutex，初始值1。结构如下

do
{
  wait(mutex);
    //critical section
  signal(mutex);
    //remainder section
}while(TRUE);

计数信号量可以用来控制访问具有若干个实例的某种资源。该信号量初始化为可用资源的数量。当每个进程需要使用资源时，需要对该信号量执行wait()操作。当进程释放资源时，需要对该信号执行signal()操作。

可以用信号量来解决各种同步问题。如先执行Pi的S1语句，然后再执行Pj的S2语句，可以通向一个信号量，初始化为0。

进程P1中插入语句：

S1;
signal(synch);

在进程P2中插入语句：

wait(synch);
S2;

因为初始化synch为0，P2

只有在P1调用signal(synch)，即(S1)之后，才会执行S2。

6.5.2 实现

信号量的主要缺点是要求 忙等待 （busy waiting）。即在进入代码段中连续地循环。忙等待浪费了CPU时钟，这种类型的信号量也称为 自旋锁 （spinlock），这是因为进程在其等待锁的时还在运行(自旋锁有其优点，进程在等待锁时不进行上下文切换，而上下文切换可能需要花费相当长的时间。因此如果锁占用的时间短，那么锁就有用了，自旋锁常用于多处理器系统中，这样一个线程在一个处理器自旋时，另一线程可在另一个处理器上在其临界区内执行).

为克服这一缺点，修改wait()和signal()的定义，信号量值不为正时，不是忙等而是 阻塞 自己，阻塞操作将一个进程放入到与信号量相关的等待队列中，并将该进程的状态切换成等待状态，接着，控制转到CPU调度程序，以选择另一个进程来执行，从而使CPU占用率变高。

被阻塞在等待信号Ｓ上的进程，可以在其他进程执行signal()的时候操作之后重新被执行，该进程的重新执行是通过wakeup()操作来进行的将进程从等待状态切换到就绪状态。接着进程被放到就绪队列中。

因而将信号量定义为如下：

typedef struct
{
    int value;                  //记录了这个信号量的值   
    struct process *list;       //储存正在等待这个信号量的进程（PCB链表指针）
}semaphore;

每个信号量都有一个整型值和一个进程链表，当一个进程必须等待信号量时，就加入到进程链表上，操作signal()会从等待进程链表中取一个进程以唤醒。

wait()实现：

wait(semaphore *S)
        {
  S->value--;
  if(S->value<0)                  //没有资源
  {
  add this process to S->list;      //进入等待队列  
  block();                          //堵塞
  }
}

signal()实现：

signal(semaphore *S)
{
    S->value++;
    if(S->value<=0)
    {                  //上面++后，S仍然还<=0，说明资源供不应求，等待者还有很多，于是唤醒等待队列中的一个
        remove a process P from S->list;
        wakeup(P);                        //切换到就绪状态  
    }
}

操作block()挂起调用他的进程。

操作wakeup(P)重新启动阻塞进程Ｐ的执行。

这两个操作都是由操作系统作为基本系统调用来提供的。

在具有忙等的信号量经典定义下，信号量的值绝对不能为负数，但是本实现可能造成信号量为负值。 如果信号量为负值，那么其绝对值就是等待该信号量的进程的个数。

等待进程的链表可以利用进程控制块PCB中的一个链接域来加以轻松实现。即每个信号量包括一个整型值和一个PCB链表的指针。

信号量的关键之处是它们原子的执行。必须确保没有两个进程能同时对一个信号量进行操作，在单处理器情况下，可以在执行wait()和signal()的时候简单的关闭中断，保证只有当前进程进行。

多处理器下，若禁止所有CPU的中断，则会严重影响性能，SMP系统必须提供其他加锁技术（如自旋锁），以确保wait()与signal()可原子地执行。

6.5.3 死锁与饥饿

具有等待队列的信号量的实现可能会导致这样的情况：

两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。这里的事件是signal()操作的执行。当出现这样的状态时，这些进程就称为死锁（deadlocked）。

例如，一个由P1

和P2组成的系统，每个都访问共享的信号量Ｓ和Ｑ，Ｓ和Ｑ初值均为１。

P0:

wait(S);
wait(Q);
//......
signal(S);
signal(Q);

P1:

wait(Q);
wait(S);
//......
signal(Q);
signal(S);

假设，P0执行wait(S)，接着P1执行wait(Q)，P0再执行wait(Q)时，必须等待，直到P1执行signal(Q)，而此时P1也在等待P0执行signal(S)，两个操作都不能进行，P0和P1就死锁了。

与死锁相关的另一个问题是 无限期阻塞（indefinite blocking）或饥饿 （starvation）：即进程在信号量内无限期等待。

举个例子来理解死锁与饥饿的区别：

死锁(deadlock)

指的是两个或者两个以上的进程相互竞争系统资源，导致进程永久阻塞。

例如：

1、桌子上有慢慢一桌子的美食，但是只有一双筷子。

2、甲拿了一根，然后在找另一根。

3、乙拿了一根，然后也在找另一根。

4、因为他们都掌握了对方必需的资源，导致最后他们俩谁都吃不到美食。

饥饿(starvation)

指的是等待时间已经影响到进程运行，此时成为饥饿现象。如果等待时间过长，导致进程使命已经没有意义时，称之为“饿死”。

例如：

1、小明要告诉妈妈明天开家长会。

2、小明妈妈因为工作太忙，在公司加班，没有回家。

3、于是第二天，小明的妈妈就错过了家长会。（“饿死”）

4、其实小明的妈妈没有出现“死锁”。只是小明的优先级过低，不如工作重要。

6.6 经典同步问题

6.6.1 有限缓存问题—生产者消费问题：

假设缓冲池有n个缓冲项，每个缓冲项能存在一个数据项。信号量mutex提供了对缓冲池访问的互斥要求，并初始化为1。信号量empty和full分别用来表示空缓冲项和满缓冲项的个数，信号量empty初始化为n；而信号量full初始化为0

生产者进程结构：

do
{
  …
  //produce an item in next p
…
wait(empty);
wait(mutex);
…
//add next p to buffer
…
signal(mutex);
signal(full);
}while(TRUE);

消费者进程结构：

do
{
wait(full);
wait(mutex);
…
//remove an item from buffer to next c
…
signal(mutex);
signal(empty);
…
//consume the item in next c
…
}while(TRUE);

6.6.2 读者-写者问题

只读数据库的进程称为读者；更新（读和写）数据库的称为写者。

第一读者-写者问题：要求没有读者需要保持等待除非已有一个写者已获得允许已使用共享数据库。换句话说，没有读者会因为一个写者在等待而会等待其他读者的完成。

第二读者-写者问题：要求一旦写者就绪，那么写者会尽可能快得执行其写操作。换句话说，如果一个写者等待访问对象，那么不会有新读者开始读操作。

对于这两个问题的解答可能导致饥饿问题。对第一种情况，写者可能饥饿；对第二种情况，读者可能饥饿。

对于第一读者－写者问题的解决:

读者进程共享以下数据结构：

semaphore mutex, wrt;
int readcount;

信号量mutex和wrt初始化为1，readcount初始化为0，信号量wrt为读者和写者进程所共有。信号量mutex用于确保在更新变量readcount时的互斥。变量readcount用来跟踪有多少进程正在读对象。信号量wrt供写者作为互斥信号量，它为第一个进入临界区和最后一个离开临界区的读者所使用，而不被其他读者所使用。

写者进程结构：

do
{
  wait(wrt);
  …;
  //writing is performed
  …;
  signal(wrt);
}while(TRUE);

读者进程结构：

do
{
    wait(mutex);
    readcount++;
    if(readcount==1)
    wait(wrt);
    signal(mutex);
    …;
    //reading is performed
    …;
    wait(mutex);
    readcount--;
    if(readcount==0)
        signal(wrt);
    signal(mutex);
}while(TRUE);

推广为读写锁。

在以下情况下最为有用：

一是，当可以区分哪些进程只需要读共享数据，哪些进程只需要写共享数据；

二是，当读者进程数比写进程多时。

6.6.3 哲学家进餐问题

拿起与他相近的两只筷子，一个哲学家一次只能拿起一只筷子，同时有两只筷子时，就能吃，吃完，会放下两只筷子。

一种简单的方法，每只筷子都用一个信号量来表示。一个哲学家通过执行wait()操作试图获取相应的筷子，他会通过执行signal()操作以释放相应的筷子。

共享数据为：semaphore chopstick[5];其中所有chopstick的元素初始化为1。

哲学家i的结构：

do
{
  wait(chopstick[i]);
  wait(chopstick[(i+1)%5]);
  …;
  //eat
  …;
  signal(chopstick[i]);
  signal(chopstick[(i+1)%5]);
  …;
  //think
  …;
}while(TRUE);

但这种方法会发生死锁，例如，所有哲学家同时饥饿，且同时拿起左边的筷子。

多种可以解决死锁的方法：

①最多只允许4个哲学家同时坐在桌子上；

②只有两只筷子都可用时才允许一个哲学家拿起它们（他必须在临界区内拿起两只筷子）；

③使用非对称解决方法，即技术哲学家先拿起左边的筷子，接着拿起右边的筷子，而偶数哲学家先拿起右边的筷子，接着拿起左边的筷子。

第七章 死锁

所有申请的资源都被其他等待进程占有，那么该等待进程有可能在无法改变其状态，这种情况称为 死锁 （deadlock）。

7.1 系统模型

进程在使用资源之前必须先申请资源，在使用资源之后要释放资源。进程所申请的资源数量不能超过系统所有资源的总量。

某系统拥有一定数量的资源，分布在若干竞争进程之间。这些资源可以分成多种类型，每种类型有一定数量的实例。

在正常操作模式下，进程只能按如下顺序使用资源 ：

• ①申请：如果申请不能立即被允许，那么申请进程必须等待，直到它获得该资源为止。
• ②使用：进程对资源进行操作。
• ③释放：进程释放资源

资源的申请与释放为 系统调用 。其他资源的申请与释放可以通过信号量的wait与signal操作或通过互斥锁的获取与释放来完成。因此对于进程和线程的每次使用，操作系统会检查以确保使用进程已经申请并获得了资源。

系统表记录了每个资源是否空闲或已被分配，分配给了哪个进程。如果进程正在申请的资源正在为其他进程所使用，那么该进程会增加到该资源的等待队列。

当一组进程的每个进程都在等待一个事件，而这个事件只能由这一组进程的另一个进程所引起，那么这组进程就处于死锁状态 。

死锁也可设计不同的资源类型。多线程可能因为竞争共享资源而容易产生死锁。

7.2 死锁特征

当出现死锁时，进程永远不能完成，并且系统资源被阻碍使用，阻止了其他作业开始执行。

7.2.1 必要条件

如果在一个系统中下面四个条件同时满足，那么会引起死锁。

（1） 互斥(mutual exclusion)：至少有一个资源必须处于非共享模式，即一次只有一个进程使用，如果另一个进程申请该资源，那么申请进程必须等到该资源被释放为止。

（2） 占有并等待(hold and wait)：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。

（3） 非抢占(no preemption)：资源不能被抢占，即资源只能在进程完成任务后自动释放。

（4） 循环等待(circular wait)：有一组等待进程｛P0,P1,P2,P3…,Pn｝,P0等待的资源被P1等待，P１等待的资源被P2所占有，……，Pn−1等待的资源为Pn所占有，Pn所等待的资源被P0所占有。

４个条件必须同时满足才会出现死锁，循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。

7.2.2 资源分配图

死锁问题可用称为系统资源分配图的有向图进行更为精确地描述。

这种图由一个节点集合Ｖ和一个边集合Ｅ组成。节点集合Ｖ可以分成两种类型的节点：

Ｐ＝｛P1，P2，…，Pn｝（系统活动进程的集合）

Ｒ＝｛R1，R2，…，Rn｝（系统所有资源的集合）

Pi→Rj

表示进程Pi已经申请了资源类型为Rj的一个实例，称为申请边

Rj→Pi

表示资源类型Rj已经分配给进程Pi，称为分配边

如一个分配图的例子如下：

有一个R1、R3的资源，有两个R2的资源，有三个R4的资源。

可以证明：

• 如果分配图没有环，那么系统就没有进程死锁。如果分配图有环，那么可能存在死锁。
• 如果每个类型只有一个实例，环是死锁存在的充分必要条件。不过每个类型不止一个实例，环是死锁的必要条件。

存在死锁的资源分配图：

存在环但是没有死锁的资源分配图:

7.3 死锁处理方法

有三种方法：

• 可使用协议以 预防或避免 死锁，确保系统不会进入死锁状态。
• 可允许系统进入死锁状态，然后检测它，并加以 修复 。
• 可忽略这个问题，认为死锁不可能在系统内发生。

这里第三种方法为绝大多数操作系统所用，因此应用程序开发人员需要自己来处理死锁。

为了确保死锁不会发生，系统可以采用死锁预防或死锁避免方案

死锁预防 （deadlock prevention）是一组方法，以确保至少一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。

死锁避免 （deadlock avoidance）要求操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息，系统可以确定：对于一个申请，进程是否应等待。为了确定当前申请是允许还是延迟，系统必须考虑可用资源，已经分配给每个进程的资源，每个进程将来申请和释放的资源。

除此之外，系统还可以提供一个算法来检查系统状态来确定死锁是否发生，并提供另一个算法来从死锁中恢复。

预防死锁的副作用是降低设备的使用率和系统的吞吐率。

缺点是低设备使用率和系统吞吐率。

7.4 死锁预防（deadlock prevention）

出现死锁有四个必要条件，只要保证至少一个条件不成立，就能预防死锁的发生。

7.4.1 互斥

对于非共享资源，必须要有互斥条件（如打印机）。另一方面，共享资源不要求互斥访问，因此不会涉及死锁（如只读文件）。

故通常不能通过否定互斥条件来预防死锁，有的资源本身就是非共享的。

7.4.2 占有并等待

为了确保占有并等待条件不会在系统内出现，必须保证： 当一个进程申请一个资源时，就不能占有其他资源。

方法一：可以通过要求申请资源的系统调用在所有其使用的协议是每个进程在执行前申请并获得所有资源。他系统调用之前进行。

方法二：允许进程在没有资源时才可申请资源，一个进程可申请一些资源并使用它们，然而，在它申请更多其他资源之前，它必须释放其现已分配的所有资源。

这两种协议有两个主要缺点：

第一，资源利用率（resource utilization）可能比较低，因为很多资源可能已分配，但长时间没有被使用。

第二，可能发生饥饿。一个进程如需要多个常用资源，可能会永久等待，比如因为其所需要的资源中至少一个总是分配给其他的进程。

7.4.3 非抢占

为确保这一条件不成立，可使用如下协议：

即可以抢占，如果一个进程占用资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占，即这些资源被隐式地释放了。只有当进程获得其原有资源和所申请的新资源时，进程才可以重新执行。

或者说，如果一个进程申请一些资源，首先检查是否可用，如果可用就分配它们，如果不可用，那么检查这些资源是否已分配给其他等待额外资源的进程。如果是就抢占这些资源，并分配给申请进程。如果资源不可用且也不可被其他等待进程占有，那么申请进程必须等待。当一个进程处于等待时，如果其他进程申请其拥有的资源，那么该进程部分资源可以被抢占。一个进程要重新执行，他必须分配到其所申请的资源，并恢复其在等待时被抢占的资源。

这个协议通常用于状态可以保存和恢复的资源，如CPU寄存器和内存，一般不适用其他资源，如打印机和磁带驱动器。

7.4.4 循环等待

一个确保此条件不成立的方法是：对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。

设Ｒ＝｛R1，R2，R3，…，Rn｝为资源类型的的集合。为每个资源类型分配一个唯一整数来允许比较两个资源以确定其先后顺序。可定义一个函数Ｆ：R→N ,其中Ｎ是自然数集合，例如：Ｆ（tapedrive）＝1 Ｆ（diskdrive）＝5 Ｆ（printer）＝12

每个进程只按照递增顺序申请资源，即一个进程开始可以申请任意数量的资源类型为Ｒｉ的实例。之后，当且仅当Ｆ（Rj）>Ｆ（Ri）时，该进程可以申请资源Rj的实例。如果需要同一资源类型的多个实例，那么对它们必须一起申请。

例如，对于以上给定函数，一个进程如果同时需要打印机和磁带驱动器，那么就必须先申请磁带驱动器，再申请打印机。换句话说，要求当一个进程申请资源类型Rj时，必须先释放所有Ri[Ｆ（Ri）>Ｆ（Rj）]

可以使用反证法证明，使用这两个协议，那么循环等待就不可能成立。

设计一个完全排序或层析并不能防止死锁，而是要靠应用程序员来按顺序编写程序。另外函数Ｆ应该根据系统内资源使用的正常顺序来定义。例如，由于磁带通常在打印机之前使用，所以定义Ｆ（tapedrive）<Ｆ（printer）较为合理。

7.5 死锁避免（deadlock-avoidance）

避免死锁的另外一种方法是获得以后如何申请资源的附加信息。

不同的算法所要求的信息量和信息的类型上有所不同，最为简单和最为常用的模型要求每个进程说明可能需要的每种资源类型实例的最大需求。根据每个进程可能申请的每种资源类型实例的最大需求的事先信息，可以构造一个算法以确保系统绝不会进入死锁状态。这种算法定义了死锁避免（deadlock-avoidance）方法。

死锁避免算法动态地检测资源分配状态以确保循环等待条件不可能成立。资源分配状态是由可用资源和已分配资源，以及进程最大需求所决定的。

7.5.1 安全状态

如果系统能按某个顺序为每个进程分配资源（不超过其最大值）并能避免死锁，那么系统状态就是 安全的。即如果存在一个安全序列，那么系统处于安全状态。如果没有这样的顺序存在，那么系统处于不安全状态。

进程顺序{P1,P2,…,Pn}，如果对于每个Pi，Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj（其中j小于i）所占用资源，那么这一顺序称为安全序列。

在这种情况下，进程Pi所需要的资源即使不能立即使用，那么Pi等待直到所有Pj释放其资源，当它们完成时，Pi可得到其所需要的所有资源，完成其给定任务。

安全状态不是死锁状态，相反，死锁状态是不安全状态。然而，不是所有不安全状态都能够导致死锁状态。

只要状态为安全，操作系统就能避免不安全（和死锁）状态。在不安全情况下，操作系统不能阻止进程以会导致死锁的方式申请资源。进程行为控制了不安全状态。

例如考虑一个系统，有12台磁带驱动器和三个进程P0,P1,P2,目前状况如下表：

进程     最大需求     当前需求

P0           10                 5

P1            4                  2

P2            9                  2

顺序｛P1，P0，P2｝满足安全条件，因为：

对于P1,2小于3

对于P0,5小于等于2+3

对于P2,7小于5+2+3

系统可以从安全状态转变为不安全状态，加入某时刻，进程P2申请并又得到了一台磁带驱动器，系统就不再安全了。

进程     最大需求     当前需求

P0     10     5

P1     4     2

P2     9     3

此时P0还需要5台，但是系统只剩４台了，必须等待，同时P2还需要６台，也必须等待，由此导致了死锁。造成这个错误的原因即允许P2

再获取了一台磁带驱动器。

有了安全状态的概念，可定义避免算法确保系统不会死锁，即确保系统处于安全状态，开始，系统处于安全状态，当进程申请一个可用资源时，系统必须确定这一资源申请是可以立即分配还是要等待，即便现在资源可用，也只有分配后系统仍处于安全状态，才允许申请。

也因此采用这种方法和没有采用死锁避免算法相比资源使用率可能更低。

7.5.2 资源分配图算法

利用资源分配图，引入需求边Pi→Rj

表示进程Pi可能在将来某个时候申请资源Rj。只有申请边变为分配边而不会导致资源分配图形成环时，才允许申请。

如果没有环存在，那么会使得系统处于安全状态，如果有环存在则分配会导致系统处于不安全状态。

例如：

假如进请资源程P2申R2。虽然R2现在可用，但是不能分配给P2，因为这会创建一个环，环表示系统处于不安全状态，如果P1再申请R2就会造成死锁。

7.5.3 银行家算法

银行家算法 ：对于每种资源类型有多个实例的资源分配系统，资源分配图就不再适用。使用银行家算法，但是效率比资源分配图方案低。

当新进程进入系统时，它必须说明其可能需要的各种类型资源实例的最大数量，这一数量不能超过当前系统资源的总和。当用户申请一组资源时，系统必须确定这些资源的分配是否仍会使系统出于安全状态，如果是，就分配资源；否则，进程必须等待直到某个其他进程释放足够资源为止。

实现银行家算法，必须有几个数据结构：Available，Max，Allocation，Need。

这些数据结构对资源分配系统的状态进行了记录。设ｎ为系统的进程的个数，ｍ为资源类型的种类：

Available ：长度为m的向量，表示每种资源类型的现有实例的数量。如果Available[j] = k，则说明资源类型Rj有现有ｋ个实例。

Max ：ｎ×ｍ矩阵，定义每个进程的最大需求，如果Max[ｉ][ｊ] = k，那么进程Pi最多申请ｋ个资源类型Rj的实例。

Allocation ：ｎ×ｍ矩阵，定义每个进程现在所分配的各种资源类型的实例数量，例如Allocation[ｉ][ｊ] = k，那么进程Pi现在已经分配了ｋ个资源类型Rj的实例。

Need ：ｎ×ｍ矩阵，表示每个进程还需要的剩余的资源。如果Need[ｉ][ｊ] = k，那么进程Pi还需要申请ｋ个资源类型Rj的实例。并且Need[ｉ][ｊ] = Max[ｉ][ｊ] - Allocation[ｉ][ｊ]

这些数据结构的大小和值会随着时间而改变。

为了简化银行家算法的描述：

设Ｘ，Ｙ为长度为n的向量，那么X≤Y 当且仅当对所有的i=1,2,3…,n，X[i]≤Y[i]，如果X≤Y 并且Ｘ!=Ｙ,那么Y小于X。

可以将矩阵Allocation 和Need的每行作为向量，并分别用Allocationi 和Needi来表示。

向量Allocationi表示分配给进程Pi的资源，Needi表示进程Pi

为完成其任务可能仍然需要申请的额外资源。

1.安全性算法

确定计算机是否处于安全状态需要以下几步：

• 1 创建Work 和 Finish 向量，长度分别为m,n，并且Work = Avallable，将Finish的每一项置为false
• 2 查找是否存在这样的i使得满足：

Finish[i] = false

Needi <= Work

如果不存在则跳到第四步。

• 3

Work = Work + Allocationi

Finish[i] = true

跳回第二步

• 4 如果对所有的ｉ，Finish[i] = true,那么系统处于安全状态。

资源请求算法

设Requesti为进程Pi的请求向量。即如果Requesti[j]==k ，那么Pi所需要资源类型Rj的实例数量为k。

当进程Pi做出资源申请时，采取如下动作：

1 如果Requesti<Needi，那么进行下一步，否则产生出错条件，因为已经超过了其最大请求。

2 如果Requesti<Available，那么进行下一步，否则Pi必须等待，因为没有可用的资源。

3 假定系统可以分配给进程Pi所需的资源，并按如下方式修改状态：

Available=Available−Requesti

Allocationi=Allocationi+Requesti

Needi=Needi−Requesti

如果所产生的资源分配状态是安全的，那么交易完成且进程Pi可分配到其所需要的资源。

然而，如果新状态不安全，那么进程Pi必须等待Requesti并回复到原资源分配状态。

7.7 死锁恢复

一种措施是通知操作员死锁已发生，以便操作人员人工处理死锁。

另一种措施是让系统从死锁状态中 自动恢复 过来。

打破死锁有两种方法：

• 一个方法是简单地终止或多个进程以打破循环等待。
• 另一个方法是从一个或多个死锁进程那里抢占一个或多个资源。

进程终止：

• 一是，终止所有死锁进程，这种方式虽然终止了死锁循环，代价太大。
• 二是，一次只终止一个进程直到取消死锁循环为止，这种方法的开销会很大，因为每次终止一个进程，就需要调用死锁检测算法以确定进程是否仍处于死锁。

资源抢占：

这里有三个问题需要处理：

①选择一个牺牲品：抢占哪些资源和哪个进程？必须确定抢占顺序以使代价最小化。

②回滚：如果从一个进程那里抢占一个资源，那么应对该进程做些什么安排？必须将这个进程回滚到某个安全状态，以便以后重启进程。

最简单的方法是完全回滚：终止进程并重新执行。更为有效的方法是将进程回滚到足够打破死锁。另一方面，这种方法要求系统维护有关运行进程状态的更多信息。

③饥饿：如何确保不会发生饥饿？最为常用的方法是在代价因素中加上回滚次数。

第八章 内存管理

8.1 背景

内存是现代计算机运行的中心。内存有很大一组字或字节组成，每个字或字节都有它们自己的地址。CPU根据程序计数器（PC）的值从内存中提取指令，这些指令可能会引起进一步对特定内存地址的读取和写入。

一个典型指令执行周期，首先从内存中读取指令。接着该指令被解码，且可能需要从内存中读取操作数。在指令对操作数执行后，其结果可能被存回到内存。内存单元只看到地址流，而并不直到这些地址是如何产生的（由指令计数器、索引、间接寻址、实地址等）或它们是什么地址（指令或数据）。

8.1.1 基本硬件

CPU所能直接访问的存储器只有 内存和处理器内的寄存器 。机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。如果数据不在内存中，那么CPU使用前必须先把数据移到内存中。

CPU内置寄存器通常可以在一个CPU时钟周期内完成访问。对于寄存器的内容，绝大多数CPU可以在一个时钟周期内解析并执行一个或多个指令，而对于内存就不行。完成内存访问需要多个CPU时钟周期，由于没有数据以便完成正在执行的指令，CPU通常需要暂停（stall）。由于内存访问频繁，这种情况是难以忍受的，解决方法是在CPU与内存之间增加高速内存。这种协调速度差异的内存缓冲区，称为 高速缓存 （cache）。（这一方面是计算机组成原理的内容）

除了保证访问物理内存的相对速度之外，还要确保操作系统不会被用户进程所访问，以及确保用户进程不会被其他用户进程访问。这种保护可通过硬件来实现，硬件实现由许多方法，将在之后讨论。

其中一种可能方案为：

首先确保每个进程都有独立的内存空间，为此，需要确定进程 可访问的合法地址的范围 ，并确保进程只能访问其合法地址。通过基 地址寄存器（base register）和界限地址寄存器 （limit register）可以实现这种保护。

基地址寄存器（base register）含有最小的物理内存地址，界限地址寄存器（limit register）决定了范围的大小。例如：如果基地址寄存器为300040而界限寄存器为120900，那么程序可以访问从300040到420940的所有地址。

这里写图片描述

内存空间保护的实现，是通过CPU硬件对用户模式所产生的每个地址与寄存器的地址进程比较来完成的。如果访问了不该访问的地址，则会陷入到操作系统中，并作为致命错误处理。

只有操作系统可以通过特殊的 特权指令 来加载基地址寄存器和界限地址寄存器。由于特权指令只可在内核模式下执行，而只有操作系统在内核模式下执行，所以只有操作系统可以加载基地址寄存器和界限地址寄存器。这种方案允许操作系统修改两个寄存器的值，而不允许用户程序去修改他们。

操作系统在内核模式下，可以无限制地访问操作系统和用户内存。因此操作系统可以将用户程序装入用户内存，在出错时输出这些程序，访问并修改系统调用的参数等。

8.1.2 地址绑定

通常，程序以二进制可执行文件的形式存储在磁盘上。为了执行，程序被调入内存并放入进程空间内。

根据所使用的内存管理方案，进程在执行时，可以在磁盘和内存之间移动。在磁盘上等待调入内存以便执行的进程形成 输入队列 （input queue）。

通常的步骤是从输入队列中选取一个进程并装入内存。进程在执行时，会访问内存中的指令和数据。最后，进程终止，其地址空间将被释放。

许多系统允许用户进程放在物理地址的任意位置。这种组合方式会影响用户程序能够使用的地址空间。在绝大多数情况下，用户程序在执行前，会经过好几个步骤，在这些步骤中，地址可能有不同的表示形式，源程序中的地址通常是用符号（如count）来表示，编译器通常将这些符号地址绑定（bind）在可重定位的地址（如：从本模块开始的第14字节）。链接程序或加载程序再将这些可重定位的地址绑定成绝对地址（如74014）。每次绑定都是从一个地址空间到另一地址空间的映射。

通常，将指令与数据绑定到内存地址有以下几种情况：

编译时 （compile time）：如果编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码（absolute code）。如果将来开始地址发生变化，那么就必须重新编译代码。

加载时 （load time）：当编译时不知道进程将驻留在内存的什么地方，那么编译器就必须生成可重定位代码（reloadable code）。绑定会延迟到加载时才进行。如果开始地址发生变化。只需要重新加载用户代码已引入改变值。

执行时（ execution time）：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才发生。绝大多数通用计算机操作系统采用这种方法。

8.1.3 逻辑地址空间和物理地址空间

生成的地址通常称为 逻辑地址 （logical address），而内存单元所看到的地址（即加载到内存地址寄存器（memory-address register）中的地址）通常称为 物理地址 （physical address）。

编译和加载时的地址绑定方法生成相同的逻辑地址和物理地址。但是，执行时的地址绑定方案导致不同的逻辑地址和物理地址。对于这种情况，通常称逻辑地址为 虚拟地址 （virtual address）。由程序所生成的所有逻辑地址称为 逻辑地址空间 （logical address space），与这些逻辑地址相对应的物理地址的集合称为 物理地址空间 （physical address space）。

运行时从 虚拟地址 到 物理地址 的映射由被称为 内存管理单元 （memory-management unit，MMU）的硬件设备来完成。有很多可选择的方法来完成这种映射，如使用一个简单的MMU方案来实现这种映射，这是一种基地址寄存器方案的推广，基地址寄存器在这里称为重定位寄存器（relocation register），用户进程所生成的地址在送交内存之前，都加上重定位寄存器的值。

假如，基地址为14000，那么用户对地址346的访问将映射为地址14346。

用户程序绝对不会看到真正的物理地址。如，程序可以创建一个指向位置346的指针，将他保存在内存中，使用它，与其他地址进行比较等等，所有这些操作都是基于346进行的。只有当它作为内存地址时（例如，在简介加载和存储时），它才进行相对于基地址寄存器的重定位。用户程序处理逻辑地址时，内存映射硬件将逻辑地址转变为物理地址。所引用的内存地址只有在引用时才最后定位。

逻辑地址空间绑定到单独的一套物理地址空间，这一概念对内存的管理至关重要。

8.1.4 动态加载（dynamic loading）

一个进程的整个程序和数据如果都必须处于物理内存中，则进程的大小受物理内存大小的限制。

为了获得更好的内存空间使用率，使用 动态加载 （dynamic loading），即一个子程序只有在调用时才被加载。

所有的子程序都以可重定位的形式保存在磁盘上。主程序装入内存并执行。当一个子程序需要调用另外一个子程序的时候，调用子程序首先检查另一个子程序是否已经被加载。如果没有，可重定位的链接程序将用来加载所需要的子程序，并更新程序的地址表以反应这一变化。接着控制传递给新加载的子程序。

动态加载的优点是不用子程序绝不会被加载，如果大多数代码需要用来处理异常情况，如错误处理，那么这种方法特别有用。对于这种情况，虽然总体上程序比较大，但是所使用的部分可能小很多。

动态加载不需要操作系统提供特别的支持。利用这种方法来设计程序主要是用户的责任。

8.1.5 动态链接（dynamically linking）与共享库

有的操作系统只支持 静态链接 （static linking）此时系统语言库的处理与其他目标模块一样，由加载程序合并到二进制程序镜像中。

动态链接的概念与动态加载相似。只是这里不是将 加载延迟到运行时 ，而是将 链接延迟到运行时 。这一特点通常用于系统库，如语言子程序库。没有这一点，系统上的所有程序都需要一份语言库的副本，这一需求浪费了磁盘空间和内存空间。

如果有动态链接，二进制镜像中每个库程序的应用都有一个 存根 （stub）。存根是一小段代码，用以指出如何定位适当的内存驻留的库程序，或如果该程序不在内存中应如何安装入库。不管怎样，存根会用子程序地址来代替自己，并开始执行子程序。因此，下次再执程序代码时，就可以直接进行，而不会因动态链接产生任何开销。采用行该子这种方案，使用语言库的所有进程只需要一个库代码副本就可以了。

动态连接也可用于库更新。一个库可以被新的版本所替代，且使用该库的所有程序会自动使用新的版本。没有动态链接，所有这些程序必须重新链接以便访问。

为了不使程序错用新的、不兼容版本的库，程序和库将包括版本信息。多个版本的库都可以装入内存，程序通过版本信息来确定使用哪个库副本。

因此，只有用新库编译的程序才会收到新库的不兼容变化影响。在新程序装入之前所链接的其他程序可以继续使用老库。这种系统也称为共享库。

与动态加载不同， 动态链接通常需要操作系统帮助 。如果内存中的进程是彼此保护的，那么只有操作系统才可以检查所需子程序是否在其他进程内存空间内，或是允许多个进程访问同一内存地址。

8.3 连续内存分配（contiguous memory allocation）

内存必须容纳 操作系统 和 各种用户进程 ，因此应该尽可能有效地分配内存的各个部分。

内存通常分为两个区域：一个用于驻留 操作系统 ，一个用于 用户进程 。操作系统可以位于低内存或高内存，影响这一决定的主要因素是 中断向量 的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统放到 低内存 。

通常需要将多个进程同时放入内存中，因此需要考虑如何为输入队列中需要调入内存的进程分配内存空间。

采用 连续内存分配 （contiguous memory allocation）时，每个进程位于一个连续的内存区域。

8.3.1 内存映射与保护

通过采用 重定位寄存器 和 界限地址寄存器 可以实现保护。

重定位寄存器含有最小的物理地址值；界限地址寄存器含有逻辑地址的范围值。

这样每个逻辑地址必须小于界限地址寄存器。MMU动态第将逻辑地址加上重定位寄存器的值后影射成物理地址。映射后的物理地址再送交内存单元。

当CPU调度器选择一个进程来执行时，作为上下文切换工作的一个部分，调度程序会用正确的值来初始化重定位寄存器和界限地址寄存器，由于CPU所产生的每一地址都需要与寄存器进程核对，所以可以保证操作系统和其他用户程序和数据不受该进程运行所影响。

重定位寄存器机制为允许操作系统动态改变提供了一个有效方法。如某驱动程序（或其他操作系统服务）不常使用便可以不必在内存中，这类代码有时称为暂时（transient）操作系统代码，它们根据需要调入或调出。因此，使用这种代码可以在程序执行时动态改变操作系统的大小。

8.3.2 内存分配

最简单的内存分配方法之一是将内存分为多个 固定大小 的分区（partition）。每个分区只能容纳一个进程。那么多道程序的程度会受分区数限制。如果使用这种 多分区方法 （multiple-partition method），当一个分区空闲时，可以输入队列中选择一个进程，以调入到空闲分区。当进程终止时，其分区可以被其他进程所使用。这种方法现在已不再使用。对于固定分区方案的推广（称为MVT），它主要用于批处理环境。也可用于纯分段内存管理的分时操作系统。

在 可变分区 （variable-partition）方案中，操作系统有一个表，用于记录那些内存可用和哪些内存已被占用。一开始，所有内存都可用于用户进程，因此可以作为一大块可用内存，称为 孔 （hole），当新进程需要内存时，为该进程查找足够大的孔，如果找到，可以从该孔进程分配所需的内存，孔内未分配的内存可用于下次再用。

随着进程进入系统，它们将被加入输入队列中。操作系统根据调度算法来对输入队列进行排序。内存不断地分配给进程，直到下一个进程的内存需求不能满足为止，如果没有足够大的孔来装入进程，操作系统可以等到有足够大的空间，或者往下扫描输入队列以确定是否其他内存需求较小的进程可以被满足。

通常，一组不同大小的孔分散在内存中。当新进程需要内存时，系统为进程查找足够大的孔。如果孔太大，那么就分成两块：一块分配给新进程，另一块还回到孔集合，当进程终止时，它将释放其内存，改内存将还给孔集合。如果孔与其他孔相邻，那么将这些孔合并为大孔。这时，系统可以检查是否有进程在等待内存空间，新合并的内存空间是否满足等待进程。

这种方法是通用动态存储分配问题的一种情况（根据一组空闲孔来分配大小为n的请求），这个问题有许多解决方法。从一组可用孔中选择一个空闲孔的最为常用方法有 首次适应 （first-fit）（第一个对够大的孔）、 最佳适应 （best-fit）（最小的最够大的孔）、 最差适应 （worst-fit）（分配最大的孔）。

首次适应 （first-fit）：分配第一个足够大的孔，查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲孔，就可以停止。

最佳适应 （best-fit）：分配最小的足够大的孔。必须查找整个列表，除非列表按照大小排序。这种方法可以产生最小剩余孔。

最差适应 （worst-fit）：分配最大的孔，同样必须查找整个列表，除非列表按照大小排序。这种方法可以产生最大剩余孔。该孔可能比最佳适应方法产生的最小剩余孔更有用。

模拟结果显示：首次适应和最佳适应方法在执行时间和利用空间方面都好于最差适应方法。首次适应和最佳适应方法在利用空间方面难分伯仲，首次适应方法更快些。

8.3.3 碎片（fragmentation）

首次适应和最佳适应算法都有 外部碎片问题 （external fragmentation）。随着进程装入和移出内存，空闲内存空间被分割为小分段，

当所有总的空用内存之和可以满足请求，但并不连续时，这就出现了外部碎片问题。最坏的情况下，每两个进程之间就有空闲块（或浪费）。如果这些内存是一整块，那么就可以再运行多个进程。

在首次适应和最佳适应之间的选择可能会影响碎片的量。另一个影响因素是从空闲块的哪端开始分配。不管使用哪种算法，外部碎片始终是个问题。

根据内存的总大小和平均进程大小的不同，外部碎片化的重要程度也不同。例如，对采用首次适应方法的统计说明，对于首次适应方法不管怎么优化，假定N个可分配块，那么可能有0.5N个块为外部碎片。即1/3内存可能不能使用，这一特性称为50%规则。

内存碎片可以是内部的，也可以是外部的。如果内存以固定大小的块为单元来分配，进程所分配的内存可能比所要的要大。这两个数字之差称为内部碎片（internal fragmentation）这部分内存在分区内，但又不能使用。

一种解决外部碎片问题的方法是 紧缩 （compaction），紧缩的目的是移动内存内容，以便所有空闲空间合并成一整块。但是紧缩并非总是可能的。如果重定位是静态的，并且在汇编时或装入时进行的，那么就不能紧缩。 紧缩仅在重定位是动态的并在运行时可采用 。如果地址被动态重定位，可以首先移动程序和数据，然后再跟据新基地址基地的值来改变址寄存器。如果采用紧缩，还要评估其开销，最简单的合并算法是简单地将所有进城移到内存的一端，而将所有的孔移到内存的另一端，以生成一个大的空闲块。这种方案开销较大。

另一种解决方法外部碎片问题的方法是 允许物理地址为非连续的。 这样只要有物理内存就可以为进程分配。这种方案有两种互补的实现技术： 分页和分段 。这两种技术也可以合并。

分页产生 内部碎片 ，分段产生 外部碎片

8.4 分页（paging）

分页（paging）内存管理方案允许进程的物理地址空间可以使 非连续的 。分页避免了将不同大小的内存块匹配到交换空间上，前面叙述的内存管理方案都有这个问题，当位于内存中的代码和数据需要换出时，必须现在备份存储上找到空间，这是问题就产生了。备份存储也有前面所述的与内存相关的碎片问题，只不过访问更慢。

传统上，分页支持一直是由硬件来处理的。最近的设计是通过将硬件和操作系统相配合来实现分页。

8.4.1 基本方法

实现分页的基本方法设计将物理内存分为固定大小的块，称为 帧 （frame）；而将逻辑内存也分为同样大小的块，称为 页 （page）。当需要执行进程时，其页从备份存储中调入到可用的内存帧中。备份存储也分为固定大小的块，其大小与帧相同。

由CPU生成个每个地址分为两个部分：页号（p）和页位移（d）。页号作为页表的索引。页表包含每页所在物理内存的基地址，这些基地址与页偏移的组合形成物理地址，就可送交物理单元。

页大小（与帧大小一样）是由硬件来决定的。通常为2的幂。选择页的大小为2的幂可以方便的将逻辑地址转换为 页号和页偏移 。如果逻辑地址空间为2m，且页大小为2n单元，那么逻辑地址的高m−n位表示页号（页表的索引），而低n位表示页偏移。每页大小从512B到16MB不等。

设页大小为a，根据页号p得到基地址f，页偏移为d，则物理地址为f∗a+d

分页是一种 动态重定位 。每个逻辑地址有分页硬件绑定为一定的物理地址。采用分页类似于使用一组基（重定位）地址寄存器，每个基地址对应这一个内存帧。

采用分页技术不会产生外部碎片：每个帧都可以分配给需要它的进程。不过分页有 内部碎片。

每个页表的条目通常为4B，不过这是可变的，一个32位的条目可以指向232个物理帧的任何一个，如果帧为4KB，那么具有4B条目的系统可以访问244B大小。

当系统进程需要执行时，它将检查该进程的大小（按页计算）。进程的每页都需要一帧。因此，如果进程需要n页，那么内存中至少应有n个帧。如果有那么就分配给新进程。进程的第一页装入一个已分配的帧，帧号放入进程的页表中。下一页分配给另一帧，其帧号也放入进程的页表中。

分页的一个重要特点是 用户视角的内存和实际的物理内存的分离。 用户程序将内存作为一整块来处理，而且它只包括这一个进程。事实上，一个用户程序与其他程序一起，分布在物理内存上。

用户视角的内存和实际的物理内存的差异是通过地址转换硬件协调的。逻辑地址转换为物理地址，这种映射是用户所不知道的，但是受操作系统所控制。注意用户进程根据定义是不能访问非它所占用的内存的。它无法访问其页表所规定之外的内存，页表只包括进程所拥有的那些页。

由于操作系统管理物理内存，它必须知道物理内存的分配细节：哪些帧已占用，哪些帧可用，总共有多少帧等。这些信息通常保存在帧表中。在帧表（frame table）中，每个条目对应一个帧，以表示该帧是空闲还是已占用，如果被占用，是被哪个进程的哪个页所占用。

另外，操作系统必须意识到用户进程是在用户空间内执行，且所有逻辑地址必须映射到物理地址。如果用户执行一个系统调用（如进行I/O），并提供地址作为参数，那么这个地址必须映射成物理地址。操作系统为每个进程维护一个页表副本，就如同它需要维护指令计数器和寄存器的内容一样。当操作系统必须手工将逻辑地址映射成物理地址时，这个副本可用来将逻辑地址转换为物理地址。当一个进程可分配到CPU时，CPU调度程序可以根据该副本来定义硬件页表。因此，分页增加了切换时间。

8.4.2 硬件支持

每个操作系统都有自己的方法来保存页表。绝大多数都为每个进程分配一个页表。页表的指针与其他寄存器的值（如指令计数器）一起存入进程控制块。当调度程序需要启动一个程序时，它必须首先装入用户寄存器，并根据所保存的用户页表来定义正确的硬件页表值。

页表的硬件实现有很多方法。最为简单的是将页表作为一组专用寄存器（register）来实现。这些寄存器应用高速逻辑电路来构造，以便有效的进行分页地址的转换。由于对内存的每次访问都要经过分页表，因此效率很重要。CPU装入或修改页表寄存器的指令是特权级的，因此只有操作系统才可以修改内存映射图。

如果页表比较小（例如256个条目），页表使用寄存器还是比较合理的。但是，绝大多数当代计算机都允许页表非常大（如100万个条目）。对于这些机器，采用快速寄存器来实现页表就不可行了，因而需要将页表放在内存中，并将 页表基寄存器 （page-table base register， PTBR ）指向页表。改变页表，只需要改变这一寄存器就可以了，这也大大降低了切换时间。

采用这种方法的问题是访问用户内存位置需要一些时间。如果要访问位置i，那么必须先用PTBR中的值再加上页号i的偏移，来查找页表。这一任务需要内存访问，根据所得的帧号，再加上页偏移，就得到了真实的物理地址，接着访问内存中所需的位置。采用这种方法，访问一个字节需要两次内存访问（一次用于页表条目，一次用于字节），这样内存访问的速度就减半，在绝大多数情况下这种延迟是无法忍受的。

对这一问题的标准解决方案是采用小但专用快速的硬件缓冲，这种缓冲称为 转换表缓冲区 （translation look-aside buffer，TLB）。TLB是关联的快速内存。 TLB条目由两部分组成：键（标签）和值 。当关联内存根据给定值查找时，它会同时与所有键进行比较。如果找到条目，那么就得到相应的值域。这种查找方式比较快，不过硬件也比较昂贵，通常，TLB中的条目数并不多，通常在64~1024之间。

TLB与页表一起按如下方式使用：TLB只包括也表中的一小部分条目。当CPU产生逻辑地址后，其页号提交给TLB。如果页码不在TLB中（称为TLB失效），那么就需要访问页表。将页号和帧号增加到TLB中。如果TLB中的条目已满，那么操作系统会选择一个来替换。替换策略有很多，从最近最少使用替换（LRU）到随机替换等。另外，有的TLB允许有些条目固定下来。通常内核代码的条目是固定下来的。

有的TLB在每个TLB条目中还 保存地址空间标识码 （address-space identifier， ASID ）。ASID可用来唯一标识进程，并为进程提供地址空间保护。当TLB试图解析虚拟页号时，它确保当前运行进程的ASID与虚拟页相关的ASID相匹配。如果不匹配，那么就作为TLB失效。除了提供地址空间保护外，ASID允许TLB同时包含多个进程的条目。如果TLB不支持独立的ASID，每次选择一个页表时（例如，上下文切换时），TLB就必须被冲刷（flushed）或删除，以确保下一个进程不会使用错误的地址转换。

页号在TLB中被查找到的百分比称为命中率。

80%的命中率意味着有80%的时间可以在TLB中找到所需的页号。

假如查找TLB需要20ns，访问内存需要100ns，如果访问位于TLB中的页号，那么采用内存映射访问需要120ns。如果不能在TLB中找到（20ns），那么必须先访问位于内存中的页表得到帧号（100ns），并进而访问内存中所需字节（100ns），这总共需要220ns。为了得到有效内存访问时间，必须根据概率对每种情况进行加权。

有效内存访问时间 =0.80∗120+0.2∗220=140（ns）

对于这种情况，现在内存访问速度要慢40

如果命中率为98%，那么

有效内存访问时间 =0.98∗120+0.02∗220=122(ns)

由于提高了命中率(Hit ratio)，内存访问时间只慢了22%

8.4.3 保护

在分页环境下，内存保护是通过与每个帧相关联的保护为来实现的。通常，这些位保存在页表中。

可以用一个位来定义一个页是可读写还是只读的。每次地址引用都要通过页表来查找正确的帧码，在计算物理地址的同时，可以检查保护位来验证。对只读页进行写操作会向操作系统产生硬件陷阱(trap)（或内存保护冲突）。

可以很容易的扩展这一方法以提供更细致的保护，可以创建硬件以提供只读、读写、只执行保护。或者，通过为每种访问情况提供独立保护位，实现这些访问的各种组合；非法访问会被操作系统捕捉到。

还有一个位通常与页表中的每一条目相关联 ：有效-无效位。 有效，表示相关的页在进程的逻辑地址空间内，因此是合法的页；无效，表示相关的页不在进程的逻辑地址空间内。通过使用有效-无效位可以捕捉非法地址。操作系统通过对该位可以允许或不允许对某页的访问。

有些系统提供硬件如 页表长度寄存器 （page-table length register，PTLR）来表示页表的大小，该寄存器的值可用于检查每个逻辑地址以验证其是否位于进程的有效范围内，如果检测无法通过，会被操作系统捕获。

8.4.4 共享页

分页的优点之一在于可以共享公共代码。

这种考虑对分时环境特别重要。考虑一个支持40个用户的系统，每个用户都执行一个文本编辑器。如果文本编辑器包括150kb

的代码和50kb的数据空间。则需要8000kb来支持这40个用户。如果代码是可重入代码（reentrant code，也称为纯代码），则可以共享。如图所示，看到3个页的编辑器（每页50kb）在三个进程间共享，而每个进程都有自己的数据页。通过这种方法，只需要在物理内存中保存一个编辑器副本。每个用户的页表映射到编辑器的同一物理副本，而数据页映射到不同帧。因此，为支持40位用户，只需要一个编辑器副本（150k）再加上40个用户数据空间副本50kb，总的需求空间为2150kb，而不是8000kb，这是一个明显的节省。

可重入代码 是不能自我修改的代码，它从不会在执行期间改变。两个或多个进程可以在相同的时间执行相同的代码。每个进程都有它自己的寄存器副本和数据存储，以控制进程执行的数据。两个不同进程的数据也将不同。

其他常用程序也可以共享，如编译器，窗口系统，运行时库，数据库系统等。

共享代码的只读特点不能只通过正确代码来保证，而需要操作系统来强制实现。

一个系统多个进程内存共享类似于一个任务的多线程地址空间共享。有的操作系统通过实现共享页来实现共享内存。

除了允许多个进程共享同样的物理页外，按页组织内存也提供了许多其他优点。

8.5 页表结构

8.5.1 层次页表

8.5.2 哈希页表（hashed page table）

8.5.3 反向页表（inversed page table）

8.6 分段（segmentation）

采用分页内存管理有一个不可避免的问题，就是 用户视角的内存和实际物理内存 的分离。

8.6.1 基本方法

用户通常愿意将内存看作是一组不同长度的段的集合，这些段之间并没有一定的顺序。如对象、数组、堆栈、变量等，就像汇编语言中对先对段进行定义，然后指针指向段的位置一样。

分段（ segmentation）就是支持这种用户视角内存管理方法。逻辑地址空间由一组段组成的。每个段都有名称和长度。地址指定了段名称和段内偏移。因此用户通过两个量来指定地址： 段名称(segment-number)和偏移(offset)。

注意这一方案与分页的对比。在分页中，用户只指定一个地址，该地址通过硬件分为页码和偏移。

为实现简单起见，段是编号的，是通过段号而不是段名来引用的。因此，逻辑地址由有序对组成：

<segment−number,offset>

通常，在编译用户程序时，编译器会自动根据输入程序来构造段。

一个C编译器可能会创建如下段：

①代码

②全局变量

③堆（内存从堆上分配）

④每个线程采用的栈

⑤标准的C库函数

在编译时链接的库可能分配为不同的段。加载程序时会装入所有这些段，并为他们分配段号。

8.6.2 硬件

用户虽然现在能够通过二维地址来引用程序中的对象，但是实际物理地址内存仍然是一维序列字节。因此，必须定义一个实现方式，以便将二维的用户定义地址映射为一维物理地址。这个地址是通过段表（segment table）来实现的。段表的每个条目都有段基地址和段界限。段基地址包含该段在内存中的开始物理地址，而段界限指定该段的长度。

一个逻辑地址由两部分组成：段号s和段内的偏移d。段号用来做段表的索引，逻辑地址的偏移d用位于0和段界限之间。

第九章 虚拟内存

9.1 背景

第八章所介绍的内存管理算法都是基于一个基本要求：执行指令必须在物理内存中，满足这一要求的第一种方法是整个进程放在内存中。 动态载入 能帮助减轻这一限制，但是它需要程序员特别小心地做一些额外的工作。

指令必须都在物理内存内的这一限制，似乎是必须和合理的，但也是不幸的，因为这使得程序的大小被限制在物理内存的大小内。事实上，研究实际程序会发现，许多情况下并不需要将整个程序放到内存中。即使在需要完整程序的时候，也并不是同时需要所有的程序。

因此运行一个部分在内存中的程序不仅有利于系统，还有利于用户。

虚拟内存（virtual memory）将 用户逻辑内存和物理内存 分开。这在现有物理内存有限的情况下，为程序员提供了巨大的虚拟内存。

进程的虚拟地址空间就是进程如何在内存中存放的逻辑（或虚拟）视图。通常，该视图为进程从某一个逻辑地址（如地址0）开始，连续存放。

根据第八章，物理地址可以按页幁来组织，且分配给进程的物理页帧也可能不是连续的。这就需要内存管理单元（MMU）将逻辑页映射到内存的物理页帧。

如上图显示，运行随着动态内存的分配，堆可向上生长。类似地，还允许随着子程序的不断调用，栈可以向下生长。堆与栈之间的巨大空白空间(或hole)为 虚拟地址 的一部分，只有在堆与栈生长的时候，才需要实际的物理页。包括空白的虚拟地址空间成为 稀地址空间 ，采用稀地址空间的优点是：随着程序的执行，栈或者堆段的生长或需要载入动态链接库（或共享对象）时，这些空白可以填充。

除了将逻辑内存与物理内存分开，虚拟内存也允许文件和内存通过共享页而为两个或者多个进程所共享，这样带来了如下的有点：

• 通过将共享对象映射到虚拟地址空间，系统库可为多个进程所共享。虽然每个进程都认为共享库是其虚拟地址空间的一部分，而共享库所用的物理内存的实际页是为所有进程所共享。通常，库是按制度方式来链接每个进程的空间的。
• 类似的，虚拟内存允许进程共享内存。两个或者多个进程之间可以通过使用共享内存来相互通信。虚拟内存允许一个进程创建内存区域，以便与其他进程进行共享。共享该内存区域的进程认为它是其虚拟地址空间的一部分，而事实上这部分是共享的。
• 虚拟内存可允许在用系统调用fork()创建进程期间共享页，从而加快进程的创建。

9.2 按需调页

一个执行程序从磁盘载入内存的时候有两种方法。

• 1. 选择在程序执行时，将整个程序载入到内存中。不过这种方法的问题是可能开始并不需要整个程序在内存中。如有的程序开始时带有一组用户可选的选项。载入整个程序，也就将所有选项的执行代码都载入到内存中，而不管这些选项是否使用。
• 2. 另一种选择是在需要时才调入相应的页。这种技术称为 按需调页 (demand paging)，常为 虚拟内存系统 所采用。

按需调页系统看类似于使用交换的分页系统，进程驻留在第二级存储器上（通常为磁盘）。当需要执行进程时，将它换入内存。不过，不是讲整个进程换入内存，而是使用 懒惰交换 (lazy swapper)。懒惰交换只有在需要页时，才将它调入内存。由于将进程看做是一系列的页，而不是一个大的连续空间，因此使用交换从技术上来讲并不正确。交换程序(swapper)对整个进程进行操作，而调页程序(pager)只是对进程的单个页进行操作。因此， 在讨论有关按需调页时， 需要使用调页程序而不是交换程序。

9.2.1 基本概念

当换入进程时，调页程序推测在该进程再次换出之前使用到的哪些页，仅仅把需要的页调入内存。从而减少交换时间和所需的物理内存空间。

这种方案需要硬件支持区分哪些页在内存，哪些在磁盘。采用 有效/无效位 来表示。当页表中，一个条目的该位为有效时，表示该页合法且在内存中；反之，可能非法，也可能合法但不在内存中。

如果进程从不试图访问标记为无效的页，那么并没有什么影响，因此，如果推测正确且只调入所有真正需要的页，那么进程就可如同所有页都调入内存一样正常运行。

当进程试图访问这些尚未调入内存的页时，会引起 页错误陷阱 （page-fault trap）。这种情况的处理方式如下：

1. 检查进程的内部页表（通常与PCB一起保存）。以确定该引用是的合法还是非法的地址访问。
2. 如果非法，则终止进程；如果引用有效但是尚未调入页面，则现在进行调入。
3. 找到一个空闲帧（如，从空闲帧表中选取一个）。
4. 调度一个磁盘操作，以便将所需页调入刚分配的帧
5. 磁盘读操作完成后，修改进程的内部表和页表，表示该页已在内存中。
6. 重新开始因陷阱而中断的指令。

如果没有空闲帧时该如何处理呢？

• 页替换：在内存中找到一些不再使用的页，将它换出去。
• 一些页可能被多次加载如内存。

程序具有局部引用，这使得按需调页的性能较为合理。

支持按需调页的硬件与分页和交换的硬件一样：

• 页表：该表通过有效-无效位或保护位的特定值，该条件设为无效
• 次级存储器：该次级存储器用来保存不再内存中的页。次级存储器通常为快速磁盘。它通常成为交换设备，用于交换的这部分磁盘称为 交换空间

9.2.2 按需调页的性能

按需调页对计算机系统的性能有重要影响，下面计算一下关于按需调页内存的 有效访问时间 （effective access time）。

设p(0≤p≤1)为页错误的概率，ma为内存访问时间:

有效访问时间=(1−p)×ma+p×页错误时间

如果p→0，则不存在页错误；

如果p→1，则每次访问都存在页错误，即 纯粹按需调页 (pure demand paging)。

其中页错误时间有很多，主要是下面三种：

• 处理页错误中断
• 读入页（页换入时间）
• 重新启动进程

按需调页的例子

内存存取时间 =200 ns

平均页错误服务时间 =8 ms

EAT=(1−p)×200 ns+p×8000000

如果每次1000次访问中有1次页错误，则EAT=8.2ns。即，因按需调页而慢40倍，如果需要性能降低不超过10%，则需要p<0.0000025

因此来看，对于 按需调页 ，降低页错误率至关重要。

另外是对交换空间的处理的使用。磁盘IO到交换空间通常比到文件系统要快，因为交换空间是按大块进行分配，并不使用文件查找和间接分配方法。因此，在进程开始时将整个文件镜像复制到交换空间，并从空间交换执行按页调度，那么有可能获得更好的性能。

另一种选择是开始时从文件系统进行按需调页，但置换出来的页写入交换空间，而后的调页则从交换空间中读取。这种方法确保只有需要的页才从文件系统中调入，又可以保证一定的性能。

9.3 写时复制

写时复制 Copy-on-Write (COW) 运行父进程与子进程开始时共享同一页面，这些页面标记为 写时复制页， 即如果任何一个进程需要对页进行写操作，那就创建一个共享页的副本。

因为指标及那些能够被修改的页，所以创建进程的过程更有效率。

写时复制所需的空闲也老子一个空闲缓冲池，系统通常用 按需填零( zero-fill-on-demand)的技术分配这些页。按需填零在需要分配之前先填零，因此清除了以前的内容。

下面的两个过程提箱了进程1修改C前后的物理内存的情况。

before

after

9.4 页面置换

操作系统为何要进行页面置换呢？这是由于操作系统给用户态的应用程序提供了一个虚拟的“大容量”内存空间，而实际的物理内存空间又没有那么大。所以操作系统就就“瞒着”应用程序，只把应用程序中“常用”的数据和代码放在物理内存中，而不常用的数据和代码放在了硬盘这样的存储介质上。如果应用程序访问的是“常用”的数据和代码，那么操作系统已经放置在内存中了，不会出现什么问题。但当应用程序访问它认为应该在内存中的的数据或代码时，如果这些数据或代码不在内存中，则根据上文的介绍，会产生缺页异常。这时，操作系统必须能够应对这种缺页异常，即尽快把应用程序当前需要的数据或代码放到内存中来，然后重新执行应用程序产生异常的访存指令。如果在把硬盘中对应的数据或代码调入内存前，操作系统发现物理内存已经没有空闲空间了，这时操作系统必须把它认为“不常用”的页换出到磁盘上去，以腾出内存空闲空间给应用程序所需的数据或代码。

操作系统迟早会碰到没有内存空闲空间而必须要置换出内存中某个“不常用”的页的情况。如何判断内存中哪些是“常用”的页，哪些是“不常用”的页，把“常用”的页保持在内存中，在物理内存空闲空间不够的情况下，把“不常用”的页置换到硬盘上就是页面置换算法着重考虑的问题。容易理解，一个好的页面置换算法会导致缺页异常次数少，也就意味着访问硬盘的次数也少，从而使得应用程序执行的效率就高。

下面提供了一种需要 页置换 的情况。

9.4.1 基本页置换

基本页置换采用方法如下。

查找需要页在磁盘上的位置。

查找一空闲帧：

• 如果有空闲帧，那么就使用它
• 如果没有空闲帧，那么就是用页置换算法选择一个 “牺牲”帧 （victim frame）
• 将牺牲帧的内容放到磁盘上，改变页表和帧表。

将所需页读入（新）空闲帧，改变页表和帧表。

重启用户进程。

如果没有帧空闲，那么需要采用两个页传输（一个换出，一个换入）。可以通过使用 修改位 或 脏位 以降低额外开销。每当页内的任何字或字节被写入时，硬件就会设置该页的修改位以表示该页已被修改。这样的话，磁盘上页的副本的内容没有必要重写。

页置换 是 按需调页 的基础。为实现按需调页，必须解决两个主要问题：必须开发帧分配算法(frame-allocation algorithm)和页置换算法(page-replacement algorithm)。如果在内存中有多个进程，那么必须决定为每个进程各分配多少帧。而且，当需要页置换时，必须选择要置换的帧。

可以这样来评估一个算法：针对特定内存引用序列，运行某个置换算法，并计算出页错误的数量。内存的引用序列成为 引用串( reference string)。

第一，对给定页大小（页大小通常由硬件或系统来决定），只需要考虑页码，而不需要完整的地址。第二，如果有一个页p的引用，那么任何紧跟着对页p的引用绝不会产生页错误。页p在第一次引用时已在内存中，任何紧跟着的引用绝不会出错。

页错误和帧数量图：

9.4.2 FIFO页置换

该算法总是淘汰最先进入内存的页，即选择在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列，队列头指向内存中驻留时间最久的页，队列尾指向最近被调入内存的页。这样需要淘汰页时，从队列头很容易查找到需要淘汰的页。FIFO算法只是在应用程序按线性顺序访问地址空间时效果才好，否则效率不高。因为那些常被访问的页，往往在内存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO算法的另一个缺点是，它有一种 异常现象（Belady现象），即在增加放置页的页帧的情况下，反而使缺页异常次数增多。

问题：随机一访问串和驻留集的大小，通过模拟程序显示淘汰的页号并统计命中率。示例：

输入访问串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1

驻留集大小：3

红色表示：指针指向调入内存的页面中“最老“的页面

通过模拟程序输出淘汰的页号分别为：7 0 1 2 3 0 4 2 3

命中率为：51.3

注意 ：内存的页面中“最老“的页面，会被新的网页直接覆盖，而不是“最老“的页面先出队，然后新的网页从队尾入队。

9.4.3 最优(Optimal)置换

由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长的未来时间内不再被访问的页面。采用最佳置换算法，通常可保证获得 最低的缺页率 。但由于操作系统其实无法预知一个应用程序在执行过程中访问到的若干页中，哪一个页是未来最长时间内不再被访问的，因而该算法是无法实际实现，但可以此算法作为上限来评价其它的页面置换算法。

9.4.4 LRU（Least Recently Used）页置换

FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页调入内存的时间，而页调入的先后顺序并不能反映页是否“常用”的使用情况。

最近最久未使用（LRU）置换算法，是根据页调入内存后的使用情况进行决策页是否“常用”。由于无法预测各页面将来的使用情况，只能利用“ 最近的过去 ”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页予以淘汰。该算法赋予每个页一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

问题：随机一访问串和驻留集的大小，通过模拟程序显示淘汰的页号并统计命中率。示例：

输入访问串：7 0 1 2 0 3 0 4 2 3 0 3 2

驻留集大小：3

算法的实现：由于LRU算法淘汰的是上次使用距离t时刻最远的页，故需记录这个距离。

有两张方法：

计数器： 为每个页表项关联一个使用时间域，并为CPU增加一个逻辑时钟或计数器。对每次内存引用，计数器都会增加。每次内存引用时，时钟寄存器的内容会复制到相应页所对应页表项的使用时间域内。置换具有最小时间的页，这种方案需要搜索页表以查找LRU页，且每次内存访问都要写入内存。在页表改变时也必须要保证时间，必须考虑时钟溢出。

堆栈 ：实现LRU置换的另一个方法是采用页码堆栈。每当引用一个页，该页就从堆栈中删除并放在顶部，这样，堆栈底部总是LRU页，该堆栈可实现为具有头指针和尾指针的双向链表

每次内存引用都必须更新时钟域或堆栈，如果每次引用都采用中断，以允许软件更新这些数据结构，那么它会使内存引用慢至少10倍

红色表示：每个页帧对应的计数器值

通过模拟程序输出淘汰的页号分别为：7 1 2 3 0 4

命中率为：413

LRU的另一种通俗理解：

例如一个三道程序，等待进入的是1，2，3，4，4，2，5，6，3，4，2，1。先分别把1，2，3导入，然后导入4，置换的是1，因为他离导入时间最远。然后又是4，不需要置换，然后是2，也不需要，因为内存中有，到5的时候，因为3最远，所以置换3，依次类推。

注意 ：虽然两个算法都是用队列这种数据结构实现的，但具体操作不完全遵从队列的原则。这一点不必纠结。

命中率是指在队满的情况下，新的元素的加入，不影响队列其它元素。即该元素已存在在队列中。

OPT、LRU以及FIFO算法的对比图如下所示：

9.4.5 近似LRU页置换

很少有计算机系统能够提供足够的硬件来支持真正的LRU页置换。有的系统不提供任何支持，因此必须使用其他置换算法。然而，许多系统都通过应用为方式提供一定支持，页表内的每项都关联着一个 引用位 (reference bit)，每当引用一个页时，相应页表的引用位就会被引脚置位。如添加一个8bit的引用位（极端情况下只有一个引用位，即二次机会算法）。每个时钟都向右移位，引用的话高位置1，否则置0。

开始，操作系统会将所有引用位都清零。随着用户进程的执行，与引用页相关联的引用位被硬件置位。通过检查引用位，能确定那些用过而那些没用过。这种部分排序信息导致了许多近似LRU算法的页置换算法。

附加引用位算法：

可以为位于内存中的每个表中的页保留一个8bit的字节。操作系统把每个页的引用位转移到其8bit字节的高位，而将其他位右移，并抛弃最低位。如果将8bit字节作为无符号整数，那么具有最小值的页为LRU页，且可以被置换。

二次机会算法：

二次机会置换的基本算法是FIFO置换算法。当要选择一个页时，检查其引用位。如果其值为0，那么就直接置换该页。如果引用位为1，那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零。且其到达时间设为当前时间。因此获得第二次机会的页，在所有其他页置换之前，是不会被置换的。另外，如果一个页经常使用以致于其引用位总是得到设置，那么它就不会被置换。

一种实现二次机会算法的方法是采用循环队列。用一个指针表示下次要置换哪个页。当需要一个帧时，指针向前移动直到找到一个引用位为0的页。在向前移动时，它将清除引用位。

增强型二次机会算法

通过将引用位和修改位作为一个有序对来考虑，能增强二次机会算法。有下面四种可能类型：

1 (0,0)最近没有使用且也没有修改。—用于置换的最佳页

2 (0,1)最近没有使用但修改过。—不是很好，因为在置换之前需要将页写出到磁盘

3 (1,0)最近使用过但没有修改—它有可能很快又要被使用

4 (1,1)最近使用过且修改过—它有可能很快又要被使用，且置换之前需要将页写出到磁盘

当页需要置换时，每个页都属于这四种类型之一。置换在最低非空类型中所碰到的页，可能要多次搜索整个循环队列。

9.4.6 页缓冲算法

系统通常保留一个空闲帧缓冲池。当出现页错误时，会像以前一样选择一个牺牲帧，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。

9.5 帧分配

9.5.1 帧的最少数量

如何在各个进程之间分配一定的空闲内存？

简单办法是将帧挂在空闲帧链表上，当发生页错误之时即进行分配。进程终止时帧再次放回空闲帧链表。

帧分配策略受到多方面限制。例如， 分配数不能超过可用帧数，也必须分配至少最少数量。保证最少量的原因之一是 性能 。页错误增加会减慢进程的执行。并且，在指令完成前出现页错误，该指令必须重新执行。所以有足够的帧至关重要。

每个进程帧的最少数量由 体系结构 决定，而最大数量是由可用 物理内存数量 决定。

9.5.2 分配算法

• 1）平均分配，每个进程一样多
• 2）按进程大小使用比例分
• 3）按进程优先级分
• 4）大小和优先级组合分

9.5.3 全局分配和局部分配

全局置换允许进程从所有帧集合中选择一个进行置换，而不管该帧是否已分配给其他进程，即它可以从其他进程抢夺帧，比如高优先级抢夺低优先级的帧；局部分配则要求每个进程只能从自己的分配帧中分配。

局部置换要求每个进程仅从其自己的分配帧中进行选择

全局置换通常有更好的吞吐量，且更为常用。一个问题是不能控制 页错误率 。因为局部置换不能使用其他进程的不常用的内存。

9.6 系统颠簸

如果一个进程在换页上用的时间多于执行时间，那么这个进程就在 颠簸（thrashing） ，颠簸其实就是频繁的页调度行为。

9.6.1 系统颠簸的原因

如果一个进程没有分配到足够的页，那么就会导致页置换不断的发生，这将导致：

• 低CPU利用率
• 低CPU利用率导致系统认为需要引入新进程，增加多道程序的程度。
• 进程分配到的帧会更少
• …死循环

9.7 内存映射文件

件的 内存映射（memory-mapping） 允许一部分虚拟内存与文件逻辑相关联。这样的结果是能够通过虚拟内存技术来将文件IO作为普通内存来访问。利用虚拟内存技术将文件I/O作为普通内存访问的方法叫做文件的内存映射。

开始的文件访问按普通请求页面调度来进行，会产生页错误。这样，一页大小的部分文件从文件系统读入物理页，以后文件的读写就按照通常的内存访问来处理

对于映射到内存的文件进行读写操作可能不会及时的更新到磁盘的文件当中。更新文件的操作通常由两种方式：

一、通过定期检查内存映射页是否改变来判断是否应该写磁盘

二、在关闭文件的时候将内存映射页写回磁盘，并从进程的虚拟内存中删除。

9.8 内核内存的分配

当用户态进程需要额外内存时，可以从内核所维护的空闲页帧链表中获取页。但是，内核内存的分配通常是从空闲内存池中获取的。

内核内存的分配与普通用户（从进程空闲链表中获取）不同：

• 内核分配内存时，有时需要的空间不到一页。因此，需要谨慎的分配内存，减少浪费。
• 有些硬件需要直接和物理内存交互，因此需要分配连续的物理页

9.8.1 buddy 系统

buddy系统是从物理上 连续的大小固定 的段上进行分配。每次分配的内存按2的幂次进行分配（2KB、4KB…），如果请求不为2的幂，那么就按下一个2的幂次来分配（如果请求11KB，则分配16KB）。

其分配是从最大的段开始尝试分配

如果满足要求，那么段平均分为两部分，取其中一半继续开始尝试分配

如果不满足要求，那么就取上一次满足尝试分配的大小分配。

优点：

可通过合并快速的形成更大的段

缺点：

容易产生碎片（如33KB的需求需要64KB才能满足）

9.8.2 slab分配

slab提出的原因：由于操作系统在运行中会不断产生、使用、释放大量重复的对象，所以对这样的重复对象的生成进行改进可以大大提高效率。

简单解释

slab是Linux操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象，如进程描述符等。

这些对象的大小一般比较小，如果直接采用buddy系统来进行分配和释放，不仅会造成大量的内存碎片，而且处理速度也太慢。

slab分配器是基于对象进行管理的，相同类型的对象归为一类(如进程描述符就是一类)。

每当要申请这样一个对象，slab分配器就从一个slab列表中分配一个这样大小的单元出去。

当要释放时，将其重新保存在该列表中，而不是直接返回给buddy系统，从而避免这些内碎片。

slab分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。

具体实现

• slab由一个或多个物理上的页组成
• 高速缓存（cache）含有一个或多个slab
• 每个内核数据结构含有一个cache，如进程描述符，文件对象，信号量等。
• 每个cache含有内核数据结构的对象实例

当cache被创建时，将所有的对象标记为 空闲 （free）

当需要内核数据结构的对象时，可以从cache上直接获取，并将该对象标记为 使用 （used）

slab有三种状态：

• 满的： slab中所有对象被标记为使用
• 空的： slab中所有对象被标记为空闲
• 部分： slab中部分对象被标记为使用

分配过程：

• slab分配器首先从部分空闲的slab进行分配
• 如没有部分空闲的slab，则从空的slab进行分配
• 如没有空的slab，则从物理连续页上分配新的slab，并将该slab赋给一个cache，再重复上述过程。

优点：

没有因碎片引起的内存浪费

内存请求可以快速满足

预调页

的一个显著特性是当一个进程开始的时候会出现 大量页错误 ，这是由于试图将最初局部调入到内存的结果。

预调页 的目的是阻止这种大量的初始调页，其策略为：同时将所需要的所有页一起调入内存中。

第十 文件系统接口

文件系统和两个不同部分组成： 一组文件 和 目录结构 。

10.1 文件概念

文件是记录在外存上得相关信息的具有名称的集合。其具有 连续的 逻辑地址空间.通常，文件表示数据和程序。

数据文件可以包括，数字、字符、字符串或二进制。文件可以是自由形式，如文本文件，也可以具有严格的格式。

文件必须具有可以长期信息存储的性质、必须能够保存大容量数据、在进程终止后信息能够保留下来、能够多进程并发访问文件中的信息。

其中a是执行文件，b是文档文件。

10.1.1 文件属性

名称：按人们易读的方式保存的信息

标识符：用户不可读，用于在文件系统内进行该文件的标识

类型：用于操作系统辨认并执行

位置：文件位于硬盘上的位置的指针

大小：大小

保护：控制谁可以读、写、执行

时间、日期和用户标识：创建，上次修改，上次访问时间等信息，用于保护，安全，使用跟踪。

文件的属性信息保存在硬盘上的目录结构中.而目录结构也保存在外存上。

10.1.2 文件的操作(File Operations)

• 创建：包含到文件系统中找到空间和在目录中为文件创建一个条目
• 写：需要执行系统调用。另外需要搜索目录查找文件位置和为该文件维护一个写位置的指针并在发生写操作时不断更新指针位置
• 读：需要执行系统调用。过程同写，需要搜索过程和维护读指针的位置
• 重定位：设置文件位置指针为给定值。该操作不需要真正的IO操作，也叫做寻址（seek）
• 删除：搜索，释放相关空间，并删除相应条目。
• 截短文件（truncate）：将文件长度设置为0KB，并释放相关空间，但不改变其他属性（不删除条目）。如截短一个命名为a.txt的文本文件后，它的大小会变为0kb，但文件名和其他属性可能没有变化。
• 上述的操作都涉及到为给定的文件搜索其在目录中的相关位置，为了避免不断搜索，在首次使用文件时，和使用完毕文件时，还需要执行两个操作：
• 打开（open）：为系统调用。将执行搜索，并将相关文件的所有内容都移动到内存中，需要操作时，通过该表的索引指定文件，并直接在内存中进行操作，从而避免了重新搜索和IO操作。
• 关闭（close）：为系统调用。将文件的索引从信息表中删除，并将相关信息从内存写到外存。

操作系统维护包含所有 打开文件的信息表 （open-file table），当需要文件操作时，通过该表的索引指定文件。

对于打开的文件，能够得到如下的信息：

• 文件指针：读和写操作的指针
• 文件打开计数器：一个文件可以被多个进程打开，文件打开计数器记录该操作，当计数器为0时，可以删除该文件条目。
• 文件磁盘位置：定位文件在磁盘的位置
• 访问权限：每个进程用一个访问模式访问文件。

系统调用create和delete的操作的是关闭文件而不是打开的文件

10.1.5 内部文件结构

由于磁盘文件总是按块来分配的，所以文件的最后一块的部分空间通常会被浪费。按块分配所浪费的字节称为内部碎片，块越大，内部碎片也越大。

10.2 访问方法

10.2.1 顺序访问

顺序访问就是打开文件后，一个字节一个字节的读，一个20Kb的文件，必须先读完前10Kb（即使不做任何操作），才能访问到第11Kb。

顺序访问是通过一个指针操作的，指针可以按顺序移动（有的系统允许向前或者向后跳过n个记录），也可以重新设置到开始位置（reset）

read next
write next
reset
noread after last write
    (rewrite)

10.2.2 直接访问

直接访问 也叫相对访问，其原理是基于磁盘的特性的，磁盘能够随时访问其任意位置。

支持直接访问的文件中，文件由固定长度的逻辑记录组成，通过这种逻辑记录（如每一个块的编号，记录等）能够做到访问文件的任意位置。

直接访问可以立即访问大量信息，所以极为有用

read n（块，直接读写）
write n
position to n
    read next
    write next
rewrite

10.3 目录结构

为了管理数据，需要合理的组织方式

为简单起见，可以将存储文件系统的一大块（手动）分配的空间称 为卷 ，一个卷可以存放多个操作系统。

每个卷包含了系统上文件的信息，保存在设备目录或卷表中。  设备目录记录了卷上所有文件的信息

10.3.2 目录概述

10.3.3 单层目录结构

在一个目录下存在：

• 命名问题：文件位于同一个目录下，他们必须具有唯一名称。
• 分组问题

10.3.4 双层目录结构

对于双层结构目录的结构，每个用户都有自己的 用户文件目录(user file directory,UFD) 。

因此在每个UFD中所有的文件名称唯一即可，不同的用户可以有相同拥有文件名的问题。

虽然双层结构目录解决了名称冲突问题，但是它仍有缺点。这种解耦股有效地对用户加以隔离。这种隔离在用户需要完全独立时是有点，但是在用户需要在某个任务上进行合作和访问其他文件时却是一个缺点。

为了访问指定的文件唯一，用户必须知道要访问文件的 路径名（path name） 。也没有解决分组问题

10.3.5 树状目录结构

树是最常用的目录结构。树有根目录，并且系统内的每一个文件都有唯一路径名。

当前目录 ：通常情况下，一个进程都有一个当前目录，包含了进程当前感兴趣的绝大多数文件。子进程的当前目录通常是创建子进程的父进程的当前目录。 用户可以使用系统调用重新定义当前目录

路径名： 路径名有绝对路径和相对路径两种形式， 绝对路径 从根路径开始， 相对路径 从当前目录开始

采用树状目录结构的一个问题是：如何处理删除目录。如果目录为空，那么可以简单的删除条目，如果目录不为空，可以有两个选择：

• 强制要求如果目录不为空就无法删除目录。如MS-DOS系统
• 递归删除目录下的所有子目录和文件。如linux下的rm命令

上图表示的是树状目录。树状结构禁止共享文件和目录，因此允许共享文件和目录后，树就变成了图。

10.3.6 无环图目录

无环图是树状目录结构的一个扩展，允许目录含有 共享子目录和文件

第十一章 文件系统实现

11.1 文件系统结构

磁盘提供大量的外存空间来维持文件系统。磁盘的下述两个特点使得其成为存储多个文件的方便介质。

①可以原地重写；

②可以直接访问磁盘上的任意一块信息。

为了提供对磁盘的高效且便捷的访问，操作系统通过文件系统来轻松地存储、定位、提取数据。文件系统有两个设计问题。

①定义文件系统对用户的接口

②创建数据结构和算法来将逻辑文件系统映射到物理外存设备上

另外，与内存管理的部分方式相同，磁盘同样是以块为单位进行转移的。每块为一个或多个扇区

• IO控制为最底层，提供设备驱动程序和中断处理程序。实现内存和磁盘之间的信息传输
• 基本文件系统发送命令，对磁盘上的物理块进行读写。  每个块通过磁盘地址标识（驱动器，柱面，磁道，扇区）
• 文件组织模块将逻辑地址转换为物理地址，管理文件的逻辑块。同时含有空闲空间管理器，跟踪未分配的块，并根据要求提供给文件组织模块。
• 逻辑文件系统管理元数据，管理目录结构，提供给文件组织模块必要的信息。以及通过文件控制块（file control block，FCB）维护文件结构

11.2 文件系统实现

11.2.1 虚拟文件系统

现代操作系统必须支持多个文件系统类型，因此操作系统必须把多个文件系统整合为一个目录结构。

一个简单但不是很好的方法是为每个文件系统编写目录和文件程序。但这不面向对象。

因此可以将文件系统分为三个层次。

• 文件系统接口：包括open()，read()，write()，close()调用及文件描述符。
• 虚拟文件系统层（VFS层）：区分本地文件和远程文件，并根据文件系统类型进一步区分不同本地文件。

VFS定义了一个清晰的VFS接口，将文件系统的通用操作和具体实现分开。

提供网络上唯一标识一个文件的机制。（基于vnode的文件表示结构）

• 各个类型的本地文件系统：通过VFS结合在一起，并由文件系统接口调用。

VFS根据文件系统类型调用特定文件类型操作以处理本地请求，通过调用NFS协议程序来处理远程请求。

VFS层有两个目的：

• VFS层通过定义一个清晰的VFS接口，以将文件系统的 通用操作和具体实现 分开。多个VFS接口的实现可以共存在同一台机器上，他允许访问已安装在本地的多个类型的文件系统。
• VFS提供了在网络上唯一标识一个文件的机制。VFS基于称为vnode的文件表示结构。UNIX内核中为每个活动节点（文件或目录）保存一个vnode结构

11.3 分配方法

磁盘是直接访问的，非常灵活，其可以存储多个文件，所以一个问题是如何为这些文件分配空间，以便有效的访问和索引这些文件。

主要的分配方法有连续、链接、索引，每种方法有其优缺点。

常见的一个系统只支持一种分配方法，但也有系统支持多种分配方法

11.3.1 连续分配

连续分配（contiguous allocation）要求每个文件在磁盘上占有一系列连续的块。

优点：

在访问块b后访问块b+1通常不需要移动磁头，当需要移动时（读到当前磁道末），只需要移动一个磁道。因此访问连续分配文件需要的寻道数最小。性能较好。

访问容易，连续分配支持 顺序访问和直接访问 。

缺点：

如何为新文件找到空间，这是一个动态存储分配问题（第八章提到过），相关的算法会产生外部碎片问题

外部碎片的一个解决方案是合并（compact），即将小的空闲空间合并起来，而将其他存储的数据变成连续数据。显而易见这种方式的主要开销是时间，因为需要很多的IO操作。不能扩展

另一方面，这种方式还需要确定一个文件占用多少空间。文件的大小有时候可能比较好确定，但通常比较难以确定。

11.3.2 链接分配

采用链接分配（linked allocation），每个文件是磁盘块的链表。目录包括文件第一块的指针和最后一块的指针。每一块都有指向下一块的指针。

采用链接分配，每一个目录条目都有一个指向文件首块的指针。这些指针一开始均为nil（代表空指针，表示空文件）。

在写文件时就可以通过空闲空间管理系统找到一个空闲块。

在读文件时，通过块到块的指针就可以简答的读块。

优点：

没有外部碎片，空闲空间的任何一块都可以满足要求。

创建文件时，不需要说明文件大小。

不需要合并磁盘空间

可以说链接分配解决了连续分配的所有问题。

缺点：

只能用于顺序访问，要找到中间位置，必须跟随指针一块一块的移动。

指针需要空间。

可靠性较低。如果硬盘损坏，若损坏的是指针，那么这可能导致链接到错误的位置。

第一个问题的一个解决方案是采用链接分配方式的变种：文件分配表（FAT），具体参考P365

第二个问题的一个解决方式是将块合并为族，指针按族分配而不是按块分配，一个族包含多个块。这样就减少了指针的使用。但这样的问题就是会增加内部碎片。

第三个问题的解决方式是增加双向链表或在每个块中存文件名和相对块数，不过这也将导致开销增大。

11.3. 3 索引分配

链接分配解决了外部碎片和大小的声明问题，但如果不使用FAT，那么就没有办法有效的支持直接访问。

索引分配（index allocation）把所有的指针存放在一起，通过索引块解决这一问题。

索引块 是一个磁盘块地址的数组。

每个文件都有索引块，其第i块指向文件的第i个块。目录条目包含索引块的地址。要读第i块只需要通过索引块的第i个条目的指针查找和读取即可。

创建文件时，索引块所有指针都设置为nil，开始写第i块时，即从空闲空间管理系统中获取一块，并将指针设置为该地址。

优点：

没有外部碎片，并且支持直接访问。因为磁盘上任何一个位置都可以通过索引获取。

缺点：

浪费空间。索引块的开销比指针要大很多。

针对缺点的解决方案：

链接方案：一个索引块通常为一个磁盘块，因此，它本身能直接读写。为了处理大文件，可以将多个索引块链接起来

多层索引：用第一层索引块指向一组第二层的索引块，第二层索引块再指向文件块，这是链接表示的一种变种。

组合方案：将索引块的头15个指针存在文件的inode中。这其中的前12个指针指向直接块。其他的3个指针指向间接块。第一个间接块为一级间接块的地址，第二个间接块为二级间接块的指针，第三个间接块为三级间接块指针

11.5 空闲空间管理

系统需要维护一个空闲空间链表（free-space list），该链表记录了所有的空闲磁盘空间，并在创建文件时，能够从该链表搜索并返回一段空闲空间。

虽然名字称为链表，但实现形式不一定表现为链表。这一点要注意

11.5.1 位图/位向量

采用位图（bit map）或位向量（bit vector），每块用一位表示，分配表示1，未分配表示0

优点：

查找空闲块和n个连续空闲块相对简单和高效。

缺点：

除非将整个位图都放在内存中方便及时查询，否则其效率就不是很高。这对于小型磁盘是完全可以的，但对大型磁盘，就需要相对较多的内存。

11.5.2 链表

将空闲磁盘块用链表连接起来，并将指向第一个空闲磁盘块的指针保存在磁盘的特殊位置，并同时放置到内存中。

这种方案的效率不高，因为遍历一遍链表需要大量的IO，但通常分配空闲空间不需要遍历，只需要将第一块分配即可。

11.5.3 组

组是对链表的一个改进，组将n个空闲块的地址存在第一个空闲块中。这n个空闲块的最后一个包含了另外n个空闲块的地址。

采用这种方式，大量的空闲块可以很快的找到。

第十二章 大容量存储器的结构

12.1 概述

文件系统的最底层：次级和三级存储结构。

传输速率 ：驱动器和计算机之间的数据传输速率

定位时间 / 随机访问时间： 由寻道时间和旋转等待时间组成

寻道时间 ：移动磁臂到所要的柱面的时间

旋转等待时间 ：等待所要的扇区旋转到磁臂下所用的时间

12.2磁盘结构

现代磁盘驱动器可以看为是一个一维的逻辑块的数组，其按顺序映射到磁盘的扇区。扇区0是最外柱面的第一个磁道的第一个扇区。

逻辑块的映射顺序：先按磁道内的扇区顺序，再按柱面内的磁道顺序，再按柱面从外到内的顺序。

逻辑块是最小的传输单位。

12.3 磁盘调度

名词解释：

寻道时间：磁臂将磁头移动到包含目标扇区的柱面的时间。

旋转延迟：磁盘将目标扇区移动到磁头下的时间。

磁盘带宽：传递的总字节数 ÷ 从服务请求开始到结束的时间

访问时间主要包括寻道时间和旋转延迟，提高调度性能，需要从这两个方面考虑。

12.3.1 FCFS调度

先到先服务算法

会出现大摆动问题（122->14->124）

12.3.2 SSTF调度

最短寻道时间优先算法（shortest-seek-time-first ，SSTF）

选择距离当前磁头位置判定的最短寻道的位置。

是一种最短作业优先调度（SJF），可能会导致饥饿现象。

12.3.3 SCAN调度

也被称为电梯调度，磁臂从一端到另一端移动，处理经过的所有请求，随后改变移动方向，继续处理。

可能会导致另一端的请求虽然很多，但等待时间过长

12.3.4 C-SCAN调度

C-SCAN（circular SCAN）是SCAN调度的一个变种，将柱面当做环，每次从一端到另一端后，马上返回到磁盘开始，从头开始处理请求。

LOOK调度和C-LOOK调度

SCAN和C-SCAN是在整个磁盘范围内移动，但实际上只需要在有请求的最大区间范围内移动即可。

在向一个方向移动时判断是否有请求，并根据请求的边界来放置磁头，这种形式的SCAN调度被称为LOOK调度（同样C-LOOK对应C-SCAN）

12.3.5 如何选择磁盘调度

对于任何调度算法，其性能主要依赖于请求的数量和类型。

磁盘服务请求很大程度上受文件分配方法所影响。程序在读一个连续分配文件时会产生数个在磁盘上相近位置的请求，因而产生有限的磁头移动。

SSTF较为普通且很有吸引力，因为它比FCFS的性能要好。

SCAN和C-SCAN对于磁盘符合较大的系统会执行得更好，这是因为它不可能产生饿死问题。

目录和索引块的位置也很重要。由于文件必须打开后才能使用，打开文件要求搜索目录结构，目录会被经常访问。

在内存中缓存目录和索引块有助于降低磁头移动，尤其是对于读请求。

由于选择需要考虑的因素比较复杂，磁盘调度算法应该作为一个操作系统的独立模块，用于方便替换。

但SSTF或LOOK是比较合理的默认算法