第4章存储体系

1、一、虚拟存储器一、虚拟存储器1、三种存储管理方式（段式、页式、段页式）三种存储管理方式（段式、页式、段页式）2、加快内部地址变换加快内部地址变换 3、页面替换算法页面替换算法4、影响主存命中率的主要因素影响主存命中率的主要因素二、高速缓冲存储器（二、高速缓冲存储器（Cache）1、三种存储管理方式（全相联、直接映象、组相联）三种存储管理方式（全相联、直接映象、组相联）2、LRU块替换算法的实现块替换算法的实现3、Cache的性能分析的性能分析三、主存保护三、主存保护、掌握段式、页式、段页式、掌握段式、页式、段页式3种不同的虚拟存储管理方种不同的虚拟存储管理方式的工作原理，掌握其地址映像规则、映

2、像表机构、式的工作原理，掌握其地址映像规则、映像表机构、虚虚实地址变换的过程实地址变换的过程及各自的优缺点；及各自的优缺点；、掌握、掌握FIFO、LRU、OPT等替换算法进行页面替换的等替换算法进行页面替换的过程模拟以及过程模拟以及LRU替换算法对页地址流的替换算法对页地址流的堆栈处理模拟堆栈处理模拟及性能分析；及性能分析；、领会在虚拟存储器中对页面失效的处理及内部地址、领会在虚拟存储器中对页面失效的处理及内部地址映象表中的映象表中的快慢表机构快慢表机构。能分析虚拟存储器中，页面大。能分析虚拟存储器中，页面大小，分配给程序的主存容量与主存命中率的变化关系。小，分配给程序的主存容量与主存命中率的

3、变化关系。能够给出改进页式虚拟存储器等效访问速度的各种办法。能够给出改进页式虚拟存储器等效访问速度的各种办法。、了解、了解Cache存储器的组成、工作原理，并能与虚拟存储器进行比存储器的组成、工作原理，并能与虚拟存储器进行比较；较；、掌握、掌握Cache存储器中全相联、直接、组相联存储器中全相联、直接、组相联3种地址映象规则，相种地址映象规则，相应的映象表机构和应的映象表机构和虚、实地址变化过程虚、实地址变化过程；、领会、领会堆栈法堆栈法和和比较对法比较对法实现实现Cache块替换的原理，能计算出用比块替换的原理，能计算出用比较对法进行块替换时所用的比较对触发器的个数；较对法进行块替换时所用的

4、比较对触发器的个数；、给出主存的块地址流后，采用组相联或直接映象、给出主存的块地址流后，采用组相联或直接映象、LRU或或FIFO替替换算法时，能熟练画出各主存块装入换算法时，能熟练画出各主存块装入Cache和其被替换的过程示意图，和其被替换的过程示意图，并计算出并计算出Cache块的命中率；块的命中率；、理解为解决、理解为解决Cache存储器透明性问题存储器透明性问题所提出的各种算法以及为提所提出的各种算法以及为提高高Cache块命中率的各种预取算法。能分析影响块命中率的各种预取算法。能分析影响Cache性能的因素及其性能的因素及其变化规律。正确理解和分析变化规律。正确理解和分析Cache存储

5、器的等效访问速度与物理存储器的等效访问速度与物理Cache速度及速度及Cache容量、容量、Cache命中率的关系。命中率的关系。1、段式、页式、段页式、段式、页式、段页式3种不同的虚拟存储管理方式种不同的虚拟存储管理方式段式段式u在段式虚拟存储器系统中，段是在段式虚拟存储器系统中，段是按照程序的逻辑结构划分的按照程序的逻辑结构划分的u虚拟地址由段号和段内地址组成虚拟地址由段号和段内地址组成u为把虚拟地址变换成实主存地址，为把虚拟地址变换成实主存地址，需要一个段表需要一个段表u装入位为装入位为1表示该段已调入主存，表示该段已调入主存，为为0则表示该段不在主存中则表示该段不在主存中u因段的长度可

6、大可小，所以段表因段的长度可大可小，所以段表需要有长度指示需要有长度指示u段表也是一个表，一般驻留在主段表也是一个表，一般驻留在主存中存中优点：优点：1、支持了程序的模块化设计和并行编程的要求、支持了程序的模块化设计和并行编程的要求 ；2、便于多道程序共享主存中某些段、便于多道程序共享主存中某些段 ；3、便于按逻辑意义实现存储器的访问方式保护、便于按逻辑意义实现存储器的访问方式保护 。 缺点：缺点：1、段映象表机构太庞大，其地址字段和段长字段都太长；、段映象表机构太庞大，其地址字段和段长字段都太长；2、查表进行地址变换的速度太慢（从多用户虚地址变换到主存实、查表进行地址变换的速度太慢（从多用户

7、虚地址变换到主存实地址需要查两次表，做两次加法运算）；地址需要查两次表，做两次加法运算）；3、对主存各区域的存储管理十分麻烦；（对辅存（磁盘存储器）、对主存各区域的存储管理十分麻烦；（对辅存（磁盘存储器）的管理比较困难。磁盘存储器通常是按固定大小的块来访问的，的管理比较困难。磁盘存储器通常是按固定大小的块来访问的，如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要做一次地址变换。做一次地址变换。 ）4、主存储器的利用率往往比较低，存储器内部的段间零头浪费大，、主存储器的利用率往往比较低，存储器内部的段间零头浪费大，有时难以利用。有时

8、难以利用。因此，单纯的段式存储管理在实际的系统中无法采用。因此，单纯的段式存储管理在实际的系统中无法采用。页式页式u页式虚拟存储器把虚拟地页式虚拟存储器把虚拟地址空间划分成一个个固定址空间划分成一个个固定大小的块，每一块称为一大小的块，每一块称为一页（虚页），把主存储器页（虚页），把主存储器的地址空间也按虚拟地址的地址空间也按虚拟地址空间同样的大小划分为页空间同样的大小划分为页（实页）。页是一种逻辑（实页）。页是一种逻辑上的划分，它可以由系统上的划分，它可以由系统管理软件任意指定。管理软件任意指定。 u在页表中，对应每一个虚在页表中，对应每一个虚存逻辑页号有一个目录，存逻辑页号有一个目录，它至

9、少包含主存页面地址它至少包含主存页面地址u主存页面地址作为实存地主存页面地址作为实存地址的高字段，与虚存地址址的高字段，与虚存地址的行地址字段相拼接，产的行地址字段相拼接，产生完整的实主存地址，据生完整的实主存地址，据此访问主存。此访问主存。 01230123456703114260虚页号页内位移实页号页内位移4888=4*1024+792 2*1024+792=28401001100011000 101100011000实实页页号号装装入入位位3111203021100100优点：优点：1、主存储器的利用率比较高。每个用户程序只有不到一页（平均为、主存储器的利用率比较高。每个用户程序只有不到

10、一页（平均为半页）的浪费；半页）的浪费；2、页表相对比较简单。它需要保存的字段数比较少，一些关键字段、页表相对比较简单。它需要保存的字段数比较少，一些关键字段的长度要短许多，因此，节省了页表的存储容量；的长度要短许多，因此，节省了页表的存储容量；3、地址映象和变换的速度比较快；、地址映象和变换的速度比较快；4、对辅存的管理比较容易。、对辅存的管理比较容易。 缺点：缺点：1、程序的模块化性能不好；、程序的模块化性能不好；2、页表很长，需要占用很大的存储空间。（虚拟存储器中的每一页、页表很长，需要占用很大的存储空间。（虚拟存储器中的每一页在页表中都要占用一个存储字。假设有一个页式虚拟存储器，它的在

11、页表中都要占用一个存储字。假设有一个页式虚拟存储器，它的虚拟存储空间大小为虚拟存储空间大小为4GB，每一个的大小为，每一个的大小为1KB,则页表的容量为则页表的容量为4MB存储字。如果每个页表存储字占用存储字。如果每个页表存储字占用4个字节，则页表的存储容量个字节，则页表的存储容量为为16MB）段页式段页式段页式管理是将程序段页式管理是将程序按逻辑意义先分成段，按逻辑意义先分成段，再让各段和实主存都再让各段和实主存都机械等分成相同大小机械等分成相同大小的页面。每道程序通的页面。每道程序通过一个段表和相应的过一个段表和相应的一组页表来进行程序一组页表来进行程序在主存空间中的定位。在主存空间中的定

12、位。段页式存储管理和纯段页式存储管理和纯段式存储管理最主要段式存储管理最主要的差别是段的起点不的差别是段的起点不再是任意的，它必须再是任意的，它必须是位于主存中某个页是位于主存中某个页面的起点上。面的起点上。u段页式虚拟地址包括基号、段号、页号和页内地址段页式虚拟地址包括基号、段号、页号和页内地址u每个程序由若干段组成，而每一段又由若干页组成每个程序由若干段组成，而每一段又由若干页组成u如程序如程序A由四段组成，程序由四段组成，程序C由三段组成由三段组成u每段应有一张页表每段应有一张页表u程序程序C的地址转换过程如下：的地址转换过程如下：u根据基号根据基号C，执行，执行SC加加1操作，得到段表

13、相应行地址，其内容为页表的起始地址操作，得到段表相应行地址，其内容为页表的起始地址bu执行执行b加加2操作，得到物理页号的地址，其内容即为物理页号操作，得到物理页号的地址，其内容即为物理页号10u物理页号与页内地址拼装即得物理地址物理页号与页内地址拼装即得物理地址2、加快内部地址变换、加快内部地址变换造成虚拟存储器速度降低的主要原因造成虚拟存储器速度降低的主要原因 在段式或页式虚拟存储器中，要访问主存储器必须先在段式或页式虚拟存储器中，要访问主存储器必须先查段表或页表，在段页式虚拟存储器中，既要查段表也要查段表或页表，在段页式虚拟存储器中，既要查段表也要查页表。如果段表和页表都在主存储器中，那

14、么，包括访查页表。如果段表和页表都在主存储器中，那么，包括访问主存储器本身这一次在内，主存储器的访问速度将要降问主存储器本身这一次在内，主存储器的访问速度将要降低低23倍。倍。 当页表或段表的容量超过了一个页面的大小时，它们当页表或段表的容量超过了一个页面的大小时，它们就有可能被映象到主存储器的不连续的页面位置上。这样，就有可能被映象到主存储器的不连续的页面位置上。这样，按照地址查找主存实页号的方法，即把页表起始地址和多按照地址查找主存实页号的方法，即把页表起始地址和多用户虚地址中虚页号相加，就不能成立。目前解决的办法用户虚地址中虚页号相加，就不能成立。目前解决的办法是采用多级页表。是采用多级

15、页表。首先由页表基地址寄存器指出第一级页表的基地址，再用第首先由页表基地址寄存器指出第一级页表的基地址，再用第一级页表各单元中的地址字段指出第二级页表的基地址，如此下去，一级页表各单元中的地址字段指出第二级页表的基地址，如此下去，构成一个树型结构的多级页表。在最后一级页表中给出主存实页号等构成一个树型结构的多级页表。在最后一级页表中给出主存实页号等信息。信息。如果一个页式虚拟存储器的虚拟存储空间大小为如果一个页式虚拟存储器的虚拟存储空间大小为Nv=4GB，页面的大小为页面的大小为Np=1KB,一个页表存储字的大小为一个页表存储字的大小为Nd=4B:则必须采用三级页表，则必须采用三级页表，第三级

16、页表有第三级页表有16K个页面（共有个页面（共有4MB个页面，每一个页面个页面，每一个页面只能描述只能描述256个页面）；个页面）；第二级页表共有第二级页表共有64个页面；个页面；第一级页表为第一级页表为1个页面；个页面；注注：通常除了第一级页表必须驻留在主存中之外，二级和：通常除了第一级页表必须驻留在主存中之外，二级和三级页表只需要驻留一小部分。当一个用户程序被调入主三级页表只需要驻留一小部分。当一个用户程序被调入主存储器时，需把相关的页表也同时装入主存储器中，并且存储器时，需把相关的页表也同时装入主存储器中，并且修改页表中的装入位和主存地址等字段。修改页表中的装入位和主存地址等字段。063

17、025502550255025502550255、目录表、目录表 目录表的基本思想是：压缩页表的存储容量，用一目录表的基本思想是：压缩页表的存储容量，用一个容量比较小的高速存储器来存放页表，从而加快页表个容量比较小的高速存储器来存放页表，从而加快页表的查表速度。的查表速度。 页表只为已经装入到主存储器中的那些页面建立虚页表只为已经装入到主存储器中的那些页面建立虚页号与实页号之间的对应关系。页号与实页号之间的对应关系。 页表的每一个存储字中主要包括多用户虚页号、主页表的每一个存储字中主要包括多用户虚页号、主存实页号、修改位和其他标志（如访问方式）等，不再存实页号、修改位和其他标志（如访问方式）等

18、，不再需要装入位。并且采用相联方式访问。需要装入位。并且采用相联方式访问。用户号U虚页号P页内偏移DU，Pp0/1多用户虚页号多用户虚页号（U，P拼接）拼接）实页号实页号p修改位修改位其他标志其他标志多用户虚地址多用户虚地址实页号p页内偏移D主存实地址主存实地址、快慢表、快慢表 由于程序在执行过程中具有由于程序在执行过程中具有局部性局部性，因此，对页表，因此，对页表中各存储字的访问并不是完全随机的。也就是说，在一中各存储字的访问并不是完全随机的。也就是说，在一段时间内，对页表的访问只是局限在少数几个存储字内。段时间内，对页表的访问只是局限在少数几个存储字内。根据这一特点，可大大缩短目录表的存储

19、容量。例如，根据这一特点，可大大缩短目录表的存储容量。例如，容量为容量为8个个16个存储字，访问速度与个存储字，访问速度与CPU中的通用寄存中的通用寄存器相当。这个小容量的页表称为快表，快表采用与目录器相当。这个小容量的页表称为快表，快表采用与目录表相同的相联方式访问。当快表中查不到时，再从存放表相同的相联方式访问。当快表中查不到时，再从存放在主存储器中的页表中查找实页号。与快表相对应，存在主存储器中的页表中查找实页号。与快表相对应，存放在主存储器中的页表称为慢表。慢表是一个全表，快放在主存储器中的页表称为慢表。慢表是一个全表，快表只是慢表的一个部分副本，而且只存放了慢表中很少表只是慢表的一个

20、部分副本，而且只存放了慢表中很少的一部分。用户同时查找快表和慢表。的一部分。用户同时查找快表和慢表。快表和慢表也构成了一个由两级存储器组成的存储系统。快表和慢表也构成了一个由两级存储器组成的存储系统。u快表由硬件组成，它比页表小的多，是页表的一部分。快表由硬件组成，它比页表小的多，是页表的一部分。u查表时，由逻辑页号同时去查快表和慢表查表时，由逻辑页号同时去查快表和慢表u当快表中有此逻辑页号时，就能很快的找到对应的物理页号，送入实主当快表中有此逻辑页号时，就能很快的找到对应的物理页号，送入实主存地址寄存器，并使慢表的查找作废。存地址寄存器，并使慢表的查找作废。u如果在快表中查不到，从慢表中查到

21、物理页号，送入实主存地址寄存器，如果在快表中查不到，从慢表中查到物理页号，送入实主存地址寄存器，并将此逻辑页号和对应的物理页号送入快表并将此逻辑页号和对应的物理页号送入快表、散列函数、散列函数 提高快表的容量，会使命中率提高，但由于快表是提高快表的容量，会使命中率提高，但由于快表是按相联方式访问的，当容量增加时，它的查表速度就会按相联方式访问的，当容量增加时，它的查表速度就会降低。因此，需要让快表改用按地址来访问。降低。因此，需要让快表改用按地址来访问。 如果要在一个按地址访问的存储器中查找一个信息，如果要在一个按地址访问的存储器中查找一个信息，可以使用顺序查找法，对分查找法和散列查找法等。其

22、可以使用顺序查找法，对分查找法和散列查找法等。其中，散列查找方法的速度最快。中，散列查找方法的速度最快。 为了避免因散列冲突而发生查快表时的错误，必须为了避免因散列冲突而发生查快表时的错误，必须把多用户虚页号也加入到快表中去，并且与主存实页号把多用户虚页号也加入到快表中去，并且与主存实页号存放在同一个快表存储字中。另外，还要用一个比较器，存放在同一个快表存储字中。另外，还要用一个比较器，把从快表中读出来的多用户虚页号与多用户虚地址中的把从快表中读出来的多用户虚页号与多用户虚地址中的多用户虚页号进行比较。多用户虚页号进行比较。 用户号用户号U虚页号虚页号P页内偏移页内偏移D多用户虚地址多用户虚地

23、址实页号实页号p页内偏移页内偏移DPvp多用户虚页号多用户虚页号实页号实页号p相等比较相等比较快表命中快表命中查慢表查慢表散列变换散列变换（硬件实现）（硬件实现）快表地址快表地址Ah用户号用户号U虚页号虚页号NV页内偏移页内偏移Nr101212u100u201u310u411Nv+IDnvNv+IDnv实页号实页号nv页内偏移页内偏移nr散列压缩散列压缩相等比较相等比较相等比较相等比较3、页面替换算法、页面替换算法评价一个页面替换算法好坏的评价一个页面替换算法好坏的标准标准：、命中率要高、命中率要高这种算法能正确反映程序的局部性；这种算法能正确反映程序的局部性；这种算法能够充分利用主存中页面调

24、度情况的历史信息，这种算法能够充分利用主存中页面调度情况的历史信息，或能够预测主存中将要发生的页面调度情况或能够预测主存中将要发生的页面调度情况、算法容易实现、算法容易实现、随机算法（、随机算法（RAND算法）算法）利用软件或硬件的随机数发生器来确定主存储器中被替换的页面利用软件或硬件的随机数发生器来确定主存储器中被替换的页面特点特点：最简单，而且容易实现。但这种算法完全没有利用主存储器中：最简单，而且容易实现。但这种算法完全没有利用主存储器中页面调度情况的历史信息，也没有反应程序的局部性。页面调度情况的历史信息，也没有反应程序的局部性。、先进先出算法（、先进先出算法（FIFO算法）算法）选择

25、最先调入主存储器的页面作为被替换的页面选择最先调入主存储器的页面作为被替换的页面特点特点：比较容易实现，能利用主存中页面调度的历史信息，但没有反：比较容易实现，能利用主存中页面调度的历史信息，但没有反应程序的局部性应程序的局部性、近期最少使用算法（、近期最少使用算法（LRU算法：算法：Least recently Used）选择近期最少访问的页面作为被替换的页面选择近期最少访问的页面作为被替换的页面特点特点：非常合理，它既充分的利用了页面调度的历史信息，有正确反：非常合理，它既充分的利用了页面调度的历史信息，有正确反映了程序的局部；实现困难，需要固定的时钟，并且每一个页面都需映了程序的局部；实

26、现困难，需要固定的时钟，并且每一个页面都需要很长的计数器要很长的计数器、近期最久没有使用算法、近期最久没有使用算法LFU （Least frequently used）把近期最久没有被访问的页面作为被替换的页面把近期最久没有被访问的页面作为被替换的页面特点特点：实现较容易，由数量：实现较容易，由数量“多多”于于“少少”的判断改为的判断改为“有有”与与“无无”的判断的判断、最优替换算法（、最优替换算法（OPT算法：算法：Optimal replacement）将来最久不被访问的页面作为被替换的页面；将来最久不被访问的页面作为被替换的页面；特点特点：只是一种理想化的算法，实际上，经常把这种算法用来

27、作为其：只是一种理想化的算法，实际上，经常把这种算法用来作为其他页面替换算法好坏的标准。他页面替换算法好坏的标准。、堆栈型算法、堆栈型算法 对任意一个程序的页地址流作两次主存页面数分配，对任意一个程序的页地址流作两次主存页面数分配，分别分配分别分配m个主存页面和个主存页面和n个主存页面，并且有个主存页面，并且有mn。如果。如果在任意时刻在任意时刻t，主存页面数集合，主存页面数集合Bt都满足关系：都满足关系： Bt（m）Bt（n）则这类算法称为堆栈型替换算法。则这类算法称为堆栈型替换算法。 即任何时刻，在即任何时刻，在n个实页中的虚页集合总是被包含在个实页中的虚页集合总是被包含在给其增加一个实页

28、，即给其增加一个实页，即n+1个实页时，在实存中的虚页集个实页时，在实存中的虚页集合之内。合之内。 即随着分配给程序的主存页面数增加，主存的命中率即随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。也提高，至少不下降。注注：LRU替换算法和替换算法和OPT替换算法都属于堆栈型的替替换算法都属于堆栈型的替换算法；而换算法；而RAND替换算法和替换算法和FIFO替换算法则不是堆替换算法则不是堆栈型的替换算法。栈型的替换算法。 只要替换算法是堆栈型的，对页地址流用堆栈处只要替换算法是堆栈型的，对页地址流用堆栈处理一次，即可同时获得不同实页数时的命中率。理一次，即可同时获得不同实页数时的

29、命中率。4 5 3 2 5 1 3 2 2 5 1 3P175习题习题12：程序XAC BEAC BC AD EAC BES（1）AC BEAC BC AD EAC BES（2）AC BEAC BC AD EAC BS（3）AC BEAABC AD EACS（4）AC BEEEBC C D EAS（5）EBBBD DS（6）N=3H HHN=4H H H H HH HHN5H H H H HH H H H H程序Y354253132513152S（1）354253132513152S（2）35425313251315S（3）3542551325531S（4）334225132223S（5）44

30、4444444S（6）N=2HHN=3HHH HN=4H HH H H H H H H HN5H HH H H H H H H H程序程序X程序程序YHxHyH分分配配方方案案353/1510/156.5/15448/1510/159/155310/154/157/15、页面失效频率法（、页面失效频率法（PFF法法 Page fault frequency） 是对是对LRU替换算法的改进。也是堆栈型算法。替换算法的改进。也是堆栈型算法。 在程序的运行过程中，操作系统不断的根据所统在程序的运行过程中，操作系统不断的根据所统计出的各道程序的页面失效率来动态调节分配给各道计出的各道程序的页面失效率来

31、动态调节分配给各道程序的实页数。程序的实页数。补充补充：页面失效应按故障对待：页面失效应按故障对待 由于虚存中的页面是机械等分，按字节编址的多由于虚存中的页面是机械等分，按字节编址的多字节数据和指令就有可能被跨在两个不同的页面上，字节数据和指令就有可能被跨在两个不同的页面上，使页面失效完全可能发生在取指令、指令分析或指令使页面失效完全可能发生在取指令、指令分析或指令执行的任一过程中。如果按一般的中断来对待，安排执行的任一过程中。如果按一般的中断来对待，安排在本条指令执行完，下条指令准备取的时刻来响应和在本条指令执行完，下条指令准备取的时刻来响应和调页，那么因为页面失效不可能得到响应，就会死机。

32、调页，那么因为页面失效不可能得到响应，就会死机。应当作为一种故障，予以立即响应和处理。应当作为一种故障，予以立即响应和处理。4、影响主存命中率的主要因素、影响主存命中率的主要因素程序在执行过程中的页地址流的分布情况程序在执行过程中的页地址流的分布情况所采用的页面替换算法所采用的页面替换算法页面大小页面大小主存容量主存容量所采用的页面调度方法所采用的页面调度方法 页面大小的选择：页面大小的选择：命中率命中率H页面大小页面大小SpS2S简单解释：简单解释：在程序的执行过程中，假设在程序的执行过程中，假设A t和和A t+1是两次相邻的是两次相邻的访问主存的逻辑地址，访问主存的逻辑地址，d= A t

33、 A t+1 。如果。如果dSp，那，那么随着么随着Sp的增大，的增大， A t和和A t+1在同一个页面的可能性就会增在同一个页面的可能性就会增加，即加，即H随着随着Sp的增大而的增大而提高提高。如果。如果dSp，那么，那么A t和和A t+1一定不在同一个页面，随着一定不在同一个页面，随着Sp的增大，的增大， 在分配给该程序在分配给该程序的主存空间一定的情况下，主存的页面数就要减少，页面的主存空间一定的情况下，主存的页面数就要减少，页面的替换将更加频繁。这样，的替换将更加频繁。这样， A t和和A t+1两个地址所在页面都两个地址所在页面都在主存中的可能性就会减少，即在主存中的可能性就会减

34、少，即H随着随着Sp的增大而的增大而减少减少。当当Sp比较小的时候，前一种情况是主要的；当比较小的时候，前一种情况是主要的；当Sp达到某一达到某一个最大值之后，后一种情况成为主要的。个最大值之后，后一种情况成为主要的。另外，当页面大小增大时，由于每个程序或程序段另外，当页面大小增大时，由于每个程序或程序段的最后一个页面一般是装不满的，由此造成的浪费也要增的最后一个页面一般是装不满的，由此造成的浪费也要增加。相反，当页面大小减小时，页表（指慢表）在主存中加。相反，当页面大小减小时，页表（指慢表）在主存中所占的比例将增加。这两种情况都要降低主存的利用率。所占的比例将增加。这两种情况都要降低主存的利

35、用率。因此，页面大小的选择要综合考虑多方面的因素。因此，页面大小的选择要综合考虑多方面的因素。主存容量：主存容量：命中率命中率H主存容量主存容量S1.0主存命中率主存命中率H随着分配给该程序的主存容量随着分配给该程序的主存容量S的增加而单调的增加而单调上升，在上升，在S比较小的时候，比较小的时候，H提高的非常快，随着提高的非常快，随着S的逐渐的逐渐增加，增加，H提高的速度逐渐降低。提高的速度逐渐降低。简单解释简单解释：在页面替换算法中有这样一个结论，对于堆栈：在页面替换算法中有这样一个结论，对于堆栈型算法，命中率随着分配给程序的页面数的增加而提高。型算法，命中率随着分配给程序的页面数的增加而提

36、高。当分配给程序的主存容量增加时，如果页面大小是一定的，当分配给程序的主存容量增加时，如果页面大小是一定的，那么，页面数就会增加，因此，命中率那么，页面数就会增加，因此，命中率H也将提高。如果也将提高。如果不是堆栈型算法，命中率虽然不会单调上升，在局部可能不是堆栈型算法，命中率虽然不会单调上升，在局部可能有下降，但总的趋势还是上升的。有下降，但总的趋势还是上升的。注：因为操作系统在为程序分配主存空间时，是以页为单注：因为操作系统在为程序分配主存空间时，是以页为单位的，因此图中所示的不应该是一条平滑的曲线，而是台位的，因此图中所示的不应该是一条平滑的曲线，而是台阶型的。阶型的。启发：在为一道程序

37、分配主存空间时，对主存命中率的要启发：在为一道程序分配主存空间时，对主存命中率的要求不能过分。当主存容量增加到某一个值之后，命中率的求不能过分。当主存容量增加到某一个值之后，命中率的提高非常缓慢，这时，主存中不活跃部分所占的比例很大，提高非常缓慢，这时，主存中不活跃部分所占的比例很大，主存的利用率就会很低。主存的利用率就会很低。所采用的页面调度方法所采用的页面调度方法分页式分页式：在程序装入主储存器之前就对程序进行链接装配，：在程序装入主储存器之前就对程序进行链接装配，并且要在整个程序都调入到主存储器中之后才能开始运行。并且要在整个程序都调入到主存储器中之后才能开始运行。请求页式请求页式：只在

38、发生页面失效时，才把要访问的页面进行：只在发生页面失效时，才把要访问的页面进行链接装配并调入到主存储器中。链接装配并调入到主存储器中。分页式的主存命中率可以达到分页式的主存命中率可以达到100%，但是，主存的利用率，但是，主存的利用率比较低，这是因为主存中不活跃部分所占的比例比较大。比较低，这是因为主存中不活跃部分所占的比例比较大。而且，当主存剩余空间小于程序所需要的主存空间时，这而且，当主存剩余空间小于程序所需要的主存空间时，这个程序就无法装入到主存中运行。个程序就无法装入到主存中运行。目前，大多数机器采用请求式调度方式。但是，在程序执目前，大多数机器采用请求式调度方式。但是，在程序执行过程

39、中经常要发生页面失效，而且处理页面失效需要比行过程中经常要发生页面失效，而且处理页面失效需要比较长的时间。特别是在程序刚开始运行时，页面失效很频较长的时间。特别是在程序刚开始运行时，页面失效很频繁。繁。预取式调度方式预取式调度方式：根据程序的局部性特点，在程序被挂起：根据程序的局部性特点，在程序被挂起之后又重新开始运行之前，先把上次停止运行前一段时间之后又重新开始运行之前，先把上次停止运行前一段时间内用到的页面先调入到主存中，然后才开始运行程序。这内用到的页面先调入到主存中，然后才开始运行程序。这样，在程序一开始运行时，主存中就已经装入了一定数量样，在程序一开始运行时，主存中就已经装入了一定数

40、量的页面，从而可以避免在程序刚开始运行时，频繁发生页的页面，从而可以避免在程序刚开始运行时，频繁发生页面失效的情况。面失效的情况。二、高速缓冲存储器（二、高速缓冲存储器（Cache）1、3种不同的高速缓冲存储管理方式种不同的高速缓冲存储管理方式 CPU与与Cache之间的数据交换是以字为单位，而之间的数据交换是以字为单位，而Cache与主存之间的数据交换是以块为单位。与主存之间的数据交换是以块为单位。 Cache分为分为4行，每行行，每行4个字。个字。 分配给分配给Cache的地址存放在一个相联存储器的地址存放在一个相联存储器CAM中，中，它是按内容寻址的。它是按内容寻址的。 当当CPU执行访

41、存指令时，就把所要访问的字的地址送执行访存指令时，就把所要访问的字的地址送到到CAM和主存。和主存。 如果如果CAM指出所要访问的字指出所要访问的字W在在Cache中，则把中，则把W从从Cache传送到传送到CPU。 如果如果W不在不在Cache中，则将中，则将W从主存传送到从主存传送到CPU，同，同时把包含时把包含W的由前后相继的的由前后相继的4个字所组成的一行数据送入个字所组成的一行数据送入Cache。 替换算法采用替换算法采用LRU。主存块号主存块号块内地址块内地址主存地址主存地址Cache块号块号块内地址块内地址目录表（专门硬件）目录表（专门硬件）相联比较相联比较Cache地址地址在主

42、存和在主存和Cache都机械等分成相同都机械等分成相同大小的块后，让主存中的任何一个大小的块后，让主存中的任何一个块均可以映象装入到块均可以映象装入到Cache中任何中任何一个块的位置上。一个块的位置上。优点优点：Cache块冲突概率最低，物块冲突概率最低，物理理Cache的空间利用率最高，的空间利用率最高，缺点缺点：用于地址映象的相联目录表：用于地址映象的相联目录表容量太大，成本极高，查表进行地容量太大，成本极高，查表进行地址变换的速度太低，所以无法实用。址变换的速度太低，所以无法实用。 、全相联映象、全相联映象区号区号主存块号主存块号块内地址块内地址主存地址主存地址Cache块号块号块内地

43、址块内地址按地址访问存储器按地址访问存储器相等比较相等比较Cache地址地址在主存和在主存和Cache都机械等分成相同大小的块后，再将都机械等分成相同大小的块后，再将主存空间按物理主存空间按物理Cache大小等分成区，让主存中每一大小等分成区，让主存中每一个区中的各个块只能按位置一一对应装入个区中的各个块只能按位置一一对应装入Cache中相中相应的块位置上。应的块位置上。优点优点：该表存储器所需的硬件量很少，成本低，易：该表存储器所需的硬件量很少，成本低，易于实现。采用直接映象时，查表找区号可以和访问于实现。采用直接映象时，查表找区号可以和访问物理物理Cache同时进行，只要同时进行，只要Ca

44、che块命中，就不需要块命中，就不需要花专门的地址变换时间，所以花专门的地址变换时间，所以Cache的实际访问速度的实际访问速度很快。很快。 缺点缺点：发生：发生Cache块冲突的概率很高，块冲突的概率很高，Cache的空间的空间利用率很低，所以现在的系统上已经很少使用。利用率很低，所以现在的系统上已经很少使用。、直接映象、直接映象区号区号组号组号主存块号主存块号块内地址块内地址主存地址主存地址组号组号Cache块号块号块内地址块内地址相联比较相联比较相等比较相等比较Cache地址地址在主存和在主存和Cache都机械等分都机械等分成相同大小的块，并将主存成相同大小的块，并将主存空间按空间按Ca

45、che大小等分成区大小等分成区后，再将后，再将Cache空间和主存空间和主存空间中的每一区都等分成大空间中的每一区都等分成大小相同的组。让主存各区中小相同的组。让主存各区中某组中的任何一块均可直接某组中的任何一块均可直接映象装入到映象装入到Cache中对应组中对应组的任何一块位置上，也就是的任何一块位置上，也就是采取组间直接映象，组内各采取组间直接映象，组内各块全相联映象。块全相联映象。、组相联映象、组相联映象00 00 00 0011 11 11 1122 22 22 2233 33 33 3344 44 44 4455 55 55 55 6 6 6 6 7 7 7 7 8 8 8 8 9

46、9 9 9 10 10 10 10 11 11 11 11段相联段相联映象实际上是组相联的变形，映象实际上是组相联的变形，它采取的是组间全相联，组内直接它采取的是组间全相联，组内直接的映象规则。的映象规则。节相联节相联映象也是组相联映象的变形，映象也是组相联映象的变形，只是根据物理只是根据物理Cache的组的个数，把的组的个数，把主存分成节，每节中的第主存分成节，每节中的第I块只能直块只能直接映想到接映想到Cache中的第中的第I组，但可以组，但可以全相联映象到该组中的任意块。全相联映象到该组中的任意块。 全相联映象：主存全相联映象：主存7Cache 0、1、2、3、4、5 直接映想：直接映想

47、： 主存主存7Cache 1 组相联映想：主存组相联映想：主存7Cache 0、1 （分成（分成3组，每组组，每组2块）块） 段相联映想：主存段相联映想：主存7Cache 1、3、5 节相联映想：主存节相联映想：主存7Cache 2、3例题例题1：设有一个主存的容量是：设有一个主存的容量是256K字，一个字，一个Cache的容量是的容量是2K字，每个字，每个块为块为16字，按字编址。求：字，按字编址。求：该主存可容纳多少个块？该主存可容纳多少个块？ 16K该该Cache可容纳多少个块？可容纳多少个块？128主存的地址是多少位？主存的地址是多少位？Cache的地址是多少位？的地址是多少位？18位

48、；位；11位位在全相联、直接映象、组相联映象这三种方式下，主存中的第在全相联、直接映象、组相联映象这三种方式下，主存中的第i块分别映块分别映象到象到Cache中的哪一块？设组相联映象方式下，中的哪一块？设组相联映象方式下，Cache分为分为8个组。个组。 任意；任意；I mod 128；I=128x+16y+z ；y组的任意一块组的任意一块在全相联、直接映象、组相联映象这三种方式下，主存和在全相联、直接映象、组相联映象这三种方式下，主存和Cache的地址的地址组成部分是什么，各部分占多少位？组成部分是什么，各部分占多少位？区号区号 7组号组号 3块号块号 4块内地址块内地址 4区号区号 7块号

49、块号 7块内地址块内地址 4块号块号 14块内地址块内地址 4块号块号 7块内地址块内地址 4主存地址主存地址Cache地址地址2、LRU块替换算法的实现块替换算法的实现、堆栈法、堆栈法：各块被访问的先后次序由该项在堆栈中距离栈底是远还是各块被访问的先后次序由该项在堆栈中距离栈底是远还是进来反映。进来反映。硬件堆栈的栈顶恒存放近期最近访问过的块的块号，而栈硬件堆栈的栈顶恒存放近期最近访问过的块的块号，而栈底恒存放近期最久没有访问过的块的块号。底恒存放近期最久没有访问过的块的块号。变形变形：将存放块号的寄存器的几何位置与：将存放块号的寄存器的几何位置与Cache中的块号中的块号来对应，而用寄存器

50、的值的大小来表示该块已被访问过的来对应，而用寄存器的值的大小来表示该块已被访问过的远近次序。远近次序。由于要使用有相联访问功能的寄存器组，设备量大，由于要使用有相联访问功能的寄存器组，设备量大，价格较贵，较少采用。价格较贵，较少采用。块号块号块号块号块号块号栈顶栈顶栈底栈底压入寄存器堆栈压入寄存器堆栈需要重新排序的块号都下移一行需要重新排序的块号都下移一行块块0块号块号块块n第第0块的访问次序块的访问次序块号块号第第n块的访问次序块的访问次序、比较对法、比较对法：让各块之间两两成对组合，用一个比较对触发器的让各块之间两两成对组合，用一个比较对触发器的状态来纪录该比较对内两块被访问的远近次序，再

51、通过门电路对各比状态来纪录该比较对内两块被访问的远近次序，再通过门电路对各比较对触发器的状态进行逻辑组合，就可以找出较对触发器的状态进行逻辑组合，就可以找出LRU的块。的块。如果采用组相联的地址映象规则，则每一组都有一套用比较对法实现如果采用组相联的地址映象规则，则每一组都有一套用比较对法实现LRU算法找算法找LRU块的硬件。块的硬件。访问访问A访问访问C访问访问B0 1Tab0 1Tbc0 1TacCLRU=TABTACTBC+TABTACTBC=TACTBCBLRU=TABTBCALRU=TABTAC比较对法的硬件量比较对法的硬件量：与门：块数与门：块数与门的扇入数：块数减与门的扇入数：块

52、数减12 触发器的个数：触发器的个数：C2p3、Cache的性能分析的性能分析 由于由于Cache存储器采用全硬件实现，所以它对应用程存储器采用全硬件实现，所以它对应用程序员和系统程序员都是透明的。为此，需要在硬件上采取序员和系统程序员都是透明的。为此，需要在硬件上采取一系列相应措施来解决好透明所带来的问题。一系列相应措施来解决好透明所带来的问题。、更新主存的两种方法、更新主存的两种方法写回法写回法（抵触修改法）：写回法在（抵触修改法）：写回法在CPU执行写操作时，如执行写操作时，如果命中果命中Cache，就只写入，就只写入Cache，而暂不写入主存。变化，而暂不写入主存。变化了的了的Cach

53、e块只有在块替换前，才用一个主存周期写回主块只有在块替换前，才用一个主存周期写回主存相应的块位置上，使两者对应的内容一致起来。存相应的块位置上，使两者对应的内容一致起来。写直达法：写直达法：是每当是每当CPU写写Cache命中时，不仅写入命中时，不仅写入Cache，也经也经CPU到主存的直达通路直接写入主存，使两者对应块到主存的直达通路直接写入主存，使两者对应块的内容始终保持一致。这样，的内容始终保持一致。这样，Cache中的块被替换时，就中的块被替换时，就不必再花时间去写回主存了。不必再花时间去写回主存了。 单处理机宜采用写回法，共享主存的多处理机宜采用写直达法。单处理机宜采用写回法，共享主

54、存的多处理机宜采用写直达法。对于共享主存的多处理机，由于写直达法并不能保证同一主存块在各对于共享主存的多处理机，由于写直达法并不能保证同一主存块在各CPU所带所带Cache中对应块的内容都一致，还得采用播写法。播写法是中对应块的内容都一致，还得采用播写法。播写法是在任何在任何CPU写入本写入本Cache和主存的同时，也将信息写入其它和主存的同时，也将信息写入其它Cache有有此单元的块中；或者让其它此单元的块中；或者让其它Cache中有此单元的块都作废。中有此单元的块都作废。 写回法和写直达法都是对应于写回法和写直达法都是对应于Cache写命中时的情况。写命中时的情况。如果如果Cache写没有

55、命中时，还涉及到是否需要按缺块处理，写没有命中时，还涉及到是否需要按缺块处理，到主存中去调块的问题。到主存中去调块的问题。不按写分配法不按写分配法只写主存，不进行调块。只写主存，不进行调块。按写分配法则按写分配法则除了要写入主存外，还要将该块从主存调除了要写入主存外，还要将该块从主存调入入Cache。 一般的，写回法宜用按写分配法，写直达法宜用不一般的，写回法宜用按写分配法，写直达法宜用不按写分配法。按写分配法。 对于主存内容已经改变，对于主存内容已经改变，Cache相应块的内容未跟相应块的内容未跟着改变的情况，可采用硬件方法将着改变的情况，可采用硬件方法将Cache中对应于该块的中对应于该块的内容作废来处理。这既保持了内容作废来处理。这既保持了Cache对操作系统透明，又对操作系统透明，又不会因这种不一致导致不会因这种不一致导致Cache存储器的工作出错。存储器的工作出错。、提高、提高Cache命中率的取算法命中率的取算法按需取进法按需取进法：在：在Cache发生块失效时才去调块发生块失效时才去调块预取法预取法：在将要用到某块之前，就已经将该块预先取进：在将要用到某块之前，就