《数据结构域算法设计计算机系统结构(第四讲)》由会员分享，可在线阅读，更多相关《数据结构域算法设计计算机系统结构(第四讲)（93页珍藏版）》请在金锄头文库上搜索。
1、计算机系统结构 (第四讲)厦门大学计算机科学系 陆达 2004年10月18日第三章 存储系统3.2 虚拟存储器1961年，Kilbrn提出虚拟存储器，虚拟存储系统，虚拟存储体 系基本工作原理，地址映象和变换方法，页 面替换算法，加速地址变换速度的方法3.2.1 虚拟存储器工作原理页式虚拟存储器 页（page）图3.16：虚拟存储器中的地址组成 实页（主存储器的页）主存地址A=实页号p+页内偏移d 虚页（虚拟存储器的页）虚地址Av=用户号U+虚页号P+页内偏移D图3.17：页式虚拟存储器工作原理变换成功（命中） 变换失败（未命中） 内部地址变换：虚页号P = 实页号p 外部地址变换：虚页号P =
2、 磁盘实地址页面替换算法（当主存储器中没有空页时 ）3.2.2 地址的映象与变换虚拟地址空间、主存地址空间、辅存地址 空间地址映象：把虚拟地址空间映象到主存地 址空间，即将用户用虚拟地址编写的程序 按照某种规则装入到主存储器中地址变换：在程序被装入主存储器后，在 实际运行时，把多用户虚地址变换成主存 实地址（内部地址变换）或磁盘存储器地 址（外部地址变换）3.2.2.1 段式虚拟存储器图3.18：地址映象段表：包括段号（或段名）、段长、起始 地址等图3.19：地址变换段表基址寄存器堆装入位、访问方式、修改标志字段段式虚拟存储器的主要优点：1）、程序的模块化性能好2）、便于程序和数据的共享3）、
3、程序的动态链接和调度比较容易4）、便于实现信息保护段式虚拟存储器的主要缺点：1）、地址变换所化的时间比较长2）、主存储器的利用率往往比较低3）、对辅存（磁盘存储器）的管理比较困难3.2.2.2 页式虚拟存储器页（page）：1page=0.5KB的整倍数=1KB16KB 虚页、实页地址映象：从虚页号到实页号的地址变换（图3.20）页表=页号+主存页号地址变换：将用户程序的虚拟地址变换成主存实地址（图3.21）多用户虚地址Av=用户号U+虚页号P+页内偏移D主存实地址A=实页号p+页内偏移d页表基址寄存器堆基址寄存器的内容=页表起始地址装入位、修改位、各种标志信息 页式虚拟存储器的主要优点：1）
4、、主存储器的利用率比较高2）、页表相对比较简单3）、地址映象和变换的速度比较快4）、对辅存（磁盘存储器）的管理比较容易页式虚拟存储器的主要缺点：1）、程序的模块化性能不好2）、页表很长虚拟存储空间=4GB、1页=1KB页表的容量=4M存储字（4GB/1KB）=4M*4B=16MB3.2.2.3 段页式虚拟存储器综合段式虚拟存储器在程序模块化方面的优点 和页式虚拟存储器在管理主存和辅存物理空间 方面的优点 基本思想是：对用户用来编写程序的虚拟存储 空间采用分段的方法管理，而对主存储器的物 理空间采用分页的方法管理地址映象：图3.22段表=页表长度+页表地址页表=主存的实页号地址变换：图3.23多
5、用户虚地址Av=用户号U+段号S+虚页号P+页 内偏移D主存地址A=实页号p+页内偏移d段表基址寄存器堆、段表、页表IBM 370/168、Multics、Amdahl470V/6等采用段 页式虚拟存储器段页式虚拟存储器的缺点：要从主存储器中访问 一个数据，需要查二次表，访问主存储器三次3.2.2.4 外部地址变换当发生页面失效时（未命中），必须进行外部地 址变换 外部地址变换：虚地址 = 辅存的实地址页面失效属于异常故障，保存和恢复故障点的现 场的方法有三个：（1）、采用硬件的缓冲寄存器（2）、只保存部分现场（如PC、PSW等）（3）、采用指令预判技术磁盘存储器的地址=磁盘号+柱面号+磁头
6、号+块号（图3.24）图3.25：外部地址变换，通常用软件实现外页表=磁盘实地址+装入位多级页表技术（见3.2.3小节）外页表与内页表合并成一个页表3.2.3 加快内部地址变换的方法造成虚拟存储器速度降低的主要原因：（1）、要访问主存储器，必须先查段表或页表或段页表（2）、页表或段表的容量超过一个页面时，需采用多级页 表技术，从而又增加了查页表（段表）的次数多级页表技术：g：页表的级数 Nv：虚拟存储空间的大小Np：页面的大小Nd：页表存储字的大小例如：Nv=4Gb、Np=1KB、Nd=4Bg=3第一级页表：1个页面，64个存储字（64*4B=256BCache地址变换部件完成B变换成b变换成
7、功，称为Cache命中 变换不成功，产生Cache失效信息将被访问字在内的一整块都从主存储器中读出来 （利用程序的局部性特点，提高Cache的命中率 ）3.3.2 地址映象与变换算法什么是Cache的地址映象？ 什么是Cache的地址变换？以“块”为单位进行调度需要考虑的因素：（1）、地址变换的硬件是否容易实现？（2）、地址变换的速度是否快？（3）、主存空间的利用率是否高？（4）、发生块冲突的概率如何？3.3.2.1 全相联映象及其变换全相联映象方式是指主存中的任意一块可以映象 到Cache中的任意一块的位置上。图3.39：全相联映象方式 Cb = Mb 图3.40：全相联映象方式的地址变换主
8、存地址=块号B+块内地址W Cache地址=块号b+块内地址w 目录表=主存块号B+Cache块号b+有效位Cache命中 Cache没有命中（ Cache失效）全相联映象方式的优点：块的冲突率 最小，Cache的利用率也最高 全相联映象方式的缺点：需要一个相 联访问速度快、容量为Cb的相联存储 器，其代价很高；相联比较所花费的 时间将影响Cache的访问速度3.3.2.2 直接映象及其变换直接映象方式：主存中一块只能映象到Cache的一个特定 的块中。b=B mod CbB：主存的块号b：Cache的块号Cb：Cache的块容量（个数）图3.41：直接相联映象方式Mb=Cb*MeMb：主存的
9、块容量（个数）Cb：Cache的块容量（个数）Me：主存的区容量（个数）图3.42：直接相联地址变换主存地址=区号E+块号B+块内地址WCache地址=块号b+块内地址w区表存储器=区号E（按地址访问）+有效位四种情况：（1）、区号比较结果相等、有效位为“1”：Cache命中（2）、区号比较结果相等、有效位为“0”：Cache没有命中；Cache中的这一块已经作废 （3）、区号比较结果不相等、有效位为“0”：Cache没有命中；Cache的这一块是空的（4）、区号比较结果不相等、有效位为“1”：Cache没有命中；原来在Cache中存放的那一 块是有用的图3.43：将区号存储器与Cache合并
10、成一个 存储器直接相联映象方式的优点：硬件实现很简 单，不需要采用相联访问的存储器，访问 速度也比较快 直接相联映象方式的缺点：块的冲突率比 较高。3.3.2.3 组相联映象及其变换 介于全相联和直接相联之间的一种折中方案图3.44：组相联映象方式Cache： Cb=Cg*GbCb：Cache总的块容量（个数）Cg：Cache的组容量（个数）Gb：Cache每一组的块容量（个数）主存储器： Mb=Gb*Cg*MeMb：主存储器总的块容量（个数）Gb：Cache每一组的块容量（个数）Cg：Cache的组容量（个数）Me：主存储器的区容量（个数）图3.45：组相联映象方式的地址变换主存地址=区号E
11、+组号G+组内块号B+块内地址WCache地址=组号g+组内块号b+块内地址w快表存储器=（区号E，组内块号B）+组内块号b（采用按地址访问和按相联访问两种方式）图3.46：采用多个相等比较器代替相联访问，以 加快查表的速度当一个块内的字数不多时，可以把块表与Cache 合并成一个存储器。即用Cache中的数据字代替 块表中的块号b字段（参见P178的图3.43）组相联映象方式与直接映象方式相比：Cache 中块的利用率能够大幅度提高，Cache块的失 效率能够明显降低，块的冲突概率大大降低。 但是，实现的难度和造价要高。 组相联映象方式与全相联映象方式相比：实现 起来容易，Cache的命中率
12、与全相联映象方式 很接近。当Gb=1（Cache每一组的块容量（个数）时 ，就成了直接映象方式 当Cg=1（Cache的组容量（个数）时，就成 了全相联映象方式可以通过选择Gb和Cg，来优化Cache的性能 （包括块冲突率、块的失效率、查表的速 度、实现的复杂性和成本等）Gb越大，块的冲突概率和Cache的失效率就 越低，但查表的速度就越慢，实现的成本 也就高表3.5：典型机器的Cache分组情况（Cb=Cg*Gb）3.3.2.4 位选择组相联映象及其变换图3.47：位选择组相联映象方式（主存不再分组）Cache：Cb=Cg*GbCb：Cache总的块容量Cg：Cache的组容量Gb：Cach
13、e每个组的块容量主存储器：Mb=Cg*MeMb：主存总的块容量Cg：主存每个区的块容量Me：主存的区容量主存中的块与Cache中的组之间是直接映象 关系；而主存中的块与Cache中组内部的各 个块之间是全相联映象方式在组相联映象方式中，主存中的一个组与 Cache中的一个组之间是多个块到多个块的 映象 在位选择组相联映象方式中，主存中的一 个块到Cache中一个组之间是一个块到多个 块的映象图3.48：位选择组相联地址变换的一种实现 方式主存地址=区号E+区内块号B+块内地址WCache地址=组号g+组内块号b+块内地址w块表=（区号E+块号b+有效位e）+（ 区号E+块号b+有效位e）（共G
14、b个）3.3.2.5 段相联映象及其变换段相联映象方式：组内采用直接映象方式 ，而组间改用全相联映象方式是组相联映象方式的一种变形，也是介于 全相联和直接相联二种映象方式之间的一 种折中方案图3.49：段相联映象方式Cache：Cb=Sb*CsCb：Cache总的块容量Cs：Cache的段容量Sb：Cache每个段的块容量主存储器：Mb=Sb*MsMb：主存总的块容量Ms：主存的段容量Sb：主存每个段的块容量图3.50：段相联地址变换方式主存地址=段号S+段内块号B+块内地址WCache地址=段号s+段内块号b+块内地址w段表=主存段号S+Cache段号s+有效位段相联映象方式的优点：段表比较
15、简单，实现的成本相对比较低块的冲突概率和Cache的失效率与Cache的 段容量Cs有关段相联映象方式的缺点：当发生段失效，要把本段内各个块原来已 经与主存建立起来的许多映象关系全部撤 消例子：256KB的Cache：8个段、每段2048 块、每块16B（8*2048*16B=256KB）3.3.3 Cache替换算法及其实现什么是Cache替换算法？直接映象方式：不需要替换算法 全相联映象方式：替换算法最复杂 组相联映象方式/位选择组相联映象方式：需要从Cache同一组内的几个块中选择一块替换 出去虚拟存储器：采用全相联映象方式，替换算法用 软件实现 Cache：替换算法用硬件实现常用的Ca
16、che替换：随机法、轮换法、LFU算法、 比较对法、堆栈法3.3.3.1 轮换法及其实现用于组相联映象方式两种实现方法： （1）、每块一个计数器 （2）、每组一个计数器1、每块一个计数器在块表中，增加设置一个替换计数器字段，计数 器字段的长度与Cache地址中的组内块号字段的 长度相同替换规则：（1）、被装入或被替换的块，它所属的计数器清 为“0”，同组的其他块所属的计数器都加“1”（2）、需要替换时，在同组中选择计数器的值最 大的块作为被替换的块例子：Solar-16/65，位选择组相联映象方式，每 组的块容量=4，2位计数器（表3.6）2、每组一个计数器只为每个组设置一个计数器替换规则：本组有替换时，计数器加“1”，计数器的值 就是要被替换出去的块号轮换法的优点：实现比较简单，能
