操作系统期末复习知识点

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 完成），异常用于处理程序运行错误（如除零、缺页），处理流程需完成上下文保存、中断/异常处理、上下文恢复。

   NOTE

   由硬件完成：

   • 中断请求与屏蔽检查
   • 保护断点与现场状态：将程序计数器（PC）和程序状态字（PSW）压入栈
   • 切换处理器模式
   • 寻找中断入口

   由操作系统完成：

   • 保存剩余现场：保存其他的通用寄存器
   • 具体中断处理逻辑
   • 恢复现场
   • 发送中断结束信号
   • 中断返回：由硬件自动恢复 PC 和 PSW 并切回用户态

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、程序计数器、寄存器集合和堆栈等必要资源，共享所属进程的全部资源。
• 进程与线程的区别
  • 资源分配：进程是资源分配基本单位，线程不独立分配资源。
  • 调度：线程是调度基本单位，进程调度开销高于线程。
  • 地址空间：进程有独立地址空间，同一进程内线程共享地址空间。
  • 开销：线程创建、切换和终止开销远小于进程。

NOTE

线程共享的资源：同一进程中的所有线程共享该进程获得的系统资源

• 内存空间：
  • 代码段
  • 数据段
  • 堆
• 操作系统资源：
  • 打开的文件描述符
  • 信号处理
  • 进程 ID
  • 环境变量与工作目录

线程独享的资源：每个线程为了能独立运行，必须拥有一些不被其他线程干扰的数据

• 线程 ID
• 程序计数器（PC）
• 寄存器集合
• 栈
• 状态信息

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 区间长度，可能导致长进程“饥饿”。
• 高响应比优先（HRRN）：根据响应比 = （等待时间 + 服务时间）/ 服务时间调度，兼顾短作业和长作业，减少“饥饿”。
• 最短剩余作业优先（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）：多个进程/线程按预定顺序执行，协调彼此的操作，如生产者-消费者问题中生产和消费的顺序。
  • 空闲让进：当临界资源处于空闲状态时，应允许一个请求进入临界区的进程立即进入；
  • 忙则等待：当临界资源正被占用时，其他试图进入临界区的进程必须等待；
  • 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入临界区；
  • 让权等待：当进程不能进入临界区时，应立即释放处理器（CPU），防止进程进入“忙等”状态。
• 临界区（Critical Section）：进程/线程中访问临界资源的代码段，需保证互斥进入。

2. 基本实现方法

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

TIP

Peterson 算法的实现：
假设有两个进程 P0 和 P1，使用全局共享变量

int turn;          // 表示现在轮到哪个进程进入临界区
int flag[2];       // flag[0]和flag[1]分别表示P0和P1是否准备好进入临界区

进程 Pi 的逻辑实现：

// 这里的 i 是当前进程编号 (0 或 1)，j 是对方编号 (1 或 0)
void enter_critical_section(int i) {
    int j = 1 - i;

    flag[i] = 1;           // 1. 我想进临界区
    turn = j;              // 2. 先把机会让给对方 (谦让)

    // 3. 等待条件：如果对方想进，并且轮到对方，则我忙等待
    while (flag[j] == 1 && turn == j) {
        // 忙等待 (busy waiting)
    }

    // ------- 临界区 (Critical Section) -------
    // 执行与共享资源相关的代码
    // ---------------------------------------

    flag[i] = 0;           // 4. 退出临界区，表示我不想进了
}

Swap 指令的实现：

// 全局共享变量
bool lock = false; 

// 线程尝试进入临界区
void enter_region() {
    bool key = true;
    while (key == true) {
        // 原子地交换 key 和 lock
        // 如果 lock 是 false，交换后 key 变为 false，循环结束
        // 如果 lock 是 true，交换后 key 保持为 true，继续循环（自旋）
        swap(&lock, &key);
    }
}

// 线程离开临界区
void leave_region() {
    lock = false; // 释放锁
}

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. 死锁检测和解除

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

3 内存管理

一、内存管理基础

1. 核心概念

• 逻辑地址（Logical Address）：用户编程时使用的地址，由段内偏移或页内偏移等组成，是虚拟地址的组成部分。
• 物理地址（Physical Address）：实际物理内存中存储单元的编号，是 CPU 可直接访问的地址。
• 地址变换（Address Translation）：通过硬件（MMU）或软件将逻辑地址转换为物理地址的过程，核心公式为 MAP: V → P ∪ {∅}（V 为虚拟地址空间，P 为物理地址空间）。
• 内存共享（Memory Sharing）：多个进程共用物理内存中的同一数据块（如共享库），通过页表项标记共享属性实现。
• 内存保护（Memory Protection）：通过页表项或段表项中的权限位（R/W/X）限制进程对内存的访问，防止越权操作。
• 内存分配与回收（Memory Allocation and Recycling）：操作系统为进程分配内存空间，并在进程结束后回收空间的过程。

2. 连续分配管理方式

• 固定分区（Fixed Partition）
  • 等长分区：将内存等分为若干大小相同的分区，分配算法简单但利用率低。
  • 变长分区：将内存划分为大小不同的分区，分配时选择满足需求的最小分区，减少浪费。
• 可变分区（Variable Partition）
  • 动态分割内存，根据进程需求分配恰好大小的空间，通过空闲分区表管理空间。
  • 存在碎片问题：外部碎片（内存中分散的不可用小空间）可通过内存紧缩解决，内部碎片（分区内未使用的空间）存在于固定分区中。

3. 页式管理（Paging）

• 核心思想：将逻辑地址空间和物理地址空间均划分为大小相等的页（Page）和页框（Frame），以页为单位分配内存。
• 地址结构
  • 虚拟地址（VA）：VPN（虚拟页号） + VPO（虚拟页偏移量），其中 VPO = PPO（物理页偏移量）。
  • 物理地址（PA）：PPN（物理页号） + PPO。
• 页表（Page Table）：存储虚拟页号到物理页号的映射，每个页表项（PTE）包含有效位、页框号、保护位等，Intel x86 结构的 PTE 还包含访问位（A）、修改位（D）等。
• 多级页表（Multi-level Page Table）：将页表进一步分级（如二级、三级），减少页表占用的连续内存空间，32 位系统典型结构为 页目录号 + 页号 + 偏移量。

4. 段式管理（Segmentation）

• 核心思想：按程序逻辑意义（代码段、数据段、栈段等）划分段，每个段独立编址，符合用户编程习惯。
• 地址结构：段号（Seg#） + 段内偏移（Offset），通过段表记录每个段的基址、长度和保护权限。
• 地址变换：先通过段号查找段表，验证偏移量是否超出段长度，再计算物理地址 物理地址 = 段基址 + 段内偏移。
• 优缺点：优点是支持分段保护和共享，符合用户直觉；缺点是存在外部碎片，内存利用率较低。

5. 段页式管理（Segmented-Paging）

• 核心思想：结合段式和页式的优点，先按逻辑分段，再将每个段划分为页，以页为单位分配内存。
• 地址变换流程：逻辑地址 → 段表查找（得到段的线性地址起始）→ 页表查找（得到物理页号）→ 物理地址 物理地址 = PPN << 页大小 + 偏移量。
• 优势：既满足用户对分段的需求，又解决了段式管理的碎片问题，是现代操作系统的常用方式。

二、虚拟内存管理

1. 虚拟内存基本概念

• 定义：进程认为拥有连续的大地址空间（如 32 位系统为 4GB），实际物理内存可能分散或部分存储在磁盘上，通过按需调页和页面置换实现。
• 核心技术：段页管理、部分加载、按需调页（Demand Paging）、换入换出（Swap In/Out）。
• 优点：地址空间可大于物理内存，简化编程；内存利用率高，支持更多进程并发。

2. 请求页式管理（Demand Paging）

• 页表改造：在页表项中增加有效位（Valid/Invalid Bit），标记页面是否在物理内存中。
• 缺页中断（Page Fault）：当访问的页面不在内存（有效位为 0）时，MMU 触发中断，由中断处理程序将页面从磁盘调入内存。
• 调页过程：1. 触发缺页中断；2. 选择空闲页框（无则置换）；3. 从磁盘调入页面；4. 更新页表项；5. 重新执行指令。

3. 页框分配与回收

• 分配策略
  • 固定分配（Fixed-Allocation）：为进程分配固定数量的页框，按平均分配、比例分配或优先级分配。
  • 可变分配（Variable-Allocation）：根据进程缺页率动态调整页框数量，缺页率高则增加页框。
• 回收策略：进程结束时，回收其占用的所有页框；页面置换时，回收被淘汰页面的页框。

4. 页置换算法（Page Replacement Algorithms）

• FIFO（先进先出）：淘汰最早调入的页面，实现简单但可能出现 Belady 异常（分配页框增多时缺页率反而上升）。
• OPT（最优置换）：淘汰未来最长时间不使用的页面，缺页率最低但无法实现（需预知未来访问序列）。
• LRU（最近最少使用）：淘汰最近最长时间没有使用过的页面，是 OPT 的近似实现，准确实现方式包括：
  • 计数器法：为每页维护时间戳，选择时间戳最小的页面。
  • 页码栈法：将访问过的页号压入栈顶，淘汰栈底页面。
• 近似 LRU
  • 附加引用位法：通过多次扫描引用位判断页面使用频率。
  • 时钟法（Clock Algorithm）：将页面组织为循环队列，通过访问位（A）和修改位（M）选择淘汰页面，分为简单时钟法和改进型时钟法。
    • 简单 Clock 置换算法：如存在页命中，访问位置 1，查询指针保持不动；否则，循环检查各页面的使用情况：若访问位为 0，选择该页淘汰，查询指针前进一步；若访问位为 1，复位访问位为 0，查询指针前进一步。
    • 改进型 Clock 置换算法：
      • 页面的四种状态：
        1. A = 0, M = 0：最近未被访问且未被修改；
        2. A = 0, M = 1：最近未被访问但已被修改；
        3. A = 1, M = 0：最近被访问但未被修改；
        4. A = 1, M = 1：最近被访问且已被修改。
      • 三轮扫描：
        1. 第一轮：查找 A=0, M=0 的页面替换，否则进入下一轮；
        2. 第二轮：查找 A=0, M=1 的页面替换，并把遍历过的页面的 A 位复位为 0，否则进入下一轮；
        3. 第三轮：复位所有页面的 A 位为 0，重复第一轮。

5. 内存映射文件（Memory-Mapped Files）

• 定义：将磁盘文件映射到进程的虚拟地址空间，进程可通过内存访问直接操作文件，无需 I/O 系统调用。
• 分类
  • 共享映射：多个进程共享同一文件映射，修改对所有进程可见。
  • 私有映射（写时复制，Copy-on-Write）：进程修改映射页面时，系统创建页面副本，原页面保持不变。
• 应用：加载可执行文件（.text/.data 段）、共享库、大文件操作等。

6. 虚拟内存性能的影响因素及改进方式

• 影响因素
  • 页大小：页越大，缺页率越低，但内部碎片越大；典型页大小为 4KB。
  • 页置换算法：LRU 及近似算法性能优于 FIFO。
  • 工作集（Working Set）：进程最近访问的页面集合，分配的页框数需覆盖工作集，否则会出现颠簸。
  • 颠簸（Thrashing）：进程频繁缺页导致 CPU 利用率急剧下降，因工作集未被完全覆盖。
• 改进方式
  • 优化页置换算法：采用改进型时钟法平衡性能与开销。
  • 动态调整工作集：根据缺页率调整进程页框数，缺页率高于上限则增加页框。
  • 减少缺页次数：程序优化（数据紧凑存放、局部性编程），增大内存容量。

三、关键公式与参数

• 地址空间大小：虚拟地址空间 N = 2ⁿ（n 为虚拟地址位数），物理地址空间 M = 2ᵐ（m 为物理地址位数）。
• 页大小：P = 2ᵖ（p 为页偏移量位数）。
• 有效访问时间（EAT）：EAT = HitR × (TLB + MA) + (1 - HitR) × (TLB + 2×MA)，其中 HitR 为 TLB 命中率，TLB 为 TLB 访问时间，MA 为内存访问时间。
• 缺页率（Page Fault Frequency, PFF）：PFF = 缺页次数 / 指令执行条数。

4 文件管理

一、文件（File）

1. 基本概念

• 文件定义：命名的磁盘字节序列（named bytes on disk），是用户存储信息的基本单位。
• 核心映射：文件系统（FS）负责将文件名和偏移量转换为磁盘块地址（文件名 + 偏移 → 磁盘块地址）。
• 核心目标：减少磁盘访问次数（minimize disk accesses），降低空间开销（minimal space overhead）。

2. 文件元数据和索引节点（inode）

• 元数据（Metadata）：描述文件属性的信息，包括文件名、权限、大小、创建/修改/访问时间、数据块位置等，存储在文件控制块（FCB）或索引节点（inode）中。
• 索引节点（inode）：
  • 作用：唯一标识一个文件，存储文件元数据和数据块指针。
  • 特点：固定大小（如 Ext2 中为 128 B），集中存储在索引节点数组（inode table）中。
  • 关键字段：文件类型及权限（i_mode）、所有者 ID（i_uid）、组 ID（i_gid）、文件大小（i_size）、数据块指针数组（i_block）、链接数（i_links_count）等。

3. 文件的操作

1. 建立（Create）：创建新文件，分配 inode 和必要的数据块，初始化元数据。
2. 删除（Delete）：释放文件占用的数据块和 inode，删除对应的目录项。
3. 打开（Open）：将文件 inode 加载到内存，建立进程与文件的关联（文件描述符）。
4. 关闭（Close）：断开进程与文件的关联，刷新文件缓存到磁盘。
5. 读（Read）：根据文件偏移量，通过 inode 找到对应磁盘块，将数据读入内存。
6. 写（Write）：将内存数据写入磁盘块，更新 inode 中的文件大小和修改时间。

4. 文件的保护

• 权限类型：读（r）、写（w）、执行（x）。
• 权限主体：所有者（owner）、组用户（group）、其他用户（other）。
• 权限存储：文件元数据（inode 或 FCB）中。
• 权限校验：进程访问文件时，通过进程 PCB 中的 uid/gid 与文件权限匹配校验。

5. 文件的逻辑结构

• 定义：用户对文件信息的逻辑组织形式，提供清晰、易用的访问接口。
• 常见形式：字符流（无结构文件）、记录式文件（有结构文件）。

6. 文件的物理结构

文件数据在磁盘上的存储方式，决定文件的存取效率和扩展性：

1. 连续存储（Contiguous Allocation）
   • 特点：文件数据块连续分配，FCB 记录起始块号和块数。
   • 优点：存取速度快（支持随机访问）、实现简单。
   • 缺点：产生外部碎片、文件扩充困难。
2. 链式存储（Linked Allocation）
   • 特点：文件数据块通过指针链接，FCB 记录起始块号，每个数据块存储下一块指针。
   • 优点：无外部碎片、易于扩充。
   • 缺点：仅支持顺序访问、效率低（查找需遍历链表）。
3. 索引存储（Indexed Allocation）
   • 特点：通过索引块记录所有数据块地址，FCB 记录索引块地址。
   • 优点：支持随机访问、无外部碎片，是连续和链式分配的折衷。
   • 缺点：索引块占用额外空间。
   • 扩展形式：多级索引（一级、二级、三级），如 UNIX 系统采用“12 个直接索引 + 1 个一级间接 + 1 个二级间接 + 1 个三级间接”。

二、目录（Directory）

1. 基本概念

• 定义：管理文件集合的特殊文件，存储目录项（< 文件名，inode 指针 >）。
• 核心作用：实现文件的按名查找，解决文件重名和分类管理问题。

2. 树形目录（Tree - Structured Directory）

• 结构：以根目录（/）为起点，目录可包含子目录和文件，形成 k 叉树。
• 优点：扩展性好、结构清晰、支持文件隔离（不同目录下文件名可重复）。
• 路径解析（Name Resolution）：通过绝对路径（如 /my/data/a）或相对路径，从根目录（或当前目录）逐层查找目录项，最终获取目标文件的 inode。
  • 示例：解析 /my/data/a 时，依次查找根目录 → my 目录 → data 目录 → a 文件的 inode。

3. 目录的操作

• 创建（Mkdir）：创建新目录，分配 inode 和数据块，初始化目录项（包含 . 和 .. 项）。
• 删除（Rmdir）：删除空目录（仅含 . 和 .. 项），释放对应的 inode 和数据块。
• 查找（Lookup）：根据文件名查找目录项，返回对应的 inode 指针。
• 列出（Ls）：遍历目录数据块，列出所有目录项中的文件名和属性。

4. 硬链接和软链接（Hard Link & Soft Link）

1. 硬链接
   • 定义：多个文件名指向同一个 inode，通过增加 inode 的链接数（i_links_count）实现。
   • 特点：删除一个文件名不影响其他链接（链接数减 1，直至为 0 时释放 inode）；不能跨文件系统。
2. 软链接（符号链接，Symbolic Link）
   • 定义：创建一个新文件（独立 inode），内容为目标文件的路径。
   • 特点：目标文件删除后，链接失效；支持跨文件系统；链接数不影响目标文件的 inode。

三、文件系统（File System）

1. 文件系统的全局结构（Layout）

（一）外存中的结构（磁盘布局）

• 分区（Partition）：磁盘被划分为多个分区，每个分区独立使用一种文件系统。

• 典型分区结构（以 UNIX 为例）：

  引导块（Boot Block）	超级块（Super Block）	索引节点数组（inode Array）	数据块（Data Blocks）
  存储引导 OS 信息（无 OS 则为空）	记录文件系统全局信息	集中存储所有文件的 inode	存储文件数据和目录数据

• Ext2 文件系统的块组（Block Group）结构：
  每个块组包含：超级块备份、组描述符表（GDT）、数据块位图、索引结点位图、索引节点表、数据区。

  • 超级块：描述文件系统信息（块大小、总块数、空闲块数、inode 总数等），多块组备份以提高容错性。
  • 位图：数据块位图标记空闲数据块，索引结点位图标记空闲 inode。

（二）内存中的结构

• 超级块缓存：将磁盘上的超级块加载到内存，避免频繁磁盘访问。
• inode 缓存：缓存最近访问的 inode，加速文件访问。
• 目录缓存：缓存常用目录的目录项，优化路径解析效率。
• 磁盘缓存（Disk Cache）：内存中划分的高速缓冲区，缓存磁盘块数据，利用局部性原理减少磁盘 I/O。

2. 外存空闲空间管理办法

1. 空闲位图（位向量，Free Bitmap）
   • 原理：每一位对应一个磁盘块，0 表示空闲，1 表示占用。
   • 优点：快速分配连续块组，查找空闲块高效。
   • 缺点：位向量占用空间大（如 1GB 磁盘，块大小 1KB 时，位向量大小为 128KB）。
2. 空闲链表（Free List）
   • 原理：将空闲块通过指针链接，超级块记录链表头。
   • 优点：分配单个/少量空闲块高效，无额外空间开销。
   • 缺点：分配连续多块时需遍历链表，效率低。

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

• 定义：操作系统提供的抽象层，屏蔽不同文件系统（如 Ext4、FAT32、NTFS）的实现差异。
• 核心作用：为用户和应用程序提供统一的文件操作接口（如 open、read、write），实现“一次调用，适配所有文件系统”。
• 架构：用户空间 → VFS 接口 → 具体文件系统实现（Ext4/FAT32/NTFS）→ 设备驱动 → 硬件（硬盘/U盘）。

4. 文件系统挂载（Mounting）

• 定义：将一个文件系统（如 U 盘的 FAT32）关联到根文件系统的某个目录（挂载点，Mount Point），使得该文件系统可通过该目录访问。
• 挂载过程：
  1. 检测存储设备（如插入 U 盘）。
  2. 读取设备上的超级块，验证文件系统格式。
  3. 将文件系统的根目录与挂载点目录建立关联。
• 卸载（Umount）：断开文件系统与挂载点的关联，确保缓存数据同步到磁盘后释放资源。

5. 典型文件系统实现

（一）Ext2（Extended File System 2）

• 索引节点（inode）：12 个直接索引 + 1 个一级间接 + 1 个二级间接 + 1 个三级间接。
  • 块大小为 4KB 时，单个文件最大大小计算： 直接索引：12 × 4KB = 48KB 一级间接：(4KB / 4B) × 4KB = 4MB 二级间接：(4KB / 4B)² × 4KB = 4GB 三级间接：(4KB / 4B)³ × 4KB = 4TB 最大文件大小 = 48KB + 4MB + 4GB + 4TB
• 目录项：ext2_dir_entry_2 结构，包含 inode 号、目录项长度、文件名、文件类型。

（二）FAT（File Allocation Table）

• 核心结构：引导区、FAT1（文件分配表）、FAT2（FAT1 备份）、根目录区、数据区。
• 簇（Cluster）：文件系统的最小分配单位，由多个扇区组成（如 4KB 簇 = 8 个 512B 扇区）。
• FAT 表：记录簇的分配状态和链接关系，表项值含义：
  • 0x0000：空闲簇
  • 0x0002 - 0xFFEF：下一个簇号
  • 0xFFFF：文件结束簇
• 特点：实现简单，兼容性好；但不支持多级索引，大文件易产生碎片。

6. 文件系统优化与容错

1. 磁盘缓存：延迟写（Delayed Write）、LRU 替换策略，减少磁盘 I/O 次数。
2. 碎片整理：合并分散的空闲块和文件数据块，提升连续访问效率。
3. 容错机制：
   • 超级块备份（Ext2）、FAT 镜像（FAT1/FAT2）。
   • RAID 技术：通过磁盘冗余实现数据恢复（如 RAID1 镜像、RAID5 奇偶校验）。
   • 日志文件系统（Journaling FS）：写数据前记录日志，崩溃后通过日志恢复一致性（如 Ext3/Ext4 的 Journal 功能）。

5 输入/输出管理

一、输入/输出（I/O）管理基础

1. 设备相关概念

1. 基本概念
   • 设备是计算机系统中与外部进行数据交换的硬件部件，核心要素包括端口（I/O 地址集）、总线（传输线+协议）、设备控制器（操作硬件的电子器件）。
   • 操作系统通过设备驱动程序实现外设支持，OS 制定标准接口，制造商开发具体操纵程序，是 OS 关键生态之一。
2. 设备分类
   • 按数据传输单位：字符设备（Character Device，如鼠标、键盘、打印机）、块设备（Block Device，如磁盘、SSD）。
   • 其他分类：独占设备（如打印机）、共享设备（如磁盘）；高速设备（如 SSD）、低速设备（如键盘）。
3. I/O 接口
   • 是 CPU、内存与外设之间的连接部件，功能包括地址译码、数据缓冲、信号转换、中断控制。
   • 示例：USB 接口、SATA 接口、PCI-E 接口等。

2. I/O 控制方式

1. 轮询方式（Programmed I/O，PIO）
   • 原理：CPU 主动循环查询设备状态，直到设备就绪后进行数据传输。
   • 流程：发送命令 → 读取状态 → 检查就绪 → 传输数据 → 出错处理。
   • 代码示例：in AL, 0x??; while(AL!=ready) { in AL, 0x??; }
   • 特点：简单易实现，但 CPU 利用率极低（CPU 速度远快于外设），浪费资源。
2. 中断方式（Interrupt-driven I/O）
   • 原理：CPU 发送命令后执行其他任务，设备就绪后向 CPU 发中断信号，CPU 暂停当前任务处理 I/O。
   • 流程：进程发 I/O 请求 → CPU 启动设备 → 进程阻塞 → 设备完成发中断 → 中断处理程序唤醒进程 → 传输数据。
   • 核心机制：通过 set_trap_gate 设置中断处理函数，响应设备中断。
   • 特点：CPU 与 I/O 并行工作，利用率高，是多数 I/O 设备的默认方式。
3. DMA方式（Direct Memory Access）
   • 原理：引入 DMA 控制器，直接实现内存与外设的数据传输，无需 CPU 全程参与。
   • 流程：CPU 初始化 DMA（内存地址、传输字节数、控制字）→ 进程阻塞 → DMA 控制传输 → 完成发中断 → 唤醒进程。
   • 特点：单次传输粒度大（批量数据），解放 CPU，适用于磁盘、显卡等高速设备。
   • 与中断方式区别：中断方式需 CPU 处理每个字节传输，DMA 仅需 CPU 初始化和中断响应。

3. I/O 软件层次结构

4. 输入/输出应用程序接口

1. 字符设备接口
   • 按字符流传输数据，无缓冲区（或简单缓冲区），接口函数：open()、close()、read()、write()、ioctl()。
   • 示例：键盘（/dev/keyboard）、打印机（/dev/lp0）。
2. 块设备接口
   • 按固定大小块（如 512 B、4 KB）传输数据，支持随机访问，接口函数包含块寻址相关操作。
   • 示例：磁盘（/dev/sda1）、SSD（/dev/nvme0n1）。
3. 网络设备接口
   • 基于数据包传输，接口函数：socket()、bind()、send()、recv()，支持 TCP/UDP 协议。
   • 示例：网卡（/dev/eth0）。
4. 阻塞/非阻塞 I/O
   • 阻塞 I/O：进程发起 I/O 后等待设备就绪，期间不占用 CPU。
   • 非阻塞 I/O：进程发起 I/O 后立即返回，通过轮询或事件通知获取结果，适用于高并发场景。

二、设备独立软件

1. 缓冲区管理

1. 缓冲目的
   解决 CPU 与外设速度不匹配问题，提高并行性，减少中断频率。

2. 缓冲分类

   • 硬件缓冲：外设自带寄存器（如打印机缓冲区、CD-ROM 缓冲区）。
   • 软件缓冲：内存中开辟的缓冲区，由 OS 管理。

3. 软件缓冲实现方式

   类型	英文名称	原理	特点
   单缓冲	Single Buffer	内存中 1 个固定大小缓冲区，串行读写	简单，并行性差
   双缓冲	Double Buffer	2 个缓冲区交替使用，CPU 与外设并行操作	并行性提升，适用于高速设备
   环形缓冲	Circular Buffer	多个缓冲区组成环形链表，Head/Full/Empty 指针管理	高效利用缓冲区，适用于流式数据
   缓冲池	Buffer Pool	共享缓冲区集合，支持输入/输出复用	系统级缓冲，提高资源利用率

4. 缓冲池工作流程

   • 收容输入：从空缓冲队列取缓冲区 → 装入输入数据 → 加入输入缓冲队列。
   • 提取输入：从输入缓冲队列取缓冲区 → 提取数据 → 归还空缓冲队列。
   • 收容输出：从空缓冲队列取缓冲区 → 装入输出数据 → 加入输出缓冲队列。
   • 提取输出：从输出缓冲队列取缓冲区 → 输出数据 → 归还空缓冲队列。

2. 设备分配与回收

1. 分配原则
   • 独占设备：独占分配（如打印机），避免冲突。
   • 共享设备：共享分配（如磁盘），通过调度算法优化访问。
   • 虚拟设备：通过 SPOOLing 技术将独占设备虚拟为共享设备。
2. 分配流程
   • 进程申请 → 检查设备可用性 → 分配设备控制器、总线 → 记录分配状态 → 进程使用 → 回收设备。

3. 假脱机技术（SPOOLing）

1. 定义
   • Simultaneous Peripheral Operation On Line（外部设备同时联机操作），将独占设备改造为共享设备的技术。
2. 核心原理
   • 截获进程输出数据，暂存于磁盘的输入井/输出井，再由守护进程逐个输出到外设。
3. 组成部分
   • 输入井/输出井：磁盘上的存储区域，用于持久化缓存 I/O 数据。
   • 输入/输出缓冲区：内存中的临时缓存，匹配 CPU 与磁盘速度。
   • 输入/输出进程：负责数据在缓冲区与井之间的传输。
4. 缓冲区与输入/输出井对比

   特性	缓冲区（Buffer）	输入/输出井（Spool）
   物理位置	内存	磁盘
   容量	小（KB ~ MB 级）	大（GB 级）
   访问速度	纳秒级	毫秒级
   核心功能	速度匹配、数据中转	批量存储、虚拟设备
   数据生命周期	临时暂存	持久化到任务完成

4. 设备驱动程序接口

1. 核心功能

   • 隐藏设备硬件差异，为 OS 提供标准接口（如 read/write），向设备控制器读写寄存器。

2. 寄存器编址方式

   • 独立编址：使用专用 I/O 指令（如 x86 的 in/out），例：out 0x21, AL。
   • 内存映像编址：寄存器作为内存地址一部分，使用 mov 指令，例：mov [0x8000f000], AL。

3. 驱动程序示例（Linux 0.11 磁盘驱动片段）

   do_hd = intr_addr; // 绑定中断处理函数
   outb_p(hd_info[drive].ctl, HD_CMD); // 向控制寄存器发命令
   outb_p(nsect, ++port); // 设置读写扇区数
   outb_p(sect, ++port); // 设置起始扇区号
   outb_p(cyl, ++port); // 设置柱面号低8位
   

三、外存管理

1. 磁盘管理

1. 磁盘结构
   • 物理组成：盘片（Platter）、磁道（Track）、扇区（Sector）、柱面（Cylinder）、磁头（Head）。
   • 关键参数：
     • 扇区：磁盘最小寻址/访问单位，默认 512 字节。
     • 柱面：所有盘片上半径相同的磁道集合，是寻道操作的目标。
     • 转速：每分钟转数（RPM），影响旋转延迟（如 5400 转/分、7200 转/分）。
2. 磁盘格式化
   • 低级格式化（物理格式化）：将磁盘划分为物理扇区，每个扇区包含头（地址）、数据区（512 B）、尾（纠错码）。
   • 高级格式化（逻辑格式化）：创建文件系统（如 EXT4、NTFS），划分引导扇区、inode 区、数据区。
3. 磁盘分区
   • 主引导记录（MBR）：磁盘第 1 个扇区（512 字节），包含 446 字节引导代码、16 × 4 字节分区表、2 字节签名（0x55AA）。
   • 分区类型：
     • 基本分区：最多 4 个，可直接使用。
     • 扩展分区：1 个，可划分子分区（逻辑分区）。
   • 示例（Linux 分区）：/dev/sda1（基本分区）、/dev/sda5（扩展分区内的逻辑分区）。
4. 磁盘访问延迟
   平均磁盘访问时间 = 平均寻道时间 + 平均旋转延迟 + 传输时间 + 控制器延迟
   • 平均寻道时间：磁头移动到目标柱面的时间（8 ~ 12 ms）。
   • 平均旋转延迟：扇区旋转到磁头下方的时间，公式：
     平均旋转延迟 = 0.5 / 转速（转/分）× 60 × 1000 (ms)
     例：5400 转/分的磁盘，平均旋转延迟 = 0.5 / 5400 × 60 × 1000 = 5.6 ms。
   • 传输时间：数据从扇区传输到内存的时间，公式：
     传输时间 = 数据大小 / 传输速率
     例：512 KB 数据，传输速率 200 MB/s，传输时间 = 512 × 1024B / (200 × 1024 × 1024 B/s) ≈ 2.56 ms。
5. 磁盘调度算法

   算法	英文名称	原理	优点	缺点
   先来先服务	FCFS	按请求顺序处理	公平、简单	平均寻道距离大，效率低
   最短寻道时间优先	SSTF	优先处理距离当前磁头最近的请求	寻道时间短，效率高	可能导致饥饿（远磁道请求长期等待）
   扫描算法	SCAN（电梯算法）	磁头沿一个方向移动，处理沿途请求，到端点后反向	无饥饿，寻道效率高	两端磁道请求延迟不均
   循环扫描算法	C-SCAN	磁头沿一个方向移动，到端点后直接返回另一端起点	两端请求延迟均匀	额外移动开销
   LOOK 算法	C-LOOK	磁头沿一个方向移动，处理沿途请求，无请求时反向	无额外移动，效率最优	实现复杂

2. 固态硬盘（SSD）管理

1. 基本结构
   • 核心组件：NAND Flash（存储介质）、控制器（嵌入式处理器）、DRAM Buffer（缓存）、总线接口（SATA/PCIe）。
   • NAND Flash分类：SLC（1 bit/单元，寿命长）、MLC（2 bit/单元）、TLC（3 bit/单元）、QLC（4 bit/单元，容量大）。
2. 读写性能特性
   • 读写限制：NAND Flash 只能将 1 变为 0，写数据需先擦除（块级擦除），不能原地覆盖。
   • 关键特性：
     • 顺序读：~ 550 MB/s，顺序写：~ 470 MB/s。
     • 随机读：~ 365 MB/s，随机写：~ 303 MB/s（受擦除速度限制）。
     • 写放大效应：修改数据时需读取块内有效页 → 修改 → 写入新页 → 擦除原块，导致实际写入量大于逻辑写入量。
3. 磨损均衡（Wear Leveling）
   • 目的：NAND Flash 块擦写次数有限（SLC：5 ~ 10 万次，TLC：3 ~ 1 万次），需使所有块擦写次数均匀。
   • 实现方式：
     • 动态磨损均衡：优先使用擦写次数少的块。
     • 静态磨损均衡：迁移冷数据（长期不更新）到高擦写次数块，释放低擦写次数块存储热数据。
4. 垃圾回收（Garbage Collection）
   • 目的：回收包含无效页的块，释放存储空间。
   • 流程：识别包含无效页的块 → 迁移块内有效页到新块 → 擦除原块 → 标记为空闲。
   • 优化：区分冷热数据，避免频繁回收热数据块。
5. 闪存翻译层（FTL）
   • 核心功能：
     • 地址映射：将逻辑扇区号（LSN）转换为物理页地址（Package → Die → Plane → Block → Page）。
     • 磨损均衡：管理块擦写次数，均匀分配磨损。
     • 垃圾回收：回收无效块，优化存储空间利用。
6. 适配文件系统
   • 传统文件系统（如 EXT4）：针对机械磁盘设计，未优化 SSD 特性，性能受限。
   • 闪存友好文件系统（如 F2FS）：基于日志追加写，数据冷热分离，支持多流写入，随机读写性能比 EXT4 高 2 倍。