进程管理

1. 进程的状态
2. 前驱图
3. PV 操作
4. 死锁问题

进程的状态

1. 三状态：运行态、就绪态、等待态
2. 五状态：运行态、活跃就绪、活跃阻塞、静止就绪、静止阻塞

活跃就绪相当于就绪，活跃阻塞相当于阻塞
将活跃转为静止是挂起，将静止转为活跃是激活
运行态可以直接通过挂起转为静止就绪

前趋图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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

死锁的预防

死锁的四大条件：

1. 互斥
2. 保持和等待
3. 不剥夺
4. 环路等待

破坏其中一个条件即可预防

死锁的避免

有序资源分配法

先把资源分给 A 进程，再分给 B 进程，再分给 C 进程。。。

银行家算法

核心思想：评估该进程是否能及时归还资源，如果不能，就不将此资源放出去

例题：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l9de686Z-1679403936014)(/assets/银行家算法例题.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kkvdh7IW-1679403936014)(/assets/银行家算法做题思路.png)]

存储管理

1. 段页式存储
2. 页面置换算法

段页式存储

内存分配空间的方式

1. 首次适应法
2. 最佳适应法：比要分配的稍大一点
3. 最差适应法：最大的空闲块
4. 循环首次适应法

改进 1：页式存储

将整个内存分区化

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0VM7SsHa-1679403936014)(/assets/页式存储1.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TtVnSwBS-1679403936015)(/assets/页式存储2.png)]

例题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KWshwYfz-1679403936015)(/assets/段页式存储例题.png)]

物理地址的求法：

1. 将逻辑地址中 页号 和 页内地址 分开：根据页面大小
2. 找出页号，查表得页号对应的 物理块号（页帧号）
3. 将物理块号和业内地址拼接起来

淘汰页的求法：

1. 页帧号为 0 的本来就不在内存里，不能淘汰
2. 刚刚本访问过的访问位为 1，不能淘汰

优缺点

1. 存储管理容易，碎片少
2. 增加了系统开销，可能产生抖动

改进 2：段式存储

页式存储一个 页 容量是固定的
段式存储的 段，则是以进程为单位，按逻辑结构划分

地址结构：段号 + 段内地址

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0lmzS6Qw-1679403936015)(/assets/段式存储.png)]

优缺点

1. 便于共享
2. 内存碎片浪费大

改进 3：段页式存储

先分段，再分页

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XgnsE5Kr-1679403936015)(/assets/段页式存储.png)]

优缺点

1. 空间浪费小，存储共享容易，存储保护容易，能动态连接
2. 复杂性高，管理开销大

改进 4：快表

快表是由 cache 组成（而非内存）
用于存放访问最频繁的 页表

页面置换算法

把哪个页淘汰出去的算法

1. 最优算法：无法在实际中应用
2. 随机算法
3. 先进先出算法（FIFO）：抖动
4. 最近最少使用算法（LRU）：最近 N-1 个进入的不淘汰

题型 1：访存次数和缺页次数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ajpQtEE5-1679403936016)(/assets/访存次数与缺页次数联系.png)]
B C

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PnyEIVPi-1679403936016)(/assets/第二问.png)]

1. 没有使用快表：页表也放在内存中，需要访存一次，所以每次读一个块需要两次访存
2. 对于一个完整的指令，约定：无论它占用了几个块都会一次性将其调入（本题 swap 放在 1023 单元中，是一个块的最后一个单元，但这条指令却占了两个单元，按道理应该产生了两次缺页中断，但在考试中只认为产生了一次）

文件管理

1. 索引文件
2. 位示图

索引文件

多级索引不指向物理盘块，而是指向下一级索引的地址

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JC8mQafe-1679403936016)(/assets/索引文件结构.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q0R1uZeG-1679403936016)(/assets/文件索引例题.png)]
CD

位示图法

管理空闲存储空间的四种方法：

1. 空闲区表法：用一个表来记录哪些地方是空闲的
2. 空闲链表法：把空闲的区块链接起来
3. 位示图法
4. 成组链表法：分组也分链

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J7l8CBMJ-1679403936017)(/assets/位示图法.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RT4dhi8q-1679403936017)(/assets/位示图法例题.png)]
D B

注意所有的编号都是从 0 开始

作业管理

设备管理

1. 虚设备与 SPOOLING 技术

虚设备与 SPOOLING 技术

数据传输控制方式

1. 程序控制方式：CPU 介入，外设被动，CPU 需要不停查询外设状态
2. 程序中断方式：CPU 介入，外设主动发送状态
3. DMA 方式：直接存取控制方式，CPU 只需要要在开头的时候安排好，其余过程由 DMA 控制器完成
4. 通道
5. 输入输出处理机

SPOOLING 技术

ABCD 争用打印机

1. ABCD 分别将需要打印的内容放入输入井中
2. 打印机顺次将要打印的内容进行处理

微内核操作系统

微内核操作系统只实现基本功能，把图形系统，文件系统，设备驱动和通信功能放在内核之外

优点：精炼，系统服务程序运行在用户地址空间，可靠性安全性高
缺点：用户态内核态需要频繁切换，效率低