操作系统复习
🧠 Chapter 1 Introduction - 操作系统导论笔记
一、什么是操作系统 (What is an OS?)
📌 1. 操作系统的两个基本定义：
- It is an extended machine（它是扩展机器）
- 为用户提供更简单、更抽象的接口（如文件而不是磁盘块，进程而不是物理CPU）
- 屏蔽硬件复杂性，提供虚拟机接口
- It is a resource manager（它是资源管理器）
- 管理硬件资源（如 CPU、内存、I/O 设备）
- 分配资源、调度任务，提高资源利用率
二、操作系统的发展历史 (History of Operating Systems)
📅 1. 第一代：无操作系统（1940s~1950s）
- 使用打孔卡或纸带
- 人工操作，只有裸机（bare machine）
📅 2. 第二代：批处理系统（Batch System，1950s~1960s）
- 引入 批处理（Batch processing）
- 使用 作业控制语言 JCL
- 有简单操作系统支持，自动运行作业
📅 3. 第三代：多道程序设计（Multiprogramming，1960s~1970s）
- 支持多个程序同时驻留内存，提高CPU利用率
- 引入：
- Spooling（假脱机技术）：I/O 排队，提高设备利用率
- Time-sharing（分时系统）：多个用户共享CPU，实现交互式使用
📅 4. 第四代：个人计算和网络操作系统（1980s~至今）
- 图形界面、多媒体、互联网
- 引入 分布式系统、移动系统、嵌入式系统等
三、操作系统的结构 (Operating System Structure)
🧱 1. Monolithic System（整体结构）
- 单块程序组成所有功能
- 所有模块运行在内核态（kernel mode）
- 优点：执行效率高
- 缺点：模块间耦合高，难于维护
🧱 2. Layered System（层次结构）
- 操作系统按功能分为多个层次
- 每一层只依赖于下一层，抽象良好
- 例子：THE系统、Multics
- 优点：结构清晰，易于调试
- 缺点：层次过多可能导致效率低
🧱 3. Microkernel（微内核结构）
- 只保留最基本的功能在内核（如进程间通信、基本调度）
- 其他服务（文件系统、驱动程序等）作为用户态服务器运行
- 优点：安全性高，模块独立性强
- 缺点：性能开销大
🧱 4. Client-Server Model（客户-服务器模型）
- 操作系统服务以服务器形式存在，用户进程作为客户端请求服务
- 通常基于微内核实现
- 典型应用：分布式操作系统、现代操作系统（如 Windows NT）
🧠 Chapter 2 Process - 操作系统中的进程（详细笔记）
一、Process Model（进程模型）
✅ 多道程序设计（Multiprogramming）& 并发（Concurrency）
- 多道程序设计：多个程序同时驻留内存，提高CPU利用率。
- 并发：多个进程“同时”执行，看起来同时进行，实际由调度器快速切换。
二、Process（进程）
✅ 定义
- 进程（Process）：一个正在执行的程序，是程序的运行实例。
✅ Program vs. Process
| 比较维度 |
Program（程序） |
Process（进程） |
| 性质 |
静态：指令集合 |
动态：执行中的实体 |
| 组成 |
只包含代码 |
包括程序、数据、临时状态、控制信息等 |
| 数量关系 |
一个程序可对应多个进程 |
一个进程可能调用多个程序 |
三、Process States（进程状态）
✅ 三种基本状态：
- Running：正在使用CPU
- Ready：已准备好执行，等待CPU
- Blocked（或 Waiting）：等待某事件（如I/O完成）
四、PCB（Process Control Block，进程控制块）
- 操作系统内核用于管理进程的 数据结构
- 每个进程一个 PCB，包含：
- 进程状态、程序计数器、寄存器、内存信息、I/O状态、优先级等
五、Process Context Switch（上下文切换）
- 当CPU从一个进程切换到另一个进程时，需要保存/恢复上下文（PCB）
- 由 调度器（scheduler） 负责完成
- 是 纯开销，通常耗时 1~1000ms，不产生直接产出
六、Process Creation & Termination（创建与终止）
✅ 创建方式：
- 系统初始化时
- 执行系统调用（如 Linux 的
fork()）
- 用户请求
- 批处理任务启动
✅ 终止方式：
| 方式 |
是否自愿 |
说明 |
| 正常退出 |
是 |
程序运行结束 |
| 出错退出 |
是 |
程序主动退出（如 return 错误） |
| 致命错误 |
否 |
运行中出现非法操作等崩溃 |
| 被其他进程杀死 |
否 |
例如通过 kill() 系统调用 |
七、Thread（线程）
✅ 定义：
- 一个进程内部的 执行流，又称“轻量级进程（Lightweight Process）”
- 同一进程的线程共享数据空间、打开的文件、信号等资源
✅ 优点：
- 创建/销毁成本低：比进程快 10~20 倍
- 切换快：线程间上下文切换比进程快 5~50 倍
- 更方便共享资源（不需拷贝）
✅ 缺点：
- 同一进程内线程 不互相保护，一个线程错误可能影响整个进程
八、Thread Model（线程模型）
✅ 实现方式：
| 模型 |
管理者 |
特点 |
| 用户级线程 |
应用层 |
上下文切换快，数量不限，但需自行协调调度 |
| 内核级线程 |
操作系统内核 |
调度由内核完成，更稳定但上下文切换较慢 |
| 混合模型 |
用户+内核 |
结合两者优点，多个用户线程映射到内核线程上 |
九、Process vs. Thread
| 比较维度 |
Process（进程） |
Thread（线程） |
| 拥有资源 |
是，独立资源单位 |
否，共享进程资源 |
| 创建开销 |
高 |
低 |
| 切换开销 |
高 |
低 |
| 独立性 |
高（互不干扰） |
低（共享地址空间） |
| 使用场景 |
多任务操作 |
并行处理、异步任务 |
十、IPC（进程间通信）
✅ 概念
- Race Condition（竞争条件）：多个进程并发访问共享资源，顺序不确定，可能导致错误。
- Critical Section（临界区）：访问共享资源的代码区域。
✅ 四个互斥要求：
- 互斥（Mutual Exclusion）
- 前进（Progress）
- 有界等待（Bounded Waiting）
- 不依赖速度（Independence of Speed）
十一、同步工具
✅ Semaphore（信号量） & PV 操作：
P(S)（等待） & V(S)（释放）- 可解决互斥和进程间同步问题
✅ 常见经典问题：
- 生产者-消费者问题
- 读者-写者问题
- 哲学家就餐问题
✅ Monitor（监视器）
- 高级同步机制：封装共享变量与操作
- 通过条件变量实现 wait/signal 控制访问
十二、Process Scheduling（进程调度）
✅ 触发调度时机：
- 有新进程创建
- 当前进程终止
- 当前进程阻塞
- I/O 中断（解锁某些阻塞进程）
- 时钟中断（如每 10ms）
✅ 调度目标：
十三、调度算法
✅ 批处理系统：
- FCFS（先来先服务）
- SJF（最短作业优先）（可抢占 / 非抢占）
✅ 交互式系统：
- Round Robin（时间片轮转）
- Priority Scheduling（优先级调度）
- 多级队列 & 多级反馈队列（MLQ / MFQ）
- Lottery Scheduling（彩票调度）
✅ 实时系统：
- 强调任务的 可调度性（schedulability），必须在截止时间前完成任务
大题隐藏其中！
✅ 大题 1：Program vs. Process（程序 vs. 进程）
问题示例（Exam Question）：
请比较程序（Program）与进程（Process）之间的区别，并举例说明它们的关系。
Compare and contrast a program and a process. Give examples to illustrate their relationship.
标准答案（Answer）：
| 比较维度 |
程序 Program |
进程 Process |
| 定义 Definition |
程序是指令和数据的静态集合。Program is a static set of instructions. |
进程是程序的执行实例，是动态活动。A process is a dynamic execution instance of a program. |
| 性质 Nature |
静态（Static） |
动态（Dynamic） |
| 组成 Components |
只包含代码。Contains only code. |
包括程序代码、数据段、堆栈、PCB 等。Includes code, data, stack, and PCB. |
| 并发 Concurrency |
程序本身不能并发执行。A program cannot run concurrently. |
多个进程可以并发执行同一个程序。Multiple processes can execute the same program concurrently. |
| 数量关系 Quantity Relation |
一个程序可以对应多个进程。One program can correspond to multiple processes. |
一个进程可调用多个程序。A process can invoke multiple programs. |
示例 Example：
例如，同一个“浏览器程序”可以被多个用户分别运行，产生多个独立的“浏览器进程”。
✅ 大题 2：Process vs. Thread（进程 vs. 线程）
问题示例（Exam Question）：
请简述进程（Process）与线程（Thread）之间的区别，说明它们在资源管理和执行效率方面的不同。
Explain the differences between a process and a thread, focusing on resource management and execution efficiency.
标准答案（Answer）：
| 比较维度 |
进程 Process |
线程 Thread |
| 定义 Definition |
资源分配的基本单位。Basic unit of resource allocation. |
程序执行的最小单位。Smallest unit of execution. |
| 资源 Resources |
每个进程有独立资源（地址空间、打开文件等）。Owns resources independently. |
线程共享进程的资源。Shares resources with other threads in the same process. |
| 独立性 Independence |
进程间独立，通信复杂。Independent; communication requires IPC. |
线程之间密切合作，通信简便。Cooperative; easy communication. |
| 开销 Overhead |
创建、切换开销大。Expensive to create/switch. |
创建、切换开销小。Cheaper to create/switch. |
| 崩溃影响 Failure Impact |
一个进程崩溃不影响其他进程。Crash isolated. |
一个线程崩溃可能影响整个进程。May crash the whole process. |
✅ 大题 3：User-level vs. Kernel-level Threads（用户级线程 vs. 内核级线程）
问题示例（Exam Question）：
比较用户级线程（User-level threads）和内核级线程（Kernel-level threads）的优缺点。
Compare user-level threads and kernel-level threads in terms of performance, resource usage, and implementation.
标准答案（Answer）：
| 比较维度 |
用户级线程（User-level Threads） |
内核级线程（Kernel-level Threads） |
| 管理者 Manager |
由应用程序或线程库管理。Managed by user-level libraries. |
由操作系统内核管理。Managed by the OS kernel. |
| 内核可见性 Kernel Awareness |
不可见，内核不知道其存在。Invisible to the kernel. |
可见，内核调度管理。Visible and scheduled by the kernel. |
| 上下文切换 Context Switching |
快速（不涉及内核）。Fast (no kernel involvement). |
慢（涉及内核态切换）。Slow (requires kernel mode switch). |
| 线程数量 Thread Count |
数量无限制。Virtually unlimited. |
受限于内核资源。Limited by system resources. |
| 阻塞影响 Blocking |
一个线程阻塞，整个进程阻塞。One blocked thread can block the entire process. |
支持真正并发，一个线程阻塞不会影响其他线程。Blocking one thread doesn’t block others. |
| 易用性 Usability |
实现复杂，需自行调度。Complex to implement. |
简单，调度由内核完成。Simpler to use. |
✅ Chapter 3 Memory Management 内存管理
📌 (1) Basic Memory Management 基本内存管理
● 静态重定位（Static Relocation）
- 在加载时完成地址调整，操作系统根据内存中的位置修改程序中的地址。
- 一旦加载完成，进程不能再移动。
● 动态重定位（Dynamic Relocation）
- 运行时将虚拟地址映射到物理地址。
- 借助硬件（如重定位寄存器 relocation register/base register）完成：
物理地址 = 虚拟地址 + 基址
- 支持进程在内存中的移动。
● 压缩（Compaction）
- 将分散的空闲内存合并，减少外部碎片。
- 代价高，涉及大量数据移动。
● 空闲空间管理（Free Space Management）
- 位图法（Bit Map）：每个单位内存对应一位，0/1 表示空闲/占用。
- 链表法（Linked List）：记录空闲块的起始位置和长度，形成空闲区链表。
📌 (2) Overlay, Swapping & Storage Placement 存储策略
● 覆盖技术（Overlay）
- 程序太大不能同时装入内存时，将程序划分成多个段，按需调入。
- 程序员或系统手动管理。
● 交换（Swapping）
- 将暂时不用的进程调出到磁盘，需要时再调入内存。
- 提高内存利用率。
● 存储分配策略（Storage Placement Strategy）
| 策略 |
说明 |
| First Fit |
找第一个足够大的空闲块。 |
| Next Fit |
从上次位置继续找第一个足够大的。 |
| Best Fit |
找最小但能容纳的块，可能产生碎片。 |
| Worst Fit |
找最大的块，尝试减少碎片，但可能浪费大块空间。 |
📌 (3) Paging 分页机制与页面置换
● 分页机制（Paging）
- 将内存分为固定大小的页帧，进程划分为相同大小的页。
- 地址转换：虚拟地址 = 页号 + 页内偏移
- 使用页表（Page Table）映射页号 → 帧号。
- 优化方式：TLB（Translation Lookaside Buffer）、多级页表、倒排页表（Inverted Page Table）
● 页面置换算法（Page Replacement Algorithms）
| 算法 |
说明 |
| Optimal |
理想最优，未来不再使用的页先换出。理论算法。 |
| FIFO |
先进先出，可能出现Belady 异常。 |
| Second Chance |
FIFO 改进，加引用位。 |
| NRU（Not Recently Used） |
分类替换，不活跃页优先。 |
| Clock（时钟） |
Second chance 的实现优化。 |
| LRU |
最近最少使用，近似未来最优。 |
| NFU |
从未使用，按时间累加引用次数。 |
| Aging |
LRU 的近似实现，使用位移老化法。 |
● 工作集（Working Set）
- 当前“活跃”页集合，即进程当前需要的页面集合。
- 避免抖动（Thrashing）的一种方法。
● 抖动（Thrashing）
- 系统频繁产生页面置换，实际工作效率低。
- 原因：工作集太大，物理页数不足。
- 解决：工作集模型、调整多道程度、增加内存。
📌 (4) 分页设计细节与段式管理
● 页面调入策略（Fetching Policies）
| 策略 |
说明 |
| Demand Paging |
按需调页，缺页时才加载，节省内存。 |
| Pre-paging |
预取页面，提前加载，可能浪费资源。 |
● 设计问题（Design Issues for Paging）
- 驻留集管理（Resident Set Management）：限制每个进程可用的页数。
- 页大小（Page Size）：大页减少页表项，小页减少内部碎片。
- 共享页（Shared Pages）：多个进程共享代码段（如库函数）。
- 写时复制（Copy-on-Write）：父子进程共享页，直到某一方修改。
● 段式管理（Segmentation）
- 内存按逻辑模块（段）划分，如代码段、数据段、堆栈段。
- 地址结构 = 段号 + 段内偏移
- 优点：逻辑清晰，便于保护和共享。
- 缺点：外部碎片严重。
● 段页式结合（Segmentation with Paging）
- 每个段再分页，结合两者优点。
- 地址 = 段号 + 页号 + 页内偏移
- 灵活性更强，但实现更复杂。
✅ Chapter 4 File System 文件系统
📌 (1) 文件与文件系统基础
● 文件（File）
A named collection of related information that is recorded on secondary storage.
● 文件系统（File System）
A method for storing and organizing files and their data to make it easy to find and access.
- 提供一种存储与组织文件及数据的方法，方便查找与访问。
● 文件系统的基本功能（Basic Functions）
- 提供文件与目录的逻辑视图
- 提高存储设备的使用效率
- 支持文件共享
● 文件类型（File Types）
| 类型 |
说明 |
| Regular File |
普通文件，包含文本（ASCII）或二进制（Binary） |
| Directory |
目录文件，包含文件名与指针 |
| Character Special File |
字符设备，如终端、键盘 |
| Block Special File |
块设备，如硬盘、U盘 |
📌 (2) 目录结构与文件存储方式
● 目录结构（Directory Structure）
| 类型 |
说明 |
| One-level |
所有文件在同一目录下，容易冲突 |
| Two-level |
每个用户一个独立目录，支持多用户 |
| Hierarchical |
多层次树形结构，最常见 |
● 文件系统布局（File System Layout）
见图 4-9（通常包括以下几个部分）：
- Boot Block：用于引导操作系统
- Super Block：存储整个文件系统的元信息
- i-Node Table、Data Blocks 等
● 文件存储实现（File Storage Implementation）
| 方法 |
说明 |
| Contiguous Allocation |
连续分配，访问快但易碎片化 |
| Linked List Allocation / FAT |
每个文件块存指针，FAT 表统一管理 |
| Indexed Allocation (i-node) |
使用索引结构（如 i-node）记录所有数据块地址，灵活高效 |
📌 (3) 文件共享与磁盘管理
● 文件共享（Shared Files）
| 方法 |
说明 |
| Hard Link |
不创建新文件，多个文件名指向同一个 i-node |
| Symbolic Link |
创建新文件，记录目标文件的路径，类似快捷方式 |
● 磁盘空间管理（Disk Space Management）
- 块大小（Block Size）：影响内部碎片与读写效率
- 空闲块管理（Free Block Tracking）：
- Linked List：每个空闲块记录下一个
- Bit Map：位图记录空闲与占用状态
● 文件系统备份（File System Backup）
- 逻辑转储（Logical Dump）：按照目录树结构进行备份，按逻辑层级遍历
📌 (4) 一致性与性能优化
● 文件系统一致性（Consistency）
- 检查 块完整性（block）与 目录结构完整性（directory）
| 技术 |
说明 |
| Caching |
使用缓存，减少磁盘 I/O |
| Block Read Ahead |
预读连续数据块，提高命中率 |
| Reducing Disk Arm Motion |
减少磁头移动，提高读写效率 |
📌 (5) 文件系统实例：MS-DOS 与 UNIX
● MS-DOS 文件系统
| 项目 |
说明 |
| 目录结构 |
简单的层次结构 |
| FAT 类型 |
FAT12、FAT16、FAT32，不同于块大小与寻址范围 |
● UNIX V7 文件系统
| 项目 |
说明 |
| i-node |
文件的索引节点，记录元数据与块地址 |
| 目录 |
实质是包含文件名与 i-node 编号的表 |
📌 (1) I/O 软件的目标（Goals of I/O Software）
| 目标 |
说明（中英文对照） |
| Device Independence |
设备无关性：程序无需知道具体硬件 |
| Uniform Naming |
统一命名：不依赖硬件，例如 /dev/sda1 |
| Error Handling |
错误处理：统一处理 I/O 异常情况 |
| Synchronous vs. Asynchronous |
同步与异步传输：同步等待 vs 异步通知 |
| Buffering |
缓冲处理：提高效率，解决速度差异问题 |
| Sharable vs. Dedicated Devices |
共享 vs 专用设备：例如打印机为专用，磁盘可共享 |
📌 (2) I/O 软件的基本方式（Principles of I/O Software）
| 类型 |
说明 |
| Programmed I/O（程序控制 I/O） |
CPU 主动读取设备状态，效率低 |
| Interrupt-driven I/O（中断驱动 I/O） |
设备完成后中断通知 CPU，CPU 被动响应 |
| DMA（Direct Memory Access） |
直接内存访问，数据由设备直达内存，不经 CPU，提高效率 |
📌 (3) I/O 软件的层次结构（I/O Software Layers）
● Interrupt Handlers（中断处理程序）
● Device Drivers（设备驱动程序）
- 从上层接收抽象读写命令，转换为设备操作。
- 职责包括：
- 执行具体设备指令
- 设备初始化与电源管理
- 请求调度（如磁盘调度）
- 记录设备事件
📌 (4) I/O 软件的更高层（continued）
● Device-Independent OS Software（设备无关的操作系统软件）
| 功能 |
说明 |
| Uniform interface |
提供统一接口给设备驱动 |
| Buffering |
数据缓存，减小访问延迟 |
| Error Reporting |
向用户报告设备错误 |
| Device Allocation |
分配/释放专用设备 |
| Block Size Abstraction |
提供统一块大小接口（隐藏设备差异） |
● User-Level I/O Software（用户层 I/O 软件）
- 如库函数
fread(), fwrite()，封装系统调用，提供易用 API。
📌 (5) 磁盘调度与优化（Disk I/O）
● 磁盘技术概念
| 名称 |
说明 |
| Cylinder Skew |
柱面偏移，防止跨柱面数据读取时错过扇区 |
| Sector Interleaving |
扇区交错，用于避免 CPU 跟不上数据传输速度 |
● 磁盘调度算法（Disk Arm Scheduling）
| 算法 |
中文说明 |
特点 |
| FCFS |
先来先服务 |
简单但效率低 |
| SSF（SSTF） |
最短寻道时间优先 |
提高性能但可能饥饿 |
| Elevator (SCAN) |
电梯算法 |
磁头来回移动，公平性好 |
✅ Chapter 6: Deadlock（死锁）
📌 (1) 死锁基本概念
🔹 Deadlock（死锁）定义
一组进程因相互等待而永远阻塞，且不会主动释放资源。
🔹 Livelock（活锁）
虽然进程在“运行”，但始终改变状态以避免冲突，却永远无法前进（例：两个进程不断让对方先走）。
🔹 Starvation（饥饿）
某个进程长时间得不到资源，被“饿死”，虽然系统仍运行。
📌 死锁产生的四个必要条件（Conditions for Deadlock）
| 条件 |
英文 |
说明 |
| 互斥 |
Mutual Exclusion |
资源一次只能被一个进程占用 |
| 占有且等待 |
Hold and Wait |
占有资源的进程还能请求其他资源 |
| 非抢占 |
No Preemption |
资源不能被强制抢占，只能自愿释放 |
| 循环等待 |
Circular Wait |
存在一组进程 {P1, P2, …, Pn}，每个等待下一个的资源形成环 |
📌 (2) 死锁处理方法（Methods for Handling Deadlock）
✅ 1. 死锁检测（Detection）
情况一：每类资源仅一个实例（Single Resource）
- 资源分配图（Resource Allocation Graph）检测是否有循环。
情况二：每类资源多个实例（Multiple Resources）
- 使用死锁检测算法，如银行家算法检测法，计算是否存在不满足资源请求的进程集合。
✅ 2. 死锁恢复（Recovery）
| 方法 |
中文解释 |
| 资源抢占 |
暂停某进程并回收其资源，需保存进程状态以便重启 |
| 回滚（Rollback） |
进程回退到某个安全点重新执行（需支持事务） |
| 杀死进程 |
选择一个或多个进程终止，释放其资源以解除死锁 |
✅ 3. 死锁避免（Avoidance）
🔹 安全状态（Safe State）
- 存在一个进程序列，所有进程都能顺序完成，不会陷入死锁。
🔹 银行家算法（Banker’s Algorithm）
- 类似“贷款银行”，资源只有在确保系统仍安全的前提下才会分配。
📌 (3) 死锁预防（Prevention）
通过破坏死锁四个必要条件之一来防止死锁：
| 条件 |
预防方法 |
| 互斥 |
采用可共享资源（如只读文件） |
| 占有且等待 |
要求进程一次性请求全部资源或在请求前释放全部已有资源 |
| 非抢占 |
允许抢占资源（中断进程并回收其资源） |
| 循环等待 |
给资源编号，按编号顺序请求资源，防止形成环 |
