操作系统

• 1: 计算机系统概述
• 1.1: 操作系统概念
• 1.2: 程序运行环境
• 1.3: 操作系统结构
• 2: 进程管理
• 2.1: 进程和线程
• 2.2: 处理机调度
• 2.3: 同步和互斥
• 2.4: 经典同步问题
• 2.5: 死锁
• 3: 内存管理
• 3.1: 内存管理概念
• 3.2: 虚拟内存管理
• 4: 文件管理
• 4.1: 文件
• 4.2: 目录
• 4.3: 文件系统
• 5: I/O 管理
• 5.1: I/O 设备
• 5.2: 设备管理
• 5.3: 磁盘

1 - 计算机系统概述

# 操作系统基础

## 操作系统的基本概念

## 操作系统发展历程

## 程序运行环境

- CPU运行模式：内核模式、用户模式
- 中断和异常的处理
- 系统调用
- 程序的链接和装入
- 程序运行时的内存映像与地址空间

## 操作系统结构

- 分层、模块化
- 宏内核、微内核
- 外核

## 操作系统引导

## 虚拟机

1.1 - 操作系统概念

概念

操作系统 是计算机系统中的一个核心软件组件，负责管理和控制计算机硬件，为用户和应用程序提供服务。

操作系统特征

1. 并发（Concurrence）：操作系统 具备同时处理和调度多个程序的能力。
2. 共享（Sharing）：系统中的资源可供内存中多个并发的进程共同使用。
3. 虚拟（Virtual）：将物理的实物虚拟为逻辑上的对应物。
4. 异步（Asynchronism）：任务可以不按固定的顺序执行，因此同一操作的结果可能因执行的时序而异。

目标和功能

• 作为用户语句计算机硬件系统之间的接口。
• 作为计算机系统资源的管理者。
• 实现了对计算机资源的抽象。

发展历程

操作系统 的发展历程经历了 手工操作、批处理操作、分时操作、实时操作 这四个阶段：

1. 手工操作 阶段：
   • 时间背景：计算机的早期阶段。
   • 特点：没有 操作系统，用户直接使用计算机硬件。
   • 操作方式：用户在一个时刻将自己的程序载入计算机，然后执行。执行完毕后，将结果记录并释放计算机。
   • 问题：效率低，CPU 大部分时间处于空闲状态。
2. 批处理操作系统：
   • 单道批处理系统：
     • 特点：系统一次只执行一个任务。完成后再执行下一个。
     • 操作方式：用户的多个作业被收集到一个作业队列中，操作系统 按照队列的顺序逐一执行。
     • 问题：CPU 利用率仍然不高，因为在 I/O 操作时，CPU 仍然处于空闲状态。
   • 多道批处理系统：
     • 特点：在内存中同时加载多个作业，并使它们共享 CPU。
     • 操作方式：当一个作业进行 I/O 操作时，CPU 可以切换到另一个作业，从而提高了 CPU 的利用率。
     • 优势：提高了系统吞吐量和 CPU 利用率。
3. 分时操作系统：
   • 时间背景：20 世纪 60 年代。
   • 特点：允许多个用户通过终端同时访问计算机。
   • 操作方式：操作系统 为每个用户提供了一个“虚拟机”的概念，使每个用户感觉自己独占了整个系统。实际上，系统在用户之间快速切换，为每个用户提供少量的 CPU 时间。
   • 优势：提高了交互性和多用户并发访问的能力。
   • 示例：Unix 操作系统在其初期就是一个分时系统。
4. 实时操作系统：
   • 特点：系统必须在严格的时间限制内响应外部输入。
   • 分类：
     • 硬实时系统：不满足时限会导致严重的后果，如飞行控制系统。
     • 软实时系统：不满足时限可能会降低系统的性能，但不会导致灾难，如多媒体播放器。
   • 操作方式：实时 操作系统 的任务调度是基于优先级的，且通常会预先定义每个任务的执行时间。
   • 优势：满足特定应用场景的实时需求，如嵌入式系统和工业控制系统。

操作系统引导

引导流程

操作系统 引导的具体流程如下：

1. 电源开机（Power-On）：
   • 当你按下计算机的电源键时，电源开始向主板和各个硬件供电。此时，系统首先进行加电自检。这个过程是由存储在主板 ROM 芯片中的基本输入/输出系统（BIOS）或统一可扩展固件接口（UEFI）固件执行的。
2. BIOS/UEFI 阶段：
   • BIOS/UEFI 会读取启动设备的首扇区（MBR 或 GPT），其中包含 引导加载器（Bootloader）的代码。
3. 引导加载器（Bootloader）：
   • 引导加载器 是一小段程序，它的主要任务是加载 操作系统 内核。
   • 常见的 bootloader 有
     • GRUB（Grand Unified Bootloader）：常用于 Linux 系统，功能强大，支持多系统引导。
     • Windows Boot Manager：Windows 操作系统的引导管理器。
   • 引导加载器 会将 操作系统 内核从存储设备（通常是硬盘）加载到内存中。
4. 加载操作系统内核：
   • 操作系统 内核是 操作系统 的核心部分，负责管理系统的各种资源，如内存、进程、设备等。引导加载器 将内核加载到内存后，会将控制权交给内核。
5. 内核初始化：
   • 操作系统 内核开始运行并进行自我初始化。它会检测和配置系统上的硬件资源，例如设置中断、初始化设备驱动、建立内存管理结构等。
6. 启动系统服务和守护进程：
   • 在内核初始化后，它会启动一系列的系统进程或服务来管理各种系统任务。

1.2 - 程序运行环境

CPU 运行模式

CPU的两种 运行模式：内核模式（又称为特权模式、系统模式或超级用户模式）和 用户模式 是操作系统设计中用于隔离系统关键任务与普通任务的机制，以提高系统的安全性和稳定性。

Ring 0 与 Ring 3 在 可执行指令集 和 可访问资源 上的边界可参考下图：

内核模式

内核模式（Kernel Mode）是操作系统内核运行的环境，具有 最高权限，能够直接访问硬件和所有系统资源。

特点

• 完全权限：内核模式下的代码可以直接操作硬件（如CPU、内存、I/O 设备等），执行特权指令。
• 核心功能：操作系统内核负责管理进程、内存、文件系统和设备驱动等核心功能，这些都在内核模式下完成。
• 上下文切换：用户模式程序通过系统调用进入内核模式，完成操作后返回用户模式。
• 高风险：内核模式的错误可能导致系统崩溃，因此需要极高的稳定性。

特权指令（Privileged Instruction）是指在计算机系统中只能由操作系统 内核态下 的程序执行的特殊指令。这些指令通常涉及对硬件资源或系统关键功能的直接控制，具有较高的权限，常见的特权指令包含如下类型：

• 硬件控制：如设置中断使能、修改处理器状态寄存器。
• 内存管理：如修改页表、设置内存保护。
• 进程管理：如创建或终止进程、更改进程优先级。
• I/O 操作：直接访问硬件设备或端口。
• 系统调用相关：如切换到内核态以执行系统服务。

用户模式

用户模式（User Mode）是普通 应用程序 运行的环境，运行在 受限的权限级别。用户程序（如浏览器、文本编辑器等）通常在此模式下运行。

特点

• 权限受限：用户模式下的程序无法直接访问硬件或核心系统资源（如内存、CPU 寄存器等），需要通过系统调用（System Call）请求操作系统服务。
• 隔离性：每个用户程序运行在自己的地址空间，相互隔离，防止程序直接干扰其他程序或系统。
• 安全性：由于权限受限，用户程序的错误（如崩溃）通常不会直接影响操作系统。
• 执行方式：用户程序通过调用库函数或API间接与操作系统交互。

用户模式和内核模式是操作系统实现安全性和稳定性的核心机制。用户模式提供隔离和安全的环境运行应用程序，而内核模式负责核心资源管理和特权操作。两者通过系统调用等机制协作，共同完成计算任务。

系统调用

系统调用（system call）是运行在用户模式的应用程序与操作系统内核之间的 接口。当应用程序需要执行一些它在用户模式下不能直接完成的任务（如文件操作、网络通信、创建进程等）时，它可以通过系统调用来请求操作系统内核在内核模式下为其执行这些操作。

系统调用的过程如上图所示，从用户态进入内核态，完成后再返回用户态：

• 当用户程序执行系统调用（或触发中断）时，CPU 会自动 切换到内核态，这时控制权就交给了操作系统。
• 操作系统执行完后，再通过特定指令（如iret, sysret, eret）切回用户态。

特点

• 特权级的转换：应用程序通常在用户模式下运行，而操作系统内核在内核模式下运行。系统调用提供了从用户模式到内核模式的一种安全的转换机制，这样内核可以代表应用程序执行特权操作。
• 系统调用的类型：常见的系统调用类型包括进程管理（如创建、终止进程）、文件操作（如打开、读取、写入、关闭文件）、网络通信、设备控制、内存管理等。
• 性能开销：执行系统调用涉及上下文切换，从用户模式到内核模式，然后再返回。这会带来一定的性能开销。因此，频繁地进行系统调用可能会影响应用程序的性能。

举个实际的 x86 例子

1. 用户程序执行 int 0x80（系统调用指令）；
2. CPU 自动：
   • 切换到 Ring 0（即内核态）；
   • 跳转到操作系统设定的系统调用处理函数；
3. 操作系统执行相关服务；
4. 执行 iret 返回用户程序；
5. CPU 自动：
   • 切回 Ring 3（即用户态）；
   • 恢复用户程序继续运行。

程序的链接

程序的链接是将编译后的代码模块（通常是目标文件）和其他所需的库组合在一起，生成一个可以执行的程序或库的过程。链接过程由 链接器（linker）完成。

根据所使用的库的链接方式，链接可以分为 静态链接 和 动态链接。

• 静态链接：
  • 当使用静态链接时，外部代码和库在链接阶段被 整合到最终的可执行文件中。这意味着，如果程序使用了某个库的函数，那么这些函数的代码会被复制到最终的二进制文件中。
  • 结果是一个较大的可执行文件，因为它包含了所有必要的代码以独立运行。
• 动态链接：
  • 使用动态链接时，外部库不会被直接嵌入到最终的可执行文件中。相反，程序包含了对动态链接库（如 Linux 中的.so 文件或 Windows 中的.dll 文件）的引用。当程序启动时，这些库会被 动态加载 到内存中供程序使用。
  • 动态链接的库通常称为动态链接库（Dynamic Link Libraries，DLL）或共享对象（Shared Object）。

静态链接

简单来说，对于 静态链接，依赖 直接作为 二进制 被打包进最后的 可执行程序 中，所以可以直接 跨机器运行（当然操作系统得一样）。

动态链接

对于 动态链接，程序只保存依赖的库地址，依赖与可执行程序 分开保存，当程序执行时再去 动态地加载依赖库。对于动态链接，拷贝可执行程序到另一台机器不一定能直接运行，这需要另外一台机器也保存有相应依赖。

两者的区别如下表所示：

程序的装入

程序的装入是指将程序或进程的代码和数据从磁盘加载到主存（RAM）中的过程，使其准备好被 CPU 执行。装入过程在程序执行周期中是必不可少的一部分，通常由操作系统中的 装入器（loader）完成。

绝对装入

适用于 单道程序环境。在编译时，若知道程序驻留在内存的某个位置，则编译程序将产生绝对地址的目标地址。绝对装入程序按照装入模块的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际地址完全相同，因此不需要对程序和数据的地址进行修改。

另外，程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时在转换为绝对地址。

可重定位装入

在 多道程序环境 下，多个目标模块的起始地址通常都从 0 开始，程序中的其他地址都是相对于起始地址的，此时应采用可重定位装入方式。根据内存的当前情况，将装入模块装入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为 重定位，又因为地位变换通常是在进程装入时一次完成的，故称为 静态重定位。

当一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则无法装入。此外，作业一旦装入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。

动态运行时装入

也称为 动态重定位。装入程序把装入模块装入内存后，并不立即把装入模块的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时进行。因此，装入内存后的所有地址都是相对地址。这种地址需要一个重定位寄存器的支持。

动态重定位的优点在于可以将程序分配到不连续的存储区；在程序运行之前可以只装入部分代码即可运行，然后在程序运行期间，根据需要动态申请分配内存。

1.3 - 操作系统结构

分层和模块化

操作系统的设计和结构在历史上经历了多种不同的方法和技巧，为了增加 可维护性、灵活性 和 可扩展性。分层 和 模块化 是操作系统设计中两种主要的技术方法。

• 分层结构：
  • 概念：在分层的操作系统中，系统被划分为多个层次或“层”，每层都为其上的层提供服务，并依赖于其下的层。
  • 优点：
    • 每层只需与其直接的上下层进行交互，简化了设计和调试。
    • 提高了灵活性，因为改变某一层的实现不会影响到其他层。
    • 有助于保护和安全性，因为较低的层（如硬件访问层）被封装起来，上层代码不能直接访问。

• 模块化结构：
  • 概念：模块化操作系统基于模块的概念，每个模块都有一个特定的功能，各个模块之间的交互通过定义良好的接口进行。模块化与面向对象编程中的封装和抽象概念类似。
  • 优点：
    • 易于维护和更新。如果某个模块需要更改或修复，可以独立于其他模块进行。
    • 提高了可扩展性。新的功能或模块可以相对容易地添加到系统中。
    • 增加了系统的可靠性和稳定性，因为每个模块的功能都被限定在明确的边界内。

内核架构

微内核

微内核（microkernel）是一种最小化的内核设计，只保留最核心的功能（如线程管理、虚拟内存、进程间通信等）在内核态运行，其他功能（如文件系统、设备驱动、网络协议栈等）以用户态服务的形式运行。

• 特点：
  • 只有最基本的服务（如基本的进程和线程管理、地址空间和 IPC）运行在 内核态。
  • 其他服务，如设备驱动、文件系统等，作为 用户空间 的独立进程运行。
  • 内核和服务间通过消息传递进行通信。
• 优点：
  • 更高的系统稳定性。用户空间的服务（如驱动程序）如果崩溃，不会影响整个系统。
  • 更加灵活，允许在运行时更改或添加服务。
  • 更容易扩展和维护。
• 缺点：
  • 由于需要频繁的上下文切换和消息传递，通常 性能会稍逊于宏内核。
• 示例：IOS 是基于微内核的系统。

宏内核

宏内核（monolithic kernel）将所有操作系统功能集成在一个大的内核程序中，运行在内核态。

• 特点：
  • 在单一的地址空间中运行大部分系统服务，如设备驱动、文件系统、网络协议等。
  • 所有的内核服务都运行在 内核态。
• 优点：
  • 由于所有的服务都在同一个地址空间中运行，因此服务间的通信较快。
  • 传统上，宏内核系统比微内核系统性能更高。
• 缺点：
  • 如果内核中的一个部分失败，整个系统都可能崩溃。
  • 随着功能的增加，内核可能会变得臃肿，导致维护困难。
• 示例：传统的 UNIX 系统、Linux 都是基于宏内核的。

虚拟机

虚拟机（Virtual Machine, VM）是一种通过软件模拟真实计算机功能的 虚拟化技术，能够在一台物理主机上创建多个独立的虚拟计算机环境。每个虚拟机都具备与真实硬件相似的运行环境，可以运行独立的操作系统和应用程序，仿佛它们运行在专属的物理设备上。这种技术广泛应用于服务器整合、测试开发、跨平台应用等场景。

虚拟机监视器

Hypervisor，也称为虚拟机监视器（Virtual Machine Monitor, VMM），是 虚拟化技术 的核心组件，运行在物理主机和虚拟机之间的中间软件层。它负责协调和管理多个虚拟机，使它们能够共享底层 物理硬件资源，同时保持彼此 隔离。Hypervisor 的主要职责包括：

1. 创建与管理虚拟机：为每个虚拟机分配独立的 虚拟化硬件资源（如 CPU、内存、存储和网络）。
2. 硬件资源抽象：通过虚拟化技术，Hypervisor 将 物理硬件资源抽象化，使每个虚拟机认为自己独占硬件资源，从而运行独立的操作系统。
3. 隔离与安全：确保虚拟机之间的运行互不干扰，增强系统安全性。

Hypervisor 的特权级

Hypervisor 通常运行在比操作系统更高的 特权级（如硬件虚拟化支持的 VMX root mode 或 Ring -1），以便有效管理虚拟机及其资源。相比之下，虚拟机中的操作系统通常运行在较低的特权级（如 Ring 0）。这种特权级差异确保 Hypervisor 能够完全控制硬件资源并协调多个虚拟机的运行，而不会与虚拟机中的操作系统发生冲突。

2 - 进程管理

# 进程管理

## 进程和线程

- 进程、线程概念
- 进程、线程状态和转换
- 线程的实现
- 进程、线程的组织和控制
- 进程间通信

## CPU调度和上下文切换

- 概念和目标
- 调度实现方式
- 调度算法
- 上下文及其切换机制

## 同步与互斥

- 概念
- 软件和硬件实现方法
- 锁
- 信号量
- 条件变量
- 经典同步问题

## 死锁

- 概念
- 死锁预防
- 死锁避免
- 死锁检测和解除

2.1 - 进程和线程

在多道程序环境下，允许多个程序并发执行，为此操作系统引入了 进程 (Process) 的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性。

进程

进程是系统资源分配的基本单位。操作系统以进程为单位建立相对独立的资源环境，例如 虚拟地址空间、打开的文件、访问权限以及其他内核资源。

不同进程通常拥有独立的虚拟地址空间，因此一个进程不能直接访问另一个进程中的数据。同一进程中的多个线程则共享进程所拥有的虚拟地址空间和大部分系统资源。

可以将进程和线程的作用概括为：

• 进程 主要解决“资源归谁所有”的问题，是资源拥有和保护的基本单位。
• 线程 主要解决“由谁执行代码”的问题，是处理机调度和执行的基本单位。

进程和程序

程序是 静态的，进程是 动态的。进程可以理解为程序的一次执行过程，两者的具体区别如下：

• 程序
  • 程序是一组指令和数据的静态集合，通常存储在磁盘等持久性存储介质中。
  • 程序本身是被动的，不会自行执行。
  • 同一个程序可以被多次运行，每次运行通常都会创建一个新的进程。
• 进程
  • 进程是程序的一次执行过程。
  • 当程序被加载并开始执行时，操作系统会为其创建进程及相应的管理信息。
  • 进程是动态的，具有创建、运行、阻塞、终止等生命周期状态。

进程控制块

操作系统通过 进程控制块（PCB，Process Control Block）管理每一个进程。

可以把 PCB 看作操作系统为每个进程建立的一张 管理档案，其中记录了操作系统管理该进程所需的各种信息。只要进程存在，对应的 PCB 就始终保存在内存中，操作系统几乎所有与进程相关的操作都需要访问它。

PCB 主要包含以下几类信息：

各类信息的作用如下：

• 进程标识信息：用于唯一标识和区分不同进程。
• 进程控制信息：供操作系统进行调度和管理，例如记录进程当前处于就绪态、运行态还是阻塞态，以及进程的优先级等。
• 处理机状态信息：保存程序暂停执行时的 CPU 运行现场，例如程序计数器、寄存器和程序状态字等，使程序再次运行时能够从原来的位置继续执行。
• 资源信息：记录进程拥有或使用的系统资源，例如虚拟地址空间、打开的文件等，便于操作系统统一管理和回收。

在传统的 单线程进程模型 中，一个进程只有一个执行流，因此程序计数器、寄存器和程序状态字等处理机现场可以直接记录在 PCB 中。

引入线程后，一个进程中可能存在多个执行流，每个线程都需要分别保存自己的程序计数器、寄存器、栈和调度状态。这些线程级信息通常记录在线程控制块或相应的内核线程结构中，而 PCB 主要保存进程级的地址空间和资源信息。

PCB 在进程的整个生命周期中都会被操作系统使用，主要体现在以下几个方面：

• 进程创建：操作系统为新进程创建对应的 PCB，并初始化其中的各项信息。
• 进程管理：操作系统通过 PCB 记录和维护进程的状态、优先级、资源等信息。
• 进程切换：在传统单线程模型中，操作系统保存当前进程的运行现场，并恢复下一进程的运行现场。
• 进程终止：操作系统释放进程占用的资源，并删除对应的 PCB。

在线程模型中，处理机调度器实际选择的是某个可运行线程，并将其调度到某个逻辑核心上执行。

父子进程

在操作系统中，父子进程 是通过进程创建机制形成的一种层级关系：

• 父进程 ：创建新进程的进程。
• 子进程 ：由父进程创建的进程。

在 UNIX 和 Linux 系统中，子进程通常由父进程通过 fork 系统调用 创建。

fork 创建子进程后，子进程获得与父进程内容近似相同、但逻辑上独立的虚拟地址空间，包括代码段、数据段、堆和栈。父子进程拥有各自独立的执行状态，一方修改自己地址空间中的数据，通常不会直接影响另一方。

现代操作系统通常采用 写时复制（Copy On Write）机制实现 fork。在 fork 刚完成时，父子进程可以暂时共享相同的物理内存页；只有当父进程或子进程尝试修改某个内存页时，操作系统才真正复制该页。

子进程还会继承父进程打开的文件描述符等部分资源。父子进程也可以通过进程间通信（IPC）机制，例如管道、信号和共享内存，进行数据交换或同步。

fork 系统调用的声明为：

pid_t fork(void);

其返回值可以用于判断当前执行的是父进程还是子进程：

• 在 父进程 中，返回值为子进程的 PID，即返回值大于 0。
• 在 子进程 中，返回值为 0。
• 如果创建失败，则在父进程中返回 -1，不会创建子进程。

fork 调用成功后，父进程和子进程都会从 fork 返回处继续执行，但二者获得的返回值不同，并且可能按照不同的顺序被调度运行。

除了 fork 外，还需要理解 exec 系列调用。两者功能不同：

• fork：创建一个新的子进程。子进程获得父进程地址空间和部分资源的副本，父子进程继续执行原来的程序。
• exec：在当前进程中装入并执行一个新程序，用新程序的代码段、数据段、堆和栈替换原有的进程映像，但通常保留 PID 等进程身份信息。

exec 不创建新的进程，因此不会增加新的并发执行流。exec 调用成功后，原程序不会继续执行；只有调用失败时，exec 才会返回。

此外，父进程可以通过 wait 或 waitpid 系统调用等待子进程终止，并读取子进程的退出状态，从而完成对子进程的回收。

线程

线程是处理机调度和执行的基本单位。

进程主要负责拥有虚拟地址空间、打开的文件等系统资源，线程则表示进程内部的一条执行流。操作系统调度时，实际选择的是某个可运行线程，并将其调度到某个 CPU 逻辑核心上执行。

多核处理器可以将不同线程调度到不同的 逻辑核心 上，因此多个线程可以在同一时刻并行运行。

每个进程启动时，至少包含一个线程，通常称为 主线程。主线程可以继续创建其他线程，从而形成多线程进程。

同一进程中的线程共享进程级资源，主要包括：

• 虚拟地址空间；
• 代码段；
• 全局变量和静态变量；
• 堆；
• 打开的文件；
• 其他进程级系统资源。

每个线程则拥有自己独立的执行现场，主要包括：

• 线程标识符；
• 程序计数器；
• 寄存器组；
• 栈；
• 线程状态；
• 调度优先级等调度信息。

线程拥有独立的栈，是指每个线程在进程虚拟地址空间中具有自己的栈区域。由于同一进程中的线程共享虚拟地址空间，一个线程原则上仍可能通过指针访问其他线程栈中的数据，因此线程之间并不存在像进程之间那样严格的地址空间隔离。

在一个进程中没有额外创建线程时，该进程为 单线程进程；如果一个进程中包含多个线程，则称为 多线程进程。

单线程进程

单线程进程只有一个执行线程，因此进程的虚拟地址空间和打开的文件等进程级资源只由该线程使用，不存在进程内部的线程同步问题。

单线程进程具有以下特点：

• 结构简单，程序设计和调试相对容易。
• 不需要处理多个线程之间的共享数据竞争。
• 当唯一线程因等待 I/O 或其他事件而阻塞时，进程中没有其他线程可以继续执行。
• 任一时刻最多只有一个线程在一个逻辑核心上运行，因此不能依靠进程内部的多个线程同时利用多个逻辑核心。

单线程虽然可能在不同时间被调度到不同逻辑核心上运行，但在任一时刻只能占用一个逻辑核心执行。

多线程进程

多线程进程包含多个线程，这些线程共享进程的虚拟地址空间和系统资源，但分别拥有自己的程序计数器、寄存器和栈。

多线程进程具有以下特点：

• 多个线程可以直接访问共享的全局变量、堆和其他进程级资源，通信效率较高。
• 多个线程可以被调度到不同逻辑核心上并行执行，提高处理器利用率。
• 当一个线程阻塞时，其他线程仍有机会继续运行。
• 多个线程同时访问共享数据时，可能发生竞态条件，需要使用互斥锁、信号量等同步机制。
• 同一进程中的线程隔离性较弱，一个线程发生严重错误可能导致整个进程终止。

完整的进程虚拟地址空间布局，以及线程视角下共享区域和私有区域的关系，可参考下图：

引入线程后，一个进程可能同时包含多个执行流，每个线程都拥有各自独立的程序计数器、寄存器和栈，因此这些与执行和调度相关的信息不能再统一保存在 PCB 中，而需要为每个线程分别维护一份管理信息，通常称为 TCB（Thread Control Block，线程控制块）。

因此，在现代操作系统中，可以将 PCB 和 TCB 的职责概括如下：

• PCB（进程控制块）：管理整个进程拥有的资源，例如虚拟地址空间、页表、打开的文件、权限等进程级信息。
• TCB（线程控制块）：管理单个线程的执行现场，例如程序计数器、寄存器、栈、线程状态以及调度信息等。

二者的关系如下图所示：

可以看出，一个 PCB 对应一个 进程，而一个 进程 可以包含多个 线程，因此一个 PCB 通常会关联多个 TCB。

操作系统在进行资源管理时，主要访问 PCB；而进行线程调度和上下文切换时，则主要访问对应线程的 TCB，保存和恢复该线程的程序计数器、寄存器等运行现场。

进程和线程对比

因此，可以将进程和线程之间的关系概括为：

进程是资源的拥有者和保护边界，线程是进程内部的执行流和处理机调度对象。

进程的状态

进程状态 是指在操作系统中，一个 进程 在执行过程中的不同阶段。它反映了 进程 当前正在做什么，以及是否可以被 CPU 执行。

状态种类

不同的操作系统对 进程状态 的划分可能不同，但常见的包括以下几种：

1. 创建状态（New）：当 进程 被创建但还未分配资源或执行时，它处于 创建状态。
2. 就绪状态（Ready）：在 就绪状态 中，进程 已准备好执行，但由于操作系统调度算法或其他原因，尚未获得 CPU 时间片。
3. 运行状态（Running）：在 运行状态 中，进程 正在执行指令并占用 CPU。
4. 阻塞状态（Blocked）：当 进程 在等待某些事件发生时，如等待 I/O 操作完成或等待其他资源时，它会进入 阻塞状态。在 阻塞状态 下，进程 暂停执行，直到等待的事件发生。
5. 终止状态（Terminated）：当 进程 执行完毕或被操作系统终止时，它进入 终止状态。

状态转化

1. 就绪态 → 运行态

2. 运行态 → 就绪态

3. 运行态 → 阻塞态

4. 阻塞态 → 就绪态

进程内存空间

• 用户空间（User Space）：包含 进程 执行的用户程序代码和数据。在 用户空间 中，进程 可以执行各种任务，如运行应用程序、访问文件系统等。用户空间 对于应用程序是可见的，但对于操作系统中的核心功能是不可见的。
  1. 代码区（Text Segment）：也称为“可执行代码区”，存储了 进程 的可执行代码，包括程序的指令和只读数据。这个区域通常是只读的，因为程序的指令在运行时不应被修改。
  2. 数据区（Data Segment），数据区分为两个子区域：
     • 初始化数据区（Initialized Data Segment）：存储全局和静态变量以及初始化的数据。这些变量在程序运行前就已经分配了内存并初始化。
     • 未初始化数据区（Uninitialized Data Segment），也称为 BSS（Block Started by Symbol）段，存储全局和静态变量，但这些变量没有显式的初始化值。操作系统会在程序启动时自动将这个区域初始化为零。
  3. 堆区（Heap）：堆区 是 动态分配内存 的地方，用于存储程序运行时需要的变量和数据结构。在 堆 中分配的内存需要手动释放，以避免内存泄漏。
  4. 栈区（Stack）：栈区 用于存储函数调用和局部变量。每个函数调用都会在栈上创建一个栈帧，栈帧包含了函数的参数、局部变量以及函数返回地址。栈 是一种后进先出（LIFO）的数据结构，它的大小通常有限，由操作系统或编程语言定义。
  5. 内存映射区域（Memory Mapped Region）：这是一些操作系统或运行时库的扩展，用于存储动态链接库（DLL）和共享库的信息以及其他系统数据结构。
• 内核空间（Kernel Space）：内核空间 包含了操作系统的核心代码和数据结构，如页表、调度程序和系统调用接口等。内核空间 具有更高的特权级别，可以执行特权指令并且访问系统的各种资源，内核空间 对于用户程序是不可见的。

函数调用时内存结构

EBP (base pointer) 指向函数栈（栈帧）的底部（高地址），函数执行过程中在栈帧中分配局部变量，栈帧由高地址向低地址增长，ESP（stack pointer）一直指向栈顶。

每个函数的栈帧中包含如下内容：

• 上一个函数的 EBP
• 该函数的局部变量
• 如果函数内有 call 指令的话，还需要保存额外信息：
  • 下一个函数的参数：依次存储从第 n 个到第 1 个，从高地址到低地址
  • 返回地址：当前 PC 指向的位置，即 call 指令的下一条指令的地址

在函数的调用过程中，调用函数叫做 caller，被调用函数叫做 callee。当我们从 caller 中调用 callee 时，callee 的 EBP 指向的物理地址的上下存储单元分别包含 caller 的返回地址以及 caller 所在栈帧的 EBP，当我们在 callee 中执行 ret 指令时，计算机可以跳转到 caller 中 call 指令的下一条并开始执行，同时 caller 的栈帧也会被恢复。

进程间通信

进程间通信（Inter-Process Communication，IPC）是指在同一计算机系统中，两个或多个 进程 之间交换数据或信号的机制。常见的 进程间通信 方式主要包含 共享内存、管道、消息队列、信号、套接字 和 信号量。

下图汇总了常见 IPC 方式的数据流向、效率与同步需求差异：

管道

管道（Pipe） 是一种最基本的 进程间通信（IPC） 机制，本质上是由操作系统内核维护的一块 内存缓冲区。进程并不是直接把数据写给另一个进程，而是：

写进程 → 管道内核缓冲区 → 读进程

管道通常具有 固定大小 的缓冲区，数据只存在于内存中，不以普通磁盘文件的形式保存。管道中的数据按照 先进先出（FIFO） 的顺序被读取，因此先写入的数据会先被读出。

可以把管道理解成一个由内核维护的缓冲区：

• 读端：用于从管道中读取数据
  • 读进程执行 read() 时，操作系统从管道缓冲区中取出数据，并将数据复制到读进程的用户空间。
• 写端：用于向管道中写入数据
  • 写进程执行 write() 时，数据并不是直接进入读进程的地址空间，而是先被复制到 内核维护的管道缓冲区 中。

可以直接类比 生产者消费者问题：

• 管道 未满：写进程可以继续写；管道 已满 时，写进程会被阻塞，等待读进程取走数据。
• 管道 非空：读进程可以继续读；管道 为空 时，读进程会被阻塞，等待写进程写入数据。

因此，管道的读和写操作都可能发生阻塞。

管道中的数据以字节流形式传输，并按 FIFO（先进先出） 顺序读取。经典管道是单向通信（半双工），若要实现双向通信，通常需要建立两个管道。

管道只在内存中存在，容量受 内核缓冲区大小 限制，而不是磁盘容量限制。

管道可以分为：

• 无名管道（anonymous pipe）
• 有名管道（named pipe / FIFO）

无名管道 没有文件系统中的名字，通常用于具有亲缘关系的进程，例如父子进程、兄弟进程。

有名管道（FIFO） 在文件系统中具有一个名字，因此不要求通信进程之间具有亲缘关系。

共享内存

共享内存 是效率很高的一种 进程间通信（IPC） 方式。多个进程可以将同一组 物理内存页 映射到各自的 虚拟地址空间 中，从而直接读写这片共享区域。

例如：

注意，不同进程的虚拟页号（VPN）可以不同，但可以映射到同一个物理页号（PPN）：

因此，A 和 B 虽然使用不同的虚拟地址访问，但最终访问的是同一块物理内存。

反过来，一个进程的一个虚拟页只能在某一时刻映射到一个物理页：

而不能：

因为同一个虚拟地址必须具有确定的地址转换关系，否则 CPU 无法确定访问哪个物理地址。

共享内存的核心思想可以概括为：

多个进程的不同虚拟地址 → 同一个物理内存区域。

由于数据直接在共享内存中读写，通信过程中不需要像管道那样反复在进程与内核之间复制数据，因此数据传输效率很高。但多个进程可能同时读写同一数据，所以仍然需要借助 信号量、互斥锁等同步机制 防止竞争条件。

消息队列

消息队列 是一种基于内核的数据结构，允许多个进程以消息为单位进行通信，具有良好的结构化和独立性。进程通过系统调用将消息发送到队列中或从中接收消息，可以实现同步与异步的通信模式。

相比 管道，消息队列 的通信更加灵活，支持优先级管理，适用于需要有序、分类传输数据的场景。但由于涉及内核操作，性能开销相对 共享内存 较大。

用户级线程和内核级线程

• 用户级线程 （ULT，User Level Thread）
  • 用户级线程 是由应用程序通过线程库来实现的，操作系统内核并不直接感知到这些 线程 的存在。
  • 线程的创建、调度和管理都由应用程序在 用户空间 完成。
• 内核级线程 （KLT，Kernel Level Thread）
  • 内核级线程 是由操作系统内核直接支持的线程。
  • 线程的创建、调度和管理都由 操作系统内核 完成。

线程模型

操作系统中的 线程实现方式 称为 线程模型，不同的 线程模型 在 用户级线程（ULT）和 内核级线程（KLT）的设计上各有不同。

系统中的 线程模型 可以分为如下三种：

• 纯用户态：所有的线程操作都在用户空间中进行，内核对线程的存在一无所知。
• 纯系统态：线程由操作系统内核直接支持和管理，内核负责线程的创建、调度和管理。
• 混合方案：应用程序可以在用户空间管理多个用户级线程，这些线程映射到较少数目的内核级线程。

混合方案中的映射关系

如果使用 混合方案 的 线程模型 的话，用户级线程 和 内核级线程 的映射方式也可以分为如下几种：

• 一对一：每一个用户级线程都对应一个内核级线程。
• 多对一：多个用户级线程映射到同一个内核级线程上。
• 多对多：多个用户级线程映射到多个内核级线程上。

2.2 - 处理机调度

调度指标

在操作系统里，调度（Scheduling） 是把 CPU 时间合理分配给多个进程（或线程）的核心机制。调度的好坏直接决定系统的响应速度、吞吐能力以及资源利用效率。为了衡量调度策略的优劣，我们通常用一组 调度指标 来量化：

1. 系统层面的宏观指标——关注整个计算机系统的运行状态，如 CPU 的利用率、系统整体的吞吐量等。这类指标帮助我们了解系统在整体负载下是否“忙碌”或出现瓶颈。
2. 进程层面的微观指标——关注单个进程在调度器眼中的表现，包括它何时进入调度队列、等待多久才被分配 CPU、实际执行多长时间以及最终何时完成等。这类指标可以帮助我们比较不同调度算法（FCFS、SJF、RR、优先级调度等）对单个作业的影响。

系统层面

系统层面主要关注 CPU 利用率和吞吐量这两个指标：

进程层面

从进程视角而言，进程从被创建到执行结束会有一系列时间周期作为指标：

系统调度过程

为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

1. 高级调度（长程调度，Long-term Scheduling）:
   • 功能：高级调度 主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
   • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
   • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
2. 中级调度（中程调度，Mid-term Scheduling）:
   • 功能：中级调度 涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
   • 主要目标：为高级调度和初级调度器优化内存使用。
   • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
3. 初级调度（短程调度，Short-term Scheduling）:
   • 功能：初级调度 决定哪个进程应当被赋予 CPU 时间片，即决定下一个运行在处理器上的进程。
   • 主要目标：确保 CPU 的高效利用。
   • 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器

调度器/调度程序（scheduler）:

• 调度器 是操作系统中负责决定下一个要执行的进程或线程的部分。
• 基于特定的调度算法（如轮转、优先级调度、短作业优先等），它决定哪个进程或线程应当获得 CPU 时间。
• 调度器 通常分为长程、中程和短程调度器，如前文所述。

调度时机

可能引发调度的事件大致有以下几类：

1. 当前进程主动让出 CPU：进程正常结束、异常终止，或因等待 I/O、等待信号量等原因由运行态转为阻塞态。
2. 有进程进入就绪队列：新进程被创建，或某个阻塞进程等待的事件已完成（如 I/O 完成）而转为就绪态。
3. 时间片用完：时钟中断到达，当前进程用完了分配给它的时间片。

其中第 1 类事件的共同点是 当前进程已经无法继续占用 CPU，因此无论采用哪种调度方式都必然发生调度；而第 2、3 类事件的共同点是 当前进程本来还可以继续运行，是否此刻切换进程，取决于系统采用的是抢占式还是非抢占式调度。

调度方式

非抢占式调度（Non-Preemptive，又称非剥夺方式）：一旦把 CPU 分配给某个进程，就让它一直运行下去，直到它 自己结束或主动转为阻塞态，才把 CPU 交给下一个进程。也就是说，只有上面第 1 类事件才会触发调度：

• 新进程创建、更高优先级的进程变为就绪 —— 不调度，新到达的进程只能在就绪队列中排队等待。
• 时间片到期 —— 不适用（非抢占式算法本身不使用时间片）。

抢占式调度（Preemptive，又称剥夺方式）：当进程正在运行时，操作系统可以强行中断它、把它放回就绪队列，再把 CPU 分配给另一个进程。除第 1 类事件外，第 2、3 类事件同样可能触发调度：

• 新进程创建，且其优先级（或剩余运行时间等指标）优于当前进程 —— 立即抢占，当前进程由运行态回到就绪态。
• 阻塞进程被唤醒进入就绪队列，且优于当前进程 —— 立即抢占。
• 时间片用完 —— 必然切换（如时间片轮转）。

因此，判断某个算法是否抢占式，一个直观的检验标准是：

一个新进程到达时，正在运行的进程会不会被打断？ 会，就是抢占式；不会，就是非抢占式。

下图以“P1 先到达、P2 后到达且优先级更高”为例，对比两种调度方式在 P2 到达这一时刻的不同处理：

闲逛进程

闲逛进程（Idle Process）是操作系统中的一个特殊进程，当系统没有任何其他可运行的进程时，调度器会将 CPU 的控制权交给这个进程。闲逛进程的主要目的是确保在没有任务可执行的情况下，CPU 不会空转，从而防止 CPU 进入不受控制的状态。

在 Linux 操作系统中，闲逛进程的进程 ID 通常是 0，被称为 swapper 或 idle task。它是系统启动时创建的第一个进程，始终在内核态运行，确保当没有其他可调度任务时，CPU 有事情可做。

在 Windows 系统中，闲逛进程被称为 System Idle Process，同样用于在系统空闲时占据 CPU 时间，以维持系统的运行稳定。如下图所示：

两种线程的调度

• 内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
• 用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
• 对于 内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
• 对于 用户级线程，因为内核不知道它们的存在，所以内核无法直接调度它们。线程之间的上下文切换可能比 内核级线程 更快，但在多处理器系统中，它们可能无法充分利用所有的处理器。

调度算法

根据 是否可抢占 可以对调度算法进行如下分类：

• 非抢占型调度算法：先来先服务、最短任务优先、最高响应比优先
• 抢占型调度算法：时间片轮转、多级反馈队列

先来先服务