6 signal(mutex1); 6 signal(empty); 7 signal(full); 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) ； wait(s1)； signal(s1)； input (b)； wait(s2)； signal(s2)； x=a+b； y=a*b； wait(s3) ； signal(s3)； Print (x,y,z)； } } }coend
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）系统是安全的，因为可以找到一个安全序列：
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
A 0 0 1 0 0 B 0 7 0 0 6 C 0 5 0 2 4 D 0 0 2 0 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进程暂时等待
Best-fit算法是最好的。
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 + 400 = 1727
（3） 第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) 增加页面长度
答：首先判断系统正在频繁地进行换页操作。所以，减少并发进程数会显著地减少换页操作，提高CPU的利用率。其它措施也有些效果，例如，安装更多内存。 1.安装一个更快的CPU。没用。
2.安装一个更大容量的磁盘用作页面交换。没用，交换空间本来就足够了。 3.增加并发进程数。没用，情况将会更糟。 4.减少并发进程数。效果明显。
5.安装更多内存。可能会有效果，因为空闲页帧增加了，换页的几率将相对减少。 6.安装更快的硬盘，或安装更多的硬盘和控制器。效果不明显。 7.增加一个预取页面算法。效果不确定。
8.增加页面长度。如果顺序访问居多，则会减少缺页次数。如果随机访问居多，因为单个页面占用更大的物理空间，页帧总数减少，所以缺页次数会增加；因为页面长度增加，页面的传输时间会增加。综上，此方案的效果不确定。
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微秒
9.01在某请求分页管理系统中，一个作业共5页，作业执行时依次访问如下页面：1，4，3，
1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为3，分别采用FIFO、LRU，试求出缺页中断的次数及缺页率。(要求画出页面置换情况表) 答：(1)采用FIFO页面置换算法，其缺页情况如表所示： FIFO页面置换算法的缺页情况