十三. 死锁问题

多刷题

---

系统不可能发生死锁的最小资源数 （w-1）m+1 <= n

w：进程所需资源数

m：进程数

n：资源

---

十四. 段页式存储

第二个计算题型，建议深入了解（重点：页式、段式），重点是要理解题目的意思

段页式存储	优点	缺点
页式存储	利用率高，碎片小，分配及管理简单	增加了系统开销，可能会产生抖动现象
段式存储	多道程序共享内存，各段程序修改互不影响	内存利用率小，内存虽破浪费大
段页式存储（基本不考察）	空间浪费小，存储共享容易，能动态连接	由于管理软件增加，复杂性和开销也增加，执行速度下降

---

抖动现象：有人需要访问刚被淘汰的资源，加载完这个资源后所淘汰的资源又被访问，循环反复

---

14.1 页式存储

---

考察：逻辑地址转物理地址（实质上就是把页号转成页帧号）

逻辑地址 = 页号 + 页内地址

物理地址 = 页帧号 + 页内地址

---

例题一： 在页式存储系统中，每个页大小4KB，逻辑地址：10 1100 1101 1100，求物理地址。

解析：

​ 4KB = 2^12（2的12次方） 12位二进制才能表示 10 1100 1101 1100

​ 由此可知逻辑地址前2位是10是页号（二进制），十进制是2，如下图2的页帧号是6，二进制就是110

​ 所以物理地址为1101100 1101 1100

---

14.1.1 缺页中断

---

状态位（1表示在内存，0表示不再内存）

访问位（1表示最近被访问，0表示最近未被访问）（一定的时间内）

修改位（1表示内容被修改过，0表示内容没修改）（一定的时间内）

第一淘汰原则： 访问位为0

第二淘汰原则： 多个访问位为0时，优先修改位为0

---

页号（逻辑）	页号（物理）	状态位	访问位	修改位
0	2	1	1	0
1	3	1	0	1
2	5	1	1	0
3	-	0	0	0
4	-	0	0	0
5	6	1	1	1

14.1.2 页面置换算法

页面置换算法	描述
最优	太过理想
随机	不稳定
先进先出	可能产生抖动
最近最少使用	不会抖动，基于“局部性原理”

14.2 段式存储

---

逻辑地址： 段号+段内偏移量

---

14.3 段页式存储

---

瞄一眼即可

---

十五. 索引文件

第三个计算题型，建议深入了解，重点是要理解题目的意思

---

考察

​ （1）逻辑页号对应的索引方式

​ （2）最大文件长度

​ （3）访问磁盘次数

索引方式	访问磁盘次数
直接索引	1
一次索引	2
二次索引	3
三次索引	4

例题一： 索引块和磁盘块均为1KB，有8个结点，其中0~4时直接索引，5和6是一级索引，7是二级索引，每个地址项是4B

​ 问：（1）若要访问逻辑号4和5需要采用什么索引方式？ （2）单个文件的最大长度是多少KB？

解析：

​ （1）直接索引存逻辑号0、1、2、3、4（一共5KB）

​ 一级索引存逻辑号 5~260（一共256KB）

​ n-5+1 = 1024/4 = 260 （n减去直接索引的个数再+1 等于 索引块大小除地址项）

答案：若要访问逻辑号4和5需要采用直接索引和一级索引

​ （2）单个文件大小为 5KB+256KB+ (256KB)^2 = 65797KB

---

十六. 文件目录

第四个计算题型，建议深入了解（重点：位示图，注意位和字从0还是1开始）

---

修改目录发生崩溃时，影响较大

---

16.1 树形目录结构

---

允许不同文件夹下文件同名

绝对路径： 从盘符开始

相对路径： 从当前目录开始

全文件名： 绝对路径+文件名

---

16.2 位示图

---

考察

​ （1）给总量求需要的字数

​ （2）给磁盘编号求所处的位置

位： 默认为0

字： 根据题目来，无特殊说明从1开始

例题一： 字长32位用位示图表示，若容量为300GB，物理块为1MB，

​问：（1）位示图大小为多少？？ （2）2054放在第几个字？第几个比特位？

解析：

​ （1）有多少磁盘需要管理？ 300GB / 1MB = 300*2^10 （磁盘个数）

​ 一个字能表示多少个磁盘？（300*2^10）/ 32 = 9600（字数）

​ （2）2054 / 32 = 64…6

​ 放在第65个字（64余6，64放不下）对应编号（字）第64个字（这里是字从0开始）

​ 64*32 = 2048，说明编号（字）第64个字第一个比特位是2049由此得出2054在第6个比特位对应编号5（位也是从0开始的）

---