?(3)进程P2的请求小于W，标记P2，W＝2 2 2 0＋2 0 0 1＝4 2 2 1 ?(4)进程P1的请求小于W，标记P1，W＝ 4 2 2 1 ＋0 0 1 0＝4 2 3 1 ?(5)所有的进程都标记了，所以系统不存在死锁

6.10 a.第四个进程到达，最大需求是60，初始要求是25

?b.第四个进程到达，最大需求是60，初始需求是35

6.13

a.三个进程共享四个资源单元

最坏情况是，3个进程各只得到1个资源单元。 这时系统尚存有1个资源单元，因而将不会死 锁。 b.

定义：claim[i]=进程i总共需要的资源数目；

allocation[i]=进程i已经分配的资源数目； deficit[i]=进程i仍然需要的资源数目。 根据题意，我们有下式成立：

在一个死锁的情况下，所有的资源都是被占

有的，所以有下式成立：

并且，此时，每个进程都在等待资源。 从以上两个式子我们可以得出：

也就是说至少有一个进程j，它已经获得了所 有所需要的资源（deficit[j]=0），将完成其工 作并释放所有的资源，剩下的进程将依次完 成工作，因此死锁不会发生。

6.14

安全状态，需要的最小资源数目是3。

依次用P1-P4来表示四个进程。从矩阵可以看 出，四个进程还需要的资源数目为（2，1， 6，5），当有一个可用资源时，P2可以执行 完成，并释放占用资源，可用资源数目为2， 允许P1执行完成，可用资源数目为3，此时， P3需要6个资源，P4需要5个资源，既最小情 况还需要2个额外资源，P4执行完成，释放资 源后，P3再执行完成。 6.17

?如果至少有一个左撇子或右撇子，则当所有哲学家都准备拿起第一根筷子时，必定会有两

个哲学家竞争一根筷子而其中一个得不到处于等待，这样必定有一个哲学家可以获得两根筷子，而不至于发生死锁。

?同样也不会发生饥饿

7.1

重定位 支持模块化程序设计

保护 进程隔离；保护和访问控制 共享 保护和访问控制 逻辑组织 支持模块化程序设计

物理组织 长期存储；自动分配和管理 7.2

分区数目等于主存的字节数除以每个分区的字 节数：

每8位二进制数表示 个分区中的一个分区。 7.3

定义s和h分别为内存中段的数量和空洞的数 量。假定在动态分区的内存中，存储段的创建 和释放以相同的概率发生，那么对于任一分 区，它后面紧挨着的那个部分是一个分区或者 是一个空洞的概率各为0.5。所以，对于有s个 段的内存中，空洞的平均数量为s/2，既空洞 的数量是段数量的一半。 7.5

最佳适配算法在每次分割之后切割下来的剩

余部分总是最小的，这样会在存储器中留下 很多难以利用的小空闲区。最坏适配算法当 有进程调入的时候每次都分配最大的空闲存 储块，这样块中剩余的空闲空间就足够大从 而可以满足另外的请求。缺点是第一次分配 的时候就把最大的空闲区分配了，当有大的 空间分配请求时极易分配失败。 7.6

a.第一个块分配到第二个空闲块，起始地址为80M,第二个块分配到第一个空闲块，起始地址为20M，第三个块分配到第二个空闲块起始地址为120M。

b.第一个块分配到第四个空闲块，起始地址为230M，第二个块分配到第一个空闲块，起始地址为20M，第三个块分配到第三个空闲

块，起始地址为160M。

c.从上一次放置的位置开始扫描（注意只往后看），所以三个块的起始地址分别为80M，120M和160M。

d.每次都找最大的空闲块。三个块的起始地址为80M，230M和360M。 7.7 a. b. 7.8

a.011011110100

b.011011100000 7.9

其中，mod表示求余运算。 7.10

a. 我们完全可以采用斐波那契（Fibonacci）数列作为块的划分准则，从而建立起与普遍采用的对分伙伴系统（binary buddy system）不同的伙伴系统。

b. 与对分伙伴系统相比，按照斐波那契数列建立起来的伙伴系统能够提供更多不同的块容量；也就是说，整个内存空间划分得更细致了，块的容量更具有多样性。因此，在为进程分配存储空间时，可以找到最佳适配的存储块，因而可以使内部碎片的尺寸得以减小，这是这

种伙伴系统具有的显著优点。 7.12

a.逻辑地址空间为：

逻辑地址空间包含的位数为26位。 b.一个帧的大小和页的大小相同都是 。

c.存储器地址空间/帧大小= ，所以指定帧需要22位。 d.逻辑地址空间有 个页，所以含有 个页表项。

e.加上一个有效/无效位，制定一个帧的位数为22，所以总共为23位。 7.14

a.从段表可以看出，段表中的四个字段依次为段0，1，2，3。 物理地址=660+198=858 b.物理地址=222+156=378

c.由于段内偏移（530）>段的长度（442），所以发生段错误。 d.物理地址=996+444=1440 e.物理地址=660+222=882 8.1

?a ?步骤：

?从虚地址求取页号和页内偏移（利用公式：虚地址=页号*页长+页内偏移） ?利用页表由页号求取对应的块号

?求物理地址（利用公式：物理地址=块号*块长+块内偏移，注意到块长=页长，块内偏移=

页内偏移）

?b.

?(i) 1052 = 1024 + 28 虚拟页号为1，得到帧号为7。 ?物理地址=7*1024+28=7196 ?(ii) 2221 = 2 * 1024 + 173 ?虚拟页号为2，页错误。

?(iii) 5499 = 5 *1024 + 379虚拟页号为5，得到帧号为0。 ?物理地址=0*1024+379=379

8.2

a.存储器地址空间/页大小= ，所以在虚拟存储器中指定页需要22位。

每一页包含 个页表项。每个页表占据了8位，因此22位需要用到三级页表。

b.两级的页表包含 个页表项，一级页表包含 个页表项(8+8+6=22)。 c.我们这里有三级，三级所占位数为6，8，8，则页的个数为： 若三级所占位数为：8，6，8，则页的个数为：

若三级所占位数为：8，8，6，则页的个数为： 8.4

?a. 3号页帧的内容将被置换，因为它最早被加载。

?b. 1号页帧的内容将被置换，因为它的上次访问时间离当前最久。 ?c. 0号页帧的内容将被置换，因为其中R位和M位的值为（0, 1）。

?d. 3号页帧的内容将被置换，因为由将来的访问序列可知，页面3的访问顺序最靠后。

8.6

?a. 命中率=16/33

?b. 命中率=16/33

c. 对于这个特定的访问序列，采用上述两种替换策略得到的命中率相等。一般来说，采用LRU替换策略的命中率会高于采用FIFO替换策略的情况，而对于这个特定的访问序列来说，一个页面被载入之后，很少发生在接下来的5次连续访问中再次被访问的情形，因此缺页发生的时刻与LRU的情况相当接近，从而使得对应的命中率接近于LRU。 8.8

存储器地址从4000开始:

4000 (R1) ONE Establish index register for i 4001 (R1) n Establish n in R2 4002 compare R1, R2 Test i > n 4003 branch greater 4009