22、试写出相应的程序来描述图2-17所示的前驱图。
(a) (b)
图2-17 前驱图
解：(a) Var a,b,c,d,e,f,g,h: semaphore: =0,0,0,0,0,0,0,0;
begin
parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end;
begin wait(b); S3; signal(e); end;
begin wait(c); S4; signal(f); end;
begin wait(d); S5; signal(g); end;
begin wait(e); S6; signal(h); end;
begin wait(f); wait(g); wait(h); S7; end;
parend
end
(b) Var a,b,c,d,e,f,g,h,i,j: semaphore: =0,0,0,0,0,0,0,0,0,0;
begin
parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end;
begin wait(b); S3; signal(e); signal(f); end;
begin wait(c); S4; signal(g); end;
begin wait(d); S5; signal(h); end;
begin wait(e); S6; signal(i); end;
begin wait(f); S7; signal(j); end;
begin wait(g); wait(h); wait(i); wait(j); S8; end;
parend
end
有三个并发进程P1、P2、P3共享一个缓冲器A，A中每次只能存放一个数，进程P1每次用random() 函数产生一个随机整数num，用put(A,num)将其存入A中。若存放到P1中的数是7的倍数，则由进程P2用get(A,x)将其取出并打印，否则由进程P3用get(A,x)取出并将被7除后的余数打印出来，为防止数的丢失和重复取同一个数，请用PV操作实现三个进程的同步与互斥活动。
Int s0=1,s1=0,s2=0;
Void p1()
{int a;
while(TRUE)
{ num=random();
p(s0);
put(A,num);
if num%7==0 then v(s1) else v(s2);
}
}
void p2()
{int b;
while(TRUE)
{ p(s1);
get(A,x);
print(x);
v(s0);
}
}
void p3()
{int b;
while(TRUE)
{ p(s2);
get(A,x);
print(x%7);
v(s0);
}
}
void main(){
parbegin(p1,p2,p3);
}
作业J1,J2,J3,J4的提交时间和运行时间如下表所示采用短作业优先调度算法（假设不考虑操作系统的开销问题）请分析给出作业调度的次序和计算平均周转时间。
解：
平均周转时间：45分钟
22. 在银行家算法中，若出现下述资源分配情：
试问：
⑴ 该状态是否安全？
⑵ 若进程
P 2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？
答：⑴该状态是安全的，因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。
⑵若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。
假设某计算机系统的内存大小为640K，在某一时刻内存的使用情况如下图所示。
此时，若进程顺序请求30K、20K和5K的存储空间，系统采用最差适应算法为进
程依次分配内存，请画出分配后的内存情况图。
答：
进程请求30K后
进程请求20K后
进程请求5K后
分配后内存情况图如下：
在一分页存储管理系统中，某作业的页表如下表所示。已知页面大小为1024字
节，试将逻辑地址1011、2148、3000、4000、5012转化为相应的物理地址。
解：对于逻辑地址1011，P=int
（1011/1024）=0,d=1011mod1024=1011
由页表可得第0页在第2块，所以物理地址为
2*1024+1011=3059
对于逻辑地址2148，P=int（2148/1024）=2,d=2148mod1024=100 由页表可得第2页在第1块，所以物理地址为
1*1024+100=1124
对于逻辑地址3000，P=int（3000/1024）=2,d=3000mod1024=952 由页表可得第2页在第1块，所以物理地址为
1*1024+952=1976
对于逻辑地址4000，P=int（4000/1024）=0,d=4000mod1024=928 由页表可得第3页在第6块，所以物理地址为
6*1024+928=7072
对于逻辑地址5012，P=int（5012/1024）=4,d=5012mod1024=916 由于页号超过页表长度，所以该逻辑地址为非法地址
考虑下面的页访问串：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
假定有4个页块，应用下面的页面置换算法，计算各会出现多少次缺页中断并给出变化情况。
（1）FIFO （2）Optimal
解：
（1）利用FIFO页面置换法：
