虚拟存储器(2).ppt

从根本上提高内存利用率的手段页式存储管理.分页存储管理的基本思想（一）进程图像等分成若干页面内存按同样大小等分成若干页框例：32位机器，配置1G内存。页面大小4K。问，进程虚地址空间占多少页？内存有多少页框？.分页存储管理的基本思想（二）一个页面占据一个页框同一个进程在主存中占据的页框不必连续页表：登记进程的页面在主存占据的页框号。每个进程拥有一张页表，进程运行时页表全部驻留主存问：页表何时被创建，系统何时会对页表进行修改？.用页表进行地址映射例：设某台计算机的页面长4k，右图是现运行进程pa的页表。问：1、逻辑地址为5K的代码在内存中的起始地址2、页表有多少表项，占多少内存？页号页框号0819213.实现地址变换的硬件逻辑假设进程执行时需要访问逻辑地址n，简单分页系统的地址变换过程如下，整个过程由硬件的地址变换机构自动完成。1将逻辑地址n分成页号p和页内位移量s。2根据页号查找页表（页表起始地址a存放在页表控制寄存器中），确定包含n单元的页面在内存中的存放位置（页框号t）。3用页框号t取代逻辑地址中的页号部分p，实现下面的计算：物理地址=页框号*页长页内位移。之后将结果送MAR访问主存。.解决页表容量过大的问题二级页表IntelPentiumsSolutionIntelPentiumsSolution总的思路：将页表进行分页，用页目录中的表项记录页表在主存中位置。页目录：页表的页表页目录占一个页框有了二级页表之后，页表不用占据连续的存储空间，甚至不用100%驻留内存请画出最小的程序的二级页表最重要的：页表的内容（容量）大大地减少了.MMU支持二级页表时逻辑地址MMU支持二级页表时逻辑地址分三部分页目录号页号页内偏移量.例：长度为128M的进程之页表长度为128k字节，32页求进程的二级页表.31张页表不必连续存放在内存只有进程最近一段时间内使用的页表才需要驻留内存，解决了页表内存消耗过大的问题.页表内存消耗巨大问题的解决方案之二PowerPCsSolutionPowerPCsSolution反向页表（InvertedPageTable）反向页表中每一项对应于一个主存页而不是虚页。.在这种方法中，系统维护一张反向页表，在这张表中每一项对应于一个主存页而不是虚页。系统使用一个简单的散列（hash）函数将虚地址的页号部分映射到散列表中的某一项，其中登记着一根指向反向页表表项的指针。由于散列表和反向页表中的每一项对应于一个主存页框，因此，无论有多少个进程、支持多少虚页，页表（反向页表）的容量是固定的。512M的主存只需要128K个反向页表表项。熟悉散列表的读者一定知道，多个页号的hash函数运算结果可能会相同，即多个虚地址页面可能会被映射到同一个主存页框；系统可以利用链接管理技术来处理hash冲突。只要hash函数选择的好，同一个hash结果对应的反向页表链会很短只有一到两项。.空闲内存区的管理：位示图（bitmap）操作系统使用位示图登记内存中物理页面的分配情况。内存的每个物理页面对应于一个bit-0相应的页框空闲可供使用，-1该页框中已存入其它进程的逻辑页面。当进程需要内存空间时，操作系统扫描位示图寻找值为0的bit,并将这些bit对应的主存页框分配给该进程。进程运行结束或出于某种原因释放内存空间时，操作系统找到所释放的所有页框，在bit图中将它们对应的bit改为0。.离散的代价访存时间加倍.简介原则上，每个虚存访问可能引起两次主存访问：一次取相应的页表项，一次取想要的数据，因此简单的页式存储方案会导致存储器访问时间加倍。为克服这个问题，系统可以在CPU和主存之间配一组特殊的高速cache,用来存放现运行进程的页表表项。这种Cache是联想寄存器，它可以按内容进行并行查找。当输人端有一个输人值页号p时，其中存放页号为p的那一项立即被选中，并输出其变换值页框号t。Cache的访问速度远远高于主存，它的引入大大提高了地址变换的速度。但由于成本关系（价格非常昂贵）联想寄存器不可能做得很大。一般而言，联想寄存器中只能够存放CPU最近用过的少数页表表项。随着进程的运行，系统会经常运行置换算法以淘汰联想寄存器中不经常使用的部分。配备了联想寄存器的系统在每次地址变换时，根据页式地址中的页面号同时查找主存页表和联想寄存器（转换后备缓冲区TLB）。若TLB中存在相匹配的页号，系统可以直接从TLB中读出页框号送MAR以形成物理地址。否则，系统等待主存页表的查询结果（页框号）；形成物理地址的同时将页框号送TLB（若TLB已满，需首先运行置换算法淘汰某个页面）。.内存访问时间加倍问题的解决转换后备缓冲区（TLB）：CPU和主存之间的联想寄存器。作为高速cache，存放CPU在最近一段时间内经常访问的页表表项。.TLB高速缓存的硬件特性：按内容查表，并发地用待查找的内容与每个表项匹配。若命中，一个访问周期内就可以得到逻辑页面在主存中的地址若不命中，等待左侧页表的查询结果。形成物理地址的同时将页框号送TLB，保证TLB始终存放CPU最近使用的页面页面置换算法注：TLB又称为快表，或联想寄存器组.虚拟存储器思想来源：实际上绝大多数进程在运行时并非用到全部程序，因此，进程在运行时图像全部驻留主存显然是不必要的。1961年英国曼彻斯特大学提出虚拟存储器的概念,使用硬盘中的swap分区作为主存的辅助存储器，存放所有进程的图像；主存中只存放CPU最近需要使用的信息.用页式管理实现虚拟存储.缺页缺页事件：CPU所访问的信息内存中不存在计算机使用中断处理缺页事件硬件：当前指令访问的数据，或CPU下一条待执行的指令不在内存，产生缺页中断软件（操作系统）：中断处理程序在swap分区中找到包含CPU所需访问的数据（指令）的逻辑页面，将其装入内存页框.完整的页表的结构页号页号块号块号状态位状态位访问字段访问字段修改位修改位外存地址外存地址（1）状态位P：指示该页是否已调入内存。（2）访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间。（3）修改位M：表示该页在调入内存后是否被修改过。若修改过，则换出时需重写至外存。（4）外存地址：指出该页在外存上的地址。缺页中断的产生缺页中断的产生地址变换查页表时，发现表项的状态位为0.地址变换机构地址变换机构地址变换机构地址变换机构开始页号页表长度？CPU检索快表NNY页表项在快表中？访问页表页在内存？修改访问位和修改位修改页表形成物理地址地址变换结束越界中断程序请求访问一页YN缺页中断处理Y保留CPU现场内存满吗？将一页从外存换入内存OS命令CPU从外存读缺页启动I/O硬件Y从外存中找到缺页选择一页换出该页被修改否？将该页写回外存修改页表NYN.页面置换缺页中断时，若此时无空页，操作系统必须从主存中选择一页进行淘汰以便为即将被调人的页让出空间。这就是页面替换，也称页面置换。.替换算法 目标：淘汰最近最不可能访问的页 1 最优页面替换算法Optimal,OPT选择下次访问距当前时间最长的页面 进行置换。（无法实现）2 FIFO 3 最近最久未使用算法LRU 选择主存页面中上次访问时间距今最长的页面予以淘汰。（硬件实现的代价太大）。4 其它 .最佳置换算法例最佳置换算法例最佳置换算法例最佳置换算法例假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换最佳置换页面淘汰算法时的缺页率？（7/12)注：注：实际上这种算法无法实现，因页面访问的未来顺序很难精确预测，但可用该算法评价其它算法的优劣。页面走向页面走向123412512345物理块物理块11111133物理块物理块2222224物理块物理块334555缺页缺页缺缺 缺缺 缺缺 缺缺缺缺缺缺 缺缺.先进先出置换算法例题先进先出置换算法例题先进先出置换算法例题先进先出置换算法例题1、假定系统为某进程分配了3 3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先进先出先进先出页面淘汰算法时的缺页率？（9/12)页面走向页面走向123412512345物理块物理块1111444555物理块物理块222211133物理块物理块33332224缺页缺页缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺缺缺 缺缺.先进先出置换算法例题先进先出置换算法例题先进先出置换算法例题先进先出置换算法例题2、假定系统为某进程分配了4 4个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时4个物理块均为空，计算采用先进先出先进先出页面淘汰算法时的缺页率？（10/12)页面走页面走向向123412512345物理块物理块11111555544物理块物理块2222211115物理块物理块333332222物理块物理块44444333缺页缺页缺缺 缺缺 缺缺 缺缺缺缺 缺缺 缺缺 缺缺 缺缺 缺缺.先进先出置换算法先进先出置换算法先进先出置换算法先进先出置换算法_ _注：注：注：注：物理块数物理块数345缺页次数缺页次数9 10 5 1 1、该算法的出发点出发点是最早调入内存的页面，其不再被访问的可能性会大一些。2 2、该算法实现比较简单，对具有线性顺序访问的程序比较合适，而对其他情况、该算法实现比较简单，对具有线性顺序访问的程序比较合适，而对其他情况效率低效率低。3 3、先进先出算法存在一种异常现象，即在某些情况下会出现分配给的进程物理块数增多，缺页次数有时增加，有时减少的奇怪现象，这种现象称为BeladyBelady现现象。象。如上几例：页面走向页面走向123412512345物理块物理块1111444555物理块物理块222211133物理块物理块33332224缺页缺页缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺.LRU最近最久未使用算法最近最久未使用算法选择到当前时间为止访问次数最少页面淘汰。选择到当前时间为止访问次数最少页面淘汰。该算法要求为每页设置一个访问计数器，该算法要求为每页设置一个访问计数器，每当页被访问，该页的访问计数器加每当页被访问，该页的访问计数器加1.1.发发生缺页中断时，淘汰计数值最小的页面，生缺页中断时，淘汰计数值最小的页面，并将所有计数器清零。并将所有计数器清零。.最近最久未使用算法最近最久未使用算法最近最久未使用算法最近最久未使用算法_ _注注注注v该算法的出发点该算法的出发点：如果某个页面被访问了，则它可能马上还要访问。反之，如果很长时间未被访问，则它在最近一段时间也不会被访问。v该算法的性能接近于最佳算法，但实现起来较困难实现起来较困难。因为要找出最近最久未使用的页面，必须为每一页设置相关记录项，用于记录页面的访问情况，并且每访问一次页面都须更新该信息。这将使系统的开销加大，所以在实际系统中往往使用该算法的近似算法往往使用该算法的近似算法。v该算法的近似算法实现该算法的近似算法实现：方法方法1 1：利用一特殊的栈保存当前使用的页号，每当进程访问某页面时，把被访问页面移到栈顶，于是栈底的页面就是最久未使用的页面。方法方法2 2：为每个页面设立一个寄存器记录页面的访问情况。每当进程访问某页面时，将该页面对应寄存器的最高位置1，系统定期将寄存器右移一位并将最高位补0，于是寄存器数值最小的页面是最久未使用的页面。.最近最久未使用算法例最近最久未使用算法例最近最久未使用算法例最近最久未使用算法例假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最近最久未使用最近最久未使用页面淘汰算法时的缺页率？（10/12)页面走页面走向向123412512345物理块物理块11114445333物理块物理块2222111144物理块物理块333322225缺页缺页缺缺缺缺 缺缺 缺缺 缺缺缺缺缺缺缺缺缺缺缺缺.简单简单简单简单ClockClock置换算法置换算法置换算法置换算法NRU:Not NRU:Not Recently UsedRecently Used算法算法 该算法是该算法是LRULRU和和FIFOFIFO的折衷。该算的折衷。该算法要求为每页设置一个访问位，并将内法要求为每页设置一个访问位，并将内存中的所有页链接成一个循环队列。当存中的所有页链接成一个循环队列。当某页被访问时，系统将其访问位设置为某页被访问时，系统将其访问位设置为1 1。置换时采用一个指针，从当前指针。置换时采用一个指针，从当前指针位置开始按序检查各页，若访问位为位置开始按序检查各页，若访问位为0 0则选择该页换出，若访问位为则选择该页换出，若访问位为1 1则将其则将其设置为设置为0 0，最后指针停留在被置换页的，最后指针停留在被置换页的下一页上。下一页上。块号块号页号页号访问位访问位指针指针0124034215650711替换替换指针指针.（2 2）改进型）改进型）改进型）改进型ClockClock置换算法置换算法置换算法置换算法 该算法即考虑页面的使用情况，该算法即考虑页面的使用情况，又考虑置换代价。被淘汰页面以修改位又考虑置换代价。被淘汰页面以修改位为为0 0者为佳。者为佳。.改进型改进型Clock置换算法的细节置换算法的细节由访问位A和修改位M可以组成下面四种类型的页框：1类：A=0,M=0 最近没有被访问，也没有被修改；2类：A=0,M=1 最近没有被访问，但被修改；3类：A=1,M=0 最近被访问过，但没有被修改；4类：A=1,M=1 最近被访问过，被修改；.改进型改进型Clock置换算法的实现置换算法的实现显然第1类页面是最佳淘汰页面，应尽量避免淘汰第4类页面。算法执行的步骤如下：1从current指针开始扫描内存页框，寻找第1类页面予以替换。2如果第1步操作失败，重新扫描，寻找第2类页面，对扫描过程中途径的所有页帧A位清0。3 如果第2步也失败，指针将回到原来的位置，并且所有的页帧使用位均为0。重复第1步，必要时重复第2步。这一次一定可以找到淘汰页（最近被访问过的页面）。.（4 4）页面缓冲算法）页面缓冲算法）页面缓冲算法）页面缓冲算法 该算法是对该算法是对FIFOFIFO算法的发展，通过建立置换页面的缓冲，就有机会找回刚算法的发展，通过建立置换页面的缓冲，就有机会找回刚被置换的页面，从而减少系统被置换的页面，从而减少系统I/OI/O的开销。的开销。页面缓冲算法用页面缓冲算法用FIFOFIFO算法选择被置换页，选择出的页面不是立即换出，而是算法选择被置换页，选择出的页面不是立即换出，而是放入两个链表之一，如果页面未被修改，就将其归入到空闲页面链表的末尾，放入两个链表之一，如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入已修改页面链表末尾。这些空闲页面和已修改页面会在内存中否则将其归入已修改页面链表末尾。这些空闲页面和已修改页面会在内存中停留一段时间停留一段时间 。如果这些页面被再次访问，只需将其从相应链表中移出，。如果这些页面被再次访问，只需将其从相应链表中移出，就可以返回进程，从而减少一次就可以返回进程，从而减少一次I/OI/O开销。开销。缺页时，系统需调页，则将新页读入到空闲页面链表的第一个页面中，然后缺页时，系统需调页，则将新页读入到空闲页面链表的第一个页面中，然后将其从该链表中移出。当已修改的页面达到一定数目后，再将它们一起写入将其从该链表中移出。当已修改的页面达到一定数目后，再将它们一起写入磁盘，然后将它们归入空闲页面链表。这样能大大减少磁盘，然后将它们归入空闲页面链表。这样能大大减少I/OI/O操作的次数。操作的次数。.虚拟存储器技术的理论基础技术的可行性分析：该技术的引入不会使程序执行速度降低许多.程序执行时呈现局部性规律：指令局部性：1 程序在执行时，除少数跳转语句外，其余仍是顺序操作，即CPU下一步要访问的是本条指令之后的指令。2 一般，子程序调用的深度不会超过5，即一段时间内，内存中驻留5个正在执行中的子程序就可以满足一段时间内CPU对指令的访问需求。数据局部性：1进程对数组等数据结构进行访问会持续一段时间，即在一段时间内，进程所访问的数据仅限于与数组相关的一组变量。.工作集程序在时刻t的前时间单位中所访问的页面集合称为程序的工作集W(t,)。根据程序的局部性原理，程序在执行时将首先相对稳定地工作在某个工作集中，其中包含所有需访问的指令和数据。当程序运行于新旧段落的转折期时，工作集将巨增以容纳新的页面。经过一段时间的调整，工作集的大小降低，直到它仅包含来自新段落的页面。.驻留集驻留集是进程在主存中的图像。在虚拟存储器中进程的驻留集会随时间而变化。1 驻留集包含工作集时，进程才能运行下去2 为减少内存的消耗，os应周期性地从驻留集中移去不在工作集中的页面。3 因为驻留集不可能包含全部进程图像，因此会出现要访问的内容在磁盘中的情况，称为缺页。一般，频繁发生缺页时，进程一定工作在两个逻辑段落过渡的时刻。.驻留集的管理操作系统应该为进程分配多少个页？内存分配策略：固定分配可变分配替换范围：局部替换全局替换.三、三、三、三、请求分页中的请求分页中的请求分页中的请求分页中的页面调入策略页面调入策略页面调入策略页面调入策略(1)(1)(1)(1)调入策略决定什么时候将一个页面由外存调入内存，从何处将页面调入策略决定什么时候将一个页面由外存调入内存，从何处将页面调入内存。调入内存。q何时调入页面 v预调页策略：将那些预调页策略：将那些预计在不久便被访问的页预先调入内存。这种调入在不久便被访问的页预先调入内存。这种调入策略提高了调页的效率，减少了策略提高了调页的效率，减少了I/OI/O次数。但由于这是一种基于局部性原次数。但由于这是一种基于局部性原理的预测，若预调入的页面在以后很少被访问，则造成浪费，故这种方理的预测，若预调入的页面在以后很少被访问，则造成浪费，故这种方式常用于程序的首次调入。式常用于程序的首次调入。v请求调页策略请求调页策略：当进程运行中访问的页出现缺页时，则发出缺页中断，：当进程运行中访问的页出现缺页时，则发出缺页中断，提出请求调页，由提出请求调页，由OSOS将所需页调入内存。这种策略实现简单，应用于目将所需页调入内存。这种策略实现简单，应用于目前的虚拟存储器中，但易产生较多的缺页中断，且每次调一页，系统开前的虚拟存储器中，但易产生较多的缺页中断，且每次调一页，系统开销较大，容易产生抖动现象。销较大，容易产生抖动现象。.请求分页中的请求分页中的请求分页中的请求分页中的页面调入策略页面调入策略页面调入策略页面调入策略(2)(2)(2)(2)q从何处调入页面 在请求分页系统中，通常将外存分成了文件区和对换区，文件区在请求分页系统中，通常将外存分成了文件区和对换区，文件区按离散分配方式存放文件，对换区按连续分配方式存放对换页。按离散分配方式存放文件，对换区按连续分配方式存放对换页。v对换区：系统有足够的对换区空间，运行前可将与进程相关的文件从：系统有足够的对换区空间，运行前可将与进程相关的文件从文件区复制至对换区，以后缺页时，文件区复制至对换区，以后缺页时，全部从对换区调页全部从对换区调页。v文件区：系统没有足够的对换区空间，凡是不会被修改的文件，每次：系统没有足够的对换区空间，凡是不会被修改的文件，每次都直接从文件区调页，换出时不必换出。都直接从文件区调页，换出时不必换出。v文件区、对换区：系统没有足够的对换区空间，对可能会修改的文件：系统没有足够的对换区空间，对可能会修改的文件第一次调页直接从文件区，换出时换至对换区，以后从对换区调页。第一次调页直接从文件区，换出时换至对换区，以后从对换区调页。vUNIX方式：凡未运行过的页面均从文件区调页，运行过的页面和换出：凡未运行过的页面均从文件区调页，运行过的页面和换出的页面均从对换区调页。的页面均从对换区调页。.