习题

处理机调度算法

分别计算按 FCFS 算法和 SJF 算法调度以下进程时的平均周转时间和平均带权周转时间。
项 \ 进程名称 A B C D E
到达时间 0 1 2 3 4
服务时间 4 3 5 2 4

项 \ 进程名称	A	B	C	D	E
到达时间	0	1	2	3	4
服务时间	4	3	5	2	4

FCFS：先来先服务算法。非抢占式调度，选择就绪队列中等待最长时间的进程。

SJF：短作业优先算法。分抢占式和非抢占式（默认后者），选择下一个期望最短处理时间的进程运行。

FCFS：

项 \ 进程名称	A	B	C	D	E
完成时间（ $到达 + m a x (服务, 上一个完成)$ ）	4	7	12	14	18
周转时间（ $完成 - 到达$ ）	4	6	10	11	14
带权周转时间（ $周转 / 服务$ ）	1	2	2	5.5	3.5

因此平均周转时间是 $(4 + 6 + 10 + 11 + 14) / 5 = 9$ ，平均带权周转时间是 $(1 + 2 + 2 + 5.5 + 3.5) / 5 = 2.8$ .

SJF：

项 \ 进程名称	A	B	C	D	E
完成时间	4	9	18	6	13
周转时间	4	8	16	3	9
带权周转时间	1	8/3	3.2	1.5	2.25

因此平均周转时间是 $(4 + 8 + 16 + 3 + 9) / 5 = 8$ ，平均带权周转时间是 $(1 + 8 / 3 + 3.2 + 1.5 + 2.25) / 5 = 2.124$ .

高响应比优先算法

在上一题的基础上，增加 HRRN 算法的计算。

HRRN 是介于 FCFS 与 SJF 之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。

先执行的是第一个提交作业，然后其余的作业再用响应比（ $(等待 + 服务) / 服务$ ）来判断执行顺序：

进程名称	响应比
B	$(3 + 3) / 3 = 2$
C	$(2 + 5) / 5 = 1.4$
D	$(1 + 2) / 2 = 1.5$
E	$(0 + 4) / 4 = 1$

B 响应比最高所以先执行，然后进一步计算剩余进程响应比：

进程名称	响应比
C	$(5 + 5) / 5 = 2$
D	$(4 + 2) / 2 = 3$
E	$(3 + 4) / 4 = 1.75$

D 响应比最高所以先执行，然后进一步计算剩余进程响应比：

进程名称	响应比
C	$(9 + 5) / 5 = 2.8$
E	$(7 + 4) / 4 = 2.75$

因此再分别执行 C、E。

项 \ 进程名称	A	B	C	D	E
完成时间	4	7	14	9	18
周转时间	4	6	12	6	14
带权周转时间	1	2	2.4	3	3.5

因此平均周转时间是 $(4 + 6 + 12 + 6 + 14) / 5 = 8.4$ ，平均带权周转时间是 $(1 + 2 + 2.4 + 3 + 3.5) / 5 = 2.38$ .

时间片调度算法

暂无情报......

进程的同步和互斥（PV 操作）

系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工作。输入进程和计算进程之间共用缓冲区 buffer1，计算进程和打印进程之间共用缓冲区 buffer2。输入进程接收外部数据放入 buffer1 中；计算进程从 buffer1 中取出数据进行计算，然后将结果放入 buffer2；打印进程从 buffer2 取出数据打印输出。用算法描述这三个进程的工作情况，并用 wait（P，借出/减 1） 和 signal（V，归还/加 1） 原语实现其同步操作。

有两个临界资源，因此需要定义两个互斥信号量和四个同步信号量。

semaphore mutex1 = 1, mutex2 = 1,
          empty1 = 1, empty2 = 1,
          full1  = 0, full2  = 0;

定义输入进程：

void inputP() {
  while (1) { // 疯狂轮询
    wait(empty1); // buffer1 不再为空
    wait(mutex1); // buffer1 不被允许其他线程访问
    input data from keyboard;
    write data to buffer1;
    signal(mutex1); // buffer1 可再被其他线程访问
    signal(full1); // buffer1 确实不再为空
  }
}

定义计算进程：

void calcP() {
  while (1) {
    wait(full1); // 等待 buffer1 有东西才操作
    wait(mutex1); // 等待 buffer1 可被访问
    take data from buffer1;
    write data to calcTemp;
    signal(mutex1); // buffer1 可再被其他线程访问
    signal(empty1); // buffer1 确实不再为空
    calculate data in calcTemp;
    wait(empty2); // buffer2 不再为空
    wait(mutex2); // buffer2 不被允许其他线程访问
    get data from calcTemp;
    write data to buffer2;
    signal(mutex2); // buffer2 可再被其他线程访问
    signal(full2); // buffer2 确实不再为空
  }
}

void printP() {
  while (1) {
    wait(full2); // 等待 buffer2 有东西才操作
    wait(mutex2); // 等待 buffer2 可被访问
    take data from buffer2;
    write data to printerTemp;
    signal(mutex2); // buffer2 可再被其他线程访问
    signal(empty2); // buffer2 确实不再为空
    print data in printerTemp;
  }
}

读者写者问题

暂无情报......

哲学家问题

暂无情报......

避免死锁

银行家算法

假定系统中有五个进程 ${P_{0}, P_{1}, P_{2}, P_{3}, P_{4}}$ 和三类资源 ${A, B, C}$ ，各种资源的数量分别为 10、5、7，在 $T_{0}$ 时刻的资源分配情况如表所示：
进程 \ 资源情况（ $A, B, C$ ） Max（最大需要） Allocation（已分配） Need（仍然需要） Available（可用）
$P_{0}$ 7 5 3 0 1 0 7 4 3 3 3 2
$P_{1}$ 3 2 2 2 0 0 1 2 2
$P_{2}$ 9 0 2 3 0 2 6 0 0
$P_{3}$ 2 2 2 2 1 1 0 1 1
$P_{4}$ 4 3 3 0 0 2 4 3 1
求：
$T_{0}$ 时刻的安全性；
$P_{1}$ 发出请求向量 $R e q u e s t_{1} (1, 0, 2)$ ，系统按银行家算法进行检查。

进程 \ 资源情况（ $A, B, C$ ）	Max（最大需要）	Allocation（已分配）	Need（仍然需要）	Available（可用）
$P_{0}$	7 5 3	0 1 0	7 4 3	3 3 2
$P_{1}$	3 2 2	2 0 0	1 2 2
$P_{2}$	9 0 2	3 0 2	6 0 0
$P_{3}$	2 2 2	2 1 1	0 1 1
$P_{4}$	4 3 3	0 0 2	4 3 1

列出分配顺序：

进程 \ 资源情况	Work（就是 Available）	Need	Allocation	Work+Allocation	Finish
$P_{1}$	3 3 2	1 2 2	2 0 0	5 3 2	T
$P_{3}$	5 3 2	0 1 1	2 1 1	7 4 3	T
$P_{4}$	7 4 3	0 1 1	0 0 2	7 4 5	T
$P_{0}$	7 4 5	7 4 3	0 1 0	7 5 5	T
$P_{2}$	7 5 5	6 0 0	3 0 2	10 5 7	T

可得最终各种资源数量为 10、5、7，故安全。

假使 $P_{1}$ 的请求已应用，则：

进程 \ 资源情况（ $A, B, C$ ）	Max（最大需要）	Allocation（已分配）	Need（仍然需要）	Available（可用）
$P_{0}$	7 5 3	0 1 0	7 4 3	==2 3 0==
$P_{1}$	3 2 2	==3 0 2==	==0 2 0==
$P_{2}$	9 0 2	3 0 2	6 0 0
$P_{3}$	2 2 2	2 1 1	0 1 1
$P_{4}$	4 3 3	0 0 2	4 3 1

列出分配顺序，并检查是否安全，这里不再列出。

内存管理

地址变换

某一页面内容自 0-7 依次为 03；07；0B；11；1A；1D；20；22。请计算页面大小为 1K 和 4K 时，逻辑地址 134D 对应的物理地址。

地址转换一下： $(134 D)_{16} = (0001 0011 0100 1101)_{2}$ .

页面大小为 1K 时，即为 $2^{10}$ ，地址占据低 10 位： $(0001 00 \bold 11 0100 1101)_{2}$

那么高 6 位就是 $(000100)_{2} = (4)_{10}$ 。而 4 号块数据是 $(1 A)_{16} = (0001 1010)_{2}$ .

因此页面大小为 1K 时，物理地址为两者拼接（数据高位舍去）： $(0110 10 \bold 11 0100 1101)_{2} = (6 B 4 D)_{16}$ .

同理，大小 4K 时，地址为 0011 0100 1101，块号为 $(0001)_{16} = (1)_{2}$ ，数据为 $(07)_{16} = (0000 0111)_{2}$ . 物理地址为 $(0111 \bold 0011 0100 1101)_{2} = (734 D)_{16}$ .

分区分配算法

在如下分区表的基础上，按照首次适应和最佳适应两种算法一次分配五个进程 P0、P1、P2、P3、P4 时的进程开始地址。五个进程的大小为 200k、15k、100k、80k、20k。
分区编号 1 2 3 4 5 6
起始地址 10k 200k 250k 320k 500k 850k
分区大小 100k 30k 50k 150k 300k 220k

分区编号	1	2	3	4	5	6
起始地址	10k	200k	250k	320k	500k	850k
分区大小	100k	30k	50k	150k	300k	220k

首次适应法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。

最佳适应法将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。

方法 \ 进程	P0	P1	P2	P3	P4
首次适应	500k	10k	320k	25k	200k
最佳适应	850k	1050k	10k	320k	200k

页面置换算法

在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配了 3 个物理块，并且此进程的页面走向位 2、3、2、1、5、2、4、5、3、2、5、2. 分别用 FIFO、LRU、OPT 算法计算出程序访问过程中所发生的缺页次数。

FIFO 是先进先出法，选择在内存中驻留时间最久的页面予以淘汰。

LRU 是最近最久未使用法，选择最近最久未使用的页面予以淘汰。

OPT 是最佳置换法，选择的被淘汰页面将是以后永不使用的，或许是在最长未来时间内不再被访问的页面。

FIFO：

物理块 \ 页号	2	3	2	1	5	2	4	5	3	2	5	2
1	2	2	2	2	5	5	5	5	3	3	3	3
2		3	3	3	3	2	2	2	2	2	5	5
3				1	1	1	4	4	4	4	4	2

缺页	Y	Y	N	Y	Y	Y	Y	N	Y	N	Y	Y

发生了 9 次缺页，缺页率 $9 / 12 = 75 %$ .

LRU：

物理块 \ 页号	2	3	2	1	5	2	4	5	3	2	5	2
1	2	2	2	2	2	2	2	2	3	3	3	3
2		3	3	3	5	5	5	5	5	5	5	5
3				1	1	1	4	4	4	2	2	2

缺页	Y	Y	N	Y	Y	N	Y	N	Y	Y	N	N

发生了 7 次缺页。

OPT：

物理块 \ 页号	2	3	2	1	5	2	4	5	3	2	5	2
1	2	2	2	2	2	2	4	4	4	2	2	2
2		3	3	3	3	3	3	3	3	3	3	3
3				1	5	5	5	5	5	5	5	5

缺页	Y	Y	N	Y	Y	N	Y	N	N	Y	N	N

发生了 6 次缺页。

磁盘与文件

磁盘调度算法

某磁盘有 8192 个磁道，编号为 0-8191，在完成了磁道 1250 处的请求后，当前正在磁道 3500 处为一个请求服务。若此时请求队列的先后顺序为 1000、4000、3300、5600、1300、6000、1200、2500. 回答下述问题：
采用 FCFS（先来先服务）算法完成上述请求。请写出磁头移动到顺序，并计算平均寻道长度，下同；
采用 SSTF（最短寻道时间优先）算法......；
采用 SCAN（电梯）算法......。

FCFS 是按照请求顺序来响应。

SSTF 是优先处理靠近当前磁头位置的请求。

SCAN 是优先处理同一方向的所有请求（但初始方向是趋大的），如存在 ${300, 100, 200, 250}$ 请求队列，且现在正在 $220$ 磁道，则应当依照 ${250, 300, 200, 100}$ 的顺序响应。

FCFS：3500 1000 4000 3300 5600 1300 6000 1200 2500， $L_{a v g} = (2500 + 3000 + 700 + 2300 + 4300 + 4700 + 4800 + 1300) / 8 = 2950$ .

SSTF：3500 3300 4000 2500 1300 1200 1000 5600 6000， $L_{a v g} = (200 + 700 + 1500 + 1200 + 100 + 200 + 4600 + 400) / 8 = 1112.5$ .

SCAN：3500 4000 5600 6000 3300 2500 1300 1200 1000， $L_{a v g} = (500 + 1600 + 400 + 2700 + 800 + 1200 + 100 + 200) / 8 = 937.5$ .

求 FAT 表大小

假定磁盘块大小为 1K，对于 540M 的硬盘，其文件分配表 FAT 需要多少存储空间？当硬盘容量为 1.2G，FAT 需要占用多少空间？

540M 的硬盘内含 540K 个 1K 的磁盘块。而 540K < $2^{20}$ = 1024K，

即每块耗费 20 位存储地址，即 2.5 字节，540K 块共耗费 1.35MB。

同理，1.2G 硬盘有 1.2M 个块，1.2M < $2^{21}$ = 2M，即 21 位/块，1.2M 块共消耗 25.2M 比特，即 3.15MB。

文件分配

系统中有 30M 的大文件和 10K 的小文件，若分别采用连续分配、链接分配、二级索引和混合索引的分配方案，假设盘块的大小为 2KB，每个盘块地址需要 2B，求：
每种方案可支持的文件最大长度；
在每种方案中，对 30M 的大文件和 10K 的小文件分别需要存储文件的物理地址的物理块数；
对于大文件的 5K 和（20M+5K）位置的内容读取对于每种方案分别需要的读盘次数（读物理块的次数）。
对于上述问题，将答案填写在下表中：
连续分配链接分配二级索引分配混合索引分配
文件最大长度
盘块数：30M 文件
盘块数：10K 文件
读盘数：5K 位置
读盘数：20M+5K 位置

	连续分配	链接分配	二级索引分配	混合索引分配
文件最大长度	不限	不限	2G	20K+2M+2G+2T
盘块数：30M 文件	0	0	15+1	1+14+1
盘块数：10K 文件	0	0	1+1	0
读盘数：5K 位置	1	3	1+1+1	1
读盘数：20M+5K 位置	1	(20M+5K)/2K	1+1+1	1+1+1

习题 ​

处理机调度算法 ​

高响应比优先算法 ​

时间片调度算法 ​

进程的同步和互斥（PV 操作） ​

读者写者问题 ​

哲学家问题 ​

避免死锁 ​

银行家算法 ​

内存管理 ​

地址变换 ​

分区分配算法 ​

页面置换算法 ​

磁盘与文件 ​

磁盘调度算法 ​

求 FAT 表大小 ​

文件分配 ​

习题

处理机调度算法

高响应比优先算法

时间片调度算法

进程的同步和互斥（PV 操作）

读者写者问题

哲学家问题

避免死锁

银行家算法

内存管理

地址变换

分区分配算法

页面置换算法

磁盘与文件

磁盘调度算法

求 FAT 表大小

文件分配