现代操作系统第三章存储管理PPT.ppt

1,第三章存储管理,无存储器抽象一种存储器抽象：地址空间虚拟内存页面置换算法分页系统的设计问题有关实现的问题分段,2,存储管理,程序员对存储的要求大快不易丢失存储器分类cache-快速、昂贵、数量小主存-中速、中等价格磁盘慢速、便宜、容量大存储管理程序处理存储器层次,3,存储管理,操作系统中管理存储器层次的部分称为存储器管理程序(memorymanager)。它的任务是记录哪些内存在使用，哪些内存是空闲的，在进程需要时为其分配存储空间，在进程使用完毕后释放存储空间，以及当内存无法装入所有进程时，管理内存和磁盘间的交换。,4,无存储器抽象,单道程序多道程序,5,单道程序,最简单的存储抽象就是没有抽象早期的大型机（20世纪60年代前）、小型机（70年代前）、个人计算机（80年代前）都没有存储器抽象。每个程序直接访问物理内存。内存中不能同时运行两个程序以下是三种单道程序的存储器模型,6,单道程序,同一时刻只运行一道程序，由程序和操作系统共享内存。第一种模型曾用于大型机和小型机，不过几乎不再使用了。第二种模型用于某些掌上机和嵌入式系统。第三种模型曾用于早期的个人计算机(例如，运行MS-DOS)，其中位于ROM中的系统部分称为BIOS(BasicInputOutputSystem，基本输入输出系统)。,7,组织存储的三种简单方式,单道程序,8,无内存抽象的多道程序,使用交换技术：把当前内存中的所有内容保存到磁盘文件中，把下一个程序读入内存运行。保证某一时间内存中只有一个程序。使用硬件的帮助保护键。利用保护键防止进程间相互干扰。,9,一种存储器抽象：地址空间,地址空间：一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间。并且这个地址空间独立于其它进程的地址空间。地址空间的概念：电话号码的地址空间：0000000099999999IPv4地址的地址空间：0232-1互联网域名的地址空间：.com等,10,地址空间VS存储空间,地址空间：源程序经编译后目标程序所在的一个地址范围，通常从0开始。逻辑地址存储空间：内存中的物理存储单元的集合。物理地址,11,多道程序,除了在简单的嵌入式系统中，几乎不再使用单道程序了。大部分现代系统都允许同时运行多个程序。同时运行多个进程意味着当某个进程在等待I/O结束而阻塞时，另一个进程可以使用CPU。因此，多道程序提高了CPU的利用率。网络服务器通常可以同时运行多个进程(为不同的客户)，不过现在大多数客户(即台式机)机也具备了多道程序能力。,12,多道程序,实现多道程序的最简单方法是直接把内存划分成n个(可能是不均等的)分区。例如，可以在系统启动时手动划分。当一个作业到达时，可以放到能容纳它的最小分区的输入队列中。在该方案里，分区大小是固定的，没有被作业使用的分区空间就不得不浪费掉了。这种固定分区和单独输入队列的系统如图42(a)所示。,13,(a)每个固定内存分区都有一个单独的输入队列(b)只有单个输入队列的固定内存分区,固定分区的多道程序,14,重定位：逻辑地址到物理地址的映射。多道程序系统中，内存通常由多个进程共享；进程经常在内存和磁盘间调入、调出因此，无法确定程序将会载入到内存的什么地方。用户在程序中使用的是逻辑地址，用于内存访问之前要转换为物理地址重定位。,重定位,15,重定位,静态重定位动态重定位,16,静态重定位,当程序载入内存时直接修改指令。载入分区1的程序，在每个地址上加100K，载入分区2的程序，在每个地址加200K，等等。为了在载入时对程序重定位，链接程序必须在产生的二进制代码程序中包含列表或者位映像，由它们指出哪些程序字的地址需要重定位，而哪些是操作码、常数或者其他一些不需要重定位的项。OS/MFT系统就是这样工作的。,17,动态重定位基址寄存器和界限寄存器,基址寄存器：程序的起始物理地址界限寄存器：程序的长度在访问内存时，进程生成的每个地址都自动加上基址寄存器的内容。因此，如果基址寄存器的值为100K，CALL100指令实际上被转换为CALL100K+100，指令本身不必修改。边界寄存器自动检查指令，以确保它们没有试图访问当前分区以外的地址。由硬件保护基址和边界寄存器，以防止用户程序修改它们。,18,交换(swapping),如果计算机物理内存足够大，可以保存所有进程，那么所有方案都可行实际上，所有进程所需的RAM数量总和通常要远远超出存储器所能够支持的范围处理内存超载的方法：交换虚拟内存,19,交换(swapping),交换：把一个进程完整地调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行时就不会占用内存。,20,内存分配情况随着进程进出内存而变化阴影区域表示的是未使用的内存,交换(swapping),21,交换(swapping),当交换在内存中造成很多空洞时，通过将所有进程尽可能地向下移动，以组合成一大块，该技术称为内存压缩(memorycompaction)。该操作不经常进行，因为要耗费大量的CPU时间。例如，一台256MB的计算机40ns可以复制4个字节，它需要花费大约2.7秒钟来压缩全部内存。,22,交换(swapping),进程创建或换入时，内存的分配：根据进程需要的大小进行分配大部分进程在运行时都要增长，为减少因内存区域不够而引起的进程交换和移动所产生的开销，为进程分配一些额外的内存，如下图。,23,(a)为增长的数据段预留空间(b)为增长的数据段和堆栈段预留空间,交换(swapping),24,内存管理,分配内存时，操作系统必须对其进行管理。有两种方式可用来跟踪内存使用情况：位图链表,25,使用位图的存储管理,使用位图：内存被划分成分配单元，可能小到几个字，也可能大到几千字节。每个分配单元对应于位图中的一位，0表示空闲，1表示占用(或者相反)。内存分配：把一个占有K个分配单元的进程调入内存时，存储管理器搜索位图，在位图中找出有K个连续0的串。,26,使用位图的存储管理,分配单元的大小是重要的设计课题。分配单元越小，位图越大。位图提供了一个简单的方法来记录固定容量的内存字，因为位图的大小只依赖于内存和分配单元的大小。缺点：查找位图中指定长度的连续0串是耗时的操作,27,(a)有5个进程和3个空闲区的内存。刻度表示内存分配单元，阴影区域表示空闲(在位映像中用0表示)(b)对应的位图(c)用链表表示的同样的信息,使用位图的存储管理,28,使用链表的存储管理,使用链表：维护一个记录已分配和空闲内存段的链表，其中，段是指一个进程，或者是两个进程间的空闲区。表中的每一项都指定了如下内容：空闲区(H)还是进程(P)、起始地址、长度以及指向下一项的指针。,29,使用链表的存储管理内存分配,当有进程新建或换入时，要查找链表进行内存分配最简单的算法是首次适配(firstfit)。存储器管理程序沿着段链表搜索，直到找到一个足够大的空闲区。除非该空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分让进程使用，另一部分为未用的内存。首次适配算法是一种快速算法，因为它尽可能少搜索。,30,使用链表的存储管理内存分配,对首次适配算法的一个小变种为下次适配(nextfit)。它的工作方式和首次适配算法相同，不同点在于每次找到合适的空闲区时都记录当时的位置，以便在下次寻找空闲区时从上次结束的地方开始搜索，而不是每次都从头开始。,31,使用链表的存储管理内存分配,最佳适配(bestfit)算法搜索整个链表，找出足够大的最小空闲区。最佳适配算法试图找出最接近实际需要的空闲区，而不是使用将来需要的大空闲区。为了避免最接近适配的空闲区会分裂出极小空洞的问题，有人考虑到最差适配(worstfit)，即总是分配最大的空闲区，使分裂出来的空闲区够大从而可以继续使用。,32,进程X终止前后的四种情况,使用链表的存储管理内存回收,33,虚拟内存,虽然存储器容量增长快速，但是软件大小的增长更快。操作系统必须能够支持多个程序同时运行，即使内存可以满足其中单独一个程序的需要，但总体上看，它们超出了内存大小交换甚至，需要运行的程序大到内存无法容纳覆盖、虚拟内存,34,虚拟内存,覆盖：把程序分割成许多片段，逻辑上没有调用关系的段可以相互覆盖，称为覆盖段。这些段可以共享内存。覆盖段存放在磁盘上，需要时由操作系统动态地在内存和磁盘间换入换出。覆盖段换入换出由系统完成，但是覆盖段的分割由程序员负责增加了程序员的负担。因此，虚拟内存技术出现。,35,虚拟内存,虚拟内存的基本思想是：程序、数据和堆栈的总量可能超过可用的物理内存的大小。操作系统把程序当前使用的部分保留在内存中，而把其他部分保存在磁盘上。虚拟存储器也可以工作于多道程序系统，在内存中同时有多个程序的片断。当一个程序等待它的一部分被调入时，它是等待I/O而不能运行，因此，可以把CPU交给另一个进程，就像在任何其他多道程序系统中一样。,36,分页(Paging),虚拟地址：程序产生的地址。它们构成了一个虚拟地址空间。物理地址：物理内存地址。内存管理单元(MMU)：将虚拟地址映射为物理地址，如下图所示。,37,MMU的位置和功能,分页(Paging),38,分页(Paging),下图给出了一个说明了该映射是如何工作的简单例子。在这个例子中，有一台可以生成16位地址的计算机，地址范围从0到64K。这些地址是虚拟地址。但是，该计算机只有32KB的物理内存，因此，虽然可以编写64-KB的程序，但是却不能将它们整个地载入内存运行。在磁盘上必须有一个64KB的程序内核映像，以保证程序片段在需要时能载入内存。,39,分页(Paging),页表表示虚拟地址和物理内存地址的关系,40,分页(Paging),页面(page)：根据页的大小将虚拟地址空间划分的单元页框(pageframe)：根据页的大小在物理内存中划分的单元页面大小=页框大小，并且由操作系统负责划分在本例中是4KB，现有的系统中常用的页大小一般从512字节到64KB。对应于64KB的虚拟地址空间和32KB的物理内存，它们分别有16个虚拟页面和8个页框。RAM和磁盘之间的传输总是以页为单位的。,41,分页(Paging),页面地址结构根据页的大小确定页号和页内偏移。例如页大小是4KB（212B），则需要12比特表示页内地址，剩余的高位则是页号,42,分页(Paging),内存分配原理：程序载入内存时，不必把所有页面都载入内存。只有部分页面在内存，而其余页面在磁盘上。当需要访问磁盘上的页面时，产生缺页中断，由操作系统负责把磁盘上的页面调入内存。,43,分页(Paging),地址映射页表页表每个进程一个页表。其中记录了页面到页框的映射关系，见下图。地址映射时，MMU查找页表，根据页面号查找到相应的页框号，完成地址变换。,44,分页(Paging),页表,45,16个4K页时MMU的内部操作,分页(Paging)地址映射,46,分页(Paging)地址映射,例1，把虚拟地址8196映射为物理地址8196MMU(8196)10即(0010000000000100)2其中低12位是页内偏移：000000000100剩余高位是页面号：0010根据页面号0010查找页表，“在/不在”位为1，可直接得出对应于该页的页框号110。页框号+页内偏移物理地址0110000000000100,47,分页(Paging)地址映射,例1：8196映射为物理地址(十进制的方法)4KB的页面，即40968196/4096商：2-页号余数：4-页内偏移通过页号2查页表-页框号110，即6页框号*页面大小+页内偏移物理地址6*4096+4=24580,48,分页(Paging)地址映射,例2，执行指令MOVEREG3278032780MMUMMU判断32780属于虚页8：1000000000000100通过页面号查找页表，发现虚页8未映射（“在/不在”位为0）产生一个缺页中断(pagefault)，由操作系统寻找一个页框将它的内容写入磁盘，并将虚页8的内容取到刚才的页框中，并修改页表中的映射关系页框号+页内偏移物理地址,49,页表(PageTable),在最简单的情况下，虚拟地址到物理地址的映射正如前面描述的。虚拟地址被分成虚页号(高位)和偏移(低位)。虚页号可用做页表的索引，以找到该虚页对应的页表项。从页表项可以找到页框号。页框号被拼接到偏移的高位端，替换掉虚页号，以形成可以发送给内存的物理地址。页表的目的是把虚页映射到页框。从数学角度说，页表是一个函数，虚页号作为参数，物理页框号作为结果。使用该函数的结果，可以把虚拟地址中的虚页域替换成页框域，从而形成物理内存地址。,50,页表项的结构,页面号作为页表的索引页框号：最重要的域。用于地址映射在/不在位：表示页面是否在内存，如果访问不在内存的页面会引起缺页中断。保护位：指出该页允许访问的类型，例如只读、读写等修改位（脏位）：记录页面的使用情况。在写入一页时由硬件自动设置该位访问位：页面被访问时设置该位。高速缓存禁止位：用于映射到设备寄存器的页面，通过该位禁止高速缓存。,51,加速分页过程,分页系统实现中的两个主要问题：地址映射的速度，页表的设计应考虑查找速度。每次访存，都需要进行地址映射。所有指令最终都必须来自内存，而且指令可能会访问内存中的操作数，因此每条指令的执行都可能会多次访问页表。页表可能非常大：设计算机地址是32位，即地址空间大小4GB，若页大小是4KB，则每个进程的页表最多要有4G/4K=220个表项（约100万个）。而且每个进程都需要一张页表。,52,加速分页过程,最简单的设计是使用由一组快速硬件寄存器组成的单一页表，每个虚页一项，按虚页号索引。在一个进程启动时，操作系统将进程的页表装入寄存器，在进程运行期间不必因为页表而访问内存。该方法的优点是直观并且在映射时不需要访问内存，其缺点是非常昂贵。而且，每次内容切换时都要载入整个页表而损害性能。,53,加速分页过程,另一种极端是把页表全部放在内存中。此时，需要的全部硬件只是一个指向页表起始地址的寄存器。该设计使得在上下文切换时，只需重新载入该寄存器就可以改变内存映射。当然，它的缺点是执行每条指令时都需要一次或多次访问内存以读取页表项。因此，该方法很少以最单纯的方式使用，下面我们将研究一些比它的性能要好得多的变种。,54,加速分页过程,加速分页的方法转换检测缓冲区软件TLB管理,55,TLB转换检测缓冲区,该设计在计算机上装备一个小的硬件设备以映射虚拟地址到物理地址，而无需通过页表。该设备称为TLB(TranslationLookasideBuffer，转换检测缓冲区)，有时候也称为相联存储器(associativememory)。它通常位于MMU内部，由少数项组成，本例中有8项，不过很少超过64项。每项都包含有一个页面的信息，包括虚页号、已修改位、保护码(读/写/执行许可)以及该页所对应的物理页框。另有一位表示该项是否有效(即是否在使用)。,56,TLB进行加速分页,TLB转换检测缓冲区,57,工作原理：,TLB转换检测缓冲区,58,性能分析：命中率：通过TLB实现内存访问的比率设页表访问时间100ns,TLB访问时间20ns，命中率90%，则平均访问时间：100*10%+20*90%=28ns,TLB转换检测缓冲区,59,软件TLB管理,TLB管理以及TLB错误的处理全部由MMU硬件完成。只有当页不在内存中时才激活操作系统陷阱。有很多策略已被开发用于TLB的软件管理，以提高机器性能。其中一种方法可以同时减少TLB失败以及当发生TLB失败时的代价(Bala等，1994)。无论是硬件还是软件，处理TLB失败的通常方法都是转向页表，并执行索引操作以定位页引用。,60,针对大内存的页表,分页系统实现中的第二个问题大页表的处理多级页表倒排页表,61,多级页表,为了避免始终在内存中保存庞大的页表，许多计算机中采用了多级页表。一个简单的例子如下图所示。在图(a)中，32位的虚拟地址被划分为10位的PTl域、10位的PT2域和12位的偏移。偏移为12位，所以页长是4KB；二级页表的表项有1024个(可表示1024*4KB=4MB的地址范围)；顶级页表的表项1024个，因此可表示的地址范围：1024*4MB=4GB。,62,(a)有2个页表域的32位地址(b)两级页表,多级页表,63,多级页表,多级页表的的秘诀就是避免把全部页表一直保存在内存中。特别是那些不需要的页表不应该保留。例：一个需要12MB内存的进程，其最底端是4MB的程序正文段，其后是4MB的数据段，顶端是4MB的堆栈段，在数据段上方和堆栈段下方是大量没有使用的空闲区。则内存中只需要保存该进程的顶层页表一个，第二层页表3个（3*4MB=12MB）。,64,倒排页表(invertedpagetable),在该设计中，实际内存中的每个页框对应一项，而不是每个虚拟地址空间的页对应一项。例如，64位虚拟地址，4-KB的页，以及256MBRAM，则虚页有264/212=252个、页框有228/212=65536个。倒排页表以页框号作索引，只需65536项。每项记录哪些(进程、虚页)位于页框中。在虚拟地址空间比物理空间大很多的时候，倒排页表节省了大量空间，但是它们有一个致命弱点：虚拟到物理的转换非常困难。解决方法就是使用TLB改进：使用散列索引技术。虚页号根据一个哈希函数生成散列值，此值作为页表的索引，相同散列值的虚页链接在一起,65,传统页表与倒排页表的比较,倒排页表(invertedpagetable),66,地址变换时，当需要的页面不再内存时，发生缺页中断，操作系统选择哪些页必须删除给进入的页腾出空间已修改的页必须首先保存下来未被修改的只需覆盖就行了最好不要选择经常使用的页可能马上又要用到这些页,页面置换算法,67,最优页面置换算法最容易描述，但不可能实现。该算法是这样工作的：发生缺页时，某些页面在内存中。其中有一页将很快被引用，其他页则要以后才会被访问。每个页都可以用该页面首次被访问前所要执行的指令数进行标记。,最优页面置换算法,68,最优页面置换算法,最优页面置换算法只是简单地规定，标记最大的页应该被淘汰掉。如果一个页在800万条指令内不会被使用，另外一个页在600万条指令内不会被使用，则淘汰掉前一个，从而把因为需要取回该页而发生的缺页推后，越远越好。这个算法唯一的一个问题是它是无法实现的。发生缺页时，操作系统无法知道各个页面下一次是在什么时候被引用。虽然这个方法在实际系统中毫无用处，但对评价页面置换算法很有用。,69,为每个页面设置两个状态位：引用位R表示页面被访问；修改位M表示页面被写入当页面被访问、被修改时设置相应位R位被定期地清零页面分为以下几类：第0类：没有被访问，没有被修改00。第1类：没有被访问，已被修改01。第2类：已被访问，没有被修改10。第3类：已被访问，已被修改11。,最近未使用(NRU)算法,70,最近未使用(NRU)算法,NRU(NotRecentlyUsed，最近未使用)算法随机地从编号最小的非空类中挑选一页删除。这个算法隐含的意思是，删除一个在最近一个时钟周期中没有被引用的已修改页要比清除一个被频繁访问的“干净”页好。NRU吸引人的地方是其易于理解和能有效地实现，并且尽管其性能不是最好的，但还是足够的。,71,思想：选择在内存驻留时间最长的页淘汰。操作系统维护一个当前在内存中的所有页面的链表，最老的页面在表头，最近到达的页面在表尾。发生缺页时，删除表头的页面，并把新页添加到表尾。缺点：未考虑程序的动态特性。在顺序访问时较理想，但对于循环程序段，往往把会频繁访问的页面周期性选择为淘汰对象。一般不单纯使用FIFO算法，要结合其它技术。,先进先出(FIFO),72,第二次机会(secondchance),FIFO算法可能会把经常使用的页面置换出去，为了避免该问题，对该算法做了简单的修改：检查最老页面的R位。如果R为0，则该页面既老又没用，因此立刻置换；如果是1，就清除该位，并将该页放到链表的尾端，更新其载入时间使它就像刚到达内存一样。然后继续搜索其它页。实质：寻找一个自上次检查以后未被访问的页淘汰。与NRU区别：R位不是定期清零，检查链表时才清除。,73,(a)按FIFO排序(b)时间20时发生缺页，A的R位被设置(数字为载入时间),第二次机会(SecondChance),74,时钟(Clock)页面置换算法,尽管第二次机会算法是一个合理的算法，但它经常要在链表中移动页面，既降低了效率，又没有必要。一个更好的办法是把所有的页保存在一个类似钟表面的环形链表中，有一个指针指向最老的页面。缺页发生时检查指针所指向的页面R=0，选择该页淘汰，算法结束。若R=1，则清除R位：R0指针加1，继续检查,75,时钟(Clock)页面置换算法,76,最久未使用(LRU)算法,对最优算法的良好近似是基于这样的观察：即在最近几条指令中使用频繁的页面很可能在接下来的几条指令中频繁使用。反过来说，已经很久没有使用的页面很有可能在未来较长的一段时间内也不会被用到。该思想提示了一个可以实现的算法：发生缺页时，淘汰未使用时间最长的页。该策略称为LRU(LeastRecentlyUsed，最久未使用)分页。,77,一种实现：维护一张链表，最近使用的页位于表头，最久未使用的页的位于表尾；每次内存访问都要更新链表（把最新访问的页移到表头）,最久未使用(LRU),78,最久未使用(LRU),一种硬件实现方法：有一个64位计数器C，它在每条指令执行完后自动加1。而且，每个页表项还必须有足够容纳该计数器的域。在每次访问内存后，C的当前值被保存到刚刚被引用页面的页表项中。发生缺页时，操作系统检查页表中所有的计数器以找出最小的一个。该页就是最久未使用的页。,79,最久未使用(LRU),第二种硬件LRU算法。有n个页框的机器中，LRU硬件可以维持一个nn位的矩阵，其初始值全部为0。每当引用到页k时，硬件首先把行k所有位都设置成1，再把列k所有位都设置成0。任何时刻，二进制值最小的行就是最久未使用的，第二小的行是下一个最久未使用的，依此类推。,80,LRU使用矩阵页面被引用的顺序为0,1,2,3,2,1,0,3,2,3,最久未使用(LRU),81,软件模拟LRU,前面两种LRU算法在理论上都可以实现，但只有非常少(如果有的话)的计算机有这种硬件，因此需要的是可以用软件实现的解决方案。一种可能的方案称为NFU(NotFrequentlyUsed，不经常使用)算法。该算法需要一个初值为0的软件计数器与每页相联。每次时钟中断时，操作系统扫描内存中的所有页面，将每页的R位(其值为0或1)加到其计数器上。缺页时淘汰计数器值最小的页实质：跟踪每页被访问的频繁程度,82,老化算法,对NFU算法的修改：先将计数器右移一位把R位加到计数器的最左端称为老化(aging)算法，很好地模拟了LRU。假设，在第一个时钟周期后，页0到5的R位值分别是1、0、1、0、1、1(页0为1，页1为0，等等)。换句话说，在时钟周期0到时钟周期1期间，页0、2、4、5被引用，设置其R位为1，而其他页仍然是0。对应的6个计数器在经过移位并把R位插入其左端后的值如下图所示。图中后面的4列是在接下来4个时钟周期后的6个计数器的值。,83,用软件模拟LRU的老化算法。图中所示是6个页面在5个时钟周期的情况，5个时钟周期分别由(a)(e)表示,老化算法,84,工作集(workingset),在单纯的分页系统里，启动进程时，内存中没有其页面。当CPU试图取第一条指令时就会产生一次缺页，使操作系统载入含有第一条指令的页。其他关于全局变量和堆栈的缺页通常会紧接着发生。一段时间以后，进程已经有了大部分其所需的页，开始安定运行，较少发生缺页了。这个策略称为请求调页(demandpaging)，因为页面只在需要时载入，而不是预先载入。,85,工作集(workingset),进程当前正在使用的页的集合称为它的工作集(workingset)。如果整个工作集都在内存中，进程的运行很少引起缺页，除非进入下一运行阶段。如果内存太小而无法容纳整个工作集，进程的运行会产生大量的缺页，且运行缓慢，由于通常执行一条指令只需要几个纳秒，而从磁盘上读入一个页面一般需要几十个毫秒。程序每执行几条指令就发生一次缺页，称为系统颠簸(thrashing)。,86,工作集(workingset),不少分页系统都设法记录进程的工作集，以确保进程运行以前，其工作集就已在内存中。该方法称为工作集模型(workingsetmodel)。其目的在于大大减少缺页率。进程运行前载入页面，也称为预先分页(prepaging)。注意：工作集一直在变化。,87,工作集是由k个最近内存引用使用的页面组成的集合。函数w(k,t)是工作集在时刻t的大小。,工作集(workingset),88,基于工作集的页面置换算法当前虚拟时间(CVT)：一个进程从它启动开始到现在所实际占用的CPU时间工作集：在进程虚拟时间中，过去秒内所访问过的页面集合思想：缺页时，淘汰不在工作集中的页面实现：页表项中有一个域记录页面最近使用时间(LUT)，R位每次时钟中断清零。发生缺页时，搜索页表，检查R位：R=1，LUTCVT(表示缺页时，此页面被访问）R=0&age=CVT-LUT(此页不在工作集中），选择该页淘汰）R=0&age=，记下age最大者重复上述步骤，无第2种情况存在，则选择age最大者淘汰（LUT最小者）；若第2、3都不存在，则选择一个M=0的页面淘汰,工作集(workingset),89,工作集算法,工作集(workingset),90,工作集时钟(WSClock),由于在每次缺页时都要扫描整个页表直到定位一个合适的候选，因此工作集算法还是比较麻烦。基于时钟算法，但是同样使用工作集信息的改进算法称为工作集时钟(WSClock)。由于其易于实现而且性能优良，在实际中被广泛使用。它所需的数据结构是页框的一个环形链表，和时钟算法一样。,91,WSClock算法的操作,工作集时钟(WSClock),92,页面置换算法示例,设内存有三个页框页面访问顺序232152453252（访问串）,最优页面置换算法6次缺页LRU7次缺页,93,页面置换算法示例,设内存有三个页框页面访问顺序232152453252,FIFO9次缺页,94,页面置换算法小结,95,页面置换算法小结,最优算法置换当前页中最后引用的页。不幸的是，没有办法确定哪一页最后，因此实际当中无法使用该算法。不过，它可以作为基准用于测试其他算法。NRU算法根据R和M位将页面分成四类。从最低序号的类中随机选择一页。该算法易于实现，但过于粗糙。还有更好的一个算法。FIFO通过链表记录页面载入内存的次序。删除最老的页面，不过该页框可能仍在使用当中，因此FIFO不是一个好的选择。,96,页面置换算法小结,第二次机会是FIFO的一种改进，该算法在删除页面之前检测其是否正在使用中。如果是，则保留该页。这一改进大大提升了性能。时钟算法与第二次机会的实现稍有不同。它具有相同的性能属性，不过算法的执行时间要少一些。LRU是一种极好的算法，但是没有特殊的硬件就无法实现。如果没有这种硬件设备，就无法使用该算法。NFU是对LRU的简单近似，并不很好。不过，老化技术是对LRU的很好的近似，而且可以有效地实现，是一种不错的选择。,97,页面置换算法小结,最后两种算法都使用工作集。工作集算法具有相当好的性能，不过其实现的代价稍大。WSClock是一个变种，不仅有好的性能，而且可以有效实现。总而言之，最好的两种算法就是老化和WSClock。它们分别基于LRU和工作集。两者都有好的分页性能，也都能有效地实现。还有几种其他的算法，不过这两个算法大概是实际中最重要的。,98,分页系统中的设计问题,局部与全局分配策略(LocalversusGlobalAllocationPolicies)负载控制(LoadControl)页面尺寸(PageSize)指令和数据空间分离(SeparateInstructionandDataSpaces)共享页面(SharedPages)清除策略(CleaningPolicy)虚拟存储器接口(VirtualMemoryInterface),99,局部与全局分配策略,局部算法实际上对应于为每个进程分配固定的内存片段；全局算法在可运行进程之间动态地分配页框。因此，分配给各个进程的页框数是随时间变化的。通常，全局算法工作得更好，特别是当工作集的大小随进程的生命期发生变化时尤甚。若使用局部算法，即使有大量的空闲页框存在，工作集的增长也会导致颠簸；如果工作集缩小了，局部算法将浪费内存。如果使用全局算法，系统必须不停地确定该给各个进程分配多少页框。,100,局部与全局页面置换(a)原始配置(b)局部页面置换（选择本进程的页面A5置换）(c)全局页面置换（选择内存中的页面B3置换）,局部与全局分配策略,101,局部与全局分配策略,如果采用全局算法，可以在每个进程启动时根据进程大小分配一定数目的页，不过在进程运行时该分配必须动态地更新。管理分配可以使用PFF(PageFaultFrequency，缺页率)算法。它告知什么时候增加或减少进程的页分配，不过不涉及缺页时置换哪一页。它只是控制分配集的大小。,102,缺页率是已指派的页框数的函数,局部与全局分配策略,103,无论设计多么好，系统仍旧有可能崩溃PFF算法表明：某些进程需要更多的内存但是没有进程会希望削减自己的内存占有量解决方案:减少竞争内存的进程数目将一个或多个进程交换到磁盘上，分割它们所占有的页面重新考虑多道程序的度,负载控制(LoadControl),104,页面尺寸(PageSize),确定最佳的页面尺寸需要在几个互相矛盾的因素之间进行平衡。一般情况下，最后一页中有一半是空的。该页中多余的空间就被浪费掉了，这种浪费称为内碎片(internalfragmentation)。对于小页面：小页面内部碎片少适用于各种数据结构和代码块内存中无用的程序少缺点：程序需要很多页面，页表大载入页寄存器的时间长,105,代价取决于页表和内部碎片式中：s=平均的进程大小(字节)p=页面大小(字节)e=页表项大小(字节),页面尺寸(PageSize),106,指令和数据空间分离,大多数计算机都有保存程序和数据的单一地址空间，但是，它通常都太小，迫使程序员绞尽脑汁以使所有东西放进该地址空间之内。由(16位)PDP-11首先提出的一种解决办法是给指令(程序正文)和数据以分离的地址空间。这些分别被称为I-空间(I-space)和D-空间(D-space)。在这种计算机中，两种地址空间能被彼此独立地分页。每个都有其自己的分页表，以及其自己对物理页框到虚页的映射。,107,(a)单地址空间(b)分离I和D空间,指令和数据空间分离,108,共享页面(SharedPages),在大的多道程序系统中，通常有几个用户同时运行相同的程序。显然，共享页面更有效率，避免同时在内存中有相同页面的两个拷贝。问题是并非所有页面都是可共享的。尤其是那些只读页面，例如程序正文，可以共享，但是数据页不能。如果支持分离的I和D-空间，可以相对简单地由两个或多个进程共享程序，I-空间使用相同的页表，而D-空间使用不同的页表。典型地，在实现支持这种共享时，页表的数据结构独立于进程表。,109,两个进程共享同一个程序，共享它的页表,共享页面(SharedPages),110,需要一个后台的进程分页监控程序周期性地检查内存状态当空页太少时使用某个替换算法选择需要清除的页面可以使用同一个循环表(时钟)如同具有不同指针的正规页面替换算法,清除策略(CleaningPolicy),111,虚拟存储器接口,在一些高级系统中，程序员可以对内存映射有某些控制，而且可以使用非传统的方式来增强程序行为。赋予程序员对其内存映射控制的一个理由是，可以允许两个或多个进程共享相同的内存。页面共享也能用于实现高性能的消息传递的系统。还有另一种高级的存储器管理技术称为分布式共享内存(distributedsharedmemory)。其思路就是允许多个进程通过网络共享一组页面，就如同单一的共享线性地址空间一样。,112,实现时涉及的问题,与分页有关的工作缺页中断处理指令备份锁定内存中的页面后备存储策略和机制的分离,113,与分页有关的工作,OS进行分页的四个时刻：进程创建确定程序大小，创建页表进程运行对新的进程重置MMU，刷新TLB缺页时确定引起缺页中断的虚拟地址选择某一目标页将其换出，需要的页换入进程终止时释放页表和内存中占用的页框,114,缺页中断处理,硬件陷阱进入内核，将程序计数器保存到堆栈。启动一个汇编代码程序来保存通用寄存器和其他易失的信息，以免被操作系统破坏。操作系统发现一个缺页时，试着查找需要哪个虚页。一旦知道了发生缺页的虚拟地址向进程发一个信号或杀掉该进程（虚址是无效的）检查是否有空闲页框运行页面置换算法(没有空闲页框),115,缺页中断处理,如果选择的页框是脏的，该页被写回磁盘。一旦页框干净了，操作系统查找所需页在磁盘上的位置，并调度磁盘操作将其载入。当磁盘中断表明该页已经到达，更新页表以反映其位置，该页框被标记为一般状态。恢复失败的指令到其原有的状态，重置程序计数器以指向该指令。调度缺页进程，操作系统返回调用它的汇编语言程序。该程序重新载入寄存器和其他状态信息，并返回用户空间继续执行，就如同没有发生缺页一样。,116,指令备份,当程序访问不在内存中的页面时，引起缺页的指令半途中止并对操作系统发出陷阱。操作系统取出所需的页后，必须重新启动引起陷阱的指令。但说起来容易做起来难。在一些机器中，CPU设计者提供了一个解决方法，通常在每条指令执行前将程序计数器复制到一个隐藏的内部寄存器中。,117,导致缺页的指令,指令备份,118,虚拟内存和I/O偶尔会相互影响进程发出调用从设备读入缓冲区在等待I/O时,另一个进程开始了导致一个缺页第一个进程的缓冲区可能被选择清除掉需要指定某些页面被锁定以保证其不会被删除,锁定内存页,119,后备存储,在磁盘上分配页空间的最简单的算法是在磁盘上设置特殊的交换区。当系统启动时，该交换区为空，并在内存中以单独的项给出其起点和容量。每个进程对应交换区的磁盘地址保存在进程页表中。写回一页时地址的计算很简单：将虚拟地址空间中页的偏移加到交换区的起始位置上。,120,后备存储,一种方法是将整个进程映像复制到交换区，使得需要时可将其载入；另一种方法是将整个进程载入内存，并在需要时换出。另一个极端的情况就是事先什么也不分配，而是在页换出时分配磁盘空间，在换入时回收。这样，内存中的进程不必固定于任何交换空间，缺点是内存中需要一个磁盘地址来记录磁盘上的每页。,121,(a)分页到静态交换区(b)动态备份页面,后备存储,122,策略与机制分离,存储器管理系统被划分成三个部分：低级的MMU处理程序缺页处理程序是内核的一部份外部的分页程序运行于用户空间该实现方法的主要优点就是代码更加模块化，更加灵活。主要的缺点就是多次穿越用户-内核边界的额外开销，以及在系统各部分之间发送各种不同消息的开销。,123,使用外部分页程序的缺页处理,策略和机制的分离,124,分段(Segmentation),在机器上提供多个互相独立的地址空间，称之为段(segment)。每个段由线性地址序列构成，从0到某个最大值。每个段的长度可以是0到允许的最大值之间的任意值。不同的段的长度可以不同，而且通常也是不同。段的长度在运行期间可以改变。堆栈段的长度在数据压入时增长，在数据弹出时减小。,125,在一维地址空间中，有多个动态增长的表时，一个表可能会撞上另一个,分段(Segmentation),126,分段(Segmentation),由于每个段都构成了一个独立的地址空间，不同的段可以独立地增长或减小而不会影响其他的段。如果某个段中的一个堆栈需要更多的地址空间来增长，它可以做到，因为在它的地址空间中没有任何其他东西阻挡。当然，段有可能被装满，不过段通常很大，所以这种情况发生的可能性很小。要在这种分段的或二维的存储器中指明一个地址，必须提供一个两段式地址：段号和段内地址。,127,分段内存允许每个表独立于其他表增大或减小。,分段(Segmentation),128,分段(Segmentation)基本原理,分段程序划分为若干个段，每个段定义了一组逻辑信息，可以是一张表，一个堆栈等每个段从0编址，段长度不等整个程序的地址空间由多个段组成，是二维的。即逻辑地址由段号和段内地址组成,129,分段(Segmentation)基本原理,分段系统的地址结构上例的地址结构中，允许每个段的最大长度是216B（64KB），一个程序最多允许有216（64K）个段,130,分段(Segmentation)基本原理,段表可变分区（交换）：系统为整个进程分配一个连续的内存空间分段：系统为每个段分配一个连续的分区，而进程中的各个段可以离散地放在内存不同的分区中段表：记录每个段在内存的起始地址及段长,131,分段(Segmentation)基本原理,地址变换机构类似于分页根据逻辑地址中的段号查找段表找到该段的起始地址+段内地址，即物理地址,132,分段(Segmentation),优点：能简化伸缩的数据结构允许程序修改并独立重新编译，不需整个程序集重新链接，链接例程的操作就可以大大地简化有助于在几个进程之间共享例程和数据不同的段可以有不同种类的保护,133,分段(Segmentation),分段与分页的比较页是物理单位而段是逻辑单位页大小固定且由系统确定，对用户是透明的；段大小不固定，取决于用户编写的程序，对用户是不透明的。分页的目的是提高内存利用率，而分段是为了满足用户的需要（即分段的优点）分页系统的地址空间是一维，而分段是两维。,134,分页和分段的比较,分段(Segmentation),135,纯分段的实现,分段和分页的实现有着本质的区别：页是定长的，而段不是。在系统运行一段时间后，内存被划分为许多块，一些包含段，一些包含空洞，这种现象被称为棋盘(checkerboarding)或者外碎片(externalfragmentation)。它在空闲区上浪费了内存，而这可以通过压缩来解决。,136,(a)-(d)棋盘的生长(e)通过压缩消除棋盘,纯分段的实现,137,分段和分页结合段页式系统,基本原理用户程序分段，每个段再分页地址结构：,138,分段和分页结合段页式系统,数据结构页表：每个段一张页表段表：与纯分段不同，记录的是页表始址和页表长度,139,分段和分页结合段页式系统,地址变换过程根据逻辑地址中的段号查找段表得到页表地址根据页表地址找到相应页表，根据页号查找页表，得到页框号页框号+页内地址，得到物理地址,140,分段和分页结合：MULTICS,如果段比较大，把它整个保存在内存中可能不方便，甚至是不可能的。这导致了对它进行分页的想法，这样，只有那些实际需要的页才被载入。MULTICS的设计者决定把每个段当成一个虚拟存储器并对它进行分页，以结合分页的优点(统一的页面尺寸以及在只使用一部分时不用把整个段全部保存在内存)和分段的优点(易于编程、模块化、保护和共享)。,141,MULTICS的虚拟存储器(a)描述符段指向页表(b)个段描述符，其中数字为域的长度。,分段和分页结合：MULTICS,142,分段和分页结合：MULTICS,MULTICS的地址由两部分构成：段和段内地址。段内地址又进一步分为页号和页内地址，进行发生内存引用时，算法如下：使用段号找到段描述符。检查该段的页表是否在内存中。如果在，定位其位置；如果不在，就发出一个缺段。如果违反了段的保护要求，发出一个错误(陷阱)。检查所请求虚页的页表项。如果页面不在内存中，则发出一个缺页；如果在内存中，就从页表项中提取该页在内存中的起始地址。把偏移地址加到页的起始地址上，得到要访问的字在内存的地址。最后进行读或写操作。,143,34位的MULTI