《计算机体系结构》第四章

1、计算机体系结构第四章 4CH4CH） 一、CH的基本工作原理 CH执行CH程序的过程 CH的任务 二、CH流量计算和时空图绘制 CH的类型 CH流量计算 字节多路CH响应处理时空图的绘制 1）计算每个子CH提供一个字节时间（1/f） 2）画出一个完整申请周期时空图 3）计算字节多路CH对每个字节响应的最长用时 计算机体系结构第四章 例3 若机器共有5级中断，中断响应优先次序为1- 2-3-4-5，现要求其实际的中断处理次序为1-4-5-2- 3。 (1)设计各级中断处理程序的中断级屏蔽位(令 “1”对应于屏蔽，“0”对应于开放)； (2)若在运行用户程序时，同时出现第4、2级中 断请求，而在处

2、理第2级中断未完成时，又同时出 现第1、3、5级中断请求，请画出此程序运行过程 示意图。 响应的前提：响应的前提：有请求；所在程序的中断级屏蔽位对其开放。 在被开放的所有中断处理程序中，其序号最小序号最小。 处理的前提：处理的前提：有请求；在请求队列中其优先级最高优先级最高。 计算机体系结构第四章 解: (1)各级中断处理程序的中断级屏蔽位 (中断处理次序为1-4-5-2-3) 中断处理 程序级别 中断级屏蔽位 1级2级3级4级5级 第1级11111 第2级01000 第3级01100 第4级01111 第5级01101 计算机体系结构第四章 （2）中断响应处理时空图中断响应处理时空图 (中断

3、处理次序为1-4-5-2-3) 主程序 中断处理程序 响 一 二 三 四 五 t 嵌套 中断请求 嵌套 嵌套 返回主程序 计算机体系结构第四章 计算机体系结构第四章 例5 某机器5级中断的中断处理次序为2-1-3-5-4。 (1)设计各级中断处理程序的中断级屏蔽位的状 态，令“0”为开放，“1”为屏蔽。 (2)若在运行用户程序时，同时发生1、3级中断 请求，而在1级中断服务未完成时，又发生2、4、 5级中断，请画出处理机执行程序的全过程示意图。 中断处理程 序级别 中断级屏蔽位 1级2级3级4级5级 第1级 第2级 第3级 第4级 第5级 计算机体系结构第四章 解: (1)各级中断处理程序的中

4、断级屏蔽位 中断处理程 序级别 中断级屏蔽位 1级2级3级4级5级 第1级 1 0 1 1 1 第2级 1 1 1 1 1 第3级 0 0 1 1 1 第4级 0 0 0 1 0 第5级 0 0 0 1 1 计算机体系结构第四章 2）中断响应处理时空图）中断响应处理时空图(中断处理次序为2-1-3-5-4) 主程序 中断处理程序 响 一 二 三 四 五 t 中断请求 嵌套 嵌套 返回主程序 计算机体系结构第四章 一、存贮体系原理一、存贮体系原理 1. 存贮器的层次结构 计算机体系结构第四章 计算机体系结构第四章 2. 2. 存贮器的参数不足存贮器的参数不足 1 1）容量不足的解决办法）容量不足

5、的解决办法 直接增加主存容量（S） 这种办法从第一代到现在都采用，但只有此法不够， 因此法随容量S，总价格C总，C位不变，用 此法不能使C位，因而不可能提高性能价格比。 计算机体系结构第四章 采用两级存贮器 利用低价格的辅存扩充存贮容量，三种信息： 活跃的信息活跃的信息，即当前正在使用的； 待命的信息待命的信息，将要使用的； 静止的信息静止的信息，已被使用而不再处理。 可将活跃的和部分待命的信息放在主存，其余放在 辅存，以减少对主存容量的要求，从而可降低C位。 在采用两级存贮器后，主辅存之间的信息调出与调 进的问题。 ）由程序员考虑和安排增加了程序员的负担。 ）用辅助机构自动定位，从而引出了虚

6、拟存贮器。 计算机体系结构第四章 虚拟存贮器 将高速辅存（如磁盘）伪装成主存访问，信息在主 存、辅存之间的调进（与调出）完全由辅助机构自动完 成，象这种将主存与辅存作为有机整体的存贮系统称为 虚拟存贮器。 2 2）速度不足）速度不足 存贮器的速度往往是整个计算机系统速度的一个瓶颈。 办法之一是直接提高主存速度，此法也在采用，但此 法随存贮器速度的提高,位价格 C位。 在CPU和主存之间加入高速缓存（cache）。 CPU 主存 cache 计算机体系结构第四章 让CPU直接面对与它的速度相匹配的cache访问，此 法也需要在CPU与cache之间利用辅助机构完成cache与主 存之间的信息调进

7、调出，cache与主存作为一个有机整体， 这也是一种存贮体系结构，称Cache -主存体系。 3. 3. 存贮体系中的辅助机构功能存贮体系中的辅助机构功能 1 1）地址映象功能：）地址映象功能：解决将M2中的信息采用何种规则调 入到M1中（即调入规则问题）。 CPUCPUM1M1M2M2 2 2）地址变换功能：）地址变换功能：根据映象规则，如何将包括M2在内 的大空间的地址变换为CPU能直接访问的M1中的地址 （即地址变换问题）。 3 3）替换算法功能：）替换算法功能：在M1中装满信息的条件下，采用何 种算法，算出调出M1的部分信息，使M2中的部分能调到 M1中（即替换算法问题）。 计算机体系

8、结构第四章 4. 4. 存贮器中的有关术语存贮器中的有关术语 1 1）存贮器：）存贮器：凡是能存放信息的记忆装置，称存贮器。 2 2）存贮系统：）存贮系统：要有两种或两以上的存贮器，才能称存 贮系统，如主存与辅存。 3 3）存贮体系：）存贮体系：只有将两（多）种不同的存贮器作为一 个有机整体的存贮系统，才能称为存贮体系。 4 4）存贮体系的两个分支）存贮体系的两个分支 虚拟存贮器，为扩充主存容量。 Cache-主存体系，为提高访问速度。 存储系统 存储体系 存储器 虚存 C-主 计算机体系结构第四章 5. 5. 对存贮体系的基本要求对存贮体系的基本要求 1）容量S：S2 S1（有足够的扩充空间

9、） 2）存取周期tm：tm1 tm2（提高访问速度） 3）位价格C位：C位2 C位1（才能降低C总，提高性 能价格比） 二、存贮器中的页式管理二、存贮器中的页式管理 1.1.页的概念页的概念 页式管理中将虚拟存贮空间和实际存贮空间等分成 固定大小的页，使虚拟页可装入主存中不同的实际页面 位置。 计算机体系结构第四章 计算机体系结构第四章 3. 3.页表页表 1）页表所需行数与虚页号数相等，虚页号与 页表行号对应，因此无需虚页号字段。 2）页表中每行内容可认为两个字段：实页号nv 及装入位（1位），0表示虚页未装入，1表示已装入。 实页号nv 装入位 0 1 2 3 4 5 6 7 011 10

10、0 001 111 110 010 101 000 计算机体系结构第四章 4 .4 .页式管理的地址变换页式管理的地址变换 1）根据虚页号Nv去查页表中的某一行m(m=Nv)。 2）查该行的装入位。 3）装入位=1时，命中。表示该虚页已装入。 从该行中送出nv（实页号）。 再将页内地址Nr直送nr， 即完成NvNr nv nr。 4）装入位=0时，失效，表示 该虚页未装入M1中。 实页号 装入位 0 1 2 3 4 5 6 7 011 100 001 111 110 010 101 000 计算机体系结构第四章 早期计算机的页面大小一般为1K。 考虑16G的硬盘，计算一下页表的记录数： 16G

11、/1K=16M 现在计算机的页面大小一般为4K，8K或16K。 设页面大小为16K，则页表的记录数：16G/16K=1M 一个页面放不下，怎么办？ 计算机体系结构第四章 5.5.页式管理中的表层次结构页式管理中的表层次结构 1 1）产生页表层次的条件）产生页表层次的条件 当用一页放不下页表时，就要用两页或两个以 上的页面来放页表，此时会出现页表层次结构。 2 2）页表层次的计算）页表层次的计算 设 虚页面数为2N，页面容量（大小）2P 则 页表层次数=N/P 如：某虚存空间有220个虚页面，页面容量 512=29个单元 则 页面层次数=20/9=3 计算机体系结构第四章 3 3）计算每层表的单

12、元数）计算每层表的单元数 底层表页的单元数与虚页面数2n=220相等，即 220行。再计算底层页表号占多少页面： 22029=211个页面 中层页表单元数与底层页表页面数相等，即 211行，而中层又占用多少页面： 21129=22个页面 上层页表单元数与中层页表的页面数相等22 行。 4 4）画出各层页表层次结构示意图）画出各层页表层次结构示意图 计算机体系结构第四章 上层(22行) 0 1 2 511 0 1 2 511 0 1 2 511 0 1 2 511 中层 (2n行4页) 底层 (220行 211页) 0 1 211-1 总页面单元数：总页面单元数：220+211+22 计算机体系

13、结构第四章 5）设所有页面数都放在主存，计算从查表开始 到最后实现访问所需时间为： 访存次数访存次数* *t tm m= =（表层次数（表层次数+1+1）* *t tm m= =（ N/PN/P +1+1）* *t tm m 访最后的数据信息 三、并行主存系统三、并行主存系统 1.1.定义：定义：凡在一个存取周期存取周期之内，能向CPU提供多个字 的存贮系统都可称为并行主存系统。 2.2.实现方法实现方法 1 1）单体多字结构）单体多字结构 利用增加一个单元中的字数来实现，只需增加存 贮器中的数据线而地址线可不增加，且控制难度并未增 加，但对同时取出的多个字的利用不一定充分。 计算机体系结构第

14、四章 W位W位W位W位 W位 地址寄存器 单字长寄存器 W位 地址寄存器 读出寄存器 L L/4 计算机体系结构第四章 计算机体系结构第四章 地址寄存器2地址寄存器1地址寄存器0地址寄存器3 存 控（主存控制部件） M0M2M3 M1 总 线 控 制 IOP CPU . 计算机体系结构第四章 3 3）多体多字结构）多体多字结构 将上述1）、2）两结构组合而成，控制难度大， 但每个tm向CPU提供的字最多，不过也存在对同 时取出的字利用不一定充分的问题。 3.3.多体单字的编址方式（设有多体单字的编址方式（设有4 4个体，每个体个体，每个体1K1K单元）单元） 1 1）体内连续编址）体内连续编址

15、（适用多处理机，减少存储器干扰） 体号首址末址 001023 110242047 220483071 330724095 单处理机基本不用,一个tm取出（0）（1024）（2048）（3072） 计算机体系结构第四章 特点：编址容易，控制方便； 由于指令执行时，顺序执行的情况较多，上条指 令与下一条指令往往来自同一个体，因而在一个tm时 间内，不能向CPU提供2条或2条以上指令。 2 2）体内断续，体间连续）体内断续，体间连续（流水线技术在存贮器中的应 用）。 体号 0123 地 址 0 4 8 4092 1 5 9 4093 2 6 10 4094 3 7 11 4095 计算机体系结构第四

16、章 1 1 某辅存共8个页面，每页 1024字，实际主存为4096字， 采用页表法进行地址映象，映 象表内容如下表所示： 1）列出会发生页面失效的全部虚 页号。 2）列出命中页面的全部虚页号。 3）以下地址计算主存实地址： 0，3728，1023，1024，2055， 7800，4096，6800。 实页号装入位 31 11 20 30 21 10 01 00 计算机体系结构第四章 1 解：解： 失效的虚页号：失效的虚页号：2、3、5、7。 命中的虚页号：命中的虚页号：0、1、4、6。 查地址查地址 Nv Nr nv 实地址实地址 装入位装入位 命中否命中否 0 0 0 3 3072 1 命中

17、命中 3728 3 656 3 3728 0 失效失效 1023 0 1023 3 4095 1 命中命中 1024 1 0 1 1024 1 命中命中 2055 2 7 2 2055 0 失效失效 7800 7 632 0 632 0 失效失效 4096 4 0 2 2048 1 命中命中 6800 6 656 0 656 1 命中命中 首址首址尾址尾址 01023 10242047 20483071 30724095 40965119 5120 6144 6143 7167 7168 8191 虚页虚页 0 1 2 3 4 5 6 7 计算机体系结构第四章 计算机体系结构第四章 存贮器的参

18、数不足存贮器的参数不足: : 容量不足容量不足=虚拟存贮器虚拟存贮器 速度不足速度不足=C-=C-主存体系主存体系 存贮体系中的辅助机构功能存贮体系中的辅助机构功能: : 地址映象功能地址映象功能 地址变换功能地址变换功能 替换算法功能替换算法功能 存贮器中的页式管理存贮器中的页式管理: : 页式管理的地址变换页式管理的地址变换 虚地址虚地址=实地址变换实地址变换 虚地址虚地址=页式虚地址页式虚地址=页式实地址页式实地址=实地址实地址 页表层次的计算页表层次的计算 计算机体系结构第四章 有四种映象规则：全相联、直接、组相联和段相全相联、直接、组相联和段相 联联，为便于介绍以主、辅存体系为例主、

19、辅存体系为例。 一、全相联映象及其变换一、全相联映象及其变换 1.1.含义：含义：对辅存中的任何一个页面都可以放到主存中 的任何一个页面上的映象规则，称全相联映象。 2.2.映象规则示意图映象规则示意图 NV 辅 主 nV 0 1 7 0 1 2 3 计算机体系结构第四章 3.3.地址变换地址变换 1)地址表示 2)全相联页表法。 与前面介绍的页式管理中的地址变换过程相同。 Nv Nr nv nr 1 虚地址 实地址 NvNv Nr nvnv nr 虚地址 实地址 计算机体系结构第四章 3）全相联目录表法 要求用相联存贮器作目录表目录表（相联存贮器是一种可按 内容的特征字段来访问的一种存贮器）

20、。 目录表的行数与主存页面数相等主存页面数相等（本例四行）。 目录表中每行的内容： ）NV为相联比较字段； ）nV为主存页号（非相联比较字段）。 送出n v 比较 比较 比较 比较 Nv Nv nv 相等 计算机体系结构第四章 地址变换过程 ）将虚地址中的NV送目录表中去进行相联比较 （一个tm）。 ）当有某个比较器比较相等时，将该行nV送出， 同时Nrnr，实现了NvNrnNvNrnv vn nr r的变换（命中）. ）若设有相等的，不命中，等待调入。 这种办法，可降低表的容量，但要求有相联存贮 器，（目录表的行数与主存页数相等）。 4.4.特点特点 1）产生页面冲突的可能性极小； 2）不能

21、实现查表与访存同时进行，不利于访问速 度提高。 计算机体系结构第四章 1.含义：先将辅存按 主存大小分为若干 块，在辅存的每块 内都有与主存相同 的页面数，辅存每 块内的页面只能调 入到与主存相同的 页面上的映象规则 称直接映象。 2.映象示意图 d ：块号 Nv：块内页号 二、直接映象及其变换二、直接映象及其变换 计算机体系结构第四章 3.3.地址变换地址变换 1 1）地址表示）地址表示 2 2）块表）块表 块表长度与主存页面数相等 （本例四行）。 块表行中的内容：块号d。 3 3）地址变换过程）地址变换过程 根据Nv去查块表中的Nv 行； 将虚地址中的块号d与所选 块表中的d比较； 比较相

22、同时命中，直接将 Nvnv，Nrnr。 比较不相同时，不命中。 0 1 M-1 Nd Nv Nr nv nr 比较X 访主存 不等 块失效 主存地址 n 虚存地址 N 计算机体系结构第四章 4.4.特点特点 1 1）可将查表与访问同时进行，有利于访问速度的提）可将查表与访问同时进行，有利于访问速度的提 高（命中时）。高（命中时）。 2 2）产生页面冲突的可能性极大（因无灵活的存放余）产生页面冲突的可能性极大（因无灵活的存放余 地）。地）。 三、组相联映象及其变换三、组相联映象及其变换 1.1.含义：先将主存分为页面数相同的若干组，再将含义：先将主存分为页面数相同的若干组，再将 辅存按主存划分为

23、若干区，组内采用全相联映象，组辅存按主存划分为若干区，组内采用全相联映象，组 间采用直接映象。间采用直接映象。 计算机体系结构第四章 2.2.示意图示意图 其中：Nd区号 q 组号 s 组内页号辅存 q组号 s组内页号主存 3.3.地址变换过程地址变换过程 1）地址表示 辅（虚） Nd q s Nr 主（实） q s nr 计算机体系结构第四章 2）随机存贮器表 表的行数与组数 相等（本例2组， 即2行）。 每行大字段数与 组内页面数相等 （本例2个）。 每个大字段又分 为三个小字段。 NdNd：区号； s s：组内页号； s s: :主存组内页号。 每个大字段还有 一个比较器。 Nd q s

24、 Nr辅(虚) 比较 Nd S S Nd S S 比较 Nd.S Nd.S = S 大字段1大字段2 每组内有多每组内有多 少个页面少个页面? 计算机体系结构第四章 3）地址变换过程 根据虚地址中的q去查随机存贮器表中的某一行。 将虚地址中的Nd、s同时送各比较器与所选行中的Nd、 s进行比较。 当有一个比较器相等时： ）将qq（组间直接）。 ）将相等大字段中S送出作S。 ）再将Nrnr,即实现了将虚址 Nd q s Nr qsnNd q s Nr qsnr r命中时的地址变换。 4. 4. 特点特点 即有直接映象中对号入座部分(组间直接)，可减少 查表范围，缩短查表时间，又有全相联中的灵活存

25、放规 则(组内全相联)，从而可降低页面冲突。但控制机构复 杂。 计算机体系结构第四章 组间直接映象 Nd q s qs 0 0 0 0 0 0 1 组内全相联映象 计算机体系结构第四章 四、段相联映象简介四、段相联映象简介 对主辅的划分与组相联映象相同，但为区分两种不 同的映象规则，将组相联中的组改为段，段间采用全相 联，段内采用直接映象。 0 1 0 1 0 1 主存 s qNd q s 辅存 0 1 0 1 0 1 0 1 0 1 0 1 0 1段间全相链 段内直接 段间全相联 可映象 Nd q s qs 0 0 0 0 0 1 0 段内直接映象 计算机体系结构第四章 五、四种映象规则关系

26、五、四种映象规则关系 1）在组相联映象中，当每组只有一页时，此时的组相 联就是直接映象。 当把主存只分为一个组时，此时的组相联也就是全 相联映象，即直接映象和全相联映象是组相联映象的两个 特例。 2）在段相联映象中，当每段只有一页时，此时的段相 联映象就是全相联映象。 当把主存只分为一个段时，此时的段相联也就是直 接映象。 计算机体系结构第四章 例2 用组相联映象组相联映象的Cache存贮器，页的大小为28个单 元，主存容量是Cache容量的4 4倍倍。映象表用单体多字按 地址访问存贮器构成，已装入内容如下表所示。用四套四套 外比较电路实现外比较电路实现组内相联查找块号。各字段用四进制四进制编

27、 码表示。 (1)给出四进制码四进制码表示的主存地址，问主存该单元内 容能否在Cache中找到。 (2)给出四进制码四进制码表示的主存地址及，问主存该单元 内容能否在Cache中找到。若能找到，指出相应的CacheCache 地址地址。 Nd SSNd SSNd SSNd SS 0001200222323 1013032331000 2330321312113 3022313211200 计算机体系结构第四章 分析 根据题意，主存容量是Cache容量的4倍，区号 Nd字段为2位。页的大小为28个单元，Nr字段为8位。4 套外比较电路实现组内相联查找块号，组内页号S字段 为2位。映象表的行数为组

28、数，所以，表中行号0、1、2、 3，对应于组号q的取值，q为2位。可见，主存的二进制 地址各字段的划分和位数为： (2位) (2位) (2位) (8位) Cache的二进制地址各字段的划分和位数为： (2位) (2位) (8位) 区号组号组内页号页内位移 组号组内页号页内位移 计算机体系结构第四章 例2 解 (1)由主存地址中的q1，到映象表中的第1行里去查各个 Nd、S，在表中均未找到有Nd3、S2 的内容，所以 主存的该页不在Cache中，发生Cache块失效，无物理 Cache地址。 (2)由主存地址(1210000)4 4知：q2，在映象表的第2行中 的最右面找到（命中）有Nd1、S1

29、、S=3 其Cache中物理单元的地址为 q=q=2, S=3,nr=0000 即：2*1024+3*256+0=2048+768=2816 由主存地址(2310333)4 4知：q=3，在映象表的第3行中 的第3部分找到有Nd2、S1、S=1 其Cache中物理单元的地址为q=3, S=1,nr=(0333)4 4 即：3*1024+1*256+(333)4 4=3072+256+63=3391 计算机体系结构第四章 四种映象规则及地址变换：四种映象规则及地址变换： 全相联映象：页表、目录表全相联映象：页表、目录表 直接映象：块表直接映象：块表 组相联和段相联：随机存贮器表组相联和段相联：随

30、机存贮器表 区号区号 组号组号 组内页号组内页号页内位移页内位移 组号组号 组内页号组内页号页内位移页内位移 Nd q s Nr辅(虚) 比较 Nd S S Nd S S 比较 Nd.S Nd.S = S 大字段1大字段2 每组内有多每组内有多 少个页面少个页面? 计算机体系结构第四章 计算机体系结构第四章 四种映象规则及地址变换：四种映象规则及地址变换： 全相联映象：页表、目录表全相联映象：页表、目录表 直接映象：块表直接映象：块表 组相联和段相联：随机存贮器表组相联和段相联：随机存贮器表 区号区号 组号组号 组内页号组内页号页内位移页内位移 组号组号 组内页号组内页号页内位移页内位移 Nd

31、 q s Nr辅(虚) 比较 Nd S S Nd S S 比较 Nd.S Nd.S = S 大字段1大字段2 每组内有多每组内有多 少个页面少个页面? 计算机体系结构第四章 CPU寄存器 b a M1:高速缓存 a,b为高速缓存块， 32个字节 (块长一般取一个主 存周期所能调出的 信息长度 ) 页面A a M2:主存储器 页面B b 页面A a M3:磁盘 存储器 页面B b 段F 段G M4:磁带机 后援存储器 段G 字单位 块单位 页单位 段单位 页面A a 页面B b 段F 计算机体系结构第四章 一、概述（以主辅存页式管理）一、概述（以主辅存页式管理） 1.1.含义：含义：在主存装满页

32、面时，采用何种算法，计算出 主存中的被替换页面，以便辅存中的页面能调入到 主存，为此而采用的算法称替换算法。 2.2.对替换算法的评价对替换算法的评价 1）要利于实现，某种算法其命中率很高，但它实现 不了，因此不能采用。 2）要保证有一定的命中率，某种算法很好实现，但 命中率无保证，因而不能采用。 3.3.为保证一定的命中率，对被替换页面的要求：为保证一定的命中率，对被替换页面的要求： 1）以后不再使用的页面，（很难确定以后是否不会 使用，除非固定页面地址流）。 2）都要使用时，先替换最后使用的页面。 3）替换最久没有使用的页面（可以统计出来）。 计算机体系结构第四章 4 4 替换算法替换算法

33、 1 1）随机替换算法）随机替换算法（利用随机函数发生器产生一个被替 换页面号）。不能反映程序的局部性，命中率低。 2 2）FIFOFIFO替换算法：替换算法：最早进入实存的页替换出去，出现 了“历史”信息，但并没能正确反映程序的局部性。 3 3）LRULRU替换算法：替换算法：近期最少使用（Least Recently Used），替换最久未被使用的页面。 4 4）OPTOPT优化替换算法：优化替换算法：是一种理想的算法, ,实现不了， 只能作为衡量其它算法优劣的标准。 计算机体系结构第四章 二、地址流，算法，调进替换页面变化时空图二、地址流，算法，调进替换页面变化时空图 1. 第一组地址流

34、A：2,3,2,1,5,2,4,5,3,2,5,2 1）几个符号 i：在主存中的普通页面 i：调入第i页； i：第i页命中(已在主存中的页面，重新被使用称命中) i#：第i页将被替换 n：主存页面数。 2）分别写出FIFO、LRU、OPT随时间推移页面变化示意 图（设n=3，主存开始为空）。 3）计算命中率H。 H=命中页数/访问时间 计算机体系结构第四章 2. 第二种地址流A :1,2,3,4,1,2,5,1,2,3,4,5 分析n对H的影响： n=3与4 。 计算机体系结构第四章 时间 t: 1 2 3 4 5 6 7 8 9 10 11 12 地址流 A替 换 算法 n 12341251

35、2345 H 3 1 1# 2 2# 3 4 3# 4# 1 1# 2 5 1# 2 5 1# 2 5 2# 5# 3 5# 3 4 3/12 FIFO 4 1 1 2 1# 2 3 1# 2 3 4 1# 2 3 4 2# 3 4 5 3# 4 5 1 4# 5# 1 2 1# 2 3 4 2# 3 2/12 3 1 1# 2 2# 3 4 3# 4# 1 1# 2 5 1 2# 5# 1 2 1# 2 3 2# 3# 4 2/12 LRU 4 1 1 2 1# 2 3 1 2# 3 4 1 2 3# 4 1 2 4# 1 2 5 4# 1 2 5 4# 1 2 5# 1# 2 3 2# 4

36、 3 4/12 3 1 1 2 # 1 2 # 1 2 4# 1 2 4# 1 2 # 1 2 5# 1# 2 5 2# 5 3# 5 3# 4 5 5/12 OPT 4 1 1 2 1 2 3 # 1 2 3 4# 1 2 3 4# 1 2 3 # 1# 2 3 5 1# 2 3 5 1# 2 3 5 2# 3 5 4 2# 3 5 6/12 计算机体系结构第四章 3. 3. 堆栈型替换算法堆栈型替换算法 利用堆栈技术，真实模拟真实模拟LRULRU在不同在不同n n条件下页面变条件下页面变 化时空图及命中率化时空图及命中率: : 调入的页面放入栈顶，栈中其余页面均向栈底方向 移动一个单元。

37、处于栈中的页面命中时，将它从栈中抽出放在栈顶， 处于它之上的页面同时向栈底挪动一个单元。 计算机体系结构第四章 例：也用上次的第二组地址流模拟n=3、4、5， 此外，用3行分别描述命中页。 123412512345 1 3 2 1 4 3 2 1 4 3 2 1 4 5 2 1 1 5 2 2 1 5 3 2 1 4 3 2 5 4 3 123444512 地址流A: 栈顶 n=3栈底 n=4栈底 n=5栈底 333451 命中率 n=3122/12 n=412124/12 n=512123457/12 2 t 1 2 3 4 5 6 7 8 9 10 11 12 1 计算机体系结构第四章 三

38、、三、LRULRU算法的实现算法的实现 1.1.堆栈法堆栈法 1）设置，需要有一定容量的堆栈。 2）替换页面的条件，处于栈底的页面将被替换。 3）堆栈功能要求： 相联比较； 全下移及部分下移； 从中间取出一项。 4）用处 当采用存贮器堆栈时，用于主-辅存体系中； 当采用寄存器堆栈时，用于C-主体系中。 计算机体系结构第四章 2.2.比较对法比较对法 1）设置 每两个页面设一个比较对触发器，比较对触发器的数 目N N与页面数P P的关系：N=PN=P* *（P-1P-1）/2/2 如P=3P=3时，N=3N=3，即有A A、B B、C C三个页面，触发器 为T TAB AB、T TACAC、T

39、TBCBC。( (左置 左置0 0，右置，右置1 1） 2）记录页面使用状况 0 表示 表示A页比页比B页更久未被使用页更久未被使用 T AB= 1 表示表示B页比页比A页更久未被使用页更久未被使用 0 表示表示A页比页比C页更久未被使用页更久未被使用 T AC= 1 表示表示C页比页比A页更久未被使用页更久未被使用 0 表示表示B页比页比C页更久未被使用页更久未被使用 T BC= 1 表示表示C页比页比B页更久未被使用页更久未被使用 Q Q TAB Q Q TAC Q Q TBC ALRUBLRUCLRU 访B 访C 访A 替换页面信号替换页面信号 计算机体系结构第四章 3）页面替换条件 A

40、页替换条件 A ALKU LKU=T =TAB AB * * T TAC AC B页替换条件 B BLKU LKU=T =TAB AB * * T TBC BC C页替换条件 C CLKU LKU=T =TAC AC * * T TBC BC 4）页面替换电路 触发器左输入端置0，触发器右输入端置1 T TAB AB表示 表示Q Q端的状态端的状态 5）用处：电路简单，速度快，在页面数不多的条件下， 替换条件形成快，可用于 C - 主体系中。 计算机体系结构第四章 一、虚拟存贮器一、虚拟存贮器 1.1.含义含义：将高速辅存伪装成主存来访问的一种体系结 构，称虚拟存贮器，在主辅存之间的信息调进与

41、调出 都由辅助机构自动完成。 2.2.主要结构主要结构 1）主存主存: :是CPU直接访问的存贮器。 2）辅存辅存：用来扩充访存空间。 3）地址寄存器地址寄存器（以页式管理为例）。 虚地址寄存器，存放虚地址； 实地址寄存器，存放实地址。 计算机体系结构第四章 4 4）页表机构（按映象规则安排）页表机构（按映象规则安排） 内页表，页面放在主存中的页表。内页表，页面放在主存中的页表。 外页表，页面放在辅存中的页表。外页表，页面放在辅存中的页表。 5 5）替换算法机构）替换算法机构 页面满否判别机构及页面满否判别机构及LRULRU替换算法机构替换算法机构 6 6）I/OI/O通道用来实现主辅存之间的

42、页面交换。通道用来实现主辅存之间的页面交换。 计算机体系结构第四章 3.3.虚拟存贮器的简单工作过程虚拟存贮器的简单工作过程 1）用虚地址中的NV去查内页表，并检查相应页表行中 装入位； 2）当装入位=1时，表示该页已在主存。 从该页表行中送出nV； 再将Nrnr；即完成命中时的NV Nrnv nr。 3）用变换好的nv nr实地址访问主存； 4）当装入位=0时，表示不命中。 此时要产生失页中断，CPU也要响应此失页中断， 且可在指令执行途中响应，若为多用户系统时还要产 生用户切换。 计算机体系结构第四章 5 5）再用）再用NvNv去查外页表，并查出该页在辅存中的位置。去查外页表，并查出该页在

43、辅存中的位置。 6 6）查主存装满页面否？）查主存装满页面否？ 7 7）当主存页面未满时（主存有空页），将辅存页面经）当主存页面未满时（主存有空页），将辅存页面经 I/OI/O通道调入到主存的页面上。通道调入到主存的页面上。 8 8）当主存已装满时，利用）当主存已装满时，利用LRULRU替换算法机构算出调出替换算法机构算出调出 主存的页面号。主存的页面号。 9 9）再将辅存页面经）再将辅存页面经I/OI/O通道调入到主存被替换的页面上。通道调入到主存被替换的页面上。 注：通常主存中的页面是辅存中某些页面的副本，但当它注：通常主存中的页面是辅存中某些页面的副本，但当它 从辅存调到主存时，若有修改

44、，且需保存修改，还应先将从辅存调到主存时，若有修改，且需保存修改，还应先将 被替换的页面经被替换的页面经I/OI/O通道调回到辅存保存，然后再调入。通道调回到辅存保存，然后再调入。 计算机体系结构第四章 计算机体系结构第四章 4.4.性能评价性能评价 除命中率H H外，还有存贮空间利用率： =(Ss-Su)/Ss=(Ss-Su)/Ss 其中SsSs：分配给某用户的所有存贮单元数； SuSu：开销，包括所有页表单元数及最后一页未用完最后一页未用完 的零头，通常用的零头，通常用1/21/2页面容量页面容量SpSp表示表示。 计算机体系结构第四章 例：某虚存空间共有2 2 2020 个虚页面，页面容

45、量 Sp=512Sp=512，若某用户占据整个虚存空间，采用页 式管理，全部页表均在主存，计算存贮空间利 用率。 解： Ss=Ss=220512=229 Su=Su=220+(22029)+(22029) 29+ Sp /2 =220+211+22+28 =( Ss- Su)/ Ss=( Ss- Su)/ Ss =229-(220+211+22+28)229 511/512 计算机体系结构第四章 二、二、CacheCache主存体系主存体系 1.1.与虚拟存储器相同之处与虚拟存储器相同之处 1）都属于存储体系结构。 2）都有地址映象及其变换机构。 3）都有替换算法机构，且都采用LRU算法。 4） 都要求有高的命中率H。 2.2.不同之处不同之处 计算机体系结构第四章 3.t tA A的计算 t t