P2 P3 P4 P5 Average
c. Waiting Time Process P1 P2 P3 P4 P5 Average d.SJF 11 13 14 19 13.4 1 4 2 9 7.2 1 18 19 6 12 2 7 4 14 9.2 FCFS 0 10 11 13 14 9.6 SJF 9 0 2 1 4 3.2 NPP 6 0 16 18 1 8.2 RR(quantum=1) 9 1 5 3 9 5.4
5.5答：最短作业优先调度和优先级调度算法会引起饥饿
5.7答：a.时间片是1毫秒：不论是哪个进程被调度，这个调度都会为每一次的上下文切换花费一个0.1毫秒的上下文切换。CPU的利用率是1/1.1*100=92%。
b.时间片是10毫秒：这I/O限制任务会在使用完1毫秒时间片后进行一次上下文切换。这个时间片要求在所有的进程间都走一遍，因此，10*1.1+10.1(因为每个I / O限定任务执行为1毫秒，然后承担上下文切换的任务，而CPU限制任务的执行10毫秒在承担一个上下文切换之前) 。因此，CPU的利用率是20、21.1*100=94%。
6.01【参考答案】
信号量mutex的作用是保证各生产者进程和消费者进程对缓冲池的互斥访问。信号量empty和full均是资源信号量，它们分别对应于缓冲池中的空闲缓冲区和缓冲池中的产品，生产者需要通过wait(empty)来申请使用空闲缓冲区，而消费者需要通过wait(full)才能取得缓冲中的产品，可见，这两个信号量起着同步生产者和消费者的作用，它们保证生产者不会将产品存放到满缓冲区中，而消费者不会从空缓冲区中取产品。
在生产者—消费者问题中，如果将两个wait操作，即wait(full)和wait(mutex)互换位置，或者wait(empty)和wait(mutex)互换位置，都可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了wait(mutex)操作并获得成功，当再执行wait(empty)操作时，它将因失败而进入阻塞状态，它期待消费者执行signal(empty)来唤醒自己，在此之前，它不可能执行signal(mutex)操作，从而使企图通过wait(mutex)进入自己的临界区的其他生产者和所有的消费者进程全部进入阻塞状态，系统进入死锁状态。类似地，消费者进程若先执行wait(mutex)，后执行wait(full)同样可能造成死锁。
signal(full)和signal(mutex)互换位置，或者signal(empty)
和signal(mutex)互换位置，则不会引起死锁，其影响只是P1 b a 使某个临界资源的释放略为推迟一些。
P3 P2 d e f c 6.02【参考答案】
如图示并发进程之间的前趋关系，为了使上述进程同
P4 P5 6 / 13
g P6 h 合作进程的前趋图 步，可设置8个信号量a、b、c、d、e、f、g、h，它们的初值均为0，而相应的进程可描述为（其中“?”表示进程原来的代码）： main( ) cobegin{
P1( ) { ?; signal(a); signal(b); }
P2( ){ wait(a); ?; signal(c); signal(d); } P3( ){ wait(b); ?; signal(e); signal(f); } P4( ){ wait(c); wait(e); ?; signal(g); } P5( ){ wait(d); wait(f); ?; signal(h); } P6( ){ wait(g); wait(h); ?; }
}coend
6.03【参考答案】
（1）生产者进程的临界区是第4行和第5行；消费者进程的临界区是第3行和第4行。 （2）信号量full、empty和mutex的初值分别是：
empty = 8 ， full = 0 , mutex = 1 。
（3）系统可能会产生死锁。例如，生产者进程得到信号量mutex，但是没有空缓冲区即empty≤0时，此时生产者进程阻塞；而消费者进程又无法得到信号量mutex，此时消费者进程也阻塞，系统产生了死锁。
（4）增加一个信号量mutex1，初值为1，其算法如下：
Producer Process Consumer Process int itemp; int itemc; while(1){ while(1){ 1 itemp = rand(); // Generate a number 1 wait(full); 2 wait(empty); 2 wait(mutex); 3 wait(mutex1); 3 itemc=buf[nextc]; 4 buf[nextp]=itemp; 4 nextc=(nextc+1)%8; 5 nextp=(nextp+1)%8; 5 signal(mutex); 6 signal(mutex1); 6 signal(empty); 7 signal(full); 7 cout << itemc << endl;
} }
6.04【参考答案】
设置三个信号：s1表示数据a是否读入，s2表示数据b是否读入，s3表示数据y=a*b计算是否完成。P1和P2两个进程的同步算法如下： semaphore s1=0, s2=0, s3=0;
7 / 13
main() cobegin{ P1: {
input (a) ； signal(s1)； wait(s2)； x=a+b； wait(s3) ； Print (x,y,z)； } }coend
P2: { wait(s1)； input (b)； signal(s2)； y=a*b； signal(s3)； }
7.1【参考答案】
（1）在此处，产生死锁的四个必要条件如下：
1) 互斥条件。每个车道的每段道路只能被一辆车占用。
2) 请求与保持条件。每个车队占用了一个车道，并请求前方的车道，即使需等待
前方车道上的车队驶离，它仍将持有已占用的车道。
3) 不抢占（剥夺）条件。在前方的车道被其它车队占用时，因为是单车道，而其
它车队又不会后退，所以无法从其它车队处抢占车道。 4) 环路等待条件。向东行驶的车队等待向北行驶的车队让出车道，向北行驶的车
队等待向西行驶的车队让出车道，向西行驶的车队等待向南行驶的车队让出车道，而向南行驶的车队则等待向东行驶的车队让出车道。故存在一循环等待链。
（2）增加一个约束条件：只有前方两个路口都空闲时，才能占用第一个路口。或者，可在十字路口设置一交通信号灯，并使南北方向的两个车队和东西方向的两个车队互斥地使用十字路口，便可避免交通死锁。
7.11【参考答案】
（1）尚需资源数矩阵如下：
Need = Max – Allocation Need P0 P1 P2 P3 P4
（2）系统是安全的，因为可以找到一个安全序列：
8 / 13
A 0 0 1 0 0 B 0 7 0 0 6 C 0 5 0 2 4 D 0 0 2 0 2 Request1(0,4,2,0) <= available(1,5,2,0) 新的状态为
Allocation Max Need Available P0 0 0 1 2 0 0 1 2 0 0 0 0 1 1 0 0 P1 1 4 2 0 1 7 5 0 0 3 3 0 P2 1 3 5 4 2 3 5 6 1 0 0 2 P3 0 6 3 2 0 6 5 2 0 0 2 0 P4 0 0 1 4 0 6 5 6 0 6 4 2
该状态是安全的，存在安全序列如
8.3【参考答案】根据First-fit、Best-fit、Worst-fit算法，计算结果如下： First-fit:
212K进程装到500K分区 417K进程装到600K分区 112K进程装到200K分区 426K进程暂时等待
Best-fit:
212K进程装到300K分区 417K进程装到500K分区 112K进程装到200K分区 426K进程装到600K分区
Worst-fit:
212K进程装到600K分区 417K进程装到500K分区 112K进程装到300K分区 426K进程暂时等待
仅就本题为例，Best-fit算法是最好的。
8.5 Answer：连续内存分配会产生外部碎片，因为地址空间是被连续分配的，当旧进程结束，新进程初始化的时候，洞会扩大。连续内存分配也不允许进程共享代码，因为一个进程的虚拟内存段是不被允许闯入不连续的段的。纯段式分配也会产生外部碎片，因为在物理内存中，一个进程的段是被连续放置的，以及当死进程的段被新进程的段所替代时，碎片也将会产生。然而，段式分配可以使进程共享代码；比如，两个不同的进程可以共享一个代码段，但是有不同的数据段。纯页式分配不会产生外部碎片，但会产生内部碎片。进程可以在页granularity中被分配，以及如果一页没有被完全利用，它就会产生内部碎片并且会产生一个相当的空间浪费。在页granularity，页式分配也允许进程共享代码。
8.9【参考答案】
（1）400纳秒，其中，200纳秒访问页表，200纳秒访问内存中的数据。
（2）有效访问时间 = 0.75 * (200纳秒访问内存数据+0纳秒访问关联寄存器) + 0.25 * (200
9 / 13
纳秒访问内存数据+200纳秒访问页表) = 250纳秒
8.12【参考答案】
（1）219 + 430 = 649 （2）2300 + 10 = 2310
（3）第2段的有效长度是100。段内偏移量500超过了这个上限，所以这是个非法地址 （4）1327 + 400 = 1727
（3） 第4段的有效长度是96。段内偏移量112超过了这个上限，所以这是个非法地址
9.5【参考答案】设缺页率为P。题目并没有明确，当缺页中断时，内存中是否有空闲页帧，所以假设内存总是忙的。
访问内存中页面：(1 - P) * 100ns
页面不在内存，但不需要保存待换出页面：P * (1 – 70%) * (8ms+100ns) 页面不在内存，但需要保存待换出页面：P * 70% * (20ms+100ns)
所以，有效访问时间=(1 - P) * 100ns + P * (1 – 70%) * (8ms+100ns) + P * 70% * (20ms+100ns) = 200ns P = 0.000006 9.10【参考答案】
首先判断系统正在频繁地进行换页操作。所以，减少并发进程数会显著地减少换页操作，提高CPU的利用率。其它措施也有些效果，例如，安装更多内存。
(1) 安装一个更快的CPU。没用。
(2) 安装一个更大容量的磁盘用作页面交换。没用，交换空间本来就足够了。 (3) 增加并发进程数。没用，情况将会更糟。 (4) 减少并发进程数。效果明显。
(5) 安装更多内存。可能会有效果，因为空闲页帧增加了，换页的几率将相对减少。 (6) 安装更快的硬盘，或安装更多的硬盘和控制器。效果不明显。 (7) 增加一个预取页面算法。效果不确定。
(8) 增加页面长度。如果顺序访问居多，则会减少缺页次数。如果随机访问居多，因为
单个页面占用更大的物理空间，页帧总数减少，所以缺页次数会增加；因为页面长度增加，页面的传输时间会增加。综上，此方案的效果不确定。 9.14【参考答案】
有效访问时间 = 80% * 1微秒 + (1-80%)((1-10%) * 1微秒 * 2 + 10% * (1微秒 * 2 + 20毫秒))= 0.8+0.2 * (0.9 * 2+0.1*20002)
= 0.8+0.2 * 2002 = 401.2微秒
9.01【参考答案】
(1)采用FIFO页面置换算法，其缺页情况如表所示：
FIFO页面置换算法的缺页情况 页面走向 10 / 13
1 4 3 1 2 5 1 4 2 1 4 5