操作系统笔记 | Rainnn の Blog

type

status

date

slug

summary

一、概述

操作系统是作为计算机硬件和计算机用户之间的中介的程序。

第一章导论

1.1 操作系统的功能

操作系统总体目标：

使计算机系统方便使用 convenient

使硬件能高效利用 efficient

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

计算机系统四个组成部分：计算机硬件、操作系统、系统程序与应用程序、用户。

操作系统控制和协调各用户的应用程序对硬件的使用。

用户视角：计算机的用户观点因所使用接口的不同而异。例：

PC ：操作系统的设计目的是为了用户使用方便，性能是次要的，而且不在乎资源使用率（resource utilization）——如何共享硬件和软件资源。

大型机或小型机：操作系统设计为资源使用做了优化：确保所有的CPU时间、内存和I/O都能得到充分使用，并且确保没有用户使用超出其权限以外的资源。

系统视角：

资源分配器（resource allocator）：管理计算机系统的资源，面对许多甚至冲突的资源请求，操作系统必须决定如何为各个程序和用户分配资源，以便计算机系统有效而公平的运行。

控制程序（control program）：管理用户程序的执行以防止计算机资源的错误使用或使用不当。

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

操作系统是一直运行在计算机上的程序（通常称为内核kernel），其他程序则为系统程序和应用程序。

1.2 计算机系统组织

计算机系统通常由一个或多个CPU和若干设备控制器通过共同的总线相连而成。该总线提供了对共享内存的访问。

CPU与设备控制器可以并发工作（concurrent execution），并竞争内存周期。

存储结构

计算机程序必须在内存(或随机访问内存(random access memory，RAM))中以便于运行。内存是处理器可以直接访问的唯一的大容量存储区域(数兆到数千兆字节)。

一个典型指令执行周期(在冯·诺依曼体系结构上执行时)首先从内存中获取指令，并保存在指令寄存器 (instruction register)中。接着，指令被解码，并可能导致从内存中获取操作数或将操作数保存在内部寄存器中。在指令完成对操作数的执行后，其结果可以存回到内存。

因此，绝大多数计算机系统都提供辅存(secondary storage)以作为内存的扩充。对辅存的主要要求是它要能够永久地存储大量的数据。

一个完整存储系统的设计必须平衡所有的因素。

I/O结构

在计算机中，存储器只是众多IO 设备中的一种操作系统的大部分代码用来进行 IO管理，这既是因为它对系统可靠性和性能的十分重要，也是因为设备变化的特性。

1.3 计算机系统体系结构

计算机系统包括三种：

单处理器系统 绝大多数系统采用单处理器。（本教材默认）

多处理器系统（并行系统 paeprallel system/ 紧耦合系统 tightly coupled system）：其优点是增加吞吐量、规模经济、增加可靠性。根据处理策略可以分为非对称多处理（每个处理器都有各自特定的任务。一个主处理器控制系统，其他处理器或者向主处理器要任务或做预先定义的任务）和对称多处理：（每个处理器都要完成操作系统中的所有任务。所有处理器对等，处理器之问没有主-从关系）。

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

1.4 操作系统结构

操作系统提供执行程序的环境。

单个用户通常不能总是使得CPU和I/O设备都忙。 多道程序设计（Multiprogramming）通过组织作业（编码或数据）使CPU总有一个作业可执行，从而提高了CPU的利用率。操作系统同时将多个任务保存在内存中。操作系统通过作业调度（job scheduling）选择一个位于内存中的作业并开始执行，当他需要等待另一个任务如I/O操作的完成时，CPU会简单的切换到另一个作业并执行。

多道程序设计系统提供了一个可以充分使用各种系统资源（如CPU、内存、外设）的环境，但是他们没有提供与计算机系统直接交互的能力。

分时系统（Timesharing）或多任务，是多道程序设计的延伸。在分时系统中，CPU通过在作业之间快速的切换来执行多个作业，由于切换频率很高，使用户可以在程序运行期间与之交互。

分时操作系统允许许多用户同时共享（共享：资源共享即共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。）计算机。

随着系统从一个用户快速的切换到另一个用户，每个用户都会感到整个系统只为自己所用，尽管他事实上为许多用户所共享。

1.5 操作系统操作

现代操作系统是由中断驱动的。如果没有进程要执行，没有 I/O 设备要服务，也没有用户请求要响应，操作系统会静静地等待某件事件的发生。事件总是由中断或陷阱引起。 陷阱trap(或异常exception)是一种软件中断，源于出错(如除数为零或无效的存储访问)或源于用户程序的一个特别请求(完成操作系统服务)。

双重模式操作 P16

为了确保操作系统的正常执行，必须区分操作系统代码和用户定义代码的执行。许多操作系统所采取的方法是提供硬件支持以允许区分各种执行模式。

至少需要两种独立的操作模式：用户模式(user mode)和内核模式（kernel mode)监督程序模式(monitor mode)(也称为管理模式(supervisor mode)、系统模式(systemmode)或特权模式(privileged mode)) 在计算机硬件中增加一个称为模式位(mode bit)的位以表示当前模式：监督程序模式(0)和用户模式(1)。

当计算机系统表示用户应用程序正在执行，系统处于用户模式。然而，当用户应用程序需要操作系统的服务(通过系统调用)，它必须从用户模式转换过来执行请求。

系统引导时，硬件开始处于内核模式。用户进程在用户态下运行，一旦出现陷阱或中断，硬件就从用户态切换到核心态。

双重模式操作提供了保护操作系统和用户程序不受错误用户程序影响的手段。实现方法为：将能引起损害的机器指令作为特权指令（privileged instructuion）。如果在用户模式下试图执行特权指令，那么硬件并不执行该指令，认为该指令非法，并将其以陷阱的形式通知操作系统，切换为kernel mode，由操作系统代为完成。

系统调用（system call）为用户程序请求操作系统代表用户程序完成预留给操作系统的任务提供了方法。

系统调用通常采用陷阱到中断向量中的一个指定位置的方式。

定时器 Timer

目标：必须确保操作系统能维持对CPU的控制，也必须防止用户程序陷入死循环或不调用系统服务，并且不将控制权返回到操作系统。

操作系统将控制权交给用户前，应确保设置好定时器以便产生中断。

如果定时器产生中断，会将控制权自动交给操作系统。

可以使用定时器来防止用户程序运行时间过长。

1.6 进程管理

处于执行中的程序被称为进程（process）。

程序是被动的实体，进程是一个活动的实体。

1.7 内存管理

见后面章节。

1.8 存储管理

计算机操作的最终速度可能与硬盘子系统的速度和管理子系统的算法有关。

1.9 保护和安全

保护是一种控制进程或用户对计算机系统资源的访问的机制。

安全的主要工作是防止系统不受外部或内部攻击。

第二章操作系统结构

操作系统为执行程序提供环境。

从以下三个角度研究操作系统：

services 提供的服务

interface 为用户和程序员提供的接口

components 研究系统各个的组成部分和相互关系

2.1 操作系统服务

提供对用户很有用的函数：

用户界面 user interface

程序执行 program execution

I/O操作 I/O operations

文件系统操作 file-system manipulation

通信 communications

错误检测 error detection

不是帮助用户而是确保系统本身高效运行：

资源分配 resource allocation

统计 accounting

保护和安全 protection and security

2.2 操作系统的用户界面

命令解释程序 CLI command-line interface

解释程序被称为shell

内部命令：命令解释程序本身包含代码以执行这些命令（没有对应的文件）

例如：删除文件的命令可能导致命令解释程序转到相应的代码段以设置参数和执行合适的系统调用。对于这种方法，所能提供的命令的数量决定了命令解释程序的大小，这是因为每个程序需要它自己实现代码。

外部命令：UNIX使用，由系统程序实现绝大多数命令

例如：rm file.txt 会搜索名为rm的文件，将该文件装入内存，并用参数file.txt来执行。与rm相关的功能是完全由文件rm的代码所决定的。这样，程序员能通过创建合适名称的新文件以轻松地向系统增加新命令。这种命令解释程序可能很小，在增加新命令时不必改变。

图形用户界面 GUI graphical user interface

2.3 系统调用

系统调用（system call）提供了操作系统提供的有效服务界面。是操作系统对应用程序和程序员提供的接口。应用程序可以通过系统调用来请求获得操作系统内核的服务，操作系统内核程序处理系统调用请求，使用系统调用可以保证系统的稳定性和安全性。

系统调用过程：传参——陷入指令/trap/访管指令——操作系统切换至kernel mode处理系统调用——返回应用程序

这些调用通常用c或c++编写，当然，对底层的任务（如必须直接访问的硬件），可能以汇编语言指令的形式提供。

绝大多数程序员不会看到这些细节。一般应用程序开发人员根据应用程序接口(API)设计程序。 API是一系列适用于应用程序员的函数，包括传递给每个函数的参数及其返回的程序员想得到的值。

在后台，组成API的函数通常为应用程序员调用实际的系统调用。

Why use APIs rather than system calls? 为什么根据API编程，而不是调用实际的系统调用呢？

可移植性，一个采用API设计程序的应用程序员希望她的程序能在任何支持同样API的系统上编译并执行

此外，对一个应用程序员而言，实际的系统调用比API更为注重细节和困难。

工作机制：用户程序执行“陷入指令”并发起系统调用，CPU从用户态进入内核态，操作系统内核程序对系统调用的请求做相应处理。处理完成后，操作系统内核程序会将CPU还给用户程序

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

最简单的：通过寄存器(registers)来传递

通常存在内存的块(blocks)和(table)表中，并将块的地址通过寄存器来传递

可通过程序放在(placed)或压入(pushed)堆栈(stack)中，并通过操作系统弹出(popped off)

采用块或堆栈方法，不限制所传递参数的数量或长度。

2.4 系统调用类型

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

2.5 系统程序

系统程序提供了一个方便的环境，以开发程序和执行程序。分为：文件管理、状态信息、文件修改、程序语言支持、程序装入和执行、通信

除系统程序外，绝大多数操作系统者提供程序以解决一般问题和执行一般操作。这些程序包括网页浏览器、字处理器和文本式化器、电子制表软件、数据库系统、编译编译器，打印和统计分析包以及游戏。这些程序称为系统工具或应用程序。

绝大多数用户所看到的操作系统是由应用和系统程序而不是系统调用所决定的，例如PC的使用。

2.6 操作系统设计与实现

设计目标

系统设计的第一个问题是定义系统的目标和规格。

需求可以分为两个基本类：用户目标和系统目标

策略和机制 Policy and mechanism 机制决定如何做，策略决定做什么。

实现 Implementation

2.7 操作系统结构

简单结构 simple structure

MS-DOS和UNIX。

分层方法 layered approach

操作系统分成若干层（级）。

最底层（层0）为硬件，最高层（层N）为用户接口。

优点：构造和调试简单的简单化。每层只能利用较低层的功能和服务，每层利用较低层所提供的功能来实现，不需要知道如何实现这些操作。

这是一个理想方法，困难在于如何划分层，一层只能使用其下的较低层

与其他方法相比效率稍差，每层都为系统调用增加了额外开销。

微内核 microkernel

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

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

微内核方法的好处：

便于扩充操作系统

很容易从一种硬件平台设计移植到另一种硬件平台设计。

更好的安全性和可靠性

遗憾的是，微内核必须忍受由于系统功能总开销的增加而导致系统性能的下降。

模块 Modules

大多数现代操作系统按模块方式实现，内核采用面向对象的方法，每个核心组件是分开的，每部分与已知接口的其他部分通信。可以是动态加载方式，每部分根据需要加载到内核。总之，类似于层，但更灵活。

2.8 虚拟机

虚拟机的基本思想是单个计算机(CPU、内存磁盘、网卡等)的硬件抽象为几个不同的执行部件，通过CPU调度和虚拟内存技术，从而造成一种“幻觉”，仿佛每个独立的执行环境都在自己的计算机上运行一样。

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

实现

底层机器有两种模式:用户模式和内核模式。虚拟机软件可以运行在内核模式，因为它就是操作系统。虚拟机本身只能运行在用户模式。正如物理机器有两种模式一样，虚拟机也有两种模式。因此，必须有虚拟用户模式和虚拟内核模式，这两种模式都运行在物理用户模式。

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

优点：

不同的系统资源具有完全的保护。

是用于研究和开发操作系统的好工具

2.9 系统生成

system generation

2.10 系统启动

装入内核以启动计算机的过程成为引导系统。

The procedure of starting a computer by loading the kernel is called booting the system.

Mechanisms determine how to do something, policies decide what will be done.

二、进程管理

第三章进程

3.1 进程概念

进程

在多道程序（multiprograming）环境中，程序的执行是断断续续的，具备动态特征，程序和程序的执行不再一一对应，有必要引入一个新的概念。

进程的定义：可并发执行的程序在一个数据集合上的运行过程。

进程是执行中的程序，这是一种非正式的说法。进程不只是程序代码(code)，程序代码有时称为文本段(text section)(或代码段)。进程还包括当前活动，通过程序计数器的值和处理器寄存器的内容来表示。

另外，进程通常还包括进程堆栈段(包括临时数据，如函数参数、返回地址和局部变量)和数据段(包括全局变量)。进程还可能包括堆 (heap)，是在进程运行期间动态分配的内存。

这里强调：程序本身不是进程；程序只是被动实体，如存储在磁盘上包含一系列指令的文件内容(常被称为可执行文件)，而进程是活动实体，它有一个程序计数器用来表示下一个要执行的命令和相关资源集合。当一个可执行文件被装入内存时，一个程序才能成为进程。装载可执行文件通常有两种方法，即双击一个代表此可执行文件的图标或在命令行中输入该文件的文件名(如 prog.exe或aout)。

虽然两个进程可以是与同一程序相关，但是它们被当作两个独立的执行序列。

进程具有五个特征：

动态性：是进程的最基本的特征，表现在进程由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤销而消亡。

并发性：多个进程实体同存于内存中，能在一段时间内同时执行。

独立性：进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。

异步性：指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。

结构特征：从结构上看，进程实体由程序段、数据段以及进程控制块（PCB）组成，这三部分也称为进程映像。

试比较进程和程序的区别

进程状态

进程在执行时会改变状态(state)。进程状态在某种程度上是由当前活动所定义的。每个进程可能处于下列状态之一：

新的：进程正在被创建

运行：指令正在被执行。

等待：进程等待某个事件的发生(如I/O完成或收到信号)

就绪：进程等待分配处理器

终止：进程完成执行

new: The process is being created

running: Instructions are being executed

waiting: The process is waiting for some event to occur

ready: The process is waiting to be assigned to a processor

terminated: The process has finished execution

running→ready中断是被动的

running→waiting 是主动的

进程控制块（process control block，PCB）

每个进程在操作系统内用进程控制块来表示，它包含许多与一个特定进程相关的信息。

进程状态（包括new ready running waiting terminated）

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

CPU寄存器（包括累加器、索引寄存器、堆栈指针、通用寄存器）

CPU调度信息（包含进程优先级、调度队列的指针）

内存管理信息（根据所使用的内存系统，包含基址和界限寄存器的值、页表或段表）

记账信息（CPU时间、实际使用时间、时间界限）

I/O状态信息（包含给进程的I/O设备列表、打开的文件列表）

PCB的作用：反映进程的动态特征，描述进程的执行情况，使操作系统能控制进程的运行。

3.2 进程调度

多道程序设计的目的是无论何时都有进程在运行，从而使CPU的利用率达到最大化。

分时系统的目的是在进程之间快速切换CPU以便用户在程序运行时能与其进行交互。

为了达到此目的，进程调度选择一个可用的进程（可能从多个可用进程集合中选择）到CPU上执行。

调度队列

作业队列（job queue）：该队列包括系统中的所有进程。（在外存中）

就绪队列（ready queue）：驻留在内存中就绪的、等待运行的进程保存在就绪队列中。

设备队列（device queues）：等待特定I/O设备的进程列表称为设备队列。

新进程开始处于就绪队列。它在就绪队列中等待直到被选中执行或被派遣。当进程分配到CPU并执行时，可能发生下面几种事件中的一种：

进程可能发出一个I/O 请求，并被放到 I/O 队列中

进程可能创建一个新的子进程，并等待其结束

进程可能会由于中断而强制释放CPU，并被放回到就绪队列中

对于前两种情况，进程最终从等待状态切换到就绪态，并放回到就绪队列中。进程继续这一循环直到终止，到时它将从所有队列中删除，其 PCB 和资源将得以释放。

调度程序

进程选择是由相应的调度程序（scheduler）来执行的。

通常对于批处理系统，进程更多地是被提交，而不是马上执行。这些进程被放到大容量存储设备(通常为磁盘)的缓冲池中,保存在那里以便以后执行。

长期调度程序（long-term scheduler）或作业调度程序（job scheduler）从该池中选择进程，并装入内存以准备执行。

短期调度程序（short-term scheduler）或CPU调度程序从准备执行的进程中选择进程，并为之分配CPU。

长期调度程序执行频率低，短期调度程序执行频率高。长期调度程序控制多道程序设计的程度（内存中的进程数量）

中期调度程序 (medium-term scheduler)的核心思想是能将进程从内存(或从 CPU 竞争)中移出，从而降低多道程序设计的程度。

长期调度程序必须仔细选择。通常，绝大多数进程可分为：I/O 为主或CPU 为主。

I/O为主的进程(I/0-bound process)在执行 I/O方面比执行计算要花费更多的时间。

CPU为主的进程(CPU-bound process)很少产生 I/O请求，与I/O为主的进程相比将更多的时间用在执行计算上。

因此，长期调度程序应该选择一个合理的包含I/O为主的和CPU为主的组合进程。如果所有进程均是I/O为主的，那么就绪队列就会几乎为空，从而短期调度程序没有什么事情可做。如果所有进程均是CPU为主的，那么I/O等待队列将几乎为空，从而几乎不使用设备，因而系统会不平衡。

对于某些没有长期调度程序的系统（UNX或WINDOWS的分时系统）只是简单地将所有新进程都放在内容中以供短期调度程序的使用。这些系统的稳定性依赖于物理限制（如可用的终端数）或用户的自我调整，如果多用户系统性能下降到令人难以接受，将有用户退出。

上下文切换 Context Switch

当发生一个中断时，系统需要保存当前运行在 CPU 中进程的上下文，从而在其处理完后能恢复上下文，即先中断进程，之后再继续。进程上下文用进程的PCB 表示，它包括 CPU 寄存器的值、进程状态和内存管理信息等。

通常，通过执行一个状态保存(state save)来保存CPU当前状态(不管它是内核模式还是用户模式)，之后执行一个状态恢复 (state restore)重新开始运行。

将CPU 切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态，这一任务称为上下文切换 (context switch)。当发生上下文切换时，内核会将旧进程的状态保存在其PCB 中，然后装入经调度要执行的并已保存的新进程的上下文。上下文切换时间是额外开销（pure overhead），因为切换时系统并不能做什么有用的工作。上下文切换速度因机器而不同，它依赖于内存速度、必须复制的寄存器的数量、是否有特殊指令(如装入或保存所有寄存器的单个指令)，一般需几毫秒。

3.3 进程操作

进程创建

进程在其执行过程中，能通过创建进程系统调用(create-process system calL)创建多个新进程。创建进程称为父进程，而新进程称为子进程。每个新进程可以再创建其他进程从而形成了进程树。

在一个进程创建子进程时，子进程可能从操作系统那里直接获得资源，也可能只从其父进程那里获得资源。父进程可能必须在其子进程之间分配资源或共享资源(如内存或文件)。限制子进程只能使用父进程的资源能防止创建过多的进程带来的系统超载。

当进程创建新进程时，有两种执行可能:

父进程与子进程并发执行。

父进程等待，直到某个或全部子进程执行完。

新进程的地址空间也有两种可能:

子进程是父进程的复制品 (具有与父进程相同的程序和数据）

子进程装入另一个新程序。

进程终止

进程完成执行最后的语句并使用系统调用exit()请求操作系统删除自身时，进程终止。

父进程终止其子进程(abort)的原因有很多，如：

子进程使用了超过它所分配到的一些资源。(为判定是否发生这种情况，要求父进程有一个检查其子进程状态的机制。)

分配给子进程的任务已不再需要。

父进程退出，如果父进程终止，那么操作系统不允许子进程继续。

有些系统，包括VMS，不允许子进程在父进程已终止的情况下存在。对于这类系统如果一个进程终止(正常或不正常)，那么它的所有子进程也将终止。这种现象，称为级联(cascading termination)，通常由操作系统进行。

用户可能 arbitrarily kill some jobs(kill)

3.4 进程间通信

操作系统内并发执行的进程可以是独立进程或协作进程。

如果一个进程不能影响其他进程或被其他进程所影响，那么该进程是独立的。显然，不与任何其他进程共享数据的进程是独立的

另一方面，如果系统中一个进程能影响其他进程或被其他进程所影响，那么该进程是协作的。显然，与其他进程共享数据的进程为协作进程

进程协作的优点：

信息共享

提高运算速度

模块化

方便

协作进程需要一种进程间通信机制(interprocess communication IPC)来允许进程相互交换数据与信息。进程间通信有两种基本模式：(1)共享内存 shared memory，2)消息传递 message passing。

在共享内存模式中，建立起一块供协作进程共享的内存区域，进程通过向此共享区域读或写入数据来交换信息。

在消息传递模式中，通过在协作进程间交换消息来实现通信。

消息传递对于交换较少数量的数据很有用，因为不需要避免冲突。共享内存比消息传递快，消息传递系统通常用系统调用来实现，因此需要更多的内核介入的时间消耗。

共享内存系统

在通信的进程之间有一块可直接访问的共享空间，对这个共享空间进行读写操作实现进程之间的信息交换。在进行读写操作时，需要使用同步互斥工具（例如P、V操作）以控制对该空间的访问。

共享存储又分为两种，低级方式的共享是基于数据结构的共享；高级方式的共享是基于存储区的共享。操作系统只负责提供可共享使用的存储空间和同步互斥工具，数据交换由用户自己实现。

进程空间一般都是独立的，因此这种共享一般需要特殊的系统调用来实现。

消息传递系统

消息传递工具提供至少两种操作：发送send（消息）和接收receive（消息）

如果进程P和Q需要通信，那么他们必须彼此互相发送消息和接收消息，他们之间必须要有通信线路（communication link）。

直接通信和间接通信 Direct Communication and Indirect Communication

直接通信方式

需要通信的每个进程必须明确地命名通信的接收者或发送者。 send(P, message) receive(Q, message) （对称寻址） send(P, message) receive(id, message) （非对称寻址）接受者不需要命名发送者

这种方案的通信线路具有如下属性:

在需要通信的每对进程之间自动建立线路。进程仅需知道相互通信的标识符。
一个线路只与两个进程相关。
每对进程之间只有一个线路。

缺点是：限制了进程定义的模块化，改变进程的名称可能必须检查所有其他进程的定义。

间接通信方式

在间接通信中，通过邮箱或端口来发送和接收消息。邮箱可以抽象成一个对象，进程可以向其中存放消息，也可从中删除消息，每个邮箱都有一个唯一的标识符。

send(A, message) receive(A, message)

对于这种方案，通信线路具有如下属性:

只有在两个进程共享一个邮箱时，才能建立通信线路。
一个线路可以与两个或更多的进程相关联。
两个通信进程之间可有多个不同的线路，每个线路对应于一个邮箱

邮箱可能为进程所拥有，那么需要区分使用者（只能向邮箱发送消息）和拥有者（只能通过邮箱接收信息）。当拥有邮箱的进程终止，邮箱将消失。任何进程后来向该邮箱发送消息，都会得知邮箱不再存在。

邮箱可能为操作系统拥有，此时的邮箱是独立存在的，并不属于某个特定的进程，因此操作系统必须提供机制以允许进程进行如下操作：

创建新邮箱
通过邮箱发送和接收消息
删除邮箱

同步和异步 Synchronous and asynchronous

消息传递可以是阻塞（Blocking）或非阻塞（Non-blocking）一一也称为同步或异步

阻塞send:发送进程阻塞，直到消息被接收进程或邮箱所接收

非阻塞send:发送进程发送消息并再继续操作。

阻塞receive:接收者阻塞，直到有消息可用。

非阻塞receive:接收者收到一个有效消息或空消息

缓冲 Buffering

不管通信是直接的或是间接的，通信进程所交换的消息都驻留在临时队列中。简单地讲，队列实现有三种方法：

零容量(zero capacity)：队列的最大长度为 0；因此，线路中不能有任何消息处于等待。对于这种情况，必须阻塞发送，直到接收者接收到消息。

有限容量(bounded)：队列的长度为有限的n；因此，最多只能有n个消息驻其中。如果在发送新消息时队列未满,那么该消息可以放在队列中(或者复制消息或者保存消息的指针)，且发送者可继续执行而不必等待。不过，线路容量有限。如果线路满，必须阻塞发送者直到队列中的空间可用为止。

无限容量(unbounded)：队列长度可以无限，因此，不管多少消息都可在其中等待，从不阻塞发送者。

零容量情况称为没有缓冲的消息系统，其他情况称为自动缓冲。

第四章线程 Threads

4.1 概述

引入线程的原因：进程时空开销大、通信代价大、不能很好的利用多处理器系统、不适合并行计算和分布计算的要求。

线程是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和栈组成。

线程是进程中的一个实体，是被系统独立调度和分派的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（程序计数器、一组寄存器和栈），但它可与同属一个进程的其他线程共享进程所拥有的全部资源。

多线程进程的线程共享堆内存和全局变量（代码数据文件属于进程），每个线程都有其独立的一组寄存器值和一个单独的栈。

多线程编程的优点：响应度高 Responsiveness 资源共享 Resource sharing 经济 Economy 多处理器体系结构的利用 Utilzation of Multi-processor Architectures：充分使用多处理器体系结构，以便每个进程能并行运行在不同的处理器上。

一个应用程序通常是作为一个具有多个控制线程的独立进程实现的。

有的时候，一个应用程序可能需要执行多个相似任务。例如，网页服务器接收用户关于网页、图像、声音等的请求。一个忙碌的网页服务器可能有多个(或数千个)客户并发访问它。如果网页服务器作为传统单个线程的进程来执行，那么只能一次处理一个请求。这样，客户必须等待很长的处理请求的时间。

一种解决方法是让服务器作为单个进程运行接收请求。当服务收到请求时，它会创建另一个进程以处理请求。事实上，这种进程创建方法在线程流行之前很常用。如上一章所述，进程创建很耗时间和资源。如果新进程与现有进程执行同样的任务，那么为什么需要这些开销呢？如果一个具有多个线程的进程能达到同样目的，那么将更为有效。这种方案要求网页服务器进程是多线程的。服务器创建一个独立线程以监听客户请求，当有请求时服务器不是创建进程，而是创建线程以处理请求。

线程与进程的比较

调度线程作为调度和分派的基本单位，进程作为资源拥有的基本单位。

并发性不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行。从而使OS具有更好的并发性。

拥有资源进程是拥有资源的一个独立单位，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源。

系统开销 OS创建进程或撤消进程时的开销将显著大于在创建或撤消线程时的开销，进程切换时的开销也远大于线程切换的开销。同一进程的多个线程具有相同的地址空间，它们之间的同步和通讯比较容易。

4.2 多线程模型 Multithreading Models

有两种不同方法来提供线程支持：用户层的用户线程或内核层的内核线程。

用户线程(user threads)受内核支持，而无须内核管理。

内核线程(kernel threads)由操作系统直接支持和管理。

用户级线程和内核级线程是什么？相对的各自有什么优点？

用户级线程：仅由用户程序执行的线程，内核并不知道线程的存在。线程的维护由应用进程通过线程库完成优点：执行速度快，线程切换不需要核心态，调度是应用程序决定的，可以选择最好的算法，可以运行在任何操作系统上 内核级线程：有关线程的所有工作都在内核中完成，应用程序中没有相应的线程管理代码，只有一个到内核的API 优点：一个进程发生阻塞不会影响到其他进程，操作系统可以将多个线程对应到多个内核上并行执行缺点：由于有内核的参与，线程切换需要切换到内核态，开销大

父进程创建子进程后，父进程与子进程同时执行(并发)。主程序调用子程序后，主程序暂停在调用点，子程序开始执行，直到子程序返回，主程序才开始执行。

多对一模型：多个用户线程映射到一个内核线程。任一时刻只有一个线程能访问内核，多个线程不能并行运行在多处理器上。

如果一个线程执行了阻塞系统调用，那么整个进程会阻塞。

一对一模型：每个用户线程映射到一个内核线程，当一个线程阻塞时其他线程可以继续执行。允许多个线程并行地运行在多处理器上。

唯一的缺点是每创建一个用户线程就需要创建一个相应的内核线程，创建内核线程的开销会影响应用程序的性能，所以这种模型的绝大多数实现限制了系统所支持的线程数量。

多对多模型：多对多模型多路复用了许多用户线程到同样数量或更小数量的内核线程上。可以创建任意多的必要用户线程，且相应内核线程能在多处理器系统中并发执行；一个线程阻塞时，另一个线程可以继续执行。

二级模型：一个流行的多对多模型的变种，仍然多路复用了许多用户线程到同样数量或更小数量的内核线程上，但也允许将一个用户线程绑定到某个内核线程上。这个变种被称为二级模型（two-level model）。

4.3 线程库 Thread Library

线程库为程序员提供创建和管理线程的API。主要有两种方法来实现线程库：

在用户空间中提供一个没有内核支持的库，此库的所有代码和数据结构都存在于用户空间中。调用库中的一个函数只是导致了用户空间中的一个本地函数调用，而不是系统调用。

执行一个由操作系统直接支持的内核级的库。此时，库的代码和数据结构存在于内核空间中。

4.4 多线程问题

线程池

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

线程池具有如下主要优点：

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

线程池限制了在任何时候可用线程的数量。这对那些不能支持大量并发线程的系统非常重要

第五章 CPU调度 CPU Scheduling

5.1 基本概念

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

多道程序的目标是在任何时候都有某些进程在运行，以使CPU 使用率最大化。

多道程序的思想较为简单。进程执行直到它必须等待，通常等待某些 I/O 请求的完成。

对于一个简单计算机系统，CPU 就会因此空闲，所有这些等待时间就浪费了，而没有完成任何有用的工作。

采用多道程序设计，系统试图有效地使用这一时间，多个进程可同时处于内存中。当一个进程必须等待时，操作系统会从该进程拿走 CPU 的使用权，而将CPU 交给其他进程，如此继续。在该进程必须等待的时间内，另一个进程就可以拿走 CPU的使用权。

这种调度是操作系统的基本功能。几乎所有的计算机资源在使用前都要调度。当然，CPU 是最重要的计算机资源之一。因此，CPU 调度对于操作系统设计来说很重要。

CPU-I/O区间周期

CPU的成功调度依赖于进程的如下属性：进程执行由CPU 执行和I/O等待周期组成，进程在这两个状态之间切换。进程执行从 CPU区间(CPU burst)开始，在这之后是I/O区间（I/O brust），接着是另一个CPU区间，然后是另一个I/O区间，如此进行下去。最终，最后的CPU区间通过系统请求终止执行。

I/O约束程序通常具有很多短CPU区间。

CPU约束程序可能有少量的长CPU区间。

这种分布有助于选择合适的CPU调度算法。

CPU burst（区间）概念：一个进程在CPU上的一次连续执行过程称为该进程的一个CPU周期。一个CPU周期由进程自我终止。当进程需等待某个事件而进入等待状态时，便终止了它的当前CPU周期。

CPU调度程序

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

抢占调度

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

当一个进程从运行状态(running)切换到等待状态(waiting)(例如，IO 请求，或调用 wait 等待一个子进程的终止)。

当一个进程从运行状态(running)切换到就绪状态(ready)(例如，当出现中断时)。

当一个进程从等待状态(waiting)切换到就绪状态(ready)(例如，I/O 完成)。

当一个进程终止时（terminated)。

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

对于第 2和第 3 两种情况，可以进行选择。

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

我们使用抢占式调度。

分派程序 Dispatcher

与CPU 调度功能有关的另一个部分是分派程序 (dispatcher)。分派程序是一个模块，用来将 CPU的控制交给由短期调度程序选择的进程。其功能包括:

切换上下文

切换到用户模式

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

分派程序应尽可能快，因为在每次进程切换时都要使用。分派程序停止一个进程而启动另一个所要花的时间称为分派延迟 (dispatch latency)。

5.2 调度准则

调度常用的评价标准有：

CPU利用率(CPU utilization)：需要使CPU尽可能忙。

吞吐量(Throughput)：一个时间单元内所完成的进程数量。

周转时间(Turnaround Time)：指从进程提交到进程完成所经历的时间。周转时间为所有时间段之和，包括等待进入内存、在就绪队列中等待、在 CPU 上执行和I/O 执行。周转时间的计算方法如下：周转时间 = 进程完成时问 - 进程提交时间

等待时间：CPU 调度算法并不影响进程运行和执行I/O的时间，它只影响进程在就绪队列中等待所花的时间。等待时间为在就绪队列中等待所花费时间之和。

响应时间：从提交请求到产生第一响应的时间。是开始响应所需要的时间，而不是输出响应所需要的时间。周转时间通常受输出设备速度的限制。

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

上面的指标中：

面向用户的：响应时间、周转时间、优先级

面向系统的：吞吐量、CPU利用率、公平、资源的平衡使用、系统开销

5.3 调度算法

FCFS 先到先服务调度算法

特点：

实现简单，自然

属于非占先调度

平均等待时间一般比较长

有利于长(CPU burst)进程，不利于短(CPU burst)进程。

会画图会计算等待时间即可很简单

SJF最短作业优先调度算法

非占先式 non-preemptive

占先式 preemptive

SJF 调度算法可证明为最佳的，这是因为对于给定的一组进程，SJF 算法的平均等待时间最小。通过将短进程移到长进程之前，短进程等待时间的减少大于长进程等待时间的增加。因而，平均等待时间减少了。

SJF 算法的真正困难是如何知道下一个 CPU 区间的长度。对于批处理系统的长期(作业)调度，可以将用户提交作业时所指定的进程时间极限作为长度。

一个 CPU 区间通常可预测为以前 CPU 区间的测量长度的指数平均。

特点：

有效地降低作业的平均等待时间，提高了系统的吞吐量;

对长作业十分不利。饿死现象。

未完全考虑作业的紧迫程度

估算作业(进程)的执行时间非常困难

优先级调度算法（Priority scheduling）

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

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

轮转法调度（Round-robin,RR）

专门为分时系统设计。类似于FCFS调度但是增加了抢占以切换进程。

定义一个较小的时间单元，称为时间片(time quantum, or time slice)。

为了实现RR调度，将就绪队列保存为进程的FIFO队列（先进先出队列）。新进程增加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程，设置定时器在第一个时间片之后中断，再分配该进程。

接下来可能发生两种情况：

进程需要小于时间片CPU区间：进程本身自动释放CPU，调度程序接着处理就绪队列的下一个进程。

运行进程的CPU区间比时间片长：定时器中断并产生操作系统中断，然后进行上下文切换，将进程加入到就绪队列的尾部，接着CPU调度程序会选择就绪队列中的下一个进程。

RR调度算法是可抢占的。

RR算法的性能很大程度上依赖时间片的大小，需要考虑上下文切换对RR调度的影响。

人们希望时间片要比上下文切换时间长，小的时间片会增加上下文切换开销，但时间片也不要太大，否则会变成FCFS调度。

多级队列调度 Multilevel queue scheduling algorithm

将就绪队列分成多个独立队列，根据进程的属性，如内存大小、进程优先级、进程类型，一个进程被永久地分配到一个队列。每个队列有自己的调度算法。例如，前台进程和后台进程可处于不同队列。前台队列可能采用 RR 算法调度，而后台队列可能采用 FCFS 算法调度。

多级反馈队列调度 Multilevel feedback queue scheduling algorithm

设置多个就绪队列，并为各个队列赋予不同的优先权。第一个队列的优先权最高，第二队列次之，其余队列的优先权逐个降低。

赋予各个队列中进程执行时间片的大小也各不相同，优先权越高，时间片越小。

当一个新进程进入内存后，首先将它放入第一队列的末尾按FCFS原则排队等待调度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统;如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行:如果它在第二队列中运行一个时间片后仍未完成，再依法将它转入第三队列。如此下去，当一个长进程从第一队列降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。

仅当第一队列空闲时，调度程序才调度第二队列中的进程运行;仅当第1~ (i-1) 队列均空时，才会调度第i队列中的进程运行。

如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列，则此时新进程将抢占正在运行进程的处理机，由调度程序把正在运行进程放回第i队列末尾，重新把处理机分配给新进程。

课堂小测一

5.4 多处理器调度 Multiple-Processor Scheduling

5.4.1 多处理器调度的方法

在一个多处理器中，CPU 调度的一种方法是让一个处理器(主服务器)处理所有的调度决定、IO处理以及其他系统活动，其他的处理器只执行用户代码。这种非对称多处理（asymmetric multiprocessing）方法更为简单，因为只有一个处理器访问系统数据结构，减轻了数据共享的需要。

另一种方法是使用对称多处理(symmetric multiprocessing，SMP)方法，即每个处理器自我调度。所有进程可能处于一个共同的就绪队列中，或每个处理器都有它自己的私有就绪进程队列。无论如何，调度通过每个处理器检查共同就绪队列并选择一个进程来执行。

下面的讨论主要是关于SMP的：

5.4.2 处理器亲和性 Processor Affinity

绝大多数SMP系统试图避免将进程从一个处理器移至另一个处理器，而是努力使一个进程在同一个处理器上运行，这被称为处理器亲和性，即一个进程需有一种对其运行所在的处理器的亲和性。

处理器亲和性有几种形式。

当一个操作系统具有设法让一个进程保持在同一个处理器上运行的策略，但不能做任何保证时，则会出现软亲和性(soft affinity)。此时，进程可能在处理器之间移动。

有些系统，如Linux，还提供一个支持硬亲和性(hard affinity)的系统调用，从而允许进程指定它不允许移至其他处理器上。

5.4.3 负载平衡

在SMP系统中，保持所有处理器的工作负载平衡，以完全利用多处理器的优点，这是很重要的。否则，将会产生一个或多个处理器空闲，而其他处理器处于高工作负载状态，并有一系列进程在等待 CPU。负载平衡(load balancing)设法将工作负载平均地分配到SMP系统中的所有处理器上。

值得注意的是：负载平衡通常只是对那些拥有自己私有的可执行进程的处理器而言是必要的。在具有共同队列的系统中，通常不需要负载平衡，因为一旦处理器空闲，他立刻从共同队列中取走一个可执行进程。但同样值得注意的是，在绝大多数支持SMP的当代操作系统中，每个处理器都具有一个可执行进程的私有队列。

负载均衡通常有两种方法：

push migration（从忙的处理器给到不忙的）

对于push migration，一个特定的任务周期地检查每个处理器上的负载，如果发现不平衡，即通过将进程从超载处理器移到（或推送）空闲或不太忙的处理器，从而平均的分配负载。

pull migration（空闲处理器从忙的处理器拿进程）

当空闲处理器从一个忙的处理器上推送(pull)一个等待任务时，发生pull migration

负载平衡会抵消处理器亲和器的优点。即保持一个进程在同一处理器上运行的优点在于，进程可以利用它在处理器缓存中的数据。但pull和push都会使此优点失效。

5.4.4 对称多线程 SMT

通过提供多个物理处理器，SMP系统允许同时运行几个线程。

另一种方法是提供多个逻辑（而不是物理的）处理器来实现。

也被称为超线程（hyperthreading）技术。

SMT的思想是在同一个物理处理器上生成多个逻辑处理器，每个逻辑处理器负责自己的中断处理。

SMT是硬件而不是软件提供的，硬件提供每个逻辑处理器的架构状态的表示以及中断处理方法。

例：两个物理处理器，每个物理处理器有包括两个逻辑处理器，在操作系统看起来这就是有4个处理器可以工作。

5.5 线程调度 Thread Scheduling

系统调度的是内核线程（kernel-level），而不是进程。

用户线程（user-level）由线程库管理，内核并不了解他们。

为了能在CPU上运行，用户线程最终必须映射到相应的内核级线程，尽管这种映射可能是间接的，可能使用轻量级进程（LWP）。

用户线程与内核线程的区别之一在于它们是如何被调度的。在执行多对一模型和多对多模型的系统上，线程库调度用户级线程到一个有效的 LWP 上运行，这被称为进程竞争范围(process-contention scope, PCS)方法，因为CPU竞争发生在属于相同进程的线程之间。当提及线程库调度用户线程到有效的 LWP 时，并不意味着线程实际上就在 CPU 上运行，这需要操作系统将内核线程调度到物理 CPU 上。

为了决定调度哪个内核线程到 CPU,内核采用系统竞争范围(system-contention scope, SCS)方法来进行。采用 SCS 调度方法，竞争 CPU 发生在系统的所有线程中，采用一对一的模型(如 Windows XP、Solaris 9、Linux) 的系统，调度仅使用 SCS 方法。

第六章进程同步

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

为了避免竞争条件，需要确定一段时间内只有一个进程能操作变量，为了实现这种保证，要求进行一定的进程同步。

6.2 临界区问题

假设某个系统有n个进程{Po,P1,…,Pn-1}。每个进程有一个代码段称为临界区(critical section)，在该区中进程可能改变共同变量、更新一个表、写一个文件等。这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行。

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

临界区问题的解答必须满足如下要求：

互斥 mutual exclusion

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

前进 progress

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

有限等待 bounded waiting

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

让权等待 non-busy waiting （补充的要求）

不能进入临界区应释放CPU

假定每个进程的执行速度不为0。然而，不能对m个进程的相对速度做任何假设。

有两种方法用于处理操作系统内的临界区问题：抢占内核(preemptive kernel)与非抢占内核(nonpreemptive kernel)。抢占内核允许处于内核模式的进程被抢占，非抢占内核不允许处于内核模式的进程被抢占。处于内核模式运行的进程会一直运行，直到它退出内核模式、阻塞或自动退出CPU的控制。显然，非抢占内核的内核数据结构从根本上不会导致竞争条件，因为某个时刻只有一个进程处于内核模式。然而，对于抢占内核，就不能这样简单说了，这些抢占内核需要认真设计以确保其内核数据结构不会导致竞争条件。对于SMP体系结构，抢占内核更难设计，因为两个处于内核模式的进程可同时运行在不同的处理器上。

临界资源(Critical resource) 并发进程可以共享系统中的各种资源，但是系统中的某些资源，例如打印机、磁带机、表格、等，虽然他们可以提供给多个进程使用，但在一段时间内却只允许一个进程访问该资源。当一个进程正在访问该资源时，其他欲访问该资源的进程必须等待，仅当该进程访问完并释放该资源后，才允许另一进程对该资源进行访问。把在一段时间内只允许一个进程访问的资源称为临界资源。即临界资源需要互斥访问。

临界区(Critical Section) 把在每个进程中访问临界资源的那段代码称为临界区。

当一个进程正在临界区执行时，其他进程不允许进入他们的临界区执行。

6.3 Peterson算法

对于只有两个进程：

算法一 Algorithm 1

实现了mutual exclusion，没实现progress

只能P0执行完P1执行 P0执行，…交替执行才可以

算法二 Algorithm 2

两个交替进行，可以P1先，也可以P0先

实现了mutual exclusion，仍然没有实现progress

算法三 Peterson算法

turn表明该谁

flag表明想不想

前三个要求都实现了（让权等待未实现），解决了两个进程间的临界区问题。

课后思考

6.4 硬件同步

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

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

然而，在多处理器环境下，这种解决方案是不可行的。在多处理器上由于要将消息传递给所有处理器，所以禁止中断可能很费时。这种消息传递导致进入每个临界区都会延迟进而会降低系统效率。而且，该方法影响了系统时钟(如果时钟是通过中断来加以更新的)。

指令 TestAndSet()，其主要特点是该指令能原子地执行。因此，如果两个指令 TestAndSet()同时执行在不同的CPU上,那么它们会按任意顺序来顺序执行。如果机器支持指令 TestAndSet()，那么可这样实现互斥：声明一个Boolean 变量 lock，初始化为 false。

与指令 TestAndSet 相比，指令 Swap 操作两个数据。与指令TestAndSet 一样，它也原子执行。如果机器支持指令 Swap，那么互斥可按如下方式实现。声明一个全局布尔变量lock，初始化为false。另外，每个进程也有一个局部Boolean变量key。

这些算法解决了互斥，但是并没有解决有限等待要求。

下面这个算法满足了临界区问题的三个要求，共用数据：

这些数据结构初始化为false

6.5 信号量 semaphore

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

用法

二进制信号量

值只能为0或1，有的系统将二进制信号量称为互斥锁，因为它可以提供互斥。可以使用二进制信号量二进制信号量处理多进程的临界区问题，这n个进程共享一个信号量mutex，并初始化为1。

计数信号量

值域不受限制，可以用来控制访问具有若干实例的某种资源。该信号量初始化为可用资源的数量。

每个进程需要使用资源时，需要对信号量执行wait()操作（减少信号量的计数）。当进程释放资源时，需要对该信号量执行signal()操作（增加信号量的计数）。当信号量计数为0时，所有资源被使用。之后，需要使用资源的进程将会被阻塞，直到其计数大于0。

也可以使用信号量来解决同步问题，例如

实现

这里所定义的信号量的主要缺点是要求忙等待(busy waiting)。当一个进程位于其临界区内时，其他任何试图进入临界区的进程都必须在其进入代码中连续的循环。

这种类型的信号量也称自旋锁(spinlock)（会发生忙等待的信号量），这是因为进程在其等待锁时还在运行（自旋锁有其优点，进程在等待锁时不进行上下文切换，而上下文切换可能需要花费相当长的时间。因此，如果锁的占用时间短，那么自旋锁就有用了，自旋锁常用于多处理器系统中，这样一个线程在一个处理器自旋时，另一线程可在另一处理器上在其临界区内执行）。

考试中的信号量是下面这个！！！

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

value的初值表示系统中某类资源的数目，因而又称为资源信号量，每次的wait操作，意味着进程请求一个单位的资源，描述为value--；当value<0时，表示资源已经分配完毕，因而进程自我阻塞，放弃处理机，添加到等待进程队列中。此时，value的绝对值表示在该信号量链中已经阻寒的进程的数目。

每次signal操作表示执行进程释放一个单位资源，故表示为value++，表示资源数目加1。若加1后仍满足value<=0，表示该信号量链中仍有等该资源的进程被阻塞，故还应该将其中的一个进程唤醒。

wait()和signal()必须成对出现，使用资源后必须释放资源。

操作block() 挂起调用他的进程 wakeup(P) 重新启动阻塞进程P的执行

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

死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况：两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。这里的事件是signal()操作的执行。当出现这样的状态时，这些进程就称为死锁(deadlocked)。

说一组进程处于死锁，即组内每个进程都等待一个事件，而该事件只可能由组内的另一个进程产生。

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

同步的经典问题

同步问题PV大题

6.7 管程 Monitors

管程是一种程序结构，结构内的多个子程序形成的多个工作线程互斥(mutual exclusion)的访问共享资源

操作系统必须提供机制以防止时序出错问题。管程为共享数据类型提供了同步机制。条件变量提供了一个方法，以供管程程序阻塞其执行直到其被通知可继续为止。

管城类型的表示包括一组变量的声明（变量的值定义了一个类型实例的状态）和对这些变量操作的子程序和函数的实现。管程类型不能直接为各个进程所使用。因此，在管程内定义的子程序只能访问位于管程内那些局部声明的变量和形式参数。管程的局部变量只能被局部子程序访问。

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。将阻塞原因定义为条件变量condition。通常一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量，每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程。

管程结构确保一次只有一个进程能在管程内活动。

一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。【面向对象的思想】

管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程(相当于通过围墙的门)才能进入，而管程每次只允许一个进程进入管程，从而实现了进程之间的互斥。

管程是在程序设计语言中实现的，需要语言编译器支持管程机制(支持管程的语言包括Java，C#,ConcurrentPascal，Mesa等，但C/C++不支持管程)

第七章死锁

如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变其状态。这种情况称为死锁(deadlock)。

7.2 死锁特征

必要条件

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

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

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

占有并等待 Hold and wait：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。

非抢占 No preemption：资源不能被抢占，即资源只能在进程完成任务后自动释放。

循环等待 Circular wait：有一组等待进程{P0,P1,…,Pn}，P0等待的资源为P1所占有，P1等待的资源为P2所占有，……，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。

在此，强调所有4个条件必须同时满足才会出现死锁。

资源分配图

按以下规则绘制资源分配图：

圆圈代表进程，方框代表资源

方框中的点表示一个资源

分配边：从资源节点指向进程节点，表示资源已经分配。

请求边：从进程指向资源节点，表示正处于阻塞状态，等待资源变为可用。

P = {P1, P2, …, Pn}, 系统活动进程的集合

R = {R1, R2, …, Rm}, 系统所有资源类型的集合

如果分配图没有环，那么系统就没有进程死锁，如果分配图有环，那么可能存在死锁。

如果每个资源类型刚好有一个实例，那么有环就意味着已经出现死锁。如果环涉及一组资源类型，而每个类型只有一个实例，那么就出现死锁。环所涉及的进程就死锁。在这种情况下，图中的环就是死锁存在的充分必要条件。

如果每个资源类型有多个实例，那么有环并不意味着已经出现了死锁。在这种情况下图中的环就是死锁存在的必要条件而不是充分条件。

7.3 死锁处理方法

死锁的处理策略有三种：

可使用协议以预防或避免死锁，确保系统不会进入死锁状态

可允许系统进入死锁状态，然后检测它，并加以恢复。

可忽视这个问题，认为死锁不可能在系统内发生。（鸵鸟策略）

这里第三种方法为绝大多数操作系统所采用，包括UNIX和Windows

7.4 死锁预防

为了确保死锁不会发生，系统可以采用死锁预防或死锁避免方案（注意区分两者）。死锁预防(deadlock prevention)是一组方法，以确保至少一个必要条件不成立，这些方法通过限制如何申请资源的方法来预防死锁。

互斥

对于非共享资源，必须要有互斥条件，通常不能通过互斥条件来预防死锁。

占有并等待

可以使用的协议：

每个进程在执行前申请并获得所有资源。可以实现通过要求申请资源的系统调用在所有其他系统调用之前进行。

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

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

资源利用率(resourceutilization)可能比较低，因为许多资源可能已分配，但是很长时间没有被使用。

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

非抢占

使用协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占。

循环等待

对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。

证明

首先定义函数F来表示每个进程的顺序

7.5 死锁避免

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

每次申请要求系统考虑现有可用资源、现已分配给每个进程的资源和每个进程将来申请与释放的资源，以决定当前申请是否满足或必须等待，从而避免死锁发生的可能性。

安全状态

系统能按某种进程推进顺序为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称该顺序为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。

安全状态不是死锁状态，死锁状态是不安全状态。

ㅤ	最大需求	当前需求T0	当前需求T1
P0	10	5	5
P1	4	2	2
P2	9	2	3

若一共只有12台磁带驱动器和3个进程。

T0时刻，系统处于安全状态，顺序<P1,P0,P2>满足安全条件。

T1时刻，系统处于不安全状态。

该死锁避免的思想为简单地确保系统始终处于安全状态。开始，系统处于安全状态。当进程申请一个可用的资源时，系统必须确定这一资源申请是可以立即分配还是要等待。只有分配后使系统仍处于安全状态，才允许申请采用这种方案，如果进程申请一个现已可用的资源，那么它可能必须等待。因此，与没有采用死锁避免算法相比，这种情况下的资源使用率可能更低。

如果有一个资源分配系统，每种资源类型只有一个实例：资源分配图算法

对于每种资源类型有多个实例的资源分配系统：银行家算法 最著名的死锁避免算法，其思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家货款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程己占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

7.6 死锁检测

如果系统不使用死锁预防或死锁避免算法，那么可能发生死锁情况。在这种情况下，系统可提供一个算法来检查系统状态以确定死锁是否发生，并提供另一个算法来从死锁中恢复(如果死锁确实已发生)。

每种资源类型只有单个实例

从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。

等待（wait-for）图中的由Pi到Pj的边意味着进程Pi等待进程Pj释放一个Pi所需的资源。

当且仅当等待图中有一个环，系统中存在死锁。（环中有什么进程，表示什么进程进入了死锁）

每种资源类型可有多个实例

死锁检测算法，与银行家算法相似

应用检测算法

每次请求分配不能立即允许时，就调用死锁检测算法。在这种情况下，不仅能确定哪些进程处于死锁，而且也能确定哪个特定进程“造成”了死锁(而实际上，每个死锁进程都是资源图的环的一个链节，因此，其实是所有进程一起造成了死锁)。

每小时一次

当CPU使用率低于40%时

7.7 死锁恢复

进程终止（Process Termination）

终止所有的死锁进程

一次只终止一个进程，直到取消死锁循环为止

资源抢占（Resource Preemption）

逐步从进程中抢占资源给其它进程使用，直到死锁环被打破为止

如果要使用抢占来处理死锁，那么有三个问题需要处理：

选择一个牺牲品 select a victim：确定抢占顺序以使代价最小化

回滚 Rollback：必须将进程回滚到某个安全状态，以便从该状态重启进程

饥饿 Starvation：同一进程可能总是被选为牺牲品，这个进程将永远不能完成其指定任务

三、内存管理

第八章内存管理

8.1 背景

基本硬件

基地址寄存器（base register）含有最小的合法物理内存地址，而界限地址寄存器（limit register）决定了范围的大小。

内存空间保护的实现，是通过CPU硬件对用户模式所产生的每一个地址与寄存器的地址进行比较来完成的。

只有操作系统可以通过特殊的特权指令来加载基地址寄存器和界限地址寄存器。

地址绑定 Address Binding

源程序中的地址通常是用符号来表示的。编译器通常将这些符号地址绑定在可重定位的地址（如：本模块开始的第14字节）。链接程序或加载程序将这些可重定位的地址绑定成绝对地址（如74014）。每次绑定都是从一个地址空间到另一个地址空间的映射。

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

编译时 compile time

如果在编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码。如果将来开始地址发生变化，需要重新编译代码。

加载时 load time

如果在编译时不知道进程将驻留在内存的什么地方，那么编译器就必须生成可重定位代码。对于这种情况，最后绑定会延迟到加载时才进行，如果开始地址发生变化，只需重新加载用户代码以引入改变值。

执行时 execution time

如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才进行。

逻辑地址和物理地址的绑定方式有几种，优缺点？

绝对装入：在编译时就确定物理地址，装入程序按照生成的物理地址将程序和数据装入内存
优点：实现简单，绝对地址可以在编译时给出也可以由程序员指定
缺点：只适用于单道程序环境

可重定位装入：根据内存的当前情况，将装入模块装入内存的适当位置，装入时对目标程序的指令和代码进行重定位。地址变换是在装入时一次完成的
优点：无需硬件支持，具有灵活性
缺点：必须在装入时一次性分配连续的地址空间，如果没有足够的空间就不能装入，装入后不可以再移动也不能再申请内存空间

动态运行时装入：装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这个地址转换推迟到真正要执行时才进行
优点：可以将程序分配到不连续的存储区中，根据需要动态申请分配内存，便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
缺点：需要硬件重定位寄存器的支持

逻辑地址空间与物理地址空间

逻辑地址（logical address）：CPU所生成的地址，也叫虚拟地址

物理地址（physical address）：内存单元所看到的地址（即加载到内存地址寄存器中的地址）

运行时从虚拟地址（逻辑地址）到物理地址的映射是由被称为内存管理单元(memory-management unit，MMU)的硬件设备来完成的。

基地址寄存器在这里（↑）称为重定位寄存器(relocation register)。

用户程序决不会看到真正的物理地址。

用户程序处理逻辑地址，内存映射硬件将逻辑地址转变为物理地址。

逻辑地址空间绑定到单独的一套物理地址空间

动态加载

了解概念即可

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

动态加载的优点是不用的子程序决不会被加载。

动态链接与共享库

动态链接库（dynamically linked library）

动态链接的概念与动态加载相似，只不过不是将加载延迟到运行时，而是将链接延迟到运行时。

如果有动态链接，二进制镜像中对每个库程序的引用都有一个存根(stub)。

可以理解为被多个进程调用的一段代码当执行存根时，存根会用子程序地址来替换自己，并执行子程序。采用这种方案，使用语言库的所有进程只需要一个库代码副本就可以了。

8.2 交换 Swap

这种交换策略的变种被用在基于优先级的调度算法中。如果有一个更高优先级的进程且需要服务，内存管理器可以交换出低优先级的进程，以便可以装入和执行更高优先级的进程。当更高优先级的进程执行完后，低优先级进程可以交换回内存以继续执行。这种交换有时称为滚出(roll out)和滚入(roll in)。

8.3 连续内存分配 Contiguous Memory Allocation

每个进程位于一个连续的内存区域。

8.3.2 内存分配

多分区方法 Multiple-partition method

将内存分为多个固定大小的分区，固定分区不拆分分区，下面的可变分区需要拆分分区。

固定分区 Fixed-sized partitions

将内存空间划分成若干个固定大小的区域，在每个区域可装入一个进程。

可变分区 variable-partition

操作系统中有一个表，用于记录哪些内存可用，哪些内存已被占用。一开始，所有内存都可用于用户进程，因此可做为一大块可用内存，称为孔（hole）

动态存储分配 Dynamic Storage Allocation

从一组可用孔中选择一个空闲孔的最为常用方法有首次适应(first-fit)、最佳适应(best-fit)、最差适应(worst-fit)：

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

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

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

8.3.3 碎片

首次适应方法和最佳适应方法都有外部碎片问题（external fragmentation）：可用内存之和可以满足请求，但并不连续

内部碎片（internal fragmentation）：进程所分配的内存比所要的要大，这两个数字之差称为内部碎片，这部分内存在分区内，但又不能使用。

可以使用紧缩（compaction）来解决外部碎片问题。

移动内存内容，以便所有空闲空间合并成一整块。仅在重定位是动态并在运行时可采用。

另一种解决方法是允许物理空间为非连续。

8.4 分页 Pageing

分页中CPU和操作系统各自承担了哪些工作？ CPU：将物理地址转换为逻辑地址操作系统：将逻辑内存和物理内存分成大小相等的块

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。

我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页内存管理方案允许进程的物理地址空间可以是非连续的。分页避免了将不同大小的内存块匹配到交换空间上这样的麻烦。

8.4.1 基本方法

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

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

页大小（与帧大小一样）是由硬件来决定的。页面大小应是2的整数幂，同时页面大小应该适中。

地址结构：前一部分为页号，后一部分为偏移量。地址结构决定了寻址空间的大小。

页大小为，逻辑地址空间为

例1：k

逻辑地址LA：10

10/4 = 2……2

页号(p)：2

页偏移(d)：2

在页表中查询页号为2对应的帧号(f)为1

即物理地址为：1*4+2=6 f*p+d=PA

例2：page size（ps）：1K=1024

LA=1005

页表：

1025/1024 = 1……1

p：1 d：1 PA = 4*1K+1

采用分页技术并不会产生外部碎片，但有内部碎片。

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

由于操作系统管理物理内存，它必须知道物理内存的分配细节：哪些帧已占用，哪些帧可用，总共有多少帧，等等。这些信息通常保存在称为帧表的数据结构中。

在帧表(frame table)中，每个条目对应着一个帧，以表示该帧是空闲还是已占用，如果占用，是被哪个(或哪些)进程的哪个页所占用。

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

8.4.2 硬件支持

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

方法一：将页表作为一组专用寄存器来实现。这些寄存器应用高速逻辑电路来构造，以便有效地进行分页地址的转换。由于对内存的每次访问都要经过分页表，因此效率很重要。CPU调度程序再装入其他寄存器时，也需要装入这些寄存器。

如果页表比较小，那么页表使用寄存器还是比较合理的。

方法二：将页表放在内存中

Page-table base register (PTBR) points to the page table 页表基寄存器指向页表 Page-table length register (PTLR) indicates size of the page table 页表长度寄存器

访问一个字节需要两次内存访问（一次用于页表条目，一次用于字节），内存访问速度会减半

对此的解决方案为：采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲区（TLB）。TLB是关键的快速内存。由两部分组成：键和值。

TLB与页表一起按如下方法使用：TLB只包括页表中的一小部分条目。当CPU产生逻辑地址后，其页号提交给TLB。如果找到页号，那么也就得到了帧号，并可用来访问内存。整个任务与不采用内存映射相比，其时间增加不会超过10%。如果页码不在 TLB 中(称为 TLB 失效)，那么就需要访问页表。当得到帧号后，就可以用它来访问内存(如图8.11所示)。同时，将页号和帧号增加到TLB中，这样下次再用时就可很快查找到。如果 TLB中的条目已满，那么操作系统会选择一个来替换。替换策略有很多，从最近最少使用替换(LRU)到随机替换等。另外，有的TLB允许有些条目固定下来，也就是说它们不会从 TLB 中被替换。通常内核代码的条目是固定下来的。

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

页号在 TLB 中被查找到的百分比称为命中率。80%的命中率意味着有80%的时间，可以在 TLB 中找到所需的页号。

假如查找TLB需要20ns，访问内存需要100ns，如果访问位于TLB中的页号，那么采用内存映射访问需要120ns。

如果不能在 TLB中找到，那么必须先访问位于内存中的页表以得到帧号(100ns)，并进而访问内存中的所需字节(100ns)，这总共要花费220ns。为了得到有效内存访问时间，必须根据概率来对每种情况进行加权。

有效内存访问时间=0.80x120+0.20x220=140(ns)

对于这种情况，现在内存访问速度要慢40%(从100~140ns)。

如果命中率为98%，那么有效内存访问时间=0.98x120+0.02x220=122(ns)

由于提高了命中率，现在内存访问速度只慢了22%。

8.4.3 保护

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

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

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

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

8.4.4 共享页

如果代码是可重入代码，则可以共享

可重入代码是不能自我修改的代码，他从不会在执行期间改变。

8.5 页面结构

8.5.1 层次页表 Hierarchial Page Tables

两级分页算法

8.5.2 哈希页表 Hashed Page Table

处理超过 32位地址空间的常用方法是使用哈希页表，并以虚拟页码作为哈希值。

哈希页表的每一条目都包括一个链表的元素,这些元素哈希成同一位置(要处理碰撞)。每个元素有3个域：(1)虚拟页码，(2)所映射的帧号，(3)指向链表中下一个元素的指针。

该算法按如下方式工作：虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的每一个元素的第一个域相比较。如果匹配，那么相应的帧号(第二个域)就用来形成物理地址；如果不匹配，那么就对链表中的下一个节点进行比较，以寻找一个匹配的页号。

8.5.3 反向页表 Inverted Page Table

通常，每个进程都有一个相关页表，该进程所使用的每个页都在页表中有一项。

反向页表对于每个真实的内存页或帧才有一个条目，每个条目包含保存在真实内存位置的页的虚拟地址以及拥有该页的进程的信息。因此，整个系统只有一个页表，对每个物理内存的页只有一条相应的条目。

虽然这种方案减少了存储每个页表所需要的内存空间，但是当引用页时，它增加了查找页表所需要的时间。由于反向页表按物理地址排序，而查找是根据虚拟地址，因此可能需要查找整个表来寻求匹配。这种查找会花费很长时间。为了解决这一问题，可以使用 8.5.2小节介绍的哈希页表来将查找限制在一个或少数几个页表条目。当然，每次访问哈希页表也为整个过程增加了一次内存引用，因此一次虚拟地址引用至少需要两个内存读：一个查找哈希页表条目，另一个查找页表。为了改善性能，可以在访问哈希页表时先查找TLB。

8.6 分段 Segmentation

8.6.1 基本方法

为实现简单起见，段是编号的，是通过段号而不是段名来引用的。因此，逻辑地址由有序对组成：<seqment-number,offset>（<段号, 段内偏移>）

8.6.2 硬件

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

内存管理大题

第九章虚拟内存

虚拟内存技术允许执行进程不必完全在内存中。

这种方案的一个显著优点就是程序可以比物理内存大。

9.1 背景

能够执行只有部分在内存中的程序可带来很多好处：

程序不再受现有的物理内存空间限制。用户可以为一个巨大的虚拟地址空间(virtual address space)编写程序，简化了编程工作量。

因为每个用户程序使用了更少的物理内存，所以更多的程序可以同时执行，CPU使用率也相应增加，而响应时间或周转时间并不增加。

由于载入或交换每个用户程序到内存内所需的I/O会更少，用户程序会运行得更快。

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

虚拟内存（virtual memory）将用户逻辑内存与物理内存分开。

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

通过将共享对象映射到虚拟地址空间，系统库可为多个进程所共享。

类似的，虚拟内存允许进程共享内存。两个或多个进程之间可以通过共享内存来通信。虚拟内存允许一个进程创建内存区域，以便与其他进程进行共享。共享内存区域的进程认为它是其虚拟地址空间的一部分，而事实上这部分是共享的。

虚拟内存允许在系统调用fork()创建进程期间共享页，从而加快进程创建。

9.2 按需调页

按需调页（demand paging），在需要时才调入相应的页。

常为虚拟内存系统所采用。

对于按需调页虚拟内存，只有程序执行时需要才载入页，那些从未访问的页不会调入到物理内存。

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

因此，在讨论有关按需调页时，需要使用调页程序而不是交换程序。

9.2.1 基本概念

有效-无效位（valid-invalid bit）

用来区分哪些页在内存里，哪些页在硬盘上。

v → in-memory 有效，合法且在内存中 i → not-in-memory （初始化全部为i）无效或有效但在磁盘上

当进程试图访问那些尚未调入到内存的页时，会产生页错误陷阱（page-fault trap）

处理这种页错误的程序比较简单：

①检查进程的内部页表(通常与PCB一起保存)，以确定该引用是合法还是非法的地址访问。

②如果引用非法，那么终止进程。如果引用有效但是尚未调入页面，那么现在应调入。

③找到一个空闲帧(例如，从空闲帧链表中选取一个)。

④调度一个磁盘操作，以便将所需要的页调入刚分配的帧。

⑤当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。

⑥重新开始因陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中。

缺页中断与一般中断的不同点：缺页中断发生在指令执行期间，一般的中断发生在上一条指令执行完毕和下一条指令执行之前。

一种极端的情况是所有的页都不在内存中，就开始执行进程。当操作系统将指令指针指向进程的第一条指令时，由于其所在的页并不在内存中，进程立即出现页错误。当页调入内存时，进程继续执行，并不断地出现页错误直到所有所需的页均在内存中。这时，进程可以继续执行且不出现页错误。这种方案称为纯粹按需调页(pure demand paging)：只有在需要时才将页调入内存。

请求调页的关键要求是能够在页错误后重新执行指令。在出现页错误时，保存中断进程的状态（寄存器、条件代码、指令计数器），必须能够按完全相同的位置和地址重复开始执行进程，只不过现在所需要的页已在内存中且可以访问。对绝大多数情况来说，这种要求容易满足。页错误可能出现在任何内存引用中。如果页错误出现在指令获取时，那么可以再次获取指令、再次译码指令，然后再次获取操作数。

9.2.2 按需调页的性能

内存访问时间：ma

页错误概率：p （0 ≤ p ≤ 1）

p越接近于0，页错误越少

有效访问时间（effective access time）= (1 - p) * ma + p * 页错误时间

为了计算有效访问时间，必须知道处理页错误需要多少时间。页错误会引起如下序列的动作产生： 1. 陷入到操作系统。 2. 保存用户寄存器和进程状态: 3. 确定中断是否为页错误。 4. 检查页引用是否合法并确定页所在磁盘的位置。 5. 从磁盘读入页到空闲帧中。 a. 在该磁盘队列中等待，直到处理完读请求。 b. 等待磁盘的寻道和/或延迟时间。 c. 开始将磁盘的页传到空闲帧。 6. 在等待时，将CPU分配给其他用户(CPU调度，可选)。 7. 从 I/O 子系统接收到中断(以示 I/O 完成)。 8. 保存其他用户的寄存器和进程状态(如果执行了第6步)。 9. 确定中断是否来自磁盘。 10. 修正页表和其他表以表示所需页现已在内存中。 11. 等待 CPU 再次分配给本进程。 12. 恢复用户寄存器、进程状态和新页表，再重新执行中断的指令。

以上步骤并不是在所有情况下都是必需的。例如，假设在第6步，在执行I/O时，将CPU分配给另一进程。这种安排允许多道程序以提高CPU 使用，但是在执行完 I/O 时也需要额外的时间来重新启动页错误处理程序。

不管如何，都有如下三个主要的页错误处理时间：

处理页错误中断

读入页

重新启动进程

1s【秒】 = 1000ms【毫秒】
1ms【毫秒】 = 1000μs【微秒】
1μs【微秒】 = 1000ns【纳秒】
1ns 【纳秒】= 1000ps【皮秒】 — 1s【秒】 = 1000ms【毫秒】 1ms【毫秒】 = 1000μs【微秒】 1μs【微秒】 = 1000ns【纳秒】 1ns 【纳秒】= 1000ps【皮秒】

有效访问时间与页错误率直接有关，对于按需调页，降低页错误率是非常重要的。

按需调页的另一个重要方面是交换空间的处理和使用。磁盘 I/O 到交换空间通常比到文件系统要快。这是因为交换空间是按大块来分配的，并不使用文件查找和间接分配方法(第 12章)。

因此，如果在进程开始时将整个文件镜像复制到交换空间，并从交换空间执行按页调度，那么有可能获得更好的调页效果。（进程启动慢）

另一选择是开始时从文件系统中进行按需调页，但是当出现页置换时则将页写入交换空间，这种方法确保只有所需的页才从文件系统中调入，而以后出现的调页是从交换空间中读入的。（效率高一些）

9.3 写时复制 copy-on-write

例如，假设子进程试图修改含有部分栈的页，且操作系统能识别出该页被设置为写时复制页，那么操作系统就会创建一个该页的副本，并将它映射到子进程的地址空间内。这样，子进程会修改其复制的页，而不是父进程的页。

采用写时复制技术，很显然只有能被进程修改的页才会被复制；所有非修改页可为父进程和子进程所共享。注意只有可能修改的页才需要标记为写时复制。不能修改的页(即包含可执行代码的页)可以为父进程和子进程所共享。

9.4 页面置换

如果一个进程具有10页而事实上只使用其中的5页，那么请求页面调度就节省了用以装入（从不使用的）另5页所必需的I/O。也可以通过运行两倍的进程以增加多道程序的程度。因此，如果有40帧，那么可以运行8个进程，而不是当每个进程都需要10帧（其中5个决不使用）时只能运行4个进程。

如果增加了多道程序的程度，那么会过度分配(over-allocating)内存。如果运行6个进程，且每个进程有10页大小但事实上只使用其中的5页，那么就获得了更高的CPU利用率和吞吐量，且有10帧可作备用。然而，有可能每个进程，对于特定数据集合，会突然试图使用其所有的 10 页，从而产生共需要60 帧，而只有40 帧可用。

内存的过度分配会出现以下问题。当一个用户进程执行时，一个页错误发生。操作系统会确定所需页在磁盘上的位置，但是却发现空闲帧列表上并没有空闲帧，所有内存都在使用。

这时操作系统会有若干选择：

它可以终止用户进程，这种选项并不是最佳选择。

操作系统也可以交换出一个进程，以释放其所有帧，并降低多道程序的级别。这种选择在有些环境下是好的

更为常用的解决方法：页置换(page replacement)

页面置换算法大题

9.4.1 基本页置换

页置换采用如下方法。如果没有空闲帧，那么就查找当前没有使用的帧，并将其释放。可采用这样的方式样来释放一个帧：将其内容写到交换空间，并改变页表(和所有其他表)以表示该页不在内存中。现在可使用空闲帧来保存进程出错的页。修改页错误处理程序以包括页置换： ① 查找所需页在磁盘上的位置。 ②查找一个空闲帧： a. 如果有空闲帧，那么就使用它。 b. 如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧(victim frame)。 c. 将“牺牲”帧的内容写到磁盘上，改变页表和帧表。 ③将所需页读入(新)空闲帧，改变页表和帧表。 4)重启用户进程。注意，如果没有帧空闲，那么需要采用两个页传输(一个换出，一个换入)。这种情况实际上把页错误处理时间加倍了，且也相应地增加了有效访问时间。

可以通过使用修改位(modify bit)或脏位(dirty bit)以降低额外开销。每页或帧可以有一个修改位，通过硬件与之相关联。每当页内的任何字或字节被写入时，硬件就会设置该页的修改位以表示该页已修改。如果修改位已设置，那么就可以知道自从磁盘读入后该页已发生了修改。在这种情况下，如果该页被选择为替换页，就必须要把该页写到磁盘上去。然而，如果修改位没有设置，那么也就知道自从磁盘读入后该页并没有发生修改。因此，磁盘上页的副本的内容没有必要(例如用其他页)重写，因此就避免了将内存页写回磁盘上：它已经在那里了。这种技术也适用于只读页(例如，二进制代码的页)。这种页不能被修改。因此，如需要，可以放弃这些页。这种方案可显著地降低用于处理页错误所需要的时间，因为如果页没有修改它，可以降低一半的 I/O 时间。

引用串（reference string）内存的引用序列

9.4.2 FIFO页置换 First-In-First-Out

好的方面：所替代的页可能是很久以前使用的、现已不再使用的初始化模块。

差的方面：所替代的页可能包含一个以前初始化的并且不断使用的常用变量。

Belady异常：对有的页置换算法，页错误率可能会随着所分配的帧数的增加而增加，而原期望为进程增加内存会改善其性能。

9.4.3 最优置换 OPT optimal page-replacement algorithm

9.4.4 LRU页置换 least-recently-used algorithm

最近最少使用算法

计数器

每个页表项关联一个使用时间域，并为CPU增加一个逻辑时钟或计数器。对每次内存引用，计数器都会增加。 置换具有最小时间的页（value越小，说明离现在时间越长）

实现LRU 置换的另一个方法是采用页码栈。每当引用一个页，该页就从栈中删除并放在顶部。这样，栈顶部总是最近使用的页，底部总是LRU页。由于必须从栈中部删除项，所以该栈可实现为具有头指针和尾指针的双向链表。这样，删除一页并放在栈顶部在最坏情况下需要改变6个指针。虽说每个更新有点费时，但是置换不需要搜索；尾指针指向栈底部，就是LRU页。

最优置换和LRU置换都没有 Belady异常。这两个都属于同一类算法,称为栈算法(stack algorithm)，都绝不可能有Belady异常。

9.4.5 近似LRU页置换

页表内的每项都关联着一个引用位(reference bit)。每当引用一个页时(无论是对页的字节进行读或写)，相应页表的引用位就被硬件置位。

开始，操作系统会将所有引用位都清零。随着用户进程的执行，与引用页相关联的引用位被硬件置位(置为1)。之后，通过检查引用位，能够确定哪些页使用过而哪些页未使用过。虽然不知道使用顺序,但是知道哪些页用过而哪些页未用过。这信息是许多近似 LRU页置换算法的基础。

1. 附加引用位算法

通过在规定时间间隔里记录引用位，可以获得额外顺序信息。可以为位于内存内的每个表中的页保留一个8位的字节。

在规定时间间隔(如，每100ms)内，时钟定时器产生中断并将控制转交给操作系统。操作系统把每个页的引用位转移到其8位字节的高位，而将其他位向右移一位，并抛弃最低位。这些8位移位寄存器包含着该页在最近8个时间周期内的使用情况。

例如，如果移位寄存器含有00000000，那么该页在8个时间周期内没有使用；如果移位寄存器的值为11111111，那么该页在过去每个周期内都至少使用过一次。

具有值为11000100的移位寄存器的页要比值为01110111的页更为最近使用。如果将这8位字节作为无符号整数，那么具有最小值的页为LRU页，且可以被置换。注意这些数字并不唯一。可以置换所有具有最小值的页，或在这些页之间采用FIFO 来选择置换。

2.二次机会算法

二次机会置换的基本算法是FIFO置换算法。当要选择一个页时，检查其引用位。如果其值为0，那么就直接置换该页。如果引用位为1，那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。（这句话严格来说是不对的，因为没有entry存放时间。如果page组成一个FIFO队列中，就是把该页放到队列的尾部）

一种实现二次机会算法(有时称为时钟算法)的方法是采用循环队列。用一个指针表示下次要置换哪一页。当需要一个帧时，指针向前移动直到找到一个引用位为0的页。在向前移动时，它将清除引用位。一旦找到牺牲页，就置换该页，新页就插入到循环队列的该位置。注意：在最坏情况下，所有位均已设置，指针会遍历整个循环队列，以便给每个页第二次机会。它将清除所有引用位后再选择页来置换。这样，如果所有位均已设置，那么二次机会置换就变成了 FIFO 置换。

3.增强型二次机会算法

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

组合	含义
(0, 0)	近期既没有被使用过，也没有被修改过，是最佳的页面置换。
(0, 1)	近期没有被使用过但是被修改过的页面，是不太好的页面置换，因为需要将该页面写回磁盘。
(1, 0)	近期被使用过但是没有被修改的页面，可能很快会被再次使用。
(1, 1)	近期既被使用过又被修改过，可能很快会再次使用，并且置换时需要写回磁盘。

每个页都属于这四种类型之一。当页需要置换时，可使用时钟算法，不是检查所指页的引用位是否设置，而是检查所指页属于哪个类型。置换在最低非空类中所碰到的页。注意在找到要置换页之前，可能要多次搜索整个循环队列。

这种方法与简单时钟算法的主要差别是这里给那些已经修改过的页以更高的级别，从而降低了所需I/O 的数量。

9.4.6 基于计数的页置换

还有许多其他算法可用于页置换。例如，可以为每个页保留一个用于记录其引用次数的计数器，并可形成如下两个方案。

最不经常使用页置换算法(least frequently used(LFU) page-replacement algorithm)

置换计数最小的页；这种选择的理由是活动页应该有更大的引用次数。

这种算法会产生如下问题：一个页在进程开始时使用很多，但以后就不再使用。由于其使用过很多，所以它有较大次数，所以即使不再使用仍然会在内存中。解决方法之一是定期地将次数寄存器右移一位，以形成指数衰减的平均使用次数。

最常使用页置换算法(most frequently used (MFU) page-replacement algorithm)

置换计数最大的页；基于如下理论：具有最小次数的页可能刚刚调进来，且还没有使用。

9.4.7 页缓冲算法

不是独立的页置换算法，与页替换算法协作。

除了特定页置换算法外，还经常采用其他措施。例如，系统通常保留一个空闲缓冲池。当出现页错误时，会像以前一样选择一个牺牲帧。然而，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。这种方法允许进程尽可能快地重启，而无须等待牺牲帧页的写出。当在牺牲帧以后写出时，它再加入到空闲帧池。

9.4.8 应用程序与页置换

在有些情况下，应用程序通过操作系统虚拟内存来访问数据会比操作系统不提供任何缓冲区更坏。数据库就是一个例子，它可提供自己的内存管理与I/O缓冲。这类程序比提供通用算法的操作系统更能理解自己的内存使用与磁盘使用。

因此有的操作系统允许特殊程序将磁盘作为逻辑块数组使用，而不需要通过文件系统的数据结构，这种数组有时称为生磁盘(raw disk)，而对数组的I/O成为生I/O。

9.5 帧分配

9.5.1 帧的最少数量

保证进程正常运行所需的最小Frame数，少于此值进程将无法运行。

分配至少最少数量的帧的原因：

性能。显然，随着分配给每个进程的帧数量的减少，页错误会增加，从而减慢进程的执行。

当在指令完成之前出现页错误时，该指令必须重新执行。因此，必须有足够的帧来容纳所有单个指令所引用的页。

9.5.2 分配算法

在n个进程之间分配m个帧：

平均分配（equal allocation）

比例分配（proportion allocation）：根据进程大小，而将可用内存分配给每个进程

9.5.3 全局分配与局部分配

全局置换(global replacement)允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程，即一个进程可以从另一个进程中拿到帧。

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

全局置换算法的一个问题是进程不能控制其页错误率。

但是，因为局部置换不能使用其他进程的不常用的内存，所以会阻碍一个进程。因此，全局置换通常会有更好的系统吞吐量，且更为常用。

9.6 系统颠簸

现象：如果进程没有它所需要的活跃使用的帧，那么它会很快产生页错误。这时，必须置换某个页。然而，其所有页都在使用，它置换一个页，但又立刻再次需要这个页。因此，它会一而再地产生页错误，置换一个页，而该页又立即出错且需要立即调进来。

定义：这种频繁的页面调度行为称为颠簸（thrashing）

本质：如果一个进程在换页上用的时间要多于执行时间，那么这个进程就在颠簸。

9.6.1 系统颠簸的原因 P294

操作系统在监视CPU的使用率。

如果CPU使用率太低，那么向系统中引入新进程以增加多道程序的程度。

采用全局置换算法，它会置换页而不管这些页是属于哪个进程的

CPU调度程序发现CPU使用降低，因此会增加多道程序的程度。新进程试图从其他运行进程中拿到帧，从而引起更多页错误，形成更长的调页设备的队列。因此，CPU使用率进一步降低，CPU调度程序试图再增加多道程序的程度。这样就出现了系统颠簸，系统吞吐量陡降，页错误显著增加。因此，有效内存访问时间增加。最终因为进程主要忙于调页，系统不能完成一件工作。

通过局部置换算法(local replacement algorithm)（或优先置换算法(priority replacement algorithm))能限制系统颠簸。采用局部置换，如果一个进程开始颠簸，那么它不能从其他进程拿到帧，且不能使后者也颠簸。然而这个问题还没有完全得到解决。如果进程颠簸，那么绝大多数时间内也会排队来等待调页设备。由于调页设备的更长的平均队列页错误的平均等待时间也会增加。因此，即使对没有颠簸的进程，其有效访问时间也会增加。

为了防止颠簸，必须提供进程所需的足够多的帧。

工作集合策略是研究一个进程实际正在使用多少帧。这种方法定义了进程执行的局部模型(locality model)。

解决方案：
使用局部置换算法限制系统抖动
使用工作集模型
控制页错误频率

9.6.2 工作集合模型

工作集合模型(working-set model)是基于局部性假设的。该模型使用参数Δ定义工作集合窗口(working-set window)。其思想是检查最近Δ个页的引用。这最近Δ个引用的页集合称为工作集合(working set)。如果一个页正在使用中，那么它就在工作集合内。如果它不在使用，那么它会在其上次引用的Δ时间单位后从工作集合中删除。因此，工作集合是程序局部的近似。

工作集合的精确度与Δ的选择有关。如果Δ太小，那么它不能包含整个局部；如果Δ太大，那么它可能包含多个局部。在最为极端的情况下，如果Δ为无穷大，那么工作集合为进程执行所接触到的所有页的集合。

这种工作集合策略防止了颠簸，并尽可能地提高了多道程序的程度，优化了CPU的利用率。

工作集合模式的困难是跟踪工作集合。工作集合窗口是移动窗口。在每次引用时，会增加新引用，而最老的引用会失去。如果一个页在工作集合窗口内被引用过，那么它就处于工作集合内。

9.6.3 页错误频率

颠簸具有高错误率，因此，需要控制页错误率。当页错误率太高时，进程需要更多帧，类似的，如果页错误率太低，那么进程可能有太多的帧。为所期望的页错误设置上限和下限。如果实际页错误率超过上限，那么为进程分配更多的帧，如果实际页错误率低于下限，那么可以从该进程中移走帧。

如果页错误增加且没有可用帧，那么必须选择一个进程暂停。接着，可将释放的帧分配给那些具有高页错误率的进程。

9.7 内存映射文件

知道思想，允许文件I/O像内存访问操作一样。

文件的内存映射可将一磁盘块映射成内存的一页(或多页)。开始的文件访问按普通请求页面调度来进行，会产生页错误。这样，一页大小的部分文件从文件系统读入物理页(有的系统会一次读入多个一页大小的内容)。以后文件的读写就按通常的内存访问来处理，由于是通过内存操作文件而不是使用系统调用read()和write()，从而简化了文件访问和使用。

注意对映射到内存中的文件进行写可能不会立即写到磁盘上的文件中。有的操作系统定期检查文件的内存映射页是否改变，以选择是否更新到物理文件。关闭文件会导致内存映射的数据写回到磁盘，并从进程的虚拟内存中删除。

有的操作系统只能通过特定的系统调用提供内存映射，而通过标准的系统调用处理所有其他文件IO。然而，有的系统不管文件是否说明为内存映射，都选择对文件进行内存映射。

多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享。其中任一进程修改虚拟内存中的数据，都会为其他映射相同文件部分的进程所见。根据虚拟内存的相关知识，可以清楚地看到内存映射部分的共享是如何实现的：每个共享进程的虚拟内存表都指向物理内存的同一页，该页有磁盘块的复制。这种内存共享如图所示。内存映射系统调用还支持写时复制功能，允许进程共享只读模式的文件，但也有它们所修改数据的各自副本。为了协调共享数据的访问，有关进程可使用第6章所述的互斥机制。

内存映射文件（Memory-Mapped Fies）与虚拟内存有些相似，将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行文件IO操作，也无须对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。

9.8 内核内存（kernel memory）的分配

当用户态进程需要额外内存时，可以从内核所维护的空闲页帧链表中获取页。该链表通常由页替换算法(如9.4节所述的)来更新，且如前所述，这些页通常分散在物理内存中。另外，请记住，如果用户进程只需要一个字节的内存，那么会产生内部碎片，这是因为进程会得到整个页帧。

但是，内核内存的分配通常是从空闲内存池中获取的，而并不是从满足普通用户模式进程的内存链表中获取的。这主要有两个原因:

①内核需要为不同大小的数据结构分配内存，其中有的不到一页。因此，内核必须谨慎使用内存，并试图减低碎片浪费。这一点非常重要，因为许多操作系统的内核代码与数据不受分页系统控制。

②用户进程所分配的页不必要在连续的物理内存中。然而，有的硬件要直接与物理内存打交道，而不需要经过虚拟内存接口，因此需要内存常驻在连续的物理页中。

下面讨论对内核进程进行内存管理的两个方法。

9.8.1 Buddy系统

从物理上连续的大小固定的段上进行分配。内存按2的幂的大小来进行分配。

一个优点是可通过合并而快速的形成更大的段。

缺点是由于调整到下一个2的幂容易产生碎片。

9.8.2 slab分配

（没有碎片损失）

slab是由一个或多个物理上连续的页组成的，高速缓存(cache)含有一个或多个slab。每个内核数据结构都有一个cache，如进程描述符、文件对象、信号量等。每个cache含有内核数据结构的对象实例。例如，信号量cache存储着信号量对象，进程描述符cache 存储着进程描述符对象。下图描述了slab、cache 及对象三者之间的关系。该图中有两个3KB大小的内核对象和三个7KB大小的内核对象。它们分别位于各自的 cache 上。

slab 分配算法采用 cache存储内核对象。当创建cache 时,起初包括若干标记为空闲的对象。对象的数量与 slab的大小有关。例如，12KB的slab(包括三个连续的页)可存储6个2KB 大小的对象。开始，所有对象都标记为空闲。当需要内核数据结构的对象时，可以从 cache 上直接获取，并将该对象标记为使用(used)。

Linux的 slab 可有三种状态:

满的：slab 中的所有对象被标记为使用

空的：slab 中的所有对象被标记为空闲

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

slab 分配器首先从部分空闲的 slab 进行分配。如没有，则从空的slab进行分配。如没有，则从物理连续页上分配新的 slab，并把它赋给一个 cache，然后再从新 slab 分配空间。

两个优点：

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

碎片不是问题，这是因为每个内核数据结构都有相应的 cache，而每个 cache 都由若干 slab 组成，而每个 slab 又分为若干个与对象大小相同的部分。因此，当内核请求对象内存时，slab 分配器可以返回刚好可以表示对象所需的内存。

内存请求可以快速满足。

slab分配器对于需要经常不断分配内存、释放内存来说特别有效，而操作系统经常这样做。内存分配与释放可能费时。然而，由于对象预先创建，所以可从 cache上快速分配。另外,当用完对象并释放时，只需要标记为空闲并返回给cache，以便下次再用。

内存请求可以快速满足。

9.9 其他考虑

9.9.1 预调页

纯按需调页系统的一个显著特性是当一个进程开始时会出现大量页错误。这种情况是由于试图将最初局部调入到内存的结果。在其他时候也会出现同样情况。

预调页(prepaging)试图阻止这种大量的初始调页。这种策略就是同时将所需要的所有页一起调入到内存中。

例如，对于采用工作集合的系统，可以为每个进程保留一个位于其工作集合内的页的列表。如果必须暂停一个进程(由于IO 等待或缺少空闲帧)，那么要记住该进程的工作集合。当该进程需要重启时(IO完成或有足够多的空闲帧)，在重启进程之前会自动调入位于其工作集合内的所有页。

预调页有时可能比较好。关键问题是采用预调页的成本是否小于处理相应页错误的成本。通过预调页而调回内存的许多页可能没有被使用。

9.9.2 页大小

如何选择页大小呢?

一方面是要考虑页表大小。对于给定虚拟内存空间，降低页大小增加了页的数量，因此也增加了页表大小。因为每个活动进程必须有其自己的页表，所以较大的页是比较理想的。

另一方面，较小的页可更好地利用内存。如果进程从位置00000开始分配内存，且一直继续到它所需要的内存为止，那么它可能不能刚好在页边界处结束。因此，最后页的一部分必须分配(因为页是分配单元)但并未使用(形成内部碎片)。为了减少碎片，需要小的页。

另一个问题是页读写所需要的时间。IO 时间包括寻道、延迟和传输时间。传输时间与传输量(即页的大小)成正比，这看似需要小页。然而，在12.1.1小节将看到寻道和延迟时间远远超过传输时间。因此，为了最小化 I/O时间，需要较大的页。

然而，因为局部性得以改善，采用较小的页，总的I/O就会降低。较小的页允许每个页更精确地匹配程序局部。采用较小的页，会有更好的精度，以允许只处理确实需要的内存。采用较大的页，不但必须分配且传输所需要的，而且还包括其他碰巧在页内的不需要的内容。因此，更小页应用导致更少的 I/O 和更少的总的分配内存。

另一方面，采用1B大小的页，每字节会产生页错误。大小为200KB的进程，只使用其中一半，如果采用1B大小的页，那么会产生102400个页错误。每个页错误会产生大量的额外开销以处理中断、保存寄存器、置换页、排队等待调页设备和更新表。为了降低页错误的数量，需要较大的页。

然而，总的来说，趋向更大的页。

9.9.3 TLB范围 TLB reach

TLB命中率(hit ratio)是指通过 TLB 而不是页表所进行的虚拟地址转换的百分比。显然，命中率与TLB的条数有关，增加TLB的条数可增加命中率。然而，这种方法的代价并不小，因为用于构造 TLB 的相关内存既昂贵又费电。

与命中率相关的另一类似测量尺度是TLB范围(TLBreach)。TLB范围指通过 TLB可访问的内存量，并且等于 TLB 条数与页大小之积。理想情况下，一个进程所有的工作集合应位于 TLB 中。否则，该进程因通过页表而不是 TLB 而浪费大量时间以进行地址转换。

如果把 TLB 条数加倍，那么可加倍 TLB 范围。然而，对于某些使用大量内存的应用程序,这样做可能不足以存储工作集合。

增加 TLB 范围的另一个方法是增加页的大小或提供多种页大小。如果增加页大小，如从 8~32 KB，那么 TLB 将翻两番。然而，对于不需要像 32 KB.这样页大小的应用程序,就会产生碎片。另一种选择是，操作系统可使用不同大小的页。

9.9.5 程序结构

在有些情况下，用户对按需调页有所了解，可以改善系统性能。（例：对两位数组的循环遍历）

9.9.6 I/O互锁

…略

四、存储管理

I/O子系统的重要目的之一是为系统其他部分提供最简单的接口。

第十章文件系统接口

10.1 文件概念

文件是记录在外存上的相关信息的具有名称的集合。

10.1.1 文件属性

名字、标识符、类型、位置、大小、权限、时间戳等描述文件的元数据。

所有文件的信息都保存在目录结构中，而且目录结构也保存在外存上。

10.1.2 文件操作

文件属于抽象类型。

创建文件、写文件、读文件、在文件内重定位、删除文件、截短文件、添加新信息、重命名现有文件

以上所述的绝大多数文件操作都涉及为给定文件搜索相关目录条目。为了避免这种不断的搜索操作，许多系统要求在首次使用文件时，需要使用系统调用open()。操作系统维护一个包含所有打开文件的信息表(打开文件表, open-file table)。

当需要一个文件操作时，可通过该表的一个索引指定文件，而不需要搜索。当文件不再使用时，进程可关闭它，操作系统从打开文件表中删除这一条目。系统调用create 和 delete 操作的是关闭文件而不是打开的文件。

操作open()会根据文件名搜索目录，并将目录条目复制到打开文件表。调用open()也可接受访问模式参数：创建、只读、读写、添加等。该模式可以根据文件许可位进行检查。如果请求模式获得允许，进程就可打开文件。系统调用open()通常返回一个指向打开文件表中一个条目的指针。通过使用该指针，而不是真实文件名称，进行所有I/O操作，以避免进一步搜索和简化系统调用接口。

单个进程的表：单个进程表跟踪单个进程打开的所有文件。表内所存是该进程所使用的文件的信息。例如，每个文件的当前文件指针就保存在这里，另外还包括文件访问权限和记账信息。

整个系统的表：单个进程表的每一条目相应地指向整个系统的打开文件表。整个系统表包含进程无关信息，如文件在磁盘上的位置、访问日期和文件大小。一旦一个进程打开一个文件，系统打开文件表就会在表中为打开文件增加相应的条目。当另一个进程执行调用open()，其结果只不过简单地在其进程打开表中增加一个条目，并指向整个系统表的相应条目。通常系统打开文件表的每个文件还有一个文件打开计数器open count，以记录多少进程打开了该文件。每个 close()会递减count，当打开计数器为0时，表示该文件不再被使用，该文件条目可从系统打开文件表中删除。

每个打开文件有如下信息：文件指针（跟踪上次读写位置以作为当前文件位置指针）、文件打开计数器、文件磁盘位置、访问权限（每个进程用一个访问模式打开文件）

10.1.3 文件类型

当设计文件系统(事实上包括整个操作系统)时，总是要考虑操作系统是否应该识别和支持文件类型。如果操作系统识别文件类型，那么它就能按合理方式对文件进行操作。例如，一个常见错误是用户试图打印一个二进制目标形式的程序。这种尝试通常会产生垃圾，但是如果操作系统已知文件是二进制目标程序，那么就能阻止它被打印。

实现文件类型的常用技术是在文件名称内包含类型。这样，用户和操作系统仅仅通过文件名称就能确定文件类型是什么。名称可分为两部分：名称和扩展名

10.1.4 文件结构

有些文件必须符合操作系统所要求的结构

可支持多个文件结构的操作系统不可避免地出现了一个缺点：操作系统会变大。如果操作系统定义了5个不同文件结构，那么它需要包含代码以支持这些文件结构。另外，每个文件可能都需要被定义成操作系统所支持的某一种类型。如果新应用程序要求按操作系统所不支持的结构来组织信息，那么就会出问题。

10.1.5 内部文件结构

从内部而言，定位文件偏移量对操作系统来说可能是比较复杂的。磁盘系统通常具有明确定义的块大小，这是由扇区大小决定的。所有磁盘I/O是按块(物理记录)来执行的，且所有块都是同样大小。物理记录大小不太可能刚好与所需逻辑记录大小一样长，而且逻辑记录的长度是可变的。对这个问题的常用解决方法是先将若干个逻辑记录打包，再放入物理记录。

例如，UNIX操作系统定义所有文件为字节流。每个字节可以从它到文件首(或尾)的偏移量来访问。在这种情况下，逻辑记录大小为1B。文件系统通常会自动将字节打包以存入物理磁盘块，或从磁盘块中解包得到字节(如按需要可能为每块 512B)。

逻辑记录大小、物理块大小和打包技术决定了多少逻辑记录可保存在每个物理块中。打包可由用户应用程序或操作系统来执行。

不管如何，文件都可当做一系列块的组合，所有基本 I/O操作都是按块来进行的。逻辑记录与物理块之间的转换相对来说是个简单的软件问题。

由于磁盘空间总是按块来分配的，所以文件的最后一块的部分空间通常会被浪费。如果每块为512B,一个大小为1949B的文件会分配到4块(2048B)；最后99B就浪费了。按块分配所浪费的字节称为内部碎片，块越大，内部碎片也越大。

10.2 访问方法

10.2.1 顺序访问 Sequential Access

文件信息按顺序，一个记录接着一个记录地加以处理。大量的文件操作是读和写。读操作读取下一文件部分，并自动前移文件指针，以跟踪I/O 位置。类似地，写操作会向文件尾部增加内容，相应的文件指针移到新增数据之后(新文件结尾)。文件也可重新设置到开始位置，有的系统允许向前或向后跳过n个(这里n为整数，有时只能为1)记录。

10.2.2 直接访问 Direct Access

文件由固定长度的逻辑记录组成，以允许程序按任意顺序进行快速读和写。直接访问方式是基于文件的磁盘模型，这是因为磁盘允许对任意文件块进行随机读和写。对直接访问，文件可作为块或记录的编号序列。因此，可先读取块 14，再读块 53，最后再写块7。对于直接访问文件，读写顺序是没有限制的。

10.2.3 索引访问 Index Access

建立在直接访问方式之上，创建文件索引，索引包括各块的指针。为了查找文件中的记录，首先搜索索引，再根据指针直接访问文件，以查找所需要的记录。

索引保存在内存中。

允许只通过少量I/O就能搜索大文件。

10.3 目录结构

10.3.1 存储结构

一块硬盘可以多个分区(Partition)，每个分区有独立的文件系统（各分区的文件系统可以不同）。

多块硬盘可以合并成一个卷(Volume)，每个卷有独立的文件系统。

每个文件系统有一个directory，记录文件的基础信息（名称、位置、大小、类型等）

10.3.2 目录概述

目录相关操作：搜索文件、创建文件、删除文件、遍历目录、重命名文件、跟踪文件系统

10.3.3 单层结构目录

所有用户共用一个目录

无法重名

10.3.4 双层结构目录

单层结构目录通常会在不同用户之间引起文件名称的混淆。标准解决方法是为每个用户创建独立目录。

对于双层结构目录的结构，每个用户都有自己的用户文件目录(user file directory，UFD)。每个 UFD 都有相似的结构，但只列出了单个用户的文件。当一个用户作业开始执行或一个用户注册时，就搜索系统的主文件目录(master file directory，MFD)。通过用户名或账号可索引MFD，每个条目指向用户的UFD。

解决了名称冲突问题，有效的对用户进行隔离。但是在用户需要在某个任务上进行合作和访问其他文件时却是个缺点。

10.3.5 树状结构目录

路径名有两种形式：绝对路径名或相对路径名。 绝对路径名从根开始并给出路径上的目录名直到所指定的文件。 相对路径名从当前目录开始定义路径。

10.3.6 无环图目录

两个用户以不同的名字去访问同一个文件（物理位置相同）

共享文件(或目录)不同于文件复制。如果有两个副本，每个程序员看到的是副本而不是原件；如果一个程序员改变了文件，那么这一改变不会出现在另一程序员的副本中。

对于共享文件，只存在一个真正文件，所以任何改变都会为其他用户所见。

实现共享文件和目录的方法：

创建一个称为链接的新目录条目。链接实际上是另一文件或目录的指针。

简单地在共享目录中重复所有(被)共享文件的信息，因此两个目录条目完全相同。

删除

增加一个新链接或目录条目就增加引用计数，删除链接或条目就降低计数。当计数为0时，没有它的其他引用就能删除该文件。

10.5 文件共享

10.6 保护

为了防止文件共享可能会导致文件被破坏或未经核谁的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令和加密是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。

对文件的访问类型区分，可以分为：

执行

添加

删除

列表清单

解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是，为每个文件和目录增加一个访问控制列表 (Access-Control List， ACL)，以规定每个用户名及其所允许的访问类型。这种方法的优点是可以使用复杂的访问方法，缺点是长度无法预计并且可能导致复杂的空问管理，使用精简的访问列表可以解决这个问题。

精简的访问列表包括拥有者、组和其他三种用户类型：

拥有者：创建文件的用户为拥有者

组：一组需要共享文件且具有类似访问的用户形成了组或工作组

其他：系统内的其他用户

这样，只需用三个域即可列出访问表中这三类用户的访问权限。文件拥有者在创建文件时，说明创建者用户名及所在的组名，系统在创建文件时也将文件主的名字、所属组名列在该文件的 FCB 中。用户访问该文件时，按照拥有者所拥有的权限访问文件，若用户和拥有者在同一个用户组，则按照同组权限访问，否则只能按其他用户权限访问。UNIX 操作系统即采用此种方法。

第十一章文件系统实现

11.1 文件系统结构

磁盘提供大量的外存空间来维持文件系统。

磁盘的下述两个特点，使其成为存储多个文件的方便介质:

①可以原地重写，可以从磁盘上读一块，修改该块，并将它写回到原来的位置。

②可以直接访问磁盘上的任意一块信息。因此，可以方便地按顺序或随机地访问文件，从一个文件切换到另一个文件只需要简单地移动读写磁头并等待磁盘转动即可以完成。

为了改善 I/O 效率，内存与磁盘之间的 I/O转移是以块为单位而不是以字节为单位来进行的。

I/O 控制为最底层，由设备驱动程序和中断处理程序组成，实现内存与磁盘之间的信息传输。

设备驱动程序可以作为翻译器。其输入由高层命令组成，如“retrieve block 123”。

其输出由底层的、硬件特定的命令组成，这些命令用于控制硬件控制器，通过硬件控制器可以使I/O设备与系统其他部分相连。设备驱动程序通常在I/O控制器的特定位置写入特定位格式来通知控制器在什么位置采取什么动作。

设备驱动程序作用：设备驱动程序是I/O系统的高层与设备控制器之间的通信程序，其主要任务是接收上层软件发来的抽象I/O要求，再把它转换为具体要求后，发送给设备控制器，启动设备去执⾏；反之，它也将由设备控制器发来的信号传送给上层软件。

基本文件系统只需要向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进行读写。

文件组织模块(file-organization module)知道文件及其逻辑块和物理块。由于知道所使用的文件分配类型和文件的位置，文件组织模块可以将逻辑块地址转换成基本文件系统所用的物理块地址。

文件组织模块也包括空闲空间管理器，用来跟踪未分配的块并根据要求提供给文件组织模块。

逻辑文件系统管理元数据。元数据包括文件系统的所有结构数据，而不包括实际数据(或文件内容)。

逻辑文件系统根据给定符号文件名来管理目录结构，并提供给文件组织模块所需要的信息。逻辑文件系统通过文件控制块FCB来维护文件结构。

逻辑文件系统也负责保护和安全。

文件控制块(file control block, FCB)包含文件的信息，如拥有者、权限、文件内容的位置。逻辑文件系统也负责保护和安全。

11.2 文件系统实现

实现文件系统要使用多个磁盘和内存结构。

在磁盘上，文件系统可能包括如下信息:如何启动所存储的操作系统、总的块数、空闲块的数目和位置、目录结构以及各个具体文件等。

(每个卷的)引导控制块(boot control block)包括系统从该卷引导操作系统所需要的信息。如果磁盘没有操作系统，那么这块的内容为空。它通常为卷的第一块。

(每个卷的)卷控制块(volume control block)包括卷(或分区)的详细信息，如分区的块数、块的大小、空闲块的数量和指针、空闲FCB 的数量和指针等。

每个文件系统的目录结构用来组织文件

每个文件的 FCB 包括很多该文件的详细信息，如文件权限、拥有者、大小和数据块的位置。

内存内信息用于文件系统管理并通过缓存来提高性能。这些数据在文件系统安装的时候被加载，卸载的时候被丢弃。这些结构可能包括：

一个内存中的安装表，包括所有安装卷的信息。

一个内存中的目录结构缓存，用来保存近来访问过的目录信息(对于卷所加载的目录，可以包括一个指向卷表的指针)。

系统范围内的打开文件表包括每个打开文件的 FCB 副本和其他信息。

单个进程的打开文件表包括一个指向系统范围内已打开文件表中合适条目的指针和其他信息。

打开文件

调用open()将文件名传给文件系统。

系统调用open()会首先搜索系统范围内的打开文件表以确定某文件是否已被其他进程所使用。

如果是，就在单个进程的打开文件表中创建一项，并指向现有系统范围内的打开文件表。该算法能节省大量开销。

当打开文件时，根据给定文件名来搜索目录结构。部分目录结构通常缓存在内存中以加快目录操作。一旦找到文件，其FCB就复制到系统范围内的打开文件表。该表不但存储 FCB，而且还跟踪打开该文件的进程数量。

接着，在单个进程的打开文件表中会增加一个条目，并通过指针将系统范围内的打开文件表的条目和其他域相连。这些其他域可以包括文件当前位置的指针(用于下一次的读写操作)和文件打开模式等。调用open()返回一个指向单个进程的打开文件表中合适条目的指针。所有之后的文件操作都是通过该指针进行的。

对于访问打开文件表的索引有多种名称，UNIX称之为文件描述符(file descriptor)，Windows称为文件句柄(file handle)。只要文件没有被关闭，所有文件操作都是要通过打开文件表来进行的。

当一个进程关闭文件，就删除一个相应的单个进程打开文件表的条目，系统范围内打开文件表相应文件条目的打开数也会递减。当打开文件的所有用户都关闭一个文件时，更新的文件元数据会复制到磁盘的目录结构中，系统范围内的打开文件表的相应条目也将删除。

文件系统结构的缓存也不应被忽视。大多数系统在内存中保留了打开文件的所有信息(除了实际的数据块)。

11.3 目录实现

目录分配和目录管理算法的选择对文件系统的效率、性能和可靠性有很大影响。

11.3.1 线性列表

最为简单的目录实现方法是使用存储文件名和数据块指针的线性列表。这种方法编程简单但运行时较为费时。要创建新文件，必须首先搜索目录以确定没有同样名称的文件存在。接着，在目录后增加一个新条目。要删除文件时，根据给定文件名搜索目录，接着释放分配给它的空间。

目录条目的线性列表的真正缺点是查找文件需要线性搜索。

事实上，许多操作系统采用软件缓存来存储最近问过的目录信息。

11.3.2 哈希表

采用这种方法时，除了使用线性列表存储目录条目外，还使用了哈希数据结构。哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。因此，它大大地减少目录搜索时间。插入和删除也较简单，不过需要一些预备措施来避免冲突(collision)(两个文件名哈希到相同的位置)。

哈希表的最大困难是其通常固定的大小和哈希函数对大小的依赖性。例如，假设使用线性哈希表来存储64个条目。哈希函数可以将文件名转换为0~63的整数,例如采用除以64 的余数。如果后来设法创建第65个文件，那么必须扩大目录哈希表，比如到128个条目。因此，需要一个新的哈希函数来将文件名映射到0~127的范围，而且必须重新组织现有目录条目以反映它们新的哈希函数值。

11.4 分配方法

11.4.1 连续分配

要求每个文件在磁盘上占有一组连续的块。

文件目录中存放起始盘块号和块数。

优点:访问容易，速度快

缺点:

分配算法复杂(最先适应、最优适应)

外碎片问题

必须事先知道文件的长度,Files cannot grow

11.4.2 链接分配

基本思想：每个文件由磁盘块链表组成，每一个盘块含有指向下盘块的指针。

Each file is a linked list of disk blocks, blocks may be scattered anywhere on the disk.

文件目录中存放指向第一个盘块和最后一个盘块的指针。

优点：实现了离散分配；无外碎片；文件大小可变。

缺点：只能顺序访问；指针占空间；链断致命（中间数据块指针丢失会导致链断裂，文件内容丢失）

改进措施1：按簇分配(Cluster)--多个block组成1个簇，缩了链表长度，但内碎片增加

改进措施2：链接信息专门存放，形成FAT文件分配表

FAT：每个卷的开始部分用于存储该FAT。每块都在该表中有一项，该表可以通过块号码来索引。目录条目含有文件首块的块号码。根据块号码索引的FAT条目包含文件下一块的块号码。

可能会导致大量的磁头寻道时间，但改善了随机访问时间

11.4.3 索引分配

每个文件都有其索引块，这是一个磁盘块地址的数组。

基本思想：为每个文件分配一个索引块，把分配给该文件的所有盘块号，都记录在该索引块中。

优点：支持直接访问，无外碎片。

缺点：浪费空间，索引块的大小问题

管理大文件的改进措施

链接(linked scheme)

一个索引块通常为一个磁盘块。因此，它本身能直接读写。为了处理大文件，可以将多个索引块链接起来。（有链表的缺点在，不太好）

多级索引(Multileve lindex)

链接表示的一种变种是用第一层索引块指向一组第二层的索引块，第一层索引块再指向文件块。为了访问一块，操作系统通过第一层索引查找第二层索引，再用第二层索引查找所需的数据块。这种方法根据最大文件大小的要求，可以继续到第三或第四层。

组合策略(Combined scheme)UNIX采用

直接块间接块（一级间接块、二级间接块、三级间接块…...）

11.5 空闲空间管理

11.5.1 位向量

通常，空闲空间表实现为位图(bitmap)或位向量(bitvector)。每块用一位表示。如果一块为空闲，那么其位为1；如果一块已分配，那么其位为0。

例如，假设有一个磁盘，其块2、3、4、5、8、9、10、11、12、13、17、18、25、26、27 为空闲，其他块为已分配。那么，空闲空间位图如下：001111001111110001100000011100000…

这种方法的主要优点是查找磁盘上第一个空闲块和n个连续空闲块时相对简单和高效。

11.5.2 链表

空闲空间管理的另一种方法是将所有空闲磁盘块用链表连接起来，并将指向第一空闲块的指针保存在磁盘的特殊位置，同时也缓存在内存中。第一块包含一个下一空闲磁盘块的指针，如此继续下去。

不过，这种方案的效率不高；要遍历整个表时，要大量的 I/O时间。好在遍历整个表并不是一个经常操作。

11.5.3 组

对空闲链表的一个改进是将n个空闲块的地址存在第一个空闲块中。这些块中的前n-1个确实为空，而最后一块包含另外n个空闲块的地址，如此继续。大量空闲块的地址可以很快地找到，这一点有别于标准链表方法。

11.5.4 计数

另外一种方法是利用这样一个事实：通常，有多个连续块需要同时分配或释放，尤其是在使用连续分配和采用簇时更是如此。因此，不是记录个空闲块的地址，而是可以记录第一块的地址和紧跟第一块的连续的空闲块的数量n。这样，空闲空间表的每个条目包括磁盘地址和数量。虽然每个条目会比原来需要更多空间，但是表的总长度会更短，这是因为连续块的数量常常大于1。

11.6 效率与性能

由于磁盘是计算机主要部件中最慢的部分，所以磁盘通常成为系统性能的瓶颈。

11.6.1 效率

磁盘空间的有效使用主要取决于所使用的磁盘分配和目录管理算法。

例如，UNIX索引节点(inode)预先分配在卷上。

这些算法试图将文件数据与其索引节点信息存放在一起，从而降低了寻道时间。

保留在文件目录条目(或索引节点)内的数据类型也需要加以考虑。通常，要记录“最近写日期”以提供给用户，如用于确定是否需要备份给定文件。有的系统也记录“最近访问日期”，以便用户能确定最后一次读文件在什么时候。

这意味着将相应块读入内存，修改相应部分，再将该块写回至磁盘，这是因为磁盘操作是以块(或簇)为单位来进行的。

通常，与文件相关的所有数据项都必须加以研究，以考虑其对效率和性能的影响。

11.6.1 性能

绝大多数磁盘控制器都有本地内存以作为板载高速缓存，它足够大,能同时存储整个磁道。

有的系统有一块独立内存用做缓冲缓存，位于其中的块假设马上需要使用。

其他系统采用页面缓存(page cache)来缓存文件数据。页面缓存使用虚拟内存技术，将文件数据作为页而不是面向文件系统的块来缓存。采用虚拟地址来缓存文件数据，与采用物理磁盘块来缓存相比，更为高效。

影响I/O性能还有其他因素，比如是同步还是异步向文件系统写入。

同步写按磁盘子系统接收顺序来进行，写并不缓存。因此，调用子程序必须等待数据写到磁盘驱动器后再继续。绝大多数时间进行的是异步写。对于异步写，将数据存在缓存后就将控制返回给调用者。

有的系统根据文件访问类型采用不同替换算法，以优化页面缓存。

按顺序所进行的文件的读入或写出就不应采用LRU 页替换，因为最近使用的页有可能最后才使用或根本不用。因此，顺序访问可以通过采用马上释放和预先读取来加以优化。

马上释放(free-behind)是在一旦请求下一页时，马上从缓存中删除上一页。以前的页不可能再次使用，且浪费缓冲空间。

采用预先读取(read-ahead)所请求的页和之后的一些页可一起读入并缓存。这些可能在本页处理之后就要被请求

11.7 恢复

11.7.1 一致性检查

由于文件和目录可保存在内存和磁盘上，所以必须注意确保系统失败不会引起数据丢失和数据的不一致性。

一致性检查程序(consistency checker)，例如 UNIX下的 fsck 和 MS-DOS 下的 chkdsk系统程序，将目录结构数据与磁盘数据块相比较，并试图纠正所发现的不一致。

分配算法和空闲空间管理算法决定了检查程序能发现什么类型的问题，及其如何成功地纠正问题。例如，如果使用链接分配，那么每一块都指向下一块，这样整个文件可以从数据块来重建，并可重建目录结构。相反，对于采用索引分配系统，目录条目的损坏可能就严重了，因为数据块之间并没有什么联系。

11.7.2 备份和恢复

磁盘有时会出错，所以必须注意确保数据在出错时不会永远丢失。为此，可以利用系统程序将磁盘数据备份到另一存储设备，如软盘、磁带、光盘或另一个硬盘上。

恢复单个文件或整个磁盘时，只需要从备份中进行恢复就可以了。

为了降低复制量，可以利用每个文件的目录条目信息。例如，如果备份程序知道一个文件上次何时备份，且目录内该文件上次写日期表明该文件自上次备份以来并未改变，那么该文件不必再复制。

第十二章大容量存储器的结构

12.1 大容量存储器结构简介

magnetic disk 磁盘 disk arm 磁臂 read-write head 读写磁头 track 磁道 cylinder 柱面 platter 磁盘面 sector 扇区 spindle 转轴 arm assembly 机械臂杆

磁盘(magnetic disk)为现代计算机系统提供了大容量的外存。

每个磁盘片为扁平圆盘，两面都涂着磁质材料。通过在磁片上进行磁记录可以保存信息。

当磁盘在使用时，驱动器马达会高速旋转磁盘。

磁盘速度有两部分。

传输速率(transfer rate)是在驱动器和计算机之间的数据传输速率。
定位时间(positioning time)，有时称为随机访问时间(random access time)，由寻道时间(seek time)（移动磁臂到所要的柱面所需时间）和旋转等待时间(rotationallatency)（等待所要的扇区旋转到磁臂下所需时间）组成。

12.2 磁盘结构

现代磁盘驱动器可以看做一个一维的逻辑块的数组，逻辑块是最小的传输单位。

一维逻辑块数组按顺序映射到磁盘的扇区。

扇区0是最外面柱面的第一个磁道的第一个扇区。该映射是先按磁道内扇区顺序，再按柱面内磁道顺序，最后按从外到内的柱面顺序来排序的。

例：cylinder柱面：1024，head磁头：16（磁道），sector分区：256

c	h	s	sector number
0	0	0	0
0	0	1	1
…	…	…	…
0	0	255	255
0	1	0	256
…	…	…	…
1023	15	255	102416256

12.3 磁盘附属

计算机访问磁盘存储有两种方式。

一种方式是通过 IO端口(或主机附属存储(host-attached storage))，小系统常采用这种方式。

另一方式是通过分布式文件系统的远程主机，这称为网络附属存储(network-attached storage)

12.3.1 主机附属存储

主机附属存储是通过本地IO端口访问的存储。

典型的台式计算机使用 IO 总线结构，如IDE或 ATA。这种结构允许每条 I/O 总线支持最多两个端口，

而 SATA 是一种新的简化了电缆连接的类似协议。

高端工作站和服务器通常采用更为复杂的I/O结构，如SCSI或FC(fiber channel)。

SCSI协议在一根总线上可支持16个设备。

12.3.2 网络附属存储

网络附属存储(network-attached storage,NAS)设备是数据网络中远程访问的专用存储系统。

12.3.3 存储区域网络

存储区域网络(storage area network，SAN)是服务器与存储单元之间的私有网络(采用存储协议而不是网络协议)

12.4 磁盘调度

操作系统的任务之一就是有效地使用硬件。对磁盘驱动器来说，满足这一要求意味着要有较快的访问速度和较宽的磁盘带宽。

访问时间包括两个主要部分：寻道时间和旋转延迟

寻道时间是磁臂将磁头移动到包含目标扇区的柱面的时间。

旋转延迟是磁盘需要将目标扇区转动到磁头下的时间。

磁盘带宽是所传递的总的字节数除以从服务请求开始到最后传递结束时的总时间。可以通过使用适当的访问顺序来调度磁盘I/O请求，提高访问速度和带宽。

以 Head pointer 53

磁盘队列：98, 183, 37, 122, 14, 124, 65, 67 为例

12.4.1 FCFS调度

总的磁头移动为：640

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

这种算法本身比较公平，但是它通常不提供最快的服务。

12.4.2 SSTF调度

总的磁盘移动为：236

最短寻道时间优先算法

选择距离当前磁头位置最短的待处理请求

提高了性能但不是最优。基本与 SJF最短作业优先调度一样，因为新请求随时会抵达，所以可能导致磁头一直在一个小范围摆动，产生饥饿。

12.4.3 SCAN调度

总的磁盘移动为：236

又称电梯调度算法。磁臂从磁盘的一端向另一端移动，磁头经过每个柱面时处理位于该柱面上的请求。到达另一端时改变移动方向继续处理

避免了饥饿现象，但当磁头到达一端折返往回移动时，在该端等待服务的请求可能很少，等待的时间也比较短，因为该区域的请求刚刚被访问过；而另一端等待服务的请求可能很多，等待的时间也可能很长

12.4.4 C-SCAN调度

总的磁盘移动为：382

SCAN 调度变种，要求磁头单项移动，即磁头从磁盘一边移动到另一端并处理请求，当磁头移动到另一端时会马上返回磁盘开始，返回时不处理请求

提供更为均匀的等待时间，与 SCAN相比比较公平，但需要移动更多个柱面

12.4.5 LOOK调度

SCAN和C-SCAN是使磁头在整个磁盘宽度内进行移动，但这并不容易实现。通常，磁头只会移动到一个方向上最远的请求为止（分别成为LOOK和C-LOOK调度）

与 SCAN 和C-SCAN相比提高了效率。

12.4.6 磁盘调度算法的选择

SSTF 较为普通且很有吸引力。

SCAN 和C-SCAN对于磁盘负荷较大的系统会执行得更好，这是因为它不可能产生饿死问题。对于一个特定请求队列,可以定义一个最佳的执行顺序，但是查找最佳调度的所需时间有可能大于SSTF或SCAN节省的时间。对于任何调度算法，其性能主要依赖于请求的数量和类型。

磁盘服务请求很大程度上受文件分配方法所影响。

磁盘调度算法应作为一个操作系统的独立模块,这样如果有必要,它可以替换成另一个不同的算法。

SSTF 或LOOK是比较合理的默认算法。

这里所描述的调度算法只考虑了寻道距离。对于现代磁盘，旋转等待几乎与平均寻道时间一样。但是操作系统比较难调度以改善旋转等待，这是因为现代磁盘并不透露逻辑块的物理位置。磁盘制造商通过在磁盘驱动器的控制器硬件中加上磁盘调度算法来缓解这个问题。如果操作系统向控制器发送一批请求，那么控制器可以对这些请求进行排队和调度，以改善寻道时间和旋转等待。

12.5 磁盘管理

12.5.1 磁盘格式化

在磁盘能存数据之前，它必须分成扇区以便磁盘控制器能读和写。这个过程称为低级格式化(或物理格式化)。

为了使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上。这分为两步。

第一步是将磁盘分为由一个或多个柱面组成的分区。操作系统可以将每个分区作为一个独立的磁盘。

在分区之后，第二步是逻辑格式化(创建文件系统)。在这一步，操作系统将初始的文件系统数据结构存储到磁盘上。这些数据结构包括空闲和已分配的空间（FAT或者inode）

为了提高效率，大多数操作系统将块集中到一大块，通常称作簇(cluster)。磁盘I/O通过块完成，但是文件系统I/O通过簇完成。这样有效确保了I/O可以进行更多的顺序存取和更少的随机存取。

有的操作系统允许特别程序将磁盘分区作为一个逻辑块的大顺序数组，而没有任何文件系统数据结构。该数组有时称为生磁盘(raw disk),对该数组的I/O称为生 I/O(raw IO)。

例如，有的数据库系统比较喜欢生I/O，因为它能控制每条数据库记录所存储的精确磁盘位置。

生 I/O 避开了所有文件系统服务，如缓冲、文件锁、提前获取、空间分配、文件名和目录。

12.5.2 引导块 Boot Block

为了让计算机开始运行，如打开电源时或重启时，它需要运行一个初始化程序。该初始化自举(bootstrap)程序初始化系统的各个方面，从CPU寄存器到设备控制器和内存，接着启动操作系统。为此，自举程序应找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的执行。

这个完整的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位置。拥有启动分区的磁盘称为启动磁盘(boot disk)，或系统磁盘。

12.5.3 坏块 Bad Blocks

由于磁盘有移动部件并且容错能力小(磁头在磁盘表面上飞行)，所以容易出问题。

常见的是一个或多个扇区坏掉。绝大多数磁盘从工厂里出来时就有坏块。根据所使用的磁盘和控制器，对这些块有多种处理方式。

对于简单磁盘，如使用IDE控制器的磁盘，可手工处理坏扇区。

例如，MS-DOS format命令执行逻辑格式化，它将扫描磁盘以查找坏扇区。如果format找到坏扇区，那么它就在相应的 FAT条目中写上特殊值以通知分配程序不要使用该块。如果在正常使用中块变坏，那么就必须人工地运行一个特殊程序，如chkdsk来搜索坏块，并像前面一样将它们锁在一边作为备用，操作系统看不到这些块。坏块中的数据通常会丢失。

更为复杂的磁盘对坏块的处理就更加智能化了（如SCSI硬盘）。

其控制器维护一个磁盘坏块链表。该链表在出厂前进行低级格式化时就已经初始化了，并在磁盘整个使用过程中不断更新。低级格式化将一些块放在一边作为备用，操作系统看不到这些块。控制器可以用备用块来逻辑地替代坏块。这种方案称为扇区备用(sector sparing)或转寄(forwarding)。

一个典型的坏扇区事务处理可能如下:

操作系统试图访问逻辑块 87。

控制器计算 ECC的值，发现该块是坏的，它将此结果通知操作系统。

下次操作系统重启时，可以运行一个特殊程序以告诉SCSI控制器用备用块替代坏块。

之后，每当系统试图访问逻辑块87时，这一请求就转换成控制器所替代的扇区的地址。

这种控制器所引起的重定向可能会使操作系统的磁盘调度算法无效。

为此，绝大多数磁盘在格式化时为每个柱面都留了少量的备用块，还保留了一个备用柱面。当坏块需要重新映射时，控制器就尽可能使用同一柱面的备用扇区。

作为扇区备用的另一方案，有的控制器采用扇区滑动(sector slipping)来替换坏扇区。

这里有一个例子：假定逻辑块 17变坏，而第一个可用的备用块在扇区 202之后。那么，扇区滑动就将所有从 17~202 的扇区向下滑动一个扇区，即扇区 202 复制到备用扇区，201到 202，200到201等，直到扇区18复制到扇区19。这样滑动扇区使得扇区18为空，这样可将扇区 17 映射到其中。

12.7 RAID结构

过去，RAID 是由许多小的、便宜磁盘组成，可作为大的、昂贵磁盘的有效替代品。

现在，RAID 的使用主要是因为其高可靠性和高数据传输率,而不是经济原因。因此，RAID中的I表示“独立(independent)”而不是“便宜(inexpensive)”

RAID级别
RAID0 通过并行处理改善性能
RAID1、RAID5通过冗余改善可靠性 — RAID级别 **RAID0 通过并行处理改善性能 RAID1、RAID5通过冗余改善可靠性**

第十三章 I/O输入系统

13.1 概述

因为I/O设备在其功能与速度方面存在很大差异(设想一下鼠标、硬盘及 CD-ROM 自动唱片点唱机)，所以需要采用多种方法来控制设备。

这些方法形成了I/O子系统的核心，该子系统使内核其他部分不必涉及复杂的 I/O设备管理。

为了封装不同设备的细节与特点，操作系统内核设计成使用设备驱动程序模块的结构。设备驱动程序(device driver) 为I/O子系统提供了统一设备访问接口，就像系统调用为应用程序与操作系统之间提供了统一的标准接口一样。

13.3 I/O应用接口

13.3.1 块与字符设备

块设备接口规定了访问磁盘驱动器和其他基于块设备所需的各个方面。通常设备应能理解 read()和 write()命令,如果是随机访问设备,也应有 seek()命令以描述下次传输哪个块。应用程序通常通过文件系统接口访问设备。大家可以看到read()、write()、seek()描述了块存储设备的基本特点，这样应用程序就不必关注这些设备的低层差别。

操作系统本身和特殊应用程序(如数据库管理系统)可能更加倾向于将块设备当做个简单的线性块数组来访问。这种访问方式有时称为原始I/O。

内存映射文件访问是建立在块设备驱动程序之上的。内存映射接口并不提供read和write操作，而是通过内存中的字节数组来访问磁盘存储。

键盘是一种可以通过字符流接口访问的设备。这类接口的基本系统调用使得应用程序可以 get()或 put()一个字符。在此接口之上，可以构造库以提供具有缓冲和编辑功能的按行访问(例如，当用户输入了一个退格键，之前的字符可以从输入流中删除)。这种访问方式对有些输入很方便，如键盘、鼠标、modem，这些设备自发地提供输入数据，也就是说，应用程序无法预计这些输入。这种访问方式也有助于输出设备，如打印机、声卡，这些设备很适合于线性字节流的概念。

13.3.2 网络设备

由于网络 I/O的性能和访问特点与磁盘I/O相比有很大差别，绝大多数操作系统所提供的网络 I/O 接口也不同于磁盘的 read()-write()-seek()接口。许多操作系统所提供的接口是网络 Socket 接口

同样，Socket接口的系统调用可以让应用程序创建一个Socket，连接本地 Socket和远程地址(将本地应用程序与由远程应用程序创建的 Socket 相连)，监听要与本地 Socket 相连的远程应用程序，通过连接发送和接收数据。为支持服务器的实现，Socket接口还提供了select()函数，以管理一组Socket。调用select()可以得知哪个 Socket 已有接收数据需要处理,哪个 Socket 有空间可以接收数据以便发送。使用 select(就不必再使用轮询和忙等待来处理网络I/O。这些函数封装了基本的网络功能，大大地加快了使用网络硬件和网络协议的分布应用程序的创建。

13.3.3 时钟与定时器

13.3.4 阻塞与非阻塞I/O Blocking and Nonblocking

当应用程序发出一个阻塞系统调用时，应用程序的执行就被挂起。应用程序将会从操作系统的运行队列移到等待队列上去。在系统调用完成后，应用程序就移回到运行队列，并在适合的时候继续执行并能收到系统调用返回的值。大多数操作系统为应用程序接口使用阻塞系统调用，这是因为阻塞应用代码比非阻塞应用代码更容易理解。

一个非阻塞调用在程序执行过长时间时并不中止应用程序，它会很快返回，其返回值表示已经传输了多少字节。用户接口是使用非阻塞I/O的例子，它用来接收键盘和鼠标输入，同时还要处理并在屏幕上显示数据。

非阻塞与异步系统调用的差别是非阻塞read()调用会马上返回任何可用的数据，其所读的数据可以等于或少于所要求的，或为零。异步read()调用所要求的传输应完整地执行，但其具体执行可以是将来某个特定时间。

非阻塞和阻塞I/O是什么，主要有什么不同，分别用在哪里
非阻塞：进行IO操作时不用将应用挂起
举例：用户接口接受输入的同时屏幕显示
阻塞：当应用程序发出一个阻塞系统调用时，应用程序的执行被挂起，应用程序将会从操作系统的运行队列中移到等待队列里，系统调用完成后，应用程序重新回到运行队列

13.4 I/O内核子系统

13.4.1 I/O调度

为设备状态表 device status table配备等待列表

13.4.2 缓冲 Buffering

缓冲区是用来保存两个设备之间或在设备和应用程序之间所传输数据的内存区域。

采用缓冲的理由：

处理数据流的生产者与消费者之间的速度差异举例：可以在内存创建缓冲区积累从调制解调器接受的字节，当缓冲区满时再次将缓冲区写入磁盘

协调传输数据大小不一致的设备举例：在计算机网络中，缓冲可用于消息的分段和重组，在发送端将一个大消息分成若干个小网络包，通过数据传输，接收端将它们放在重组缓冲区内，以生成完整的源数据镜像

支持应用程序I/O的复制语义举例：某应用程序要将缓冲区内数据写到磁盘上，可以调用write(),当系统调用返回时，如果应用程序改变了缓冲区的内容，操作系统写入磁盘的数据仍是write()系统调用时发生的版本

13.4.3 高速缓冲 Cache

高速缓存(cache)是可以保留数据副本的高速存储器。高速缓冲区副本的访问要比原始数据访问要更为高效。

缓冲与高速缓存的差别是缓冲可能是数据项的唯一的副本，而根据定义，高速缓存只是提供了一个驻留在其他地方的数据在高速存储上的一个副本。

缓解CPU和内存之间速度的不匹配问题，能够提高系统性能。

高速缓存和缓冲是两个不同功能，但有时一块内存区域也可以同时用于这两个目的。例如，为了维护复制语义和有效调度磁盘I/O，操作系统在内存中开辟缓冲区来保留磁盘数据。这些缓冲区被用做高速缓存，以改善对某些文件的I/O操作效率，这些文件可被多个程序所共享或者被快速地写入和重读。当内核收到I/O请求时，内核首先检查高速缓存以确定相应文件的内容是否在内存中。如果是这样，物理磁盘I/O就可以避免或延迟。而且，几秒的磁盘写也可以累加在缓冲区中，这样大量的传输导致高速的写调度。

13.4.4 假脱机与设备预留

目的：解决独占设备的并发访问问题以提高设备利用率

假脱机(Spooling)是用来保存设备输出的缓冲区，这些设备(如打印机)不能接收交叉的数据流。虽然打印机只能一次打印一个任务，但是可能有多个程序希望并发打印而又不将其输出混在一起。

操作系统通过截取对打印机的输出来解决这一问题。

应用程序的输出先是假脱机到一个独立的磁盘文件上。当应用程序完成打印时，假脱机系统将对相应的待送打印机的假脱机文件进行排队。假脱机系统一次复制一个已排队的假脱机文件到打印机上。有的操作系统采用系统守护进程来管理假脱机，而有的操作系统采用内核线程来处理假脱机。不管怎样，操作系统都提供了一个控制接口以便用户和系统管理员来显示队列，删除那些尚未打印的而不再需要的任务，当打印机工作时暂停打印等。

假脱机是一种操作系统可以用来协调并发输出的方法。处理并发设备访问的另一个方法是提供协调所需要的工具。

Spooling技术是低速输入输出设备与主机交换的一种技术，通常也被称为假脱机真联机，它的核心思想是以联机的方式得到脱机的效果，可以将一台物理I/O设备虚拟为多台逻辑I/O设备，允许多个用户共享一台物理I/O设备 实现方法：在内存中形成缓冲区，在高级设备形成输入井和输出井，传递的时候，从低速设备传入缓冲区，再传到高速设备的输出井，再从高速设备的传出井，传到缓冲区，再传到低速设备

13.4.5 错误处理

操作系统可以对短暂的出错进行弥补。例如，磁盘read()出错可以导致 read()重试，网络 send()出错可以导致resend()(如果协议允许)。但是，如果某个重要系统组件出现了永久出错，那么操作系统就不可能从中恢复。

作为一个规则，I/O系统调用通常返回一个位来表示调用状态信息，以表示成功或失败。对UNIX操作系统，一个名为errmo的额外整数变量用来表示出错代码，约有100个，表示失败的一般原因(例如，参数超过范围，坏指针，文件未打开)。

相反，有的硬件能提供很详细的出错信息,虽然目前许多操作系统并不将这些信息传递给应用程序。许多 SCSI设备都维护一个出错日志信息以便主机查询，不过这一功能实际很少使用。

13.4.6 I/O保护

通过发出非法 I/O指令，用户程序可以有意或无意地中断系统的正常操作。可使用各种机制以确保这种中断不会发生。

定义所有 I/O指令为特权指令。

用户程序执行系统调用来请求操作系统代表用户程序执行IO操作。

所有的内存映射和 IO 端口内存位置都受到内存保护系统的保护，以阻止用户访问。

13.4.7 内核数据结构

内核需要保存IO组件使用的状态信息，可以通过若干内核数据结构如文件打开表等来完成，参见11.1节。内核使用许多类似的结构来跟踪网络连接、字符设备通信和其他 I/O活动等。

有的操作系统更为广泛地使用了面向对象方法。例如，WindowsNT的IO采用消息传递来实现。

13.5 把I/O操作转换成硬件操作

//课上只让看书上阻塞读请求的经典周期的10步（超长）

其他题目

计算机系统为保证操作系统及应用程序的可靠真确执行，采取了很多保护措施，阐述你所了解的相关技术。（提示：从硬件的执行模式、进程对临界区的并发访问、存储管理、文件管理、设备管理等内容涉及的保护技术进行阐述）

硬件执行：将操作系统拥有一些特权指令，当应用程式试图调用可能对操作系统造成破坏的程序时，系统就转入到内核态，通过系统调用完成某些操作，将结果返回给用户程序。避免用户接触到可能对计算机造成损害的指令

临界区的并发访问：为了避免两个或多个程序同时使用临界资源，操作系统设计临界区，使用软件措施、硬件措施、信号量等多种方式控制对临界资源的并发访问

存储管理：在分页情况下，内存保护通过与每个帧相关联的保护位来实现，这些位保存在页表中。可以用一个为定义一个页时可读写还是只读的，如果错误操作就会向操作系统产生硬件陷阱。还可以用有效位-无效位标记页是否合法，限制对非法页面的访问

文件管理：为文件设置口令或密码。或者以组的形式控制对文件的访问权限，避免对文件的非法访问

设备管理：IO系统调用通常返回一个位表示调用状态信息，以表示成功或失败

访存操作可能会导致IO进行，某进程读写文件时可能没有IO设备执行，为什么？

改文件首次调入时就已经调入内存，读写文件时直接在内存中进行不需要IO设备执行

读写文件首先是CPU读写内存，然后内存中的数据与设备进行I/O交互。所以读写文件时在CPU和内存交互时并没有IO设备参与。

CPU是进程运行必需资源，为什么进程不会因为等待CPU而发生死锁

死锁的四个必要条件：占有并请求，互斥，非抢占，循环等待

占有并请求：当一个进程等待CPU时，它并不持有任何资源，不满足请求并保持这一条件因此进程不会因为等待CPU而发生死锁

原语 Primitive

原语一般指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断

在什么情况下，使用多个内核线程的多线程解决方案会比单处理器系统上的单线程解决方案提供更好的性能？

比如当一个内核线程出现页面错误需要等待的时候，多线程方案下可以切换到另一个内核线程，不用一个出错所有都等待，可以以更有效的方式交错使用时间，提高CPU的使用率。然而在单线程的模式下，如果一个程序出现页面错误等需要等待的情况，那整个程序就要卡在这一直等待。所以当一个程序可能较多出现页面错误或其他必须等待的系统事件的情况下，在单处理机情况下多线程方案会比单线程方案性能更好。

一个使用多个用户级线程的多线程解决方案在多处理器系统上能否比在单处理器系统上获得更好的性能？

操作系统只能看到内核级线程，内核级线程才是处理机分配的单位。一个由多个用户级线程组成的多线程系统如果只对应一个内核级线程（多对一模型），则不能同时利用多处理器系统中的不同处理器，此时操作系统只看到一个单一的进程，不会将进程的不同线程安排在不同的处理器上。因此，这种情况下在多处理器系统上执行多个用户级线程没有任何性能优势。

解释为什么自旋锁不适合单处理器系统，却经常用于多处理器系统。

自旋锁并不适合于单处理器系统，因为要使一个进程脱离自旋锁的条件只能通过执行不同的进程来获得。如果进程不放弃处理器，其他进程就没有机会设置第一个进程取得进展所需的程序条件。

在一个多处理器系统中，其他进程在其他处理器上执行，从而修改程序状态，以便将第一个进程从自旋锁中释放。

考虑一个由4个相同类型的资源组成的系统，由3个进程共享，每个进程最多需要2个资源。证明该系统是无死锁的。

假设这个系统是可以发生死锁的，那么意味着每个进程都持有一个资源并等待获得另一个资源。因为只有三个进程和四个相同的资源，那么其中一个进程肯定能获得两个资源从而投入运行，运行后归还资源，从而系统不会死锁，与假设矛盾。故系统不会死锁。

一般情况下，操作系统尽量提高资源的利用率和程序的运行效率，但有时也违反这一原则，为什么？请举例说明。

说明基于请求页式虚拟存储管理的基本思想。

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

操作系统需要考虑哪些调度,这些调度目标和方法。

低级调度（进程调度）：按照某种策略从就绪队列中选择一个进程，将 CPU 分配给它。是最基本的一种调度，频率很高，一般几十毫秒一次。

方法：FCFS，短作业/短进程优先，HRRN，RR，优先级调度算法等。

中级调度：按照某种调度策略决定将哪个处于挂起状态（暂时调到外存等待的进程的状态为挂起状态）的进程重新调入内存。

高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。

线程调度：引入线程后，进程只是除了CPU 外资源分配的基本单位，线程是调度的基本单位。根据多线程模型进行调度：一对一，多对一，多对多。

磁盘调度：优化寻道时间，缩短一次磁盘读写所需要的时间。

方法：FCFS，最短寻找时间优先，SCAN，LOOK，C-SCAN，C-LOOK。

IO设备调度：用某种算法确定一个好的顺序来处理各个 I/O 请求。

方法：先来先服务算法、优先级算法、短作业优先等。

分段存储管理系统中，如何保证一个进程不能访问其它进程的地空间？

段的共享是通过两个进程共享一个段的数据副本实现的，当一个进程要限制对段的共享时，应该组织段再次创造副本，具体方法是给段添加一个标志位，当标志位为1时禁止制造副本（我不会我蒙的）

某计算机系统有多个 CPU，用户使用 pthread 提供的多线程机制创建了多个用户级线程。问这些用户级线程是否可以分配到多个处理器上并行执行？说明你的理由。（提示：根据用户进程与核心进程的映射模型讨论）

可以，可以使用一对一模型为每一个线程分配一个内核线程，这样多个线程就可以并行的运行在多个处理器上。也可以使用多对多模型，避免了一对一模型开销大的缺点。两种模型在一个线程发生阻塞时都不影响剩下的线程运行

请图示说明页式存储管理系统中对页面共享的方法，并说明共享代码和共享数据有何限制条件。

简述阻塞、饥饿、死锁的区别

阻塞：某一事件由于等待某一资源或者其他事件的发生而处于停滞状态

饥饿：某一事件由于等待某种资源而长期处于停滞状态，若该事件一直得不到资源，那么这个事件就会被饿死

死锁：存在一系列进程，分别占有某种资源，这些进程均在等待某一事件的产生，而该事件则只能由这一系列事件中的另一个进程产生，于是，就形成了死锁

FCFS在cpu调度、磁盘调度、页置换中分别的优缺点

CPU调度

优点：不会发生饥饿现象,实现简单、公平

缺点：不能让优先级较高的进程优先得到执行，对长作业有利，对短作业不利

磁盘调度

优点：实现简单、公平、集中访问的时候性能尚可

缺点：如果访问的磁道很分散，FCFS调度性能差，接近于随机调度

页置换

优点：调度算法简单，容易时间

缺点：不符合程序局部性原理，可能会导致频繁的页面调入调出影响CPU效率，有Bellday异常

逻辑地址和物理地址的绑定方式有几种，优缺点？

绝对装入：在编译时就确定物理地址，装入程序按照生成的物理地址将程序和数据装入内存

优点：实现简单，绝对地址可以在编译时给出也可以由程序员指定
缺点：只适用于单道程序环境

可重定位装入：根据内存的当前情况，将装入模块装入内存的适当位置，装入时对目标程序的指令和代码进行重定位。地址变换是在装入时一次完成的

特点：无需硬件支持，具有灵活性
缺点：必须在装入时一次性分配连续的地址空间，如果没有足够的空间就不能装入，装入后不可以再移动也不能再申请内存空间

动态运行时装入：装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这个地址转换推迟到真正要执行时才进行

优点：可以将程序分配到不连续的存储区中，根据需要动态申请分配内存，便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
缺点：需要硬件重定位寄存器的支持

进程、线程概念及特点

进程：是运行中的程序，是系统进行资源分配和调度的基本单位，是可以独立运行的基本单位，是操作系统结构的基础

特点：动态性、异步性、结构性、并发性、独立性

线程：是一个基本的CPU执行单元，进程中的一个运行实体，是进程的实际运作单位

线程特点

线程是CPU调度的基本单位，多核计算机的各个线程可以占用不同的CPU
每个线程都有一个线程ID和线程控制块TCB
线程也有就绪、阻塞、运行三种基本状态
线程几乎不拥有系统资源，同一进程中不同线程共享该进程的资源
因为线程共享内存地址空间，同一进程中线程通信几乎无需系统干预
同一进程中线程的切换不会引起进程的切换，不同线程的切换回引起进程的切换
切换同一进程内的线程开销很小，切换不同进程的系统开销很大

年份	链接
2024	2024年山东大学软件学院操作系统期末考回忆版-CSDN博客
2023	山东大学软件学院操作系统2022-2023期末考试回忆版_山东大学操作系统期末考试2023-CSDN博客
ㅤ	山东大学软件学院2022-2023学年操作系统期末试题_山东大学操作系统期末考试-CSDN博客
2022	https://blog.csdn.net/weixin_52720733/article/details/125555653
ㅤ	山东大学软件学院2022年春操作系统期末考试_请解释使用time sharing 和multiprogramming的意义,请比较layered -CSDN博客
2021	山东大学2021年软件学院操作系统期末考试回忆版_山东大学操作系统期末题2021-CSDN博客
ㅤ	2021年山东大学操作系统考卷回忆版_山东大学操作系统大水-CSDN博客
2020	山东大学软件学院操作系统（考试）——期末考试回忆版_山东大学操作系统期末2020-CSDN博客
ㅤ	ㅤ