计算机系统结构课后习题答案

3.15 欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。

P= n=1 n=2 n=3 n=4 n=5

(2)n=4

(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单元访问肯定是命中的，而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况，共有7次页命中（折算为7×1024次单元命中），5次页不命中（折算为5×1023次单元命中，也可写为5×1024-5），单元访问总次数为12×1024，故有： Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96%

3.15加1题 一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下

P1 = 1 2 3 4 1 3 2 1 P2 = 1 2 3 4 2 2 3 3

试作2个实存分配方案，分别使2道程序满足 (1)命中率相同； (2)命中次数之和最大。

解：分别为2道程序作“堆栈模拟图”，其中“√”表示命中。

1 2 3 4 1 P1 = 1 2 3 4 1 1 2 3 4 1 2 3 1 2 n1= 1

n1= 2

n1= 3

n1= 4 √

P2 = n2= 1 n2= 2 n2= 3 n2= 4

将两图结果综合，得到4个分配方案的命中率情况表如下

6 5 N(1)+N(2) 4 3 2 N(1) N(2) 1 1+4 2+3 3+2 4+1 1 1 2 2 1 3 3 2 1 4 4 3 2 1 2 2 4 3 1 √ √ 2 2 4 3 1 √ √ √ √ 3 3 2 4 1 √ √ 3 3 2 4 1 √ √ √ √ 命中次数N(2) 2 2 4 4

3 3 1 4 2 √ √ 2 2 3 1 4 √ 1 1 2 3 4 √ √ 命中次数N(1) 0 0 2 4

4 4 5 5 4 3 3 5 4 2 2 3 5 4 5 5 2 3 4 √ √ √ 1 1 5 2 3 4 3 3 1 5 2 4 √ √ 2 2 3 1 5 4 √ √ 3 3 2 1 5 4 √ √ √ √ 5 5 3 2 1 4 √ √ 1 1 5 3 2 4 √ √ 3 3 1 5 2 4 √ √ √ 命中次数 0 1 3 7 7

(1)Hmax=7/12≈58.3%

n1 N(1) n2 N(2) N(1)+N(2)

3.19中(3)(4)(6)(8)问 (3)

虚存 0 1 2 3 4 5 6 7 · · · · 1 0 4 4 4 2 0 3 4 4 3 2 2 2 4 4 4 1 2 6 结论如下

(1)命中率相同的方案是n1= 3而n2= 2；

(2)命中次数之和最大的方案是n1= 4而n2= 1。

0 1 2 3

实页 0 虚 页

0 1 2 3 4 5 6 7 √ √ √ √ 1 √ √ √ √ 2 √ √ √ √ 3 √ √ √ √ 虚组0 虚组1 虚组2 虚组3

实存 实组0 实组1

(a) 虚页集合与实页集合的对应关系 (b) 对应关系表（√为有关系） (4)通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。

P= C0 C1 C2 C3 C=

(6)H=4/12≈33%

(8)做法同3.15题(3)问，Hcell=(12×16-8)/(12×16)≈95.8%

第四章(P250)

4.5 已知中断服务次序为3-2-4-1，。 (1)中断屏蔽字表如下图； (2)中断过程示意图如右图。

D1 D2 D3 D4 D1 0 0 0 0 D2 1 0 0 1 D3 1 1 0 1 D4 1 0 0 0 时间 中断请求 D1，D2 D3，D4

4.8

(1)f=2×10字节/秒，T=5us (2)Ts+Td=5us，通道时间图如下。作图时

注意：至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。

5

6 6 入 2 2 6* 2 入 3 4 4 6* 2 入 0 1 4* 1 6* 2 入 1 4 4 1* 6* 2 中 0 6 4 1* 6 2* 中 2 3 4 1* 6* 3 替 3 0 4* 0 6* 3 替 1 4 4 0* 6* 3 中 0 5 4* 5 6* 3 替 1 7 4* 5 7 3* 替 2 3 4* 5 7* 3 中 3

此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。

主程序 1级 2级 3级 4级

设 备 号

优 先 级

D1 1 D2 4 D3 2 D4 3 时间

(us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 (3)5，160，20，40；

(4)D2丢失第一次请求的数据； (5)参见P245。

第五章(P343)

5.9 为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。

记c1=A1×B1，……，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。

F=c1+c2+c3+c4+c5+c6 6 1 2 3 4 5 6 7 8 9 10 11

(a)

(b)

5 1 2 3 4 5 6 4 1 2 3 4 5 6 3 7 8 9 10 11 2 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 12 14 15 18 22 7 8 9 10 11

根据时空图(b)得

5.15 Δt=10ns=10秒 (1)F={1，2，5}，C=(10011) (2)状态转移图如下图(a)所示。

(3)最小启动循环=（3）,最小平均启动距离=3Δt。

(4)插入2个延迟，最小启动循环=（2）,最小平均启动距离=2Δt。 (5)新预约表如下图(b)所示。

-8

TP = 11/(22Δt) = 1/(2Δt)

S = (6×4Δt + 5×4Δt)/(22Δt) = 2 E = (6×4Δt + 5×4Δt)/(6×22Δt) = 1/3

(6)F={1，3，7}，C=(1000101)，状态转移图如下图(c)所示。

1 2 3 4 5 6 7 8 S1 × 1 2 × S2 × 1 ×

1 0 0 0 1 0 1 4，6，≥8

2 5 1 0 0 0 1 1 1 5 S3 × 4，6，≥8

初态 4，6，≥8

初态 3，4，≥6

1 0 0 1 1 S4 1 × × D1 × (b) 1 0 1 0 1 0 1 2 D2 × (a) (c) (7)插入前TPmax = 1/3Δt = 1/30ns，插入后TPmax = 1/2Δt = 1/20ns。

(8)插入前TP = 10/33Δt = 1/33ns，插入后TP = 10/26Δt = 1/26ns，如下图所示。

D2 1 2 3 11 D1 1 2 3 4 10 10 10 10 10 8 t

S4 1 1 2 2 3 S3 1 2 3 10 10 10 10 10 t 6 ……… S2 1 1 2 2 3 10 S1 1 2 1 3 2 10

3 9×3 (a) 插入前

S4 1 1 2 2 3 3 S3 1 2 3 4 S2 1 2 1 3 2 4 3 5 S1 1 2 3 4 1 5 2

2 9×2 ……… 10 10 10 (b) 插入后