操作系统期末复习知识点

1 计算机系统概述

一、操作系统的基本概念

1. 操作系统定义
   操作系统是一个大型程序系统，负责计算机系统软/硬件资源的分配，控制和协调并发活动，提供用户接口，为用户提供良好工作环境。
2. 操作系统核心功能
   • 硬件资源管理：处理器管理、存储器管理、设备管理
   • 软件资源管理：文件管理（信息、数据管理）
   • 并发活动控制与协调
   • 用户界面与环境提供
3. 操作系统主要特征
   • 并发（Concurrence）：宏观上多个事件同一时间段内同时运行，微观上交替执行；并行是同一时刻多个事件同时发生，并发是单处理机 OS 最重要特征。
   • 共享（Sharing）
     • 互斥共享：一段时间内仅允许一个进程访问，如打印机等临界资源。
     • 同时访问：宏观上“同时”，微观上轮流访问，如处理机、内存、磁盘等。
   • 异步（Asynchronism）：任务以不可预知速度推进，由资源竞争导致不确定性。
   • 虚拟（Virtual）：隐藏实际实现复杂性，为上层提供抽象表示，如进程（处理器抽象）、虚拟存储器（主存抽象）、文件（I/O 设备抽象）。
4. 操作系统的抽象表示
   操作系统对计算机硬件进行抽象，为应用程序提供统一接口：
   • 处理器 → 进程
   • 主存 → 虚拟存储器
   • I/O 设备 → 文件

二、操作系统的发展历程

1. 手工操作阶段
   特点为直接通过纸带、卡片等外设操作计算机，存在严重人机矛盾，CPU 速度提升后，人工操作时间占比过高，资源利用率极低。
2. 批处理系统阶段
   • 联机批处理：由监督程序管理，将多个作业通过输入机存入磁带，主机依次处理，减少人工干预，但主机仍需等待外设。
   • 脱机批处理：引入卫星机，负责作业输入输出，主机专注计算，提升了主机资源利用率。
3. 多道程序系统
   允许多个程序同时驻存内存，CPU 交替执行，可使 CPU 与 I/O 设备并行工作，大幅提升资源利用率。
4. 分时系统
   采用时间片轮转机制，为多个终端用户提供交互式服务，保证每个用户都能及时获得系统响应。
5. 现代操作系统分支
   包括分布式操作系统、云操作系统、国产操作系统（鸿蒙、银河麒麟等）、主流操作系统（Linux、Windows、Mac OS 等）。
6. 关键系统发展
   • Unix：1969 年 Ken Thompson 用汇编写出原型；1973 年用 C 语言重写，奠定跨平台基础。
   • Linux：1991 年诞生时仅 1 万行代码，后续发展至超 2000 万行代码规模。

三、程序运行环境

1. CPU 运行模式
   • 用户模式：用户程序运行的模式，权限低，只能受限访问内存等资源。
   • 内核模式：操作系统内核运行的模式，权限高，可直接访问硬件资源，处理中断、异常等。
2. 中断和异常的处理
   中断和异常是 CPU 由用户态切换至内核态的触发条件，中断用于处理外设请求（如 I/O 完成），异常用于处理程序运行错误（如除零、缺页），处理流程需完成上下文保存、中断/异常处理、上下文恢复。
3. 系统调用
   • 定义：内核提供的通用访问接口，是用户程序请求 OS 服务的唯一途径，用于访问 CPU、内存、I/O 等内核管理资源。
   • 类型（五大类）
     1. 进程控制：fork（Unix）/ CreateProcess（Windows）、exit、wait 等。
     2. 文件管理：open、read、write、close 等。
     3. 设备管理：ioctl（Unix）、SetConsoleMode（Windows）等。
     4. 信息维护：getpid（Unix）、GetCurrentProcessID（Windows）等。
     5. 通信：pipe（Unix）、CreatePipe（Windows）等。
   • 执行流程：应用程序（用户态）→ 系统调用接口 → 内核函数（内核态）→ 硬件，执行后由内核态返回用户态。
4. 程序的链接与装入
   以 hello.c 为例的 GCC + Linux 处理流程：
   • 预处理：hello.c → hello.i（cpp 工具，展开头文件、处理宏）。
   • 编译：hello.i → hello.s（cc1 工具，生成汇编代码）。
   • 汇编：hello.s → hello.o（as 工具，生成可重定位目标文件）。
   • 链接：hello.o + 库文件 → hello 可执行目标文件（ld 工具，完成符号解析与重定位）。
5. 程序运行时内存映像与地址空间
   32 位系统典型内存映像（从高地址到低地址）：
   • 内核虚存区（0xC0000000 开始）：系统代码、系统数据。
   • 共享库内存映射区域：共享库代码与数据。
   • 堆（heap）：动态内存分配区域（由 malloc 管理）。
   • 读写数据段（.data）：已初始化全局 / 静态变量。
   • 只读代码段（.text/.rodata）：程序指令、只读常量。
   • 未初始化数据段（.bss）：未初始化全局 / 静态变量（运行时初始化为 0）。
   • 用户栈（User stack）：函数调用栈帧、局部变量（%esp 指向栈顶）。

四、操作系统结构

1. 分层结构
   按功能分层，上层为下层抽象，下层为上层实现，层间通过接口交互，降低模块耦合，但层序固定，灵活性不足。
2. 模块化结构
   将 OS 划分为多个功能模块，模块间通过明确定义的接口通信，可按需组合，但模块依赖关系复杂，难以维护。
3. 宏内核（Monolithic Kernel）
   • 结构特点：用户服务与内核服务运行在同一地址空间，内核包含调度器、虚拟内存、设备驱动等所有核心功能。
   • 优缺点：尺寸大，执行速度快；可扩展性差，单个服务崩溃易导致整个系统崩溃。
   • 实例：Linux、BSD、Windows 95/98、AIX。
   • 文件读取流程：用户进程 → 系统调用 → 虚拟文件系统（VFS）→ IDE 驱动 → 硬件，通过函数调用直接访问内核逻辑。
4. 微内核（Microkernel）
   • 结构特点：用户服务与内核服务运行在不同地址空间，内核仅保留基本功能（IPC、虚拟内存、调度），其他服务（文件、设备驱动）以用户态服务器形式存在。
   • 优缺点：尺寸小，可扩展性强，单个服务崩溃不影响全局；执行速度慢（需频繁 IPC 通信），代码量大。
   • 实例：QNX、Symbian、鸿蒙、Mac OS X。
   • 文件读取流程：用户进程 → 向 FS 进程发 read 请求 → FS 进程请求 IDE 进程 → 内核通过 IPC 协调 → 结果返回用户进程。
5. 混合内核
   结合宏内核与微内核优点，内核保留部分核心服务（如调度、虚拟内存），其他服务可动态加载，兼顾性能与扩展性，实例为 Windows 7/10/Server 2003。
6. 外核
   核心思想是“资源能力暴露”，内核仅负责资源保护与分配，将资源管理决策交给应用程序，为特殊场景（如高性能服务器）提供高度定制化能力。

五、操作系统引导

1. 引导原理
   系统上电后从固定内存地址开始执行，ROM/EEPROM 中存储的引导加载程序（Bootloader）负责定位、加载内核至内存并启动。
2. 两步引导流程
   • 第一步：ROM 代码加载固定位置的引导块。
   • 第二步：引导块加载完整的引导加载程序（如 GRUB），再由其选择并加载内核。
3. 最小化 OS 引导示例
   • 编写 boot.asm 汇编程序（包含引导扇区标志 0xaa55，大小为 512 字节）。
   • 编译生成二进制文件 boot.bin，制作软盘镜像 boot.img。
   • 虚拟机挂载镜像，启动后执行引导程序，显示“Hello, OS world!”。

六、虚拟机

1. 虚拟机定义
   由操作系统或专用软件实现的“虚拟计算机”，通过虚拟化技术抽象硬件资源，为用户提供独立、隔离的运行环境。
2. 虚拟化核心
   依托操作系统的虚拟技术，对处理器、内存、I/O 设备等硬件进行抽象，屏蔽底层物理硬件差异，实现多系统、多环境的并行运行。
3. 作用
   支持在单一物理机上运行多个不同操作系统（如 Windows 虚拟机中运行 Linux），兼顾资源利用率与环境隔离性，常用于开发测试、系统兼容等场景。

2 进程与线程

一、进程与线程

1. 基本概念

• 进程（Process）：是程序在计算机中的一次执行过程，是系统进行资源分配和调度的基本单位，由程序、数据和进程控制块（PCB）三部分组成。
• 线程（Thread）：是进程内的一个相对独立的可调度执行单元，是 CPU 调度和分派的基本单位，仅拥有线程 ID、程序计数器、寄存器集合和堆栈等必要资源，共享所属进程的全部资源。
• 进程与线程的区别
  • 资源分配：进程是资源分配基本单位，线程不独立分配资源。
  • 调度：线程是调度基本单位，进程调度开销高于线程。
  • 地址空间：进程有独立地址空间，同一进程内线程共享地址空间。
  • 开销：线程创建、切换和终止开销远小于进程。

2. 进程/线程的状态与转换

• 进程的基本状态
  • 就绪态（Ready）：具备运行条件，等待 CPU 调度。
  • 运行态（Running）：占用 CPU 并执行指令。
  • 阻塞态（Blocked）：因等待某事件（如 I/O）暂停运行。
  • 新建态（New）：进程刚创建，尚未调入主存。
  • 终止态（Terminated）：进程完成或被撤销。
• 线程的基本状态：与进程类似，包括就绪态、运行态、阻塞态，部分系统还包含初始化态、备用态、转换态等。
• 状态转换
  • 就绪态 → 运行态：进程调度分配 CPU。
  • 运行态 → 就绪态：时间片用完或被高优先级进程抢占。
  • 运行态 → 阻塞态：进程请求 I/O 或等待资源。
  • 阻塞态 → 就绪态：等待的事件发生。

3. 线程的实现

• 内核支持的线程（Kernel-level Threads）：由操作系统内核直接管理，内核为每个线程维护 PCB，线程切换需内核参与，支持多处理器并行，一个线程阻塞不影响其他线程。
• 线程库支持的线程（User-level Threads）：由用户空间的线程库管理，内核不感知线程存在，线程切换无需内核参与，开销小，但一个线程阻塞会导致整个进程阻塞，无法利用多处理器。
• 混合实现（多对多模型）：多个用户级线程映射到少量内核级线程，兼顾低开销和并行性。

4. 进程与线程的组织与控制

• 进程控制块（PCB）：存储进程描述信息（PID、UID）、控制和管理信息（状态、优先级）、资源分配清单（代码段指针、文件描述符）、处理器相关信息（寄存器值、程序计数器）。
• 线程控制块（TCB）：存储线程 ID、程序计数器、寄存器集合、堆栈指针等线程上下文信息。
• 控制操作
  • 创建：进程通过 fork() 创建，线程通过 pthread_create() 创建。
  • 终止：进程通过 exit() 终止，线程通过 pthread_exit() 终止。
  • 阻塞与唤醒：进程/线程因等待事件主动阻塞，事件完成后被唤醒。
  • 切换：进程切换需保存和恢复 PCB 及内存管理数据，线程切换仅需保存和恢复 TCB。

5. 进程间通信（IPC）

• 共享内存（Shared Memory）：进程直接访问共享内存区域，通信速度最快，需同步机制保证互斥访问，Linux 下通过 shmget()、shmat() 等系统调用实现。
• 消息传递（Message Passing）：进程通过发送和接收消息交换数据，分为直接通信（消息缓冲队列）和间接通信（信箱），无需共享内存，适合分布式系统。
• 管道（Pipe）：分为普通管道（半双工，仅父子进程使用）和命名管道（FIFO，任意进程使用），基于文件系统实现，遵循先进先出规则。
• 信号（Signal）：内核向进程发送的事件通知，用于处理异步事件，如 SIGINT（Ctrl + C 终止进程）、SIGCHLD（子进程终止），进程可忽略、终止或执行自定义处理函数。

二、CPU 调度与上下文切换

1. 调度的基本概念

• 定义：操作系统按一定策略从就绪队列选择进程/线程，分配 CPU 使用权的过程。
• 调度器（Scheduler）：实现调度功能的内核程序，分为长程调度（作业调度）、中程调度（内存调度）和短程调度（CPU 调度）。
• 闲逛进程（Idle Process）：当无就绪进程时运行的进程，占用空闲 CPU 时间。

2. 调度的目标

• 提高 CPU 利用率：使 CPU 尽可能处于忙碌状态。
• 提升吞吐量：单位时间内完成的进程数最大化。
• 缩短周转时间：进程从提交到完成的总时间最短。
• 减少等待时间：进程在就绪队列中的等待时间最短。
• 降低响应时间：交互式系统中，从用户输入到系统响应的时间最短。
• 保证公平性：所有进程得到公平的 CPU 分配。

3. 调度的实现

• 调度时机：进程终止、时间片用完、进程阻塞、高优先级进程到达、系统调用返回。
• 调度方式
  • 非抢占式调度：进程主动让出 CPU（完成任务或阻塞），调度器才重新分配 CPU，开销小，适合批处理系统。
  • 抢占式调度：操作系统强行暂停运行中的进程，将 CPU 分配给其他进程，响应时间短，适合交互式系统。
• 调度层次
  • 内核级线程调度：内核直接调度线程，支持抢占和并行。
  • 用户级线程调度：线程库调度，内核仅调度进程，不感知线程，无法抢占。

4. CPU调度算法

• 先到先服务（FCFS）：按进程到达顺序调度，简单公平，适合长进程。
• 最短作业优先（SJF）：选择 CPU 区间最短的进程先执行，平均周转时间短，需预知 CPU 区间长度，可能导致长进程“饥饿”。
• 最短剩余作业优先（SRJF）：SJF 的抢占式版本，选择剩余 CPU 区间最短的进程，性能更优，但同样依赖 CPU 区间预测。
• 优先级调度（Priority Scheduling）：按进程优先级调度，优先级高的先执行，可动态调整优先级（老化技术）避免“饥饿”。
• 轮询调度（RR）：按时间片轮转分配 CPU，每个进程执行一个时间片后切换，响应时间短，上下文切换开销大，时间片通常设为 10-100 ms。
• 多级反馈队列（MLFQ）：多个优先级队列，进程按 CPU 使用情况在队列间移动，高优先级队列时间片短，兼顾短进程和长进程。
• 彩票算法（Lottery Scheduling）：进程拥有彩票数比例决定 CPU 占用率，随机选择中奖进程，保证公平性和比例控制。

5. 多处理机调度

• 对称多处理（SMP）：所有 CPU 地位平等，共享内存和资源，调度器可将进程分配到任意 CPU。
• 非对称多处理（AMP）：CPU 分为主 CPU 和从 CPU，主 CPU 负责调度和管理，从 CPU 执行进程。
• 调度策略：负载均衡（进程均匀分配到各 CPU）、亲和性调度（进程优先在同一 CPU 执行，减少缓存失效）。

6. 上下文及其切换机制

• 上下文（Context）：进程/线程运行的环境，包括寄存器值、程序计数器、堆栈指针、内存映射等。
• 上下文切换：暂停当前进程/线程，保存其上下文，加载待运行进程/线程的上下文并执行的过程。
• 切换步骤
  1. 保存当前进程的寄存器和程序计数器。
  2. 更新 PCB 信息，将当前进程移入相应队列（就绪/阻塞）。
  3. 选择下一个运行进程，更新其 PCB。
  4. 恢复下一个进程的上下文，更新内存管理数据。
  5. 切换 CPU 执行权限，开始执行新进程。
• 切换开销：直接开销（保存/恢复上下文的 CPU 时间）和间接开销（缓存失效、TLB 失效）。

三、同步与互斥

1. 基本概念

• 互斥（Mutual Exclusion）：多个进程/线程不能同时访问临界资源，需排他性使用，如打印机、共享变量。
• 同步（Synchronization）：多个进程/线程按预定顺序执行，协调彼此的操作，如生产者-消费者问题中生产和消费的顺序。
• 临界区（Critical Section）：进程/线程中访问临界资源的代码段，需保证互斥进入。

2. 基本实现方法

• 软件方法：通过算法实现互斥，如 Peterson 算法、Dekker 算法，无需硬件支持，但效率低。
• 硬件方法：利用硬件指令（如 Test-and-Set、Swap）实现互斥，简单高效，但需硬件支持。

3. 同步互斥工具

• 锁（Lock）：分为互斥锁（Mutex）和读写锁（Read-Write Lock），提供 lock() 和 unlock() 操作，保证临界区互斥访问。
• 信号量（Semaphore）：由 Dijkstra 提出，是具有非负整数值的全局变量，通过 P、V 操作实现同步互斥。
  • P 操作（wait）：若信号量值 > 0 则减 1，否则阻塞。
  • V 操作（signal）：信号量值加 1，若有阻塞进程则唤醒。
  • 分类：二元信号量（0 或 1，用于互斥）、计数信号量（用于资源计数）。
• 条件变量（Condition Variable）：与锁配合使用，用于线程间等待特定条件，提供 wait() 和 signal() 操作，wait() 释放锁并阻塞，signal() 唤醒阻塞线程。

4. 经典同步问题

• 生产者-消费者问题：生产者向缓冲区生产数据，消费者从缓冲区消费数据，需保证缓冲区满时生产者阻塞，缓冲区空时消费者阻塞。
  • 解决方案：使用互斥锁保证缓冲区互斥访问，计数信号量 empty（空闲槽位）和 full（已用槽位）实现同步。
• 读者-写者问题：多个读者可同时读共享数据，写者需互斥写，分为读者优先和写者优先。
  • 读者优先：读者无需等待（除非有写者），可能导致写者“饥饿”。
  • 写者优先：写者到达后优先写，读者需等待写者完成。
• 哲学家进餐问题：五个哲学家交替思考和进餐，需拿左右两支筷子，易产生死锁。
  • 解决方案：最多允许四位哲学家同时拿左筷子、按奇偶顺序拿筷子、仅当左右筷子都可用时才拿。

四、死锁

1. 基本概念

• 死锁（Deadlock）：多个进程/线程因循环等待资源而无法继续执行的状态，如进程 A 持有资源 1 等待资源 2，进程 B 持有资源 2 等待资源 1。
• 死锁的四个必要条件
  1. 互斥条件：资源只能被一个进程独占。
  2. 不可抢占条件：资源只能由持有进程自愿释放，不能强行抢占。
  3. 持有和等待条件：进程持有部分资源，同时等待其他资源。
  4. 循环等待条件：多个进程形成资源等待循环链。

2. 死锁预防

• 破坏互斥条件：资源改为共享访问（如只读文件），但部分资源无法实现。
• 破坏不可抢占条件：允许抢占持有资源的进程（如 CPU、内存）。
• 破坏持有和等待条件：进程执行前一次性申请所有资源，或释放已持有资源再申请新资源。
• 破坏循环等待条件：对资源按序编号，进程需按编号顺序申请资源。

3. 死锁避免

• 安全状态：存在一个进程执行序列，使所有进程都能完成，系统处于安全状态则无死锁。
• 银行家算法：Dijkstra 提出，通过检查资源请求是否导致系统进入不安全状态来避免死锁。
  • 核心思想：进程申请资源时，先试探分配，若分配后系统安全则允许，否则拒绝。
  • 关键数据结构：可用资源向量（Available）、已分配矩阵（Allocation）、需求矩阵（Need）。

NOTE

初始化数据：

• 可利用资源向量 Available：含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目。
• 最大需求矩阵 Max：n × m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。
• 分配矩阵 Allocation：n × m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
• 需求矩阵 Need：n × m 的矩阵，用以表示每一个进程尚需的各类资源数，Need = Max - Allocation。

安全性检查算法过程如下：

1. 初始化设定
   • Work = Available
   • Finish[i] = false, 对所有进程 i
2. 查找这样的进程 Pi，使得 Finish[i] = false 且 Need[i] ≤ Work，如果没有这样的进程则转到步骤 4
3. 若有这样的进程 Pi，则 Pi 一定可以完成，归还其占用的资源并转到步骤 2
   • Work = Work + Allocation[i]
   • Finish[i] = true
4. 若所有进程 Pi 都是能完成的，即 Finish[i] = true，则系统处于安全状态；否则系统处于不安全状态。

资源请求算法过程如下：

1. 进程 Pi 发出资源请求 Request[i]，如果 Request[i] ≤ Need[i]，则转到步骤 2，否则出错
2. 如果 Request[i] ≤ Available[i]，则转到步骤 3，否则 Pi 进入等待状态
3. 系统试探分配资源，修改相关数据：
   • Available[i] -= Request[i]
   • Allocation[i] += Request[i]
   • Need[i] -= Request[i]
4. 调用安全性检查算法，若系统处于安全状态，则分配资源给 Pi；否则，Pi 进入等待状态，试探性分配作废。

4. 死锁检测和解除

• 死锁检测：通过资源分配图或银行家算法变种检测死锁，定期检测或资源利用率低时检测。
  • 资源分配图：存在循环且每个资源只有一个实例时，一定死锁；多个实例时需进一步分析。
• 死锁解除
  • 终止进程：终止所有死锁进程或逐个终止代价最小的进程，直到死锁解除。
  • 剥夺资源：从死锁进程中抢占资源，分配给其他死锁进程，需回滚进程到安全状态。