end; P:begin repeat

wait(full1);

get from buffer1; signal(empty1); wait(empty2); put to buffer2; signal(full2); until false; end; O:begin repeat

wait(full2)

get from buffer2; signal(empty2); until false; end;

parend; end;

第5章

5.1什么是死锁？引起死锁的原因和必要条件是什么？

死锁是指多个进程因为竞争资源造成的一种僵局。

原因：并发进程对临界资源的竞争和并发进程推进顺序不当。

必要条件：互斥条件，占有并请求条件，不剥夺条件，环路等待条件。

5.2 比较解决死锁的方法中，那种方法最容易实现？那种方法使得资源的利用率最高？

解决死锁的方法：预防死锁，避免死锁，检测死锁，解除死锁。

预防死锁是通过设计协同资源管理程序，在进程运行期间，柏怀死锁产生的四个条件之中的任何一个，是指不成立。 是最容易实现的方法。

解除死锁是在发现死锁后，解除死锁，释放资源。是资源利用率最高的方法。

5.3预防死锁的方法有哪些？

破坏互斥条件，破坏占有并请求，阻止环路等待，允许剥夺

5.8系统中有3个进程共享4个资源，每个进程每次只能申请或释放一个资源，每个进程最多需要2个资源，给进程是否会发生死锁，为什么？ 解:

不会发生死锁。3个进程共享4个资源，每个进程最多需要2个资源。 总有一个进程的请求会满足，运行并释放资源。不会形成环路等待。

5.9系统中有20个进程，每个进程最多使用3个资源，每个进程逐个申请并竞争使用60个同类资源。一旦某进程获得所需要的资源，完成后立即释放全部资源。系统是否会发生死锁？为什么？

系统不会发生死锁。以最坏的情况来考虑，20个进程都需要使用3个资源。当前，每个进程都持有2个资源。（20*2=40）.都在申请第3个资源（60-40=20）对于剩余的20个资源，每个进程多会得到一个资源。不会形成环路等待。

5.10 一台计算机有8台打印机，被N个进程竞争使用，每个进程最多需 要3台。 请问N为多少时，系统没有死锁的危险，说明原因。 解:

N=3时，没有死锁的危险。

对于N个进程，都持有2台打印机时，申请第3台打印机，只要有一台的多余的打印机能被申请到，则系统就没有死锁的危险。即N*2+1<=8 ，得 N<=3。

5.11 考虑图5.9所示的资源分配图，哪个进程会发生死锁？

进程P3,P4会发生死锁。

对于进程P1,P2，进程的推进不需要等待其他进程的完成。 进程P3,P4。P3要等P4完成并释放资源后方能推进。而P4要等到P3完成后才能。结果是P3,P4都不能完成。形成死锁。

5.12 假定有3个人排队等候上电梯。当电梯门打开的时候，3个人都朝门口冲去，但是门不够大，他们3人不能同时进门。描述解决这种死锁的方法，可以让3个人都上电梯。说明你的解决方案清除了哪个死锁的必要条件。 答：让3个人轮流进电梯。

破坏了死锁发生的4个必要条件中的“不剥夺条件”。

5.13 假定一个系统具有四种资源类型，分别为：R={3，7，2，3}，最大资源需求数表如图5.10所示。资源分配器根据图5.11中的表来分配资源，这个状态安全吗？为什么？

图5.10 图5.11

答：这个状态安全。存在安全执行序列{P4,P0,P1,P3,P2}；

6.9 如果一个分页系统能够向用户提供的逻辑地址最大为16页，页面大 小为2K，内存总共有8个存储块。请问逻辑地址应该为多少位？内 存空间为多大？

解：逻辑地址应该为4+11=15（位） 内存空间为8*2K =16K

6.10 如果一个分页系统的页表存放在内存。

（1）若对内存的一次存取需要1.2?s，请问一次页面访问的存取需 要花多少时间？

（2）若系统配置了联想寄存器，对快表的命中率为70%，假如查询 联想寄存器的时间忽略不计，请问实现一次页面访问的存取 时间是多少？ 解：（1）访问一次页面的存取需要花费的时间为2*1.2?s=2.4?s （2）实现一次页面访问的存取时间=0.3*1.2?s+1.2?s=1.56?s

6.11 如果一个分页系统逻辑地址长度为16位，页面大小为4KB，第0、1、2页对应10、12、14号物理块， 请问逻辑地址为2F6AH对应的物理地址为多少？ 解：逻辑地址为2F6AH对应的二进制码为：0010 1111 0110 1010，页号为：2，页内偏移为F6AH。

查询页表2号页面对应14号块，所以，物理地址为 1110 1111 0110 1010，最终物理地址为：EF6AH

6.12 如果内存中有4个空闲块，每个空闲块的大小为10MB。有10个请求，每次请求1MB的内存大小，对于下面列出的内存分配方法中的每一种，确定所有10个请求都被满足之后剩余空闲块的大小。 （a）首次适应算法 （b）循环首次适应算法 （c）最佳适应算法 （d）最坏适应算法 解：（a）首次适应算法：块1用完，块2，3，4剩余10MB。 （b）循环首次适应算法：块1，2余7MB，块3.4余8MB。 （c）最佳适应算法：块1用完，块2，3，4余10MB。 （d）最坏适应算法：块1，2余7MB，块3，4余8MB。

6.13 如果一个系统的段表为： 段 号 始 址 0 1 2 3 200 900 100 1200 段 长 510 30 80 500 4 1800 80 求下列逻辑地址相应的物理地址。如果越界请指明。 {0,380}、{1,20}、{1,24}、{2,200}、{3,500}、{4,120}。 解：{0,380}表示为0段，段内偏移为380，物理地址为580； {1,20}表示为1段，段内偏移为20，物理地址为920；

{1,24}表示为1段，段内偏移为24，物理地址为924； {2,200}表示为2段，段内偏移为200，已经越界；

{3,500}表示为3段，段内偏移为500，物理地址为1700； {4,120}表示为4段，段内偏移为120，已经越界。

7.5 在分页虚拟存储器管理中，如果已知时间利用率为：CPU20%、分页 磁盘92%、外设50%，请问采取哪些措施可以改善CPU的利用率？ 解：增大分页磁盘空间。

7.6 一个32位地址的计算机系统使用二级页表，虚拟地址为9位顶级页 表，11位二级页表和偏移。请问：页面长度为多少？虚拟地址空间 有多少个页面？

解：页面占用的位数=32-9-11=12位，页面长度为4K。虚拟地址空间有1M个页面。

7.7 如果分页虚拟存储系统向用户提供的逻辑地址空间最大为16页，每 页2KB，内存总共有8个存储块，请问逻辑地址至少应为多少位？内 存空间多大？

解：解：逻辑地址应该为4+11=15（位） 内存空间为8*2K =16K

7.8 在一个请求分页的虚拟存储器管理中，一个程序的运行页面走向为： 1、2、3、4、2、3、5、6、3、1、4、6、7、5、2、4、1、3、2

如果为程序分配页框为3个、4个，请分别用FIFO、OPT和LRU算法求出缺页中断次数和缺页率。 解：页框为3：

FIFO缺页中断次数为14；缺页率为14/19。 OPT缺页中断次数为8；缺页率为8/19。

LRU缺页中断次数为13；缺页率为13/19。

页框为4：

FIFO缺页中断次数为7；缺页率为7/19。

OPT缺页中断次数为5；缺页率为5/19。

LRU缺页中断次数为10；缺页率为10/19。

9.9 若采用字长为16位的位示图管理磁盘空间，某操作系统的磁盘文件空间共有500块，问位示图需要多少个字？第i列第j行对应的块号为多少？ 答：32,i,j按照书上公式

9.10 一个链接文件由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小都为512字节，一次存放在25，70，98，83，60号磁盘上。若要存取文件的第1 769逻辑字节处的信息，问需要访问哪个磁盘块？ 答：83

9.11 在UNIX操作系统中，如果一个盘块的大小为1KB，每个盘块号占用4个字节，即每块可放256个地址，如果进程要访问偏移为143 140处的数据，问需要几次寻址？ 答：1次间址

9.12 从磁盘高速缓存读取数据需要1ms，从磁盘读取数据需要40ms，如果命中率为50%，计算出读取数据的平均时间。 答：20.5ms

9.13 一个请求磁盘I/O的磁盘队列，分别在下列柱面上阻塞： 40，90，170，38，110，20，144，48，59。

请分别按照FCFS、SSTF、SCAN、CSCAN、CLOOK调度算法计算平均寻道长度，并说明那种调度算法最优。

9.14 如果磁盘总共包括A个块，其中F个是空闲的。一个磁盘地址需要dB。位示图为每个块使用1位。空闲链表中的每个链指向一个单独的空闲块。 （a）假设空闲链表方法单独地链接了所有的块，给出两种方法开销相同时必须满足条件（用A,F,d表示）。

（b）假设空闲链表方法链接了相邻块组，而不是单独的块，重复上面的问题。每个链元素指向了组中的第一块，并包括了一个说明在该组中有多少个块的2字节数。一个组的平均大小是5个磁盘块。

答：位示图的开销：位示图的列为dByte，行为（A）/d，开销为（A） 空闲链表至少包括空闲块号、指针（A-F个）

9.15 比较使用位示图和使用空闲链表表示磁盘空闲块的情况。