【软考笔记】2. 操作系统基本原理
进程管理
- 进程的状态
- 前驱图
- PV 操作
- 死锁问题
进程的状态
- 三状态：运行态、就绪态、等待态
- 五状态：运行态、活跃就绪、活跃阻塞、静止就绪、静止阻塞
活跃就绪相当于就绪，活跃阻塞相当于阻塞
将活跃转为静止是挂起，将静止转为活跃是激活
运行态可以直接通过挂起转为静止就绪
前趋图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CWaQVp2U-1679403936012)(/assets/前趋图.png)]
PV 操作
进程的同步与互斥
互斥的反义词是共享，同步（需要等待）的反义词是异步
PV
临界资源：进程间互斥进行共享的资源
临界区：每个进程中访问临界资源的那段代码
信号量
P(S) {S--;if(S <= 0) 将当前进程挂起
}V(S) {S++;
}
生产者消费者问题
S1 = 1;
S2 = 0; // 一开始消费者是没有东西可消费的，不能让他先开始生产者：生产一个产品P(S1);送产品到缓冲区V(S2);消费者：P(S2);从缓冲区取产品V(S1);消费产品
PV 操作+前趋图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r8zUQYqM-1679403936013)(/assets/前趋图+PV操作.png)]
技巧：在每个箭头的出发点加一个 V 操作，在每个箭头的终点加一个 P 操作
死锁
题型 1：至少有多少个资源才不会发生死锁
给每个进程分配它需要的资源数 -1 个，然后再来一个资源，一定不会发生死锁
(∑i=0N(counti−1))+1(\sum_{i=0}^N (count_i-1)) + 1(i=0∑N(counti−1))+1
死锁的预防
死锁的四大条件：
- 互斥
- 保持和等待
- 不剥夺
- 环路等待
破坏其中一个条件即可预防
死锁的避免
有序资源分配法
先把资源分给 A 进程，再分给 B 进程，再分给 C 进程。。。
银行家算法
核心思想：评估该进程是否能及时归还资源，如果不能，就不将此资源放出去
例题：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l9de686Z-1679403936014)(/assets/银行家算法例题.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kkvdh7IW-1679403936014)(/assets/银行家算法做题思路.png)]
存储管理
- 段页式存储
- 页面置换算法
段页式存储
内存分配空间的方式
- 首次适应法
- 最佳适应法：比要分配的稍大一点
- 最差适应法：最大的空闲块
- 循环首次适应法
改进 1：页式存储
将整个内存分区化
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0VM7SsHa-1679403936014)(/assets/页式存储1.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TtVnSwBS-1679403936015)(/assets/页式存储2.png)]
例题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KWshwYfz-1679403936015)(/assets/段页式存储例题.png)]
物理地址的求法：
- 将逻辑地址中
页号和页内地址分开：根据页面大小 - 找出页号，查表得页号对应的
物理块号（页帧号） - 将物理块号和业内地址拼接起来
淘汰页的求法：
- 页帧号为 0 的本来就不在内存里，不能淘汰
- 刚刚本访问过的访问位为 1，不能淘汰
优缺点
- 存储管理容易，碎片少
- 增加了系统开销，可能产生抖动
改进 2：段式存储
页式存储一个 页 容量是固定的
段式存储的 段，则是以进程为单位，按逻辑结构划分
地址结构：段号 + 段内地址
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0lmzS6Qw-1679403936015)(/assets/段式存储.png)]
优缺点
- 便于共享
- 内存碎片浪费大
改进 3：段页式存储
先分段，再分页
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XgnsE5Kr-1679403936015)(/assets/段页式存储.png)]
优缺点
- 空间浪费小，存储共享容易，存储保护容易，能动态连接
- 复杂性高，管理开销大
改进 4：快表
快表是由 cache 组成（而非内存）
用于存放访问最频繁的 页表
页面置换算法
把哪个页淘汰出去的算法
- 最优算法：无法在实际中应用
- 随机算法
- 先进先出算法（FIFO）：抖动
- 最近最少使用算法（LRU）：最近 N-1 个进入的不淘汰
题型 1：访存次数和缺页次数
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ajpQtEE5-1679403936016)(/assets/访存次数与缺页次数联系.png)]
B C
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PnyEIVPi-1679403936016)(/assets/第二问.png)]
- 没有使用快表：页表也放在内存中，需要访存一次，所以每次读一个块需要两次访存
- 对于一个完整的指令，约定：无论它占用了几个块都会一次性将其调入（本题 swap 放在 1023 单元中，是一个块的最后一个单元，但这条指令却占了两个单元，按道理应该产生了两次缺页中断，但在考试中只认为产生了一次）
文件管理
- 索引文件
- 位示图
索引文件
多级索引不指向物理盘块，而是指向下一级索引的地址
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JC8mQafe-1679403936016)(/assets/索引文件结构.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q0R1uZeG-1679403936016)(/assets/文件索引例题.png)]
CD
位示图法
管理空闲存储空间的四种方法：
- 空闲区表法：用一个表来记录哪些地方是空闲的
- 空闲链表法：把空闲的区块链接起来
- 位示图法
- 成组链表法：分组也分链
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J7l8CBMJ-1679403936017)(/assets/位示图法.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RT4dhi8q-1679403936017)(/assets/位示图法例题.png)]
D B
注意所有的编号都是从 0 开始
作业管理
设备管理
- 虚设备与 SPOOLING 技术
虚设备与 SPOOLING 技术
数据传输控制方式
- 程序控制方式：CPU 介入，外设被动，CPU 需要不停查询外设状态
- 程序中断方式：CPU 介入，外设主动发送状态
- DMA 方式：直接存取控制方式，CPU 只需要要在开头的时候安排好，其余过程由 DMA 控制器完成
- 通道
- 输入输出处理机
SPOOLING 技术
ABCD 争用打印机
- ABCD 分别将需要打印的内容放入输入井中
- 打印机顺次将要打印的内容进行处理
微内核操作系统
微内核操作系统只实现基本功能，把图形系统，文件系统，设备驱动和通信功能放在内核之外
优点：精炼，系统服务程序运行在用户地址空间，可靠性安全性高
缺点：用户态内核态需要频繁切换，效率低