5.5下面哪些算法会引起饥饿 a.先来先服务 b.最短作业优先调度 c.轮转法调度 d.优先级调度 答：最短作业优先调度和优先级调度算法会引起饥饿。
5.7考虑一个运行10个I/O约束（型）任务和一个CPU约束（型）任务的系统。假设，I/O约束任务每进行1毫秒的CPU计算发射一次I/O操作，但每个I/O操作的完成需要 10毫秒。同时，假设上下文切换要0.1毫秒，所有的进程都是长进程。对一个RR调度来说，以下情况时CPU的利用率是多少： a.时间片是1毫秒 b.时间片是10毫秒
答：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操作和两个signal操作，则可能发生什么情况？
答：信号量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)互换位置，则不会引起死锁，其影响只是使某个临界资源的释放略为推迟一些。
6.02 一组合作进程，执行顺序如下图。请用wait、signal操作实现进程间的同步操作。
答：如图示并发进程之间的前趋关系，为了使上述进程同步，可设置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在生产者和消费者问题中，多个生产者进程（Producer
int nextc=0, nextp=0, buf[8]; semaphore full; empty; mutex;
生产者进程和消费者进程问题的算法描述如下： Producer Process: int itemp; while(1){
Consumer Process:
int itemc; while(1){
P1 P2 P4 P6 P5 P3 各进程的执行顺序 P1 a P2 c P4 g P6 b P3 f P5 h d e Process）和多个消费者进程
（Consumer Process）共享一个大小为8的缓冲区，他们的信号量和共享变量设置如下：
1 itemp = rand(); // Generate a number 2 wait(empty); 3 wait(mutex);
1 wait(full); 2 wait(mutex); 3 itemc=buf[nextc]; 4 nextc=(nextc+1)%8; 6 signal(empty);
7 cout << itemc << endl; }
4 buf[nextp]=itemp; 5 nextp=(nextp+1)%8; 6 signal(mutex); 7 signal(full); }
5 signal(mutex);
（1）生产者进程和消费者进程的临界区是哪些？ （2）信号量full、empty和mutex的初值是多少?
（3）如果对调生产者进程中的两个P操作即第2行和第3行，以及对调消费者进程中的两个P操作即第1行和第2行，如下所示。可能发生什么情况？
Producer Process ?
Consumer Process ?
1 wait(mutex); 2 wait(full); 3 itemc=buf[nextc]; ?
1 itemp = rand(); // Generate a number 2 wait(mutex); 3 wait(empty); ?
（4）上面的生产者和消费者同步算法有一个缺点，在有空缓冲区时，当消费者进程正在临界区时，生产者进程必须等待，反之亦然。您如何可以解决这个问题，以提高生产者和消费者进程之间并发？写出新的生产者进程和消费者进程的同步算法。 答：（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 int itemp; while(1){
Consumer Process
int itemc; while(1){
1 wait(full); 2 wait(mutex); 3 itemc=buf[nextc];
1 itemp = rand(); // Generate a number 2 wait(empty); 3 wait(mutex1);
4 buf[nextp]=itemp; 5 nextp=(nextp+1)%8; 6 signal(mutex1); 7 signal(full);
}
4 nextc=(nextc+1)%8; 5 signal(mutex);
6 signal(empty);
7 cout << itemc << endl;
}
6.04有2个合作的进程P1、P2 。他们从一台输入设备读入数据, P1进程读入数据a，P2进程读入数据b。输入设备是一台独享设备 。两个进程做如下计算：
P1: x = a + b P2: y = a * b
计算完成后结果的x、y由进程P1输出。用信号量实现P1、P2同步算法。
输出设备 P1 Input(a) 输入设备 P2 Input(b) 答：设置三个信号：s1表示数据a是否读入，s2表示数据b是否读入，s3表示数据y=a*b计算是否完成。P1和P2两个进程的同步算法如下：
semaphore s1=0, s2=0, s3=0; main() cobegin{ P1: {
P2: { }
input (a) ； signal(s1)； wait(s2)； x=a+b；
wait(s3) ； } }coend
wait(s1)； input (b)； signal(s2)； signal(s3)；
y=a*b；
Print (x,y,z)；
7.1 假设有如下图所示的交通死锁情况：
(1) 说明产生死锁的4个必要条件在此处成立。 (2) 给出一个避免死锁的简单规则。 答：（1）在此处，产生死锁的四个必要条件如下：
1) 2) 3) 4)
互斥条件。每个车道的每段道路只能被一辆车占用。
请求与保持条件。每个车队占用了一个车道，并请求前方的车道，即使需等待前方车道上的车队驶离，它仍将持有已占用的车道。
不抢占（剥夺）条件。在前方的车道被其它车队占用时，因为是单车道，而其它车队又不会后退，所以无法从其它车队处抢占车道。
环路等待条件。向东行驶的车队等待向北行驶的车队让出车道，向北行驶的车队等待向西行驶的车队让出车道，向西行驶的车队等待向南行驶的车队让出车道，而向南行驶的车队则等待向东行驶的车队让出车道。故存在一循环等待链。
（2）增加一个约束条件：只有前方两个路口都空闲时，才能占用第一个路口。或者，可在十字路口设置一交通信号灯，并使南北方向的两个车队和东西方向的两个车队互斥地使用十字路口，便可避免交通死锁。 7.11设有一系统在某时刻的资源分配情况如下： 进程号
已分配资源 A B C D
最大请求资源 剩余资源
A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6
请问：（1）系统中各进程尚需资源数各是多少？（2）当前系统安全吗？ （3） 如果此时进程P1提出资源请求（0，4，2，0），系统能分配给它吗？ 答：（1）尚需资源数矩阵如下：
Need = Max – Allocation
Need P0 P1 P2 P3 P4
（2）系统是安全的，因为可以找到一个安全序列：
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某系统有五个固定分区，其长度依次为100K, 500K, 200K, 300K, 600K。今有四个进程，对内存的需求分别是212K, 417K, 112K,
426K。当分别用First-fit, Best-fit, Worst-fit算法响应这四个进程的内存申请时，请分别给出系统的内存分配动态。哪种算法最有效？
答：根据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进程暂时等待
8.5 对下列问题，试比较连续内存分配方案、纯段式分配方案、纯页式分配方案中的内存组织方法：
a. 外部碎片 b. 内部碎片 c. 共享跨进程代码的能力
答：连续内存分配会产生外部碎片，因为地址空间是被连续分配的，当旧进程结束，新进程
初始化的时候，洞会扩大。连续内存分配也不允许进程共享代码，因为一个进程的虚拟 内存段是不被允许闯入不连续的段的。纯段式分配也会产生外部碎片，因为在物理内存 中，一个进程的段是被连续放置的，以及当死进程的段被新进程的段所替代时，碎片也 将会产生。然而，段式分配可以使进程共享代码；比如，两个不同的进程可以共享一个 代码段，但是有不同的数据段。纯页式分配不会产生外部碎片，但会产生内部碎片。进 程可以在页granularity中被分配，以及如果一页没有被完全利用，它就会产生内部碎片 并且会产生一个相当的空间浪费。在页granularity，页式分配也允许进程共享代码。 8.9考虑一个分页式存储管理系统，其页表常驻内存。
（1）如果内存访问耗时200 ns，那么，访问内存中的数据需要多长时间？
（2）如果引入联想寄存器，而且75%的页面可以从关联寄存器中找到，那么，此时的有效访问时间为多少？(假设访问关联寄存器的时间可以忽略)
答：（1）400纳秒，其中，200纳秒访问页表，200纳秒访问内存中的数据。
（2）有效访问时间 = 0.75 * (200纳秒访问内存数据+0纳秒访问关联寄存器) + 0.25 * (200纳秒访问内存数据+200纳秒访问页表) = 250纳秒 8.12假设有下列段表：
段 基地址 段长度 0 219 600 1 2300 14
2 90 100 3 1327 580 4 1952 96
下列逻辑地址对应的物理地址是什么？
（1） 0,430 （2）1,10 （3）2,500 （4）3,400 （5）4,112 答：（1）219 + 430 = 649 （2）2300 + 10 = 2310
（3） 第2段的有效长度是100。段内偏移量500超过了这个上限，所以这是个非法地址
（4） 1327 00 = 1727 （5）第4段的有效长度是96。段内偏移量112超过了这个上限，所以这是个非法地址
9.5假设一个“按需调页”虚拟存储空间，页表由寄存器保存。在存在空闲页帧的条件下，处理一次缺页的时间是8毫秒。如果没有
空闲页面，但待换出页面并未更改，处理一次缺页的时间也是8毫秒。如果待换出页面已被更改，则需要20毫秒。访问一次内存的时间是100纳秒。假设70％的待换出页面已被更改，请问缺页率不超过多少，才能保证有效访问时间小于或等于200纳秒？ 答：设缺页率为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利用率20%
用作页面交换的磁盘的利用率97.7% 其它I/O设备利用率5%
下列措施中，哪些会改善CPU利用率（如果有的话），请说明理由：
(1) 安装一个更快的CPU
(2) 安装一个更大容量的磁盘用作页面交换 (3) 增加并发进程数 (4) 减少并发进程数 (5) 安装更多内存
(6) 安装更快的硬盘，或安装更多的硬盘和控制器 (7) 增加一个预取页面算法 (8) 增加页面长度
答：a.首先判断系统正在频繁地进行换页操作。所以，减少并发进程数会显著地减少换页操作，提高CPU的利用率。其它措施也有些效果，例如，安装更多内存。
b.安装一个更快的CPU。没用。
c.安装一个更大容量的磁盘用作页面交换。没用，交换空间本来就足够了。 d.增加并发进程数。没用，情况将会更糟。 e.减少并发进程数。效果明显。
f.安装更多内存。可能会有效果，因为空闲页帧增加了，换页的几率将相对减少。 g.安装更快的硬盘，或安装更多的硬盘和控制器。效果不明显。 h.增加一个预取页面算法。效果不确定。
i.增加页面长度。如果顺序访问居多，则会减少缺页次数。如果随机访问居多，因为单
个页面占用更大的物理空间，页帧总数减少，所以缺页次数会增加；因为页面长度增加，页面的传输时间会增加。综上，此方案的效果不确定。
9.14一页式虚拟存储系统，用于页面交换的磁盘的平均访问、传输时间是20毫秒。页表保存在主存，访问时间1微秒。也就是说，
每引用一次指令或数据，需要访问两次内存。为改善性能，我们可以增设一个关联寄存器。如果页表项在关联寄存器里，则只要访问一次内存就够了。假设80％的访问，其页表项在关联寄存器中；剩下的20％里，10％的访问（即总数的2％）会产生缺页。请计算有效访问时间。
答：有效访问时间 = 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微秒