操作系统

参考哔哩哔哩的课程：https://www.bilibili.com/video/BV1YB4y1i7xe/?spm_id_from=333.337.search-card.all.click&vd_source=731595967596af37618c926a191e7811

参考了博客：https://lfool.gitbook.io/operating-system/untitled-1/2.-cao-zuo-xi-tong-de-si-ge-te-zheng

参考了大纲：https://mubu.com/doc/d9TGd1--LY#m

参考了图解系统：https://xiaolincoding.com/os/1_hardware/how_cpu_run.html#%E5%9B%BE%E7%81%B5%E6%9C%BA%E7%9A%84%E5%B7%A5%E4%BD%9C%E6%96%B9%E5%BC%8F

参考了视频：https://www.bilibili.com/video/BV19r4y1b7Aw/?spm_id_from=333.337.search-card.all.click&vd_source=731595967596af37618c926a191e7811

参考了：https://www.cnblogs.com/cxuanBlog/p/13320810.html

第一章 操作系统概述

操作系统的基本概念

操作系统是资源管理程序，其作用是控制管理计算机系统的资源和程序的指向。操作系统是计算机中最基础的软件，其作用简单来讲：

  • 通过资源管理，提高计算机系统的效率

  • 改善界面，为用户提供友好的工作环境（方便性）

最开始的计算机是依靠图灵机而演变来的，通过图灵机可以较好的了解计算机发展的过程

图灵机

图灵机的基本组成如下：

  • 有一条「纸带」，纸带由一个个连续的格子组成，每个格子可以写入字符，纸带就好比内存，而纸带上的格子的字符就好比内存中的数据或程序；
  • 有一个「读写头」，读写头可以读取纸带上任意格子的字符，也可以把字符写入到纸带的格子；
  • 读写头上有一些部件，比如存储单元、控制单元以及运算单元：
    • 1、存储单元用于存放数据；
    • 2、控制单元用于识别字符是数据还是指令，以及控制程序的流程等；
    • 3、运算单元用于执行运算指令

通过上面的图灵机计算 1 + 2 的过程，可以发现图灵机主要功能就是读取纸带格子中的内容，然后交给控制单元识别字符是数字还是运算符指令，如果是数字则存入到图灵机状态中。如果是运算符，则通知运算符单元读取状态中的数值进行计算，计算结果最终返回给读写头，读写头把结果写入到纸带的格子中。

可以看到早期的计算机有着：读取->计算->返回数据的功能。

冯诺依曼架构

基本结构为 5 个部分，分别是运算器、控制器、存储器、输入设备、输出设备，包含这 5 个部分的计算机也被称为冯诺依曼模型。

主机：主机部分由运算器(CPU)、存储器(内存和硬盘)和控制器(主板上集成的电气元件)组成。

  • 运算器：负责执行所有的算术和逻辑运算。
  • 存储器：用于存储数据和指令。
  • 控制器：负责解释和执行指令，并控制其他部件的操作。

外设：由用户主导的输入和输出设备。

  • 输入设备：例如键盘、打孔卡片机等，用于将数据和指令输入到计算机中。
  • 输出设备：例如打印机、显示器等，用于将计算结果和其他信息输出给用户。

程序执行过程

程序实际上是一条一条指令，所以程序的运行过程就是把每一条指令一步一步的执行起来，负责执行指令的就是 CPU。

CPU 执行程序的过程如下：

  • 第一步，CPU 读取「程序计数器」的值，这个值是指令的内存地址，然后 CPU 的「控制单元」操作「地址总线」指定需要访问的内存地址，接着通知内存设备准备数据，数据准备好后通过「数据总线」将指令数据传给 CPU，CPU 收到内存传来的数据后，将这个指令数据存入到「指令寄存器」。
  • 第二步，「程序计数器」的值自增，表示指向下一条指令。这个自增的大小，由 CPU 的位宽决定，比如 32 位的 CPU，指令是 4 个字节，需要 4 个内存地址存放，因此「程序计数器」的值会自增 4；
  • 第三步，CPU 分析「指令寄存器」中的指令，确定指令的类型和参数，如果是计算类型的指令，就把指令交给「逻辑运算单元」运算；如果是存储类型的指令，则交由「控制单元」执行；

简单总结一下就是，一个程序执行的时候，CPU 会根据程序计数器里的内存地址，从内存里面把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，开始顺序读取下一条指令。CPU 从程序计数器读取指令、到执行、再到下一条指令，这个过程会不断循环，直到程序执行结束，这个不断循环的过程被称为 CPU 的指令周期。

操作系统的分类

无操作系统

1946年第一台计算机诞生—20世纪50年代中期，还未出现操作系统，计算机工作采用手工操作方式。

程序员将对应于程序和数据的已穿孔的纸带（或卡片）装入输入机，然后启动输入机把程序和数据输入计算机内存，接着通过控制台开关启动程序针对数据运行；计算完毕，打印机输出计算结果；用户取走结果并卸下纸带（或卡片）后，才让下一个用户上机。

手工操作方式两个特点：

  • 用户独占全机。不会出现因资源已被其他用户占用而等待的现象，但资源的利用率低。
  • CPU 等待手工操作。CPU的利用不充分。
批处理系统

批处理系统：加载在计算机上的一个系统软件，在它的控制下，计算机能够自动地、成批地处理一个或多个用户的作业（这作业包括程序、数据和命令）。

首先出现的是联机批处理系统，即作业的输入/输出由CPU来处理。主机与输入机之间增加一个存储设备——磁带。在运行于主机上的监督程序的自动控制下，计算机可自动完成：成批地把输入机上的用户作业读入磁带，依次把磁带上的用户作业读入主机内存并执行并把计算结果向输出机输出。完成了上一批作业后，监督程序又从输入机上输入另一批作业，保存在磁带上，并按上述步骤重复处理。

监督程序不停地处理各个作业，从而实现了作业到作业的自动转接，减少了作业建立时间和手工操作时间，有效克服了人机矛盾，提高了计算机的利用率。但是，在作业输入和结果输出时，主机的高速CPU仍处于空闲状态，等待慢速的输入/输出设备完成工作： 主机处于“忙等”状态。

为克服与缓解高速主机与慢速外设的矛盾，提高CPU的利用率，又引入了脱机批处理系统，即输入/输出脱离主机控制。这种方式的显著特征是：增加一台不与主机直接相连而专门用于与输入/输出设备打交道的卫星机。

  • 从输入机上读取用户作业并放到输入磁带上。
  • 从输出磁带上读取执行结果并传给输出机。

这样，主机不是直接与慢速的输入/输出设备打交道，而是与速度相对较快的磁带机发生关系，有效缓解了主机与设备的矛盾。主机与卫星机可并行工作，二者分工明确，可以充分发挥主机的高速计算能力。

IBM-7090/7094：配备的监督程序就是脱机批处理系统，是现代操作系统的原型。

即使引入了卫星机以提高数据传输效率，存储设备的速度仍然无法跟上CPU的运算速度。每次主机内存中只能存放一道作业，当该作业运行并发出输入/输出（I/O）请求时，快速的CPU不得不等待低速I/O的完成，导致CPU频繁空闲。为了改善CPU的利用率，多道程序系统应运而生。

多道处理系统

所谓多道程序设计技术，就是指允许多个程序同时进入内存并运行。即同时把多个程序放入内存，并允许它们交替在CPU中运行，它们共享系统中的各种硬、软件资源。当一道程序因I/O请求而暂停运行时，CPU便立即转去运行另一道程序。

单道程序的运行过程：在A程序计算时，I/O空闲， A程序I/O操作时，CPU空闲（B程序也是同样）必须A工作完成后，B才能进入内存中开始工作，两者是串行(可以理解为在同一个通道运行)的，全部完成共需时间=T1+T2。

多道程序的运行过程：将A、B两道程序同时存放在内存中，它们在系统的控制下，可相互穿插、交替地在CPU上运行。当A程序因请求I/O(输入输出)操作而放弃CPU时，B程序就可占用CPU运行，这样 CPU不再空闲，而正进行A I/O操作的I/O设备也不空闲，显然，CPU和I/O设备都处于忙状态，大大提高了资源的利用率。

在多道程序运行的情况下A、B全部完成所需时间<<T1+T2。

多道程序设计技术不仅使CPU得到充分利用，同时改善I/O设备和内存的利用率，从而提高了整个系统的资源利用率和系统吞吐量（单位时间内处理作业（程序）的个数），最终提高了整个系统的效率。

将多道程序设计技术融入到前面提到的批处理系统之中就会产生两种操作系统

  • 单批处理机系统
  • 多道批处理系统

这两个程序系统融入了多道程序设计技术的理念，可以同时处理多道程序，但是由于批处理系统的原理，其不提供人机交互能力，会给用户使用计算机带来不便，为了追求保证计算机效率，又能方便用户使用计算机，也就出现了一种全新的操作系统，分时操作系统。

分时操作系统

多用户分时系统是当今计算机操作系统中最普遍使用的一类操作系统。

由于CPU速度不断提高和采用分时技术，一台计算机可同时连接多个用户终端，而每个用户可在自己的终端上联机使用计算机，好象自己独占机器一样。

分时技术：把处理机(CPU)的运行时间分成很短的时间片，按时间片轮流把处理机分配给各联机作业使用。

若某个作业在分配给它的时间片内不能完成其计算，则该作业暂时中断，把处理机让给另一作业使用，等待下一轮时再继续其运行。由于计算机速度很快，作业运行轮转得很快，给每个用户的印象是，好像他独占了一台计算机。而每个用户可以通过自己的终端向系统发出各种操作控制命令，在充分的人机交互情况下，完成作业的运行。

从上面的描述可以得出，分时操作系统具有以下性质

  • 多路性。若干个用户同时使用一台计算机。微观上看是各用户轮流使用计算机；宏观上看是各用户并行工作。
  • 交互性。用户可根据系统对请求的响应结果，进一步向系统提出新的请求。这种能使用户与系统进行人机对话的工作方式，明显地有别于批处理系统，因而，分时系统又被称为交互式系统。
  • 独立性。用户之间可以相互独立操作，互不干扰。系统保证各用户程序运行的完整性，不会发生相互混淆或破坏现象。
  • 及时性。系统可对用户的输入及时作出响应。分时系统性能的主要指标之一是响应时间，它是指：从终端发出命令到系统予以应答所需的时间。

分时系统的主要目标：对用户响应的及时性，即不至于用户等待每一个命令的处理时间过长。

分时系统可以同时接纳数十个甚至上百个用户，由于内存空间有限，往往采用对换（又称交换）方式的存储方法。即将未轮到的作业放入磁盘，一旦轮到，再将其调入内存；而时间片用完后，又将作业存回磁盘（俗称“滚进”、“滚出“法），使同一存储区域轮流为多个用户服务。

实时系统

虽然多道批处理系统和分时系统能获得较令人满意的资源利用率和系统响应时间，但却不能满足实时控制与实时信息处理两个应用领域的需求。于是就产生了实时系统，即系统能够及时响应随机发生的外部事件，并在严格的时间范围内完成对该事件的处理。实时系统在一个特定的应用中常作为一种控制设备来使用。

实时系统可分成两类：

  • 实时控制系统。当用于飞机飞行、导弹发射等的自动控制时，要求计算机能尽快处理测量系统测得的数据，及时地对飞机或导弹进行控制，或将有关信息通过显示终端提供给决策人员。当用于轧钢、石化等工业生产过程控制时，也要求计算机能及时处理由各类传感器送来的数据，然后控制相应的执行机构。
  • 实时信息处理系统。当用于预定飞机票、查询有关航班、航线、票价等事宜时，或当用于银行系统、情报检索系统时，都要求计算机能对终端设备发来的服务请求及时予以正确的回答。此类对响应及时性的要求稍弱于第一类。

实时操作系统的主要特点：

  • 及时响应。每一个信息接收、分析处理和发送的过程必须在严格的时间限制内完成。
  • 高可靠性。需采取冗余措施，双机系统前后台工作，也包括必要的保密措施等。

操作系统发展图谱

操作系统运行环境*

在计算机中存在两种程序，系统外层的应用程序和内核程序。CPU在设计时存在特权指令与非特权指令，特权指令例如内存指令等。

处理器执行状态*

内核态和用户态是操作系统中的两种运行模式。它们的主要区别在于权限和可执行的操作：

  • 内核态（Kernel Mode）：在内核态下，CPU可以执行所有的指令和访问所有的硬件资源。这种模式下的操作具有更高的权限，主要用于操作系统内核的运行。
  • 用户态（User Mode）：在用户态下，CPU只能执行部分指令集，无法直接访问硬件资源。这种模式下的操作权限较低，主要用于运行用户程序。

内核态的底层操作主要包括：内存管理、进程管理、设备驱动程序控制、系统调用等。这些操作涉及到操作系统的核心功能，需要较高的权限来执行。分为内核态和用户态的原因主要有以下几点：

  • 安全性：通过对权限的划分，用户程序无法直接访问硬件资源，从而避免了恶意程序对系统资源的破坏。
  • 稳定性：用户态程序出现问题时，不会影响到整个系统，避免了程序故障导致系统崩溃的风险。
  • 隔离性：内核态和用户态的划分使得操作系统内核与用户程序之间有了明确的边界，有利于系统的模块化和维护。
内核态(特权模式)

内核态也被称为内核模式或特权模式，是操作系统内核的运行状态。处于内核态的CPU可以执行所有的指令，访问所有的内存地址，拥有最高的权限。内核态下运行的程序可以访问系统的所有资源，包括CPU、内存、I/O等。

在内核态下，操作系统可以响应所有的中断请求，处理硬件事件和系统调用。当应用程序发出系统调用时，CPU会切换到内核态，执行相应的操作，然后返回用户态。此外，当发生严重错误或异常时，也会触发内核态的切换。

内核指令

  1. 时钟管理

    时钟在操作系统中扮演着非常关键的角色，其主要功能和用途包括：

    • 计时：时钟提供了系统时间的基准，允许操作系统跟踪时间和日期。这是许多系统功能（如文件时间戳、计划任务）所必需的。
    • 时钟中断：时钟中断是操作系统用于时间管理的核心机制。通过定期触发时钟中断，操作系统可以执行以下任务：
    • 进程切换：在多任务操作系统中，时钟中断用于进程调度。调度程序可以决定是否需要进行上下文切换，以确保各个进程按计划运行。
    • 时间片管理：操作系统通过时钟中断来实现时间片轮转调度（Round-Robin Scheduling），确保每个进程在特定的时间片内执行。时间片结束时，时钟中断触发，调度程序检查是否需要将CPU分配给其他进程。

  2. 中断机制

    • 中断机制是操作系统响应各种事件的基本机制，分为硬件中断和软件中断。

    • 硬件中断：来自外部设备的信号，通知CPU有事件需要处理

      1. 键盘输入：用户按键产生中断，操作系统读取输入数据。

      2. 网络数据包：网络接口卡接收到数据包，产生中断通知操作系统处理。

      3. 定时器中断：系统时钟定期产生中断，用于维护时间和调度。

    • 软件中断：由程序或操作系统生成的中断，通常用于系统调用和异常处理：

      1. 系统调用：用户程序通过软件中断请求操作系统服务。
        1. 异常处理：例如除零错误、非法访问内存等会产生软件中断，操作系统捕获并处理这些异常。

  3. 原语

    原语是操作系统提供的基本操作，通常是底层的、不可分割的操作，具有以下特点

    • 接近硬件：原语通常直接操作硬件或系统的核心数据结构，如进程控制块(PCB)、内存页表等。

    • 原子性：原语必须是原子操作，确保操作在执行过程中不被中断，以保持系统的一致性和稳定性。例如，禁用中断期间的上下文切换操作。

    • 运行时间短：原语通常设计为非常短小，以减少对系统的整体性能影响。它们被频繁调用，必须执行迅速，以确保操作系统的高效性。

  4. 系统控制的数据结构

    进程管理是操作系统中负责创建、调度、和终止进程的部分，相关的数据结构包括：

    • 进程管理：PCB，进程队列，信号量和互斥锁
    • 存储器管理：页表，段表，内存块描述符，帧管理表
    • 设备管理：设备控制块（DCB），设备队列，缓冲区，I/O调度表
用户态(用户模式)

用户态也被称为用户模式，是指应用程序的运行状态。在这种模式下，应用程序拥有有限的系统资源访问权限，只能在操作系统划定的特定空间内运行。用户态下运行的程序不能直接访问硬件设备或执行特权指令，所有对硬件的访问都必须通过操作系统进行。

在用户态下，应用程序通过系统调用来请求操作系统提供的服务。例如，文件操作、网络通信等都需要通过系统调用来实现。当应用程序发出系统调用时，会触发上下文切换，将CPU的控制权交给操作系统内核，进入内核态。

中断与异常

中断是计算机系统中用于响应硬件设备请求的一种机制。它允许操作系统在外部设备需要处理时打断当前运行的程序，并切换到核心态执行相应的中断服务程序（ISR）。因此，中断机制可以被视为用户态与核心态之间的一种沟通方式，但不仅限于用户态发起的请求，硬件设备也会主动产生中断信号

中断是一种异步事件处理机制，异步处理事允许在某个操作启动后继续执行其他操作。当系统接收到中断请求时，当前正在运行的进程会被暂停，操作系统会调用中断处理程序来响应请求。中断处理程序应尽快完成，以避免影响其他进程的执行和后续中断请求的处理。

中断（外中断）

外中断是由计算机系统外部设备（如键盘、鼠标、网络适配器等）产生的中断信号，主要用于通知CPU处理外部事件。它的特点包括：

  1. 来源：外部硬件设备发出的信号。
  2. 响应性：确保及时响应用户输入和设备请求。
  3. 优先级：可以设置不同的优先级以处理重要事件。
异常（内中断）

异常是指在程序执行过程中出现的错误或非正常情况。例如，除以零、访问不存在的内存地址等等。当发生异常时，操作系统会停止当前进程的执行，并处理异常。处理完毕后，操作系统会终止当前进程并回收资源。

  • 文件损坏：例如，尝试访问受损的文件。
  • 进程越界：如访问非法内存地址。
  • 算术溢出：例如，整数溢出或除零错误。
  • 硬件故障：如硬件组件出现故障。
  • 软件中断：程序故意触发的软件中断请求。

异常通常是不预期的，指示系统出现了错误或问题。

区别：异常是中断的一种特殊形式，主要由于错误或不正常的情况触发，而中断不一定是由异常引起的，它可以是外部设备的正常请求或用户操作。

中断异常处理

中断异常处理是操作系统中一个重要的机制，用于处理外部事件或内部错误。当发生中断时，硬件设备或程序会向CPU发送中断信号。CPU收到中断信号后，会先保存当前的执行上下文，包括程序计数器和寄存器状态，以便在中断处理完成后能够恢复。接下来，操作系统会根据中断向量表确定中断的来源和类型。

然后，操作系统调度相应的中断处理程序（ISR）来处理特定的中断请求。ISR中会执行相应的处理逻辑，比如读取设备数据、清除中断标志或更新状态等。ISR执行完毕后，系统会恢复之前保存的上下文，以确保被中断的程序能够继续正常执行，最后通过中断返回指令使CPU返回到被中断的程序继续执行。

在具体实现中，假设一个键盘中断的例子：

  • 当用户按下键盘时，硬件生成一个中断信号。
  • CPU保存当前执行的程序状态。
  • 操作系统识别为键盘中断，调用相应的ISR来读取按键。
  • ISR完成任务后，恢复程序状态，继续执行被中断的程序。

这个过程确保了操作系统能够及时响应各种事件，并且在处理完成后能够恢复到原来的执行状态。

系统调用

系统调用是指的是，用户在程序中调用操作系统所提供的子功能，系统调用可视为特殊的公共子程序，这些系统调用按照功能可以大致分为几类。

  • 设备管理：完成设备的请求和释放，以及设备启动
  • 文件管理：完成文件的读写创建和删除
  • 进程管理：关于创建撤销和阻塞等功能
  • 进程通讯：完成进程之间关系的传递
  • 内存管理：完成内存的分配

系统调用的作用正是通过用户态控制内核态。系统调用提供了一种机制，允许用户程序（在用户态运行）请求操作系统内核（在内核态运行）执行特权操作，如文件操作、进程管理、内存分配和网络通信等。这个过程一般如下：

  1. 用户程序发起请求：程序通过特定的系统调用接口（如库函数）发起请求，传递必要的参数。
  2. 陷入内核态：程序会通过软中断或特定的指令（如syscall或int还有trap）切换到内核态，操作系统会保存当前的用户上下文。
  3. 执行系统调用：在内核态下，操作系统根据系统调用号找到对应的处理程序，执行请求的操作。
  4. 返回用户态：操作系统完成请求后，恢复用户程序的上下文，并返回到用户态，继续执行。

系统结构*

系统结构的目的是降低系统的复杂度，让人类可以直观理解操作系统的组成。

单体结构

到目前为止，在大多数系统中，整个系统在内核态以单一程序的方式运行。整个操作系统是以程序集合来编写的，链接在一块形成一个大的二进制可执行程序。使用此技术时，如果系统中的每个过程都提供了前者所需的一些有用的计算，则它可以自由调用任何其他过程。在单体系统中，调用任何一个所需要的程序都非常高效，但是上千个不受限制的彼此调用往往非常臃肿和笨拙，而且单体系统必然存在单体问题，那就是只要系统发生故障，那么任何系统和应用程序将不可用，这往往是灾难性的。

在单体系统中构造实际目标程序时，会首先编译所有单个过程（或包含这些过程的文件），然后使用系统链接器将它们全部绑定到一个可执行文件中

对于单体系统，往往有下面几种建议

  • 需要有一个主程序，用来调用请求服务程序
  • 需要一套服务过程，用来执行系统调用
  • 需要一套服务程序，用来辅助服务过程调用

在单体系统中，对于每个系统调用都会有一个服务程序来保障和运行。需要一组实用程序来弥补服务程序需要的功能，例如从用户程序中获取数据。可将各种过程划分为一个三层模型

除了在计算机初启动时所装载的核心操作系统外，许多操作系统还支持额外的扩展。比如 I/O 设备驱动和文件系统。这些部件可以按需装载。在 UNIX 中把它们叫做 共享库(shared library)，在 Windows 中则被称为 动态链接库(Dynamic Link Library,DLL)。他们的扩展名为 .dll，在 C:\Windows\system32 目录下存在 1000 多个 DLL 文件，所以不要轻易删除 C 盘文件，否则可能就炸了哦。

层次结构

分层系统使用层来分隔不同的功能单元。每一层只与该层的上层和下层通信。每一层都使用下面的层来执行其功能。层之间的通信通过预定义的固定接口通信。

分层系统是由 E.W.Dijkstar 和他的学生在荷兰技术学院所开发的 THE 系统。把上面单体系统进一步通用化，就变为了一个层次式结构的操作系统，它的上层软件都是在下层软件的基础之上构建的。该系统分为六层，如下所示

层号 功能
5 操作员
4 用户程序
3 输入/输出管理
2 操作员-进程通信
1 存储器和磁鼓管理
0 处理器分配和多道程序编程

处理器在 0 层运行，当中断发生或定时器到期时，由该层完成进程切换；在第 0 层之上，系统由一些连续的进程组成，编写这些进程时不用再考虑在单处理器上多进程运行的细节。内存管理在第 1 层，它分配进程的主存空间。第 1 层软件保证一旦需要访问某一页面，该页面必定已经在内存中，并且在页面不需要的时候将其移出。

第 2 层处理进程与操作员控制台（即用户）之间的通信。第 3 层管理 I/O 设备和相关的信息流缓冲区。第 4 层是用户程序层，用户程序不用考虑进程、内存、控制台或 I/O 设备管理等细节。系统操作员在第 5 层。

微内核结构

在分层方式中，设计者要确定在哪里划分 内核-用户 的边界。传统上，所有的层都在内核中，但是这样做没有必要。事实上，尽可能减少内核态中功能可能是更好的做法。因为内核中的错误很难处理，一旦内核态中出错误会拖累整个系统。

所以，为了实现高可靠性，将操作系统划分成小的、层级之间能够更好定义的模块是很有必要的，只有一个模块 —- 微内核 —- 运行在内核态，其余模块可以作为普通用户进程运行。由于把每个设备驱动和文件系统分别作为普通用户进程，这些模块中的错误虽然会使这些模块崩溃，但是不会使整个系统死机。

MINIX 3 是微内核的代表作，它的具体结构如下

在内核的外部，系统的构造有三层，它们都在用户态下运行，最底层是设备驱动器。由于它们都在用户态下运行，所以不能物理的访问 I/O 端口空间，也不能直接发出 I/O 命令。相反，为了能够对 I/O 设备编程，驱动器构建一个结构，指明哪个参数值写到哪个 I/O 端口，并声称一个内核调用，这样就完成了一次调用过程。

位于用户态的驱动程序上面是服务器层，包含有服务器，它们完成操作系统的多数工作。由一个或多个文件服务器管理着文件系统，进程管理器创建、销毁和管理进程。服务器中有一个特殊的服务器称为 再生服务器(reincarnation server)，它的任务就是检查服务器和驱动程序的功能是否正确，一旦检查出来错误，它就会补上去，无需用户干预。这种方式使得系统具有可恢复性，并具有较高的可靠性。

微内核中的内核还具有一种 机制 与 策略 分离的思想。比如系统调度，一个比较简单的调度算法是，对每个进程赋予一个优先级，并让内核执行具有最高优先级的进程。这里，内核机制就是寻找最高的优先级进程并运行。而策略（赋予进程优先级）可以在用户态中的进程完成。在这种模式中，策略和机制是分离的，从而使内核变得更小。

客户-服务器模式

微内核思想的策略是把进程划分为两类：服务器，每个服务器用来提供服务；客户端，使用这些服务。这个模式就是所谓的 客户-服务器(C/S)模式。

客户-服务器模式会有两种载体，一种情况是一台计算机既是客户又是服务器，在这种方式下，操作系统会有某种优化；但是普遍情况下是客户端和服务器在不同的机器上，它们通过局域网或广域网连接。

客户通过发送消息与服务器通信，客户端并不需要知道这些消息是在本地机器上处理，还是通过网络被送到远程机器上处理。对于客户端而言，这两种情形是一样的：都是发送请求并得到回应。

越来越多的系统，包括家里的 PC，都成为客户端，而在某地运行的大型机器则成为服务器。许多 web 就是以这种方式运行的。一台 PC 向某个服务器请求一个 Web 页面，服务器把 Web 页面返回给客户端，这就是典型的客服-服务器模式

虚拟机

虚拟机（通常简称为 VM）与其他任何物理计算机（如笔记本电脑、智能手机或服务器）没有什么不同。它也包括用于存储文件的 CPU、内存和磁盘，并可连接到 Internet（如果需要）。虽然构成计算机的部件（称为硬件）是物理的、有形的，但 VM 通常被认为是物理服务器中的虚拟计算机或软件定义的计算机，仅以代码的形式存在。

虚拟化是创建基于软件的，或计算机的“虚拟”版本的过程，其中包含从物理主机计算机（如个人计算机）和/或远程服务器（如云提供商的数据中心的服务器）“借用”的专用 CPU、内存和存储量。虚拟机是指行为方式类似于实际计算机的计算机文件（通常称为映像）。它可以作为独立的计算环境在窗口中运行，通常用于运行不同的操作系统，甚至可作为用户的整个计算机体验，这在许多人的工作计算机上都很常见。虚拟机与系统的其余部分相互隔离，这意味着虚拟机中的软件不会干扰主机的主要操作系统。

下面是虚拟机的几种使用方式：

  • 构建应用并将其部署到云。
  • 试用新的操作系统 (OS)，包括 beta 版本。
  • 创建一个新环境，使开发人员能够更简单、更快地运行开发测试方案。
  • 备份现有 OS。
  • 通过安装旧版 OS 访问受病毒感染的数据或运行旧版应用程序。
  • 在最初并不适用的操作系统上运行软件或应用。

组成硬件

内存(RAM)

在计算机数据存储中，存储数据的基本单位是字节（*byte*），1 字节等于 8 位（8 bit）。每一个字节都对应一个内存地址。

内存的地址是从 0 开始编号的，然后自增排列，最后一个地址为内存总字节数 - 1，这种结构好似我们程序里的数组，所以内存的读写任何一个数据的速度都是一样的。

中央处理器(CPU)

CPU的作用是取值执行，32 位和 64 位 CPU 最主要区别在于一次能计算多少字节数据：

  • 32 位 CPU 一次可以计算 4 个字节；
  • 64 位 CPU 一次可以计算 8 个字节；

之所以 CPU 要这样设计，是为了能计算更大的数值，如果是 8 位的 CPU，那么一次只能计算 1 个字节 0~255 范围内的数值，这样就无法一次完成计算 10000 * 500 ，于是为了能一次计算大数的运算，CPU 需要支持多个 byte 一起计算，所以 CPU 位宽越大，可以计算的数值就越大，比如说 32 位 CPU 能计算的最大整数是 4294967295。

寄存器

程序计数器（PC，Program counter），用于存放指令的地址。为了保证程序(在操作系统中理解为进程)能够连续地执行下去，CPU必须具有某些手段来确定下一条指令的地址。当执行一条指令时，首先需要根据PC中存放的指令地址，将指令由内存取到指令寄存器中，此过程称，为“取指令”。与此同时，PC中的地址或自动加1或由转移指针给出下一条指令的地址。此后经过分析指令，执行指令。完成第一条指令的执行，而后根据PC取出第二条指令的地址，如此循环，执行每一条指令。

指令寄存器（IR，Instruction Register），用来保存当前正在执行的一条指令。是临时放置从内存里面取得的程序指令的寄存器，用于存放当前从主存储器读出的正在执行的一条指令。当执行一条指令时，先把它从内存取到数据寄存器（DR，Data Register）中，然后再传送至IR。指令划分为操作码和地址码字段，由二进制数字组成。为了执行任何给定的指令，必须对操作码进行测试，以便识别所要求的操作。指令译码器就是做这项工作的。指令寄存器中操作码字段的输出就是指令译码器的输入。操作码一经译码后，即可向操作控制器发出具体操作的特定信号。

通用寄存器（GR，General register）：通用寄存器可用于传送和暂存数据，也可参与算术逻辑运算，并保存运算结果。除此之外，它们还各自具有一些特殊功能。通用寄存器的长度取决于机器字长，汇编语言程序员必须熟悉每个寄存器的一般用途和特殊用途，只有这样，才能在程序中做到正确、合理地使用它们。

总线

总线是用于 CPU 和内存以及其他设备之间的通信，总线可分为 3 种：

  • 地址总线，用于指定 CPU 将要操作的内存地址；
  • 数据总线，用于读写内存的数据；
  • 控制总线，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；

当 CPU 要读写内存数据的时候，一般需要通过下面这三个总线：

  • 首先要通过「地址总线」来指定内存的地址；
  • 然后通过「控制总线」控制是读或写命令；
  • 最后通过「数据总线」来传输数据；

第二章 进程与线程

进程

操作系统中最核心的概念就是 进程，进程是对正在运行中的程序的一个抽象。操作系统的其他所有内容都是围绕着进程展开的。进程是操作系统提供的最古老也是最重要的概念之一。即使可以使用的 CPU 只有一个，它们也支持（伪）并发操作。它们会将一个单独的 CPU 抽象为多个虚拟机的 CPU。可以说：没有进程的抽象，现代操作系统将不复存在。

所有现代的计算机会在同一时刻做很多事情，过去使用计算机的人（单 CPU）可能完全无法理解现在这种变化，举个例子更能说明这一点：首先考虑一个 Web 服务器，请求都来自于 Web 网页。当一个请求到达时，服务器会检查当前页是否在缓存中，如果是在缓存中，就直接把缓存中的内容返回。如果缓存中没有的话，那么请求就会交给磁盘来处理。

但是，从 CPU 的角度来看，磁盘请求需要更长的时间，因为磁盘请求会很慢。当硬盘请求完成时，更多其他请求才会进入。如果有多个磁盘的话，可以在第一个请求完成前就可以连续的对其他磁盘发出部分或全部请求。很显然，这是一种并发现象，需要有并发控制条件来控制并发现象。

现在考虑只有一个用户的 PC。当系统启动时，许多进程也在后台启动，用户通常不知道这些进程的启动，试想一下，当你自己的计算机启动的时候，你能知道哪些进程是需要启动的么？这些后台进程可能是一个需要输入电子邮件的电子邮件进程，或者是一个计算机病毒查杀进程来周期性的更新病毒库。某个用户进程可能会在所有用户上网的时候打印文件以及刻录 CD-ROM，这些活动都需要管理。于是一个支持多进程的多道程序系统就会显得很有必要了。

在许多多道程序系统中，CPU 会在进程间快速切换，使每个程序运行几十或者几百毫秒。然而，严格意义来说，在某一个瞬间，CPU 只能运行一个进程，然而我们如果把时间定位为 1 秒内的话，它可能运行多个进程。这样就会让我们产生并行的错觉。有时候人们说的 伪并行(pseudoparallelism) 就是这种情况，以此来区分多处理器系统(该系统由两个或多个 CPU 来共享同一个物理内存)

再来详细解释一下伪并行：伪并行是指单核或多核处理器同时执行多个进程，从而使程序更快。 通过以非常有限的时间间隔在程序之间快速切换CPU，因此会产生并行感。 缺点是 CPU 时间可能分配给下一个进程，也可能不分配给下一个进程。

因为 CPU 执行速度很快，进程间的换进换出也非常迅速，因此我们很难对多个并行进程进行跟踪，所以，在经过多年的努力后，操作系统的设计者开发了用于描述并行的一种概念模型（顺序进程），使得并行更加容易理解和分析。

进程模型

在进程模型中，所有计算机上运行的软件，通常也包括操作系统，被组织为若干顺序进程(sequential processes)，简称为 进程(process) 。一个进程就是一个正在执行的程序的实例，进程也包括程序计数器、寄存器和变量的当前值。从概念上来说，每个进程都有各自的虚拟 CPU，但是实际情况是 CPU 会在各个进程之间进行来回切换。

这种方式不是主流，主流的是抢占式多任务

如上图所示，这是一个具有 4 个程序的多道处理程序，在进程不断切换的过程中，程序计数器也在不同的变化。

在上图中，这 4 道程序被抽象为 4 个拥有各自控制流程（即每个自己的程序计数器）的进程，并且每个程序都独立的运行。当然，实际上只有一个物理程序计数器，每个程序要运行时，其逻辑程序计数器会装载到物理程序计数器中。当程序运行结束后，其物理程序计数器就会是真正的程序计数器，然后再把它放回进程的逻辑计数器中。

从下图我们可以看到，在观察足够长的一段时间后，所有的进程都运行了，但在任何一个给定的瞬间仅有一个进程真正运行。

因此，当我们说一个 CPU 只能真正一次运行一个进程的时候，即使有 2 个核（或 CPU），每一个核也只能一次运行一个线程。

由于 CPU 会在各个进程之间来回快速切换，所以每个进程在 CPU 中的运行时间是无法确定的。并且当同一个进程再次在 CPU 中运行时，其在 CPU 内部的运行时间往往也是不固定的。进程和程序之间的区别是非常微妙的，但是通过一个例子可以让你加以区分：想想一位会做饭的计算机科学家正在为他的女儿制作生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原料：面粉、鸡蛋、糖、香草汁等。在这个比喻中，做蛋糕的食谱就是程序、计算机科学家就是 CPU、而做蛋糕的各种原料都是输入数据。进程就是科学家阅读食谱、取来各种原料以及烘焙蛋糕等一系例了动作的总和。

现在假设科学家的儿子跑过来告诉他，说他的头被蜜蜂蜇了一下，那么此时科学家会记录出来他做蛋糕这个过程到了哪一步，然后拿出急救手册，按照上面的步骤给他儿子实施救助。这里，会涉及到进程之间的切换，科学家（CPU）会从做蛋糕（进程）切换到实施医疗救助（另一个进程）。等待伤口处理完毕后，科学家会回到刚刚记录做蛋糕的那一步，继续制作。

这里的关键思想是认识到一个进程所需的条件，进程是某一类特定活动的总和，它有程序、输入输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另外一个进程提供服务。另外需要注意的是，如果一个进程运行了两遍，则被认为是两个进程。那么我们了解到进程模型后，那么进程是如何创建的呢？

进程的终止

进程在创建之后，它就开始运行并做完成任务。然而，没有什么事儿是永不停歇的，包括进程也一样。进程早晚会发生终止，但是通常是由于以下情况触发的

  • 正常退出(自愿的)
  • 错误退出(自愿的)
  • 严重错误(非自愿的)
  • 被其他进程杀死(非自愿的)

  1. 正常退出(中断)

    多数进程是由于完成了工作而终止。当编译器完成了所给定程序的编译之后，编译器会执行一个系统调用告诉操作系统它完成了工作。这个调用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向屏幕中的软件也支持自愿终止操作。字处理软件、Internet 浏览器和类似的程序中总有一个供用户点击的图标或菜单项，用来通知进程删除它锁打开的任何临时文件，然后终止。

  2. 错误退出(中断)

    进程发生终止的第二个原因是发现严重错误，例如，如果用户执行如下命令cc foo.c

    为了能够编译 foo.c 但是该文件不存在，于是编译器就会发出声明并退出。在给出了错误参数时，面向屏幕的交互式进程通常并不会直接退出，因为这从用户的角度来说并不合理，用户需要知道发生了什么并想要进行重试，所以这时候应用程序通常会弹出一个对话框告知用户发生了系统错误，是需要重试还是退出。

  3. 严重错误(异常)

    进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所导致的。例如，执行了一条非法指令，引用不存在的内存，或者除数是 0 等。在有些系统比如 UNIX 中，进程可以通知操作系统，它希望自行处理某种类型的错误，在这类错误中，进程会收到信号（中断），而不是在这类错误出现时直接终止进程。

  4. 被其他进程杀死

    第四个终止进程的原因是，某个进程执行系统调用告诉操作系统杀死某个进程。在 UNIX 中，这个系统调用是 kill。在 Win32 中对应的函数是 TerminateProcess（注意不是系统调用）。

进程控制块(PCB)

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

PCB具体包含的信息如下：

  1. 进程描述信息
    • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符(PID)
    • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
  1. 进程控制和管理信息：
    • 进程当前状态，如 new、ready、running、waiting 或 blocked 等
    • 进程优先级：进程抢占 CPU 时的优先级
  1. 资源分配清单：有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。
  1. CPU 相关信息：CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

可见，PCB 包含信息还是比较多的。每个 PCB 是如何组织的呢？通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

  • 将所有处于就绪状态的进程链在一起，称为就绪队列；
  • 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
  • 另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

除了链接的组织方式，还有索引方式，它的工作原理：将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。一般会选择链表，是因为可能面临进程创建，销毁等调度导致进程状态发生变化，通过链表能够更加灵活的插入和删除。

进程状态

一般说来，一个进程并不是自始至终连续不停地运行的，它与并发执行中的其他进程的执行是相互制约的。它有时处于运行状态，有时又由于某种原因而暂停运行处于等待状态，当使它暂停的原因消失后，它又进入准备运行状态。

所以，在一个进程的活动期间至少具备三种基本状态，即运行状态、就绪状态、阻塞状态。

上图中各个状态的意义：

  • 运行状态（Running）：该时刻进程占用 CPU；
  • 就绪状态（Ready）：可运行，由于其他进程处于运行状态而暂时停止运行；
  • 阻塞状态（Blocked）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；

当然，进程还有另外两个基本状态：

  • 创建状态（new）：进程正在被创建时的状态；
  • 结束状态（Exit）：进程正在从系统中消失时的状态；

于是，一个完整的进程状态的变迁如下图：

再来详细说明一下进程的状态变迁：

  • NULL -> 创建状态：一个新进程被创建时的第一个状态。

  • 创建状态 -> 就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的。

    • 过程：申请空白PCB → 填写控制信息 → 分配资源 → 转入就绪状态（若资源足够）。

  • 就绪状态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运行该进程。

    • 特征：在就绪队列中等待调度。

    • 原因：进程被调度程序选中，获得CPU时间片。

  • 运行状态 -> 结束状态：当进程已经运行完成或出错时，会被操作系统作结束状态处理。

    • 描述：进程正在使用CPU执行任务。

  • 运行状态 -> 就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行。

    • 原因：时间片用完，或有更高优先级的进程变为就绪状态。

  • 运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件。

    • 描述：进程等待某些事件发生，如I/O操作完成或资源释放。

    • 原因：进程因等待某些事件（如I/O操作）而无法继续执行。

  • 阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态。

    • 原因：所等待的事件发生，进程被唤醒，重新进入就绪队列。

  • 结束状态：

    • 描述：进程正常或异常结束，操作系统进行善后处理，清除PCB并释放资源

如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间，显然不是我们所希望的，毕竟物理内存空间是有限的，被阻塞状态的进程占用着物理内存就一种浪费物理内存的行为。所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。

另外，挂起状态可以分为两种：

  • 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现
  • 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行

这两种挂起状态加上前面的五种状态，就变成了七种状态变迁

导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

  • 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
  • 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程
进程控制

我们熟知了进程的状态变迁和进程的数据结构 PCB 后，再来看看进程的创建、终止、阻塞、唤醒的过程，这些过程也就是进程的控制。

  1. 创建进程

    操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源。创建进程的过程如下：

    • 申请一个空白的 PCB，并向 PCB 中填写一些控制和管理进程的信息，比如进程的唯一标识等；

    • 为该进程分配运行时所必需的资源，比如内存资源；

    • 将 PCB 插入到就绪队列，等待被调度运行；

  1. 终止进程进程可以有 3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。

    当子进程被终止时，其在父进程处继承的资源应当还给父进程。而当父进程被终止时，该父进程的子进程就变为孤儿进程，会被 1 号进程收养，并由 1 号进程对它们完成状态收集工作。终止进程的过程如下：

    • 查找需要终止的进程的 PCB；

    • 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程；

    • 如果其还有子进程，则应将该进程的子进程交给 1 号进程接管；

    • 将该进程所拥有的全部资源都归还给操作系统；

    • 将其从 PCB 所在队列中删除；

  1. 阻塞进程

    当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。阻塞进程的过程如下：

    • 找到将要被阻塞进程标识号对应的 PCB

    • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行

    • 将该 PCB 插入到阻塞队列中去

  1. 唤醒进程

    进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的。如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。唤醒进程的过程如下：

    • 在该事件的阻塞队列中找到相应进程的 PCB

    • 将其从阻塞队列中移出，并置其状态为就绪状态

    • 把该 PCB 插入到就绪队列中，等待调度程序调度

进程的阻塞和唤醒是一对功能相反的语句，如果某个进程调用了阻塞语句，则必有一个与之对应的唤醒语句。

上下文切换

进程切换到另一个进程运行，称为进程的上下文切换。

在详细说进程上下文切换前，先来看看 CPU 上下文切换

大多数操作系统都是多任务，通常支持大于 CPU 数量的任务同时运行。实际上，这些任务并不是同时运行的，只是因为系统在很短的时间内，让各个任务分别在 CPU 运行，于是就造成同时运行的错觉。任务是交给 CPU 运行的，那么在每个任务运行前，CPU 需要知道任务从哪里加载，又从哪里开始运行。

所以，操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器。

CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存（缓存）。举个例子，寄存器像是你的口袋，内存像你的书包，硬盘则是你家里的柜子，如果你的东西存放到口袋，那肯定是比你从书包或家里柜子取出来要快的多。

再来，程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。所以说，CPU 寄存器和程序计数是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。既然知道了什么是 CPU 上下文，那理解 CPU 上下文切换就不难了。

CPU 上下文切换就是先把前一个任务的 CPU 上下文（CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

系统内核会存储保持下来的上下文信息，当此任务再次被分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。上面说到所谓的「任务」，主要包含进程、线程和中断。所以，可以根据任务的不同，把 CPU 上下文切换分成：进程上下文切换、线程上下文切换和中断上下文切换。

进程的上下文切换到底是切换什么

进程是由内核管理和调度的，所以进程的切换只能发生在内核态。

所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行，如下图所示：

需要注意的是，进程的上下文开销是很关键的，我们希望它的开销越小越好，这样可以使得进程可以把更多时间花费在执行程序上，而不是耗费在上下文切换。

发生进程上下文切换的哪些场景

  • 为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；
  • 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行
  • 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
  • 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
  • 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

线程*

线程简述

在早期的操作系统中都是以进程作为独立运行的基本单位，直到后面，计算机科学家们又提出了更小的能独立运行的基本单位，也就是线程。

可以把线程理解为轻量级进程或者理解为在CPU中运行的最小程序

我们举个例子，假设你要编写一个视频播放器软件，那么该软件功能的核心模块有三个

  • 从视频文件当中读取数据；
  • 对读取的数据进行解压缩；
  • 把解压缩后的视频数据播放出来；

对于单进程的实现方式，会是以下这个方式：

对于单进程的这种方式，存在以下问题：

  • 播放出来的画面和声音会不连贯，因为当 CPU 能力不够强的时候，Read 的时候可能进程就等在这了，这样就会导致等半天才进行数据解压和播放；
  • 各个函数之间不是并发执行，影响资源的使用效率

改进成多进程的方式：

对于多进程的这种方式，依然会存在问题：

  • 进程之间如何通信，共享数据？比如我需要根据不同的视频进度更新进度条，但是进程之间无法直接通讯(一般通过管道)，速度就很慢。
  • 同时维护进程的系统开销较大，如创建进程时，分配资源、建立 PCB；终止进程时，回收资源、撤销 PCB；进程切换时，保存当前进程的状态信息；

为了解决这些问题需要有一种新的实体，满足以下特性：

  • 实体之间可以并发运行
  • 实体之间共享相同的地址空间

这个时候就发明出了线程，通常我们说的多线程是存在于一个进程中的。但是为什么要在进程的基础上再创建一个线程的概念，准确的说，这其实是进程模型和线程模型的讨论，回答这个问题，可能需要分三步来回答

  • 多线程之间会共享同一块地址空间和所有可用数据的能力，这是进程所不具备的
  • 线程要比进程更轻量级，由于线程更轻，所以它比进程更容易创建，也更容易撤销。在许多系统中，创建一个线程要比创建一个进程快 10 - 100 倍。
  • 第三个原因可能是性能方面的探讨，如果多个线程都是 CPU 密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的 I/O 处理，拥有多个线程能在这些活动中彼此重叠进行，从而会加快应用程序的执行速度

通过线程，我们就可以解决上面提出的问题。

线程模型

理解进程的另一个角度是，用某种方法把相关的资源集中在一起。进程有存放程序正文和数据以及其他资源的地址空间。这些资源包括打开的文件、子进程、即将发生的定时器、信号处理程序、账号信息等。把这些信息放在进程中会比较容易管理。

另一个概念是，进程中拥有一个执行的线程，通常简写为 线程(thread)。线程会有程序计数器，用来记录接着要执行哪一条指令；线程还拥有寄存器，用来保存线程当前正在使用的变量；线程还会有堆栈，用来记录程序的执行路径。尽管线程必须在某个进程中执行，但是进程和线程完完全全是两个不同的概念，并且他们可以分开处理。进程用于把资源集中在一起，而线程则是 CPU 上调度执行的实体。

线程给进程模型增加了一项内容，即在同一个进程中，允许彼此之间有较大的独立性且互不干扰。在一个进程中并行运行多个线程类似于在一台计算机上运行多个进程。在多个线程中，各个线程共享同一地址空间和其他资源。在多个进程中，进程共享物理内存、磁盘、打印机和其他资源。因为线程会包含有一些进程的属性，所以线程被称为轻量的进程(lightweight processes)。

多线程(multithreading)一词还用于描述在同一进程中多个线程的情况。

下图我们可以看到三个传统的进程，每个进程有自己的地址空间和单个控制线程。每个线程都在不同的地址空间中运行

下图中，我们可以看到有一个进程三个线程的情况。每个线程都在相同的地址空间中运行。

线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址，因此一个线程可以读取、写入甚至擦除另一个线程的堆栈。线程之间除了共享同一内存空间外，还具有如下不同的内容

上图左边的是同一个进程中每个线程共享的内容，上图右边是每个线程中的内容。也就是说左边的列表是进程的属性，右边的列表是线程的属性。

和进程一样，线程可以处于下面这几种状态：运行中、阻塞、就绪和终止（进程图中没有画）。正在运行的线程拥有 CPU 时间片并且状态是运行中。一个被阻塞的线程会等待某个释放它的事件。例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞直到有输入为止。线程通常会被阻塞，直到它等待某个外部事件的发生或者有其他线程来释放它。线程之间的状态转换和进程之间的状态转换是一样的。

每个线程都会有自己的堆栈，如下图所示

线程实现

主要有三种实现方式，这里简单说一下，用户空间就是用户操作操作系统时所能接触到的一切内容。通常内核空间会对于用户空间来隐藏，也就意味着内核空间需要最高权限才能调用。还有就是，内核空间可以调用硬件的各种功能。

  • 在用户空间中实现线程；
  • 在内核空间中实现线程；
  • 在用户和内核空间中混合实现线程。
用户空间

第一种方法是把整个线程包放在用户空间中，内核对线程一无所知，它不知道线程的存在。所有的这类实现都有同样的通用结构

线程在运行时系统之上运行，运行时系统是管理线程过程的集合，包括前面提到的四个过程： pthread_create, pthread_exit, pthread_join 和 pthread_yield。

运行时系统(Runtime System) 也叫做运行时环境，该运行时系统提供了程序在其中运行的环境。此环境可能会解决许多问题，包括应用程序内存的布局，程序如何访问变量，在过程之间传递参数的机制，与操作系统的接口等等。

在用户空间管理线程时，每个进程需要有其专用的线程表(thread table)，用来跟踪该进程中的线程。这些表和内核中的进程表类似，不过它仅仅记录各个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态。该线程标由运行时系统统一管理。当一个线程转换到就绪状态或阻塞状态时，在该线程表中存放重新启动该线程的所有信息，与内核在进程表中存放的信息完全一样。**

在用户空间实现线程的优势

在用户空间中实现线程要比在内核空间中实现线程具有这些方面的优势：考虑如果在线程完成时或者是在调用 pthread_yield 时，必要时会进程线程切换，然后线程的信息会被保存在运行时环境所提供的线程表中，然后，线程调度程序来选择另外一个需要运行的线程。保存线程的状态和调度程序都是本地过程，所以启动他们比进行内核调用效率更高。因而不需要切换到内核，也就不需要上下文切换，也不需要对内存高速缓存进行刷新，因为线程调度非常便捷，因此效率比较高。

在用户空间实现线程还有一个优势就是它允许每个进程有自己定制的调度算法。例如在某些应用程序中，那些具有垃圾收集线程的应用程序（知道是谁了吧）就不用担心自己线程会不会在不合适的时候停止，这是一个优势。用户线程还具有较好的可扩展性，因为内核空间中的内核线程需要一些表空间和堆栈空间，如果内核线程数量比较大，容易造成问题。

在用户空间实现线程的劣势

尽管在用户空间实现线程会具有一定的性能优势，但是劣势还是很明显的，你如何实现阻塞系统调用呢？假设在还没有任何键盘输入之前，一个线程读取键盘，让线程进行系统调用是不可能的，因为这会停止所有的线程。所以，使用线程的一个目标是能够让线程进行阻塞调用，并且要避免被阻塞的线程影响其他线程。

与阻塞调用类似的问题是缺页中断问题，实际上，计算机并不会把所有的程序都一次性的放入内存中，如果某个程序发生函数调用或者跳转指令到了一条不在内存的指令上，就会发生页面故障，而操作系统将到磁盘上取回这个丢失的指令，这就称为缺页故障。而在对所需的指令进行读入和执行时，相关的进程就会被阻塞。如果只有一个线程引起页面故障，内核由于甚至不知道有线程存在，通常会吧整个进程阻塞直到磁盘 I/O 完成为止，尽管其他的线程是可以运行的。

另外一个问题是，如果一个线程开始运行，该线程所在进程中的其他线程都不能运行，除非第一个线程自愿的放弃 CPU，在一个单进程内部，没有时钟中断，所以不可能使用轮转调度的方式调度线程。除非其他线程能够以自己的意愿进入运行时环境，否则调度程序没有可以调度线程的机会。

内核空间

现在我们考虑使用内核来实现线程的情况，此时不再需要运行时环境了。另外，每个进程中也没有线程表。相反，在内核中会有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它会进行一个系统调用，这个系统调用通过对线程表的更新来完成线程创建或销毁工作。

内核中的线程表持有每个线程的寄存器、状态和其他信息。这些信息和用户空间中的线程信息相同，但是位置却被放在了内核中而不是用户空间中。另外，内核还维护了一张进程表用来跟踪系统状态。所有能够阻塞的调用都会通过系统调用的方式来实现，当一个线程阻塞时，内核可以进行选择，是运行在同一个进程中的另一个线程（如果有就绪线程的话）还是运行一个另一个进程中的线程。但是在用户实现中，运行时系统始终运行自己的线程，直到内核剥夺它的 CPU 时间片（或者没有可运行的线程存在了）为止。

由于在内核中创建或者销毁线程的开销比较大，所以某些系统会采用可循环利用的方式来回收线程。当某个线程被销毁时，就把它标志为不可运行的状态，但是其内部结构没有受到影响。稍后，在必须创建一个新线程时，就会重新启用旧线程，把它标志为可用状态。

如果某个进程中的线程造成缺页故障后，内核很容易的就能检查出来是否有其他可运行的线程，如果有的话，在等待所需要的页面从磁盘读入时，就选择一个可运行的线程运行。这样做的缺点是系统调用的代价比较大，所以如果线程的操作（创建、终止）比较多，就会带来很大的开销。

混合实现

结合用户空间和内核空间的优点，设计人员采用了一种内核级线程的方式，然后将用户级线程与某些或者全部内核线程多路复用起来

在这种模型中，编程人员可以自由控制用户线程和内核线程的数量，具有很大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。

进程通讯

进程是需要频繁的和其他进程进行交流的。例如，在一个 shell 管道中，第一个进程的输出必须传递给第二个进程，这样沿着管道进行下去。因此，进程之间如果需要通信的话，必须要使用一种良好的数据结构以至于不能被中断。下面我们会一起讨论有关 进程间通信(Inter Process Communication, IPC) 的问题。

关于进程间的通信，这里有三个问题

  • 上面提到了第一个问题，那就是一个进程如何传递消息给其他进程。
  • 第二个问题是如何确保两个或多个线程之间不会相互干扰。例如，两个航空公司都试图为不同的顾客抢购飞机上的最后一个座位。
  • 第三个问题是数据的先后顺序的问题，如果进程 A 产生数据并且进程 B 打印数据。则进程 B 打印数据之前需要先等 A 产生数据后才能够进行打印。

需要注意的是，这三个问题中的后面两个问题同样也适用于线程

第一个问题在线程间比较好解决，因为它们共享一个地址空间，它们具有相同的运行时环境，可以想象你在用高级语言编写多线程代码的过程中，线程通信问题是不是比较容易解决？

另外两个问题也同样适用于线程，同样的问题可用同样的方法来解决。我们后面会慢慢讨论这三个问题，你现在脑子中大致有个印象即可。

竞态条件

在一些操作系统中，协作的进程可能共享一些彼此都能读写的公共资源。公共资源可能在内存中也可能在一个共享文件。为了讲清楚进程间是如何通信的，这里我们举一个例子：一个后台打印程序。当一个进程需要打印某个文件时，它会将文件名放在一个特殊的后台目录(spooler directory)中。另一个进程 打印后台进程(printer daemon) 会定期的检查是否需要文件被打印，如果有的话，就打印并将该文件名从目录下删除。

假设我们的后台目录有非常多的 槽位(slot)，编号依次为 0，1，2，…，每个槽位存放一个文件名。同时假设有两个共享变量：out，指向下一个需要打印的文件；in，指向目录中下个空闲的槽位。可以把这两个文件保存在一个所有进程都能访问的文件中，该文件的长度为两个字。在某一时刻，0 至 3 号槽位空，4 号至 6 号槽位被占用。在同一时刻，进程 A 和 进程 B 都决定将一个文件排队打印，情况如下

墨菲法则(Murphy) 中说过，任何可能出错的地方终将出错，这句话生效时，可能发生如下情况。

进程 A 读到 in 的值为 7，将 7 存在一个局部变量 next_free_slot 中。此时发生一次时钟中断，CPU 认为进程 A 已经运行了足够长的时间，决定切换到进程 B 。进程 B 也读取 in 的值，发现是 7，然后进程 B 将 7 写入到自己的局部变量 next_free_slot 中，在这一时刻两个进程都认为下一个可用槽位是 7 。

进程 B 现在继续运行，它会将打印文件名写入到 slot 7 中，然后把 in 的指针更改为 8 ，然后进程 B 离开去做其他的事情

现在进程 A 开始恢复运行，由于进程 A 通过检查 next_free_slot也发现 slot 7 的槽位是空的，于是将打印文件名存入 slot 7 中，然后把 in 的值更新为 8 ，由于 slot 7 这个槽位中已经有进程 B 写入的值，所以进程 A 的打印文件名会把进程 B 的文件覆盖，由于打印机内部是无法发现是哪个进程更新的，它的功能比较局限，所以这时候进程 B 永远无法打印输出，类似这种情况，即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)。调试竞态条件是一种非常困难的工作，因为绝大多数情况下程序运行良好，但在极少数的情况下会发生一些无法解释的奇怪现象

互斥的概念

上面展示的情况称为竞争条件（race condition），当多线程相互竞争操作共享变量时，由于运气不好，即在执行过程中发生了上下文切换，我们得到了错误的结果，事实上，每次运行都可能得到不同的结果，因此输出的结果存在不确定性（indeterminate）。

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。我们希望这段代码是互斥（mutualexclusion）的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程。

另外，说一下互斥也并不是只针对多线程。在多进程竞争共享资源的时候，也同样是可以使用互斥的方式来避免资源竞争造成的资源混乱。

同步的概念

互斥解决了并发进程/线程对临界区的使用问题。这种基于临界区控制的交互作用是比较简单的，只要一个进程/线程进入了临界区，其他试图想进入临界区的进程/线程都会被阻塞着，直到第一个进程/线程离开了临界区。我们都知道在多线程里，每个线程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个线程能密切合作，以实现一个共同的任务。

例子，线程 1 是负责读入数据的，而线程 2 是负责处理数据的，这两个线程是相互合作、相互依赖的。线程 2 在没有收到线程 1 的唤醒通知时，就会一直阻塞等待，当线程 1 读完数据需要把数据传给线程 2 时，线程 1 会唤醒线程 2，并把数据交给线程 2 处理。

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

举个生活的同步例子，你肚子饿了想要吃饭，你叫妈妈早点做菜，妈妈听到后就开始做菜，但是在妈妈没有做完饭之前，你必须阻塞等待，等妈妈做完饭后，自然会通知你，接着你吃饭的事情就可以进行了。

注意，同步与互斥是两种不同的概念：

  • 同步就好比：「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都完成之后才能执行」等
  • 互斥就好比：「操作 A 和操作 B 不能在同一时刻执行」

同步方式

锁

使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

忙等待锁

在说明「忙等待锁」的实现之前，先介绍现代 CPU 体系结构提供的特殊原子操作指令 —— 测试和置位（*Test-and-Set*）指令。

如果用 C 代码表示 Test-and-Set 指令，形式如下：

测试并设置指令做了下述事情:

  • 把 old_ptr 更新为 new 的新值
  • 返回 old_ptr 的旧值；

当然，关键是这些代码是原子执行。因为既可以测试旧值，又可以设置新值，所以我们把这条指令叫作「测试并设置」。

那什么是原子操作呢？原子操作就是要么全部执行，要么都不执行，不能出现执行到一半的中间状态

我们可以运用 Test-and-Set 指令来实现「忙等待锁」，代码如下：

我们来确保理解为什么这个锁能工作：

  • 第一个场景是，首先假设一个线程在运行，调用 lock()，没有其他线程持有锁，所以 flag 是 0。当调用 TestAndSet(flag, 1) 方法，返回 0，线程会跳出 while 循环，获取锁。同时也会原子的设置 flag 为1，标志锁已经被持有。当线程离开临界区，调用 unlock() 将 flag 清理为 0。
  • 第二种场景是，当某一个线程已经持有锁（即 flag 为1）。本线程调用 lock()，然后调用 TestAndSet(flag, 1)，这一次返回 1。只要另一个线程一直持有锁，TestAndSet() 会重复返回 1，本线程会一直忙等。当 flag 终于被改为 0，本线程会调用 TestAndSet()，返回 0 并且原子地设置为 1，从而获得锁，进入临界区。

很明显，当获取不到锁时，线程就会一直 while 循环，不做任何事情，所以就被称为「忙等待锁」，也被称为自旋锁（*spin lock*）。

这是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

无等待锁

无等待锁是不自旋的锁，但是还是会进入队列进行等待

无等待锁顾明思议就是获取不到锁的时候，不用自旋。既然不想自旋，那当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。

本次只是提出了两种简单锁的实现方式。当然，在具体操作系统实现中，会更复杂，但也离不开本例子两个基本元素。

信号量

P是阻塞，相减

V是唤醒，相加

信号量是操作系统提供的一种协调共享资源访问的方法。

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。

另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：

  • P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
  • V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

P 操作是用在进入临界区之前，V 操作是用在离开临界区之后，这两个操作是必须成对出现的。

举个类比，2 个资源的信号量，相当于 2 条火车轨道，PV 操作如下图过程：

PV 操作

信号量数据结构与 PV 操作的算法描述如下图：

PV 操作的函数是由操作系统管理和实现的，所以操作系统已经使得执行 PV 函数时是具有原子性的。

PV 使用

信号量不仅可以实现临界区的互斥访问控制，还可以线程间的事件同步。

我们先来说说如何使用信号量实现临界区的互斥访问：

  • 为每类共享资源设置一个信号量 s，其初值为 1，表示该临界资源未被占用。

  • 只要把进入临界区的操作置于 P(s) 和 V(s) 之间，即可实现进程/线程互斥：

此时，任何想进入临界区的线程，必先在互斥信号量上执行 P 操作，在完成对临界资源的访问后再执行 V 操作。由于互斥信号量的初始值为 1，故在第一个线程执行 P 操作后 s 值变为 0，表示临界资源为空闲，可分配给该线程，使之进入临界区。若此时又有第二个线程想进入临界区，也应先执行 P 操作，结果使 s 变为负值，这就意味着临界资源已被占用，因此，第二个线程被阻塞。

并且，直到第一个线程执行 V 操作，释放临界资源而恢复 s 值为 0 后，才唤醒第二个线程，使之进入临界区，待它完成临界资源的访问后，又执行 V 操作，使 s 恢复到初始值 1。

对于两个并发线程，互斥信号量的值仅取 1、0 和 -1 三个值，分别表示：

  • 如果互斥信号量为 1，表示没有线程进入临界区；
  • 如果互斥信号量为 0，表示有一个线程进入临界区；
  • 如果互斥信号量为 -1，表示一个线程进入临界区，另一个线程等待进入。

通过互斥信号量的方式，就能保证临界区任何时刻只有一个线程在执行，就达到了互斥的效果。

再来，我们说说如何使用信号量实现事件同步。

同步的方式是设置一个信号量，其初值为 0。

我们把前面的「吃饭-做饭」同步的例子，用代码的方式实现一下：

妈妈一开始询问儿子要不要做饭时，执行的是 P(s1) ，相当于询问儿子需不需要吃饭，由于 s1 初始值为 0，此时 s1 变成 -1，表明儿子不需要吃饭，所以妈妈线程就进入等待状态。

当儿子肚子饿时，执行了 V(s1)，使得 s1 信号量从 -1 变成 0，表明此时儿子需要吃饭了，于是就唤醒了阻塞中的妈妈线程，妈妈线程就开始做饭。

接着，儿子线程执行了 P(s2)，相当于询问妈妈饭做完了吗，由于 s2 初始值是 0，则此时 s2 变成 -1，说明妈妈还没做完饭，儿子线程就等待状态。

最后，妈妈终于做完饭了，于是执行 V(s2)，s2 信号量从 -1 变回了 0，于是就唤醒等待中的儿子线程，唤醒后，儿子线程就可以进行吃饭了。

经典同步问题*

生产-消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。 用PV操作实现上述过程

生产者-消费者问题描述：

  • 生产者在生成数据后，放在一个缓冲区中；
  • 消费者从缓冲区取出数据处理；
  • 任何时刻，只能有一个生产者或消费者可以访问缓冲区；

我们对问题分析可以得出：

  • 任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，需要互斥；
  • 缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者需要同步。

那么我们需要三个信号量，分别是：

  • 互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；
  • 资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；
  • 资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；

具体的实现代码：

如果消费者线程一开始执行 P(fullBuffers)，由于信号量 fullBuffers 初始值为 0，则此时 fullBuffers 的值从 0 变为 -1，说明缓冲区里没有数据，消费者只能等待。

接着，轮到生产者执行 P(emptyBuffers)，表示减少 1 个空槽，如果当前没有其他生产者线程在临界区执行代码，那么该生产者线程就可以把数据放到缓冲区，放完后，执行 V(fullBuffers) ，信号量 fullBuffers 从 -1 变成 0，表明有「消费者」线程正在阻塞等待数据，于是阻塞等待的消费者线程会被唤醒。

消费者线程被唤醒后，如果此时没有其他消费者线程在读数据，那么就可以直接进入临界区，从缓冲区读取数据。最后，离开临界区后，把空槽的个数 + 1。

读者-写者问题

「哲学家进餐问题」对于互斥访问有限的竞争问题（如 I/O 设备）一类的建模过程十分有用。另外，还有个著名的问题是「读者-写者」，它为数据库访问建立了一个模型。读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。

读者-写者的问题描述：

  • 「读-读」允许：同一时刻，允许多个读者同时读
  • 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
  • 「写-写」互斥：没有其他写者时，写者才能写

接下来，提出几个解决方案来分析分析。

方案一

使用信号量的方式来尝试解决：

  • 信号量 wMutex：控制写操作的互斥信号量，初始值为 1 ；
  • 读者计数 rCount：正在进行读操作的读者个数，初始化为 0；
  • 信号量 rCountMutex：控制对 rCount 读者计数器的互斥修改，初始值为 1；

接下来看看代码的实现：

上面的这种实现，是读者优先的策略，因为只要有读者正在读的状态，后来的读者都可以直接进入，如果读者持续不断进入，则写者会处于饥饿状态。

方案二

那既然有读者优先策略，自然也有写者优先策略：

  • 只要有写者准备要写入，写者应尽快执行写操作，后来的读者就必须阻塞；
  • 如果有写者持续不断写入，则读者就处于饥饿；

在方案一的基础上新增如下变量：

  • 信号量 rMutex：控制读者进入的互斥信号量，初始值为 1；
  • 信号量 wDataMutex：控制写者写操作的互斥信号量，初始值为 1；
  • 写者计数 wCount：记录写者数量，初始值为 0；
  • 信号量 wCountMutex：控制 wCount 互斥修改，初始值为 1；

具体实现如下代码：

注意，这里 rMutex 的作用，开始有多个读者读数据，它们全部进入读者队列，此时来了一个写者，执行了 P(rMutex) 之后，后续的读者由于阻塞在 rMutex 上，都不能再进入读者队列，而写者到来，则可以全部进入写者队列，因此保证了写者优先。

同时，第一个写者执行了 P(rMutex) 之后，也不能马上开始写，必须等到所有进入读者队列的读者都执行完读操作，通过 V(wDataMutex) 唤醒写者的写操作。

方案三

既然读者优先策略和写者优先策略都会造成饥饿的现象，那么我们就来实现一下公平策略。

公平策略：

  • 优先级相同；
  • 写者、读者互斥访问；
  • 只能一个写者访问临界区；
  • 可以有多个读者同时访问临界资源；

具体代码实现：

对比方案一的读者优先策略，可以发现，读者优先中只要后续有读者到达，读者就可以进入读者队列， 而写者必须等待，直到没有读者到达。

没有读者到达会导致读者队列为空，即 rCount==0，此时写者才可以进入临界区执行写操作。

而这里 flag 的作用就是阻止读者的这种特殊权限（特殊权限是只要读者到达，就可以进入读者队列）。

比如：开始来了一些读者读数据，它们全部进入读者队列，此时来了一个写者，执行 P(falg) 操作，使得后续到来的读者都阻塞在 flag 上，不能进入读者队列，这会使得读者队列逐渐为空，即 rCount 减为 0。

这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列中的读者全部读取结束后，最后一个读者进程执行 V(wDataMutex)，唤醒刚才的写者，写者则继续开始进行写操作。

哲学家-进餐问题

先来看看哲学家就餐的问题描述：

  • 5 个老大哥哲学家，闲着没事做，围绕着一张圆桌吃面；
  • 巧就巧在，这个桌子只有 5 支叉子，每两个哲学家之间放一支叉子；
  • 哲学家围在一起先思考，思考中途饿了就会想进餐；
  • 奇葩的是，这些哲学家要两支叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐；
  • 吃完后，会把两支叉子放回原处，继续思考；

那么问题来了，如何保证哲学家们的动作有序进行，而不会出现有人永远拿不到叉子呢？

方案一

上面的程序，好似很自然。拿起叉子用 P 操作，代表有叉子就直接用，没有叉子时就等待其他哲学家放回叉子。

不过，这种解法存在一个极端的问题：假设五位哲学家同时拿起左边的叉子，桌面上就没有叉子了， 这样就没有人能够拿到他们右边的叉子，也就说每一位哲学家都会在 P(fork[(i + 1) % N ]) 这条语句阻塞了，很明显这发生了死锁的现象。

方案二

既然「方案一」会发生同时竞争左边叉子导致死锁的现象，那么我们就在拿叉子前，加个互斥信号量，代码如下：

上面程序中的互斥信号量的作用就在于，只要有一个哲学家进入了「临界区」，也就是准备要拿叉子时，其他哲学家都不能动，只有这位哲学家用完叉子了，才能轮到下一个哲学家进餐。

方案二虽然能让哲学家们按顺序吃饭，但是每次进餐只能有一位哲学家，而桌面上是有 5 把叉子，按道理是能可以有两个哲学家同时进餐的，所以从效率角度上，这不是最好的解决方案。

方案三

那既然方案二使用互斥信号量，会导致只能允许一个哲学家就餐，那么我们就不用它。

另外，方案一的问题在于，会出现所有哲学家同时拿左边刀叉的可能性，那我们就避免哲学家可以同时拿左边的刀叉，采用分支结构，根据哲学家的编号的不同，而采取不同的动作。

即让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。

上面的程序，在 P 操作时，根据哲学家的编号不同，拿起左右两边叉子的顺序不同。另外，V 操作是不需要分支的，因为 V 操作是不会阻塞的。

方案三即不会出现死锁，也可以两人同时进餐。

方案四

在这里再提出另外一种可行的解决方案，我们用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。

那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。

第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：

  • LEFT : ( i + 5 - 1 ) % 5
  • RIGHT : ( i + 1 ) % 5

比如 i 为 2，则 LEFT 为 1，RIGHT 为 3。

具体代码实现如下：

上面的程序使用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。

注意，每个进程/线程将 smart_person 函数作为主代码运行，而其他 take_forks、put_forks 和 test 只是普通的函数，而非单独的进程/线程。

方案四同样不会出现死锁，也可以两人同时进餐。

死锁*

多线程产生的问题

如果要对死锁进行一个定义的话，下面的定义比较贴切

如果一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，这种情况会导致死锁。简单一点来表述一下，就是每个进程都在等待其他进程释放资源，而其他资源也在等待每个进程释放资源，这样没有进程抢先释放自己的资源，这种情况会产生死锁，所有进程都会无限的等待下去。

换句话说，死锁进程结合中的每个进程都在等待另一个死锁进程已经占有的资源。但是由于所有进程都不能运行，它们之中任何一个资源都无法释放资源，所以没有一个进程可以被唤醒。这种死锁也被称为资源死锁(resource deadlock)。资源死锁是最常见的类型，但不是所有的类型，我们后面会介绍其他类型，我们先来介绍资源死锁

资源死锁的条件

针对我们上面的描述，资源死锁可能出现的情况主要有

  • 互斥条件：每个资源都被分配给了一个进程或者资源是可用的
  • 保持和等待条件：已经获取资源的进程被认为能够获取新的资源
  • 不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显示释放
  • 循环等待：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源。

发生死锁时，上面的情况必须同时会发生。如果其中任意一个条件不会成立，死锁就不会发生。可以通过破坏其中任意一个条件来破坏死锁，下面这些破坏条件就是我们探讨的重点

死锁模型

Holt 在 1972 年提出对死锁进行建模，建模的标准如下：

  • 圆形表示进程
  • 方形表示资源

从资源节点到进程节点表示资源已经被进程占用，如下图所示

在上图中表示当前资源 R 正在被 A 进程所占用，由进程节点到资源节点的有向图表示当前进程正在请求资源，并且该进程已经被阻塞，处于等待这个资源的状态

在上图中，表示的含义是进程 B 正在请求资源 S 。Holt 认为，死锁的描述应该如下

这是一个死锁的过程，进程 C 等待资源 T 的释放，资源 T 却已经被进程 D 占用，进程 D 等待请求占用资源 U ，资源 U 却已经被线程 C 占用，从而形成环。

总结一点：吃着碗里的看着锅里的容易死锁

那么如何避免死锁呢？我们还是通过死锁模型来聊一聊

假设有三个进程 (A、B、C) 和三个资源(R、S、T) 。三个进程对资源的请求和释放序列如下图所示

操作系统可以任意选择一个非阻塞的程序运行，所以它可以决定运行 A 直到 A 完成工作；它可以运行 B 直到 B 完成工作；最后运行 C。

这样的顺序不会导致死锁（因为不存在对资源的竞争），但是这种情况也完全没有并行性。进程除了在请求和释放资源外，还要做计算和输入/输出的工作。当进程按照顺序运行时，在等待一个 I/O 时，另一个进程不能使用 CPU。所以，严格按照串行的顺序执行并不是最优越的。另一方面，如果没有进程在执行任何 I/O 操作，那么最短路径优先作业会优于轮转调度，所以在这种情况下串行可能是最优越的

现在我们假设进程会执行计算和 I/O 操作，所以轮询调度是一种合理的调度算法。资源请求可能会按照下面这个顺序进行

下图是针对上面这六个步骤的资源分配图。

这里需要注意一个问题，为什么从资源出来的有向图指向了进程却表示进程请求资源呢？刚开始看也有这个疑问，但是想了一下这个意思解释为进程占用资源比较合适，而进程的有向图指向资源表示进程被阻塞的意思。

在上面的第四个步骤，进程 A 正在等待资源 S；第五个步骤中，进程 B 在等待资源 T；第六个步骤中，进程 C 在等待资源 R，因此产生了环路并导致了死锁。

然而，操作系统并没有规定一定按照某种特定的顺序来执行这些进程。遇到一个可能会引起死锁的线程后，操作系统可以干脆不批准请求，并把进程挂起一直到安全状态为止。比如上图中，如果操作系统认为有死锁的可能，它可以选择不把资源 S 分配给 B ，这样 B 被挂起。这样的话操作系统会只运行 A 和 C，那么资源的请求和释放就会是下面的步骤

下图是针对上面这六个步骤的资源分配图。

在第六步执行完成后，可以发现并没有产生死锁，此时就可以把资源 S 分配给 B，因为 A 进程已经执行完毕，C 进程已经拿到了它想要的资源。进程 B 可以直接获得资源 S，也可以等待进程 C 释放资源 T 。

有四种处理死锁的策略：

  • 忽略死锁带来的影响（惊呆了）
  • 检测死锁并回复死锁，死锁发生时对其进行检测，一旦发生死锁后，采取行动解决问题
  • 通过仔细分配资源来避免死锁
  • 通过破坏死锁产生的四个条件之一来避免死锁

下面我们分别介绍一下这四种方法

解决死锁

鸵鸟算法

最简单的解决办法就是使用鸵鸟算法(ostrich algorithm)，把头埋在沙子里，假装问题根本没有发生。每个人看待这个问题的反应都不同。数学家认为死锁是不可接受的，必须通过有效的策略来防止死锁的产生。工程师想要知道问题发生的频次，系统因为其他原因崩溃的次数和死锁带来的严重后果。如果死锁发生的频次很低，而经常会由于硬件故障、编译器错误等其他操作系统问题导致系统崩溃，那么大多数工程师不会修复死锁。

死锁检测和恢复*

第二种技术是死锁的检测和恢复。这种解决方式不会尝试去阻止死锁的出现。相反，这种解决方案会希望死锁尽可能的出现，在监测到死锁出现后，对其进行恢复。下面我们就来探讨一下死锁的检测和恢复的几种方式

每种类型一个资源的死锁检测方式

每种资源类型都有一个资源是什么意思？我们经常提到的打印机就是这样的，资源只有打印机，但是设备都不会超过一个。

可以通过构造一张资源分配表来检测这种错误，比如我们上面提到的

的算法来检测从 P1 到 Pn 这 n 个进程中的死锁。假设资源类型为 m，E1 代表资源类型1，E2 表示资源类型 2 ，Ei 代表资源类型 i (1 <= i <= m)。E 表示的是 现有资源向量(existing resource vector)，代表每种已存在的资源总数。

现在我们就需要构造两个数组：C 表示的是当前分配矩阵(current allocation matrix) ，R 表示的是 请求矩阵(request matrix)。Ci 表示的是 Pi 持有每一种类型资源的资源数。所以，Cij 表示 Pi 持有资源 j 的数量。Rij 表示 Pi 所需要获得的资源 j 的数量

一般来说，已分配资源 j 的数量加起来再和所有可供使用的资源数相加 = 该类资源的总数。

死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的，算法会开始对进程做标记，进程被标记后说明进程被执行了，不会进入死锁，当算法结束时，任何没有被标记过的进程都会被判定为死锁进程。

上面我们探讨了两种检测死锁的方式，那么现在你知道怎么检测后，你何时去做死锁检测呢？一般来说，有两个考量标准：

  • 每当有资源请求时就去检测，这种方式会占用昂贵的 CPU 时间。
  • 每隔 k 分钟检测一次，或者当 CPU 使用率降低到某个标准下去检测。考虑到 CPU 效率的原因，如果死锁进程达到一定数量，就没有多少进程可以运行，所以 CPU 会经常空闲。
银行家算法*

银行家算法是Dijkstra在 1965 年提出的一种调度算法，它本身是一种死锁的调度算法。它的模型是基于一个城镇中的银行家，银行家向城镇中的客户承诺了一定数量的贷款额度。算法要做的就是判断请求是否会进入一种不安全的状态。如果是，就拒绝请求，如果请求后系统是安全的，就接受该请求。

比如下面的例子，银行家一共为所有城镇居民提供了 15 单位个贷款额度，一个单位表示 1k 美元，如下所示

城镇居民都喜欢做生意，所以就会涉及到贷款，每个人能贷款的最大额度不一样，在某一时刻，A/B/C/D 的贷款金额如下

上面每个人的贷款总额加起来是 13，马上接近 15，银行家只能给 A 和 C 进行放贷，可以拖着 B 和 D、所以，可以让 A 和 C 首先完成，释放贷款额度，以此来满足其他居民的贷款。这是一种安全的状态。如果每个人的请求导致总额会超过甚至接近 15 ，就会处于一种不安全的状态，如下所示

这样，每个人还能贷款至少 2 个单位的额度，如果其中有一个人发起最大额度的贷款请求，就会使系统处于一种死锁状态。

这里注意一点：不安全状态并不一定引起死锁，由于客户不一定需要其最大的贷款额度，但是银行家不敢抱着这种侥幸心理。

银行家算法就是对每个请求进行检查，检查是否请求会引起不安全状态，如果不会引起，那么就接受该请求；如果会引起，那么就推迟该请求。

破坏死锁

在多线程编其他问题程中，我们为了防止多线程竞争共享资源而导致数据错乱，都会在操作共享资源之前加上互斥锁，只有成功获得到锁的线程，才能操作共享资源，获取不到锁的线程就只能等待，直到锁被释放。

那么，当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，那么这两个互斥锁应用不当的时候，可能会造成两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了死锁。

举个例子，小林拿了小美房间的钥匙，而小林在自己的房间里，小美拿了小林房间的钥匙，而小美也在自己的房间里。如果小林要从自己的房间里出去，必须拿到小美手中的钥匙，但是小美要出去，又必须拿到小林手中的钥匙，这就形成了死锁。

死锁只有同时满足以下四个条件才会发生：

  • 互斥条件；
  • 持有并等待条件；
  • 不可剥夺条件；
  • 环路等待条件；
互斥条件

互斥条件是指多个线程不能同时使用同一个资源。

比如下图，如果线程 A 已经持有的资源，不能再同时被线程 B 持有，如果线程 B 请求获取线程 A 已经占用的资源，那线程 B 只能等待，直到线程 A 释放了资源。

持有并等待条件

持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。

不可剥夺条件

不可剥夺条件是指，当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。

环路等待条件

环路等待条件指的是，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。

比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，而想请求资源 2，这就形成资源请求等待的环形图。

简单来说，死锁问题的产生是由两个或者以上线程并行执行的时候，争夺资源而互相等待造成的。死锁只有同时满足互斥、持有并等待、不可剥夺、环路等待这四个条件的时候才会发生。**所以要避免死锁问题，就是要破坏其中一个条件即可，最常用的方法就是使用资源有序分配法来破坏环路等待条件**。

CPU调度*

处理机也叫做CPU，也就是处理机调度

进程都希望自己能够占用 CPU 进行工作，那么这涉及到前面说过的进程上下文切换。一旦操作系统把进程切换到运行状态，也就意味着该进程占用着 CPU 在执行，但是当操作系统把进程切换到其他状态时，那就不能在 CPU 中执行了，于是操作系统会选择下一个要运行的进程。

选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序（这里的进程指只有主线程的进程，所以调度主线程就等于调度了整个进程）。那到底什么时候调度进程，或以什么原则来调度进程呢？

调度时机

决定哪个进程或线程可以在何时运行的机制

在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。

比如，以下状态的变化都会触发操作系统的调度：

  • 从就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行
  • 从运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行
  • 从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行

因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给 CPU 运行，或者是否让当前进程从 CPU 上退出来而换另一个进程运行。

另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：

  • 非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
  • 抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。

调度原则

原则一：如果运行的程序，发生了 I/O 事件的请求，那 CPU 使用率必然会很低，因为此时进程在阻塞等待硬盘的数据返回。这样的过程，势必会造成 CPU 突然的空闲。所以，为了提高 CPU 利用率，在这种发送 I/O 事件致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。

原则二：有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着 CPU，会造成系统吞吐量（CPU 在单位时间内完成的进程数量）的降低。所以，要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。

原则三：从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间。进程的周转时间越小越好，如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。

原则四：处于就绪队列的进程，也不能等太久，当然希望这个等待的时间越短越好，这样可以使得进程更快的在 CPU 中执行。所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则。

原则五：对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则就会影响用户体验了。所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。

针对上面的五种调度原则，总结成如下：

  • CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
  • 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
  • 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
  • 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
  • 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

说白了，这么多调度原则，目的就是要使得进程要「快」。

CPU调度类型

作业调度

高级调度负责将作业从外存（辅存）调入内存。由于内存空间有限，不能将所有作业一次性加载进内存，因此需要按照一定的规则来决定哪些作业应优先加载。

  • 从外存中的后备队列中挑选作业，将其加载到内存。
  • 为每个作业分配内存和其他必要资源，并建立进程控制块（PCB）。
  • 作业调入时会创建PCB，作业完成后会销毁PCB。

关注点：主要关注如何将作业调入内存。调出操作由作业运行结束触发。

内存调度

中级调度决定哪些处于挂起状态的进程需要被重新调入内存。调度的频率高于高级调度，因为一个进程可能被多次调入和调出内存。

  • 引入虚拟存储技术后，可以将暂时无法运行的进程转移至外存，待内存有空闲时再调入内存。
  • 被挂起的进程状态记录在内存中的PCB中，PCB本身不会被调出内存。PCB包含进程在外存中的位置及状态等信息。
  • 操作系统通过内存中的PCB管理挂起队列，维护对进程的监控和管理。
进程调度

低级调度负责从就绪队列中选择一个进程，并将处理器分配给它。是操作系统中最基本的调度类型。

  • 根据调度策略选择一个就绪进程，分配CPU资源。
  • 进程调度的频率很高，一般在几十毫秒内发生一次。

关注点：确保系统中的处理器资源得到有效利用，通过合理的调度策略来优化系统性能。

典型调度算法

不同的调度算法适用的场景也是不同的。接下来，说说在单核 CPU 系统中常见的调度算法。

先来先服务调度算法(FCFS)

最简单的一个调度算法，就是非抢占式的先来先服务（First Come First Serve, FCFS）算法了。

顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

短作业有限调度算法(SJF)

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

高响应比有限调度算法(HRRN)

前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。那么，高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。

每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：

从上面的公式，可以发现：

  • 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行；
  • 如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；
时间片轮调度算法(RR)

最古老、最简单、最公平且使用最广的算法就是时间片轮转（*Round Robin, RR*）调度算法。

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

  • 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程；
  • 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

另外，时间片的长度就是一个很关键的点：

  • 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
  • 如果设得太长又可能引起对短作业进程的响应时间变长。

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。

优先级调度算法(PAS)

前面的「时间片轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。

但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。

进程的优先级可以分为，静态优先级和动态优先级：

  • 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
  • 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

  • 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
  • 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列调度算法(MFQ)

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

顾名思义：

  • 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
  • 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

来看看，它是如何工作的：

  • 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
  • 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
  • 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

举例说明调度算法

办理业务的客户相当于进程，银行窗口工作人员相当于 CPU。

现在，假设这个银行只有一个窗口（单核 CPU ），那么工作人员一次只能处理一个业务。

那么最简单的处理方式，就是先来的先处理，后面来的就乖乖排队，这就是先来先服务（FCFS）调度算法。但是万一先来的这位老哥是来贷款的，这一谈就好几个小时，一直占用着窗口，这样后面的人只能干等，或许后面的人只是想简单的取个钱，几分钟就能搞定，却因为前面老哥办长业务而要等几个小时，你说气不气人？

有客户抱怨了，那我们就要改进，我们干脆优先给那些几分钟就能搞定的人办理业务，这就是短作业优先（SJF）调度算法。听起来不错，但是依然还是有个极端情况，万一办理短业务的人非常的多，这会导致长业务的人一直得不到服务，万一这个长业务是个大客户，那不就捡了芝麻丢了西瓜

那就公平起见，现在窗口工作人员规定，每个人我只处理 10 分钟。如果 10 分钟之内处理完，就马上换下一个人。如果没处理完，依然换下一个人，但是客户自己得记住办理到哪个步骤了。这个也就是时间片轮转（RR）调度算法。但是如果时间片设置过短，那么就会造成大量的上下文切换，增大了系统开销。如果时间片过长，相当于退化成 FCFS(先来先服务) 算法了。

既然公平也可能存在问题，那银行就对客户分等级，分为普通客户、VIP 客户、SVIP 客户。只要高优先级的客户一来，就第一时间处理这个客户，这就是最高优先级（HPF）调度算法。但依然也会有极端的问题，万一当天来的全是高级客户，那普通客户不是没有被服务的机会，不把普通客户当人是吗？那我们把优先级改成动态的，如果客户办理业务时间增加，则降低其优先级，如果客户等待时间增加，则升高其优先级。

那有没有兼顾到公平和效率的方式呢？这里介绍一种算法，考虑的还算充分的，多级反馈队列（MFQ）调度算法，它是时间片轮转算法和优先级算法的综合和发展。它的工作方式：

用多个队列实现的。

  • 银行设置了多个排队（就绪）队列，每个队列都有不同的优先级，各个队列优先级从高到低，同时每个队列执行时间片的长度也不同，优先级越高的时间片越短。
  • 新客户（进程）来了，先进入第一级队列的末尾，按先来先服务原则排队等待被叫号（运行）。如果时间片用完客户的业务还没办理完成，则让客户进入到下一级队列的末尾，以此类推，直至客户业务办理完成。
  • 当第一级队列没人排队时，就会叫号二级队列的客户。如果客户办理业务过程中，有新的客户加入到较高优先级的队列，那么此时办理中的客户需要停止办理，回到原队列的末尾等待再次叫号，因为要把窗口让给刚进入较高优先级队列的客户。

可以发现，对于要办理短业务的客户来说，可以很快的轮到并解决。对于要办理长业务的客户，一下子解决不了，就可以放到下一个队列的末尾，虽然等待的时间稍微变长了，但是轮到自己的办理时间也变长了，也可以接受，不会造成极端的现象，可以说是综合上面几种算法的优点。

第三章 内存管理

在现代操作系统中，进程通常使用的是虚拟内存（Virtual Memory）而不是直接的物理内存。

虚拟内存

介绍虚拟内存之前，先介绍单片机。对于单片机来说，其中的地址都是直接物理地址。所以每次写完代码，都需要借助工具把程序烧录进去，这样程序才能跑起来。另外，单片机的 CPU 是直接操作内存的「物理地址」。

这种情况下，要想在内存中同时运行两个程序是无法达成的，因为每一次写入都会覆盖之前烧录进物理内存中的地址，运行两个程序会立马崩溃。于是操作系统使用了虚拟内存在解决这个问题

上述问题中，两个程序都直接引用了物理地址才导致了无法运行，这里需要解决这个问题。我们可以把进程所使用的地址隔离起来，使得操作系统为每一个进程独立分配一套虚拟地址，每一个进程都使用自己的地址，互不干涉。但是它们都不能直接访问物理地址，然后问题就来到了虚拟地址是怎么落到物理内存上的了。

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

于是，这里就引出了两种地址的概念：

  • 我们程序所使用的内存地址叫做虚拟内存地址
  • 实际存在硬件里面的空间地址叫物理内存地址

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存，如下图所示：

操作系统是如何管理虚拟地址与物理地址之间的关系？

主要有两种方式，分别是内存分段和内存分页，分段是比较早提出的，我们先来看看内存分段。

内存分段

分段的内存，大小不固定由具体的逻辑结构决定。

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。

分段机制下，虚拟地址和物理地址是如何映射的？

分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。

段选择因子和段内偏移量：

  • 段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
  • 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

在上面，知道了虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址

如果要访问段 3 中偏移量 500 的虚拟地址，我们可以计算出物理地址为，段 3 基地址 7000 + 偏移量 500 = 7500。

分段的办法很好，解决了程序本身不需要关心具体的物理内存地址的问题，但它也有一些不足之处：

  • 第一个就是内存碎片的问题。
  • 第二个就是内存交换的效率低的问题。

我们先来看看，分段为什么会产生内存碎片的问题？

我们来看看这样一个例子。假设有 1G 的物理内存，用户执行了多个程序，其中：

  • 游戏占用了 512MB 内存
  • 浏览器占用了 128MB 内存
  • 音乐占用了 256 MB 内存。

这个时候，如果我们关闭了浏览器，则空闲内存还有 1024 - 512 - 256 = 256MB。

如果这个 256MB 不是连续的，被分成了两段 128 MB 内存，这就会导致没有空间再打开一个 200MB 的程序。

内存分段会出现内存碎片吗？

内存碎片主要分为，内部内存碎片和外部内存碎片。

内存分段管理可以做到段根据实际需求分配内存，所以有多少需求就分配多大的段，所以不会出现内部内存碎片。但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。

解决「外部内存碎片」的问题就是内存交换。

可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。

这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。

分段为什么会导致内存交换效率低的问题？

对于多进程的系统来说，用分段的方式，外部内存碎片是很容易产生的，产生了外部内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。因为硬盘的访问速度要比内存慢太多了，每一次内存交换，我们都需要把一大段连续的内存数据写到硬盘上。

所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。为了解决内存分段的「外部内存碎片和内存交换效率低」的问题，就出现了内存分页。

内存分页

页表用于管理和映射虚拟地址与物理内存地址之间的对应关系

分段的好处就是能产生连续的内存空间，但是会出现「外部内存碎片和内存交换的空间太大」的问题。

要解决这些问题，那么就要想出能少出现一些内存碎片的办法。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点，这样就可以解决问题了。这个办法，也就是内存分页（Paging）。

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB。虚拟地址与物理地址之间通过页表来映射

页表是存储在内存里的，内存管理单元 （MMU）就做将虚拟内存地址转换成物理地址的工作。而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。

分页是怎么解决分段的「外部内存碎片和内存交换效率低」的问题？

内存分页由于内存空间都是预先划分好的，也就不会像内存分段一样，在段与段之间会产生间隙非常小的内存，这正是分段会产生外部内存碎片的原因。而采用了分页，页与页之间是紧密排列的，所以不会有外部碎片。

但是，因为内存分页机制分配内存的最小单位是一页，即使程序不足一页大小，我们最少只能分配一个页，所以页内会出现内存浪费，所以针对内存分页机制会有内部内存碎片的现象。

如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。

更进一步地，分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。

分页机制下，虚拟地址和物理地址是如何映射的？

在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址，见下图。

总结一下，对于一个内存地址转换，其实就是这样三个步骤：

  • 把虚拟内存地址，切分成页号和偏移量；
  • 根据页号，从页表里面，查询对应的物理页号；
  • 直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。

下面举个例子，虚拟内存中的页通过页表映射为了物理内存中的页，如下图：

简单的分页有什么缺陷吗？

有空间上的缺陷。因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。

这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64位的环境了。

多级页表

要解决上面的问题，就需要采用一种叫作多级页表（Multi-Level Page Table）的解决方案。

在前面我们知道了，对于单页表的实现方式，在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。

我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？

当然如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。

每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。

如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

那么为什么不分级的页表就做不到这样节约内存呢？

我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。

对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

  • 全局页目录项 PGD
  • 上层页目录项 PUD
  • 中间页目录项 PMD
  • 页表项 PTE

TLB(页表缓存)

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。

我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB ，通常称为页表缓存、转址旁路缓存、快表等。

在 CPU 芯片里面，封装了内存管理单元芯片，它用来完成地址转换和 TLB 的访问与交互。有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。

段页式内存管理*

内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理。

段页式内存管理实现的方式：

  • 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
  • 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；

这样，地址结构就由段号、段内页号和页内位移三部分组成。用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号，如图所示：

段表 -> 段页表 - >物理页号

段页式地址变换中要得到物理地址须经过三次内存访问：

  • 第一次访问段表，得到页表起始地址；
  • 第二次访问页表，得到物理页号；
  • 第三次将物理页号与页内位移组合，得到物理地址。

可用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率。

内存分配与回收

应用程序通过 malloc 函数申请内存的时候，实际上申请的是虚拟内存，此时并不会分配物理内存。

当应用程序读写了这块虚拟内存，CPU 就会去访问这个虚拟内存， 这时会发现这个虚拟内存没有映射到物理内存， CPU 就会产生缺页中断，进程会从用户态切换到内核态，并将缺页中断交给内核的 Page Fault Handler （缺页中断函数）处理。

缺页中断处理函数会看是否有空闲的物理内存，如果有就直接分配物理内存，并建立虚拟内存与物理内存之间的映射关系。如果没有空闲的物理内存，那么内核就会开始进行回收内存的工作，回收的方式主要是两种：直接内存回收和后台内存回收。

  • 后台内存回收（kswapd）：在物理内存紧张的时候，会唤醒 kswapd 内核线程来回收内存，这个回收内存的过程异步的，不会阻塞进程的执行。
  • 直接内存回收（direct reclaim）：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是同步的，会阻塞进程的执行。

如果直接内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会放最后的大招了 ——触发 OOM （Out of Memory）机制。

OOM Killer 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM Killer 会继续杀死占用物理内存较高的进程，直到释放足够的内存位置。

申请物理内存的过程如下图：

哪些内存可以被回收

系统内存紧张的时候，就会进行回收内存的工作，那具体哪些内存是可以被回收的呢？

主要有两类内存可以被回收，而且它们的回收方式也不同。

  • 文件页（File-backed Page）：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Cache）都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据（也就是脏页），就得先写入磁盘，然后才能进行内存释放。所以，回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存。
  • 匿名页（Anonymous Page）：这部分内存没有实际载体，不像文件缓存有硬盘文件这样一个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们回收的方式是通过 Linux 的 Swap 机制，Swap 会把不常访问的内存先写到磁盘中，然后释放这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。

文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。LRU 回收算法，实际上维护着 active 和 inactive 两个双向链表，其中：

  • active_list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；
  • inactive_list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

越接近链表尾部，就表示内存页越不常访问。这样，在回收内存时，系统就可以根据活跃程度，优先回收不活跃的内存。

活跃和非活跃的内存页，按照类型的不同，又分别分为文件页和匿名页。可以从 /proc/meminfo 中，查询它们的大小，比如：

1
2
3
4
5
6
7
8
9
# grep表示只保留包含active的指标（忽略大小写）
# sort表示按照字母顺序排序
[root@xiaolin ~]# cat /proc/meminfo | grep -i active | sort
Active:           901456 kB
Active(anon):     227252 kB
Active(file):     674204 kB
Inactive:         226232 kB
Inactive(anon):    41948 kB
Inactive(file):   184284 kB

回收内存带来的性能影响

在前面我们知道了回收内存有两种方式。

  • 一种是后台内存回收，也就是唤醒 kswapd 内核线程，这种方式是异步回收的，不会阻塞进程。
  • 一种是直接内存回收，这种方式是同步回收的，会阻塞进程，这样就会造成很长时间的延迟，以及系统的 CPU 利用率会升高，最终引起系统负荷飙高。

可被回收的内存类型有文件页和匿名页：

  • 文件页的回收：对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先写回到磁盘再释放内存，这个操作会发生磁盘 I/O 的，这个操作是会影响系统性能的。
  • 匿名页的回收：如果开启了 Swap 机制，那么 Swap 机制会将不常访问的匿名页换出到磁盘中，下次访问时，再从磁盘换入到内存中，这个操作是会影响系统性能的。

可以看到，回收内存的操作基本都会发生磁盘 I/O 的，如果回收内存的操作很频繁，意味着磁盘 I/O 次数会很多，这个过程势必会影响系统的性能，整个系统给人的感觉就是很卡。

内存页面置换算法

置换的目的是把正在物理内存运行的页，换为硬盘中未执行的页。主要目的是在物理内存不足时有效地管理内存页面，确保系统能够尽可能高效地利用有限的内存资源。

内存页面是用于映射虚拟内存到物理内存的基本单位。每个内存页面代表虚拟地址空间中的一个固定大小的块，并映射到物理内存中的一个页面框。每一个进程都由一个独一的内存页面。内存页面置换的主要目的是在物理内存不足时，动态管理虚拟内存的使用，从而确保系统能够高效地运行多个进程。当物理内存不够时，操作系统将不活跃的页面从物理内存移到磁盘的交换空间，以释放物理内存，然后将需要的页面加载到物理内存中。

这里需要补充一点，缺页异常会常常出现在内存页面置换的场景之中，其中分为两类：

  • 合法缺页异常：当一个程序访问它的虚拟地址空间中合法的、但尚未加载到内存的页面时发生的缺页异常。操作系统将该页面加载到内存，程序继续执行。
  • 非法缺页异常：当程序试图访问不在其虚拟地址空间中的页面（例如，未分配的内存或只读页面被写入）时发生的缺页异常。操作系统通常会终止该程序。

最佳置换算法(OPT)*

最佳页面置换算法的基本思路是，置换在未来最长时间不访问的页面该算法需要计算内存中每一个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面

假设一开始有 3 个空闲的物理页，然后有请求的页面序列，那它的置换过程如下图：

在这个请求的页面序列中，缺页共发生了 7 次（空闲页换入 3 次 + 最优页面置换 4 次），页面置换共发生了 4 次。这很理想，但是实际系统中无法实现，因为程序访问页面时是动态的，我们是无法预知每个页面在「下一次」访问前的等待时间。所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。

先进先出算法(FIFO)

既然我们无法预知页面在下一次访问前所需的等待时间，那我们可以选择在内存驻留时间很长的页面进行中置换，这个就是「先进先出置换」算法的思想。还是以前面的请求的页面序列作为例子，假设使用先进先出置换算法，则过程如下图：

在这个请求的页面序列中，缺页共发生了 10 次，页面置换共发生了 7 次，跟最佳页面置换算法比较起来，性能明显差了很多。

最近最久未使用算法(LRU)

最近最久未使用（LRU）的置换算法的基本思路是，发生缺页时，选择最长时间没有被访问的页面进行置换，也就是说，该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

这种算法近似最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的页面，而 LRU 则是通过「历史」的使用情况来推测要淘汰的页面。还是以前面的请求的页面序列作为例子，假设使用最近最久未使用的置换算法，则过程如下图：

在这个请求的页面序列中，缺页共发生了 9 次，页面置换共发生了 6 次，跟先进先出置换算法比较起来，性能提高了一些。

虽然 LRU 在理论上是可以实现的，但代价很高。为了完全实现 LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是，在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作。

所以，LRU 虽然看上去不错，但是由于开销比较大，实际应用中比较少使用。

时钟置换算法(CLOCK)

该算法的思路是，把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面：

  • 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置
  • 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止

了解了这个算法的工作方式，就明白为什么它被称为时钟（Clock）算法了。

内存问题

内存抖动

在程序中，每次创建一个对象，都会为它分配一块内存；随着更多对象的创建，程序可用的内存逐渐减少。当已使用的内存达到一定阈值时，垃圾回收器（Garbage Collector，GC）会启动，回收不再使用的内存。在 Android 中，View.onDraw() 方法每次重绘界面时都会被调用，这意味着如果在 onDraw() 中编写了创建对象的代码，那么在界面频繁刷新时，这些代码会反复创建大量的临时对象。这会导致内存使用快速上升，并很快触发 GC 回收这些短暂的对象。

频繁创建和回收对象并不是问题本身。问题在于，当对象频繁创建导致内存迅速增加，而 GC 紧接着进行回收后，内存又会迅速上升。这种反复的过程会导致内存不断在增长和回收之间波动，形成了一种短时间内频繁发生的循环。

这种现象被称为 内存抖动（Memory Churn）。内存抖动不是指内存本身在震荡，而是描述内存频繁分配和回收所引起的波动和资源消耗。Android 官方文档也将其翻译为“内存抖动”。

抖动预防方法

  • 减少短生命周期对象的创建：使用对象池复用对象。避免在频繁调用的方法中创建对象。
  • 优化内存使用：避免不必要的对象分配。使用合适的数据结构，控制数据结构的大小。
  • 改进代码设计：选择高效算法，减少临时对象的生成。合并小对象，减少内存碎片。
  • 使用内存分析工具：监控内存使用，检测内存泄漏。进行内存优化和问题修复。
  • 调整垃圾回收策略：选择合适的GC算法。调整GC配置，优化内存管理。
  • 避免频繁的UI更新：减少UI对象创建，复用UI元素。优化渲染操作，减少对象创建开销。

工作集

工作集（或驻留集）是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长时间不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。

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

第四章 文件管理

文件

文件是一种抽象机制，它提供了一种方式用来存储信息以及在后面进行读取。可能任何一种机制最重要的特性就是管理对象的命名方式。在创建一个文件后，它会给文件一个命名。当进程终止时，文件会继续存在，并且其他进程可以使用名称访问该文件。

文件命名规则对于不同的操作系统来说是不一样的，但是所有现代操作系统都允许使用 1 - 8 个字母的字符串作为合法文件名。

某些文件区分大小写字母，而大多数则不区分。UNIX 属于第一类；历史悠久的 MS-DOS 属于第二类（顺便说一句，尽管 MS-DOS 历史悠久，但 MS-DOS 仍在嵌入式系统中非常广泛地使用，因此它绝不是过时的）；因此，UNIX 系统会有三种不同的命名文件：maria、Maria、MARIA 。在 MS-DOS ，所有这些命名都属于相同的文件。

这里可能需要在文件系统上预留一个位置。Windows 95 和 Windows 98 都使用了 MS-DOS 文件系统，叫做 FAT-16，因此继承了它的一些特征，例如有关文件名的构造方法。Windows 98 引入了对 FAT-16 的一些扩展，从而导致了 FAT-32 的生成，但是这两者很相似。另外，Windows NT，Windows 2000，Windows XP，Windows Vista，Windows 7 和 Windows 8 都支持 FAT 文件系统，这种文件系统有些过时。然而，这些较新的操作系统还具有更高级的本机文件系统(NTFS)，有不同的特性，那就是基于 Unicode 编码的文件名。事实上，Windows 8 还配备了另一种文件系统，简称 ReFS(Resilient File System)，但这个文件系统一般应用于 Windows 8 的服务器版本。下面除非我们特殊声明，否则我们在提到 MS-DOS 和 FAT 文件系统的时候，所指的就是 Windows 的 FAT-16 和 FAT-32。这里要说一下，有一种类似 FAT 的新型文件系统，叫做 exFAT。它是微软公司对闪存和大文件系统开发的一种优化的 FAT 32 扩展版本。ExFAT 是现在微软唯一能够满足 OS X读写操作的文件系统。

许多操作系统支持两部分的文件名，它们之间用 . 分隔开，比如文件名 prog.c。原点后面的文件称为 文件扩展名(file extension) ，文件扩展名通常表示文件的一些信息。例如在 MS-DOS 中，文件名是 1 - 8 个字符，加上 1 - 3 个字符的可选扩展名组成。在 UNIX 中，如果有扩展名，那么扩展名的长度将由用户来决定，一个文件甚至可以包括两个或更多的扩展名，例如 homepage.html.zip，html 表示一个 web 网页而 .zip 表示文件homepage.html 已经采用 zip 程序压缩完成。一些常用的文件扩展名以及含义如下图所示

bak 备份文件
c c 源程序文件
gif 符合图形交换格式的图像文件
hlp 帮助文件
html WWW 超文本标记语言文档
jpg 符合 JPEG 编码标准的静态图片
mp3 符合 MP3 音频编码格式的音乐文件
mpg 符合 MPEG 编码标准的电影
o 目标文件（编译器输出格式，尚未链接）
pdf pdf 格式的文件
ps PostScript 文件
tex 为 TEX 格式化程序准备的输入文件
txt 文本文件
zip 压缩文件

在 UNIX 系统中，文件扩展名只是一种约定，操作系统并不强制采用。

名为 file.txt 的文件是文本文件，这个文件名更多的是提醒所有者，而不是给计算机传递信息。但是另一方面，C 编译器可能要求它编译的文件以.c 结尾，否则它会拒绝编译。然而，操作系统并不关心这一点。

对于可以处理多种类型的程序，约定就显得及其有用。例如 C 编译器可以编译、链接多种文件，包括 C 文件和汇编语言文件。这时扩展名就很有必要，编译器利用它们区分哪些是 C 文件，哪些是汇编文件，哪些是其他文件。因此，扩展名对于编译器判断哪些是 C 文件，哪些是汇编文件以及哪些是其他文件变得至关重要。

与 UNIX 相反，Windows 就会关注扩展名并对扩展名赋予了新的含义。用户(或进程) 可以在操作系统中注册扩展名，并且规定哪个程序能够拥有扩展名。当用户双击某个文件名时，拥有该文件名的程序就启动并运行文件。例如，双击 file.docx 启动了 Word 程序，并以 file.docx 作为初始文件。

文件结构

文件的构造有多种方式。下图列出了常用的三种构造方式

上图中的 a 是一种无结构的字节序列，操作系统不关心序列的内容是什么，操作系统能看到的就是字节(bytes)。其文件内容的任何含义只在用户程序中进行解释。UNIX 和 Windows 都采用这种办法。

把文件看成字节序列提供了最大的灵活性。用户程序可以向文件中写任何内容，并且可以通过任何方便的形式命名。操作系统不会为为用户写入内容提供帮助，当然也不会干扰阻塞你。对于想做特殊操作的用户来说，后者是十分重要的。所有的 UNIX 版本（包括 Linux 和 OS X）和 Windows 都使用这种文件模型。

图 b 表示在文件结构上的第一部改进。在这个模型中，文件是具有固定长度记录的序列，每个记录都有其内部结构。 把文件作为记录序列的核心思想是：读操作返回一个记录，而写操作重写或者追加一个记录。第三种文件结构如上图 c 所示。在这种组织结构中，文件由一颗记录树构成，记录树的长度不一定相同，每个记录树都在记录中的固定位置包含一个key 字段。这棵树按 key 进行排序，从而可以对特定的 key 进行快速查找。

在记录树的结构中，可以取出下一个记录，但是最关键的还是根据 key 搜索指定的记录。如上图 c 所示，用户可以读出指定的 pony 记录，而不必关心记录在文件中的确切位置。用户也可以在文件中添加新的记录。但是用户不能决定添加到何处位置，添加到何处位置是由操作系统决定的。

文件类型

很多操作系统支持多种文件类型。例如，UNIX（同样包括 OS X）和 Windows 都具有常规的文件和目录。除此之外，UNIX 还具有字符特殊文件(character special file) 和 块特殊文件(block special file)。常规文件(Regular files) 是包含有用户信息的文件。用户一般使用的文件大都是常规文件，常规文件一般包括 可执行文件、文本文件、图像文件，从常规文件读取数据或将数据写入时，内核会根据文件系统的规则执行操作，是写入可能被延迟，记录日志或者接受其他操作。

字符特殊文件和输入/输出有关，用于串行 I/O 类设备，如终端、打印机、网络等。块特殊文件用于磁盘类设备。我们主要讨论的是常规文件。

常规文件一般分为 ASCII 码文件或者二进制文件。ASCII 码文件由文本组成。在一些系统中，每行都会用回车符结束（ASCII码是13，控制字符 CR，转义字符\r。），另外一些则会使用换行符（ASCII码是10，控制字符LF，转义字符\n）。一些系统（比如 Windows）两者都会使用。

ASCII 文件的优点在于显示 和 打印，还可以用任何文本编辑器进行编辑。进一步来说，如果许多应用程序使用 ASCII 码作为输入和输出，那么很容易就能够把多个程序连接起来，一个程序的输出可能是另一个程序的输入，就像管道一样。

其他与 ASCII 不同的是二进制文件。打印出来的二进制文件是无法理解的。下面是一个二进制文件的格式，它取自早期的 UNIX 。尽管从技术上来看这个文件只是字节序列，但是操作系统只有在文件格式正确的情况下才会执行。

一个文件有五个段：文件头、征文、数据、重定位位和符号表。文件头以 魔数(magic number) 为开始，表明这个文件是一个可执行文件（以防止意外执行非此格式的文件）。然后是文件各个部分的大小，开始执行的标志以及一些标志位。程序本身的正文和数据在文件头后面，他们被加载到内存中或者重定位会根据重定位位进行判断。符号表则用于调试。

二进制文件的另外一种形式是存档文件，它由已编译但没有链接的库过程（模块）组合而成。每个文件都以模块头开始，其中记录了名称、创建日期、所有者、保护码和文件大小。和可执行文件一样，模块头也都是二进制数，将它们复制到打印机将会产生乱码。

所有的操作系统必须至少能够识别一种文件类型：它自己的可执行文件。以前的 TOPS-20 系统（用于DECsystem 20）甚至要检查要执行的任何文件的创建时间，为了定位资源文件来检查自动文件创建后是否被修改过。如果被修改过了，那么就会自动编译文件。在 UNIX 中，就是在 shell 中嵌入 make 程序。此时操作系统要求用户必须采用固定的文件扩展名，从而确定哪个源程序生成哪个二进制文件。

什么是 make 程序？在软件发展过程中，make 程序是一个自动编译的工具，它通过读取称为 Makefiles 的文件来自动从源代码构建可执行程序和库，该文件指定了如何导出目标程序。尽管集成开发环境和特定于语言的编译器功能也可以用于管理构建过程，但 Make 仍被广泛使用，尤其是在 Unix 和类似 Unix 的操作系统中使用。

当程序从文件中读写数据时，请求会转到内核处理程序(kernel driver)。如果文件是常规文件，则数据由文件系统驱动程序处理，并且通常存储在磁盘或其他存储介质上的某块区域中，从文件中读取的数据就是之前在该位置写入的数据。

当数据读取或写入到设备文件时，请求会被设备驱动程序处理。每个设备文件都有一个关联的编号，该编号标示要使用的设备驱动程序。设备处理数据的工作是它自己的事儿。

  • 块设备 也叫做块特殊文件，它的行为通常与普通文件相似：它们是字节数组，并且在给定位置读取的值是最后写入该位置的值。来自块设备的数据可以缓存在内存中，并从缓存中读取；写入可以被缓冲。块设备通常是可搜索的，块设备的概念是，相应的硬件可以一次读取或者写入整个块，例如磁盘上的一个扇区
  • 字符设备 也称为字符特殊文件，它的行为类似于管道、串行端口。将字节写入字符设备可能会导致它在屏幕上显示，在串行端口上输出，转换为声音。

目录(Directories) 是管理文件系统结构的系统文件。它是用于在计算机上存储文件的位置。目录位于分层文件系统中，例如 Linux，MS-DOS 和 UNIX。

它显示所有本地和子目录（例如，cdn 目录中的 big 目录）。当前目录是 C 盘驱动器的根目录。之所以称为根目录，是因为该目录下没有任何内容，而其他目录都在该目录下分支。

文件访问

早期的操作系统只有一种访问方式：序列访问(sequential access)。在这些系统中，进程可以按照顺序读取所有的字节或文件中的记录，但是不能跳过并乱序执行它们。顺序访问文件是可以返回到起点的，需要时可以多次读取该文件。当存储介质是磁带而不是磁盘时，顺序访问文件很方便。

在使用磁盘来存储文件时，可以不按照顺序读取文件中的字节或者记录，或者按照关键字而不是位置来访问记录。这种能够以任意次序进行读取的称为随机访问文件(random access file)。许多应用程序都需要这种方式。

随机访问文件(无论数据存储在哪里，你都能快速、直接地找到并读取它)对许多应用程序来说都必不可少，例如，数据库系统。如果乘客打电话预定某航班机票，订票程序必须能够直接访问航班记录，而不必先读取其他航班的成千上万条记录。

有两种方法可以指示从何处开始读取文件。第一种方法是直接使用 read 从头开始读取。另一种是用一个特殊的 seek 操作设置当前位置，在 seek 操作后，从这个当前位置顺序地开始读文件。UNIX 和 Windows 使用的是后面一种方式。

文件属性

文件包括文件名和数据。除此之外，所有的操作系统还会保存其他与文件相关的信息，如文件创建的日期和时间、文件大小。我们可以称这些为文件的属性(attributes)。有些人也喜欢把它们称作 元数据(metadata)。文件的属性在不同的系统中差别很大。文件的属性只有两种状态：设置(set) 和 清除(clear)。下面是一些常用的属性

属性 含义
保护 谁可以访问文件、以什么方式存取文件
密码（口令） 访问文件所需要的密码（口令）
创建者 创建文件者的 ID
所有者 当前所有者
只读标志 0 表示读/写，1 表示只读
隐藏标志 0 表示正常，1 表示不再列表中显示
系统标志 0 表示普通文件，1 表示系统文件
存档标志 0 表示已经备份，1 表示需要备份
ASCII / 二进制标志 0 表示 ASCII 文件，1 表示二进制文件
随机访问标志 0 表示只允许顺序访问，1 表示随机访问
临时标志 0 表示正常，1 表示进程退出时删除该文件
加锁标志 0 表示未加锁，1 表示加锁
记录长度 一个记录中的字节数
键的位置 每个记录中的键的偏移量
键的长度 键字段的字节数
创建时间 创建文件的日期和时间
最后一次存取时间 上一次访问文件的日期和时间
最后一次修改时间 上一次修改文件的日期和时间
当前大小 文件的字节数
最大长度 文件可能增长到的字节数

没有一个系统能够同时具有上面所有的属性，但每个属性都在某个系统中采用。

前面四个属性（保护，口令，创建者，所有者）与文件保护有关，它们指出了谁可以访问这个文件，谁不能访问这个文件。

保护（File Protection）： 用于保护计算机上有价值数据的方法。文件保护是通过密码保护文件或者仅仅向特定用户或组提供权限来实现。

在一些系统中，用户必须给出口令才能访问文件。标志(flags)是一些位或者短属性能够控制或者允许特定属性。

  • 隐藏文件位(hidden flag)表示该文件不在文件列表中出现。
  • 存档标志位(archive flag)用于记录文件是否备份过，由备份程序清除该标志位；若文件被修改，操作系统则设置该标志位。用这种方法，备份程序可以知道哪些文件需要备份。
  • 临时标志位(temporary flag)允许文件被标记为是否允许自动删除当进程终止时。

记录长度(record-length)、键的位置(key-position)和键的长度(key-length)等字段只能出现在用关键字查找记录的文件中。它们提供了查找关键字所需要的信息。

不同的时间字段记录了文件的创建时间、最近一次访问时间以及最后一次修改时间，它们的作用不同。例如，目标文件生成后被修改的源文件需要重新编译生成目标文件。这些字段提供了必要的信息。

当前大小字段指出了当前的文件大小，一些旧的大型机操作系统要求在创建文件时指定文件呢最大值，以便让操作系统提前保留最大存储值。但是一些服务器和个人计算机却不用设置此功能。

文件操作*

使用文件的目的是用来存储信息并方便以后的检索。对于存储和检索，不同的系统提供了不同的操作。以下是与文件有关的最常用的一些系统调用：

  1. Create，创建不包含任何数据的文件。调用的目的是表示文件即将建立，并对文件设置一些属性。
  2. Delete，当文件不再需要，必须删除它以释放内存空间。为此总会有一个系统调用来删除文件。
  3. Open，在使用文件之前，必须先打开文件。这个调用的目的是允许系统将属性和磁盘地址列表保存到主存中，用来以后的快速访问。
  4. Close，当所有进程完成时，属性和磁盘地址不再需要，因此应关闭文件以释放表空间。很多系统限制进程打开文件的个数，以此达到鼓励用户关闭不再使用的文件。磁盘以块为单位写入，关闭文件时会强制写入最后一块，即使这个块空间内部还不满。
  5. Read，数据从文件中读取。通常情况下，读取的数据来自文件的当前位置。调用者必须指定需要读取多少数据，并且提供存放这些数据的缓冲区。
  6. Write，向文件写数据，写操作一般也是从文件的当前位置开始进行。如果当前位置是文件的末尾，则会直接追加进行写入。如果当前位置在文件中，则现有数据被覆盖，并且永远消失。
  7. append，使用 append 只能向文件末尾添加数据。
  8. seek，对于随机访问的文件，要指定从何处开始获取数据。通常的方法是用 seek 系统调用把当前位置指针指向文件中的特定位置。seek 调用结束后，就可以从指定位置开始读写数据了。
  9. get attributes，进程运行时通常需要读取文件属性。
  10. set attributes，用户可以自己设置一些文件属性，甚至是在文件创建之后，实现该功能的是 set attributes 系统调用。
  11. rename，用户可以自己更改已有文件的名字，rename 系统调用用于这一目的。

目录

文件系统通常提供目录(directories) 或者 文件夹(folders) 用于记录文件的位置，在很多系统中目录本身也是文件，下面我们会讨论关于文件，他们的组织形式、属性和可以对文件进行的操作。

一级目录系统

目录系统最简单的形式是有一个能够包含所有文件的目录。这种目录被称为根目录(root directory)，由于根目录的唯一性，所以其名称并不重要。在最早期的个人计算机中，这种系统很常见，部分原因是因为只有一个用户。下面是一个单层目录系统的例子

该目录中有四个文件。这种设计的优点在于简单，并且能够快速定位文件，毕竟只有一个地方可以检索。这种目录组织形式现在一般用于简单的嵌入式设备（如数码相机和某些便携式音乐播放器）上使用。

层次目录系统

对于简单的应用而言，一般都用单层目录方式，但是这种组织形式并不适合于现代计算机，因为现代计算机含有成千上万个文件和文件夹。如果都放在根目录下，查找起来会非常困难。为了解决这一问题，出现了层次目录系统(Hierarchical Directory Systems)，也称为目录树。通过这种方式，可以用很多目录把文件进行分组。进而，如果多个用户共享同一个文件服务器，比如公司的网络系统，每个用户可以为自己的目录树拥有自己的私人根目录。这种方式的组织结构如下

根目录含有目录 A、B 和 C ，分别属于不同的用户，其中两个用户个字创建了子目录。用户可以创建任意数量的子目录，现代文件系统都是按照这种方式组织的。

路径名

当目录树组织文件系统时，需要有某种方法指明文件名。常用的方法有两种，第一种方式是每个文件都会用一个绝对路径名(absolute path name)，它由根目录到文件的路径组成。举个例子，/usr/ast/mailbox 意味着根目录包含一个子目录usr，usr 下面包含了一个 mailbox。绝对路径名总是以 / 开头，并且是唯一的。在UNIX中，路径的组件由/分隔。在Windows中，分隔符为\。 在 MULTICS 中，它是>。 因此，在这三个系统中，相同的路径名将被编写如下

1
2
3
Windows \usr\ast\mailbox 
UNIX /usr/ast/mailbox 
MULTICS >usr>ast>mailbox

不论使用哪种方式，如果路径名的第一个字符是分隔符，那就是绝对路径。

另外一种指定文件名的方法是 相对路径名(relative path name)。它常常和 工作目录(working directory) （也称作 当前目录(current directory)）一起使用。用户可以指定一个目录作为当前工作目录。例如，如果当前目录是 /usr/ast，那么绝对路径 /usr/ast/mailbox可以直接使用 mailbox 来引用。也就是说，如果工作目录是 /usr/ast，则 UNIX 命令

1
cp /usr/ast/mailbox  /usr/ast/mailbox.bak

和命令

1
cp mailbox mailbox.bak

具有相同的含义。相对路径通常情况下更加方便和简洁。而它实现的功能和绝对路径安全相同。

一些程序需要访问某个特定的文件而不必关心当前的工作目录是什么。在这种情况下，应该使用绝对路径名。

支持层次目录结构的大多数操作系统在每个目录中有两个特殊的目录项. 和 ..，长读作 dot 和 dotdot。dot 指的是当前目录，dotdot 指的是其父目录（在根目录中例外，在根目录中指向自己）。可以参考下面的进程树来查看如何使用。

一个进程的工作目录是 /usr/ast，它可采用 .. 沿树向上，例如，可用命令

1
cp ../lib/dictionary .

把文件 usr/lib/dictionary 复制到自己的目录下，第一个路径告诉系统向上找（到 usr 目录），然后向下到 lib 目录，找到 dictionary 文件

第二个参数 . 指定当前的工作目录，当 cp 命令用目录名作为最后一个参数时，则把全部的文件复制到该目录中。当然，对于上述复制，键入

1
cp /usr/lib/dictionary .

是更常用的方法。用户这里采用 . 可以避免键入两次 dictionary 。无论如何，键入

1
cp /usr/lib/dictionary dictionary

也可正常工作，就像键入

1
cp /usr/lib/dictionary /usr/lib/dictionary

一样。所有这些命令都能够完成同样的工作。

目录操作

不同文件中管理目录的系统调用的差别比管理文件的系统调用差别大。为了了解这些系统调用有哪些以及它们怎样工作，下面给出一个例子（取自 UNIX）。

  1. Create，创建目录，除了目录项 . 和 .. 外，目录内容为空。
  2. Delete，删除目录，只有空目录可以删除。只包含 . 和 .. 的目录被认为是空目录，这两个目录项通常不能删除
  3. opendir，目录内容可被读取。例如，未列出目录中的全部文件，程序必须先打开该目录，然后读其中全部文件的文件名。与打开和读文件相同，在读目录前，必须先打开文件。
  4. closedir，读目录结束后，应该关闭目录用于释放内部表空间。
  5. readdir，系统调用 readdir 返回打开目录的下一个目录项。以前也采用 read 系统调用来读取目录，但是这种方法有一个缺点：程序员必须了解和处理目录的内部结构。相反，不论采用哪一种目录结构，readdir 总是以标准格式返回一个目录项。
  6. rename，在很多方面目录和文件都相似。文件可以更换名称，目录也可以。
  7. link，链接技术允许在多个目录中出现同一个文件。这个系统调用指定一个存在的文件和一个路径名，并建立从该文件到路径所指名字的链接。这样，可以在多个目录中出现同一个文件。有时也被称为硬链接(hard link)。
  8. unlink，删除目录项。如果被解除链接的文件只出现在一个目录中，则将它从文件中删除。如果它出现在多个目录中，则只删除指定路径名的链接，依然保留其他路径名的链接。在 UNIX 中，用于删除文件的系统调用就是 unlink。

文件系统的实现

在对文件有了基本认识之后，现在是时候把目光转移到文件系统的实现上了。之前用户关心的一直都是文件是怎样命名的、可以进行哪些操作、目录树是什么，如何找到正确的文件路径等问题。而设计人员关心的是文件和目录是怎样存储的、磁盘空间是如何管理的、如何使文件系统得以流畅运行的问题，下面我们就来一起讨论一下这些问题。

文件系统布局

文件系统存储在磁盘中。大部分的磁盘能够划分出一到多个分区，叫做磁盘分区(disk partitioning) 或者是磁盘分片(disk slicing)。每个分区都有独立的文件系统，每块分区的文件系统可以不同。磁盘的 0 号分区称为 主引导记录(Master Boot Record, MBR)，用来引导(boot) 计算机。在 MBR 的结尾是分区表(partition table)。每个分区表给出每个分区由开始到结束的地址。系统管理员使用一个称为分区编辑器的程序来创建，调整大小，删除和操作分区。这种方式的一个缺点是很难适当调整分区的大小，导致一个分区具有很多可用空间，而另一个分区几乎完全被分配。

MBR 可以用在 DOS 、Microsoft Windows 和 Linux 操作系统中。从 2010 年代中期开始，大多数新计算机都改用 GUID 分区表（GPT）分区方案。

下面是一个用 GParted 进行分区的磁盘，表中的分区都被认为是 活动的(active)。

当计算机开始引 boot 时，BIOS 读入并执行 MBR。

引导块

MBR 做的第一件事就是确定活动分区，读入它的第一个块，称为引导块(boot block) 并执行。引导块中的程序将加载分区中的操作系统。为了一致性，每个分区都会从引导块开始，即使引导块不包含操作系统。引导块占据文件系统的前 4096 个字节，从磁盘上的字节偏移量 0 开始。引导块可用于启动操作系统。

在计算机中，引导就是启动计算机的过程，它可以通过硬件（例如按下电源按钮）或者软件命令的方式来启动。开机后，电脑的 CPU 还不能执行指令，因为此时没有软件在主存中，所以一些软件必须先被加载到内存中，然后才能让 CPU 开始执行。也就是计算机开机后，首先会进行软件的装载过程。

重启电脑的过程称为重新引导(rebooting)，从休眠或睡眠状态返回计算机的过程不涉及启动。

除了从引导块开始之外，磁盘分区的布局是随着文件系统的不同而变化的。通常文件系统会包含一些属性，如下

超级块

紧跟在引导块后面的是 超级块(Superblock)，超级块 的大小为 4096 字节，从磁盘上的字节偏移 4096 开始。超级块包含文件系统的所有关键参数

  • 文件系统的大小
  • 文件系统中的数据块数
  • 指示文件系统状态的标志
  • 分配组大小

在计算机启动或者文件系统首次使用时，超级块会被读入内存。

空闲空间块

接着是文件系统中空闲块的信息，例如，可以用位图或者指针列表的形式给出。

BitMap 位图或者 Bit vector 位向量

位图或位向量是一系列位或位的集合，其中每个位对应一个磁盘块，该位可以采用两个值：0和1，0表示已分配该块，而1表示一个空闲块。下图中的磁盘上给定的磁盘块实例（分配了绿色块）可以用16位的位图表示为：0000111000000110。

使用链表进行管理

在这种方法中，空闲磁盘块链接在一起，即一个空闲块包含指向下一个空闲块的指针。第一个磁盘块的块号存储在磁盘上的单独位置，也缓存在内存中。

碎片

这里不得不提一个叫做碎片(fragment)的概念，也称为片段。一般零散的单个数据通常称为片段。 磁盘块可以进一步分为固定大小的分配单元，片段只是在驱动器上彼此不相邻的文件片段。如果你不理解这个概念就给你举个例子。比如你用 Windows 电脑创建了一个文件，你会发现这个文件可以存储在任何地方，比如存在桌面上，存在磁盘中的文件夹中或者其他地方。你可以打开文件，编辑文件，删除文件等等。你可能以为这些都在一个地方发生，但是实际上并不是，你的硬盘驱动器可能会将文件中的一部分存储在一个区域内，另一部分存储在另外一个区域，在你打开文件时，硬盘驱动器会迅速的将文件的所有部分汇总在一起，以便其他计算机系统可以使用它。

inode

然后在后面是一个 inode(index node)，也称作索引节点。它是一个数组的结构，每个文件有一个 inode，inode 非常重要，它说明了文件的方方面面。每个索引节点都存储对象数据的属性和磁盘块位置

有一种简单的方法可以找到它们 ls -lai 命令。让我们看一下根文件系统：

文件的实现

最重要的问题是记录各个文件分别用到了哪些磁盘块。不同的系统采用了不同的方法。下面我们会探讨一下这些方式。分配背后的主要思想是有效利用文件空间和快速访问文件 ，主要有三种分配方案

  • 连续分配
  • 链表分配
  • 索引分配
连续分配

最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。因此，在具有 1KB 块的磁盘上，将为 50 KB 文件分配 50 个连续块。

上面展示了 40 个连续的内存块。从最左侧的 0 块开始。初始状态下，还没有装载文件，因此磁盘是空的。接着，从磁盘开始处（块 0 ）处开始写入占用 4 块长度的内存 A 。然后是一个占用 6 块长度的内存 B，会直接在 A 的末尾开始写。

注意每个文件都会在新的文件块开始写，所以如果文件 A 只占用了 3 又 1/2 个块，那么最后一个块的部分内存会被浪费。在上面这幅图中，总共展示了 7 个文件，每个文件都会从上个文件的末尾块开始写新的文件块。

连续的磁盘空间分配有两个优点。

  • 第一，连续文件存储实现起来比较简单，只需要记住两个数字就可以：一个是第一个块的文件地址和文件的块数量。给定第一个块的编号，可以通过简单的加法找到任何其他块的编号。
  • 第二点是读取性能比较强，可以通过一次操作从文件中读取整个文件。只需要一次寻找第一个块。后面就不再需要寻道时间和旋转延迟，所以数据会以全带宽进入磁盘。

因此，连续的空间分配具有实现简单、高性能的特点。

不幸的是，连续空间分配也有很明显的不足。随着时间的推移，磁盘会变得很零碎。下图解释了这种现象

这里有两个文件 D 和 F 被删除了。当删除一个文件时，此文件所占用的块也随之释放，就会在磁盘空间中留下一些空闲块。磁盘并不会在这个位置挤压掉空闲块(也就是不会移动块填补空洞)，因为这会复制空闲块之后的所有文件，可能会有上百万的块，这个量级就太大了。

刚开始的时候，这个碎片不是问题，因为每个新文件都会在之前文件的结尾处进行写入。然而，磁盘最终会被填满，因此要么压缩磁盘、要么重新使用空闲块的空间。压缩磁盘的开销太大，因此不可行；后者会维护一个空闲列表，这个是可行的。但是这种情况又存在一个问题，为空闲块匹配合适大小的文件，需要知道该文件的最终大小。

想象一下这种设计的结果会是怎样的。用户启动 word 进程创建文档。应用程序首先会询问最终创建的文档会有多大。这个问题必须回答，否则应用程序就不会继续执行。如果空闲块的大小要比文件的大小小，程序就会终止。因为所使用的磁盘空间已经满了。那么现实生活中，有没有使用连续分配内存的介质出现呢？

CD-ROM 就广泛的使用了连续分配方式。

CD-ROM（Compact Disc Read-Only Memory）即只读光盘，也称作只读存储器。是一种在电脑上使用的光碟。这种光碟只能写入数据一次，信息将永久保存在光碟上，使用时通过光碟驱动器读出信息。

然而 DVD 的情况会更加复杂一些。原则上，一个 90分钟 的电影能够被编码成一个独立的、大约 4.5 GB 的文件。但是文件系统所使用的 UDF(Universal Disk Format) 格式，使用一个 30 位的数来代表文件长度，从而把文件大小限制在 1 GB。所以，DVD 电影一般存储在 3、4个连续的 1 GB 空间内。这些构成单个电影中的文件块称为扩展区(extends)。

就像我们反复提到的，历史总是惊人的相似，许多年前，连续分配由于其简单和高性能被实际使用在磁盘文件系统中。后来由于用户不希望在创建文件时指定文件的大小，于是放弃了这种想法。但是随着 CD-ROM 、DVD、蓝光光盘等光学介质的出现，连续分配又流行起来。从而得出结论，技术永远没有过时性，现在看似很老的技术，在未来某个阶段可能又会流行起来。

链表分配

第二种存储文件的方式是为每个文件构造磁盘块链表，每个文件都是磁盘块的链接列表，就像下面所示

每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。如果上面这张图你看的不是很清楚的话，可以看看整个的链表分配方案

与连续分配方案不同，这一方法可以充分利用每个磁盘块。除了最后一个磁盘块外，不会因为磁盘碎片而浪费存储空间。同样，在目录项中，只要存储了第一个文件块，那么其他文件块也能够被找到。

另一方面，在链表的分配方案中，尽管顺序读取非常方便，但是随机访问却很困难（这也是数组和链表数据结构的一大区别）。

还有一个问题是，由于指针会占用一些字节，每个磁盘块实际存储数据的字节数并不再是 2 的整数次幂。虽然这个问题并不会很严重，但是这种方式降低了程序运行效率。许多程序都是以长度为 2 的整数次幂来读写磁盘，由于每个块的前几个字节被指针所使用，所以要读出一个完成的块大小信息，就需要当前块的信息和下一块的信息拼凑而成，因此就引发了查找和拼接的开销。

使用内存表进行链表分配

由于连续分配和链表分配都有其不可忽视的缺点。所以提出了使用内存中的表来解决分配问题。取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决上述链表的两个不足之处。下面是一个例子

上图表示了链表形成的磁盘块的内容。这两个图中都有两个文件，文件 A 依次使用了磁盘块地址 4、7、 2、 10、 12，文件 B 使用了6、3、11 和 14。也就是说，文件 A 从地址 4 处开始，顺着链表走就能找到文件 A 的全部磁盘块。同样，从第 6 块开始，顺着链走到最后，也能够找到文件 B 的全部磁盘块。你会发现，这两个链表都以不属于有效磁盘编号的特殊标记（-1）结束。内存中的这种表格称为 文件分配表(File Application Table,FAT)。

使用这种组织方式，整个块都可以存放数据。进而，随机访问也容易很多。虽然仍要顺着链在内存中查找给定的偏移量，但是整个链都存放在内存中，所以不需要任何磁盘引用。与前面的方法相同，不管文件有多大，在目录项中只需记录一个整数（起始块号），按照它就可以找到文件的全部块。

这种方式存在缺点，那就是必须要把整个链表放在内存中。对于 1TB 的磁盘和 1KB 的大小的块，那么这张表需要有 10 亿项。。。每一项对应于这 10 亿个磁盘块中的一块。每项至少 3 个字节，为了提高查找速度，有时需要 4 个字节。根据系统对空间或时间的优化方案，这张表要占用 3GB 或 2.4GB 的内存。FAT 的管理方式不能较好地扩展并应用于大型磁盘中。而这正是最初 MS-DOS 文件比较实用，并仍被各个 Windows 版本所安全支持。

inode(索引)

最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为 inode(索引节点) 的数据结构，每个文件都与一个 inode 进行关联，inode 由整数进行标识。

下面是一个简单例子的描述。

给出 inode 的长度，就能够找到文件中的所有块。

相对于在内存中使用表的方式而言，这种机制具有很大的优势。即只有在文件打开时，其 inode 才会在内存中。如果每个 inode 需要 n 个字节，最多 k 个文件同时打开，那么 inode 占有总共打开的文件是 kn 字节。仅需预留这么多空间。

这个数组要比我们上面描述的 FAT(文件分配表) 占用的空间小的多。原因是用于保存所有磁盘块的链接列表的表的大小与磁盘本身成正比。如果磁盘有 n 个块，那么这个表也需要 n 项。随着磁盘空间的变大，那么该表也随之线性增长。相反，inode 需要节点中的数组，其大小和可能需要打开的最大文件个数成正比。它与磁盘是 100GB、4000GB 还是 10000GB 无关。

inode 的一个问题是如果每个节点都会有固定大小的磁盘地址，那么文件增长到所能允许的最大容量外会发生什么？一个解决方案是最后一个磁盘地址不指向数据块，而是指向一个包含额外磁盘块地址的地址，如上图所示。一个更高级的解决方案是：有两个或者更多包含磁盘地址的块，或者指向其他存放地址的磁盘块的磁盘块。Windows 的 NTFS 文件系统采用了相似的方法，所不同的仅仅是大的 inode 也可以表示小的文件。

NTFS 的全称是 New Technology File System，是微软公司开发的专用系统文件，NTFS 取代 FAT(文件分配表) 和 HPFS(高性能文件系统) ，并在此基础上进一步改进。例如增强对元数据的支持，使用更高级的数据结构以提升性能、可靠性和磁盘空间利用率等。

目录的实现

文件只有打开后才能够被读取。在文件打开后，操作系统会使用用户提供的路径名来定位磁盘中的目录。目录项提供了查找文件磁盘块所需要的信息。根据系统的不同，提供的信息也不同，可能提供的信息是整个文件的磁盘地址，或者是第一个块的数量（两个链表方案）或 inode的数量。不过不管用那种情况，目录系统的主要功能就是 将文件的 ASCII 码的名称映射到定位数据所需的信息上。

与此关系密切的问题是属性应该存放在哪里。每个文件系统包含不同的文件属性，例如文件的所有者和创建时间，需要存储的位置。一种显而易见的方法是直接把文件属性存放在目录中。有一些系统恰好是这么做的，如下。

在这种简单的设计中，目录有一个固定大小的目录项列表，每个文件对应一项，其中包含一个固定长度的文件名，文件属性的结构体以及用以说明磁盘块位置的一个或多个磁盘地址。

对于采用 inode 的系统，会把 inode 存储在属性中而不是目录项中。在这种情况下，目录项会更短：仅仅只有文件名称和 inode 数量。这种方式如下所示

到目前为止，我们已经假设文件具有较短的、固定长度的名字。在 MS-DOS 中，具有 1 - 8 个字符的基本名称和 1 - 3 个字符的可拓展名称。在 UNIX 版本 7 中，文件有 1 - 14 个字符，包括任何拓展。然而，几乎所有的现代操作系统都支持可变长度的扩展名。这是如何实现的呢？

最简单的方式是给予文件名一个长度限制，比如 255 个字符，然后使用上图中的设计，并为每个文件名保留 255 个字符空间。这种处理很简单，但是浪费了大量的目录空间，因为只有很少的文件会有那么长的文件名称。所以，需要一种其他的结构来处理。

一种可选择的方式是放弃所有目录项大小相同的想法。在这种方法中，每个目录项都包含一个固定部分，这个固定部分通常以目录项的长度开始，后面是固定格式的数据，通常包括所有者、创建时间、保护信息和其他属性。这个固定长度的头的后面是一个任意长度的实际文件名，如下图所示

上图是 SPARC 机器使用正序放置。

处理机中的一串字符存放的顺序有正序(big-endian) 和逆序(little-endian) 之分。正序存放的就是高字节在前低字节在后，而逆序存放的就是低字节在前高字节在后。

这个例子中，有三个文件，分别是 project-budget、personnel 和 foo。每个文件名以一个特殊字符（通常是 0 ）结束，用矩形中的叉进行表示。为了使每个目录项从字的边界开始，每个文件名被填充成整数个字，如下图所示

这个方法的缺点是当文件被移除后，就会留下一块固定长度的空间，而新添加进来的文件大小不一定和空闲空间大小一致。

这个问题与我们上面探讨的连续磁盘文件的问题是一样的，由于整个目录在内存中，所以只有对目录进行紧凑拼接操作才可节省空间。另一个问题是，一个目录项可能会分布在多个页上，在读取文件名时可能发生缺页中断。

处理可变长度文件名字的另外一种方法是，使目录项自身具有固定长度，而将文件名放在目录末尾的堆栈中。如上图所示的这种方式。这种方法的优点是当目录项被移除后，下一个文件将能够正常匹配移除文件的空间。当然，必须要对堆进行管理，因为在处理文件名的时候也会发生缺页异常。

到目前为止的所有设计中，在需要查找文件名时，所有的方案都是线性的从头到尾对目录进行搜索。对于特别长的目录，线性搜索的效率很低。提高文件检索效率的一种方式是在每个目录上使用哈希表(hash table)，也叫做散列表。我们假设表的大小为 n，在输入文件名时，文件名被散列在 0 和 n - 1 之间，例如，它被 n 除，并取余数。或者对构成文件名字的字求和或类似某种方法。

无论采用哪种方式，在添加一个文件时都要对与散列值相对 应的散列表进行检查。如果没有使用过，就会将一个指向目录项的指针指向这里。文件目录项紧跟着哈希表后面。如果已经使用过，就会构造一个链表（这种构造方式是不是和 HashMap 使用的数据结构一样？），链表的表头指针存放在表项中，并通过哈希值将所有的表项相连。

查找文件的过程和添加类似，首先对文件名进行哈希处理，在哈希表中查找是否有这个哈希值，如果有的话，就检查这条链上所有的哈希项，查看文件名是否存在。如果哈希不在链上，那么文件就不在目录中。

使用哈希表的优势是查找非常迅速，缺点是管理起来非常复杂。只有在系统中会有成千上万个目录项存在时，才会考虑使用散列表作为解决方案。

另外一种在大量目录中加快查找指令目录的方法是使用缓存，缓存查找的结果。在开始查找之前，会首先检查文件名是否在缓存中。如果在缓存中，那么文件就能立刻定位。当然，只有在较少的文件下进行多次查找，缓存才会发挥最大功效。

共享文件*

当多个用户在同一个项目中工作时，他们通常需要共享文件。如果这个共享文件同时出现在多个用户目录下，那么他们协同工作起来就很方便。下面的这张图我们在上面提到过，但是有一个更改的地方，就是 C 的一个文件也出现在了 B 的目录下。

如果按照如上图的这种组织方式而言，那么 B 的目录与该共享文件的联系称为 链接(link)。那么文件系统现在就是一个 有向无环图(Directed Acyclic Graph, 简称 DAG)，而不是一棵树了。

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图，我们不会在此着重探讨关于图论的东西，大家可以自行 google。

将文件系统组织成为有向无环图会使得维护复杂化，但也是必须要付出的代价。

共享文件很方便，但这也会带来一些问题。如果目录中包含磁盘地址，则当链接文件时，必须把 C 目录中的磁盘地址复制到 B 目录中。如果 B 或者 C 随后又向文件中添加内容，则仅在执行追加的用户的目录中显示新写入的数据块。这种变更将会对其他用户不可见，从而破坏了共享的目的。

有两种方案可以解决这种问题。

  • 第一种解决方案，磁盘块不列入目录中，而是会把磁盘块放在与文件本身相关联的小型数据结构中。目录将指向这个小型数据结构。这是 UNIX 中使用的方式（小型数据结构就是 inode）。
  • 在第二种解决方案中，通过让系统建立一个类型为 LINK 的新文件，并把该文件放在 B 的目录下，使得 B 与 C 建立链接。新的文件中只包含了它所链接的文件的路径名。当 B 想要读取文件时，操作系统会检查 B 的目录下存在一个类型为 LINK 的文件，进而找到该链接的文件和路径名，然后再去读文件，这种方式称为 符号链接(symbolic linking)。

上面的每一种方法都有各自的缺点，在第一种方式中，B 链接到共享文件时，inode 记录文件的所有者为 C。建立一个链接并不改变所有关系，如下图所示。

第一开始的情况如图 a 所示，此时 C 的目录的所有者是 C ，当目录 B 链接到共享文件时，并不会改变 C 的所有者关系，只是把计数 + 1，所以此时 系统知道目前有多少个目录指向这个文件。然后 C 尝试删除这个文件，这个时候有个问题，如果 C 把文件移除并清除了 inode 的话，那么 B 会有一个目录项指向无效的节点。如果 inode 以后分配给另一个文件，则 B 的链接指向一个错误的文件。系统通过 inode 可知文件仍在被引用，但是没有办法找到该文件的全部目录项以删除它们。指向目录的指针不能存储在 inode 中，原因是有可能有无数个这样的目录。

所以我们能做的就是删除 C 的目录项，但是将 inode 保留下来，并将计数设置为 1 ，如上图 c 所示。c 表示的是只有 B 有指向该文件的目录项，而该文件的前者是 C 。如果系统进行记账操作的话，那么 C 将继续为该文件付账直到 B 决定删除它，如果是这样的话，只有到计数变为 0 的时刻，才会删除该文件。

对于符号链接，以上问题不会发生，只有真正的文件所有者才有一个指向 inode 的指针。链接到该文件上的用户只有路径名，没有指向 inode 的指针。当文件所有者删除文件时，该文件被销毁。以后若试图通过符号链接访问该文件将会失败，因为系统不能找到该文件。删除符号链接不会影响该文件。

符号链接的问题是需要额外的开销。必须读取包含路径的文件，然后要一个部分接一个部分地扫描路径，直到找到 inode 。这些操作也许需要很多次额外的磁盘访问。此外，每个符号链接都需要额外的 inode ，以及额外的一个磁盘块用于存储路径，虽然如果路径名很短，作为一种优化，系统可以将它存储在 inode 中。符号链接有一个优势，即只要简单地提供一个机器的网络地址以及文件在该机器上驻留的路径，就可以连接全球任何地方机器上的文件。

还有另一个由链接带来的问题，在符号链接和其他方式中都存在。如果允许链接，文件有两个或多个路径。查找一指定目录及其子目录下的全部文件的程序将多次定位到被链接的文件。例如，一个将某一目录及其子目录下的文件转存到磁带上的程序有可能多次复制一个被链接的文件。进而，如果接着把磁带读入另一台机器，除非转出程序具有智能，否则被链接的文件将被两次复制到磁盘上，而不是只是被链接起来。

第五章 OI管理

I/O 系统：I/O 系统是 OS 的重要组成部分，I/O 系统管理的主要对象是 I/O 设备和相应的设备控制器。其最主要的任务是，完成用户提出的 I/O 请求，提高 I/O 速率，以及提高设备的利用率，并能为更高层的进程方便地使用这些设备提供手段。

I/O 系统的基本功能

为了满足系统和用户的要求，I/O 系统应具有下述几方面的基本功能。

功能 说明
隐藏物理设备的细节 I/O 设备的类型非常多，I/O 系统通过对设备加以适当的抽象，以隐藏掉物理设备的实现细节，仅向上层进程提供少量的、抽象的读/写命令
与设备的无关性 用户不仅可以使用抽象的I/O命令，还可使用抽象的逻辑设备名来使用设备
提高处理机和 I/O 设备的利用率 尽可能地让处理机和 I/O 设备并行操作，处理机能快速响应用户的 I/O 请求，并尽量减少在 I/O 设备运行时处理机的干预时间
对 I/O设备进行控制 目前对 I/O 设备有四种控制方式：采用轮询的可编程 I/O 方式、采用中断的可编程 I/O 方式、直接存储器访问方式、I/O 通道方式
确保对设备的正确共享 进程应互斥地访问独占设备，共享设备可以在一段时间内允许多个进程同时访问
错误处理 低层软件能够解决的错误就不向上层报告，只有低层软件解决不了的错误才向上层报告，请求高层软件解决

I/O软件层次

  1. 用户进程层执行输入输出系统调用，对I/O数据进行格式化，为假脱机输入输出做准备。实现与用户交互的接口，用户可以直接调用该层提供的库函数对设备进行操作
  2. 独立于设备的软件实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，为设备管理和数据传送提供必要的存储空间
  3. 设备驱动程序设置设备寄存器、检查设备的执行状态，用于具体实现系统对设备发出的操作指令，驱动 I/O 设备工作的驱动程序
  4. 中断处理程序负责I/O完成时，唤醒设备驱动程序进程，进行中断处理，用于保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断的进程
  5. 硬件层面实现物理I/O的操作
I/O 系统模型

与前面所述的 I/O 软件组织的层次结构相对应，I/O 系统本身也可分为三个层次。

层次 说明
中断处理程序 处于 I/O 系统的底层，直接与硬件进行交互。当有 I/O 设备发来中断请求信号时，中断处理程序首先保存被中断进程的 CPU 环境，然后转入相应设备的中断处理程序进行处理，在处理完成后又恢复被中断进程的 CPU 环境，返回断点继续运行
设备驱动程序 处于 I/O 系统的次底层，是进程和设备控制器之间的通信程序，将上层发来的抽象 I/O 请求转换为对 I/O 设备的具体命令和参数，并把它装入到设备控制器中的命令和参数寄存器中
设备独立性软件 实现了与设备无关性，内容包括设备命名、设备分配、数据缓冲和数据高速缓冲一类软件等

由于设备之间的差异很大，每类设备的驱动程序都不相同，故必须由设备制造厂商提供。每当在系统中增加一个新设备时，都需要由安装厂商提供新的驱动程序。这些层次之间有 I/O 系统接口和软件/硬件接口。

接口 说明
I/O 系统接口 I/O 系统与上层系统之间的接口，向上层提供对设备进行操作的抽象 I/O 命令，一些 OS 在用户层提供了与 I/O 操作有关的库函数
软件/硬件(RW/HW)接口 在它的上面是中断处理程序和用于不同设备的设备驱动程序，在它的下面是各种设备的控制器
I/O 系统接口

在 I/O 系统与高层之间的接口中，根据设备类型的不同，又进一步分为若干个接口，例如块设备接口、流设备接口和网络接口。

块设备接口

　　块设备接口是块设备管理程序与高层之间的接口，用于控制该类设备的输入或输出。块设备是指数据的存取和传输都是以数据块为单位的设备，典型的块设备是磁盘。该设备的基本特征是传输速率较高，并且可寻址。块设备接口将磁盘上的所有扇区从 0 到 n-1 依次编号，n 是磁盘中的扇区总数。这样编号后把磁盘的二维结构改变为一种线性序列，使块设备接口隐藏了磁盘地址是二维结构的情况。块设备接口支持上层发来的对文件或设备的打开、读、写和关闭等抽象命令，将上述命令映射为设备能识别的较低层具体操作。

　　虚拟存储器系统也需要使用块设备接口，因为在进程运行期间若所访问的页面不在内存时会发生缺页中断，此时就需要利用 I/O 系统，通过块设备接口从磁盘存储器中将所缺之页面调入内存。

流设备接口

　　流设备接口是流设备管理程序与高层之间的接口，用于控制字符设备的输入或输出。字符设备指数据的存取和传输是以字符为单位的设备，如键盘、打印机等，基本特征是传输速率较低，并且不可寻址，因而对它只能采取顺序存取方式，用户程序获取或输出字符的方法是采用 get 和 put 操作。由于大多数流设备都属于独占设备，必须采取互斥方式实现共享，为此流设备接口提供了打开和关闭操作。

网络通信接口

在现代 OS 中都提供了面向网络的功能，首先需要通过某种方式把计算机连接到网络上，同时操作系统也必须提供相应的网络软件和网络通信接口，使计算机能通过网络与网络上的其它计算机进行通信或上网浏览。

中断处理程序*

中断处理程序又被称为中断服务程序 或者是 ISR(Interrupt Service Routines)，它是最靠近硬件的一层。中断处理程序由硬件中断、软件中断或者是软件异常启动产生的中断，用于实现设备驱动程序或受保护的操作模式（例如系统调用）之间的转换。中断在操作系统是多道程序得以实现的基础，，因为进程之间的切换是通过中断来完成的。中断也是设备管理的基础，为了提高处理机的利用率和实现 CPU 与 I/O 设备并行执行，也必需有中断的支持。

　　中断处理程序负责处理中断发生时的所有操作，操作完成后阻塞，然后启动中断驱动程序来解决阻塞。通常会有三种通知方式，依赖于不同的具体实现

  • 信号量实现中：在信号量上使用 up 进行通知；
  • 管程实现：对管程中的条件变量执行 signal 操作
  • 还有一些情况是发送一些消息

不管哪种方式都是为了让阻塞的中断处理程序恢复运行。

中断和陷入

　　中断是指 CPU 对 I/O 设备发来的中断信号的一种响应，CPU 暂停正在执行的程序，保留 CPU 环境后，自动地转去执行该 I/O 设备的中断处理程序。执行完后再回到断点，继续执行原来的程序。I/O 设备可以是字符设备，也可以是块设备、通信设备等。由于中断是由外部设备引起的，故又称外中断。

　　另外还有一种由 CPU 内部事件所引起的中断，通常把这类中断称为内中断或陷入(trap)。若系统发现了有陷入事件，CPU 也将暂停正在执行的程序，转去执行该陷入事件的处理程序。中断和陷入的主要区别是信号的来源，即是来自 CPU 外部还是 CPU 内部。

中断向量表

　　为了处理上的方便，通常是为每种设备配以相应的中断处理程序，并把该程序的入口地址放在中断向量表的一个表项中。每一个设备的中断请求规定一个中断号，它直接对应于中断向量表的一个表项中。当 I/O 设备发来中断请求信号时，由中断控制器确定该请求的中断号，根据中断号去查找中断向量表取得中断处理程序的入口地址。经常会有多个中断信号源，每个中断源对服务要求的紧急程度并不相同，为此系统就需要为它们分别规定不同的优先级。

中断处理方案有很多种

  • 非嵌套的中断处理程序按照顺序处理各个中断，非嵌套的中断处理程序也是最简单的中断处理
  • 嵌套的中断处理程序会处理多个中断而无需分配优先级
  • 可重入的中断处理程序可使用优先级处理多个中断
  • 简单优先级中断处理程序可处理简单的中断
  • 标准优先级中断处理程序比低优先级的中断处理程序在更短的时间能够处理优先级更高的中断
  • 高优先级 中断处理程序在短时间能够处理优先级更高的任务，并直接进入特定的服务例程。
  • 优先级分组中断处理程序能够处理不同优先级的中断任务

下面是一些通用的中断处理程序的步骤，不同的操作系统实现细节不一样

  • 保存所有没有被中断硬件保存的寄存器（包括PSW）。
  • 为中断服务程序设置上下文环境，可能包括设置 TLB、MMU 和页表。
  • 为中断服务程序设置栈
  • 对中断控制器作出响应，如果不存在集中的中断控制器，则继续响应中断
  • 把寄存器从保存它的地方拷贝到进程表中
  • 运行中断服务程序，它会从发出中断的设备控制器的寄存器中提取信息
  • 操作系统会选择一个合适的进程来运行。如果中断造成了一些优先级更高的进程变为就绪态，则选择运行这些优先级高的进程
  • 为进程设置 MMU 上下文，可能也会需要 TLB，根据实际情况决定
  • 加载进程的寄存器，包括 PSW 寄存器
  • 开始运行新的进程

　　由此可见， 中断处理远不是无足轻重的小事。 它要花费相当多的CPU指令， 特别是在存在虚拟内存并且必须设置页表或者必须保存MMU状态（例如R和M位） 的机器上。 在某些机器上， 当在用户态与核心态之间切换时， 可能还需要管理TLB和CPU高速缓存， 这就要花费额外的机器周期。

设备驱动程序

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

　　设备驱动程序通常位于操作系统其余部分的下面， 如图5-12所示。

设备驱动程序的功能

为了实现 I/O 系统的高层与设备控制器之间的通信，设备驱动程序应具有以下功能：

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

设备驱动程序的特点

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

  1. 实现在与设备无关的软件和设备控制器之间通信和转换的程序；
  2. 对于不同类型的设备，应配置不同的驱动程序，但可以为相同的多个终端设置终端驱动程序。
  3. 驱动程序与 I/O 设备所采用的 I/O 控制方式紧密相关；
  4. 其中的一部分必须用汇编语言书写，目前很多驱动程序的基本部分固化在 ROM 中；
  5. 一个正在运行的驱动程序常会在一次调用完成前被再次调用。

设备处理方式

在不同的操作系统中，所采用的设备处理方式并不完全相同。设备处理方式分成以下三类，目前来说第三类用的比较多。

  1. 为每一类设备设置一个进程，专门用于执行这类设备的 I/O 操作；
  2. 在整个系统中设置一个 I/O 进程，专门用于执行系统中所有各类设备的 I/O 操作；
  3. 不设置专门的设备处理进程，而只为各类设备设置相应的设备驱动程序，供用户或系统进程调用。

设备驱动程序的处理过程

  1. 典型的驱动程序在启动时要检查输入参数， 检查输入参数的目的是搞清它们是否是有效的， 如果不是， 则返回一个错误。 如果输入参数是有效的， 则可能需要进行从抽象事项到具体事项的转换。 对磁盘驱动程序来说， 这可能意味着将一个线性的磁盘块号转换成磁盘几何布局的磁头、 磁道、 扇区和柱面号。
  2. 接着， 驱动程序可能要检查设备当前是否在使用。 如果在使用， 请求将被排入队列以备稍后处理。 如果设备是空闲的， 驱动程序将检查硬件状态以了解请求现在是否能够得到处理。 在传输能够开始之前， 可能需要接通设备或者启动马达。 一旦设备接通并就绪， 实际的控制就可以开始了。
  3. 控制设备意味着向设备发出一系列命令。 依据控制设备必须要做的工作， 驱动程序处在确定命令序列的地方。 驱动程序在获知哪些命令将要发出之后， 它就开始将它们写入控制器的设备寄存器。 驱动程序在把每个命令写到控制器之后， 它可能必须进行检测以了解控制器是否已经接收命令并且准备好接收下一个命令。这一序列继续进行， 直到所有命令被发出。 对于某些控制器， 可以为其提供一个在内存中的命令链表， 并且告诉它自己去读取并处理所有命令而不需要操作系统提供进一步帮助。
  4. 命令发出之后， 会牵涉两种情形之一。 在多数情况下， 设备驱动程序必须等待， 直到控制器为其做某些事情， 所以驱动程序将阻塞其自身直到中断到来解除阻塞。 然而， 在另外一些情况下， 操作可以无延迟地完成， 所以驱动程序不需要阻塞。 在字符模式下滚动屏幕只需要写少许字节到控制器的寄存器中， 由于不需要机械运动， 所以整个操作可以在几纳秒内完成， 这便是后一种情形的例子。在前一种情况下， 阻塞的驱动程序可以被中断唤醒。 在后一种情况下， 驱动程序根本就不会休眠。 无论是哪一种情况， 操作完成之后驱动程序都必须检查错误。 如果一切顺利， 驱动程序可能要将数据（例如刚刚读出的一个磁盘块） 传送给与设备无关的软件。
  5. 最后， 它向调用者返回一些用于错误报告的状态信息。 如果还有其他未完成的请求在排队， 则选择一个启动执行。 如果队列中没有未完成的请求， 则该驱动程序将阻塞以等待下一个请求。

　　这一简单的模型只是现实的粗略近似， 许多因素使相关的代码比这要复杂得多。 首先， 当一个驱动程序正在运行时， 某个I/O设备可能会完成操作， 这样就会中断驱动程序。 中断可能会导致一个设备驱动程序运行， 事实上， 它可能导致当前驱动程序运行。 例如， 当网络驱动程序正在处理一个到来的数据包时， 另一个数据包可能到来。 因此， 驱动程序必须是重入的（reentrant） ， 这意味着一个正在运行的驱动程序必须预料到在第一次调用完成之前第二次被调用。

　　在一个热可插拔的系统中， 设备可以在计算机运行时添加或删除。 因此， 当一个驱动程序正忙于从某设备读数据时， 系统可能会通知它用户突然将设备从系统中删除了。 在这样的情况下， 不但当前I/O传送必须中止并且不能破坏任何核心数据结构， 而且任何对这个现已消失的设备的悬而未决的请求都必须适当地从系统中删除， 同时还要为它们的调用者提供这一坏消息。 此外， 未预料到的新设备的添加可能导致内核重新配置资源（例如中断请求线） ， 从驱动程序中撤除旧资源， 并且在适当位置填入新资源。

　　驱动程序不允许进行系统调用， 但是它们经常需要与内核的其余部分进行交互。 对某些内核过程的调用通常是允许的。 例如， 通常需要调用内核过程来分配和释放硬接线的内存页面作为缓冲区。 还可能需要其他有用的调用来管理MMU、 定时器、 DMA控制器、 中断控制器等。

与设备无关的 I/O 软件

为了方便用户和提高 OS 的可适应性与可扩展性，在现代 OS 的 I/O 系统中都增加了与设备无关的 I/O 软件，以实现设备独立性(设备无关性)。其基本含义是：应用程序中所用的设备，不局限于使用某个具体的物理设备。为了实现设备独立性，必须再在设备驱动程序之上设置一层软件，称为与设备无关的 I/O 软件(设备独立性软件)。

图5-13所示的功能典型地由与设备无关的软件实现。

引入设备独立性软件的动机

　　在早期 OS 中，应用程序在使用 I/O 设备时都使用设备的物理名称，这使应用程序与系统中的物理设备直接相关。当应用进程运行时，如果所请求的物理设备(独占设备类型)已分配给其它进程，系统无法将另外相同的设备(物理设备名不同)分配给它，致使该应用进程请求 I/O 失败而被阻塞。当应用程序所需要的设备在系统中已经被更新时，该应用程序将再也无法在该系统上运行。可见应用程序直接与物理设备相关是不灵活的，I/O 设备的利用率低。

　　为了实现与设备的无关性而引入了逻辑设备和物理设备两个概念，逻辑设备是抽象的设备名，并没有指定具体的设备。只要系统中有一台该类设备未被分配，进程就不会被阻塞。与设备的无关软件还可实现 I/O 重定向，是指用于 I/O 操作的设备可以更换，而不必改变应用程序。

与设备无关的软件实现

在与设备无关的软件中，包括了执行所有设备公有操作的软件，具体有如下几项。

功能 说明
设备驱动程序的统一接口 要求每个设备驱动程序与 OS 之间都有着相同或者相近的接口，使添加一个新的设备驱动程序变得很容易
缓冲管理 为了缓和 CPU 和 I/O 设备之间的速率矛盾，需要为设备配置相应的缓冲区
差错控制 设备中的机械和电气部分比主机更容易出现故障，因此需要对差错进行处理
对独立设备的分配与回收 为了避免诸进程对独占设备的争夺，必须由系统来统一分配，不允许进程自行使用
独立于设备的逻辑数据块 不同类型的设备的数据交换单位和读取、传输速率相同，设备独立性软件应能够隐藏这些差异

其中设备的错误可分为如下两类：

设备错误 说明
暂时性错误 因发生暂时性事件引起的，如电源的波动，可以通过重试操作来纠正
持久性错误 由持久性故障引起的，如电源掉电、磁盘上有划痕或者在计算中发生除以零的情况等

设备名映射

当应用程序请求使用 I/O 设备时应当用逻辑设备名。但系统只识别物理设备名，因此在系统中需要配置一张逻辑设备表，用于将逻辑设备名映射为物理设备名。逻辑设备表 LUT(Logical Unit Table)的每个表目中包含了三项：逻辑设备名、物理设备名和设备驱动程序的入口地址。当进程用逻辑设备名请求分配 I/O 设备时，系统为它分配一台相应的物理设备，并在逻辑设备表上建立一个表目。当以后进程再利用该逻辑设备名请求 I/O 操作时，系统通过查找 LUT 可找到该逻辑设备所对应的物理设备和该设备的驱动程序。

在系统中可采取两种方式设置逻辑设备表，第一种方式是在整个系统中只设置一张 LUT。由于系统中所有进程的设备分配情况都记录在同一张 LUT 中，因而不允许在 LUT 中具有相同的逻辑设备名，在多用户环境下这通常是难以做到的。第二种方式是为每个用户设置一张 LUT，每当用户登录时，系统便为该用户建立一个进程，同时也为之建立一张 LUT 放入进程的 PCB 中。

用户层的 I/O 软件

大部分的 I/O 软件都放在操作系统内部，但仍有一小部分在用户层，其中包括与用户程序链接在一起的库函数和假脱机系统。

系统调用

为使诸进程能有条不紊地使用 I/O 设备，且能保护设备的安全性，不允许运行在用户态的应用进程去直接调用运行在核心态（系统态）的 OS 过程。但另一方面，应用进程在运行时，又必须取得 OS 所提供的服务。为了解决此矛盾，OS 在用户层中引入了系统调用，应用程序可以通过它间接调用 OS 中的 I/O 过程。

当应用程序需要执行某种 I/O 操作时，在应用程序中必须使用相应的系统调用。当 OS 捕获到应用程序中的该系统调用后，便将 CPU 的状态从用户态转换到核心态，然后转向操作系统中相应过程，由该过程完成所需的 I/O 操作。执行完成后，系统又将 CPU 状态从核心态转换到用户态，返回到应用程序继续执行。

在早期的操作中，系统调用是以汇编语言形式提供的，所以只有在用汇编语言编写的程序中，才能直接使用系统调用。后来在 C 语言中，首先提供了与系统调用相对应的库函数。库函数对于 I/O 方面，主要是对文件和设备进行读/写的库函数，以及控制/检查设备状态的库函数。

假脱机系统

假脱机(SPOOLing)技术，则可将一台物理 I/O 设备虚拟为多台逻辑 I/O 设备，这样就允许多个用户共享一台物理 I/O 设备。SPOOLing 的系统组成如下：

组成部分 说明
输入井 在磁盘上开辟出来的存储区域，输入井模拟脱机输入时的磁盘，用于收容 I/O 设备输入的数据
输出井 在磁盘上开辟出来的存储区域，输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据
输入缓冲区 在内存上开辟出来的存储区域，用于暂存由输入设备传送的数据，之后再传送到输入井
输出缓冲区 在内存上开辟出来的存储区域，用于暂存从输出井传送的数据，之后再传送到输出设备
输入进程 用于模拟脱机输入时的外围控制机，将用户要求的数据从输入设备传送到输入缓冲区
输出进程 用于模拟脱机输出时的外围控制机，将输出井中的数据经过输出缓冲区输出至输出设备上
井管理程序 用于控制作业与磁盘井之间信息的交换

SPOOLing 系统有以下特点：

  1. 提高了 I/O 的速度：从对低速 I/O 设备执行的 I/O 操作演变为对磁盘缓冲区中数据的存取；
  2. 将独占设备改造为共享设备；
  3. 实现了虚拟设备功能：宏观上虽然是多个进程在同时使用一台独占设备，而对于每一个进程而言，它们都会认为自己是独占了一个设备。

假脱机打印机

　　打印机是经常用到的输出设备，属于独占设备，利用假脱机技术可将它改造为一台可供多个用户共享的打印设备。假脱机打印系统主要有以下三部分：

部分 说明
磁盘缓冲区 在磁盘上开辟的一个存储空间，用于暂存用户程序的输出数据
打印缓冲区 设置在内存中，暂存从磁盘缓冲区送来的数据，以后再传送给打印设备进行打印
假脱机管理进程 为每个要求打印的用户数据建立一个假脱机文件，并把它放入假脱机文件队列中
假脱机打印进程 依次对队列中的文件进行打印

　　当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：

  1. 在磁盘输出井中为进程申请一个空闲缓冲区，并将要打印的数据送入其中；
  2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中，再将该表挂到假脱机文件队列上。

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

I/O硬件原理*

I/O设备

　　I/O 就是输入/输出(Input/Output)，I/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。I/O 设备一般是由执行 I/O 操作的机械部分和执行控制 I/O 的电子部件组成，I/O 设备的机械部件主要用来执行具体 I/O 操作，例如鼠标/键盘的按钮、显示器的 LED 屏和移动硬盘的磁臂、磁盘盘面。

　　CPU 无法直接控制 I/O 设备的机械部件，因此 I/O 设备还要有一个电子部件作为 CPU 和 I/O 设备机械部件之间的“中介”，用于实现 CPU 对设备的控制。这个电子部件就是 I/O 控制器，又称设备控制器，通常是一块插入主板扩充槽的印刷电路板。CPU 可控制 I/O 控制器，又由 I/O 控制器来控制设备的机械部件。

I/O设备类型

按数据组织分：

  • 块设备：这类设备用于存储信息，信息以数据块为单位，如磁盘，每个盘块512B~4KB，传输速率较高，通常每秒钟几兆位，另一特征是可寻址，即对它可随机地读/写任一块，磁盘设备的I/O常采用DMA方式。
  • 字符设备：用于数据的输入和输出，其基本单位是字符，属于无结构类型，如打印机等，其传输速率较低，通常为几个字节至数千个字节，另一特征是不可寻址，即输入/出时不能指定数据的输入源地址及输出的目标地址，此外，常采用中断驱动方式。

按资源分配：

  • 独占设备：在一段时间内只允许一个用户（进程）访问的设备，即临界资源。
  • 共享设备：在一段时间内允许多个进程同时访问的设备，当然，每一时刻仍然只允许一个进程访问，如磁盘（可寻址和可随机访问）。
  • 虚拟设备：通过虚拟技术将一台设备变换为若干台逻辑设备，供若干个用户（进程）同时使用。常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚设备。目的：将慢速的独占设备改造为多个用户共享设备，提高设备利用率。例如：spooling技术，利用虚设备技术——用硬盘模拟输入输出设备。

按使用特性分配：

  • 存储设备：也称外存、辅存，用以存储信息，存取速度较内存慢但容量大且价格便宜。

  • I/O设备：

    • 输入设备：用来接收外部信息，如键盘、鼠标、扫描仪、视频摄像等
    • 输出设备：用于将计算机处理后的信息送向处理机外部的设备，如打印机、绘图仪等
    • 交互式设备：则是指集成的上述两类设备，用于同步显示用户命令以及命令执行的结果

按传输速度分配：

  • 低速设备：传输速率仅为每秒钟几个字节至数百个字节，例如键盘、鼠标器
  • 中速设备：传输速率在每秒钟数千个字节至数十万个字节，例如行式打印机、激光打印机等
  • 高速设备：传输速率在数十万字节至千兆字节，例如磁带机、磁盘机、光盘机等

I/O设备组成

I/O设备一般由机械和电子两部分组成。

  • 机械部分是设备本身（物理装置）

  • 电子部分又称设备控制器（或适配器）

    • （端口）地址译码
    • 按照主机与设备之间约定的格式和过程接受计算机发来的数据和控制信号或向主机发送数据和状态信号
    • 将计算机的数字信号转换成机械部分能识别的模拟信号，或反之
    • 实现设备内部硬件缓冲、数据加工等提高性能或增强功能

设备与控制器之间的接口

　　通常设备并不是直接与 CPU 进行通信，而是与设备控制器通信，因此在 I/O 设备中应含有与设备控制器间的接口。

在该接口中有三种类型的信号，各对应一条信号线。

信号线 说明
数据信号线 在设备和设备控制器之间传送数据信号
控制信号线 由设备控制器向 I/O 设备发送控制信号时的通路，信号规定了设备将要执行的操作，如读操作、写操作或执行磁头移动等操作
状态信号线 该信号线用于传送指示设备当前状态的信号，状态有正在读(或写)、设备已读(写)完成

设备控制器

　　设备控制器是计算机中的一个实体，其主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换，它是CPU与I/O设备之间的接口，它接收从CPU发来的命令，并去控制I/O设备工作，以使处理从繁杂的设备控制事务中解脱出来。其是一个可编址的设备，当它仅控制一个设备时，它只有一个唯一的设备地址，若控制器可连接多个设备时，则应该含有多个设备地址，并使每个设备地址对应一个设备。每一个设备地址对应一个设备。设备控制器可以分为用于控制字符设备的控制器和用于控制块设备的控制器。

　　设备控制器的基本功能如下

　　① 接收和识别命令，CPU可以向控制器发送多种不同的命令，设备控制器应能够接收并识别这些命令，为此，控制器中应具有相应的控制寄存器，用来存放接收的命令和参数，并对所接收的命令进行译码，相应的，在磁盘控制器中有多个寄存器和命令译码器。当控制器接受一条命令后，可独立于CPU完成指定操作，CPU可以另外执行其他计算；命令完成时，控制器产生一个中断，CPU响应中断，控制转给操作系统；通过读控制器寄存器中的信息，获得操作结果。

　　② 数据交换，实现CPU与控制器之间、控制器与设备之间的数据交换，对于前者，通过数据总线，由CPU并行地将数据写入控制器，或从控制器中并行地读出数据，对于后者，是是被将数据输入到控制器，或从控制器传送给设备，为此，在控制器中必须设置一个数据寄存器。

　　③ 标识和报告设备的状态，控制器应该几下设备的状态供CPU了解，在控制器中设置一状态寄存器，用其中的每一位来反映设备的某一种状态，当CPU将该寄存器的内存读入后，便可了解该设备的状态。

　　④ 地址识别，系统中的每一个设备都有一个地址，而设备控制器又必须能够识别它所控制的每个设备的地址，此外，为使CPU能向（或从）寄存器中写入（或读出）数据，这些寄存器都应该具有唯一的地址，如硬盘控制器中各寄存器的地址分别为320~32F之一，控制器应该能正确识别这些地址，为此，需要在控制器中配置地址译码器。

　　⑤ 数据缓冲，由于I/O设备的速率较低而CPU和内存速率很高，故在控制器中必须设置一个缓冲器，在输出时，用此缓冲器暂存由主机高速传来的数据，然后才以I/O设备所具有的速率将缓冲器的数据传送给I/O设备，在输入时，缓冲器则用于暂存从I/O设备送来的数据，待接收一批数据后，再将缓冲器中的数据高速地传送至主机。

　　⑥ 差错控制，设备控制器监管对I/O设备传送来的数据进行差错检测，若发现传送中出现了错误，则向CPU报告，于是CPU将本次传送的数据作废，并重新传送一次，这样便可以确保数据输入的正确性。

设备控制器的组成

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

组件 说明
设备控制器与处理机的接口 用于实现 CPU 与设备控制器之间的通信，在该接口中共有三类信号线：数据线、地址线和控制线
设备控制器与设备的接口 设备控制器上可以连接多个设备，便有多个设备接口。在每个接口中都存在数据、控制和状态三种类型的信号
I/O 逻辑 用于实现对设备的控制，它通过一组控制线与处理机交互，处理机利用该逻辑向控制器发送 I/O 命令。

数据线通常与两类寄存器相连接，第一类是数据寄存器，用于存放从设备送来的数据(输入)或从 CPU 送来的数据(输出)。第二类是控制/状态寄存器，用于存放从CPU送来的控制信息或设备的状态信息。

I/O端口地址

I/O端口地址：接口电路中每个寄存器具有的、唯一的地址，是个整数。

所有I/O端口地址形成I/O端口空间（受到保护）

I/O指令形式与I/O地址是相互关联的，主要两种形式：

  • 内存映像编址（内存映像I/O模式）
  • I/O独立编址（I/O专用指令）

I/O独立编址

分配给系统中所有端口的地址空间完全独立，与内存地址空间无关

使用专门的I/O指令对端口进行操作

优点：

  • 外设不占用内存的地址空间；
  • 编程时易于区分时对内存操作还是对I/O端口操作

缺点：I/O端口操作的指令类型少，操作不灵活

内存映像编址

分配给系统中所有端口的地址空间与内存的地址空间统一编址

把I/O端口看作一个存储单元，对I/O的读写操作等同于对内存的操作

优点：

  • 凡是可对内存操作的指令都可对I/O端口操作
  • 不需要专门的I/O指令
  • I/O端口可占有较大的地址空间

缺点：占用内存空间

内存映像

　　驱动程序将抽象 I/O 命令转换出的一系列具体的命令、参数等数据装入设备控制器的相应寄存器，由控制器来执行这些命令实施对 I/O 设备的控制。这一工作在早期的计算机中利用特定的 I/O 指令实现，为每个控制寄存器分配一个 I/O 端口并设置了一些特定的 I/O 指令。该方法的主要缺点是，访问内存和访问设备需要两种不同的指令。

现在采用的是内存映像 I/O，这种方式中在编址上不再区分内存单元地址和设备控制器中的寄存器地址，而是设置一个 k 值。当 k 值处于 0 ~ n-1 范围时被认为是内存地址，若 k ≥ n 时被认为是某个控制器的寄存器地址。内存映像 I/O 方式统一了对内存和对控制器的访问方法，简化 I/O 的编程。

内存映射I/O的优点

  • 不需要特殊的保护机制来阻止用户进程执行I/O操作；

    • 操作系统必须要做的事情：避免把包含控制寄存器的那部分地址空间放入任何用户的虚拟地址空间之中

  • 可以引用内存的每一条指令也可以引用控制寄存器

    • 例如：如果指令TEST可以测试一个内存字是否为0，那么也可以用来测试一个控制寄存器是否为0

I/O 通道*

引入 I/O 通道的动机

　　虽然在 CPU 与 I/O 设备之间增加了设备控制器后能减少 CPU 对 I/O 的干预，但当主机所配置的外设很多时 CPU 的负担仍然很重。为此在 CPU 和设备控制器之间又增设了I/O 通道(I/O Channel)。主要目的是使一些原来由 CPU 处理的 I/O 任务转由通道来承担，从而把 CPU 从繁杂的 I/O 任务中解脱出来。

　　在设置了通道后，CPU 只需向通道发送一条 I/O 指令，通道从内存中取出本次要执行的通道程序然后执行。仅当通道完成了规定的 I/O 任务后，才向 CPU 发中断信号。实际上 I/O 通道是一种特殊的处理机，它具有执行 I/O 指令的能力，通过执行通道 I/O 程序来控制 I/ O操作。但 I/O 通道的指令类型单一，且没有自己的内存。

通道类型

外围设备的类型较多，传输速率相差甚大，因而使通道具有多种类型。根据信息交换方式的不同，可把通道分成以下三种类型。

通道 说明
字节多路通道(Byte Multiplexor Channel) 按字节交叉方式工作的通道，通常都含有许多非分配型子通道，按时间片轮转方式共享主通道，当第一个子通道控制其 I/O 设备完成一个字节的交换后，便立即腾出主通道让给第二个子通道使用
数组选择通道(Block Selector Channel) 按数组方式进行数据传送的数组选择通道，可以连接多台高速设备，但它只含有一个分配型子通道，在一段时间内只能执行一道通道程序
数组多路通道(Block Multiplexor Channel) 将数组选择通道传输速率高和字节多路通道能使各子通道（设备）分时并行操作的优点相结合，它含有多个非分配型子通道，既具有很高的数据传输速率，又能获得令人满意的通道利用率

瓶颈问题

　　由于通道价格昂贵，致使机器中所设置的通道数量势必较少，这往往又使它成了 I/O 的瓶颈，进而造成整个系统吞吐量的下降。例如在图中如果要使用设备 1 需要占用通道 1 和控制器 1，但此时如果还要使用设备 2，会因为通道和控制器数量不足而无法使用。

解决“瓶颈”的方法是增加设备到主机间的通路而不增加通道，也就是把一个设备连接到多个控制器上，而一个控制器又连接到多个通道上。

I/O控制方式

　　在 I/O 控制方式的整个发展过程中，始终贯穿着这样一条宗旨：尽量减少主机对 I/O 控制的干预，把主机从繁杂的 I/O 控制事务中解脱。

程序I/O方式（轮询/查询）

　　在早些计算机系统中，由于无中断机构，处理机对I/O设备的控制采取程序I/O方式，或称为忙-等待方式，即在处理机向控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy设置为1，然后便不断地循环测试busy，只有当其为0时，表示输入已经送入控制器的数据寄存器中，于是处理机将数据寄存器中的数据取出，送入内存指定单元中，这样便完成了一个字（符）的I/O。

　　在程序I/O方式中，由于CPU的高速性和I/O设备的低速性，致使CPU的绝大部分时间都处于等待I/O设备完成数据I/O的循环测试中，造成对CPU的极大浪费。

中断驱动I/O控制方式

　　当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务，设备控制器于是按照该命令的要求去控制指定I/O设备，此时，CPU与I/O设备并行操作。一旦数据进入数据寄存器，控制器便通过控制线向CPU发送一个中断信号，由CPU检查输入过程中是否出错，若无错，便由控制器发送取走数据的信号，再通过控制器及数据线将数据写入内存指定单元中。

　　在I/O设备输入每个数据的过程中，由于无需CPU干预，因而可使CPU与I/O设备并行工作，仅当完成一个数据输入时，才需CPU花费极短的时间去做一些中断处理。

直接存储器访问（DMA）I/O控制方式

虽然中断驱动I/O比程序I/O方式更有效，但是，它仍是以字（节）为单位进行I/O的，每当完成一个字（节）的I/O时，控制器便要向CPU请求一次中断，换言之，采用中断驱动I/O方式时的CPU是以字（节）为单位进行干预的，将这种方式用于块设备的I/O是非常低效的，例如，为了从磁盘读取1KB的数据块，需要中断CPU1K次，为了进一步减少CPU对I/O的干预而引入了直接存储器访问方式DMA (Direct Memory Access)，该方式的特点如下

　　① 数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块。

　　② 所传送的数据是从设备直接送入内存的，或者相反。

　　③ 仅在传送一个或多个数据块的开始和结束时，需要CPU干预，整块数据的传送是在控制器的控制下完成的。

当给 I/O 模块发送命令时，CPU 指明此次要进行的操作，并说明要读入多少数据、数据要存放在内存的什么位置数据在外部设备上的地址。控制器会根据 CPU 提出的要求完成数据的读/写工作，整块数据的传输完成后，才向 CPU 发出中断信号。

DMA控制器由三部分组成，主机与DMA控制器的接口；DMA控制器与块设备的接口；I/O控制逻辑。

说明：DMA控制器中的寄存器说明如下

　　① 命令/状态寄存器（CR），用于接收从CPU发送来的I/O命令，或有关控制信息，或设备的状态。

　　② 内存地址寄存器（MAR），在输入时，它存放把数据从设备传送到内存的起始目标地址，在输出时，它存放由内存到设备的内存源地址。

　　③ 数据寄存器（DR），用于暂存从设备到内存，或从内存到设备的数据。

　　④ 数据计数器（DC），存放本次CPU要读或写的字（节）数。

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

DMA 的优点是数据传输以“块”为单位，CPU 介入频率进一步降低。数据的传输不再需要先经过C PU 再写入内存，数据传输效率进一步增加，CPU 和 I/O 设备的并行性得到提升。缺点是 CPU 每发出一条 I/O 指令，只能读/写一个或多个连续的数据块。下图展示了三种不同方式的流程。

I/O 通道控制方式

　　I/O 通道方式是 DMA 方式的发展，它把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。同时，又可实现 CPU、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。不过实现复杂，需要专门的通道硬件支持。

　　例如当 CPU 要完成一组相关的读(或写)操作及有关控制时，只需向 I/O 通道发送一条 I/O 指令，以给出其所要执行的通道程序的首址和要访问的 I/O 设备。通道接到该指令后，通过执行通道程序便可完成 CPU 指定的 I/O 任务。

设备分配

“设备、控制器、通道”之间的关系是一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。

设备分配中的数据结构

　　系统为实现对独占设备的分配，必须在系统中配置相应的数据结构，记录了对设备或控制器进行控制所需的信息。系统为每一个设备都配置了一张设备控制表 DCT，用于记录设备的情况。

字段 说明
设备队列队首指针 凡因请求本设备而未得到满足的进程，应将其 PCB 按照一定的策略排成一个设备请求队列
忙/闲标志 用于表示当前设备的状态是忙或闲
与设备连接的控制器表指针 指向该设备所连接的控制器的控制表
重复执行次数 设备在工作中发生错误时应重复执行的次数

系统为每一个控制器都设置了用于记录控制器情况的控制器控制表 COCT。

每个通道都有一张通道控制表 CHCT。

系统设备表 SDT 是系统范围的数据结构，记录了系统中全部设备的情况，每个设备占一个表目，其中包括有设备类型、设备标识符、设备控制表及设备驱动程序的入口等项。

独占设备的分配

在申请设备时，,如果设备空闲，就将其独占，不再允许其他进程申请使用，一直等到该设备被释放，才允许被其他进程申请使用。须考虑效率问题，并避免由于不合理的分配策略造成死锁。

  • 静态分配：在进程运行前，完成设备分配；运行结束时，收回设备。缺点：设备利用率低。

  • 动态分配：在进程运行过程中，当用户提出设备要求时，进行分配，一旦停止使用立即收回。优点：效率高；缺点：分配策略不好时，产生死锁。

分时共享设备的分配

分时共享就是以一次I/O为单位分时使用设备，不同进程的I/O操作请求以排队方式分时地占有设备进行I/O。由于同时有多个进程同时访问，就会影响整个设备使用效率，影响系统效率。因此要考虑多个访问请求到达时服务的顺序使平均服务时间越短越好。

设备分配的因素

系统在分配设备时，应考虑如下几个因素：

设备的固有属性

设备的固有属性可分成三种，对它们应采取不同的分配策略：

固有属性 说明
独占设备的分配策略 将一个设备分配给某进程后，便由该进程独占
共享设备的分配策略 对于共享设备，可同时分配给多个进程使用
虚拟设备的分配策略 虚拟设备属于可共享的设备

设备分配算法

对设备分配的算法，通常只采用以下两种分配算法：

分配算法 说明
先来先服务 根据诸进程对某设备提出请求的先后次序，将这些进程排成一个设备请求队列
优先级高者优先 将优先级高的进程排在设备队列前面，而对于优先级相同的 I/O 请求，则按先来先服务原则排队

设备分配中的安全性

从进程运行的安全性上考虑，设备分配有以下两种方式：

分配方式 说明
安全分配方式 为进程分配一个设备后就将进程阻塞，本次 I/O 完成后才将进程唤醒
不安全分配方式 进程发出 I/O 请求后，系统为其分配 I/O 设备，之后还可以发出新的 I/O 请求

设备分配的步骤

只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动 I/O 设备进行数据传送。

  1. 根据进程请求的物理设备名查找 SDT；
  2. 分配设备，根据 SDT 找到 DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程；
  3. 分配控制器，根据 DCT 找到 COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程；
  4. 分配通道，根据 COCT 找到 CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

为获得设备的独立性，进程应使用逻辑设备名请求 I/O。这样系统首先从 SDT 中找出第一个该类设备的 DCT，若该设备忙又查找第二个该类设备的 DCT，仅当所有该类设备都忙时，才把进程挂在该类设备的等待队列上。

缓冲技术

  • 解决CPU与I/O设备之间速度不匹配问题：凡是数据到达和离去速度不匹配的地方均可采用缓冲技术
  • 提高CPU与I/O设备之间的并行性
  • 减少了I/O设备对CPU的中断请求次数，放宽CPU对中断响应时间的要求

缓冲区

　　缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合(如存储器管理中所用的联想寄存器）一般情况下利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区。

　　引入缓冲区的原因有：

  1. 缓和 CPU 与 I/O 设备间速度不匹配的矛盾：CPU 的运算速率远远高于 I/O 设备的速率，如果没有缓冲区，在运行时会因为 I/O 设备跟不上 CPU 的速度导致 CPU 停下来等待；
  2. 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制。随着传输速率的提高，需要配置位数更多的寄存器进行缓冲；
  3. 解决数据粒度不匹配的问题：生产者所生产的数据粒度比消费者小时，生产者进程可以一连生产多个数据单元的数据。生产者比消费者粒度大时，生产者每次生产的数据消费者可以分几次从缓冲区中取出消费；
  4. 提高 CPU 和 I/O 设备之间的并行性：生产者在生产了一批数据并将它放入缓冲区后，便可立即去进行下一次的生产。

缓冲区分类

  • 硬缓冲：由硬件寄存器实现（例如：设备中设置的缓冲区）

  • 软缓冲：在内存中开辟了一个空间，用作缓冲区

缓冲区管理：

  • 单缓冲

  • 双缓冲

缓冲池（多缓冲，循环缓冲）：统一管理多个缓冲区，采用有界缓冲区的生产者/消费者模型对缓冲池中的缓冲区进行循环使用

单缓冲区

假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲(Single Buffer)的策略，操作系统会在主存中为其分配一个缓冲区。当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出。当缓冲区为空时可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。

假定从磁盘把一块数据输入到缓冲区的时间为 T，OS 将该缓冲区中的数据传送到用户区的时间为 M，CPU 数据处理(计算)的时间为C。由于 T 和 C 是可以并行的，当 T > C 时系统对每一块数据的处理时间为 M + T，反之则为M + C，故可把系统对每一块数据的处理时间表示为 Max(C,T) + M。

双缓冲区

由于缓冲区是共享资源，生产者与消费者在使用缓冲区时必须互斥。如果消费者尚未取走缓冲区中的数据，即使生产者又生产出新的数据，也无法将它送入缓冲区，生产者等待。

如果设置了两个缓冲区能解决这一问题，同时可以加快输入和输出速度，提高设备利用率。双缓冲区机制(Double Buffer)也称缓冲对换(Buffer Swapping)，在设备输入时先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据，并送入用户进程，接着由 CPU 对数据进行计算。

在双缓冲时系统处理一块数据的时间可以粗略地认为是 Max(C，T)，如果 C < T 可使块设备连续输入，如果 C > T 则可使 CPU 不必等待设备输入。对于字符设备，若采用行输入方式，在 CPU 执行第一行中的命令时，用户可继续向第二缓冲区输入下一行数据。

　　如果在实现两台机器之间的通信时仅为它们配置了单缓冲，那么它们之间在任一时刻只能实现半双工的数据传输。为了实现全双工数据传输，必须在两台机器中都设置两个缓冲区，一个用作发送缓冲区，另一个用作接收缓冲区。

环形缓冲区

若两个缓冲区的速度相差甚远，双缓冲的效果则不够理想，不过可以通过缓冲区数量的增加来改善。多缓冲机制可将多个缓冲区组织成环形缓冲区形式，在环形缓冲中包括多个缓冲区，其每个缓冲区的大小相同。

作为输入的多缓冲区可分为三种类型：用于装输入数据的空缓冲区 R、已装满数据的缓冲区 G 以及计算进程正在使用的现行工作缓冲区 C。作为输入的缓冲区可设置三个指针：用于指示计算进程下一个可用缓冲区 G 的指针 Nextg、指示输入进程下次可用的空缓冲区 R 的指针 Nexti，以及用于指示计算进程正在使用的缓冲区 C 的指针 Current。

使用输入循环缓冲，可使输入进程和计算进程并行执行,相应地指针 Nexti 和 Nextg 将不断地沿着顺时针方向移动。这样就可能出现下 Nexti 指针追赶上 Nextg 指针，这意味着输入进程输入数据的速度大于计算进程处理数据的速度。也有可能出现 Nextg 指针追赶上 Nexti 指针，这意味着输入数据的速度低于计算进程处理数据的速度。

缓冲池

当系统较大时会存在大量的循环缓冲，这不仅要消耗大量的内存空间，而且其利用率不高。目前广泛流行既可用于输入又可用于输出的公用缓冲池，在池中设置了多个可供若干个进程共享的缓冲区。缓冲池与缓冲区的区别在于，缓冲区仅仅是一组内存块的链表，而缓冲池则是包含了一个管理的数据结构及一组操作函数的管理机制。

缓冲池管理着多个缓冲区，每个缓冲区由用于标识和管理的缓冲首部以及用于存放数据的缓冲体两部分组成。缓冲首部一般包括缓冲区号、设备号、设备上的数据块号、同步信号量以及队列链接指针等。为了管理上的方便，一般将缓冲池中具有相同类型的缓冲区链接成一个队列，于是可形成以下三个队列。除了三个队列外，还应具有四种工作缓冲区：用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区、用于收容输出数据的工作缓冲区，以及用于提取输出数据的工作缓冲区。

队列 说明
空白缓冲队列 emq 由空缓冲区所链成的队列
输入队列 inq 由装满输入数据的缓冲区所链成的队列
输出队列 outq 由装满输出数据的缓冲区所链成的队列

缓冲区可以有如下 4 个工作方式：

  1. 输入进程请求输入数据；
  2. 计算进程想要取得一块输入数据；
  3. 计算进程想要将准备好的数据冲入缓冲区；
  4. 输出进程请求输出数据。

I/O性能问题

  • 利用缓冲技术解决CPU与I/O设备之间速度不匹配问题
  • 利用异步I/O使CPU不等待I/O
  • 利用DMA和通道让CPU摆脱I/O操作

windows提供了两种模式的I/O

  • 异步：应用程序启动I/O操作，然后再I/O请求执行的同时继续处理

    • 系统实现：

      • 通过切换进程保证CPU利用率
      • 对少量数据的I/O操作会引入切换的开销

    • 用户实现：

      • 将访问控制分成两段进行
      • 发出读取指令后继续做其他操作
      • 当需要用读入的数据的时候，在使用wait命令等待其完成
      • 不引入线程切换，减少开销

  • 同步：应用程序被阻塞直到I/O操作完成