} 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
引用 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；
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)，说明此时已经发生死锁，并找出参与死锁的 进程。
⑵ 在 ⑴ 的基础上，当 P 对逻辑地址 27A8H 进行访问， 该逻辑地址对应的物理地址是多少？
-1-
解： 页面大小为 2KB，2KB=2×210=211，
即逻辑地址和物理地址的地址编码的低 11 位为页内偏移；
⑴ ① 逻辑地址 4C7H=0100 1100 0111B，高于 11 位为 0，所以该地址访问逻辑页面 0；
五、死锁问题
某系统采用死锁检测发现死锁。设系统有资源类集合为 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
{ west_wait– –; west_crossing ++ ; V ( wq ) ; /*唤醒西边第一位等待者*/
} V(w_wait); /*唤醒西边后续的等待者*/ } V ( mutex ) ;
七、进程互斥
并发进程 P0 和 P1 关于共享变量的临界区分别为 region0 和 region1。用软件方法解决 P0 和 P1 互斥进入其 临界区的不．完．整．的 C 伪代码如下：
-4-
西面过河者算法： P(w_wait); /*后续过桥者将在此等待*/ P(mutex); if (east_crossing > 0)
{ west_wait ++ ; if (west_wait= =1) P(e_wait); //西边有等待，东边后续过桥者将等待 V ( mutex ) ; P ( wq ); /*西边第一位过桥者在此等待*/
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（磁道）
四、文件系统
（1）给出“用户打开文件表”和“系统打开文件表”的形式，并图示二者之间的联系； （2）说明“写文件”系统调用命令 write(fd,buf,count)的实现过程。
解：⑴ 用户打开文件表和系统打开文件表图示如下：
文件 打开 读写 系统打开 描述符 方式 指针 文件表入口
fd1
进程 P1 的用户打开文件表
int flag[2]={0,0}; /*公共变量*/
int turn;
/*公共变量*/
进程 P0：
do { flag[0]=1; turn= ① ; while ( ③ ) do continue;
<region0>；
进程 P1：
do { flag[1]=1; turn= ②; while ( ④ ) do continue;
文件 打开 读写 系统打开 描述符 方式 指针 文件表入口
FCB 主部 文件号 共享计数 修改标志
15
2
0/1
系统打开文件表
fd2
进程 P2 的用户打开文件表
（2）write(fd,buf,count)的实现过程如下： 参数含义：fd：文件描述符；count：写出记录个数；buf：内存起始位置； 执行步骤：① 由 fd 查找用户打开文件表，找到对应的系统打开文件表入口； ② 根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性； ③ 查系统打开文件表，找到文件的地址； ④ 计算欲访问起始记录的地址； ⑤ 如果需要，申请存储块； ⑥ 将内存中由 buf 起始的 count 个记录写到文件中由当前写指针所确定的区域； ⑦ 调整用户打开文件表的读写指针。
-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)
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 操作
一南北流向的小河上有一座独木桥，如下图所示：
解：⑴ 在上述情况下，系统依次接收请求：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
西
东
该独木桥宽度只能容纳一人，且该桥最多只能承重 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，防止对方饿死*/
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
换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个
在内存的表项。设当前进程 P 的页表如下（“时钟”指针指向逻辑页面 3 的表项）：
逻辑页号
页框号
访问位 r
修改位 m