第三章存储系统4-4

1、13.4.2 多模块交叉存储器 1. 1.存储器的模块化组织存储器的模块化组织 一个由若干模块组成的主存储器是线性编址。地址在各模块安排方式有两种方式： 顺序方式和交叉方式顺序方式和交叉方式。 在常规主存储器设计中，访问地址采用顺序方式，图3.17(a)所示。2设存储器容量为32字，分M0-M3四个模块，每个模块存储8个字。访问地址按顺序分配给一个模块后,接着又按顺序为下一个模块分配访问地址.存储器的32个字可由5位地址寄存器指示，高2位选择4个模块中的一个，低3位选择每个模块中的8个字。在顺序方式中某个模块进行存取时，其他模块不工作。而某一模块出现故障时，其他模块可以照常工作，另外通过增添模

2、块来扩充存储器容量也比较方便。缺点缺点:是各模块一个接一个串行工作，因此存储器 的带宽受到了限制。3图3.17(b)表示采用交叉方式寻址的存储器模块化组织示意图。存储器容量也是32个字，也分成4个模块，每个模块8个字。但地址的分配方法与顺序方式不同：将4个线性地址0,1,2,3依次分给M0,M1,M2,M3模块，再将线性地址4,5,6,7依次分配给M0,M1,M2,M3直到全部线性地址分配完毕为止。当存储器寻址时，用地址寄存器的低2位选择4个模块中的一个，用高3位选择模块中的8个字。4用地址码的低位字段经过译码选择不同的模块,高位字段指向相应模块内的存储字. 连续地址分布在相邻的不同模块内,同

3、一个模块内的地址都是不连续。 对连续字的成块传送,交叉方式的存储器可以实现多模块流水式并行存取,大大提高存储器的带宽。 CPU的速度比主存快，同时从主存取出n条指令,必然会提高机器的运行速度。5 2.多模块交叉存储器的基本结构 图3.18示出了四模块交叉存储器结构框图。主存被分成4个相互独立、容量相同的模块M0,M1,M2,M3，每个模块都有自己的读写控制电路、地址寄存器和数据寄存器，各自以等同的方式与CPU传送信息.如果程序段或数据块都是连续地在主存中存取，将大大提高主存的访问速度。6CPU同时访问四个模块，由存储器控制部件控制它们分时使用数据总线进行信息传递。 对每一个存储模块来说，从CP

4、U给出访存命令直到信息仍然使用了一个存取周期时间，而对CPU来说，它可以在一个存取周期内连续访问四个模块。 各模块的读写过程将重叠进行，多模块交叉存储器是一种并行存储器结构。7 下面作定量分析下面作定量分析。设模块字长等于数据总线宽度，设模块存取一个字的存储周期为T，总线传送周期为r，存储器的交叉模块数为m，为了实现流水线方式存取应当满足：T=mr 成块传送可按r间隔流水方式进行,也就是每经r时间延迟后启动下一个模块。图3.31示出了m=4的流水线方式存取示意图。8 m=T/r 称为交叉存取度。交叉存储器要求其模块数必须大于或等于m以保证启动某模块后经mr时间再次启动该模块时，它的上次存取操作

5、已经完成。连续读取m个字所需的时间为:t1=T+(m-1)r顺序方式存储器连续读取 m个字所需时间为t2=mT从以定量分析可知，由于t1t2，交叉存储器的带宽确实大大提高了。9（例（例4 4）设存储器容量为）设存储器容量为3232字，字长字，字长6464位，模块数位，模块数 m=4m=4，分别用，分别用顺序方式和交叉方式进行组织。存储周期顺序方式和交叉方式进行组织。存储周期 T=200nsT=200ns，数据总，数据总线宽度为线宽度为6464位，总线传送周期位，总线传送周期 r=50ns r=50ns 问顺序存储器的交叉问顺序存储器的交叉存储器的带宽各是多少？存储器的带宽各是多少？ 解：顺序存

6、储器和交叉存储器连续读出m=4个字的信息总量都是： q=64位4256位顺序存储器和交叉存储器连续读出4个字所需的时间分别是： t2=mT=4 200 ns= 800 ns=8 10-7 s t1=T+(m-1)r=200ns+3 50ns=350ns=3.5 10-7 s 顺序存储器和交叉存储器的带宽分别是：W2=q/t2=256/(8 10-7 )=32 10-7 位/s W1=q/t1=256/(3.5 10-7 )=73 10-7 位/s103.二模块交叉存储器举例 下图，每个模块的容量为256K32位，有8片256 K4位的DRAM芯片组成。存储器的总容量为2MB（512K32位）.

7、数据总线宽度为32位,地址总线宽度为24位。11DRAM存储器有读周期、写周期和刷新周期.存储器读/写周期时,在行选信号RAS有效下输入行地址，在列选通信号CAS有效下输入列地址，于是芯片中行列矩阵中的某一位组被选中。如果是读周期，此位组内容被读出；如果是写周期，将总线上数据写入此位组。刷新周期是在RAS有效下输入刷新地址，此地址指示的一行所有存储元全部被再生。刷新周期比读/写周期有高的优行权，当对同一行进行读/写与刷新操作时，存储控制器对读/写请求予以暂存，延迟此行刷新结束后再进行。1224位的存储器物理地址指定的系统主存总容量可达16MB，按“存储体块字”进行寻址。其中高3位用于存储体选择

8、，全系统有8个2MB存储体A20A3的18位地址用于模块中256K个存储字的选择。读/写周期时，它们分为行、列地址两部分送至芯片的9位地址引脚。一个块内所有芯片的RAS引脚连接到一起，模块0由RAS0驱动，模块1由RAS1驱动。在读/写周期时，A2 用于模块选择，连续的存储字(32位，双字)交错分存在两个模块上，偶地址在模块0，奇地址在模块1。CPU给出的主存地址中没有A1、A0位。替代的是4个字节允许信号BE3-BE0，允许对A23-A2指定的存储字(双字)中的字节或字完成读/写访问。当BE3-BE0全有效时，完成双字存取。13 DRAM存储器需要逐行定时刷新，防止存储信息的电容漏电而造成信

9、息丢失。 DRAM芯片的读出是一种破坏性读出，在读取之后要立即按读出信息予以充电再生。若CPU先后两次读取的存储字使用同一RAS选通信号，CPU在接收到第一个存储字之后必须插入等待状态，直至前一存储字再生完毕才开始第二个存储字的读取。图3.33是无等待状态成块存取示意图。由于采用m=2的交叉存取度的成块传递，两个连续地址字的读取之间不必插入等待状态，称为零等待存取。14153.4.3 相联存储器1.相联存储器的基本原理 相联存储器是按内容访问的存储器。 相联存储器 指其中任一存储项内容作为地址来存取的存储器用来寻址存储器的子段叫做关键字关键字，简称为键键。16 相联存储器的基本原理 把存储单元

10、所存内容的某一部分作为检索项(关键字)，去检索该存储器，并将存储器中与该检索项符合的存储单元内容进行读出或写入。172.相联存储器的组成相联存储器 存储体 检索寄存器 屏蔽寄存器 符合寄存器 比较线路 代码寄存器 控制线路18(1)检索寄存器检索寄存器检索寄存器:用来存放检索字。检索寄存器的位数和相联存储器的存储单元位数相等(n位)，每次检索时，取检索寄存储器中若干位为检索项。19(2)屏蔽寄存器：屏蔽寄存器用来存放屏蔽码。屏蔽寄存器的位数和检索寄存器位数相同。20(3)符合寄存器 符合寄存器用来存放按检索项内容检索存储体中与之符合的单元地址。 (4)比较线路 比较线路是把检索项和从存储体中读

11、出的所有单元内容的相应位进行比较，如果有某个存储单元和检索符合，就把符合寄存器的相应位置“1”，表示该字已被检索。(5)代码寄存器 代码寄存器用来存放存储体中读出的代码，或者存放向存储体中写入的代码。21(6)存储体 用高速半导体存储器构成,以求快速存取。 相联存储器作用 用于虚拟存储器中存放分段表、页表和快表； 在高速缓冲存储器中，相联存储器作为存放cache的行地址之用。223.5 Cache存储器 3.5.1 Cache基本功能与原理1. Cache1. Cache的功能的功能解决CPU和主存之间速度不匹配速度不匹配采用的一项重要技术。主存的缓冲存储器，由高速的SRAM组成。23242.

12、Cache的基本原理图3.36 Cache 原理图253.5.2 主存与cache的地址映射地址映射: 为了把主存块放到cache中, 采用某种方法把主存地址定位到cache中. 地址映射方式全相联方式全相联方式: :一对多一对多直接方式：多对一直接方式：多对一组相联方式：组对应，组内行任意组相联方式：组对应，组内行任意261.全相联映射方式（一对多）一对多）主存的数据块大小称为块cache的数据块大小称为行将主存中一个块的地址（块号）与块的内容（字）一起存于cache的行中，块地址存于cache行的标记部分中。全部标记用一个相联存储器保存全部数据用一个普通RAM保存27全相联映射 主 存 c

13、 a c h e图3 - 2 3 全 相 联 映 象第0 块第1 块第0 块第1 块第N - 1 块第M N - 1 块28全相联映射 特点： （一对多）主存的一个块直接拷备到中cache任意一行。 缺点： 比较器电路难于设计和实现。全相联映射：只适合于小容量cache采用。29不相等块失效 块表 0 1 -1主存地址块内地址cache地址主存块号块内地址比较块号相联查找cache块号主存块号标志302.直接映射方式 (多对一)是一种多对一的映射关系，一个主存块只能拷贝到cache的一个特定行位置上去。Cache的行号I和主存的块号j有如下函数关系： I=j mod m 主 存 c a c h

14、 e第0 块第1 块第0 块第1 块第N - 1 块第 ( M - 1 ) N块第N - 1 块第 ( M - 1 ) N - 1 块第M N - 1 块第0 区第M - 1 区图3 - 2 0 c a c h e 的 直 接 相 联 映 象31不相等块失效图 3-21 直接映象的地址变换方法块内地址主存地址cache地址块表0按块号查找N-1主存区号标志访问cache主存块号区号块内地址比较块号323.组相联映射方式 组相联映射方式是全相联映射和直接映射两种方式的折衷方案。组对应，组内行任意组对应，组内行任意 主 存 c ac he图 3- 26 组 相 联 映 象第 0 块第 0 组第 0

15、 区第 0 组第 1 组第 1 组第 0 组第 M -1 区第 1 组第 0 块第 N-1 块第 (M -1)N 块第 N-1 块第 M N -1 块33不相等块失效 块表 0 N-1图3-27 组相联映象的地址变换方法主存地址块内地址cache地址组号块内地址比较组内相联查找cache块号主存块号标志区号标志块号区号组号主存块号343.5.3 替换策略及更新策略 常用替换算法：最不经常使用（LFU）算法近期最少使用(LRU)算法随机替换FIFO算法（先进先出）351.最不经常使用（LFU）算法原理：原理：将一段时间内被访问次数最少的那行数据换出。实现过程：实现过程：每行设置一个计数器。新行建

16、立后从0开始计数，每访问一次，被访问的计数器增1。当需要替换时，对这些特定行的计数值进行比较，将计数值最小的行换出，同时将计数器清零。缺点：缺点：这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，不能严格反映近期访问情况。362. 近期最少使用(LRU)算法原理：原理：将近期内长久未被访问过的行换出。实现过程：实现过程：每行设置一个计数器，但是Cache每命中一次，命中行计数器清零，其它各行计数器增1。当需要替换时，比较各特定行的计数器，将计数值最大的行换出，这种算法保护了刚进入cache中的新数据行。特点：特点：符合cache工作原理，使cache有较高的命中率。373. 随机替

17、换 原理： 从特定行位置中随机地选取一行换出即可。 实现过程： 从特定行中随机地选取一行。 特点： 在硬件上容易实现，速度也比前两种策略快。 但随意换出的数据很可能马上以要使用， 从而降低命中率和cache工作效率。384. FIFO算法 原理：选择最早装入cache中的页作为被替换的页。 实现过程每一个页都与一个“装入顺序数”相联系，每当一个页送入cache或从cache中取出时，更新“装入顺序数”。检查这些数,就可以决定最先进入的页 特点：在硬件上容易实现，但经常使用的页也有可能由于它是最早的页而被替换。393.5.4 Cache的写操作策略三种写操作策略:写回法 当CPU写cache命中

18、时，只修改Cache的内容，而不立即写入主存。只有当此行被换出时写回主存。全写法 当写cache命中时cache与主存同时发生写修改。写一次法 写命中与写未命中的处理方法与写回法基本相同只是第一次写命中时要同时写入主存。40 3.5.5 奔腾PC机的Cache 奔腾PC机是一单CPU系统，它采用两级cache结构安装在主板上的2级cache(L2)，其容量是512KB采用2路组相联映射方式,每行可以是32B，64或128B集成在CPU内的1级cache(L1)，其容量是16KB，采用的也是2路组相联映射方式，每行是32B。 CPU中的L1分设成各8KB的指令cache和数据Cache这种体系结

19、构有利于CPU高速执行程序41 CPU与外部数据交换时存储器读写总线周期主要有两类： 一类是256位狡发式传送，用于L1的行填入和行写出。 另一类是不经L1的64位(或32位，16位，8位)传送，此时CHACE#为高电平，称为非超高速缓存式传送。42图3.42 奔腾两极Cache 工作环境43 L2级cache采用的是写回法， L1级数据cache采用的是写一次法。 为了维护cache的一致性，L1和L2均采用MESI协议。44 3.6 3.6 虚拟存储器虚拟存储器 3.6.1 基本概念 虚拟存储器：虚拟存储器：只是一个存储器的逻辑模型而不是任何实际的物理存储器，它借助于磁盘等辅助存储器来扩大

20、主存容量，使之为更大的程序所使用。 虚拟地址虚拟地址：程序的逻辑地址。 虚拟地址空间虚拟地址空间：程序的逻辑地址空间。 物理地址物理地址：由CPU引脚送出，它用于访问主存的地址。 主存主存- -外存的基本信息传送单位：外存的基本信息传送单位：有段,页或段页三种。451.段式管理：把主存按段分配的存储管理方式。 优点优点： 1.段的分界与程序的自然分界对应。 2.段的逻辑独立性使它易于编译,管理,修改保 护，也便于多道程序共享。 3.某些类型的段(堆栈，队列)具有动态可变长 度，允许自由调度以便有效利用主存空间 缺点：缺点： 1.由于段的长度各不相同，段的起点和终点不 定，给主存空间分配带来麻烦

21、。 2. 产生碎片，造成浪费。462.2.页式管理页式管理 ：传送信息的基本是页。 优点优点：1.页面的起点和终点地址固定2.产生碎片小，造成浪费少。 缺点：缺点：由于页不是逻辑上独立的实体，所以处理，保护和共享都不及段式来得方便。3.3.段页式管理：段页式管理：采用分段，分页管理。特点特点：程序按模块分段，段内再分页，进入主存仍以页以为基本信息传送单位，用段表各页表进行两级定位管理。473.6.2 页式虚拟存储器 逻辑页逻辑页：在页式虚拟存储系统中， 把虚拟空间分成页。 物理页物理页:在主存空间也分成同样大小的页。 虚存地址：虚存地址：48虚存地址与物理存储之间关系主 存 页 号 主 存 地

22、 址 空 间 虚 存 页 号 程 序 地 址 空 间013240127491. 页式虚拟存储器的地址映象过程页内地址页内地址实页号虚页号基号 2 1 6 1(b) 地址映象方法主存页号 装入位 - 0 7 1 - 0 5页表长度 页表基址虚地址实地址页表页基址表0502. 2. 虚拟地址到主存实地址的变换是由放在主存的页表来实现页表逻辑页号物理页号装入位(有效位)修改位替换控制位保护位513. 快表和慢表实现内部地址变换 快表 把页表的活跃部分放在高速存储器中组成快表，快表只是慢表的一个小小副本。 过程查表时，由逻辑页号同时去快表和慢表，当在快表中有此逻辑页号时，就能很快地找到对应的物理页号送

23、入实主存储地址寄存器，并使慢表的查找作废，就能做到虽采用虚拟存储器但访问主存速度几乎没有下降。52如果在快表中查不到，那就要费一个访问主存时间查慢表，从中查到物理页号送入实主存地址寄存器，并将此逻辑页和对应的物理页号送入快表，替换快表中应该移掉的内容，要用替换算法。53 虚地址 快表 慢表 实地址 0 0 相 . 1 联 查 N-1 2 找 实页号 装入位 用户标志 虚页号 实页号 图3-43 用快表和慢表实现的内部地址变换 页内地址 虚页号 基号 543.6.3 段式虚拟存储器 段页式虚拟存储器的作用：分隔地址空间；解决主存容量；程序的重定位； 段式虚拟存储器地址结构：55段式虚拟存储器的地

24、址变换过程 主存地址空间 程序地址空间 1000 3000 (a) 地址映象关系 0 0 . 1 N-1 2 段表长度 段表基址 段基址 装入位 段长 访问方式 (b) 地址映象方法 图 3-44 段式虚拟存储器 0 段 1 段 2 段 段内地址 段号 基号 - 0 1K 3000 1 2K 1000 1 1K 3 虚地址 实地址（相加形成） 段表 段基址表 563.6.4 段页式虚拟存储器 段页式虚拟存储器是段式虚拟存储器段式虚拟存储器和页式虚页式虚拟存储器拟存储器的结合。 在这种方式中，把程序按逻辑单位分段以后，把程序按逻辑单位分段以后，再把每段分成固定大小的页。再把每段分成固定大小的页。

25、 程序对主存的调入调出调入调出是按页面按页面进行的，但它又可以按段实现共享和保护按段实现共享和保护。 在段页式虚拟存储系统中，每道程序是通过一个段表和一组页表来进行定位的。57段页式虚拟存储器的地址变换过程：(a) 地址映象关系 段基址表 段表 页表 0 0 0 . N-1 L-1 M-1 段表长度 段表基址 装入位 段长 页表地址(b) 地址映象方法页内地址页内地址页号页号段号基号 1 M 1 L主存地址空间程序地址空间A 段B 段虚地址实地址58例 ：假设有三道程序(用户标志号为A,B,C)其段表指明该段页表的起始地址为Sa,Sb,Sc,逻辑地址到物理地址的变换过程如下在主存中，每道程序都

26、有一张段表，A程序有4段，C程序有3段。每段应有一张页表，段表的每行就表示相应页表的起始位置而表内的每行即为相应的物理页号。59 上图地址变换过程如下：1. 根据基号C，执行Sc(基址寄存器内容)加1(段号)操作，得到段表相应行地址，其内容为页表的起始地址b.2. 执行b(页表起始地址)+2(页号)，得到物理页号地址，其内容即为物理页10。3. 物理页号与页内地址拼接即得物理地址。段页式虚拟存储系统由虚拟地址向实主存地址的变换至少需要查两次表(段表与页表)。段页表构成表层次。表层次不只段页式有，页表也会有，因为整个页表是连续，当一上页表的大小超 过一个页面的大小时，页表就可能分成几个页。形成了

27、二级页表层次。一个大的程序可能需要多级页表层次。对于多级表层次，在程序 运行时，除了第一级页表需驻留在主存这外，整个页表中只需有一部分是在主存中，大部分可存于外存，需要时再由第一级页表调入，可减小每道程序占用的主存空间。60 3.6.5 替换算法替换算法：替换算法： 当产生缺页，而主存页面已全部占满，此时用什么规则来替换主存的哪一页，就是替换算法替换算法。虚拟存储器中的页面替换和缓冲中行替换策略 不同之处：缺页至少要涉及前一次磁盘存取，因此缺页使系统蒙受的损失要比缓冲未命中大得多。 页面替换是由操作系统软件实现的；页面替换的选择余地很大，属于一个进程的页面都可替换。61 对于将被替换出去的页面

28、进行的处理：对于将被替换出去的页面进行的处理：由于在外存中留有副本，假如该页调入主存后没有被修改过，那么就不必进行处理否则就应把该页面重新写入外存，以保证外存中数据的正确性。为此在页表的每一行可设置一修改位当该页刚调入主存时，此位为0，当对该页面任一地址进行写入时，就把该位改1。在该页被替换时，检查其修改位，如为1，则先将该 页内容从主存写入外存，然后再从外存接改新一页 在虚拟存储器中，为了实现逻辑地址到物理地址在虚拟存储器中，为了实现逻辑地址到物理地址的变换并在页面失效时进入操作系统环境的变换并在页面失效时进入操作系统环境，设置了由硬件实现的存储管理部件MMU。62例：假设主存只有例：假设主

29、存只有a,b,ca,b,c三个页框，组成三个页框，组成a a进进c c出的出的FIFOFIFO队列，队列，进程访问页面的序列是进程访问页面的序列是0,1,2,4,2,3,0,2,1,3,20,1,2,4,2,3,0,2,1,3,2号。号。 若采用若采用1)FIFO1)FIFO算法，算法， 2) FIFO2) FIFO算法算法+LRU+LRU算法，用列表法分算法，用列表法分别求两种替换策略情况下的命中率别求两种替换策略情况下的命中率 解：求解表格如下。FIFO算法只是依序将页面在队列推进，先进先出，最先进入队列的页面由C页框推出(被替换掉)。当命中后不再保持队列不变，而是将这个命中的页面移到a页

30、框。从表中看出命中2次故命中率为18.2%。 当FIFO算法结合LRU算法时，当命中后不再保持队列不变，而是将这个命中的页面移到a页框。从表中看出命中3次，使命中率提高到27.3%。63643.6.6 虚拟存储器实例1.奔腾奔腾PCPC的虚地址模式的虚地址模式 奔腾PC的存储管理部件MMU包括： 分段部件SU 分页部件PU 1)1)分段不分页模式分段不分页模式虚拟地址(逻辑地址)由一个16位的段参照和一个32位的偏移组成。段参照的最低2 位与保护机构打交道，高14位用于指定具体的段。一个进程拥可有的最大虚拟地址空间是2=64TB。分段部件SU将二维的分段虚拟地址转换成一维的32位红性地址也就是

31、主存的物理地址。 优点优点：无需访问页目录和页表地址,转换速度快另外，对段提供的一些保护定义，可以一直贯通到段的单个字节级。652)2)分段分页模式分段分页模式 这是一种在分段基础一增加分页存储管理的模式。将SU部件转换后的32位线性地址看由页目录，页表页内偏移三个字段组成，再由PU部件完成两 级页表的，将其转换页换成32位物理地址。 一个进程可拥有的最大虚拟地址空间也是64TB。优点优点：这种模式兼顾分段和分页两种方式的优点。3)3)不分段分页模式不分段分页模式 这种模式下SU不工作，只是PU工作。程序也不提供段参照，寄存器提供的32位地址被看成是由页目录，页表，页内偏移三个字段组成。由PU

32、完成虚拟地址到物理地址的转换。进程所拥有的最大虚拟地址空间是4GB。662.2.保护模式的分页地址转换保护模式的分页地址转换两种分页方式：一种有4KB的页，使用二级页表(页目录，页表)进行地址转换. 一种是新增加的方式，采用4MB的页，使用单级页表进行地址转换。页面（页框）大小为4MB的分页方式单级页表，由于只进行一次主存访问，地址转换过程加快了。674MB分页方式，其地址转换过程示如下：683.7 3.7 存储保护存储保护 当多个用户共享主存时，就有多个用户程序和系统软件存于主存中。为使系统能正常工作，系统应提供存储保护，防止由于一个用户系统应提供存储保护，防止由于一个用户程序出错而踊坏其他用户的程序和系统软件，程序出错而踊坏其他用户的程序和系统软件，还要防止一个用户程序不合法地访问不是分配还要防止一个用户程序不合法地访问不是分配给它的主存区域。给它的主存区域。通常采用的方法是存储区域保护存储区域保护和访问方访