OS期中知识点汇总

I. 引论与OS结构

• OS 角色与功能:
  • 定义: 操作系统是管理计算机硬件资源的软件集合，向计算机程序提供共性服务。
  • 核心作用:
    • 资源管理者: 有效控制和管理计算机系统中的各种软硬件资源（处理机、存储器、I/O设备、文件等），提高资源利用率和系统效率（吞吐量、响应时间）。
    • 用户与硬件间的接口: 提供用户接口（如命令行Shell、图形界面GUI）和程序接口（API），屏蔽硬件复杂性，使计算机更易于使用。
    • 抽象/扩展机/虚拟机: 在裸机之上覆盖一层软件，实现对计算机资源的抽象，提供更强大、方便的功能。
  • 主要功能模块:
    • 处理机管理 (进程/线程控制、同步、通信、调度)
    • 存储器管理 (内存分配、保护、地址映射、扩充)
    • 设备管理 (I/O设备分配、操作、缓冲、虚拟设备)
    • 文件管理 (文件存储空间管理、目录管理、读写、保护)
    • 作业控制 (作业调度与控制)
    • 用户接口 (提供给用户的操作界面)
  • 设计目标: 方便性 (易用) 和 高效性 (资源利用率、吞吐量)。
• 启动过程 (Boot Process):
  • Bootstrapping (引导): 计算机启动是一个“自举”过程，需要先运行程序才能启动，但不启动又无法运行程序。早期通过“拉鞋带”比喻，将一小段程序装入内存使计算机运行起来。
  • BIOS/UEFI:
    • BIOS (基本输入/输出系统): 固化在主板ROM/EEPROM中的固件。上电后CPU跳转到固定物理地址 0xFFFF0 (Intel 80386) 开始执行BIOS。
    • BIOS 功能: 加载硬件信息 (CPU, 内存, 启动顺序等), 执行POST (Power-On Self-Test, 硬件自检), 根据启动顺序查找可引导设备。
    • BIOS 局限: 16/20位实模式寻址能力有限，移植性差。
    • UEFI (统一可扩展固件接口): BIOS的现代替代品，克服了BIOS的限制。支持大容量硬盘(>2TB, GPT分区)、CPU无关架构和驱动、模块化设计、提供预操作系统环境（如网络功能）。
  • MBR (主引导记录):
    • 位置: 硬盘的第一个物理扇区 (0磁头0磁道1扇区)。
    • 大小: 512字节。
    • 结构:
      • 引导代码 (Bootloader的一部分, 446字节)（预启动信息）。
      • 硬盘分区表 (DPT, 4个16字节的分区项, 共64字节)。
      • 结束标志/幻数 (Magic Number, 2字节, 0xAA55)。
    • 作用: BIOS将MBR加载到内存 0x7C00 处并跳转执行。MBR代码检查分区表，找到活动分区，加载该分区的引导扇区(Boot Sector)到 0x7C00 并执行。
    • P.S. MBR的主要功能是传递引导控制权，从BIOS传递到活动分区的引导扇区（或下一阶段的Boot Loader），它本身不负责初始化磁盘（BIOS做了初步工作），也不直接加载操作系统内核。因此，原判断题的描述是不准确的。
  • 引导扇区 (Boot Sector): 位于每个分区的第一个扇区，包含加载该分区操作系统的代码。MBR将活动分区的引导扇区加载并执行。
  • Bootloader (引导加载程序):
    • 定义: 操作系统内核运行前执行的一段小程序。
    • 组成 (Booter + Loader): 初始化硬件 (Booter)，加载操作系统内核映像到内存并跳转执行 (Loader)。
    • 阶段: 常分为 Stage 1 (依赖硬件, 通常汇编实现, 如MBR或Boot Sector中的代码) 和 Stage 2 (功能更复杂, 通常C实现, 具有更好可读性和移植性)。
    • 常见类型: U-Boot (嵌入式常用), LILO, GRUB (X86常用)。
    • 依赖性: 严重依赖具体硬件，常需移植。
  • 加载内核:
    • Bootloader将内核映像 (可能是压缩的, 如zImage, bzImage) 从存储介质加载到内存指定位置。
    • 进行必要的内存移动、解压缩。
    • 初始化早期环境 (如堆栈)。
    • 执行内核入口代码 (如Linux的 head.s 中的 kernel_entry 或 start_kernel)。
    • 内核接管控制权，进行进一步初始化（内存管理、页表、调度器、设备驱动、中断等）。
  • 启动 Init 进程: 内核初始化完成后，启动用户空间的第一个进程 /sbin/init。
  • Init 进程工作: 读取 /etc/inittab (或Systemd配置)，设置运行级别 (Runlevel)，执行相应的启动脚本 (rc.sysinit, rcX.d/*, rc.local)，最终启动登录程序 (getty/login) 等待用户登录。
  • 整体过程: 逐级引导，逐步释放系统灵活性。
• 内核态 (Kernel Mode) vs. 用户态 (User Mode):
  • 目的: 保护操作系统内核和关键系统资源不被用户程序破坏。
  • 内核态: 运行操作系统代码，具有最高权限，可访问所有硬件和内存，执行特权指令。
  • 用户态: 运行用户应用程序，权限受限，不能直接访问硬件，不能执行特权指令。
  • 特权指令: 只能在内核态执行的指令，如I/O操作、修改中断屏蔽字、修改内存管理寄存器、停机等。
  • 模式切换:
    • 用户态 -> 内核态: 通过中断、异常或系统调用（陷阱 Trap）。
    • 内核态 -> 用户态: 通过执行特定指令（如 iret 中断返回指令）。
  • 保护边界: 通过硬件机制（如CPU模式位、MMU）强制隔离用户态和内核态。
• 系统调用 (System Calls):
  • 定义: 用户程序请求操作系统内核提供服务的接口。是用户态进入内核态的主要方式之一。
  • 机制: 通常通过特定的“陷阱”指令（如x86的 int 0x80 或 syscall）触发，将控制权转移给内核中的系统调用处理程序。
  • 实现:
    • 用户程序将系统调用号和参数放入指定寄存器或内存。
    • 执行陷阱指令，CPU切换到内核态。
    • 内核根据系统调用号在系统调用分派表 (System service dispatch table) 中找到对应的服务例程地址。
    • 执行内核服务例程。
    • 执行完毕，将结果返回给用户程序，切换回用户态，从陷阱指令后继续执行。
  • 例子: read(fd, buffer, nbytes)
• 中断 (Interrupts) 与 异常 (Exceptions):
  • 中断: 来自硬件设备（如I/O完成、定时器）的异步信号，与当前指令执行无关。可屏蔽或不可屏蔽。
  • 异常: 由CPU执行指令时内部产生的同步事件。
    • 陷阱 (Trap): 有意产生的异常，如系统调用、调试断点。通常在指令执行后处理，返回到下一条指令。
    • 故障 (Fault): 可恢复的错误，如缺页、除零错误。通常在指令执行前/中检测到，处理后返回到当前指令重新执行。
    • 终止 (Abort): 不可恢复的严重错误，如硬件错误。无法返回。
  • 处理过程: CPU检测到中断/异常 -> 保存当前状态 (PC, PSW等) -> 根据中断/异常向量号查找中断处理程序入口地址 -> 跳转执行中断处理程序 (ISR) -> 恢复现场 -> 返回原执行点。
  • 作用: 实现并发 (I/O与CPU并行)、处理错误、实现系统调用。
• OS 类型与历史:
  • 史前: 无OS，手动操作。
  • 批处理系统:
    • 联机: 作业直接由CPU控制输入输出，CPU等待I/O，效率低。
    • 脱机: 使用卫星机处理I/O，主机与卫星机通过磁带交互，提高CPU利用率。
    • 多道批处理: 内存中驻留多个作业，CPU在一个作业等待I/O时切换到另一个作业，进一步提高效率。特点：多道、成批、无交互。
  • 分时系统: 允许多用户通过终端同时与计算机交互。特点：多路性、交互性、独立性、及时性。关键技术：时间片轮转。
  • 实时系统: 对响应时间有严格要求。特点：及时响应、高可靠性、专用性。
  • 网络操作系统 (NOS): 提供网络通信和资源共享功能，但各计算机仍是独立的。
  • 分布式操作系统 (DOS): 将多台计算机联结成一个逻辑整体，对用户透明。
  • 嵌入式操作系统: 面向特定应用，资源受限。
  • 混合型: 现代操作系统通常结合多种类型特点。
• **存储层次结构 (Memory Hierarchy):
  • 结构: 寄存器 -> Cache (L1, L2, L3) -> 主存 (RAM) -> 辅存 (磁盘/SSD) -> 备份存储 (磁带)。
  • 特点: 越靠近CPU速度越快、容量越小、成本越高。
  • 速度差异: CPU与内存/I/O存在巨大速度差异 ("内存墙"问题)，Cache用于缓解此问题。
  • 管理: 操作系统主要负责主存及辅存的管理，对Cache的管理通常由硬件完成，但OS需要考虑Cache一致性等问题。
• 操作系统结构 (OS Structure):
  • 模块化: 将OS划分为功能模块，通过接口交互。优点：灵活性、易修改维护；缺点：接口定义困难。
  • 分层结构: 将OS功能组织成有序层次，下层为上层提供服务。优点：结构清晰、易验证；缺点：效率可能较低，层间依赖严格。
  • 微内核: 内核只保留最基本功能（IPC、基本调度、中断处理），其他服务（文件系统、内存管理、设备驱动）作为用户态服务器进程运行。优点：可靠性、灵活性、可移植性；缺点：性能开销（进程间通信频繁）。
  • 虚拟机 (VM): 在硬件之上创建一层软件（虚拟机监视器VMM/Hypervisor），模拟出多个裸机环境，每个环境可运行独立操作系统。支持遗留系统、隔离性好。
  • 混合结构: 如类微内核（Windows NT）或宏内核（Linux, Unix）结合了不同结构的特点。
  • 机制与策略分离: 将“如何做”（机制）与“做什么”（策略）分开，增加系统灵活性和可扩展性。

II. 进程管理

1. 进程概念 (Process Concept):
   • 引入原因:
     • 程序的并发执行带来了间断性、非封闭性和不可再现性等问题 ，单纯的“程序”概念无法描述和管理这种动态、并发的活动。
     • “程序”是静态的指令集合，而“计算/执行”是动态的过程，两者并非一一对应。
     • 多道程序环境下，资源（如CPU、内存）受限，程序执行会走走停停，需要一种机制来管理这种状态。
     • 最早在 MULTICS 和 IBM CTSS/360 等系统中引入。
   • 定义:
     • 进程是程序的一次执行过程。
     • 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
     • 进程是可以和别的计算并发执行的计算。
     • 进程是程序在一个数据集合上运行的过程。
     • 核心角色: 进程是操作系统进行资源分配和调度的一个独立单位。
   • 与程序的区别:
     • 动态 vs. 静态: 进程是动态的执行过程，程序是静态的代码集合。
     • 生命周期: 进程是暂时的（有创建、运行、消亡），程序是永久的（可存储）。
     • 组成: 进程包含程序、数据和进程控制块 (PCB)，程序只是代码。
     • 对应关系: 一个程序可以对应多个进程（多次执行），一个进程在其执行过程中可能调用多个程序。
   • 特征:
     • 动态性: 进程有生命周期，状态会变化。
     • 并发性: 多个进程实体可同时存在于内存中并交替执行。
     • 独立性: 作为资源分配和调度的基本单位，独立运行。
     • 异步性: 进程按各自独立的、不可预知的速度推进，相互制约。
2. 进程控制块 (PCB - Process Control Block):
   • 定义: 操作系统为管理和控制进程而定义的数据结构，是进程存在的唯一标志。
   • 作用: 保存进程的状态信息，使得进程可以被中断和恢复，实现并发。OS通过PCB来管理和调度进程。
   • 生命周期: PCB在进程创建时建立，伴随进程整个生命周期，进程撤销时回收。
   • 包含信息 (主要内容):
     • 进程标识符 (PID): 唯一的内部ID。
     • 进程状态: 如就绪、运行、阻塞等。
     • 程序计数器 (PC): 指向下一条要执行的指令地址。
     • CPU寄存器: 通用寄存器、状态寄存器等的副本（用于上下文切换时恢复）。
     • CPU调度信息: 进程优先级、调度队列指针等。
     • 内存管理信息: 页表或段表的指针、内存界限等。
     • 记账信息: CPU使用时间、时间限制等。
     • I/O状态信息: 分配给进程的I/O设备、打开文件列表等。
     • 进程间通信/同步信息: 信号量、消息队列指针等。
     • 家族关系: 父进程ID (PPID)、子进程列表指针等。
     • 链接指针: 用于将PCB组织到不同的状态队列（如就绪队列、阻塞队列）。
   • 组织方式:
     • 线性表: 将所有PCB存在一个数组中，简单但查找效率低，不易于状态管理。
     • 索引表: 按状态建立不同的索引表，指向PCB。
     • 链接表: 按状态将PCB组织成链式队列（如就绪队列、各事件的阻塞队列），最常用、灵活。
   • Linux 实现: Linux 内核中使用 task_struct 结构体作为PCB。
3. 进程状态 (Process States):
   • 基本状态 (三种):
     • 运行 (Running): 进程正在CPU上执行。
     • 就绪 (Ready): 进程已获得除CPU外的所有资源，等待被调度执行。
     • 阻塞/等待 (Blocked/Waiting): 进程因等待某个事件（如I/O完成、资源可用、信号）而暂停执行。
   • 扩展状态 (五种):
     • 新建 (New): 进程正在被创建，尚未准备好运行。
     • 就绪 (Ready): 同上。
     • 运行 (Running): 同上。
     • 阻塞/等待 (Waiting): 同上。
     • 终止 (Terminated): 进程执行完毕或被终止，正在进行资源回收。
   • 状态转换:
     • 新建 -> 就绪 (Admitted): 进程创建完成，资源基本分配到位。
     • 就绪 -> 运行 (Scheduler Dispatch): 调度程序选中该进程，分配CPU。
     • 运行 -> 就绪 (Interrupt/Timeout): 时间片用完或被更高优先级进程抢占。
     • 运行 -> 阻塞 (I/O or Event Wait): 进程请求I/O或等待某个事件发生。（这是进程自身可以决定的转换）
     • 阻塞 -> 就绪 (I/O or Event Completion): 等待的事件发生（如I/O完成）。
     • 运行 -> 终止 (Exit): 进程正常完成或出错终止。
4. 进程创建与终止:
   • 创建 (Creation):
     • 时机/情形: 用户登录、批处理作业提交、提供服务（如Web服务器创建子进程处理请求）、一个进程创建另一个进程。
     • 原语: 操作系统提供创建进程的原语（如 fork, exec）。
     • fork() 系统调用: (Unix/Linux) 创建一个与父进程几乎完全一样的子进程。关键在于：
       • 调用一次，返回两次。
       • 父进程中返回子进程的PID。
       • 子进程中返回 0。
       • 子进程复制父进程的地址空间（通常使用写时复制 CoW 优化）、文件描述符等。
     • 创建过程: 分配PID -> 创建PCB -> 分配资源（如内存空间） -> 初始化PCB -> 插入就绪队列。
   • 终止 (Termination):
     • 时机/情形: 正常完成、出错（如非法指令、内存访问越界）、被其他进程终止（如父进程终止子进程 kill）、用户退出登录、达到时限等。
     • 原语: 操作系统提供终止进程的原语（如 exit, kill）。
     • 终止过程: 设置进程状态为终止 -> 回收占用的资源 -> 回收PCB。
   • 进程树: 进程间存在父子关系，形成树状结构。
5. 上下文切换 (Context Switching):
   • 定义: CPU从一个进程（或线程）转换到另一个进程（或线程）去执行的过程。
   • 时机: 中断处理、调度程序运行时。
   • 过程:
     • 保存当前运行进程的上下文（CPU寄存器状态、PC、PSW等到其PCB中）。
     • 更新当前进程的PCB信息（如状态变为就绪或阻塞）。
     • 将该PCB移到相应的队列（就绪或阻塞）。
     • 选择一个新的就绪进程。
     • 更新新进程的PCB（状态变为运行）。
     • 根据新进程PCB恢复其上下文（加载寄存器、PC、PSW等）。
     • 切换内存映射（更新页表基址寄存器，可能需要刷新TLB）。
   • 与模式切换 (Mode Switch) 的区别:
     • 模式切换: CPU运行状态从用户态到内核态（或反之）的切换，通常由中断、异常、系统调用引起。只涉及少量CPU状态（如PC、PSW、部分寄存器）的保存和恢复。开销相对较小。
     • 上下文切换: 必须在内核态完成，包含模式切换，但还涉及调度、PCB操作、内存管理（页表切换、TLB刷新）等更复杂、开销更大的操作。
   • 开销: 上下文切换是纯粹的系统开销，需要尽量减少其频率和耗时。
6. 进程间通信 (IPC - Inter-Process Communication):
   • 必要性: 进程是独立地址空间的，需要机制来交换信息和协作。
   • 方式:
     • 低级通信: 传递状态和整数值（如信号量，用于同步互斥）。
     • 高级通信: 传递任意数量数据。主要包括：
       • 管道 (Pipe) / 命名管道 (FIFO)
       • 消息队列 (Message Queue)
       • 共享内存 (Shared Memory): 将同一块物理内存映射到不同进程的地址空间，允许进程直接读写，效率最高，但需要额外的同步机制。
       • 信号量 (Semaphore) - 也可用于传递简单信息
       • 套接字 (Socket) - 主要用于网络通信
       • 信号 (Signal) - 异步通知事件
   • (本课件主要在同步章节详细讲解IPC，此处仅提及共享内存作为高效方式)
7. 程序内存布局:
   • 进程拥有独立的虚拟地址空间。
   • 典型布局（Linux/MIPS示例）：
     • 用户空间 (kuseg): 应用程序代码 (.text)、已初始化数据 (.data)、未初始化数据 (.bss)、堆 (heap, malloc分配)、栈 (stack, 函数调用)。
     • 内核空间 (kseg0, kseg1, kseg2): 操作系统内核代码和数据、共享库映射区、内核栈等。用户态不可直接访问。
   • PCB中存储了指向这些区域的相关信息（如页表指针）。
8. 程序加载与链接:
   • 加载: 操作系统负责将可执行文件从磁盘读入内存，创建进程映像，设置PC指向入口点。
   • 链接: 将编译后的目标文件和库文件组合成可执行文件的过程（静态链接）或在运行时加载共享库（动态链接）。

III. 线程 (Thread)

1. 线程概念:
   • 引入动机/进程的不足:
     • 进程作为资源分配和调度的单位，创建和切换开销较大。
     • 进程在一个时间只能做一件事；若想并发执行多个任务（如Web服务器同时处理多个请求，或字处理软件同时输入、检查、显示），用多进程方式实现，进程间通信和共享数据复杂且效率低。
     • 若进程中某个执行流因I/O等原因阻塞，整个进程都会挂起，即使进程中其他部分不依赖该阻塞操作也无法执行。
   • 定义:
     • 线程是进程内的一个执行单元/实体。
     • 是操作系统能够进行CPU调度和分派的基本单位。
     • 也称为轻量级进程 (Lightweight Process, LWP)，尤其是在混合模型中。
   • 核心思想: 将传统进程的两个属性——“资源拥有者”和“可执行单元”——进行分离。进程继续作为资源（地址空间、文件等）的拥有者，而线程作为执行的实体。
2. 进程 vs. 线程:
   • 资源所有权:
     • 进程: 拥有独立的地址空间、文件句柄、I/O设备等系统资源，是资源分配的基本单位。
     • 线程: 基本上不拥有系统资源（除了必需的如PC、寄存器、栈），它共享其所属进程的所有资源（包括地址空间、全局变量、打开的文件、信号处理等）。
   • 调度单位:
     • 进程: 传统上也是调度单位。
     • 线程: 是CPU调度的基本单位。OS调度器选择线程来运行。
   • 独立性/通信:
     • 进程: 具有较强的独立性，地址空间隔离，进程间通信（IPC）需要内核特殊机制（管道、消息队列、共享内存等），相对复杂且开销大。
     • 线程: 同一进程内的线程共享地址空间，通信非常方便（直接读写全局变量、堆内存，传递指针），但也因此需要显式同步来避免数据竞争。
   • 开销:
     • 创建/撤销: 创建线程比创建进程快得多（通常10-100倍），因为不需要分配和初始化那么多资源（如地址空间、页表）。
     • 切换: 线程上下文切换比进程上下文切换开销小，因为通常只需要保存/恢复线程私有的寄存器和栈指针，而不需要切换地址空间（页表）。
   • 并发性: 线程提供了更细粒度的并发。
   • 私有成分 vs. 共享成分:
     • 线程私有: 线程ID (TID)、程序计数器 (PC)、寄存器集合、栈 (Stack)、线程局部存储 (TLS)。
     • 进程共享 (线程间共享): 代码段、数据段、堆内存、文件描述符、信号处理方式、当前工作目录、用户和组ID等。
3. 多线程 (Multithreading):
   • 定义: 一个进程包含多个线程。
   • 优点:
     • 提高响应速度: 如GUI程序，可以将耗时操作（如I/O、复杂计算）放在后台线程，保持UI线程响应用户操作。
     • 资源共享方便: 线程间通过共享内存高效通信。
     • 经济性: 创建和切换线程开销远小于进程。
     • 提高系统吞吐量/并发度: 在多核CPU上，不同线程可以真正并行执行，充分利用硬件资源。
   • 潜在开销与挑战:
     • 同步开销: 需要使用锁、信号量等机制保护共享数据，带来额外开销和复杂性。
     • 上下文切换开销: 虽然比进程切换小，但频繁切换仍有开销。
     • 编程复杂性: 多线程程序设计和调试比单线程程序更困难，容易出现死锁、竞争条件等问题。
4. 用户级线程 (User-Level Threads, ULT) vs. 内核级线程 (Kernel-Level Threads, KLT):
   • 实现方式:
     • ULT: 完全在用户空间实现，由应用程序通过线程库 (library) 进行管理 (创建、调度、同步)。内核不知道线程的存在，只认进程。
     • KLT: 由操作系统内核直接支持和管理。线程的创建、调度、管理都是内核负责。
   • 内核感知:
     • ULT: 内核不可感知。
     • KLT: 内核可感知。
   • 创建与管理:
     • ULT: 通过调用线程库函数完成，速度快，无需系统调用。
     • KLT: 需要执行系统调用，由内核完成，速度相对较慢。
   • 调度与切换:
     • ULT: 调度由用户级线程库实现（可定制），切换非常快，仅需保存/恢复少量寄存器，无需模式切换。
     • KLT: 调度由内核调度器完成，切换需要完整的上下文切换（可能包括模式切换），速度相对较慢。
   • 阻塞行为: (关键区别)
     • ULT: 如果一个ULT执行了阻塞型系统调用（如读文件），那么整个进程（包含其所有ULT）都会被内核阻塞，因为内核只知道这个进程在等待。
     • KLT: 如果一个KLT阻塞，内核可以调度同一进程的其他KLT或其他进程的KLT来运行。
   • 系统调用处理:
     • ULT: 系统调用由进程（内核线程）发出，可能导致整个进程阻塞。
     • KLT: 系统调用由线程发出，阻塞只会影响该线程。
   • 并行性:
     • ULT (Many-to-One模型): 无法利用多核处理器实现真正的并行，因为内核一次只能调度一个进程（对应一个内核线程）到CPU上。
     • KLT: 可以被内核调度到不同的CPU核心上，实现真正的并行。
   • 修改页表的能力: 无论是ULT还是KLT，修改页表都是内核的特权操作。用户级代码（包括线程库）不能直接修改页表。KLT的切换可能伴随内核进行的页表相关操作，但并非线程自身能力。
   • 线程模型:
     • 多对一 (Many-to-One): 多个ULT映射到一个KLT。实现简单，但有阻塞问题和并行限制。
     • 一对一 (One-to-One): 每个ULT对应一个KLT。并发性好，阻塞问题解决，但创建KLT开销大。
     • 多对多 (Many-to-Many): 多个ULT映射到小于等于ULT数量的KLT（或LWP）。兼具两者优点，较复杂。
5. 线程通信:
   • 主要方式是共享内存，因为它们共享进程的地址空间（全局变量、堆）。
   • 可以直接读写共享变量或通过指针访问共享数据结构。
   • 线程库也可能提供消息传递等机制。
   • 必须进行同步以保护共享数据。
6. 线程特定数据:
   • 虽然线程共享大部分进程资源，但每个线程必须拥有自己独立的：
     • 程序计数器 (PC): 指示下一条要执行的指令。
     • 寄存器集合: 保存线程当前的运算状态。
     • 栈 (Stack): 用于存储局部变量、函数参数、返回地址等。这是线程独立性的重要体现。
   • 线程局部存储 (Thread-Local Storage, TLS): 一种机制，允许线程拥有看似全局或静态，但实际上是线程私有的数据副本（例如，解决多线程环境下errno全局变量的覆盖问题）。

IV. CPU 调度

• 基本概念: （之前已有）目标、抢占等。
• 调度队列: （之前已有）就绪队列、阻塞队列等。
• 优先级调度问题:
  • 优先级反转 (Priority Inversion):
    • 问题定义: 一个高优先级进程（或线程）被一个低优先级进程（或线程）阻塞，而该低优先级进程又无法执行（因为它被一个中优先级进程抢占），导致高优先级进程长时间等待。
    • 发生场景: 当低优先级进程持有高优先级进程所需的锁（如进入了临界区）时。
    • 解决方案 : 优先级继承 (Priority Inheritance)、优先级天花板 (Priority Ceiling Protocol)。

V. 进程同步

1. 并发与同步/互斥基础:
   • 并发执行特征: 间断性、非封闭性、不可再现性。
   • 产生的问题: 资源争夺、与时间有关的错误。
   • 竞争条件 (Race Condition): 多个进程/线程并发访问和操作同一共享数据，执行结果取决于访问发生的特定顺序。
   • 临界资源 (Critical Resource): 一次仅允许一个进程/线程访问的共享资源（如打印机、共享变量）。
   • 临界区 (Critical Section): 进程/线程中访问临界资源的那段代码。
   • 进程互斥 (Mutual Exclusion): 确保任意时刻最多只有一个进程/线程在临界区内执行，是对临界资源的排他性访问。
   • 进程同步 (Synchronization): 协调并发进程/线程间的执行顺序，使它们能有效共享资源和协作完成任务（直接制约关系）。
   • 互斥与同步的区别与联系: 互斥是排他性访问，同步是协调执行次序。同步通常包含互斥。
   • 临界区管理需满足的条件/准则:
     • 互斥进入 (Mutual Exclusion): 一次最多一个。
     • 有空让进 (Progress): 无进程在临界区且有进程想进入时，不能无限延迟选择。
     • 有限等待 (Bounded Waiting): 进程请求进入临界区的等待时间必须有限。
     • (让权等待): 无法进入临界区时应释放CPU，避免忙等。
   • Bernstein 条件: 判断两个语句/进程段是否可以并发执行而结果可再现的充分条件（基于读写集分析）。
2. 实现同步/互斥的方法:
   • 基于忙等待 (Busy-Waiting) 的方法:
     • 软件方法:
       • 尝试1 (轮转法 turn): 违反 Progress。
       • 尝试2 (标志法 Occupied): 不能保证互斥。
       • 尝试3 (双标志法 pturn, qturn): 可能都无法进入，违反 Progress。
       • 尝试4 (双标志+让权): 破坏互斥。
       • Dekker 算法 (1965): 第一个正确的纯软件解法，结合标志和轮转。
       • Peterson 算法 (1981): 更简洁的软件解法，适用于两个进程。
       • Lamport 面包店算法 (Bakery Algorithm): 适用于N个进程的软件解法，基于取号排队思想。
       • 软件方法缺点: 普遍存在忙等待问题，浪费CPU。
     • 硬件方法:
       • 中断屏蔽:
         • 方法：进临界区前关中断，出临界区后开中断。
         • 优点：简单。
         • 缺点：代价高（影响系统效率和时钟），不适用于多CPU，用户进程使用危险。主要用于内核自身短临界区。
       • 原子指令 (Test-and-Set, TSL):
         • TestAndSet(lock): 原子地读取 lock 的旧值并将其设为 true。
         • 自旋锁 (Spinlock): 基于TSL实现，循环测试锁直到获取。
       • 原子指令 (Swap/XCHG): 原子地交换内存单元和寄存器（或两个内存单元）的值。也可用于实现锁。
       • 原子指令 (MIPS LL/SC - Load Linked / Store Conditional): 更精巧的原子操作对，用于实现无锁数据结构或高效锁。LL 读取并标记，SC 仅在标记未被清除（即期间无其他写操作）时才写入并返回成功。
       • 硬件方法缺点: 仍然是忙等待，浪费CPU，可能导致优先级反转。
   • 基于阻塞等待的同步原语:
     • 基本思路 (Sleep/Wakeup): 进程等待条件不满足时调用 Sleep 阻塞自己，条件满足时由其他进程调用 Wakeup(pid) 唤醒。存在“丢失的唤醒”问题（未详述）。
     • 信号量 (Semaphore): (Dijkstra, 1965)
       • 定义: 一个包含整数值 (count) 和一个等待队列 (queue) 的数据结构。
       • 类型:
         • 二元信号量 (Binary Semaphore / Mutex): 值只能为0或1，常用于互斥。
         • 计数信号量 (Counting Semaphore): 值可为任意非负整数，常用于资源计数。
         • 强信号量 vs. 弱信号量: 队列管理方式（FIFO vs. 无序）。
       • 原子操作 (P / wait / down 和 V / signal / up):
         • P(S) 或 wait(S): S.count--；如果 S.count < 0，则阻塞调用进程并加入 S.queue。
         • V(S) 或 signal(S): S.count++；如果 S.count <= 0，则从 S.queue 唤醒一个进程。
       • 物理意义: S.count >= 0 表示可用资源数；S.count < 0 其绝对值表示等待该资源的进程数。
       • 实现: P/V操作必须原子执行，可通过关中断或硬件原子指令（如TSL、CAS）保护。
       • 应用: 实现互斥 、有限并发、进程同步
       • 信号量集 (Semaphore Set): 一次性申请/释放多个资源。
         • AND 型: 所有资源都满足才分配。
         • 一般型: 对每个资源可指定不同需求量(ti)和占用量(di)。
       • 优缺点: 表达能力强，但使用易出错（PV顺序、忘记V等），可能导致死锁。
     • 管程 (Monitor): (Hoare/Hanson, 1973)
       • 动机: 解决信号量编程复杂、易错的问题，提供更高级的同步抽象。
       • 定义: 一种语言结构（模块），包含共享数据、对数据操作的一组过程、以及初始化代码。
       • 特性:
         • 互斥: 任何时刻只有一个进程能在管程内执行其过程（由编译器保证）。
         • 条件变量 (Condition Variable, CV): 用于进程在管程内等待特定条件满足。CV本身不存值，只有等待队列。
         • CV操作: wait(cv) (阻塞当前进程并释放管程锁，加入cv队列)，signal(cv) (唤醒cv队列中的一个等待进程)。
       • CV 与信号量的区别: wait 总阻塞，signal 若无等待者则无效；信号量P不一定阻塞，V总改变计数值。
       • signal 语义:
         • Hoare 管程: signal后，唤醒者(P)等待，被唤醒者(Q)立即执行。引入紧急等待队列。
         • Mesa 管程: signal后，被唤醒者(Q)变就绪，唤醒者(P)继续执行。
       • 实现 (Hoare管程使用信号量): 需要 mutex (管程入口互斥), next (紧急等待队列信号量), next_count, 以及每个CV对应的 x-sem 和 x-count。
3. 进程间通信 (IPC - Inter-Process Communication):
   • 分类:
     • 低级通信: 传递状态/控制信息（如信号量、管程本身）。
     • 高级通信: 传递任意数据。
   • 常见高级IPC机制:
     • 管道 (Pipe):
       • 无名管道: 半双工，只能用于父子/兄弟进程，存在于内存中。
       • 有名管道 (FIFO): 有文件系统路径，允许无亲缘关系进程通信。
     • 消息传递 (Message Passing):
       • 原语: send(destination, message), receive(source, message)。
       • 方式: 阻塞/非阻塞。
       • 寻址: 直接通信/间接通信 (邮箱 Mailbox)。
     • 共享内存 (Shared Memory):
       • 机制: 将同一物理内存映射到不同进程的虚拟地址空间。
       • 优点: 速度最快（无内核干预的数据传输）。
       • 缺点: 需要外部同步机制（如信号量、互斥锁）来保证访问正确性。
     • 信号量 (Semaphore): 也可用于简单通信。
     • 套接字 (Socket): 主要用于网络通信，也可用于本机IPC。
     • 信号 (Signal): 异步通知机制。
   • POSIX IPC 接口: 提供了对信号量、消息队列、共享内存的标准API。
4. 经典同步问题:
   • 生产者-消费者问题 (Bounded Buffer Problem):
     • 描述: 生产者放数据到缓冲区，消费者取数据，缓冲区大小有限。
     • 关系: 生产者/消费者之间互斥访问缓冲区，生产者需等待缓冲区有空位，消费者需等待缓冲区有数据（同步）。
     • 信号量解法: mutex (互斥访问缓冲区), empty (空槽位计数), full (满槽位计数)。注意PV操作顺序避免死锁。
     • 管程解法: 使用管程封装缓冲区和计数器，用条件变量 full, empty。
     • 扩展: 银行柜台问题。
   • 读者-写者问题 (Readers-Writers Problem):
     • 描述: 允许多个读者同时读，但写者必须独占访问。读写互斥，写写互斥。
     • 信号量解法 (读者优先): rmutex (互斥访问 readcount), fmutex (互斥访问文件/数据), readcount (记录当前读者数)。
     • 问题: 可能导致写者饥饿。
     • 公平解法 (使用闸机 Turnstile / Lightswitch 概念): 引入额外机制（如 turnstile 信号量）控制入口，防止新读者在写者等待时进入。
   • 哲学家进餐问题 (Dining Philosophers Problem):
     • 描述: 5个哲学家围桌吃饭，每人需要左右两根筷子才能吃。
     • 问题: 可能发生死锁（所有人都拿起左手筷子）。
     • 解法思路: 限制同时进餐人数；奇偶编号不同拿筷顺序；原子地拿两根筷子。
   • 睡眠理发师问题 (Sleeping Barber Problem):
     • 描述: 理发师等待顾客，顾客等待理发师或空椅子。
     • 关系: 顾客唤醒理发师，理发师服务完一个顾客后可能唤醒下一个等待的顾客。互斥访问等待椅子计数。
     • 信号量解法: customers (等待理发的顾客数), barbers (空闲理发师数), mutex (互斥访问 waiting 计数器)。
   • H2O 构建问题:
     • 描述: H、O原子线程需要同步形成H2O分子。
     • 解法: 使用信号量/计数器跟踪H、O原子数量，使用 Barrier (或其他同步机制如信号量实现的条件等待) 确保2H和1O都到达后才能 bond，并释放一个 mutex。

VI. 内存管理

1. 基本概念:
   • 内存的角色: 内存是CPU能直接访问的唯一存储介质（不含寄存器和Cache），程序和数据必须装入内存才能运行。
   • 内存管理的目标:
     • 抽象: 向程序员提供方便易用的逻辑地址空间，屏蔽物理内存的复杂性。
     • 保护: 确保每个进程在自己的地址空间内运行，互不干扰。防止恶意或无意的非法访问。
     • 共享: 允许多个进程安全、高效地共享内存中的代码或数据（如共享库）。
     • 效率: 提高内存利用率，减少碎片，支持多道程序并发执行，提高系统吞吐量。
   • 逻辑地址空间 (Logical Address Space) vs. 物理地址空间 (Physical Address Space):
     • 逻辑地址（虚拟地址）: CPU（或说进程）生成的地址。用户程序看到的地址空间。
     • 物理地址: 内存硬件单元（Memory Address Register - MAR）看到的地址，即加载到内存中的实际地址。
     • 内存管理单元 (MMU - Memory Management Unit): 负责将逻辑地址动态转换为物理地址的硬件设备。
   • 地址绑定 (Address Binding): 将程序指令和数据中的地址确定（绑定）到具体物理内存地址的过程。
     • 编译时绑定: 如果编译时就知道程序在内存中的绝对地址，则直接生成绝对代码。要求程序加载到固定位置，缺乏灵活性。
     • 加载时绑定: 如果编译时不知道加载地址，编译器生成可重定位代码。加载器在加载程序时，根据分配的起始地址进行重定位，将逻辑地址转换为物理地址。程序一旦加载，不能在内存中移动。
     • 运行时绑定 (执行时绑定): 地址转换延迟到程序运行时才进行。CPU生成的逻辑地址在每次访问内存时由硬件（MMU）动态转换为物理地址。这是现代操作系统最常用的方式，允许程序在内存中移动，是虚拟内存的基础。
   • 重定位 (Relocation): 将程序中的逻辑地址转换为物理地址的过程。
     • 静态重定位: 在程序加载时由加载器完成。一次性转换，程序加载后不能移动。
     • 动态重定位: 在程序运行时由硬件(MMU)完成。每次访存都可能需要转换。需要基址寄存器(Base Register)和限长寄存器(Limit Register)（用于连续分配）或页表/段表（用于非连续分配）的支持。
   • 程序的链接与加载 (回顾):
     • 链接: 将多个目标模块（.o文件）和库函数组合成一个单一的可执行文件的过程。解决外部符号引用，合并代码段、数据段等。
     • 加载: 将可执行文件从磁盘读入内存，准备运行的过程。涉及空间分配、地址重定位（静态或建立映射关系）。
     • ELF 文件格式: Linux 等系统常用的可执行和可链接文件格式，包含文件头、程序头表（描述段）、节头表（描述节）、各种节（如 .text, .data, .bss, .symtab, .rel.text 重定位表）。加载器依赖程序头表将 LOAD 类型的段加载到内存。
   • 内存保护:
     • 确保进程只能访问分配给自己的内存空间。
     • 界限寄存器 (Base and Limit Registers): (用于连续分配) CPU生成的逻辑地址先与限长寄存器比较，若小于限长，则加上基址寄存器的值得到物理地址；否则地址越界。
     • 保护键 (Protection Keys): (用于分区) 给每个分区和每个进程赋予一个键值，访问时匹配键值。
     • (分页/分段中的保护机制后续详述)
2. 连续分配 (Contiguous Allocation):
   • 概念: 为每个进程分配一块连续的物理内存区域。
   • 早期方案:
     • 单道程序: 内存只放OS和一个用户程序。
     • 固定分区 (Fixed Partition / Static Partition): 内存预先划分为若干固定大小的分区。分区大小可相等或不等。实现简单，但有内部碎片。
   • 动态分区 (Dynamic Partition):
     • 内存不预先划分，根据进程请求的大小动态地从空闲区域中分配。
     • 分配算法: (当有多个空闲分区满足要求时如何选择)
       • 首次适应 (First-Fit): 从头开始查找，选择第一个足够大的空闲分区。简单快速，但易在低地址产生小碎片。
       • 下次适应 (Next-Fit): 从上次查找结束的位置开始查找。减少低地址碎片的查找开销，但可能缺乏大空闲块。
       • 最佳适应 (Best-Fit): 查找所有空闲分区，选择大小与请求最接近（最小且足够大）的那个。试图减少大块被分割，但易产生大量无法利用的极小碎片。
       • 最差适应 (Worst-Fit): 查找所有空闲分区，选择最大的那个。试图保留更多中小空闲块，但可能导致大块迅速耗尽。
     • 空闲空间管理: 如何记录空闲分区？
       • 位图 (Bitmap): 内存划分成小单元，用一位表示单元是否空闲。简单，但查找连续空间可能较慢。
       • 空闲链表 (Free List): 将所有空闲分区链接起来，记录起始地址和大小。分配和回收时需要维护链表。
   • 碎片 (Fragmentation) 问题:
     • 内部碎片 (Internal Fragmentation): 分配的内存区域大于进程实际所需，区域内部未被使用的部分。固定分区和分页都有此问题。
     • 外部碎片 (External Fragmentation): 内存中存在足够多的空闲空间，但它们不连续，无法满足较大进程的连续内存请求。动态分区的主要问题。
   • 紧凑 (Compaction): 解决外部碎片的方法。通过移动内存中的进程，使所有空闲空间合并成一整块。开销很大，需要动态重定位支持。
   • 伙伴系统 (Buddy System):
     • 介于固定分区和动态分区之间。将可用内存按2的幂次大小进行管理。
     • 分配: 查找大小合适的空闲块，若没有则分裂更大的块（伙伴块一分为二）直到找到合适大小。
     • 回收: 回收块时检查其伙伴是否也空闲，若是则合并成更大的块，递归进行。
     • 优点: 分配回收较快，一定程度上减少外部碎片。
     • 缺点: 存在内部碎片（因为只能分配2的幂次大小）。Linux 内核中使用。
   • 覆盖 (Overlay) 与 交换 (Swapping):
     • 覆盖: 早期用于小内存运行大程序的技术。程序员手动将程序划分为相互覆盖的段，只将需要的段调入内存。对用户不透明。
     • 交换: 将暂时不运行的整个进程从内存移到外存（磁盘），腾出空间给其他进程。需要时再换回内存。由OS管理。
3. 分页 (Paging):
   • 基本思想:
     • 将物理内存划分为大小固定的块，称为页框 (Frame / Page Frame)。
     • 将逻辑地址空间也划分为相同大小的块，称为页 (Page)。
     • 通过页表 (Page Table) 建立页到页框的映射关系。
     • 进程的页可以非连续地存放在物理内存的任何可用页框中。
   • 机制:
     • 页 (Page): 逻辑地址空间的基本单位。
     • 页框 (Frame): 物理内存的基本单位，大小与页相同。
     • 页表 (Page Table): 每个进程一张页表，存放在内存中。记录该进程每个逻辑页对应的物理页框号。
     • 页表项 (Page Table Entry, PTE): 页表中的每个条目，包含页框号和其他控制位。
   • 地址转换过程:
     • CPU 生成逻辑地址，分为页号 (p) 和页内偏移 (d)。逻辑地址 = p | d
     • 硬件使用页号 p 作为索引在进程的页表中查找对应的页表项 (PTE)。页表的基地址由页表基址寄存器 (PTBR) 指向。
     • 从 PTE 中获取物理页框号 (f)。
     • 将页框号 f 和页内偏移 d 拼接成物理地址。物理地址 = f | d
     • 检查: 地址转换过程中需要检查页号是否越界（与页表长度寄存器 PTLR 比较），以及访问权限（PTE中的保护位）。
   • 页表项 (PTE) 内容:
     • 页框号 (Frame Number): 核心内容，指向物理内存块。
     • 有效位/存在位 (Valid/Present Bit): 标记该逻辑页是否在物理内存中（是否已加载/映射）。用于支持虚拟内存。
     • 保护位 (Protection Bits): 控制对该页的访问权限，如只读 (Read-Only)、读写 (Read/Write)、可执行 (Execute)。
     • 脏位/修改位 (Dirty/Modified Bit): 标记该页内容是否被修改过。用于页面换出时判断是否需要写回磁盘。
     • 访问位/引用位 (Accessed/Referenced Bit): 标记该页是否被访问过。用于页面置换算法（如LRU）。
     • 其他控制位: 如禁止缓存 (Cache Disabled)、全局页 (Global Page, TLB中不清空) 等。
   • 页面大小 (Page Size):
     • 由硬件决定，通常是 2 的幂次方（如 4KB, 2MB, 1GB）。
     • 小页面: 减少内部碎片，但页表更大，页表访问开销可能增加。
     • 大页面: 减少页表大小和TLB未命中率，但内部碎片可能更严重。
   • 共享页 (Shared Pages):
     • 允许多个进程的页表项指向同一个物理页框。
     • 常用于共享代码（如共享库、编译器）或只读数据。
     • 共享代码必须是可重入 (Reentrant / Pure Code) 的，即代码本身在执行过程中不被修改。
     • 写时复制 (Copy-on-Write, CoW) 可用于共享可写页面（如 fork() 时）。
4. 页表结构:
   • 问题: 对于大的逻辑地址空间（如32位或64位），单级页表本身可能非常大，占用大量连续内存。
   • 快表 (Translation Lookaside Buffer, TLB):
     • 定义: CPU 内部或旁边的一个高速、小的、由硬件管理的页表缓存，存储近期访问过的页表项（(页号, 页框号) 对）。
     • 工作流程: CPU生成逻辑地址 -> 先查TLB:
       • 命中 (TLB Hit): 直接从TLB获取页框号，快速形成物理地址。
       • 未命中 (TLB Miss): 需要访问内存中的页表，查到PTE后，将其加载到TLB中（可能替换旧条目），再形成物理地址。
     • 作用: 大大减少平均内存访问时间，因为大多数访存会命中TLB。
     • 有效访问时间 (EAT): EAT = HitRate * (TLBAccessTime + MemoryAccessTime) + MissRate * (TLBAccessTime + PageTableAccessTime + MemoryAccessTime)。
     • ASID (Address-Space Identifier): TLB条目中可以包含进程标识符，避免上下文切换时清空整个TLB。
   • 多级页表 (Hierarchical / Multi-Level Paging):
     • 思想: 将巨大的单级页表进行分页，即把页表本身也存储在页面中。
     • 结构 (以二级为例): 逻辑地址分为三部分：外层页号 (p1) | 内层页号 (p2) | 页内偏移 (d)。p1 用于索引外层页表（页目录 Page Directory），找到对应内层页表的物理地址（页框号）；p2 用于索引该内层页表，找到数据页的物理页框号 f；最后 f | d 得到物理地址。
     • 优点: 只有实际使用到的内层页表才需要分配内存，大大节省了存储页表的空间，尤其是在地址空间稀疏使用时。
     • 缺点: 每次地址转换需要多次访存（二级页表需两次访存查页表，三级需三次...），增加了内存访问延迟（TLB可以缓解此问题）。
   • 哈希页表 (Hashed Page Table):
     • 常用于处理大于32位的地址空间。
     • 将逻辑页号通过哈希函数映射到哈希表的一个桶 (bucket)。
     • 每个桶包含一个链表，存储 (逻辑页号, 页框号, 指针) 形式的元素。
     • 地址转换时，计算哈希值找到桶，然后遍历链表查找匹配的逻辑页号。
   • 反向页表 (Inverted Page Table):
     • 思想: 系统中只有一张页表，表的大小与物理内存页框数成正比，而不是与所有进程的逻辑地址空间总和成正比。
     • 结构: 每个页表项对应一个物理页框，存储 (进程ID (pid), 逻辑页号 (p))。
     • 地址转换: 给定逻辑地址 (pid, p, d)，需要在整个反向页表中搜索 (pid, p) 对，找到其索引 i，则 i 就是物理页框号。搜索通常通过哈希表加速。
     • 优点: 极大节省了存储页表的空间，尤其是在逻辑地址空间远大于物理内存时。
     • 缺点: 地址转换需要搜索（即使有哈希表，也比直接索引慢），实现内存共享困难（因为一个物理页框只能映射到一个 (pid, p)）。
5. 分段 (Segmentation):
   • 基本概念:
     • 将程序的地址空间划分为若干逻辑意义上的段 (Segment)，如代码段、数据段、堆栈段等。
     • 段的大小不定，由程序的逻辑结构决定。
     • 地址空间是二维的：(段号 (s), 段内偏移 (d))。
   • 机制:
     • 段表 (Segment Table): 每个进程一张段表，存放在内存中。
     • 段表项 (Segment Descriptor): 段表中的条目，包含：
       • 段基址 (Base Address): 该段在物理内存中的起始地址。
       • 段限长 (Limit): 该段的大小/长度。
       • 保护位 (Protection Bits): 如读/写/执行权限、特权级等。
     • 段表寄存器: 存放当前进程段表的基地址和长度。
   • 地址转换:
     • CPU生成逻辑地址 (s, d)。
     • 硬件使用段号 s 查找段表，获取段表项。
     • 检查段号 s 是否越界（与段表长度比较）。
     • 检查段内偏移 d 是否越界（d < limit ?）。
     • 检查访问权限。
     • 若检查通过，物理地址 = 段基址 + 段内偏移 d。
   • 优点:
     • 方便编程、信息共享（以逻辑段为单位共享）、信息保护（以段为单位设置权限）。
     • 支持动态增长（段可以动态改变大小）。
     • 支持动态链接。
   • 缺点:
     • 外部碎片: 动态分配和回收不定长的段会导致内存中产生许多不连续的小空闲块。需要使用连续分配的策略（FF, BF, WF）和可能的紧凑操作。
     • 内存分配复杂。
   • 分页与分段比较:
     • 用户视图: 段是用户可见的逻辑单位，页对用户透明。
     • 地址空间: 段是二维，页是一维。
     • 大小: 段大小不定，页大小固定。
     • 基本单位: 段是信息逻辑单位，页是物理单位。
     • 碎片: 段产生外部碎片，页产生内部碎片。
     • 共享/保护: 段更方便实现逻辑共享和保护。
6. 段页式 (Segmented Paging):
   • 思想: 结合分段和分页的优点。先将程序按逻辑结构分段，再将每个段分页。
   • 地址结构: 逻辑地址包含三部分：段号 (s) | 段内页号 (p) | 页内偏移 (d)。
   • 数据结构:
     • 每个进程一张段表。段表项包含该段对应的页表的基地址和页表长度。
     • 每个段一张页表。页表项包含物理页框号和控制位。
   • 地址转换过程:
     • 用段号 s 查段表，得到对应段的页表基地址。
     • 用段内页号 p 查该段的页表，得到物理页框号 f。
     • 物理地址 = f | d。
     • 需要进行段号越界、页号越界和权限检查。
     • 访存次数: 需要访问三次内存（段表、页表、实际数据），通常使用TLB加速。
   • 优点: 兼具分段（逻辑结构清晰、便于共享保护）和分页（无外部碎片、内存分配简单）的优点。
   • 缺点: 系统开销更大（需要更多硬件支持、地址转换更复杂、需要更多存储空间存放段表和页表）。
   • X86 实例: X86架构（尤其32位保护模式）是段页式管理的典型例子。逻辑地址（由段选择子+偏移组成）-> 通过段描述符（GDT/LDT）和段寄存器 -> 线性地址 -> 通过页目录和页表（CR3寄存器指向页目录）-> 物理地址。Linux 等现代 OS 在 x86-64 上通常采用“扁平模式”，将段基址设为0，限长设为最大，主要依赖分页进行内存管理和保护。

七、虚拟内存

1. 核心概念： 允许逻辑地址空间大于物理地址空间、请求调页（Demand Paging）。
2. 请求调页： 仅在需要时才加载页面。
3. 缺页处理（Page Fault Handling）：
   • 检测（通过无效PTE）。
   • 操作系统陷阱（trap）处理程序步骤。
   • 需要重新执行导致缺页的指令。
   • 操作系统 vs. 用户进程的角色。
4. 页面置换算法：
   • 目标：最小化缺页中断次数。
   • 算法：FIFO（先进先出）、LRU（最近最少使用）、OPT（Optimal，理想最优）、二次机会/Clock算法、Aging（LRU近似）、工作集（Working Set）、WSClock。
   • 算法特性：性能比较（LRU/OPT 通常优于 FIFO）、Belady 异常（FIFO 可能出现）。
5. 性能问题：
   • 抖动/颠簸（Thrashing）：原因（过度的页面换入换出）、检测、解决方法（降低多道程序度、检查工作集大小）。
   • 局部性原理（时间和空间局部性）是虚拟内存有效工作的基础。
6. 写时复制（Copy-on-Write, CoW）： fork() 的优化策略，延迟页面的复制直到有写入操作发生。

---

• ← Previous Post
• Next Post →

---

---