操作系统与数据结构核心知识点解析

操作系统与数据结构核心知识点解析
课程摘要
本文详细解析了操作系统和数据结构的核心知识点，包括操作系统的基本概念、内核与用户模式、中断异常、系统调用、引导过程，以及操作系统的目标和功能。同时，也深入讲解了进程与线程的引入、状态与切换、CPU调度、同步与互斥等关键概念。此外，还涉及了内存管理的概念、连续分配与非连续分配方式、虚拟内存技术、文件管理的目录操作、逻辑结构与物理结构，以及数据结构中的压缩矩阵、二叉树、二叉排序树、图存储结构与算法等。通过这些内容的讲解，帮助读者全面理解并掌握操作系统和数据结构的核心知识。
分段知识点总结
操作系统核心知识点精讲
一、操作系统基本概念
1.1 定义与特征
操作系统的定义是管理计算机硬件与软件资源的系统软件。其核心特征包括：
并发性：多个任务在宏观上同时执行
共享性：
互斥共享（如打印机）
同时访问（如只读文件）
虚拟性：通过技术手段扩展物理资源能力
异步性：程序执行顺序和速度不可预知
注：并发与并行的区别在于并发是逻辑上的同时执行，而并行是物理上的同时执行。
1.2 目标与功能
功能模块 管理对象 对应章节
处理机管理 CPU资源 进程与线程
存储器管理 内存资源 内存管理
文件管理 文件系统 文件管理
设备管理 I/O设备 I/O设备管理
graph LRA[操作系统功能] --> B[处理机管理]A --> C[存储器管理]A --> D[文件管理]A --> E[设备管理]
1.3 接口类型
命令接口：
联机命令接口（交互式）
脱机命令接口（批处理）
程序接口：系统调用（如API）
二、操作系统运行环境
2.1 特权指令与模式切换
特权指令：仅在内核态执行的指令（如I/O操作）
模式切换：
用户态→内核态：通过trap指令触发中断
内核态→用户态：通过IRET指令返回
2.2 中断与异常
类型 触发源 特点
外中断 外部设备 异步发生
内中断 CPU内部 同步发生
异常 程序错误 不可屏蔽
原语操作：具有原子性，执行过程不可中断（如信号量操作）
2.3 系统调用机制
系统调用执行流程：
用户程序执行trap指令
切换到内核态并保存现场
查找系统调用表执行服务例程
返回用户态并恢复现场
三、进程与线程管理
3.1 进程定义与特征
进程是程序的一次执行过程，核心特征：
动态性：有生命周期
并发性：多个进程可同时存在
独立性：资源分配基本单位
异步性：执行速度不可预知
3.2 进程状态转换
graph LRA[创建] --> B[就绪]B --> C[运行]C --> D[阻塞]D --> BC --> E[终止]C -->|时间片用完| B
状态转换触发条件：
运行→阻塞：主动请求资源（如I/O操作）
阻塞→就绪：被动由操作系统唤醒
运行→就绪：时间片用完被抢占
3.3 进程控制块（PCB）
PCB包含的核心信息：
进程标识符（PID）
进程状态（运行/就绪/阻塞）
程序计数器（PC值）
寄存器集合
内存分配信息
I/O状态信息
真题示例（行号70）：在PCB中存储进程调度所需的信息主要是处理机状态信息（寄存器值、PC指针等）。
3.4 进程通信方式
共享存储：建立共享内存区域
消息传递：
直接通信（发送到接收方队列）
间接通信（通过信箱中转）
管道通信：
匿名管道（单向传输）
命名管道（支持双向）
3.5 线程模型比较
对比项 进程 线程
资源分配 CPU资源基本单位 不拥有资源
地址空间 独立地址空间 共享进程地址空间
切换开销 大（需切换页表） 小（仅切换PC和寄存器）
并发性 进程间并发 线程间更高并发
关键结论：引入线程后，进程仍是CPU资源分配的基本单位。
四、处理机调度
4.1 三级调度体系
调度级别 发生位置 状态转换 功能
作业调度 外存→内存 后备→就绪 选择作业装入内存
中级调度 外存↔内存 挂起↔就绪 内存资源平衡
进程调度 内存→CPU 就绪→运行 分配CPU时间片
4.2 调度算法对比
算法名称 抢占性 优点 缺点
FCFS 非抢占 实现简单 长作业等待时间长
SJF 可抢占 平均等待时间最小 可能饥饿
优先级调度 可选 满足紧急任务 低优先级可能饥饿
时间片轮转 抢占 公平响应快 上下文切换开销大
多级反馈队列 抢占 兼顾长短作业 实现复杂
4.3 调度性能指标
CPU利用率 =“CPU有效工作时间” /“总时间”
吞吐量：单位时间完成作业数
周转时间 = 作业完成时间 - 提交时间
带权周转时间 =“周转时间” /“实际运行时间”
五、同步与互斥
5.1 基本概念
graph TBA[临界资源] --> B[互斥访问]C[进程同步] --> D[直接制约关系]
同步机制四大原则：
空闲让进
忙则等待
有限等待
让权等待
5.2 信号量机制
记录型信号量操作原理：
P(S){ S.value–;if(S.value <0){ 加入等待队列; 阻塞当前进程;}}V(S){ S.value++;if(S.value <=0){ 从队列移出一个进程; 唤醒该进程;}}
PV操作必须成对出现：同步操作遵循”前V后P”原则（前驱操作完成后执行V，后继操作前执行P）
5.3 经典同步问题
生产者-消费者问题
共享变量：
缓冲区buffer[n]
信号量mutex=1（缓冲区互斥）
empty=n（空缓冲区数）
full=0（满缓冲区数）
哲学家进餐问题
解决方案：
限制最多4人同时就餐
奇数号先取左叉再取右叉
使用AND型信号量
六、死锁处理
6.1 死锁条件与处理策略
必要条件：
互斥条件
请求和保持
不可抢占
循环等待
处理策略对比：
策略 实施时机 典型方法
死锁预防 事前 破坏必要条件
死锁避免 事中 银行家算法
死锁检测 事后 资源分配图化简
死锁解除 检测后 资源剥夺/进程终止
6.2 银行家算法
安全状态判断步骤：
计算Need矩阵（Need=Max-Allocation）
查找Need≤Work的进程
假设分配并更新Work=Work+Allocation
重复步骤2-3直到所有进程完成
重要结论：安全状态一定不会死锁，不安全状态不必然导致死锁
七、内存管理
7.1 连续分配方式
分配方式 碎片类型 特点
单一连续 内部碎片 系统区/用户区划分
固定分区 内部碎片 分区大小预先设定
动态分区 外部碎片 分区大小动态可变
动态分区分配算法：
首次适应（FF）：从低地址开始查找
最佳适应（BF）：选择最小合适分区
最坏适应（WF）：选择最大合适分区
邻近适应（NF）：从上次结束位置开始
7.2 分页存储管理
地址变换过程：
逻辑地址 → 页号|页内偏移 ↓查询页表 → 物理块号 ↓物理地址 = 块号|页内偏移
多级页表示例（二级页表）：
逻辑地址 → 页目录号|页表号|页内偏移 ↓查询页目录 → 页表起始地址 ↓查询页表 → 物理块号 ↓物理地址 = 块号|页内偏移
7.3 页面置换算法
算法名称 特点 可能问题
OPT 淘汰最远将访问页 理想不可实现
FIFO 淘汰最先进入页 Belady异常
LRU 淘汰最久未使用页 开销大
CLOCK 环形链表+访问位 改进FIFO
缺页率计算：$=% $
八、文件系统管理
8.1 文件物理结构
结构类型 随机访问 文件扩展 典型应用
连续分配 支持 困难 CD-ROM
链接分配 不支持 容易 FAT文件系统
索引分配 支持 容易 UNIX文件系统
FAT表示例：
簇号 下一簇指针
0 EOF
1 3
2 4
3 2
4 1
8.2 文件目录结构
graph TDA[根目录] --> B[用户目录1]A --> C[用户目录2]B --> D[文件A]B --> E[文件B]C --> F[子目录]F --> G[文件C]
8.3 磁盘调度算法
算法名称 寻道特点 可能问题
FCFS 按请求顺序服务 效率低
SSTF 选择最近磁道 可能饥饿
SCAN 磁头单向移动到底 无饥饿
C-SCAN 单向移动且直接回起点 公平性更好
九、I/O设备管理
9.1 I/O软件层次
graph BTA[用户进程] --> B[设备独立性软件]B --> C[设备驱动程序]C --> D[中断处理程序]D --> E[硬件设备]
9.2 缓冲区技术
缓冲区类型对比：
类型 缓冲区数量 特点
单缓冲 1 T=max(C,M)+T
双缓冲 2 T=max(C,T)
循环缓冲 多个 组成缓冲池
缓冲池 共享池 动态分配缓冲区
公式说明：C=计算时间，M=传输入缓冲时间，T=传出缓冲时间
9.3 假脱机技术（SPOOLing）
工作原理：
在磁盘建立输入井和输出井
输入进程模拟脱机输入
输出进程控制实际输出
核心作用：将独占设备改造成共享设备