操作系统例题讲解

引用 4C7H，页表表项 0：r=1；
② 逻辑地址 19B4H=0001 1001 1011 0100B，高于 11 位为 3，所以该地址访问逻辑页面 3；
修改 19B4H，页表表项 3：r=1, m=1;
③ 逻辑地址 0C9AH=0000 1100 1001 1010B，高于 11 位为 1，所以该地址访问逻辑页面 1；
0
0
0
0
0
2
P4
2
1
0
0
3
1
P5
0
0
1
0
0
0
上一状态没有死锁。
因为，用死锁检测算法，进程 P5、P0、P1、P2、P3、P4 能依次运行完。
⑵ 在⑴所确定的状态下，系统接收请求：request[0]=(0,3,1)，系统状态变化如下：
allocation
A
B
C
request
A
B
C
available
A
2
1
0
0
3
1
P5
0
0
1
0
0
0
-3-
问 题：
⑴ 在上述状态下，系统依次接收请求：request[0]=(1,0,0)、request[1]=(2,1,0)、request[3]=(0,0,2)， 给出系统状态变化情况，并说明没有死锁。
⑵ 在⑴所确定的状态下，系统接收请求：request[0]=(0,3,1)，说明此时已经发生死锁，并找出参与死锁的 进程。
四、文件系统
（1）给出“用户打开文件表”和“系统打开文件表”的形式，并图示二者之间的联系； （2）说明“写文件”系统调用命令 write(fd,buf,count)的实现过程。
解：⑴ 用户打开文件表和系统打开文件表图示如下：
文件 打开 读写 系统打开 描述符 方式 指针 文件表入口
fd1
进程 P1 的用户打开文件表
操作系统例题讲解
一、调度算法
对如下表所示的 5 个进程：
进程
到 达 时 间 （ ms）
优先级
P1
2
3
P2
0
1
P3
4
4
P4
0
2
P5
5
5
采用可剥夺的静态最高优先数算法进行调度（不考虑系统开销）。
问 题： ⑴ 画出对上述 5 个进程调度结果的 Gantt 图； ⑵ 计算 5 个进程的平均周转时间、平均带权周转时间。
逻辑页 1 不在内存，发生缺页中断；
①、②两操作后，P 的页表如下：
逻辑页号
页框号
访问位 r
修改位 m
内外标识
0
101H
1
0
1
1
—
0
2
110H
1
0
1
3
138H
1
1
1
4
—
0
5
100H
1
1
1
按改进的时钟算法，且时钟指针指向表项 3，应淘汰 0 页面，
即把 P 的逻辑页面 1 读到内存页框 101H，页表时钟指针指向表项 2。
五、死锁问题
某系统采用死锁检测发现死锁。设系统有资源类集合为 R＝｛A，B，C｝，6 个进程 P0、P1、P2、P3、P4、
P5 并发运行。当前系统状态如下：
allocation
request
available
A
B
C
A
B
C
A
B
C
P0
1
0
0
0
0
0
2
2
1
P1
3
2
1
0
0
0
P2
0
1
2
2
0
2
P3
0
0
0
0
0
0
P4
文件 打开 读写 系统打开 描述符 方式 指针 文件表入口
FCB 主部 文件号 共享计数 修改标志
15
2
0/1
系统打开文件表
fd2
进程 P2 的用户打开文件表
（2）write(fd,buf,count)的实现过程如下： 参数含义：fd：文件描述符；count：写出记录个数；buf：内存起始位置； 执行步骤：① 由 fd 查找用户打开文件表，找到对应的系统打开文件表入口； ② 根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性； ③ 查系统打开文件表，找到文件的地址； ④ 计算欲访问起始记录的地址； ⑤ 如果需要，申请存储块； ⑥ 将内存中由 buf 起始的 count 个记录写到文件中由当前写指针所确定的区域； ⑦ 调整用户打开文件表的读写指针。
B
C
P0
2
0
0
0
3
1
1
2
1
P1
3
2
1
2
1
0
P2
0
1
2
2
0
2
P3
0
0
0
0
0
2
P4
2
1
0
0
3
1
P5
0
0
1
0
0
0
对上一状态用死锁检测算法，P5、P3 能完成，P0、P1、P2、P4 不能完成，
发生死锁，参与死锁的进程为 P0、P1、P2、P4。
六、信号量与 P/V 操作
一南北流向的小河上有一座独木桥，如下图所示：
{east_wait ++ ; if (east_wait= =1) P(w_wait); //东边有等待，西边后续过桥者将等待 V ( mutex ) ; P ( eq ); /*东边第一位过桥者在此等待*/
} else { P(num); /*过河人数超过 4 人则等待*/ east_crossing++; V ( mutex ); } V(east_wait); <上独木桥过河>; P ( mutex ) ; east_crossing -- ; V(num); /*过桥人数减少 1 人*/ if (east_crossing = = 0) { if (west_wait > 0) do
解： ⑴ 调度结果的 Gantt 图如下：
CPU 阵发时间（ms） 3 2 3 4 2
P4
P1
P3
P5
P3
P1
P4
P2
0
2
(2) 时间计算：
4
5
7
9
10
12
14
进程 P1
到达时间 （ms）
2
优先级 3
运行时间 （ms）
3
பைடு நூலகம்
开始时间 （ms）
2
完成时间 （ms）
10
周转时间 （ms）
8
带权周转 时间（ms）
{ east_wait– –; east_crossing ++ ; V ( eq ) ; /*唤醒东边第一位等待者*/
} V(e_wait); /*唤醒东边后续的等待者*/ } V ( mutex ) ;
东面过河者算法： P(east_wait);/*后续过桥者将在此等待*/ P(mutex); if (west_crossing > 0)
} else { P(num); /*过河人数超过 4 人则等待*/ west_crossing++; V ( mutex ); } V(w_wait); <上独木桥过河>; P ( mutex ) ; west_crossing -- ; V(num); /*过桥人数减少 1 人*/ if (west_crossing = = 0) { if (east_wait > 0) do
Process
Arrival time
Burst time
P1
0
10
P2
3
6
P3
4
3
P4
7
4
问题：
⑴ 画出按最短剩余时间优先的 CPU 调度算法得到的进程调度结果的 Gantt 图； ⑵ 计算四个进程的平均等待时间、平均周转时间、平均带权周转时间。
解：⑴ 按最短剩余时间优先调度算法的进程调度结果 Gantt 图：
{ west_wait– –; west_crossing ++ ; V ( wq ) ; /*唤醒西边第一位等待者*/
} V(w_wait); /*唤醒西边后续的等待者*/ } V ( mutex ) ;
七、处理机调度算法
某系统按最短剩余时间（Shortest Remaining Time First）优先算法调度 CPU。已知四个进程 P1、P2、P3、 P4 的到达时间和 CPU 阵发时间如下（时间单位：毫秒）：
并执行操作： 修改 0C9AH。
经上述 3 个操作后，P 的页表如下：
逻辑页号
页框号
访问位 r
修改位 m
内外标识
0
—
0
0
0
1
101H
1
1
1
2
110H
0
0
1
3
138H
0
1
1
4
—
0
5
100H
0
1
1
⑵ 逻辑地址 27A8H=0010 0111 1010 1000B，高于 11 位为 4，所以该地址访问逻辑页面 4； 页面 4 不在内存，发生缺页中断；按改进的时钟算法，淘汰页面 2，页面 4 读到 110H 页框， 所以，逻辑地址 27A8H 对应的物理地址为： 0001 0001 0000 111 1010 1000B=887A8H。
换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个
在内存的表项。设当前进程 P 的页表如下（“时钟”指针指向逻辑页面 3 的表项）：
逻辑页号
页框号
访问位 r
修改位 m
内外标识
0
101H
0
0
1
1
—
0
2
110H
1
0
1
3
138H
0
0
1
4
—
0
5
100H
1
1
1
问 题： ⑴ 当进程 P 依次对逻辑地址执行下述操作： ① 引用 4C7H； ② 修改 19B4H； ③ 修改 0C9AH； 写出进程 P 的页表内容；
解：⑴ 在上述情况下，系统依次接收请求：request[0]=(1,0,0)、request[1]=(2,1,0)、request[3]=(0,0,2)， 系统状态变化如下：
allocation
request
available
A
B
C
A
B
C
A
B
C
P0
2
0
0
0
0
0
1
2
1
P1
3
2
1
2
1
0
P2
0
1
2
2
0
2
P3
8/3
P2
0
1
2
12
14
14
7
P3
4
4
3
4
9
5
5/3
P4
0
2
4
0
12
12
3
P5
5
5
2
5
7
2
1
平均周转时间=(8+14+5+12+2)/5=41/5=8.2 (ms)
平均带权周转时间=(8/3+7+5/3+3+1)/5=46/15≈3.07(ms)
二、存储管理
某系统采用虚拟页式存储管理方式，页面大小为 2KB，每个进程分配的页框数固定为 4 页。采用局部置
50, 20, 60, 30, 75, 30, 10, 65, 20, 80, 15, 70
问 题： ⑴ 写出对上述 I/O 请求序列的调度序列，并计算磁头引臂的移动量； ⑵ 计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问处理时间。
解：⑴ 考虑序列中有重复磁道的 I/O 请求，调度序列为： 60→75→50→30→20→15→10→65→70→80 磁头移动量=(75-60)+(75-50)+(50-30)+(30-20)+ (20-15)+(15-10)+(65-10)+(70-65)+(80-70) =15+25+20+10+5+5+55+5+10=155（磁道）
-4-
西面过河者算法： P(w_wait); /*后续过桥者将在此等待*/ P(mutex); if (east_crossing > 0)
{ west_wait ++ ; if (west_wait= =1) P(e_wait); //西边有等待，东边后续过桥者将等待 V ( mutex ) ; P ( wq ); /*西边第一位过桥者在此等待*/
西
东
该独木桥宽度只能容纳一人，且该桥最多只能承重 4 人；东、西两方向过桥人只能前进、不能后退。 问 题：写出用信号量和 PV 操作实现东、西两方向行人过桥没有死锁、没有饿死的并发运行算法。 要 求：给出定义的各信号量和变量的含义及其初值；算法用类 C 伪代码描述。
解：共享变量定义： int west_crossing=0,east_crossing=0,west_wait=0,east_wait=0; semaphore wq , eq; /*初值均为 0*/ semaphore mutex; /*初值均为 1，用于共享变量的互斥*/ semaphore num;/*初值为 4，用于限制过河人数*/ semaphore w_wait, e_wait; /*初值均为 1，防止对方饿死*/
⑵ 在 ⑴ 的基础上，当 P 对逻辑地址 27A8H 进行访问， 该逻辑地址对应的物理地址是多少？
-1-
解： 页面大小为 2KB，2KB=2×210=211，
即逻辑地址和物理地址的地址编码的低 11 位为页内偏移；
⑴ ① 逻辑地址 4C7H=0100 1100 0111B，高于 11 位为 0，所以该地址访问逻辑页面 0；
三、设备与 I/O 管理
设系统磁盘只有一个移动磁头，磁道由外向内编号为：0、1、2、……、199；磁头移动一个磁道所需时 间为 1 毫秒；每个磁道有 32 个扇区；磁盘转速 R=7500r/min. 系统对磁盘设备的 I/O 请求采用 N-Step Look （即 N-Step Scan，但不必移动到磁道尽头），N=5。设当前磁头在 60 号磁道，向内移动；每个 I/O 请求访问 磁道上的 1 个扇区。现系统依次接收到对磁道的 I/O 请求序列如下：
-2-
⑵ 总寻道时间=1×155=155（ms） 一次访盘的旋转时间=1/(2R)=1/(2×7500/min)=(60×1000)/(2×7500)ms=4(ms) 请求序列共 12 次访盘，总旋转延迟时间=4×12=48(ms) 1 次访盘的传输时间=1/(R×32)=(60×1000)/(7500×32)=1/4ms 12 次访盘总传输时间=1/4×12=3(ms) 总访盘处理时间=155+48+3=206(ms)