一、信号量
1. 利用信号量实现前趋关系
在图上标记自定义信号量：
[!NOTE]
从根节点开始，
有几个前驱节点就写几个 wait() （P操作）；
有几个后继节点就写几个 signal() （V操作）。
main() {
Semaphore a, b, c, d, e, f, g; // 声明信号量
a = b = c = d = e = f = g = 0; // 赋初值
cobegin
{ S1; signal(a); signal(b); } // S1没有前驱信号量
{ wait(a); S2; signal(c); signal(d); }
{ wait(b); S3; signal(e); }
{ wait(c); S4; signal(f); }
{ wait(d); S5; signal(g); }
{ wait(e); wait(f); wait(g); S6; } // S6没有后继信号量
coend
}
二、分页重定位
1. 已知某分页系统，内存容量为 64KB，页面大小为 1KB，对一个 4 页大的作业，其 0、1、2、3 页分别被分配到内存的 2、4、6、7 块中。
画出页表：
| 页号 | 物理块号 |
|---|---|
| 0 | 2 |
| 1 | 4 |
| 2 | 6 |
| 3 | 7 |
(1) 将十进制的逻辑地址 1023、2500、3500、4500 变换为物理地址。
[!NOTE]
逻辑地址 ÷ 页面大小 得到页号，余数为 页内地址（偏移量）
物理地址 = 物理块号 × 页面大小 + 页内地址(偏移量)
页面大小需要换算
Tip. 如果页表中的页号从 1 开始，页号需要 减1，本题页号从 0 开始，故不需要减1
页面大小 = 1KB = 1×1024 = 1024B
① 1023
逻辑地址 ÷ 页面大小 = 1023 ÷ 1024 = 0 ······ 1023
页号为 0，偏移量为 1023，查询页表得物理块号为 2
故物理地址为 2×1024 + 1023 = 3071
② 2500
2500 ÷ 1024 = 2 ······ 452
页号为 2，偏移量为 452，查询页表得物理块号为 6
故物理地址为 6×1024 + 452 = 6596
③ 3500
3500 ÷ 1024 = 3 ······ 428
页号为 3，偏移量为 428，查询页表得物理块号为 7
故物理地址为 7×1024 + 428 = 7596
④ 4500
4500 ÷ 1024 = 4 ······ 404
页号为 4，偏移量为 404
页号大于页表长度，越界中断
(2) 以十进制的逻辑地址 1023 为例，画出地址变换过程图。
2. 某虚拟存储器的用户空间共有 32个页面，每页 1KB，内存 16KB。假定某时刻系统为用户的第 0、1、2、3 页分配的物理块号分别为 5、10、4、7，而该用户作业的长度为 6 页，试将十六进制的逻辑地址 0A5C、103C、1A5C 转换成物理地址。
画出页表：
| 页号 | 物理块号 |
|---|---|
| 0 | 5 |
| 1 | 10 |
| 2 | 4 |
| 3 | 7 |
[!NOTE]
逻辑地址为十六进制逻辑地址，先转换为十进制
逻辑地址 ÷ 页面大小 得到页号，余数为 页内地址（偏移量）
物理地址 = 物理块号 × 页面大小 + 页内地址(偏移量)
作业长度为 6 页，为最大合法页数
单页大小 1KB = 1024 Byte
① 0A5C
(0A5C)HEX = (2652)10
2652 ÷ 1024 = 2 ······ 604
页号为 2，偏移量为 604，查询页表得物理块号为 4
故物理地址为 4×1024 + 604 = (4700)10 = (125C)HEX
② 103C
(103C)HEX = (4156)10
4156 ÷ 1024 = 4 ······ 60
页号为 4，偏移量为 60
页号合法，但该页未装入内存，缺页中断
③ 1A5C
(1A5C)HEX = (6748)10
6748 ÷ 1024 = 6 ······ 604
页号为 6，偏移量为 604
页号大于页表长度，越界中断
三、置换算法
1. 有一个请求分页式虚拟存储器系统，分配给某进程 3 个物理块，开始时内存中预装入第 1,2,3 个页面，该进程的页面访问序列为 1,2,4,2,6,2,1,5,6,1。计算缺页率
[!IMPORTANT]
本题中开始时内存中已经预装入第 1,2,3 个页面，故前三个时刻不算缺页！！！
(1) 先进先出（First In First Out, FIFO）置换算法：
| 时刻 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 访问顺序 | 1 | 2 | 4 | 2 | 6 | 2 | 1 | 5 | 6 | 1 |
| 物理块1 | 1 | 1 | 1 | (已存在,不置换) | 6(丢出1,页面置换) | 6 | 6 | |||
| 物理块2 | 2 | 2 | 2 | 1 | 1 | |||||
| 物理块3 | 4 | 4 | 4 | 5 | ||||||
| 缺页 | √ | √ | √ |
[!NOTE]
按照访问顺序依次填入物理块；
缺页行：该列发生页面置换，缺页打勾。
共发生 3 次缺页，共访问 10 次，FIFO 算法缺页率 3/10
(2) 最佳页面（Optimal, OPT）置换算法：
思想：选择以后永不访问或者未来最长时间内不再被访问的页面**（向未来时刻查找，从左向右）**
| 时刻 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 访问顺序 | 1 | 2 | 4 | 2 | 6 | 2 | 1 | 5 | 6 | 1 |
| 物理块1 | 1 | 1 | 1 | (已存在,不置换) | 1 | 1 | ||||
| 物理块2 | 2 | 2 | 2 | 5 | ||||||
| 物理块3 | 4 | 6(丢出4,页面置换) | 6 | |||||||
| 缺页 | √ | √ |
[!NOTE]
按照访问顺序依次填入物理块；
第 4 时刻由于内存中已存在 2，不进行置换；
第 5 时刻内存中有 1, 2, 4，向右看，其中：4 在未来永不访问，因此选择将 4 调出内存（有多个选择一个）；
第 8 时刻内存中有 1, 2, 6，向右看，其中：2 在未来永不访问，因此选择将 2 调出内存。
共发生 2 次缺页，共访问 10 次，OPT 算法缺页率 2/10 = 1/5
(3) 最近最久未使用（Least Recently Used, LRU）置换算法：
思想：最新访问过的页面可能会很快再被访问，因此将内存当中留存时间较短的页面保留，将留存时间最长的页面淘汰**（向历史时刻查找，从右向左）**
| 时刻 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 访问顺序 | 1 | 2 | 4 | 2 | 6 | 2 | 1 | 5 | 6 | 1 |
| 物理块1 | 1 | 1 | 1 | (已存在,不置换) | 6(丢出1,页面置换) | 6 | 5 | 5 | ||
| 物理块2 | 2 | 2 | 2 | 2 | 2 | 6 | ||||
| 物理块3 | 4 | 4 | 1 | 1 | 1 | |||||
| 缺页 | √ | √ | √ | √ |
[!NOTE]
按照访问顺序依次填入物理块；
第 4 时刻内存中已存在 2，访问2（2的访问时刻在此重置），不进行置换；
第 5 时刻内存中有 1, 2, 4，向左看，其中：1 在内存中有 4 个时刻未被访问，2 在上一个时刻就被访问仅停留1个时刻，4 停留 2 个时刻未被访问，1 留存时间最久，将 1 调出内存；
第 6 时刻内存中已存在2，访问2（2的访问时刻在此重置），不进行置换；
第 7 时刻内存中有 6, 2, 4，向左看，其中：6 在内存中有 3 个时刻未被访问，2 在第 6 时刻被访问，存在1个时刻，4 在内存中 有 5 个时刻未被访问，4 留存时间最久，将 4 调出内存；
第 8 时刻内存中有 6, 2, 1，其中：6 停留 3 时刻，2 停留 2 时刻，1 停留 1 时刻，故将 6 调出内存；
第 9 时刻内存中有 5, 2, 1，其中：5 停留 1 时刻，2 停留 3 时刻，1 停留 2 时刻，故将 2 调出内存；
第 10 时刻中内存存在 1，访问1，不进行置换。
Tip. 可在页面右下角标记页面留存时长
共发生 4 次缺页，共访问 10 次，LRU 算法缺页率 4/10 = 2/5
四、磁盘驱动调度
1. 假设有 11 个进程先后提出磁盘 I/O 请求，当前磁头正在 110 号磁道处，并预向磁道序号增加的方向移动。请求队列的顺序为 30、145、120、78、82、140、20、42、165、55、65，分别用 FCFS 调度算法和 SCAN 调度算法完成上述请求，写出磁道访问顺序和每次磁头移动的距离，并计算平均移动磁道数。
[!NOTE]
总寻道长度 = 总移动距离相加
平均寻道长度 = 总寻道长度 / 移动次数(本题中为进程数)
移动距离从当前磁头位置开始计算
(1) FCFS (先来先服务) 调度算法：
[!NOTE]
列表：先来先服务即按顺序访问
| 被访问下一个磁道号 | 移动距离（从110号开始） |
|---|---|
| 30 | 80 (110-30) |
| 145 | 115 (145-30) |
| 120 | 25 |
| 78 | 42 |
| 82 | 4 |
| 140 | 58 |
| 20 | 120 |
| 42 | 22 |
| 165 | 123 |
| 55 | 110 |
| 65 | 10 |
总寻道长度 = 80+115+25+42+4+58+120+22+123+110+10 = 709
平均移动磁道数 = 709 ÷ 11 = 64.45
(2) SCAN (扫描) 调度算法：
[!NOTE]
注意题中所要求移动方向，先排序再计算，增到最大（减到最小）后再从该位置开始从大到小（从小到大）往回排序
| 被访问下一个磁道号（从110号开始增加） | 移动距离（从110号开始） |
|---|---|
| 120 | 10 (120-110) |
| 140 | 20 (140-120) |
| 145 | 5 |
| 165 | 20 |
| 82 | 83 |
| 78 | 4 |
| 65 | 13 |
| 55 | 10 |
| 42 | 13 |
| 30 | 12 |
| 20 | 10 |
总寻道长度 = 10+20+5+20+83+4+13+10+13+12+10 = 200
平均移动磁道数 = 200 ÷ 11 = 18.18
(3) [本题中未出] FSCAN (循环扫描) 调度算法：
[!NOTE]
注意题中所要求移动方向，先排序再计算，增到最大（减到最小）后再重新从头（尾）开始从小到大（从大到小）排序
| 被访问下一个磁道号（从110号开始增加） | 移动距离（从110号开始） |
|---|---|
| 120 | 10 (120-110) |
| 140 | 20 (140-120) |
| 145 | 5 |
| 165 | 20 |
| 20 | 145 |
| 30 | 10 |
| 42 | 12 |
| 55 | 13 |
| 65 | 10 |
| 78 | 13 |
| 82 | 4 |
总寻道长度 = 10+20+5+20+145+10+12+13+10+13+4 = 262
平均寻道长度 = 262 ÷ 11 = 23.81
(4) [本题中未出] SSTF (最短寻道时间) 调度算法：
[!NOTE]
先排序再计算，从离当前磁头位置最近的开始依次排序
| 被访问下一个磁道号（从离110号最近的开始排序） | 移动距离（从110号开始） |
|---|---|
| 120 | 10 (120-110) |
| 140 | 20 (140-120) |
| 145 | 5 |
| 165 | 20 |
| 82 | 83 |
| 78 | 4 |
| 65 | 13 |
| 55 | 10 |
| 42 | 13 |
| 30 | 12 |
| 20 | 10 |
总寻道长度 = 10+20+5+20+83+4+13+10+13+12+10 = 200
平均寻道长度 = 200 ÷ 11 = 18.18
2. 磁盘请求服务队列中要访问的磁道分别为 38、6、37、100、14、124、65、67，磁头上次访问了 20 号磁道，当前处于 30 号磁道上，试采用 FCFS、SSTF 和 SCAN 调度算法，分别计算磁头移动的磁道数。
(1) FCFS (先来先服务) 调度算法：
| 被访问下一个磁道号 | 移动距离（从30号开始） |
|---|---|
| 38 | 8 (38-30) |
| 6 | 32 (38-6) |
| 37 | 31 |
| 100 | 63 |
| 14 | 86 |
| 124 | 110 |
| 65 | 59 |
| 67 | 2 |
磁头移动的磁道数 = 8+32+31+63+86+110+59+2 = 391
(2) SSTF (最短寻道时间) 调度算法：
| 被访问下一个磁道号（从离30号最近的开始排序） | 移动距离（从30号开始） |
|---|---|
| 37 | 7 |
| 38 | 1 |
| 14 | 24 |
| 6 | 8 |
| 65 | 59 |
| 67 | 2 |
| 100 | 33 |
| 124 | 24 |
磁头移动的磁道数 = 7+1+24+8+59+2+33+24 = 158
(3) SCAN (扫描) 调度算法：
磁头上次访问 20，当前位于 30，故刺头移动方向为增加
| 被访问下一个磁道号（从30号开始增加） | 移动距离（从30号开始） |
|---|---|
| 37 | 7 |
| 38 | 1 |
| 65 | 27 |
| 67 | 2 |
| 100 | 33 |
| 124 | 24 |
| 14 | 110 |
| 6 | 8 |
磁头移动的磁道数 = 7+1+27+2+33+24+110+8 = 212
五、文件系统目录计算
1. 一个文件系统中，FCB 占 64B，一个盘块大小为 1KB，采用单级文件目录，假如文件目录中有 3200 个目录项，则检索一个文件平均需要访问磁盘大约多少次？
[!NOTE]
目录文件占用大小 = 目录项个数 × FCB
占用盘块个数 = 目录文件占用大小 ÷ 单个盘块大小
平均需要访问磁盘次数 = (占用盘块个数 + 1) ÷ 2 （结果须化为整数）
Tip. 注意单位换算成相同的，1KB = 1024Bytes
目录文件占用大小 = 目录项个数 × FCB = 3200 × 64B = 204800B = 200KB
占用盘块个数 = 200KB ÷ 1KB = 200 个
平均需要访问磁盘次数 = (占用盘块个数 + 1) ÷ 2 = (200 + 1) ÷ 2 = 100.5 ≈ 100 次
所以 检索一个文件平均需要访问磁盘大约100次
2. 在某个文件系统中，每个盘块占 512B，FCB 占 64B，其中文件名占 8B。如果索引节点编号占 2B，则针对一个存放在磁盘上的、具有 256 个目录项的目录，请分别计算引入索引节点前后，为找到某个文件的 FCB 而平均启动磁盘的次数。
(1) 引入索引点前
目录文件占用大小 = 目录项个数 × FCB = 256 × 64B = 16384B
占用盘块个数 = 16384B ÷ 512B = 32 个
平均启动磁盘次数 = (占用盘块个数 + 1) ÷ 2 = (32 + 1) ÷ 2 = 16.5 ≈ 17 次
(2) 引入索引点后
[!NOTE]
引入索引节点后，每个目录项中需要额外存放文件名和索引节点编号，应额外该部分存储占用的盘块个数
索引占用大小 = 目录项个数 × (文件名占用大小 + 索引节点编号占用大小)
索引占用盘块个数 = 索引占用大小 ÷ 单个盘块大小
建立索引后平均磁盘启动次数 = (索引占用盘块个数 + 1) ÷ 2 + 1 （整数）
(注意：引入索引后磁盘启动次数需要 + 1，因为得到索引节点编号后，还须启动磁盘一次以将对应文件的索引节点读入内存！)
索引占用大小 = 256 × (8B + 2B) = 2560B
索引占用盘块个数 = 2560B ÷ 512B = 5 个
建立索引后平均磁盘启动次数 = (5 + 1) ÷ 2 + 1 = 4 次
3. 某文件系统的目录由文件名和索引节点编号构成。若每个目录项的长度均为 64B，其中 4B 存放索引节点编号，60B 存放文件名。文件名由小写英文字母构成，则该文件系统能创建的文件数量上限为多少？
[!NOTE]
创建的文件数量上限等于索引节点数量上限
索引节点编号占用大小单位转换为 bit (位) （1Byte = 8bit）
索引节点上限为 $2^{索引节点编号占用大小}$ 个，即为创建文件数量上限
索引节点编号占用大小 = 4B = 32bit
所以索引节点上限为 $2^{32}$ 个
故最多能创建 $2^{32}$ 个文件