操作系统

• 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: 磁盘

操作系统在 408 试卷中占据 35 分，是分数第三高的科目，包含十道选择题和两道大题。

需要注意的是，内存管理和 I/O 管理与计算机组成原理有很多相似之处。建议在复习时将这两部时对比学习，以深化对它们的理解。除此外，进程管理和文件管理也是重要的内容，大题常常会让你编写代码去解决一个同步问题，因此需要熟练掌握信号量的使用和同步逻辑的设计。

---

操作系统的考察目标包含如下内容（来自 408 考研大纲）：

1. 掌握操作系统的基本概念、方法和原理，了解操作系统的结构、功能和服务，理解操作系统所采用的策略、算法和机制。
2. 能够从计算机系统的角度理解并描述应用程序、操作系统内核和计算机硬件协作完成任务的过程。
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的两种 运行模式：内核模式（又称为特权模式、系统模式或超级用户模式）和 用户模式 是操作系统设计中用于隔离系统关键任务与普通任务的机制，以提高系统的安全性和稳定性。

内核模式

内核模式（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) 的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性。

进程

进程是系统资源分配的基本单位。进程拥有独立的系统资源，包括内存空间、文件描述符、CPU 时间片等，这些资源的分配由操作系统负责。

进程和程序

程序是 静态的，进程是 动态的，进程可以理解成运行的程序，两者的具体区别如下：

• 程序
  • 程序是一组指令的静态集合，它存储在磁盘等持久性存储介质中。
  • 程序是被动的，它本身并不执行任何操作。
  • 一个程序可以多次运行，每次运行都会创建一个新的进程。
• 进程
  • 进程是程序在内存中执行的实例。
  • 当一个程序被加载到内存中并开始执行时，操作系统会创建一个进程。
  • 进程是动态的，它代表了程序的执行过程。

进程控制块

操作系统通过 进程控制块（PCB，Process Control Block）对进程进行管理。 PCB 中保存了 操作系统管理进程所需的关键信息，当发生 进程切换（上下文切换） 时，需要将运行进程的状态保存到 PCB 中。

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

解释：

• 进程标识信息：用于唯一标识进程
• 进程控制信息：用于操作系统进行调度和管理
• 处理机状态信息：保存 CPU 运行现场，实现 进程切换
• 资源信息：记录进程占用的系统资源

进程控制块 在操作系统 进程 管理的多个阶段都发挥重要作用：

• 进程创建和终止：在进程创建时，操作系统为它新建一个PCB（进程控制块）。该结构在进程存在期间常驻内存，可以随时存取，并在进程结束时删除。
• 进程调度：当操作系统进行进程调度时，会根据PCB中存储的信息（如优先级、进程状态）来决定哪个进程应该获得CPU的控制权。

父子进程

在操作系统中，进程 是程序执行的基本单位。父子进程 是指通过 进程创建机制 生成的一种层级关系：

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

子进程 通常由 父进程 通过 fork 系统调用 建立。子进程是父进程的副本，继承父进程的代码段、数据段、堆栈等资源，但拥有自己的独立地址空间和执行状态。两者可以通过进程间通信（IPC）机制（如管道、信号、共享内存）进行数据交换或同步。

fork 系统调用的声明为 pid_t fork(void)，其返回值为一个整数，可以用于判定该程序是 父进程 还是 子进程：

• 在 父进程 中，返回值为 子进程 的 pid（pid > 0）。
• 在 子进程 中，返回值为 0。

fork 调用后，父进程 和 子进程 从 fork 调用后的下一条指令开始继续执行。子进程 获得 父进程 的 代码、数据 和 堆栈 的副本，但两者地址空间独立。

除了 fork 系统调用外，还有一个 exec 系统调用，两种具有不同的功能，需要能够区分：

• fork：创建 子进程，复制 资源，不改变程序，父子进程 继续执行原代码。
• exec：在当前 进程 中加载并执行一个新的程序。替换当前 进程 的 代码段、数据段 和 堆栈，保留部分 资源 如 进程 PID，不涉及到并发。

此外，父进程 可以通过 wait 系统调用等待 子进程 执行结束，并获取 子进程 的退出状态，防止 进程 成为 僵尸进程。

线程

线程是系统调度的基本单位。多核处理器可以将系统中的不同 线程 调度到不同的 CPU 逻辑核心上，所以在同一个时刻，系统中的 线程 可能会在不同的逻辑核心上并行运行。

每个 进程 启动的时候，都包含一个 线程（主线程），可以在主线程外创建更多的 线程。

如上图所示，一个 进程 中的所有 线程 都共享 虚拟地址空间 和系统 资源，但是每个 线程 都维护自己的 堆栈、寄存器和一些额外信息。

在一个 进程 中没有创建 线程 时，则该 进程 为 单线程进程，否则该 进程 中包含多个 线程。

单线程进程 只有一个线程，独占进程的虚拟地址空间和系统资源，如文件描述符和内存。线程维护自己的堆栈和寄存器，无需同步，但无法利用多核CPU，且阻塞会影响整个进程，适合简单任务，但并发性和响应性较差。

多线程进程 包含多个线程，共享虚拟地址空间和系统资源，如代码段和堆，便于高效通信。每个线程有独立的堆栈、寄存器和线程ID，需通过锁等机制同步以避免资源竞争。

进程的状态

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

状态种类

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

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

状态转化

1. 就绪态 → 运行态
   • 调度：当操作系统的调度器选择一个就绪状态的进程分配给处理器时，该进程就会从就绪状态转换到运行状态。
2. 运行态 → 就绪态
   • 时间片用完：如果系统使用时间共享调度，当进程的时间片用完，它会被中断并放回就绪队列。
   • 优先级更高的进程就绪：在优先级调度算法中，如果一个优先级更高的进程变为就绪状态，当前运行的进程可能会被挂起。
   • 自愿放弃 CPU：进程可能主动放弃CPU，比如它发出了一个系统调用请求其他资源。
3. 运行态 → 阻塞态
   • I/O 请求：进程进行I/O操作，由于I/O设备比CPU慢得多，进程会被挂起直到I/O完成。
   • 等待资源：进程等待不可用的资源，如信号量、互斥锁等。
   • 等待事件：如等待其他进程的信号、消息或者某个条件的发生。
4. 阻塞态 → 就绪态
   • I/O 完成：当 I/O 操作完成，相应的进程会被移至就绪队列。
   • 资源获得：进程所等待的资源变得可用，如获得了互斥锁。
   • 事件发生：进程所等待的事件发生了，如接收到了另一个进程发出的信号。

进程内存空间

• 用户空间（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）是指在同一计算机系统中，两个或多个 进程 之间交换数据或信号的机制。常见的 进程间通信 方式主要包含 共享内存、管道、消息队列、信号、套接字 和 信号量。

管道 是一种最基本的 进程间通信 方式，主要用于具有亲缘关系的 进程 之间的数据传递。它分为 无名管道 和 有名管道，其中 无名管道 只能在 父子进程 或 兄弟进程 之间使用，而 有名管道（FIFO）通过文件系统中的特殊文件实现，不要求通信双方存在亲缘关系。

管道 以 字节流 的形式传输数据，具备先进先出的特性，但 只支持单向通信，并且效率相对较低，适用于简单的任务传递。

# 在 linux shell 中使用 | 操作符创建一个管道通信
# cat 进程的标准输出（stdout）会从管道输入到 grep 进程的标准输入（stdin）
cat file.txt | grep word

共享内存 是效率最高的一种 进程间通信 方式，允许多个进程将同一段 物理内存 映射到各自的 虚拟地址空间 中，从而直接读写该区域的数据。

由于不需要内核频繁介入，通信效率极高，非常适合大规模数据的快速传输。然而，由于多个进程可同时访问内存区域，必须通过额外的同步机制如 信号量 或 互斥锁 来确保数据一致性，否则容易出现竞争条件和数据错误。

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

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

用户级线程和内核级线程

• 用户级线程 （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 时间。
• 调度器通常分为长程、中程和短程调度器，如前文所述。

调度时机

调度的时机可能包括以下情况：

• 进程进入或退出系统
• 进程从运行状态变为阻塞状态
• 或者一个时间片结束。

调度方式

• 抢占式调度（Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将 CPU 分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
• 非抢占式调度（Non-Preemptive）：在这种方式下，一旦 CPU 分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待 I/O 操作）。

闲逛进程

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

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

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

两种线程的调度

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

调度算法

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

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

先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序 分配依次执行。先到达的进程先执行，后续进程等待直到前一个进程执行才能进一步执行。

最短作业优先

最短作业优先（Shortest Job First，SJF）算法在从就绪队列中选择进程时，会 选择运行时间最短 的进程进行执行。

在题目中进程的运行时间一般都是给定的，所以 SJF 算法比较容易实现。但是在真实的系统中进程的运行时间是不确定的，所以在使用该算法时操作系统需要对进程的运行时间进行预估。

最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）算法从就绪队列中选择 响应比 最高的进程进行执行。

其中 响应比（Response Ratio）的计算公式如下：

其中 $W$ （Waiting Time）为进程的等待时间， $B$ （Burst Time）为进程的要求服务时间（从执行开始到结束所需时间）。

这种计算策略可以有效地避免饥饿现象，即一个进程等待了很长时间但仍没有得到执行。一个进程的等待时间越长，其 响应比 就会更大，进而优先得到执行机会。一个进程的执行时间很长，其 响应比 就会越小，会优先调度其他进程。

• 时刻 0：只有 P1 到达，执行 P1。
• 时刻 5：P1 执行完成。P2 的 响应比 为 (4 + 3) / 3 ≈ 2.33，P3 的 响应比 为 (3 + 8) / 8 = 1.375，P4 的 响应比 为 (2 + 6) / 6 ≈ 1.33，此时 P2 的 响应比 最大，执行 P2。
• 时刻 8：P2 执行完成。P3 的 响应比 为 (6 + 8) / 8 = 1.75，P4 的 响应比 为 (5 + 6) / 6 ≈ 1.83。此时 P4 的 响应比 更大，执行 P4。
• 时刻 14：P4 执行完成，只剩下 P3 了，最后执行 P3。

所以进程的执行顺序为 P1、P2、P4、P3，每个进程的时间指标如下表所示：

优先级调度

优先级调度是一种基于进程优先级的调度算法，广泛应用于操作系统中。根据是否允许中断当前正在执行的进程，优先级调度可分为 非抢占式优先级调度 和 抢占式优先级调度 两种形式。

在 非抢占式优先级调度 中，调度器总是从就绪队列（等待队列）中选择优先级最高的进程执行。一旦某个进程开始执行，它将持续运行直到完成（或主动释放 CPU，例如进入等待 I/O 状态）。在此期间，即使有更高优先级的进程到达并加入就绪队列，当前进程也不会被中断，而是继续执行直到结束。

抢占式优先级调度旨在确保系统中任何时刻运行的进程始终是优先级最高的。当一个更高优先级的进程到达时，调度器会立即暂停当前运行的低优先级进程（将其挂起并加入就绪队列），然后将 CPU 分配给新到达的高优先级进程。

下图给出了两种优先级调度方式的实例对比，其中绿色的进程表示执行态，黄色表示就绪态：