搜索
一、虚拟存储器1、三种存储管理方式（段式、页式、段页式）2、加快内部地址变换3、页面替换算法4、影响主存命中率的主要因素二、高速缓冲存储器（Cache）1、三种存储管理方式（全相联、直接映象、组相联）2、LRU块替换算法的实现3、Cache的性能分析三、主存保护⑴、掌握段式、页式、段页式3种不同的虚拟存储管理方式的工作原理，掌握其地址映像规则、映像表机构、虚实地址变换的过程及各自的优缺点；⑵、掌握FIFO、LRU、OPT等替换算法进行页面替换的过程模拟以及LRU替换算法对页地址流的堆栈处理模拟及性能分析；⑶、领会在虚拟存储器中对页面失效的处理及内部地址映象表中的快慢表机构。能分析虚拟存储器中，页面大小，分配给程序的主存容量与主存命中率的变化关系。能够给出改进页式虚拟存储器等效访问速度的各种办法。⑴、了解Cache存储器的组成、工作原理，并能与虚拟存储器进行比较；⑵、掌握Cache存储器中全相联、直接、组相联3种地址映象规则，相应的映象表机构和虚、实地址变化过程；⑶、领会堆栈法和比较对法实现Cache块替换的原理，能计算出用比较对法进行块替换时所用的比较对触发器的个数；⑷、给出主存的块地址流后，采用组相联或直接映象、LRU或FIFO替换算法时，能熟练画出各主存块装入Cache和其被替换的过程示意图，并计算出Cache块的命中率；⑸、理解为解决Cache存储器透明性问题所提出的各种算法以及为提高Cache块命中率的各种预取算法。能分析影响Cache性能的因素及其变化规律。正确理解和分析Cache存储器的等效访问速度与物理Cache速度及Cache容量、Cache命中率的关系。1、段式、页式、段页式3种不同的虚拟存储管理方式段式在段式虚拟存储器系统中，段是按照程序的逻辑结构划分的虚拟地址由段号和段内地址组成为把虚拟地址变换成实主存地址，需要一个段表装入位为1表示该段已调入主存，为0则表示该段不在主存中因段的长度可大可小，所以段表需要有长度指示段表也是一个表，一般驻留在主存中优点：1、支持了程序的模块化设计和并行编程的要求；2、便于多道程序共享主存中某些段；3、便于按逻辑意义实现存储器的访问方式保护。缺点：1、段映象表机构太庞大，其地址字段和段长字段都太长；2、查表进行地址变换的速度太慢（从多用户虚地址变换到主存实地址需要查两次表，做两次加法运算）；3、对主存各区域的存储管理十分麻烦；（对辅存（磁盘存储器）的管理比较困难。磁盘存储器通常是按固定大小的块来访问的，如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要做一次地址变换。）4、主存储器的利用率往往比较低，存储器内部的段间零头浪费大，有时难以利用。因此，单纯的段式存储管理在实际的系统中无法采用。页式页式虚拟存储器把虚拟地址空间划分成一个个固定大小的块，每一块称为一页（虚页），把主存储器的地址空间也按虚拟地址空间同样的大小划分为页（实页）。页是一种逻辑上的划分，它可以由系统管理软件任意指定。在页表中，对应每一个虚存逻辑页号有一个目录，它至少包含主存页面地址主存页面地址作为实存地址的高字段，与虚存地址的行地址字段相拼接，产生完整的实主存地址，据此访问主存。01230123456703114260虚页号页内位移实页号页内位移4888=4*1024+7922*1024+792=28401001100011000101100011000实页号装入位3111203021100100优点：1、主存储器的利用率比较高。每个用户程序只有不到一页（平均为半页）的浪费；2、页表相对比较简单。它需要保存的字段数比较少，一些关键字段的长度要短许多，因此，节省了页表的存储容量；3、地址映象和变换的速度比较快；4、对辅存的管理比较容易。缺点：1、程序的模块化性能不好；2、页表很长，需要占用很大的存储空间。（虚拟存储器中的每一页在页表中都要占用一个存储字。假设有一个页式虚拟存储器，它的虚拟存储空间大小为4GB，每一个的大小为1KB,则页表的容量为4MB存储字。如果每个页表存储字占用4个字节，则页表的存储容量为16MB）段页式段页式管理是将程序按逻辑意义先分成段，再让各段和实主存都机械等分成相同大小的页面。每道程序通过一个段表和相应的一组页表来进行程序在主存空间中的定位。段页式存储管理和纯段式存储管理最主要的差别是段的起点不再是任意的，它必须是位于主存中某个页面的起点上。段页式虚拟地址包括基号、段号、页号和页内地址每个程序由若干段组成，而每一段又由若干页组成如程序A由四段组成，程序C由三段组成每段应有一张页表程序C的地址转换过程如下：根据基号C，执行SC加1操作，得到段表相应行地址，其内容为页表的起始地址b执行b加2操作，得到物理页号的地址，其内容即为物理页号10物理页号与页内地址拼装即得物理地址2、加快内部地址变换造成虚拟存储器速度降低的主要原因在段式或页式虚拟存储器中，要访问主存储器必须先查段表或页表，在段页式虚拟存储器中，既要查段表也要查页表。如果段表和页表都在主存储器中，那么，包括访问主存储器本身这一次在内，主存储器的访问速度将要降低2—3倍。当页表或段表的容量超过了一个页面的大小时，它们就有可能被映象到主存储器的不连续的页面位置上。这样，按照地址查找主存实页号的方法，即把页表起始地址和多用户虚地址中虚页号相加，就不能成立。目前解决的办法是采用多级页表。首先由页表基地址寄存器指出第一级页表的基地址，再用第一级页表各单元中的地址字段指出第二级页表的基地址，如此下去，构成一个树型结构的多级页表。在最后一级页表中给出主存实页号等信息。如果一个页式虚拟存储器的虚拟存储空间大小为Nv=4GB，页面的大小为Np=1KB,一个页表存储字的大小为Nd=4B:则必须采用三级页表，第三级页表有16K个页面（共有4MB个页面，每一个页面只能描述256个页面）；第二级页表共有64个页面；第一级页表为1个页面；注：通常除了第一级页表必须驻留在主存中之外，二级和三级页表只需要驻留一小部分。当一个用户程序被调入主存储器时，需把相关的页表也同时装入主存储器中，并且修改页表中的装入位和主存地址等字段。0…630…2550…2550…2550…2550…2550…255①、目录表目录表的基本思想是：压缩页表的存储容量，用一个容量比较小的高速存储器来存放页表，从而加快页表的查表速度。页表只为已经装入到主存储器中的那些页面建立虚页号与实页号之间的对应关系。页表的每一个存储字中主要包括多用户虚页号、主存实页号、修改位和其他标志（如访问方式）等，不再需要装入位。并且采用相联方式访问。用户号U虚页号P页内偏移DU，Pp0/1多用户虚页号（U，P拼接）实页号p修改位其他标志多用户虚地址实页号p页内偏移D主存实地址②、快慢表由于程序在执行过程中具有局部性，因此，对页表中各存储字的访问并不是完全随机的。也就是说，在一段时间内，对页表的访问只是局限在少数几个存储字内。根据这一特点，可大大缩短目录表的存储容量。例如，容量为8个—16个存储字，访问速度与CPU中的通用寄存器相当。这个小容量的页表称为快表，快表采用与目录表相同的相联方式访问。当快表中查不到时，再从存放在主存储器中的页表中查找实页号。与快表相对应，存放在主存储器中的页表称为慢表。慢表是一个全表，快表只是慢表的一个部分副本，而且只存放了慢表中很少的一部分。用户同时查找快表和慢表。快表和慢表也构成了一个由两级存储器组成的存储系统。快表由硬件组成，它比页表小的多，是页表的一部分。查表时，由逻辑页号同时去查快表和慢表当快表中有此逻辑页号时，就能很快的找到对应的物理页号，送入实主存地址寄存器，并使慢表的查找作废。如果在快表中查不到，从慢表中查到物理页号，送入实主存地址寄存器，并将此逻辑页号和对应的物理页号送入快表③、散列函数提高快表的容量，会使命中率提高，但由于快表是按相联方式访问的，当容量增加时，它的查表速度就会降低。因此，需要让快表改用按地址来访问。如果要在一个按地址访问的存储器中查找一个信息，可以使用顺序查找法，对分查找法和散列查找法等。其中，散列查找方法的速度最快。为了避免因散列冲突而发生查快表时的错误，必须把多用户虚页号也加入到快表中去，并且与主存实页号存放在同一个快表存储字中。另外，还要用一个比较器，把从快表中读出来的多用户虚页号与多用户虚地址中的多用户虚页号进行比较。用户号U虚页号P页内偏移D多用户虚地址实页号p页内偏移DPv’p多用户虚页号实页号p相等比较快表命中查慢表散列变换（硬件实现）快表地址Ah用户号U虚页号NV页内偏移Nr101212u100u201u310u411Nv+IDnvNv+IDnv实页号nv页内偏移nr散列压缩相等比较相等比较3、页面替换算法评价一个页面替换算法好坏的标准：⑴、命中率要高——这种算法能正确反映程序的局部性；这种算法能够充分利用主存中页面调度情况的历史信息，或能够预测主存中将要发生的页面调度情况⑵、算法容易实现①、随机算法（RAND算法）利用软件或硬件的随机数发生器来确定主存储器中被替换的页面特点：最简单，而且容易实现。但这种算法完全没有利用主存储器中页面调度情况的历史信息，也没有反应程序的局部性。②、先进先出算法（FIFO算法）选择最先调入主存储器的页面作为被替换的页面特点：比较容易实现，能利用主存中页面调度的历史信息，但没有反应程序的局部性③、近期最少使用算法（LRU算法：LeastrecentlyUsed）选择近期最少访问的页面作为被替换的页面特点：非常合理，它既充分的利用了页面调度的历史信息，有正确反映了程序的局部；实现困难，需要固定的时钟，并且每一个页面都需要很长的计数器④、近期最久没有使用算法LFU（Leastfrequentlyused）把近期最久没有被访问的页面作为被替换的页面特点：实现较容易，由数量“多”于“少”的判断改为“有”与“无”的判断⑤、最优替换算法（OPT算法：Optimalreplacement）将来最久不被访问的页面作为被替换的页面；特点：只是一种理想化的算法，实际上，经常把这种算法用来作为其他页面替换算法好坏的标准。⑥、堆栈型算法对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任意时刻t，主存页面数集合Bt都满足关系：Bt（m）≤Bt（n）则这类算法称为堆栈型替换算法。即任何时刻，在n个实页中的虚页集合总是被包含在给其增加一个实页，即n+1个实页时，在实存中的虚页集合之内。即随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。注：LRU替换算法和OPT替换算法都属于堆栈型的替换算法；而RAND替换算法和FIFO替换算法则不是堆栈型的替换算法。只要替换算法是堆栈型的，对页地址流用堆栈处理一次，即可同时获得不同实页数时的命中率。453251322513P175习题12：程序XACBEACBCADEACBES（1）ACBEACBCADEACBES（2）ACBEACBCADEACBS（3）ACBEAABCADEACS（4）ACBEEEBCCDEAS（5）EBBBDDS（6）N=3HHHN=4HHHHHHHHN≥5HHHHHHHHHH程序Y354253132513152S（1）354253132513152S（2）35425313251315S（3）3542551325531S（4）334225132223S（5）444444444S（6）N=2HHN=3HHHHN=4HHHHHHHHHHN≥5HHHHHHHHHH程序X程序YHxHyH分配方案353/1510/156.5/15448/1510/159/155310/154/157/15⑦、页面失效频率法（PFF法Pagefaultfrequency）是对LRU替换算法的改进。也是堆栈型算法。在程序的运行过程中，操作系统不断的根据所统计出的各道程序的页面失效率来动态调节分配给各道程序的实页数。补充：页面失效应按故障对待由于虚存中的页面是机械等分，按字节编址的多