操作系统概念（原书第9版）笔记

本文为操作系统概念（原书第9版）学习笔记，仅涉及本书的前4部分，为课上老师教授部分。

操作系统概念

目录

一 概论

Chapter 1 导论

1.1 操作系统的功能

  • 计算机系统：硬件——OS——应用程序——用户
    • 硬件：如 $CPU$、内存、$I/O$ 设备，为系统提供基本的计算资源。
    • 操作系统：控制硬件，并协调各个用户应用程序的硬件使用。
    • 应用程序：规定了用户为解决计算问题而使用这些资源的方式。
1.1.1 用户视角
  • pc 机：主要目的是使用方便，次要的是性能，不在乎的是资源利用率；
  • 大型机（mainframe）或小型机（minicomputer）：设计目标是优化资源使用率；
  • 工作站（workstation）：兼顾使用方便性和资源利用率。
1.1.2 系统视角
  • 资源分配器（resource allocator）：面对许多甚至冲突的资源请求，操作系统应考虑如何为各个程序和用户分配资源，以便计算机系统能有效且公平地运行。
  • 控制程序（control programmer）：管理用户程序的执行，以放置计算机资源的错误或不当使用。特别注重I/O设备的运行和控制。
1.1.3 操作系统的定义
  • 摩尔定律（Moore‘s Law）
  • 内核（Kernel）：一直运行在计算机上的程序。
  • 系统程序（system program）：于系统运行有关的程序，但不是内核的一部分。
  • 用户程序（user program）：与系统运行无关的所有其他程序。

1.2 计算机系统的组成

1.2.1 计算机系统的运行

  • 引导程序（bootstrap program）：当计算机电源打开或重启以便开始运行时，运行的初始程序，初始化系统的各个组件，定位操作系统内核并且加入到内存。位与计算机的固件。

  • 中断（interrupt）

    image-20201115110730974

  • 中断向量（interrupt vector）：包含所有服务实例的地址。对于任一给定的中断请求，可通过唯一的设备号来索引，进而提供设备的中断处理程序的地址。

  • CPU 和 I/O 可以并发执行。

1.2.2 存储结构
  • 主存：随机访问，易失性。
  • 二级存储：对主存的延展，非易失的。
  • *三级存储：包括磁带驱动器以及磁带、CD/DVD 驱动器及光盘等。
  • 高速缓存
1.2.3 I/O结构
  • 设备驱动程序（device driver）
  • 直接内存访问（Direct Memory Access，DMA）：在为这种I/O设备设置好缓冲、指针和计数器之后，设备控制器可以在本地缓冲和内存之间传送整块的数据，而无须CPU的干预。每块只产生一个中断，来告知设备驱动程序操作已经完成，而不是像低速设备那样每个字节产生一个中断。

1.3 计算机系统的体系结构

1.3.1 单处理器系统
1.3.2 多处理器系统
  • 增加吞吐量
  • 经济规模
  • 增加可靠性：适度退化（graceful degradation），容错（fault tolerant）
  • 非对称处理（asymmetric multiprocessing）：每个处理器都有各自特定的任务。一个主处理器（boss processor）控制系统，其他处理器或者向主处理器要任务或做预先规定的任务。这种方案称为主从关系。
  • 对称多处理（Symmetric MultiProcessing，SMP）：每个处理器都参与完成操作系统的所有任务。
1.3.集群系统
  • 集群系统（clustered system）：有两个或多个独立系统（节点）组成。松耦合的（loosely coupled），每个节点可为单处理器系统或多核系统。
    • 提供高可用性服务
    • 提供高性能计算
  • 非对称集群（asymmetric cluster）：一台机器处于热备份模式（hot-standby mode），而另一台运行应用程序。热备份主机只监视活动服务器。如果活动服务器失效，那么热备份主机变成活动服务器。
  • 对称集群（symmetric cluster）：所有主机都运行应用程序，并互相监视。当有多个应用可供执行时，这种结构更高效。

1.4 操作系统的结构

  • 多道程序设计（multiprogramming）：通过安排作业（编码与数据）使得CPU总有一个执行作业，从而提高CPU使用率。
  • 分时系统（time sharing）：CPU 频繁地切换工作，使得用户能够在进程运行时进行交互。响应时间通常小于 $1$ 秒。

1.5 操作系统的执行

1.5.1 双重模式与多重模式的执行
  • 用户模式（user mode）：
  • 内核模式（kernel mode）：也称为监视模式、系统模式或特权模式。
  • 计算机硬件可以通过一个位模式（mode bit）来表示当前模式：内核（0）和用户（1）。
1.5.2 定时器（Timer）
  • 定时器：可以在指定周期后中断计算机。
    • 在将控制交到用户之前，操作系统确保定时器已设置好以便产生中断。
    • 定时器可以防止用户程序运行过长。

1.6 进程管理

  • 在 CPU 上调度进程和线程
  • 创建和删除用户进程和系统进程
  • 挂起和重启进程
  • 提供进程同步机制
  • 提供进程通信机制

1.7 内存管理

  • 记录内存的哪部分在被使用以及被谁使用
  • 决定哪些进程会调入或调出内存
  • 根据需要分配和释放内存空间

1.8 存储管理

1.8.1 文件系统管理
  • 操作系统负责文件系统管理的以下活动：
    • 创建和删除文件
    • 创建和删除目录，以便组织文件
    • 提供文件和目录的操作原语
    • 映射文件到外存
    • 备份文件到稳定（非易失的）的存储介质
1.8.2 大容量存储器管理
  • 操作系统负责硬盘管理的一下活动：
    • 空闲空间管理
    • 存储空间分配
    • 硬盘调度
1.8.3 高速缓存
  • 高速缓存一致性
1.8.4 I/O 设备
  • I/O 子系统的组件
    • 包括缓冲、高速缓存和假脱机的内存管理组件
    • 设备驱动器的通用接口
    • 特定硬件设备的驱动程序

1.9 保护与安全

  • 保护（protection）：是一种机制，用于控制进程或用户访问计算机系统的资源。

  • 安全（security）：防止系统不受外部或内部的攻击。

  • 用户标识（User ID，UID）

1.10 内核数据结构

1.10.1 列表、堆栈及队列
1.10.2 树
1.10.3 哈希函数和哈希表
1.10.4 位图

1.11 计算环境

1.11.1 传统计算
1.11.2 移动计算
1.11.3 分布计算
1.11.4 客户机-服务器计算
  • 服务器系统分类
    • 计算服务器系统：提供接口，一边客户发送请求以执行操作。
    • 文件服务器系统：提供文件系统接口，以便客户机可以创建、更新和删除文件。
1.11.5 对等计算
1.11.6 虚拟化
1.11.7 云计算
1.11.8 实时嵌入式系统

1.12 开源操作系统

Chapter 2 操作系统结构

重点：用户界面、命令实现的方法、三组常见的API、三种传参方法、六种系统调用、两种进程间通信模型、分层设计的优点缺点和难点、微内核的主要功能及优点、可加载内核模块及优点、Android运行时环境、核心转储和崩溃转储

2.1 操作系统的服务

  • 用于提供用户功能的服务：

    • 用户界面（User Interface）：命令行界面（CLI）与图形用户界面（GUI）
    • 程序执行
    • I/O 操作
    • 文件系统操作
    • 通信
    • 错误检测

  • 为确保系统本身运行高效的服务：

    • 资源分配
    • 记账
    • 保护与安全

2.2 用户与操作系统的界面

2.2.1 命令解释程序
  • 命令实现的两种常用方法：
    • 命令解释程序本身包含代码以执行这些命令
    • 通过系统程序实现大多数的命令
2.2.2 图形用户界面
2.2.3 界面的选择

2.3 系统调用

  • 三组常见 API

    • Windows API
    • POSIX API
    • Java API

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

    • 通过寄存器（X86-64只能使用寄存器用存储 6 个参数）
    • 通过内存的块或表
    • 通过堆栈

2.4 系统调用的类型

2.4.1 进程控制

image-20201115153455923

2.4.2 文件管理

image-20201115153508731

2.4.3 设备管理

image-20201115153642288

2.4.4 信息维护

image-20201115153654005

2.4.5 通信
  • 进程间通信的常用模型：
    • 消息传递：需要建立连接，消息交换可以直接进行也可通过共同的邮箱进行。
    • 共享内存
  • 消息传递对少量数据的交换很有用，也更容易实现。
  • 共享内存在通信方面具有高速和便捷的特点，但使用共享内存的进程在保护和同步方面存在问题。
2.4.6 保护
  • 提供控制访问计算机的系统资源的机制

2.5 系统程序

  • 系统程序（system program）：也成为系统工具（system utility），为程序开放和执行提供了一个方便的环境。

  • 系统程序的分类

    • 文件管理
    • 状态信息
    • 文件修改
    • 程序语言支持
    • 程序加载与执行
    • 通信
    • 后台服务

2.6 操作系统的设计与实现

2.6.1 设计目标
  • 从高层来说，系统设计取决于所选硬件和系统类型：批处理、分时、单用户、多用户、分布式、实时或通用。
  • 需求的两个基本大类：用户目标和系统目标。
2.6.2 机制与策略
  • 机制（mechanism）：如何做
  • 策略（policy）：做什么
  • 机制与策略的分离可以提高系统的灵活性，例如微内核只提供机制。
2.6.3 实现

2.7 操作系统的结构

2.7.1 简单结构
  • 单片系统（monolithic system）：MS-DOS，最初的UNIX
2.7.2 分层方法
  • 分层法：将操作系统分成若干层。
  • 分层法的优点
    • 简化了构造和调试。
    • 简化了系统的调试和验证。
  • 分层法的缺点：效率低
  • 分层法的难点：如何合理地定义各层。
2.7.3 微内核

image-20201115160309198

  • 微内核的主要功能：为客户端程序和运行在用户空间中的各种服务提供通信。采用消息传递的方法。
  • 微内核的优点：
    • 便于扩展操作系统；
    • 容易从一种硬件平台上移植到另一种硬件平台；
    • 安全性好
    • 可靠性高
2.7.4 模块
  • 可加载的内核模块（loadable kernel module）：目前操作系统设计的最佳方法。内核有一组核心组件，无论在启动或运行时，内核都可通过模块加载额外服务。内核提供核心服务，而其他服务可在内核运行时动态实现，且不用重新编译内核。
  • 模块化的优点：类似于一个分层系统，每个内核部分都有已定义的、受保护的接口，且比分层系统更加灵活，比微内核更有效。
2.7.5 混合系统

  • Mac OS X

    image-20201115161402595

  • iOS

    image-20201115161428264

  • Android

    image-20201115161454785

2.8 操作系统的调试

2.8.1 故障分析
  • 核心转储（core dump）：（应用程序出错）即进程内存的捕获，并保存到一个文件以便以后分析。运行程序和核心转储可用调试器来分析。
  • 崩溃转储（crash dump）：发生崩溃（crash）时，即内核故障（操作系统出错），错误信息会保存到一个日志文件，并且内存状态会保存到一个崩溃转储。
2.8.2 性能优化
2.8.3 DTrace

2.9 操作系统的生成

  • 系统生成（SYStem GENeration，SYSGEN）：对于某个特定的计算机成所，配置和生成操作系统的这一过程。

2.10 系统引导

  • 引导（booting）：加载内核以启动计算机的过程。

二 进程管理

Chapter 3 进程

重点：进程的内存结构、进程状态、PCB块、3中调度队列、长期中期短期三种调度、两种密集型程序、上下文与上下文切换、进程创建与终止、僵尸进程与孤儿进程、消息传递的类型、普通管道与命名管道。

3.1 进程概念

3.1.1 进程

  • 进程的内存结构

    • 文本段（text section）：程序代码
    • 栈（stack）：临时数据
    • 数据段（data section）：全局变量
    • 堆（heap）：动态分配的内存

  • 程序是被动实体，进程是活动实体，具有一个程序计数器用于表示下个执行命令和一组相关资源。当一个可执行文件加载到内存时，这个程序变为进程。

  • 进程本身也可以作为一个环境。

3.1.2 进程状态

image-20201115163834812

3.1.3 进程控制块
  • 进程控制块（Process Control Block，PCB）：包含许多于某个特定进程相关的信息。
    • 进程状态（process state）
    • 程序计数器（program counter）
    • CPU 寄存器（CPU register）
    • CPU 调度信息（CPU-scheduling information）：包括进程优先级、调度队列的指针和其他调度参数。
    • 内存管理信息（memory-management information）：包括基地址和界限寄存器的值、页表和段表。
    • 记账信息（accounting information）：包括 CPU 使用时间、实际使用时间、时间期限、记账数据、作业或进程数量等。
    • I/O 状态信息（I/O status information）：包括分配给进程的 I/O 设备列表、打开文件列表等。

3.2 进程调度

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

  • 进程调度器（process scheduler）：选择一个可用的进程（可能从多个可用进程集合中）到 CPU 上执行。
3.2.1 调度队列
  • 工作队列（job queue）：进程在进入系统时，加入的队列。包括系统内的所有进程。
  • 就绪队列（ready queue）：驻留在内存中的、就绪的、等待运行的进程所保存的队列。
  • 设备队列（device queue）：等待特定I/O设备的进程列表。
3.2.2 调度程序
  • 长期调度程序（long-term scheduler）：从大容量存储设备的缓冲池中选择进程，加到内存，以便执行。
  • 中期调度程序（medium-term scheduler）：可从进程从内存中移除，进而降低多道程序程度。
  • 短期调度程序（short-term scheduler）：从准备执行的进程中选择进程，并分配 CPU。
  • 多道程序程度（degree of multiprogramming）：内存中的进程数量。
  • I/O 密集型进程（I/O-bound process）
  • CPU 密集型进程（CPU-bound process）
3.2.3 上下文切换（汇编编写）
  • 进程上下文：采用 BCP 表示，包括 CPU 寄存器的值、进程状态和内存管理信息等。
  • 上下文切换（context switch）：保存当前进程状态，恢复另一个进程的状态。上下文切换的时间与硬件支持密切相关。纯粹的开销。

3.3 进程运行

3.3.1 进程创建
  • 进程树（process tree）
  • 进程标识符（process identifier，pid）
  • 子进程资源的来源
    • 从操作系统直接获得资源；
    • 从父进程获得资源子集。
  • 进程创建新进程时两种执行可能
    • 父进程与子进程并发执行；
    • 父进程等待，直到某个或全部子进程执行完。
  • 新进程的地址空间的两种可能
    • 子进程是父进程的复制品；
    • 子进程加载另一个新程序。

image-20201116200829733

3.3.2 进程终止
  • 父进程终止子进程的原因
    • 子进程使用了超过它所分配的资源；
    • 分配给子进程的任务，不再需要；
    • 父进程正在退出，而且操作系统不允许无父进程的子进程继续执行。
  • 级联终止（cascade termination）：父进程终止，其所有的子进程也都终止。
  • 僵尸进程（zombie process）：当进程已经终止，但是其父进程尚未调用 $wait( )$ 。
  • 孤儿进程（orphan process）：父进程没有调用 $wait( )$ 就终止。$Linux$ 和 $UNIX$ 将 $init$ 进程作为孤儿进程的父进程。

3.4 进程间通信

  • 进程间通信的理由
    • 信息共享（information sharing）
    • 计算加速（computation speedup）
    • 模块化（modularity）
    • 方便（convenience）
  • 进程间通信的两个基本模型
  • 对于分布式系统，消息传递也比共享内存更容易实现。
3.4.1 共享内存系统
  • 消费者 & 生产者
  • 有界缓冲区 & 无界缓冲区
  • $in == out$ （空） & $(in + 1) % BUFFER_SIZE == out$（满）
3.4.2 消息传递模型
  • 直接或间接的通信
    • 直接通信（direct communication）：对称寻址：需要通信的每个进程必须明确指定通信的接收者或发送者；非对称寻址：只用发送者指定接收者，而接收者不需要指定发送者。
    • 间接通信（indirect communication）：通过邮箱或者端口来收发消息。
  • 同步或异步的通信
    • 同步/阻塞
    • 异步/非阻塞
    • 如果收发都是阻塞的，则发送者和接收者之间就会有一个交会（rendezvous）
  • 自动或显示的缓冲
    • 零容量（zero capacity）：发送者阻塞，直到接收者接收到消息。
    • 有限容量（bounded capacity）
    • 无限容量（unbouned capacity）：发送者从不阻塞。

3.5 IPC系统例子

3.6 客户机/服务器通信

3.6.1 套接字
3.6.2 远程程序调用（RPC）
3.6.3 管道
  • 普通管道：
    • 单向
    • 两个进程应是父子关系，并在开始时关闭管道未使用的一端
    • Windows 下为匿名管道（anonymous pipe）
  • 命名管道：
    • 双向
    • 不要求父子关系

Chapter 4 多线程编程

重点：并行与并发、Amdahl定律、数据并行与任务并行、多线程模型、实现线程库的两种方法、三种主要线程库、异步线程与同步线程、三种隐式多线程方法、同步与异步信号、线程撤销、线程本地存储、LWP、回调。

4.1 概述

4.1.1 动机
4.1.2 优点
  • 响应性：如果一个交互程序采用多线程，那么即使部分阻塞或者执行冗长操作，它仍可以继续执行。
  • 资源共享：线程默认共享它们所属进程的内存和资源。
  • 经济：由于线程能够共享它们所属进程的资源，所以创建和切换线程更加经济。
  • 可伸缩性：线程可在多处理核上并行运行。

4.2 多核编程

  • 并行（parallelism）：可以同时执行多个任务。

  • 并发（concurrency）：支持多个任务，允许所有任务都能取得进展。

  • Amdahl 定律：$S$ 为程序串行部分，$N$ 为系统核数
    $$
    加速比 \le \frac{1}{S+\frac{1-S}{N}}
    $$

4.2.1 编程挑战
  • 识别任务
  • 平衡
  • 数据分割
  • 数据依赖
  • 测试与调试
4.2.2 *并行类型
  • 数据并行：将数据分布于多个计算核上，并在每个核上执行相同操作。
  • 任务并行：将任务（线程）而不是数据分配到多个计算核。不同的线程可以操作相同的数据，也可以操作不同的数据。

4.3 *多线程模型

  • 用户线程（user thread）
  • 内核线程（kernel thread）
  • 用户线程位与内核之上，它的管理无需内核支持；而内核线程由操作系统来直接支持与管理。
  • 用户线程映射到内核线程才可执行，通过内核调度。
4.3.1 多对一模型
  • 多对一模型：多个用户级线程映射到一个内核线程。image-20201117155426100
  • 不允许多个线程并行运行在多核处理器上。
4.3.2 一对一模型
  • 一对一模型：每个用户线程映射到一个内核线程。image-20201117155607555
  • 提供更好的并发功能，但创建一个用户线程就要创建一个内核线程，创建内核线程的开销会影响应用程序的性能。
4.3.3 多对多模型
  • 多对多模型：多路复用多个用户级线程到同样数量或更少数量的内核线程。image-20201117160229890
  • 双层模型：允许绑定某个用户线程到一个内核线程。image-20201117160304443

4.4 线程库

  • 线程库（thread library）：为程序员提供创建和管理线程的 API 。
  • 实现线程库的两种主要方法：
    • 在用户空间中提供一个没有内核支持的库；
    • 实现由操作系统直接支持的内核级的一个库。
  • 三种主要线程库
    • POSIX Pthreads
    • Windows API
    • Java
  • 多线程创建的两个常用策略
    • 异步线程：一旦父进程创建了一个子线程后，父线程就恢复自身的执行，这样父进程与子线程会并发执行。
    • 同步线程：如果父线程创建一个或多个子线程后，在恢复执行之前等待所有子线程的终止。
4.4.1 Pthreads
  • $pthread_create$
  • $pthread_join$
  • $pthread_attr_init$
4.4.2 Windows 线程
4.4.3 Java 线程

4.5 *隐式多线程

  • 隐式多线程（implicit threading）：将多线程的创建与管理交给编译器和运行时库来完成。
4.5.1 线程池
  • 线程池的主要思想：在进程开始时创建一定数量的线程，并加到池中以等待工作。
  • 线程池的优点：
    • 用现有线程服务请求比等待创建一个线程更快。
    • 线程池限制了任何时候可用线程的数量。
    • 将要执行任务从创建任务的机制中分离出来，允许我们采用不同策略运行任务。
4.5.2 OpenMP（编译扩展）
  • OpenMP：一组编译指令和 API，支持共享内存环境下的并发编程。
4.5.3 大中央调度（语言扩展）
  • 大中央调度（Grand Central Dispatch，GCD）：允许应用程序开发人员将某些代码区段并行运行。
  • GCD 为 C 和 C++ 语言增加了块（block）的扩展。通过将这些块放置在调度队列（dispatch queue）上，GCD 调度块以便执行。

4.6 多线程问题

4.6.1 系统调用 fork() 和 exec()
  • fork() 的两种形式：复制所有线程；仅仅复制调用了 fork() 的线程。
4.6.2 信号处理

  • 信号遵循的模式

    • 由特定事件发生而产生；
    • 被传递给某个进程；
    • 一旦收到就应处理。

  • 同步信号发送到由于执行操作导致这个信号的同一进程；异步信号发送到另一个进程。

  • 信号处理程序可以分为两种：

    • 缺省的信号处理程序（缺省信号处理程序）；
    • 用户定义的信号处理程序（用户定义信号处理程序）。

  • 信号传递的目的地：

    • 所有适用的线程；
    • 进程内的每个线程；
    • 进程内的某些线程；
    • 规定一个特定线程以接受进程的所有信号。
4.6.3 线程撤销

  • 线程撤销：线程完成之前终止线程。

  • 目标线程（target thread）：需要撤销的线程。

  • 目标线程的撤销可以有两种情况：

    • 异步撤销：一个线程立即终止目标线程。
    • 延迟撤销：目标线程不断（周期性）检查自己是否应该终止。
4.6.4 线程本地存储
  • 线程本地存储（Thread-Local Storage，TLS）
4.6.5 程序调度激活

  • 轻量级进程（Light Weight Process，LWP）：对于用户级线程库，LWP 表现为虚拟处理器。

  • 调度器激活（scheduler activation）：用户线程库与内核之间的一种通信方案。内核提供一组 LWP 给应用程序，而应用程序可以调度用户线程到任何一个可用 LWP。

  • 回调（upcall handler）：内核将有关特定事件通知应用程序的过程，由线程库通过回调处理程序（upcall handler）来处理。

4.7 操作系统例子

4.7.1 Windows 线程
4.7.2 Linux 线程

Chapter 5 进程调度

重点：调度点、抢占和非抢占调度、调度程序的功能、调度延迟、五种调度准则、调度算法、Gantt图、线程调度竞争范围、多处理器调度（调度方法、亲和性、负载平衡）、两种实时CPU调度、完全公平调度程序。

5.1 基本概念

5.1.1 CPU-I/O 执行周期
  • I/O 密集型程序通常具有大量短 CPU 执行。CPU 密集型程序可能只有少量长 CPU 执行。
5.1.2 CPU 调度程序

  • 采用短期调度程序

  • 就绪队列的实现有多种方式

  • 队列内的记录为 PCB

5.1.3 抢占调度
  • 调度点
    • running —— waiting
    • running —— ready
    • waiting —— ready
    • terminated
  • 抢占 & 非抢占
5.1.4 调度程序

  • 调度程序（dispatcher）：是一个模块，用来将 CPU 控制交给由短期调度程序选择进程。

  • 调度程序的功能：

    • 切换上下文
    • 切换到用户模式
    • 跳转到用户程序的合适位置，以便重新启动

  • 调度延迟（dispatch latency）：调度程序停止一个进程而启动另外一个进程所需要的时间。

5.2 调度准则

  • 调度准则
    • CPU 使用率
    • 吞吐量：在一个时间单元内进程完成的数量。
    • 周转时间（turnaround time）：从进程提交到进程完成的时间段。
    • 等待时间：进程在就绪队列中等待所花费的时间。
    • 响应时间：从提交请求到产生第一响应的时间。
  • 对于交互系统，最小化响应时间的方差。

5.3 调度算法

5.3.1 先到先服务调用(First Come First Serve)
  • 护航效果（convey effect）：进程都等待一个大进程释放CPU。
5.3.2 最短作业优先调度
  • SJF 常用于长期调度。
  • 下次 CPU 执行时间的预测
    • 设 $t_{n}$ 为第 n 个 CPU 执行长度
    • 设 $\tau_{n+1}$ 为下次 CPU 执行预测值
    • 对于 $\alpha \in [0, 1]$ 定义 $\tau_{n+1}=\alpha t_{n} + (1-\alpha)\tau_{n}$
  • 抢占 SJF 算法——最短剩余时间优先调度
5.3.3 优先级调度(priority-scheduling)
  • 具有相同优先级的进程按照 FCFS 调度。
  • 本书使用低数字表示高优先级。
  • 优先级调度的主要问题
    • 饥饿（starvation）：也成为无穷阻塞。
    • 老化（aging）：逐渐增加在系统中等待时间很长的进程的优先级。
5.3.4 轮转调度(Round-Robin)
  • 如果时间片很大，RR 算法就和 FCFS 算法相同。
  • 如果时间片很小，RR 算法就会有大量的上下文切换。
5.3.5 多级队列调度（multilevel queue scheduling）
  • 将就绪队列分为多个单独的队列，根据进程属性将一个进程永久的分配到一个队列中。
  • 每个队列有自己的调度算法。
5.3.6 多级反馈队列调度
  • 相较于多级队列调度，多级反馈队列允许进程在队列之间迁移。
  • 根据不同 CPU 执行的特点来区分进程。 CPU 执行时间越短的优先级越高。
  • 老化：在较低优先级队列中等待过长的进程会被移到优先级更高的队列。

5.4 线程调度

5.4.1 竞争范围
  • 进程竞争范围（Process-Contention Scope，PCS）：竞争 CPU 是发生在同一进程的线程之间。
  • 系统竞争范围（System-Contention Scope，SCS）：竞争 CPU 发生在系统内的所有线程之间。
5.4.2 Pthreads 调度

5.5 多处理器调度

5.5.1 多处理器调度的方法
  • 非对称多处理：让一个处理器（主服务器）访问所有调度决定、I/O 处理以及其他系统活动，其他的处理器只执行用户代码。
    • 只有一个处理器访问系统数据结构，减少了数据共享的需要。
  • 对称多处理：每个处理器自我调度。
5.5.2 处理器亲和性
  • 处理器亲和性（processor affinity）：即一个进程对它运行的处理器具有亲和性。
  • 软亲和性（soft affinity）：一个操作系统试图保持进程运行在一个处理器上。
  • 硬亲和性（hard affinity）：允许某个进程运行在某个处理器子集上。
  • 系统的内存构架可以影响处理器的亲和性。
5.5.3 负载平衡
  • 负载平衡（load balance）：设法将负载平均分配到 SMP 系统的所有处理器。
  • 负载平衡的两种方法
    • 退迁移（push migration）：一个特定的任务周期性检查每个处理器的负载，如果发现不平衡，通过将进程从超载处理器推到空闲或不太忙的处理器，从而平均分配负载。
    • 拉迁移（pull migration）：空闲处理器从一个忙的处理器上拉一个等待任务。
5.5.4 多核处理器
  • 内存停顿（memory stall）：当一个处理器访问内存时，它花费大量时间等待所需数据。
  • 处理器核的多线程方法
    • 粗粒度（coarse-grained）：线程一直在处理器上运行，直到一个长延迟时间发生。
    • 细粒度（fine-grained）：在更细的粒度级别上切换线程。

5.6 实时 CPU 调度

  • 软实时系统（soft real-time system）：不保证会调度关键实时进程。
  • 硬实时系统（hard real-time system）：一个任务应在它的截止期限之前完成，
5.6.1 最小化延迟
  • 事件延迟（event latency）：从事件发生到事件得到服务的时间。
  • 中断延迟（interrupt latency）：从 CPU 收到中断到中断处理程序开始的时间。
  • 保持调度延迟尽可能低的最有效技术是抢占式内核。
  • 调度延迟的冲突阶段
    • 抢占在内核中运行的任何进程；
    • 释放高优先级进程所需要的、低优先级进程占有的资源。
5.6.2 优先级调度
5.6.3 单调速率调度
  • 单调速率（rate-monotonic）调度：采用抢占的、静态优先级的策略，调度周期性任务。
  • 周期越短、优先级越高；周期越长，优先级越低。
5.6.4 最早截止期限优先调度
  • 最早截止期限优先（Earliest-Deadline-First，EDF）调度：根据截止期限动态分配优先级。
  • 截止期限越早，优先级越高；截止期限越晚，优先级越低。
5.6.5 比例分享调度
  • 比例分享调度（proportional share）：在所有应用之间分配 T 股。
5.6.6 POSIX 实时调度

5.7 操作系统例子

5.7.1 例子：Linux 调度

  • 完全公平调度程序（Completely Fair Scheduler，CFS）：Linux 的默认调度算法。

  • Linux 系统的调度基于调度类（schedule class）。每个类都有一个特定优先级。内核针对不同的调度类，采用不同的调度算法。

  • 每个任务分配的具体 CPU 处理时间比例是根据友好值（nice value）来计算的。友好值范围从 -20 到 19 ，数值越低的友好值表示较高的相对优先级。

  • 目标延迟（target latency）：每个可运行任务应当运行一次的时间间隔。使用目标延迟来代替离散的时间片。

  • 虚拟运行时间（virtual run time）：记录每个任务运行多久。

    • 友好值为 0 的进程的虚拟运行时间与实际物理运行时间相同。友好值高于 0 ，虚拟运行时间高于实际物理运行时间；友好值低于 0 ，虚拟运行时间低于实际运行时间。
    • I/O 密集型任务的 vruntime 值最终将会小于 CPU 密集型任务的。

image-20210119171511438

5.7.2 例子：Windows 调度
5.7.3 例子：Solaris 调度

5.8 算法评估

5.8.1 确定性模型
  • 确定性模型（deterministic modeling）：采用特定的预先确定的负荷，计算在该负荷下每个算法的性能。
5.8.2 排队模型
  • Little 公式：$n=\lambda \times W （平均到达率 × 平均等待时间）
5.8.3 仿真
5.8.4 实现

Chapter 6 同步

重点：临界区问题解决方案的三点要求、Peterson解决方案、

6.1 背景

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

6.2 临界区问题

  • 临界区（critical section）：当一个进程在临界区内执行时，其他进程不允许在它们的临界区内执行。

    image-20210119195201936

  • 临界区问题的解决方案应满足如下三点

    • 互斥（mutual exclusive）
    • 进步（progress）
    • 有限等待（bounded waiting）

  • 两种用于处理操作系统临界区问题的常用方法

    • 抢占式内核（preemptive kernel）：抢占式内核允许处于内核模式的进程被抢占。
    • 非抢占式内核（nonpreemptive kernel）：非抢占式内核不允许处于内核模式的进程被抢占。

6.3 Peterson 解决方案

  • Peterson 解决方案：适合用于两个进程交错执行临界区与剩余区。

6.4 硬件同步

  • 硬件同步本质是增加原子指令

  • 对于单处理器环境临界区问题解决方法

    • 在修改共享变量时只要禁止中断出现。（非抢占式内核 + 禁止中断）

  • 在多处理器环境下

    • 使用中断禁止很耗时，因为消息要传遍所有的处理器。
    • 消息传递会延迟进入临界区，并降低系统效率。

  • test_and_set：将 TARGET 设置为 true，并返回 TARGET 的原始值。

    boolean test_and_set(boolean *target);

  • compare_and_swap​：检查 VALUE 是否和 EXPECTED 相等，如果相等则赋予 NEW_VALUE，并返回 VALUE 的值。

    int compare_and_swap(int *value, int expected, int new_value);

  • 采用 test_and_set 的有界等待互斥

    do {
	waiting[i] = true;
	key = true;
	while (waiting[i] && key) 
      key = test_and_set(&lock); 
   	waiting[i] = false; 
   	
   	/* critical section */ 
   	j = (i + 1) % n; 
   	while ((j != i) && !waiting[j]) 
   		j = (j + 1) % n; 
   	if (j == i) 
      	lock = false; 
   	else 
      	waiting[j] = false;
        
   	/* remainder section */ 
} while (true);

6.5 互斥锁

  • 自旋锁（spinlock）：当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环地调用 acquire() ，需要忙等待（busy waiting）
  • 自旋锁的优点
    • 当进程在等待锁时，没有上下文切换。

6.6 信号量

  • PV操作
    • P 操作：wait()
    • V 操作：signal()
6.6.1 信号量的使用
  • 计数信号量（counting semaphore）：值不受限制。
  • 二进制信号量（binary semaphore）：只能为 1 或 0 。类似于互斥锁。
6.6.2 信号量的实现

  • 信号量操作 wait()

    image-20210119202543622

  • 信号量操作 signal()

    image-20210119202556806

6.6.3 死锁与饥饿
6.6.4 优先级反转
  • 资源优先级为负；
  • 进程优先级大于等于 0；
  • 当进程占有某个资源时，其自己的优先级于资源的优先级相乘的到新的优先级。

6.7 经典同步问题

6.7.1 有界缓冲问题
6.7.2 读者-作者问题

  • 读者-写者问题

    • 第一读者写者问题
    • 第二读者写者问题

  • 读写锁（read-writer lock）：多个进程可以并发地获取读模式的读写锁，但是只有一个进程可以获取写模式的读写锁，作者进程之间需要互斥访问。

  • 读写锁在以下情况最有用

    • 容易识别哪些进程只读共享数据和哪些进程只写共享数据的应用程序。
    • 读者进程数比作者进程数多的应用程序。
6.7.3 哲学家就餐问题

6.8 管程

6.8.1 使用方法
6.8.2 哲学家就餐问题的管程解决
6.8.3 采用信号量的管程实现
6.8.4 管程内进程重启

6.9 同步例子

6.9.1 Windows 同步
  • 调度对象（dispatcher object）
6.9.2 Linux 同步
  • 原子整数（atomic integer）：用于整型变量的更新。
  • 互斥锁：用于保护内核中的临界区。
  • 自旋锁和信号量
  • 启用和禁用内核抢占
6.9.3 Solaris 同步
  • 自适应互斥（adaptive mutex）
    • 如果这个锁正在被另一个 CPU 上运行的线程所拥有，那么拥有该锁的线程可能很快结束，所以请求该锁的线程就自旋以便等待锁的可用。
    • 如果拥有这个锁的线程现在不处于运行状态，那么线程就阻塞并进入睡眠，直到该锁释放时被唤醒。
6.9.4 Pthreads 同步
  • 互斥锁、信号量、条件变量
  • 命名信号量
  • 无名信号量

6.10 替代方法

6.10.1 事务内存
  • 事务内存的优点
    • 事务性内存系统而非开放人员负责保证原子性。
    • 不涉及锁，所以死锁是不可能的。
  • 软件事务内存（Software Transactional Memory，STM）：完全通过软件来实现。
  • 硬件事务内存（Hardware Transactional Memory，HTM）：使用高速缓存层次结构和高速缓存一致性协议，对涉及驻留在单独处理器的高速缓存中的共享数据进行管理和解决冲突。
6.10.2 OpenMP
6.10.3 函数式编程语言

Chapter 7 死锁

重点：死锁的必要条件、资源分配图、死锁预防、安全序列、资源分配图算法、银行家算法、死锁检测算法、死锁恢复的两种方式及其考虑的问题。

7.1 系统模型

  • 进程使用资源的顺序
    • 申请
    • 使用
    • 释放

7.2 死锁特征

7.2.1 必要条件
  • 在一个系统中一下四个条件同时成立，那么能引起死锁
    • 互斥
    • 占有并等待
    • 非抢占
    • 循环等待
7.2.2 资源分配图
  • 顶点
    • 进程点
    • 资源点
  • 边
    • 请求边：从进程指向资源的有向边。
    • 分配边：从资源指向进程的有向边。

image-20210119190741649

  • 如果分配图没有环，那么系统就没有进程死锁；如果有环，则可能存在死锁。
  • 一实例一环必死锁。

7.3 死锁处理方法

  • 三种方法
    • 通过协议来预防（确保至少有一个必要条件不成立）或避免（操作系统事先得到有关进程申请资源和使用资源的额外信息）死锁，确保系统不会进入死锁状态。
    • 可以允许系统进入死锁状态，然后检测它，并加以恢复。
    • 可以忽视这个问题，认为死锁不可能在系统内发生。（大多数操作系统采用）

7.4 死锁预防

7.4.1 互斥
  • 使用可共享资源。
7.4.2 持有并等待
  • 每个进程在执行之前申请并获得所有资源。
  • 进程仅在没有资源时才可申请资源。
  • 两种协议的缺点
    • 资源利用率低
    • 发生饥饿
7.4.3 无抢占
  • 当一个进程申请一些资源时，首先检查它们是否可用。
    • 可用就分配。
    • 不可用，那么检查这些资源是否已分配给等待额外资源的其他进程。如果是，那么从等待进程中抢占这些资源。如果资源不可用且也不被其他等待进程持有，那么申请进程应等待。
  • 只有当一个进程分配到申请的资源，并恢复在等待时被抢占的资源时，它才能重新执行。
7.4.4 循环等待
  • 对所有的资源类型进行完全排序，而且要求每个进程按递增顺序来申请资源。

7.5 死锁避免

  • 死锁避免算法动态检查资源分配状态，以便确保循环等待条件不能成立。
7.5.1 安全状态
  • 安全序列（safe sequence）：为每个进程分配资源的一定顺序。只有存在一个安全序列，系统才处于安全状态。
7.5.2 资源分配图算法
  • 要求每种资源类型只有一个实例。
  • 需求边（claim edge）：使用虚线表示，从进程指向资源的有向边。进程$P_{i}$可能在将来的某个时候申请资源 $R_{j}$ 。
7.5.3 银行家算法
  • 银行家算法（banker’s algorithm）
  • $n$ 为系统进程的数量，$m$ 为资源类型的数量
    • $Available$：长度为 $m$ 的向量，表示每种资源的可用实例数量。
    • $Max$：$n \times m$ 矩阵，定义每个进程的最大需求。
    • $Allocation$：$n \times m$ 矩阵，定义每个进程现在分配的每种资源类型的实例数量。
    • $Need$：$n \times m$ 矩阵，表示每个进程还需要的剩余资源。

7.6 死锁检测

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

  • 等待图（wait-for graph）：从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。

    image-20210119193433474

  • 图中从 $P_{i}$ 到 $P_{j}$ 的边意味着，$P_{i}$ 等待 $P_{j}$ 释放一个 $P_{i}$ 需要的资源。

  • 从图中检测环的算法需要 $n^2$ 的数量级。

7.6.2 每种资源类型可有多个实例
  • 使用一种银行家算法的变体。
7.6.3 应用检测算法
  • 何时调用检测算法取决于两个因素
    • 死锁可能发生的频率是多少？
    • 当死锁发生时，有多少进程收到影响？

7.7 死锁恢复

7.7.1 进程终止
  • 通过中止进程来消除死锁，有两种方法
    • 终止所有死锁的进程
    • 一次中止一个进程，直到消除死锁循环为止。
7.7.2 资源抢占
  • 采用抢占来处理死锁，需要处理三个问题
    • 选择牺牲进程：抢占哪些资源和哪些进程？
    • 回滚：应该将进程回滚至某个安全状态，以便从该状态重启进程。
    • 饥饿：如何确保不会发生饥饿？保证资源不会总是从同一个进程中被抢占。

三 内存管理

Chapter 8 内存

重点：地址绑定、硬件支持、交换、连续分配、分段、分页、页表结构

8.1 背景

8.1.1 基本硬件
  • 基地址寄存器
  • 界限地址寄存器
  • 只有操作系统可以通过特殊的特权指令，才能加载基地址寄存器和界限地址寄存器。
8.1.2 地址绑定
  • 编译时绑定（compile time）：在编译时就知道进程将在内存中的驻留地址，就可以生成绝对代码（absolute code）。如果将来开始地址发生变化，那么就有必要重新编译代码。
  • 加载时绑定（load time）：如果在编译时并不知道进程将驻留在何处，那么编译器就生成可重定位代码（relocatable code）。如果开始地址发生变化，那么只需要加载用户代码以合并更改的值。
  • 执行时绑定（runtime time）：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定应延迟到执行时才进行。需要特定硬件的支持。大多数通用计算机操作系统采用这种方法。
8.1.3 逻辑地址空间和物理地址空间
  • 逻辑地址（logical address）：CPU生成的地址。（常称为虚拟地址）
  • 物理地址（physical address）：内存单元看到的地址。
  • 编译时和加载时的地址绑定方法生成相同的逻辑地址和物理地址。执行时绑定方法生成不同的逻辑地址和物理地址。
  • 内存管理单元（Memory-Manage Unit，MMU）：从虚拟地址到物理地址的运行时映射。
  • 重定位寄存器（relocation register）：基地址寄存器在重定位中的名称。
8.1.4 动态加载
  • 动态加载（dynamic loading）：一个程序只有在调用时才会加载，所有程序都以可重定位加载格式保存在磁盘上。从而获得更好的内存空间利用率。
8.1.5 动态链接与共享库
  • 动态链接库（dynamically linked library）：为系统库，可链接到用户程序，以便运行。动态链接属于动态加载。
  • 存根（stub）：是一小段代码，用来指出如何定位适当的内存驻留库程序，或者在程序不在内存内时应该如何加载库。存在于动态链接情况下，二进制映像内的每个库程序的引用中。
  • 共享库（shared library）：一个库的多个版本可以都加载到内存中，程序将通过版本信息来确定使用哪个库的副本。

8.2 交换

​ 进程可以暂时从内存交换（swap）到备份存储（backing store）中，当再次执行的时候再调回到内存中。交换有可能让所有进程的总的物理地址空间超过真实系统的物理地址空间，从而增加了系统的多道程序程度。

8.2.1 标准交换
  • 标准交换：标准交换再内存与备份存储之间移动进程。
  • 不能换出等待处理I/O的进程；I/O操作的执行只能使用操作系统的缓冲。
  • 现代操作系统并不使用标准交换，因为交换的时间太多，执行的时间太短。转而采用变种交换：正常情况下，禁止交换；当内存空闲低于某个阈值时，启用交换。
8.2.2 移动系统的交换
  • iOS：要求应用程序自愿放弃分配的内存。
  • Android：如果没有足够可用的空闲内存，则它可以终止进程。在终止进程之前，将应用程序状态写到闪存，以便它能快速重新启动。

8.3 连续内存分配

​ 内存通常分为两个区域：一个用于驻留操作系统，另一个用于用户进程。

  • 连续内存分配（contiguous memory allocation）：每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。
8.3.1 内存保护
8.3.2 内存分配
  • 分区（partition）
  • 多分区方法
  • 可变分区（variable-partition）
  • 孔（hole）
  • 空闲孔的适配方式
    • 首次适配（first-fit）
    • 最优适配（best-fit）
    • 最差适配（worst-fit）
8.3.3 碎片
  • 外部碎片（external fragmentation）
  • 内部碎片（internal fragmentation）
  • 外部碎片的解决方法
    • 紧缩（compaction）
    • 允许进程的逻辑地址空间是不连续的

8.4 分段

8.4.1 基本方法
  • 段的逻辑地址：<段号，偏移>
8.4.2 分段硬件
  • 段表（segment table）：段表基地址寄存器（STBR）和段表界限寄存器（STLR）
  • 段基地址（segment base）：包含该段在内存中的开始物理地址。
  • 段界限（segment limit）：指定该段的长度。

8.5 分页

8.5.1 基本方法
  • 将物理内存划分为帧（frame），对应帧表
  • 将虚拟内存划分为页（page），对应页表
  • CPU生成的每个虚拟地址分为两部分：页码（page number）和页偏移（page offset）
  • 分页增加上下文切换的时间。
8.5.2 硬件支持
  • 页表基地址寄存器
  • 页表长度寄存器
  • 旁路翻译缓冲（Translation Look-aside Buffer，TLB）
  • 替换策略
  • 地址空间标识符（Address-Space Identifier，ASID）：唯一标识每个进程，并为进程提供地址空间的保护。
  • 有效内存访问时间（effective memory-access time）：$EMTA=(T_{m}+\epsilon)\alpha+(2T_{m}+\epsilon)(1-\alpha)$
    • $T_{m}$：单次内存访问时间
    • $\epsilon$：单次 TLB 访问时间
    • $\alpha$：TLB 命中概率。TLB 命中时一次内存访问，不命中时两次内存访问。
8.5.3 保护
  • 有效-无效位（valid-invalid bit）
    • 有效：表示相关的页在进程的逻辑地址空间内。
    • 无效：表示相关的页不在进程的逻辑地址空间内。
8.5.4 共享页
  • 可重入代码（reentrant code） & 纯代码（pure code）可以共享

8.6 页表结构

8.6.1 分层分页
  • 向前映射页表（forward-mapped page table）
8.6.2 哈希页表
  • 哈希页表（hashed page table）：每一个条目都包括一个链表，该链表的元素哈希到同一位置。其中链表用来处理碰撞问题。
  • 聚簇页表（clustered page table）：哈希表内每个条目引用多个页。因此单个页表条目可以映射到多个物理帧。对于稀疏（sparse）地址空间特别有用。
8.6.3 倒置页表
  • 倒置页表（inverted page table）：对于每个真正的内存页或帧，页表中才有一个条目。每个条目包含存在真正内存位置上的页的虚拟地址，以及拥有该页进程的信息。
  • 虽然这种方法减少了存储每个页表所需的内存空间，但是它增加了由于引用页而查找页表所需的时间。

8.7 例子：Intel 32 位与 64 位体系结构

8.7.1 IA-32架构

​ IA-32 系统的内存管理可分为分段和分页两个部分。

image-20210113193356390

  • 分段

    • 段最大为 4 GB，每个进程最多有 16 K个段。

    • 局部描述符表（Local Descriptor Table，LDT）：保存进程逻辑地址空间的单个进程私有的第一部分信息。

    • 全局描述符表（Global Descriptor Table，GDT）：保存进程逻辑地址空间的所有进程共享的第二部分信息。

    • LDT 和 GDT 中的每个条目由 8 字节组成。

    • CPU 有 6 个段寄存器。

    • 逻辑地址转化成线性地址。

      image-20210113194107818

  • 分页

    • 页大小为 4 KB 或 4 MB

    image-20210113194450536

8.7.2 x86-64
  • 四级分页，支持48位虚拟地址。

image-20210113194534248

8.8 例子：ARM架构

  • 一级分页：1 MB 和 16 MB 的页
  • 二级分页：4 KB 和 16 KB 的页

image-20210113194905223

Chapter 9 虚拟内存

重点：有效访问时间、页面置换算法、抖动、内存映射文件、分配内核内存

9.1 背景

  • 通过将共享对象映射到虚拟地址空间中，系统库可以为多个进程所共享。
  • 虚拟内存允许进程共享内存。
  • 当通过系统调用 fork() 创建进程时，可以共享页面，从而加快进程创建。

9.2 请求调页

  • 请求调页：仅在需要的时候才加载页面。
  • 懒惰交换器（lazy swapper）：除非需要某个页面，否则从不将它交换到内存中。
  • 调页程序（pager）
9.2.1 基本概念
  • 缺页错误（page fault）：对标记为无效的页面访问。
  • 纯请求调页（pure demand paging）：只有在需要时才将页面调入。
9.2.2 请求调页的性能
  • 有效访问时间（effective access time）：$EAT=Page FaultTime\times \alpha + T_{m}(1-\alpha)$
    • $\alpha$：缺页错误的概率；
    • $PageFaultTime$：缺页错误处理时间；
    • $T_{m}$：内存访问时间。
  • 缺页错误处理时间
    • 处理缺页错误中断
    • 读入页面
    • 重新启动进程

9.3 写时复制

  • 写时复制（copy-on-write）
  • 页面池（page pool）

9.4 页面置换

9.4.1 基本页面置换
  • 页面置换
  • 脏位（dirty bit）：若置位，则说明该页被修改，需要写回到磁盘上；否则说明该页未被修改，直接丢弃。可以显著降低缺页错误处理时间。
  • 评估置换算法：针对特定的内存引用串，运行某个置换算法，并计算缺页错误的数量。
  • 引用串（reference string）
9.4.2 FIFO 页面置换
  • Belady 异常（Belady anomaly）：对于同一引用串，物理帧数多的情况下反而缺页错误数更高。
  • FIFO 存在 Belady 异常
9.4.3 最优页面置换
  • 最优页面置换（optimal page-replacement algorithm）：置换最长时间不会使用的页面。具有所有算法最低的缺页错误率。主要用于比较研究。
9.4.4 LRU 页面置换
  • 最近最少使用算法（Least-Recent-Used algorithm，LRU）：置换最长时间没有使用的页。
9.4.5 近似 LRU 算法
  • 额外引用位算法
  • 第二次机会算法
  • 增强型第二次机会算法：引用位+修改位。(0,0)、(0,1)、(1,0) 和 (1,1) 四种情况。
9.4.6 基于计数的页面置换
  • 最不经常使用（Least Frequently Used，LFU）
  • 最经常使用（Most Frequently used，MFU）
9.4.7 页面缓冲算法
  • 当出现缺页错误时，会像以前一样选择一个牺牲帧。然而，在写出牺牲帧之前，所需页面就读到来自缓冲池的空闲帧。
  • 这种措施允许进程尽快恢复启动，而无需等待写出牺牲帧。
  • 当牺牲帧写出后，它被添加到空闲帧池。
9.4.7 应用程序与页面置换
  • 双缓冲
  • 原始磁盘

9.5 帧分配

9.5.1 帧的最小数
9.5.2 分配算法
  • 平均分配
  • 比例分配
  • 优先级分配
9.5.3 全局分配与局部分配
  • 全局置换（global replacement）：允许一个进程从所有帧集合中选择一个置换帧，不管该帧是否已分配给其他进程。
  • 局部置换（local replacement）：只能在分配给自己的帧中选择。
  • 全局置换存在的问题：进程不能控制自身的缺页错误率。
  • 局部置换存在的问题：不能使用其他进程很少使用的内存页面，降低内存利用率。
9.5.4 非均匀内存访问
  • 延迟组：这种做法最大限度地减少总体内存延迟，且最大化CPU缓存命中率。

9.6 系统抖动

  • 抖动（thrashing）：高度的页面调度活动。如果一个进程的调页时间多于它执行的时间，那么这个进程在抖动。
9.6.1 系统抖动的原因
9.6.2 工作集模型
9.6.3 缺页错误频率

9.7 内存映射文件

  • 内存映射（memory mapping）：运行一部分虚拟内存与文件进行逻辑关联。
9.7.1 基本机制
  • 实现文件的内存映射是，将每个磁盘块映射到一个或多个内存页面。
  • 当关闭文件时，所有内存映射的数据会写到磁盘。
9.7.2 共享内存 Windows API
9.7.3 内存映射 I/O

9.8 分配内核内存

  • 内核要为不同大小的数据结构请求内存，其中有的小于一页。
  • 用户模式进程分配的页面不必位于连续物理内存。而内核中有的需要常驻在连续物理内存中。
9.8.1 伙伴系统
  • 伙伴系统（buddy system）：从物理连续的大小固定的段上进行分配。
  • 2 的幂分配器（power-of-2 allocator）
  • 伙伴系统的优点：通过合并（coalesce）技术，可以将相邻伙伴快速组合成更大的分段。
  • 伙伴系统的缺点：很可能造成分配段内的碎片。
9.8.2 slab分配
  • slab：由一个或多个物理连续的页面组成。
  • slab分配器的优点
    • 没有因碎片而引起的内存浪费。
    • 可以快速满足内存请求。
  • SLOB & SLUB

9.9 其他注意事项

9.9.1 预调页面
9.9.2 页面大小
9.9.3 TLB 范围
9.9.4 倒置页表
9.9.5 程序结构
9.9.6 I/O 联锁与页面固定

四 存储管理

Chapter 10 文件系统

重点：文件属性、文件操作、访问方式、目录结构、一致性语义

10.1 文件概念

  • 文件（file）：操作系统对存储设备的物理属性加以抽象，从而定义逻辑存储单位。文件由操作系统映射到物理设备上。
10.1.1 文件属性
  • 通常属性
    • 名称
    • 标识符
    • 类型
    • 位置
    • 尺寸
    • 保护
    • 时间、日期和用户标识
10.1.2 文件操作
  • 基本文件操作
    • 创建文件
    • 写文件
    • 读文件
    • 重新定位文件
    • 删除文件
    • 截断文件
  • 打开文件的关联信息
    • 文件指针
    • 文件打开计数
    • 文件的磁盘位置
    • 访问权限
  • 共享锁（shared lock） & 独占锁（exclusive lock）：共享锁可以多个进程并发获取；独占锁一次只有一个进程可以获取。
  • 强制文件锁定机制 & 建议文件锁定机制
10.1.3 文件类型
10.1.4 文件结构
10.1.5 内部文件结构
  • 逻辑记录大小、物理块大小和打包技术决定了每个物理块可有多少逻辑记录。

10.2 访问方法

10.2.1 顺序访问
  • 顺序访问（sequential access）：文件信息按顺序加以处理。最常见的访问模式，编辑器和编译器通常以这种方式访问文件。
10.2.2 直接访问
  • 直接访问（direct access）：文件由固定长度的逻辑记录组成，以允许程序按任意顺序进行快速读取和写入记录。通常应用于数据库。
10.2.3 其他访问方式
  • 索引访问（index access）

10.3 目录与磁盘的结构

  • 卷（volume）：包含文件系统的分区。
10.3.1 存储结构
10.3.2 目录概述
  • 对目录执行的操作
    • 搜索文件
    • 创建文件
    • 删除文件
    • 遍历目录
    • 重命名文件
    • 遍历文件系统
10.3.3 单级目录

image-20210114213213456

10.3.4 两级目录

  • 用户文件目录（User File Directory，UFD）

  • 主文件目录（Master File Directory，MFD）

image-20210114213354892

10.3.5 树形目录

image-20210114213520930

  • 不能共享文件和目录
10.3.6 无环图目录

image-20210114213541475

  • 可以共享目录和文件
10.3.7 通用图目录

image-20210114213553838

  • 垃圾收集（garbage collection）

10.4 文件系统安装

  • 操作系统需要知道设备的名称和安装点（mount point）。

10.5 文件共享

10.5.1 多用户
10.5.2 远程文件系统

  • 远程文件共享的方法

    • 通过 ftp 程序在机器之间手动传送文件
    • 通过分布式文件系统（Distributed File System，DFS），远程目录从本机上可以直接访问
    • 万维网

  • 客户机-服务器模型

  • 分布式信息系统

  • 故障模式

    • 文件系统的磁盘故障
    • 目录结构或其他磁盘管理信息（元数据）的损坏
    • 磁盘控制器的故障、电缆故障和主机适配器故障
10.5.3 一致性语义
  • 一致性语义（consistency semantic）：是个重要准则，用于评估支持文件共享的文件系统。这些语义规定系统的多个用户如何访问共享文件。
  • UNIX 语义：导致用户进程的延迟
    • 一个用户对已打开文件的写入，对于打开同一文件的其他用户立即可见。（修改立即可见）
    • 一种共享模式允许用户共享文件的当前位置指针。（共享文件指针）
  • Andrew 语义：没有延迟
    • 一个用户对已打开文件的写入，对于打开用以文件的其他用户不立即可见。
    • 一旦文件关闭，对其所作的更改只能被后来打开的会话可见。
  • 不可变共享文件（immutable shared file）语义
    • 一旦一个文件由创建者声明为共享，它就不能被修改。
    • 两个关键属性
      • 文件的名称不可重用
      • 内容不可以改变

10.6 保护

10.6.1 访问类型
  • 读
  • 写
  • 执行
  • 附加
  • 删除
  • 列表
10.6.2 访问控制
  • 根据用户身份控制访问
  • 不好的实现方法：为每个文件和目录关联一个访问控制列表（Access-Control List，ACL），以指定每个用户的名称及其允许的访问类型。
    • 缺点：无聊的任务；大小固定难以管理。
  • 精简后的实现方法：根据三种用户类型给出访问控制权限。
10.6.3 其他保护方式

Chapter 11 文件系统实现

重点：

11.1 文件系统结构

  • 磁盘的优势

    • 可以原地重写
    • 可以直接访问包含信息的任何块

  • 为了提高I/O效率，内存和磁盘之间的I/O传输以 块 为单位执行。

  • 文件系统的设计问题

    • 如何定义文件系统的用户接口
    • 创建算法和数据结构，以便映射逻辑文件系统到物理外存设备

  • 文件系统的分层设计

    • 逻辑文件系统（logical file system）：向上连接应用程序。管理元数据信息。它通过文件控制块来维护文件结构。
    • 文件组织模块（file-organization module）：知道文件及其逻辑块以及物理块。
    • 基本文件系统（basic file system）：只需向适当设备驱动程序发送通用命令，以读取和写入磁盘块。该层页管理内存缓冲区和保存各种文件系统、目录和数据块的缓存。
    • I/O控制（I/O control）：向下连接硬件设备。包括设备驱动程序和中断处理程序，以在主内存和磁盘系统之间传输信息。

  • 分层设计的优点：最小化代码的重复。

  • 分层设计的缺点：增加操作系统的开销，导致性能降低。

11.2 文件系统实现

11.2.1 概述
  • 在磁盘上文件系统包括如下信息：
    • 引导控制块（boot control block）
    • 卷控制块（volume control block）
    • 文件系统的目录结构
    • 每个文件的FCB
  • 在内存中文件系统包括如下信息：
    • 安装表（mount table）
    • 目录结构的缓存
    • 整个系统的打开文件表
    • 每个进程的打开文件表
    • 缓冲区
11.2.2 分区与安装
  • 生分区（raw partition）：没有文件系统。
  • 熟分区（cooked partition）：含有文件系统。
  • 根分区（root partition）：包括操作系统内核和其他系统文件，在启动时安装。
11.2.3 虚拟文件系统

  • 现代操作系统必须支持多种类型的文件系统。

  • 虚拟文件系统（Virtual File System，VFS）

    • 通过定义一个清晰的 VFS 接口，将文件系统的通用操作和实现分开。
    • 提供一种机制，以唯一表示网络上的文件。

  • Linux VFS 定义 4 种主要对象类型

    • 索引节点对象（inode object）：一个单独的文件。
    • 文件对象（file object）：一个已打开的文件。
    • 超级块对象（superblock object）：表示整个文件系统。
    • 目录条目对象（dentry object）：单个目录条目。

11.3 目录实现

11.3.1 线性列表
11.3.2 哈希表

11.4 分配方法

11.4.1 连续分配
  • 连续分配（contiguous allocation）：每个文件在磁盘上占有一组连续的块。
  • 连续分配的问题：
    • 具有外部碎片
    • 难以在初次分配时确定文件需要的空间大小
  • 连续分配的修正方案：当初次连续分配的数量不够时，会添加另一块连续空间（扩展）。
11.4.2 链接分配
  • 链接分配（linked allocation）：解决了连续分配的所有问题。每个文件是磁盘块的链表；磁盘块可能会散布在磁盘的任何地方。
  • 链接分配的问题
    • 只能有效用于顺序访问的文件
    • 指针需要空间，降低空间利用率
      • 可通过簇（cluster）来解决，提高磁盘吞吐量并且降低块分配和空闲列表管理所需的空间。但增加了内部碎片。
    • 低可靠性
  • 链接分配的一个重要的变种——文件分配表（File-Allocation Table，FAT）
    • 在该表中，每个磁盘块都有一个条目，并可按照块号来索引。
11.4.3 索引分配

  • 索引分配（index allocation）：通过将所有的指针放在一起，即索引块。

  • 索引分配支持直接访问，并没有外部碎片问题。

  • 解决索引块应该多大的机制

    • 链接方案：一个索引块通常为一个磁盘块。将多个索引块链接起来。

    • 多级索引：链接方案的一种变种，通过第一级索引块指向一组第二级的索引块，以此类推。

    • 组合方案：包含直接链接和间接链接。有直接链接块、一级间接块、二级间接块和三级间接块。

      image-20210115191555399

11.4.4 性能
  • 有的系统通过使用连续分配支持直接访问的文件，通过链接分配支持顺序访问的文件。
  • 鉴于 CPU 速度和磁盘速度的差距，操作系统采用数千条指令以节省一些磁头移动是合理的。

11.5 空闲空间管理

  • 空闲空间链表（free-space list）：用来跟踪空闲磁盘空间。
11.5.1 位向量
  • 通常，空闲空间链表按位图（bit map）或位向量（bit vector）来实现。如果块是空闲的，位为1；如果块是分配的，位为0。
  • 扫描第一个非零的字，以查找值为1的位，该块号码的计算如下：（每个字的位数）×（值为0的字数）+ 第一个值为1的位的偏移。
11.5.2 链表
  • 将所有空闲磁盘块用链表链接起来，将指向第一块空闲块的指针保存在磁盘的特殊位置上，同时也将其缓存在内存中。
11.5.3 组
  • 在第一个空闲块中存储n个空闲块的地址。在第一个空闲块中存储n个空闲块的地址。这些块的前n-1个确实为空。最后一块包含另外n个空闲块的地址。
11.5.4 计数
  • 记录第一块的地址和紧跟第一块的连续空闲块数量n。
11.5.5 空间图

11.6 效率与性能

11.6.1 效率
  • 磁盘空间的有效使用在很大程度上取决于磁盘分配和目录算法。
  • 保存在文件目录条目内的数据类型也需要加以考虑。
11.6.2 性能

  • 缓存方法提高性能

    • 缓冲区缓存（buffer cache）：一块独立的内存，假设其中的块将很快再次使用。

    • 页面缓存（page cache）：页面缓存采用虚拟内存技术，将文件数据按页面而不是按面向文件系统的块来缓存。

    • 统一缓冲区缓存（unified buffer cache）：使用统一缓冲区缓存时，内存映射与 read() 和 write() 系统调用都会采用同样的页面缓存。这样有利于避免双缓存，并允许虚拟内存系统来管理文件系统数据。

      image-20210115194107876image-20210115194209008

  • 文件的同步写与异步写

    • 同步写（synchronous write）：按磁盘子系统接受顺序来进行，并不缓冲写入。
    • 异步写（asynchronous write）：将数据先存在缓存后，就将控制返回给调用者。

  • 随后释放（free-behind）：一旦请求下一个页面，就从缓冲区中删除一个页面。

  • 预先读取（read-ahead）：请求的页面和一些之后的页面可以一起读取并缓存。

11.7 恢复

11.7.1 一致性检查
  • 一致性检查程序（consistency checker）：比较目录结构的数据和磁盘的数据块，并且试图修复发现的不一致。
11.7.2 基于日志的文件系统
  • 基于日志的面向事务（log-based transaction-oriented）：所有元数据修改按顺序写到日志。
  • 事务（transaction）：执行特定任务的一组操作。
  • 环形缓冲区（circular buffer）
11.7.3 其他解决方法
  • 快照（snapshot）：保留旧的指针和块。
11.7.4 备份和恢复
  • 备份（backup）
  • 恢复（restore）

11.8 NFS

11.8.1 概述
  • NFS 将一组互连的工作站视作一组具有独立文件系统的独立机器。目的是为了允许透明（根据显示请求）共享这些文件系统。
  • NFS 规范区分两种服务
    • 由安装机制提供的服务（对应安装协议）
    • 真正远程文件访问服务（对应远程文件访问协议）
  • NFS 协议（由RPC表示，是实现透明远程文件访问的基础）
    • 安装协议
    • 远程文件访问协议
11.8.2 安装协议
  • 安装协议（mount protocol）：在客户机和服务器之间建立初始逻辑链接。
  • 安装操作包括需要安装的远程目录名称和存储它的服务器名称。
  • 输出列表（export list）：服务器维护，用于列出可以安装的本地文件系统，以及允许安装它们的机器名称。
  • 当服务器收到符合导出列表的安装请求时，它就返回给客户机一个文件句柄。
11.8.3 NFS协议（支持异构）

  • NFS 协议为远程文件提供的一组 RPC 操作

    • 搜索目录内的文件
    • 读取一组目录条目
    • 操作链接和目录
    • 访问文件属性
    • 读写文件（不能并发）

  • NFS 服务器的一个突出特点是无状态的。服务器没有与 UNIX 的打开文件表和文件结构相似。因此每个请求必须提供整套参数，包括唯一文件标识符和用于特定操作的文件内的绝对偏移。

  • 单个 NFS 写入程序调用确保是原子的，不会与其他写入同一文件的调用混合。

  • NFS 通过 VFS 集成到操作系统

    image-20210115201400257

    这种架构的优点是，客户机和服务器都是相同的，因此机器可以是客户机或服务器，或两个都是。服务器的实际服务是由内核线程执行的。

11.8.4 路径名称转换
  • 路径名称转换（path-name translation）：将路径名称，如 /usr/local/dir1/file.txt 解析成单独的目录条目或组件：usr、local 和 dir1。路径名称转换包括：将路径分解成组件名称，并且为每对组件名和目录 vnode 执行单独的 NFS 查找调用。
11.8.5 远程操作
  • 远程文件操作可以直接转换成对应的 RPC
  • 为了提高性能也采用了缓冲和缓存技术
  • 有两个缓存：
    • 文件属性（索引节点信息）缓存
    • 文件块缓存

Chapter 12 大容量存储结构

重点：磁盘连接、磁盘调度算法、RAID

12.1 大容量存储结构概述

12.1.1 磁盘
  • 磁盘结构

    image-20210115202625070

  • 传输速率（transfer rate）：在驱动器和计算机之间的数据流的速率。

  • 定位时间（positioning time）或随机访问时间（random access time）

    • 寻道时间（seek time）：移动磁臂到所要柱面的所需时间；
    • 旋转延迟（rotation latency）：转磁臂到所要扇区的所需时间。

  • 磁头碰撞（head crash）：磁头有时可能损坏磁盘表面。

  • 磁盘驱动器通过称为 I/O总线（I/O bus）的一组电缆连到计算机。

    • 硬盘技术接口（Advanced Technology Attachment，ATA）
    • 串行ATA（Serial ATA，SATA）
    • 外部串行 ATA（external SATA，eSATA）
    • 通用串口总线（Universal Serial Bus，USB）
    • 光纤通道（Fiber Channel，FC）

  • 主控制器 & 磁盘控制器

12.1.2 固态硬盘
  • 固态硬盘（Solid-State Disk，SSD）
  • SSD 的每兆字节更昂贵、容量也更大、寿命更短、更小、更快、更节能。
12.1.3 磁带

12.2 磁盘结构

  • 扇区 0 是最外面柱面的第一个磁道的第一个扇区。
  • 在实践中，由于两个原因，映射很难实现
    • 大多数磁盘都有一些缺陷扇区
    • 对于某些驱动器，每个磁道的扇区数并不是常量
  • 恒定线速度（Constant Linear Velocity，CLV）
  • 恒定角速度（Constant Angular Velocity，CAV）

12.3 磁盘链接

  • 本地：通过I/O端口（主机连接存储）
  • 远程：分布式文件系统（网络连接存储）
12.3.1 主机连接存储
  • 主机连接存储（host-attached store）：通过本地I/O端口来访问的存储。
12.3.2 网络连接存储

  • 网络连接存储（network-attached store，NAS）：一种专用存储系统，可以通过数据网络来远程访问，采用网络协议。

    image-20210115204430094

  • 网络连接存储的缺点

    • 存储 I/O 操作消耗数据网络的带宽，从而增加网络通信的延迟
12.3.3 存储区域网络
  • 存储区域网络（Storage Area Network，SAN）：是专用网络，采用存储协议连接服务器和存储单元。
  • SAN 的优势
    • 灵活性：多个主机和多个存储阵列可以连接到同一个 SAN 上，存储可以动态分配到主机。

image-20210115204910311

12.4 磁盘调度

12.4.1 FCFS 调度
12.4.2 SSTF 调度
  • 最短寻道时间优先（Shortest-Seek-Time-First，SSTF）
  • 存在饥饿
12.4.3 SCAN 调度
12.4.4 C-SCAN 调度
12.4.5 LOOK 调度
12.4.6 磁盘调度算法的选择
  • SSTF 和 LOOK 是默认算法的合理选择。

12.5 磁盘管理

12.5.1 磁盘格式化
  • 低级格式化（low-level formatting）：也成为物理格式化。将磁盘分成扇区，以便磁盘控制器能读写。由厂商制作磁盘时完成。
  • 扇区的数据结构
    • 头部
    • 数据区域（通常 512 字节大小）
    • 尾部
    • 头部和尾部包含了一些磁盘控制器的使用信息，如扇区号和纠错代码。
  • 分区（partition）：将磁盘分为由柱面组成的多个分区。操作系统可以将每个分区作为一个单独磁盘。
  • 逻辑格式化（logical formatting）：创建文件系统。
12.5.2 引导块

  • 自举程序（bootstrap）：初始化系统的所有部分，从CPU寄存器到设备控制器和内存，接着启动操作系统。在磁盘上找到操作系统内核，加载到内存，并转到起始地址一边开始操作系统的执行。从磁盘上调入完整的引导程序。被存放在ROM上。

  • 完整的引导程序存储在磁盘固定位置上的 “ 启动块 ” 中。

  • 启动磁盘（boot disk）或系统磁盘（system disk）：有启动分区的磁盘。

  • Windows下

    • 引导分区（boot partition）：包含操作系统和设备驱动程序。
    • 引导扇区（boot sector）：引导分区的第一个扇区。

    image-20210115212057847

12.5.3 坏块

  • 扇区备用（sector sparing）或扇区转寄（sector forwarding）：设备控制器可以采用备用块来逻辑地替代坏块。可能会使操作系统的磁盘调度算法失效。

  • 扇区滑动（sector slipping）：扇区备用的替代方法。从坏块开始的所有块向后移动。

  • 硬错误（hard error）：不可恢复，造成数据丢失。

12.6 交换空间管理

  • 交换空间的设计和实现的主要目标：为虚拟内存提供最佳吞吐量。
12.6.1 交换空间的使用
12.6.2 交换空间位置
  • 位于普通文件系统之上
  • 一个单独的磁盘分区
12.6.3 交换空间管理例子

  • 交换空间仅仅用作备份以存储匿名内存（anonymous memory）页面，包括给栈、堆和进程未初始化数据等的分配内存。

  • 页槽（page slot）

  • 交换映射（swap map）：一个整型计数器数组，其中每个整数对应于交换区的页槽。如果计数器为0，则页槽可用，如果大于0则表示页槽被交换页面占据。计数器的数值表示交换页面的映射数量。

image-20210115212118343

12.7 RAID 结构

  • 磁盘冗余阵列（Redundant Array of Independent Disk，RAID）：多种磁盘组织技术的统称。通常用于处理性能与可靠性问题。
12.7.1 通过冗余提高可靠性
  • 平均故障时间（mean time to failure）
  • 镜像卷的平均故障时间取决于
    • 单个磁盘的平均故障时间
    • 平均维修时间：用于替换损坏磁盘并恢复其上数据的平均时间
12.7.2 通过并行处理提高性能
  • 数据分条（data striping）
    • 位级分条（bit-level striping）
    • 块级分条（block-level striping）
  • 磁盘系统的并行化通过数据分条实现，有两个主要目标：
    • 通过负载平衡，增加了多个小访问（即页面访问）的吞吐量。
    • 降低大访问的响应时间。
12.7.3 RAID 级别
  • RAID 0：非冗余条带
  • RAID 1：镜像磁盘
  • RAID 2：内存式错误纠正码
  • RAID 3：位交错奇偶校验
  • RAID 4：块交错奇偶检验
  • RAID 5：块交错分布式奇偶校验
  • RAID 6：P+Q冗余

image-20210115213045746image-20210115213058614

12.7.4 RAID 级别的选择
12.7.5 扩展
12.7.6 RAID 的问题

12.8 稳定存储实现

  • 磁盘写入导致三种结果
    • 成功完成
    • 部分故障
    • 完全故障
  • 系统为每个逻辑块维护两个物理块，以检测写入时故障。

Chapter 13 I/O 系统

重点：I/O硬件三要素，四组寄存器、轮询、中断、DMA、时钟与定时器、异步与非阻塞、流、性能

13.1 概述

  • I/O 设备技术呈现两个冲突趋势

    • 软件和硬件的接口标准化日益增长
    • I/O 设备的种类也日益增多

  • I/O 设备的基本要素

    • 端口（port）
    • 总线（bus）
    • 设备控制器（controller）

  • 设备驱动程序（device driver）：为 I/O 子系统提供了统一的设备访问接口。

13.2 I/O 硬件

  • 计算机设备种类
    • 存储设备
    • 传输设备
    • 人机交互设备
  • 端口（port）：设备与计算机的通信通过一个连接点或端口。
  • 总线（bus）：是一组线路和通过线路传输信息的严格定义的一个协议。
    • PCI 总线：常用PC系统总线，将处理器内存子系统连接到快速设备。
    • 扩展总线（expansion bus）：连接相对较慢的设备，如键盘和串口和USB端口。
    • 小型计算机系统接口（Small Computer System Interface，SCSI）：连接磁盘。
    • PCI Express（PCIe）：吞吐量高达 16GB/s
    • HyperTransport：吞吐量高达 25GB/s
  • 控制器（controller）：可以操作端口、总线或设备的一组电子器件。
    • 串行端口控制器是一个简单的控制器。
    • SCSI 总线控制器复杂。
  • 处理器如何对控制器发出命令和数据以便完成 I/O 传输？
    • 控制器具有一个或多个寄存器，用于数据和控制信号。
    • 处理器通过读写这些寄存器的位模式来与控制器通信。
    • 或者，设备控制器可以支持内存映射I/O。在这种情况下，设备控制寄存器被映射到处理器的地址空间。处理器执行 I/O 请求是通过标准数据传输指令读写映射到物理内存的设备控制器。
  • I/O 端口通常由四个寄存器组成
    • 数据输入寄存器（data-in register）：被主机读取以获取数据。
    • 数据输出寄存器（data-out register）：被主机写入以发送数据。
    • 状态寄存器（status register）：包含主机可以读取的位，描述相关设备控制器的状态。
    • 控制寄存器（control register）：可由主机写入，以便启动命令或更改设备模式。
13.2.1 轮询
  • 当主机需要通过端口来输出数据时，主机与控制器的协调如下：
    1. 主机重复读取设备状态寄存器的忙位，直到该位清零。(主机存在忙等待)
    2. 主机设置控制寄存器的写位，并写一个字节到数据输出寄存器。
    3. 主机设置控制寄存器中的命令就绪位。
    4. 当控制器注意到命令就绪位已经设置，则设置忙位（避免被其他请求打断）。
    5. 控制器读取控制寄存器，看到写命令。它从数据输出寄存器中读取一个字节，并向设备执行 I/O 操作。
    6. 控制器清除命令就绪位，清除状态寄存器的故障位表示设备 I/O 成功，清除忙位表示完成。
13.2.2 中断（Interrupt）
  • 中断请求线（Interrupt-Request Line，IRL）：CPU 硬件，用于传输中断信号。CPU 在执行完每条指令后，都会检测 IRL 。
  • 中断处理程序（interrupt-handler routine）：确定中断原因，执行必要处理，执行状态恢复，并执行返回中断指令以便 CPU 回到中断前的执行状态。
  • 引起（raise） & 捕获（catch） & 分派（dispatch）
  • 非屏蔽中断（nonmaskable interrupt）：保留用于诸如不可恢复的内存错误等事件。
  • 可屏蔽中断（maskable interrupt）：在执行不得中断的关键指令序列之前，它可由 CPU 关闭。
  • 中断向量（interrupt vector）
  • 中断链（interrupt chaining）：中断向量内的每个元素指向中断处理程序链表的头部。当中断发生时，相应链表上的中断处理程序都一一检测，直到发现可以处理请求的那个为止。因为计算机设备常常多于中断向量内的地址，所以采用这种方法。
  • 中断优先级（interrupt priority level）：能使 CPU 延迟处理低优先级中断而不屏蔽所有中断，并且可以让高优先级中断抢占低优先级中断。
  • 异常（exception）：由CPU 内部产生。中断是外部设备产生。
  • 陷阱（trap）：应用程序产生。
  • 多线程内核架构非常适合实现多优先级中断，并且确保中断处理的优先级高于内核后台处理和用户程序。
13.2.3 直接内存访问（DMA）

  • 程序控制 I/O（Programmed I/O，PIO）：通过昂贵的通用处理器来观察状态位并且按字节来发送数据到控制寄存器。

  • 使用 DMA 的原因：为了别面因 PIO 而增加 CPU 负担。

  • 直接内存访问（Direct-Memory Access）寄存器：专用处理器。

  • DMA 命令块：在启动 DMA 传输时，被主机写到内存。

    • 传输来源地址指针
    • 传输目标地址指针
    • 传输的字节数

  • DMA 请求（DMA-request） & DMA 确认（DMA-acknowledge）

    • DMA 控制器与设备控制器之间的握手，通过这一对线路进行。
    • 有数据需要传输时，设备控制器发送信号到DMA 请求线路。这个信号会使得 DMA 控制器占用内存总线，发送所需地址到内存地址总线，并发送信号到 DMA 确认线路。
    • 当设备控制器收到 DMA 确认信号时，它就传输数据到内存，并清除 DMA 请求信号。

  • 周期窃取（cycle stealing）：DMA 控制器占据内存总线时，CPU 被暂时阻止内存访问。设备会周期性的产生 DMA 请求。可能会减慢 CPU 计算。

  • 直接虚拟地址访问（Direct Virtual Memory Access，DVMA）：直接对虚拟地址而不是物理地址进行访问，这里所用的虚拟内存地址需要虚拟到物理地址的转换。DVMA 可以直接实现两个内存映射设备之间的传输，而无需 CPU 干预或采用内存。

13.3 应用程序 I/O 接口

image-20210116101216097

方面 差异 例子
数据传输模式 字符，块 中断，磁盘
访问方式 顺序，随机 调制解调器，光盘
传输方式 同步，异步 磁带，键盘
分享 专用，共享 磁带，键盘
设备速度 延迟，寻道时间，传输速率，操作延迟
I/O 方向 只读，只写，读写 光盘，图形控制器，磁盘

  • 字符流或块：

  • 顺序访问或随机访问

  • 同步或异步

  • 共享或专用

  • 操作速度

  • 读写、只读、只写

  • 逃逸（escape） 或 后门（back door）：能使应用程序透明传递任何命令到设备控制器。绕过操作系统。

13.3.1 块与字符设备
  • 块设备接口（block-device interface）：为磁盘驱动器和其他基于块设备的访问，规定了所需的各个方面。
  • 键盘是通过字符流接口（character-stream interface）访问的一个设备例子。
13.3.2 网络设备
  • 套接字（socket）
13.3.3 时钟与定时器
  • 硬件时钟和计时器提供的基本功能
    • 获取当前时间
    • 获取经过时间
    • 设置定时器，以便在 T 时触发操作 X。
  • 可编程间隔定时器（programmable interval timer）：测量经过时间和触发操作的硬件。
13.3.4 非阻塞与异步 I/O
  • 当应用程序执行阻塞（blocking）系统调用时，应用程序的执行就被挂起。
  • 非阻塞 I/O
  • 异步系统调用：非阻塞系统调用的一种替代方式。异步调用立即返回，无需等待 I/O 完成。
  • 非阻塞调用会立即返回任何有用数据，异步调用的传输过程会完整执行，但是将在未来的某个时间。
13.3.5 向量 I/O
  • 向量 I/O（vectored I/O）：允许系统调用，来执行涉及多个位置的多个 I/O 操作。
  • 多个单独缓冲区可以通过一个系统调用来传输它们的内容，避免上下文切换和系统调用消耗。

13.4 内核 I/O 子系统

13.4.1 I/O 调度

  • 调度可以改善系统整体性能，可以在进程间公平共享设备访问，可以减少 I/O 完成所需的平均等待时间。

  • 操作系统开放人员通过为每个设备维护一个请求等待队列，来实现队列。

  • 设备状态表（device-status table）

    image-20210116103413470

13.4.2 缓冲
  • 缓冲区（buffer）：是一块内存区域，用于保存在两个设备之间或在设备和应用程序之间传输的数据。
  • 采用缓冲的原因
    • 处理数据流的生产者与消费者之间的速度不匹配（speed dismatch）
    • 协调传输数据大小不一的设备（size dismatch）
    • 支持应用程序 I/O 的复制语义（数据一致性）
13.4.3 缓存
  • 缓存（cache）是保存数据副本的告诉内存区域。
  • 缓存和缓冲的功能不同，但是有时一个内存区域可以用于两个目的。
13.4.4 假脱机与设备预留
  • 假脱机（spool）：是保存设备输出的缓冲区。
  • 应用程序的输出先是假脱机到一个单独的磁盘文件。当应用程序完成打印时，假脱机系统排序相应的假脱机文件，以便输出到打印机。
13.4.5 错误处理
  • SCSI 协议报告 SCSI 设备故障的详细级别
    1. 感应键（sense key）：用于标识故障的一般性质，如硬件错误或非法请求。
    2. 额外感应代码（additional sense code）：用于表示故障类型，如错误命令参数或自检失败。
    3. 额外感应代码修饰词（additional sense-code qualifier） ：用于给出更详细的信息，如哪个命令参数出错或哪个硬件子系统自检失败。
13.4.6 I/O 保护
  • 为了防止用户执行非法 I/O ，我们定义所有 I/O 指令为特权指令。
  • 内存保护系统保护任何内存映射和 I/O 端口内存位置，以便阻止用户访问。
13.4.7 内核数据结构

image-20210116110153051

13.5 I/O 请求转成硬件

image-20210116110303717

13.6 流

  • 流（stream）：UNIX System V 中的机制，能使应用程序自动组合驱动程序代码流水线。是在设备驱动程序和用户级进程之间的全双工连接。

  • 流的构成

    • 流头（stream head）：与用户进程相连
    • 流模块（stream module）：读队列和写队列
    • 驱动程序端（driver end）

    image-20210116110608502

  • 流控制（flow control）

  • 流 I/O 是异步的，除非用户进程与流头直接通信。

13.7 性能

  • I/O 是系统性能的一个主要因素。

  • 为了改善 I/O 效率，可以采用多种方法

    • 减少上下文切换的次数。
    • 减少设备和应用程序之间传递数据时的内存数据的复制次数。
    • 通过大传输、智能控制器、轮询，减少中断频率。
    • 通过 DMA 智能控制器和通道来为主 CPU 承担简单数据复制，增加并发。
    • 将处理原语移到硬件，允许控制器操作与 CPU 和总线操作并发。
    • 平衡 CPU、内存子系统、总线和 I/O 的性能，因为任何移除的过载都会引起其他部分的空闲。

  • I/O 功能到底应该在哪里实现呢？

    • 最初，在应用程序级别上实现实验性的 I/O 算法。（应用层）
    • 当应用程序级别的算法证明它的价值时，可以在内核中重新实现它。（内核）
    • 高性能可以通过设备或控制器的专用硬件实现来得到。（硬件）

    image-20210116111645564

Tags:

VirMach 便宜 VPS

QNews

QNews