三态模型：**就绪**（已获除CPU外所有资源，等待调度）、**运行**（正在CPU执行）、**阻塞**（等待某事件如I/O完成，主动放弃CPU）
🔹进程与线程
- 进程是资源分配的基本单位，拥有独立地址空间；线程是CPU调度的基本单位，同一进程内线程共享代码段、数据段和打开文件等资源，但有独立栈和寄存器上下文。
- 线程切换开销远小于进程切换（无需TLB刷新、页表切换等）。
🔹PCB（进程控制块）
- 操作系统感知进程的唯一数据结构，包含：进程ID、状态、程序计数器、CPU寄存器、内存管理信息（页表基址）、优先级、记账信息、I/O状态（打开文件列表、等待事件等）。
🔹进程状态
- 三态模型：就绪（已获除CPU外所有资源，等待调度）、运行（正在CPU执行）、阻塞（等待某事件如I/O完成，主动放弃CPU）。
- 扩展五态含新建（New）和终止（Terminated）；Linux中还有不可中断睡眠（D）、僵尸（Z）等状态。
🔹进程调度算法
| 算法 | 特点 | 缺陷 |
|---|---|---|
| FCFS | 简单公平，非抢占 | 平均等待时间长，存在“护航效应” |
| SJF（非抢占/抢占→SRTF） | 最小平均等待时间（最优） | 需预知运行时间，易导致长作业饥饿 |
| RR（时间片轮转） | 响应及时，公平 | 时间片过小→频繁上下文切换；过大→退化为FCFS |
| 优先级调度 | 支持实时/交互/批处理混合负载 | 可能饥饿（低优先级永远不执行），需老化（Aging）机制 |
🔹死锁
- 四个必要条件（缺一不可）：互斥、占有并等待、非抢占、循环等待。
- 银行家算法：安全性检测算法（基于资源最大需求与当前分配），属死锁避免策略；需预先声明最大资源需求，不适用于动态申请场景。
🔹内存管理
- 分页：逻辑地址→页号+页内偏移；物理地址→帧号+页内偏移；消除外部碎片，引入内部碎片与页表开销。
- 分段：按逻辑模块（主程序、栈、堆、数据段）划分，支持共享与保护，但产生外部碎片。
- 段页式：先分段再分页，结合二者优点（逻辑清晰 + 无外部碎片），地址变换需查段表+页表（二级甚至多级）。
🔹虚拟内存
- 核心思想：以磁盘为扩展内存，仅将活跃页装入物理内存，通过局部性原理实现高效运行。
- 关键机制：请求调页（Demand Paging）、写时复制（Copy-on-Write）、页表项中的有效位/修改位/访问位。
🔹页面置换算法
| 算法 | 特点 | 实现难度 |
|---|---|---|
| FIFO | 简单，用队列实现 | Belady异常（增加页框数反而缺页率上升） |
| OPT（最优） | 理论下限，替换最久不用页 | 不可实现（需预知未来） |
| LRU | 近似OPT，替换最久未使用页 | 硬件支持（如访问位+定时清零扫描）或软件近似（Clock算法） |
🔹文件系统
- FAT（File Allocation Table）：以链式索引（簇号链）管理磁盘块，简单高效，但不支持权限、硬链接、日志；FAT32支持最大4GB单文件。
- NTFS（Windows）：支持ACL权限、加密（EFS）、压缩、日志（$LogFile）、硬/软链接、稀疏文件、事务语义（TxF）。
- inode（Unix/Linux）：每个文件唯一inode号，存储元数据（权限、所有者、大小、时间戳、块指针）；目录本质是“文件名→inode号”的映射表；支持硬链接（同inode）、软链接（独立inode，存路径字符串）。
🔹磁盘调度算法
| 算法 | 特点 | 问题 |
|---|---|---|
| SSTF | 类似SJF，选最近柱面 | 可能饥饿（远离当前磁头的请求长期等待） |
| SCAN（电梯算法） | 往复扫描，双向服务 | 中间区域响应较好，两端延迟高 |
| C-SCAN | 单向扫描至端点后立即返回起点（空载），更均匀 | 吞吐量略低于SCAN，但响应更公平 |
# 示例：LRU缓存（基于OrderedDict实现，O(1) get/put）fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.cache=OrderedDict()self.capacity=capacitydefget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)# 移至末尾表示最近使用returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)# 弹出最久未用（头部）