层次存储系统与输入输出系统

本节导读

大纲对系统结构的第 4、5 条要求：掌握层次存储系统的基本原理、结构和并行存储器，重点掌握虚拟存储器和高速缓冲存储器的原理、地址映像与变换方法、替换算法；掌握输入输出系统的组织方式、基本输入输出方式、中断系统的软硬件功能分配、中断优先级和中断屏蔽，了解通道处理机和存储设备。

这一节要会的计算很多：平均访问时间、Cache 地址划分、页表大小、页面替换的缺页次数、通道流量；中断屏蔽字的设置则要会动手设计。学完你应该能把这几类计算一步一步写出来，特别是先看清题目对「不命中时间」的约定。

存储层次与性能参数

寄存器、Cache、主存、辅存组成存储层次，目标是让整体速度接近最快的一层、容量和每位价格接近最大最便宜的一层。两级存储的主要参数：命中率 H（在高一级找到的访问占的比例）、平均访问时间、访问效率 $e = \frac{T_1}{T}$e=TT1​​。

平均访问时间有两种常见的写法，做题前先看清题目的约定：

约定	公式
不命中时只算访问低一级的时间 $T_2$T2​	$T = H T_1 + (1 - H) T_2$T=HT1​+(1−H)T2​
不命中时先花 $T_1$T1​ 查高一级、再花 $T_2$T2​ 访问低一级	$T = T_1 + (1 - H) T_2$T=T1​+(1−H)T2​

例如 $T_1 = 5$T1​=5 ns、$T_2 = 60$T2​=60 ns、H = 0.95：按第一种约定 $T = 4.75 + 3 = 7.75$T=4.75+3=7.75 ns，按第二种约定 $T = 5 + 3 = 8$T=5+3=8 ns。Cache 的性能也常写成「命中时间 + 不命中率 × 不命中开销」，就是第二种约定。

主存常用多体交叉（低位交叉）组织成并行存储器：m 个存储体轮流工作，连续地址分在不同的体里，理想情况下带宽提高到 m 倍；遇到转移或数据相关时实际达不到。

Cache 的地址映像与变换

主存块放进 Cache 的规则叫地址映像，有三种：

映像方式	规则	特点
全相联	主存的任何一块可以放进 Cache 的任何一行	冲突最少，但要和所有行比较标记，代价最大
直接映像	第 j 块只能放进第 j mod C 行（C 为行数）	最简单，冲突不命中最多
组相联（n 路）	第 j 块放进第 j mod S 组（S 为组数）的任意一行	折中，实际最常用

主存地址划分为「标记、组号（或行号）、块内地址」三段：块内地址位数 = $\log_2$log2​（块大小），组号位数 = $\log_2$log2​（组数），其余是标记。例如 32 位地址、16 KB 的 4 路组相联 Cache、块大小 32 B：共 512 行、128 组，块内地址 5 位、组号 7 位、标记 20 位。直接映像相当于每组 1 行，全相联相当于只有 1 组。

写 Cache 时有两种策略：写直达法（同时写主存，简单但写操作多）和写回法（只写 Cache，块被替换时如果被改过，即「脏」，才写回主存）。写不命中时还要决定是否把这一块调入 Cache（按写分配或不按写分配）。

虚拟存储器与替换算法

虚拟存储器让程序使用比主存大得多的地址空间。页式虚拟存储器把虚地址分成虚页号和页内地址，用页表把虚页号变成实页号；页表放在主存里，为了加快变换，把最近用过的页表项放在快表（TLB）里。页面不在主存时发生缺页，由操作系统调入。段式按程序的逻辑段划分，段的长度可变；段页式先分段、段内再分页。页表大小 = 页表项个数 × 每项字节数，例如 32 位虚地址、4 KB 页面、每项 4 B，页表项有 $2^{20}$220 个，页表占 4 MB。

主存满了要调入新页时，用替换算法选一页换出：

算法	换出哪一页	说明
FIFO	最早调入的页	实现简单；可能出现「页框增加、缺页反而增加」的 Belady 异常
LRU	最久没有被访问的页	利用了时间局部性，命中率较高
OPT	将来最久不会被访问的页	命中率最高，但要预知未来，只作比较的标准

LRU 和 OPT 属于堆栈型算法，页框增加时命中率不会下降。Cache 的行替换也用类似的算法。