第四章作业

4-14.

考虑有一个可变分区系统，含有如下顺序的空闲区：10K，40K，20K，18K，7K，9K，12K 和 15K，现有请求分配存储空间的序列：(1) 12K，(2) 10K，(3) 9K。若采用首次适应时，将分配哪些空闲区；若采用最佳适应和最坏适应算法呢？

先把初始空闲区按顺序用字母标记（便于画图）：

A: 10K B: 40K C: 20K D: 18K E: 7K F: 9K G: 12K H: 15K

首次适应

扫描顺序从 A 到 H，遇到第一个能放下的区就分配。

css复制代码

初始:  A(10)  B(40)  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)

R1=12: A(10)  B(40)→分配12, 剩28  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)
R2=10: A(10)→分配10(已用)  B(28)  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)
R3=9:  A(已用)  B(28)→分配9, 剩19  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)

最终空闲区（按位置）:
      A(已用)  B(19)  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)

最佳适应

每次在所有足够大的区中选尺寸最小的。

css复制代码

初始:  A(10)  B(40)  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)

R1=12: 在≥12的区中最小为 G(12) → G(已用)
R2=10: 在剩余≥10的区中最小为 A(10) → A(已用)
R3=9:  在剩余≥9的区中最小为 F(9)  → F(已用)

最终空闲区（按位置）:
A(已用)  B(40)  C(20)  D(18)  E(7)  F(已用)  G(已用)  H(15)

最坏适应

每次在所有足够大的区中选最大的区分配（然后分割）。

css复制代码

初始:  A(10)  B(40)  C(20)  D(18)  E(7)  F(9)  G(12)  H(15)

R1=12: 最大为 B(40) → 从 B 分配12, 剩28  ⇒ B(28)
R2=10: 当前最大为 B(28) → 从 B 分配10, 剩18  ⇒ B(18)
R3=9:  当前最大为 C(20) → 从 C 分配9, 剩11   ⇒ C(11)

最终空闲区（按位置）:
A(10)  B(18)  C(11)  D(18)  E(7)  F(9)  G(12)  H(15)

4-15.

有如图所示的页表中的虚地址与物理地址之间的关系即该进程分得 6 个主存块。页的大小为 4096。给出对应下面虚地址的物理地址。

(1) 20；(2) 5100；(3) 8300；(4) 47000。

页表：

物理地址 = 物理块号 × 页大小 + 页内偏移

（1）20

页号 = 20 ÷ 4096 = 0 偏移 = 20 页 0 → 物理块 2 物理地址 = 2×4096 + 20 = 8192 + 20 = 8212

(2) 5100

5100 ÷ 4096 = 1 页 偏移 = 5100 mod 4096 = 1004 页 1 → 物理块 1 物理地址 = 1×4096 + 1004 = 4096 + 1004 = 5100

(3) 8300

8300 ÷ 4096 = 2 页 偏移 = 8300 mod 4096= 108 页 2 → 物理块 6 物理地址 = 6×4096 + 108

6×4096 = 24576 24576 + 108 = 24684

(4) 47000

47000 ÷ 4096 = 11 页 但页表只有 0～7 页, 页号11 不在页表内，所以页号越界。

4-16.

一个进程在执行过程中，按如下顺序依次访问各页：0，1，7，2，3，2，7，1，0，3，2，5，1，7。若进程分得 4 个主存块，在分别采用 FIFO、LRU 和 OPT 算法时，要产生多少次缺页中断？假设进程开始运行时，主存没有页面。

先进先出算法FIFO

按到达顺序替换最早进入的页。逐步替换结果（只写帧内容，空格左为帧1 → 帧4；“F”表示缺页）：

步	引用页	帧内容（帧1,帧2,帧3,帧4）	缺页?
1	0	0, -, -, -	F
2	1	0, 1, -, -	F
3	7	0, 1, 7, -	F
4	2	0, 1, 7, 2	F
5	3	3, 1, 7, 2 (替换 0)	F
6	2	3, 1, 7, 2	命中
7	7	3, 1, 7, 2	命中
8	1	3, 1, 7, 2	命中
9	0	3, 0, 7, 2 (替换 1)	F
10	3	3, 0, 7, 2	命中
11	2	3, 0, 7, 2	命中
12	5	3, 0, 5, 2 (替换 7)	F
13	1	3, 0, 5, 1 (替换 2)	F
14	7	3, 0, 5, 7 (替换 3)	F

FIFO 总缺页次数 = 9 次。

最近最少使用算法LRU

每次缺页时替换最近最久未被访问的页。逐步（记录最近使用时间，用“F”标缺页）：

缺页发生在步骤：1(0),2(1),3(7),4(2),5(3),9(0),10(3),11(2),12(5),13(1),14(7)。

LRU 总缺页次数 = 11 次。

最佳置换算法OPT

每次缺页时替换将来最长时间内不再使用或下次使用最远的页。按最优策略替换，缺页发生在步骤：1,2,3,4,5,9,12,14。

OPT 总缺页次数 = 8 次。

4-17.

有如图所示段表，给出如下所示的逻辑地址所对应的物理地址。

(1) 0,430；(2) 1,10；(3) 2,500；(4) 3,400；(5) 4,112。

段表：

物理地址 = 段始址 + 段内偏移

(1) 0,430 430 < 600 → 合法 物理地址 = 219 + 430 = 649

(2) 1,10 10 < 14 → 合法 物理地址 = 2300 + 10 = 2310

(3) 2,500 500 ≥ 100 → 越界（非法地址）

(4) 3,400 400 < 580 → 合法 物理地址 = 1326 + 400 = 1726

(5) 4,112 112 ≥ 96 → 越界（非法地址）

4-18.

一台计算机含有 65536B 的存储空间，这一空间被分成许多长度为 4096B 的页。有一程序其代码段为 32768B，数据段为 16386B，栈段为 15870B。试问该机器的主存空间适合这个进程吗？如果每页改成 512B，适合吗？

页大小 = 4096B 时

主存页框总数：

65536 ÷ 4096 = 16 页框

程序每段需要的页数：

代码段：32768 ÷ 4096 = 8 页

数据段：16386 ÷ 4096 = 4 页 + 余 610 B → 5 页

栈段：15870 ÷ 4096 = 3 页 + 余 3582 B → 4 页

程序总页数：

8 + 5 + 4 = 17 页

但机器只有 16 页框。

所以 主存空间 = 17 * 4096 = 69632 时适合这个进程

页大小 = 512B 时

主存页框总数：

65536 ÷ 512 = 128 页框

程序所需页数：

代码段：32768 ÷ 512 = 64 页 数据段：16386 ÷ 512 = 32 页（余2）→ 33 页 栈段：15870 ÷ 512 = 30 页（余270）→ 31 页

总页数：

64 + 33 + 31 = 128 页

主存页框 = 128 程序需要 = 128

所以适合

4-19.

在某虚拟页式管理系统中，页表包括 512 项，每个页表项占 16 位（其中一位是有效位），每页大小为 1024 字节，则逻辑地址中分别用多少位表示页号和页内地址？

页表有 512 项 ⇒ 需要能编号 0～511 的页号。

• 512 = 2⁹ ⇒ 页号字段需要 9 位。

每页大小为 1024B：

• 1024 = 2¹⁰ ⇒ 页内地址字段需要 10 位。

因此：

• 页号占 9 位
• 页内地址占 10 位

整个逻辑地址长度 = 9 + 10 = 19 位。

4-20.

有一个虚存系统，按行存储矩阵的元素。一进程要为矩阵进行清零操作，系统为该进程分配物理主存共 3 页，系统用其中一页存放程序，且已经调入，其余两页空闲。若按需调入矩阵数据，当进程按如下两种方式进行编程时：

var A: array[1..100,1..100] of integer;

//程序A：
{
    for i=1 to 100
        for j=1 to 100
            A[i,j] = 0
}

//程序B
{
    for j:=1 to 100
        for i:=1 to 100
            A[i,j] = 0
}

(1) 若每页可存放 200 个整数，问采用程序 A 和程序 B 方式时，各个执行过程分别会发生多少次缺页？

矩阵需要页数：

10000/200=50 页10000 / 200 = 50 \text{ 页}10000/200=50 页

系统只有 2 个数据页框，程序是只读顺序访问，没有回访旧页，因此可把内存视为 容量仅为 2 的 FIFO，而访问序列是 严格递增页号。

---

程序 A：按行访问（顺序访问 1,2,3,...）

按行存储 → 访问顺序是：

text复制代码

页0 → 页1 → 页2 → ... → 页49

每次访问新页必然缺页，且不会再次访问旧页，因此：

A 的缺页次数：50 页全部会缺页

---

程序 B：按列访问

• 每访问一个新页都会缺页
• 页从不会被命中（不再回来时还在）

有100列，50页，100 * 50 = 5000

B 的缺页次数：5000 页

(2) 若每页只能存放 100 个整数时，会是什么情况？

程序 A：按行访问

按行存储 → 访问顺序是：

text复制代码

页0 → 页1 → 页2 → ... → 页99

每页访问完不会回头

A 的缺页次数：100 页

---

程序 B：按列访问

• 每访问一个新页都会缺页
• 页从不会被命中（不再回来时还在）

有100列，100页，100 * 100 = 10000

B 的缺页次数：10000 页

4-21.

一个请求分页管理系统中，内存的读写周期为 8ns，当配置有快表时，查找快表需要 1ns，内、外存之间传送一个页面的平均时间为 5000ns。假定快表的命中率为 75%，页面失效率为 10%，求内存的有效存取时间。

有效存取时间 EAT 是一个概率期望值，形式：

$EAT = (1 - \text{缺页率}) \times T_{\text{无缺页}} + \text{缺页率} \times T_{\text{有缺页}}$

TLB 命中的 TLB 查找期望=0.75×1

TLB 未命中时访问页表的代价=0.25×8

缺页代价=0.10 × (8+5000+8)

0.9×(0.75×1+0.25×8)+0.10×(8+5000+8)+8=512.075

4-23.

某计算机的 CPU 的地址长度为 64 位，若页的大小为 8192B，页表项占 4B。要求一个页表的信息应该存放在一个页中，问采用几级页表比较好？

页大小：8192=$2^{13}$

所以页内偏移13位，页号位数：64−13=51 位，共有$2^{51}$个页

8192/4=2048=$2^{11}$

每一级页表有 $2^{11}$个页表项，每一级页表可索引的位数 = 11 位

51/11 ≈ 4.6 ≈ 5

所以5级页表