第4章__存储管理计算机操作系统第三版ppt课件

第4章存储管理,4.1概述4.2分区存储管理方案4.3页式存储管理4.4段式存储管理4.5段页式存储管理4.6交换技术与覆盖技术4.7虚拟存储4.8高速缓冲存储器4.9内存管理实例分析习题,4.1概述,存储器是计算机系统中的重要组成部分，随着计算机技术的飞速发展和内存价格的降低，现代计算机中的内存也在不断增加，已经达到GB的范围。,4.1.1存储体系存储器的功能是保存指令和数据，它的发展方向是高速、大容量和小体积，诸如内存在访问速度方面的发展有DRAM、SDRAM、SRAM等技术；而磁盘技术的发展方向主要在大容量方面，比如接口标准、存储密度等。,存储组织的功能是在存储技术和CPU寻址技术许可的范围内组织合理的存储结构，其依据是访问速度的匹配关系、容量要求和价格。常见的存储结构有两种：“寄存器内存外存”结构和“寄存器快速缓存内存外存”结构。图4.1所示的是“寄存器快速缓存内存外存”结构。,图4.1存储层次结构,从源程序到程序执行,编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。,库,地址空间的概念,物理（绝对）地址程序执行每个内存单元的固定顺序地址（编号）。逻辑（相对）地址装入（汇编编译）被链接装配（或汇编、编译）后的目标模块所限定的地址的集合；相对于某个基准量（通常为：0）的编址。,4.1.2地址重定位可执行文件的建立过程是：源程序编译目标模块(多个目标模块或程序库)链接可执行文件。当程序执行时由操作系统装入内存而成为进程。对程序员来说，数据的存放地址是由符号决定的，故称为符号名地址，或者称为名地址。,当程序被装入内存时，程序的逻辑地址被转换成内存的物理地址，称为地址重定位。在可执行文件装入时需要解决可执行文件中地址(指令和数据)和内存地址的对应问题。这是由操作系统中的装入程序Loader来完成的，如图4.2所示。,图4.2地址重定位,1绝对装入(absoluteloading)在可执行文件中记录内存地址，装入时直接定位于上述内存地址的方式称为绝对装入(或者称为固定地址再定位)。在这种方式下，程序的地址再定位是在执行之前被确定的，也就是在编译、链接时直接制定程序在执行时访问的实际存储器地址。这样，程序的地址空间和内存地址空间是一一对应的。单片机或者单用户系统常采用这种方式。固定地址再定位的优点是装入过程简单；缺点是过于依赖于硬件结构，不适合多道程序系统。,2可重定位装入(relocatableloading)可重定位装入方式是指在可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应的偏移量。一个有相对地址空间的程序装入到物理地址空间时，由于两个空间不一致，就需要进行地址变换，或称地址映射，即地址的再定位。地址再定位有两种方式：静态再定位和动态再定位。,1)静态再定位静态再定位是指当程序执行时，由装入程序运行重定位程序，根据作业在内存重分配的起始地址，将可执行的目标代码装入到指定内存中。所谓静态，是指地址定位完成后，在程序的执行期间将不会再发生变化。静态再定位是在程序执行之前进行地址再定位的，这一工作通常是由装配程序完成的。,静态重定位示意图,静态地址再定位的优点是：无需硬件地址变化机构支持，容易实现；无需硬件支持，它只要求程序本身是可再定位的；它只对那些要修改的地址部分做出某种标识，再由专门设计的程序来完成。在早期的操作系统中大多数都采用这种方法。静态地址再定位的缺点是：必须给作业分配一个连续的存储区域，该存储区不能分布在内存的不同区域；在作业的执行期间不能扩充存储空间，也不能在内存中移动，因而不能重新分配内存，不利于内存的有效利用；多个用户很难共享内存中的同一程序，如若共享同一程序，则各用户必须使用自己的副本。,2)动态再定位动态地址再定位是在程序执行期间，在每次存储访问之前进行的。程序在装入内存时，并不修改程序的逻辑地址值，而是在访问物理内存之前，再实时地将逻辑地址转换成物理地址。在这种情况下，其实现机制要依赖硬件地址变换机构，即通过基地址寄存器BR、变址寄存器VR计算出指令的有效地址，再利用硬件机构实现地址变换，如图4.3所示。,图4.3动态地址再定位的原理,从图4.3中可以看出：当程序开始执行时，系统将程序在内存的起始地址送入BR中。执行指令时，系统将逻辑地址与BR中的起始地址相加，从而得到物理地址。动态地址再定位的优点是：程序在执行期间可以换入和换出内存，这样可以缓解内存紧张的矛盾；可以把内存中的碎片集中起来，以充分利用空间；不必给程序分配连续的内存空间，可以较好地利用较小的内存块；若干用户可以共享同一程序。,动态地址再定位的缺点：需要附加的硬件支持，而且实现存储管理的软件算法比较复杂。,3动态运行期装入动态运行期装入(dynamicrun-timeloading)是指在可执行文件中记录虚拟内存地址，在装入和执行时通过硬件地址变换机构完成虚拟地址到实际内存地址的变换。动态运行期装入的优点是：操作系统可以将一个程序分散存放于不连续的内存空间，可以通过移动程序来实现共享；能够支持程序执行中产生的地址引用，如指针变量(而不仅是生成可执行文件时的地址引用)。动态运行期装入的缺点是：需要硬件支持(通常是CPU)，操作系统的实现比较复杂。,4.1.3链接1链接方法常见的链接方法有静态链接和动态链接两种。1)静态链接静态链接(staticlinking)是在生成可执行文件时进行的，即在目标模块中记录被调用模块的名字符号地址(symbolicaddress)，在可执行文件中将该名字改写为指令直接使用的数字地址，如图4.4所示。,图4.4静态链接,2)动态链接动态链接(dynamic-linking)是在运行可执行文件时进行的,亦即，执行过程中，当发现一个被调用模块未装入内存时，立即取找到该模块，并链接到调用者模块上。通常被链接的共享代码称为动态链接库(DynamicLinkLibrary，DLL)或共享库(sharedlibrary)。,动态链接的优点是：(1)共享：多个进程可以共用一个DLL，比较节省内存，从而可以减少文件的交换。(2)部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作的DLL装入内存。(3)便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数(输入和输出)不变，则修改函数及其DLL时，无需对可执行文件重新编译或链接。(4)便于适应运行环境：调用不同的DLL，就可以适应多种使用环境并提供不同的功能。,动态链接的缺点是：(1)增加了程序执行时的链接开销。(2)程序由多个文件组成，因此增加了管理复杂度。,4.1.5存储管理的任务在现代操作系统中，存储管理的主要任务有以下几个方面。(1)存储分配和回收：是存储管理的主要内容，用来确定其算法和相应的数据结构。(2)地址变换(地址再定位)：可执行文件生成中的链接技术、程序加载时的重定位技术及进程运行时硬件和软件的地址变换技术和机构。,(3)存储共享和保护：将代码和数据共享，设定对地址空间的访问权限(读、写、执行)。(4)存储器扩充：它涉及存储器的逻辑组织和物理组织，有两种控制方式：如果由应用程序控制，则采用覆盖技术。如果由操作系统控制，则采用交换技术(整个进程空间范围内)或请求调入和预调入(部分进程空间)。,4.1.6各种存储管理方案从操作系统的发展历史来看，存储管理主要有以下几个方案：(1)分区存储管理方案：是一种连续存储管理方案，但需要一次性全部装入内存。(2)段式存储管理方案：是一种不连续存储管理方案，段和段之间可以不连续，但需要一次性全部装入内存。(3)页式存储管理方案：是一种不连续存储管理方案，也需要一次性全部装入内存。,(4)段页式存储管理方案：是一种不连续存储方案，如果采用纯分页和分段思想，需要一次性全部装入内存；如果采用虚拟存储思想，则不需要一次性全部装入内存。(5)交换技术和覆盖技术：是存储扩充的两种技术，其中交换技术的优点是编写程序时不需要特殊的控制，也不会影响程序的结构。(6)虚拟存储管理方案：又分为两种，分别是虚拟页式(请求分页)存储管理和虚拟段式(请求分段)存储管理。,4.2分区存储管理方案,分区存储管理方案的数据结构是分区表或分区链表，主要功能是：(1)可以只记录空闲分区，也可以同时记录空闲和占用分区。(2)分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。(3)分区表可以划分为两个表格：空闲分区表和分配分区表，从而减小每个表格的长度。,4.2.1单一连续分区存储管理单一连续分区存储管理把整个内存空间的最低端和最高端作为操作系统区，中间作为用户程序区。在DOS操作系统中就采用了这种方法，如图4.7所示。,图4.7单一连续分区存储管理的分配方式,这种存储分配思想将内存分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。单一连续分区的优点是：简单，适用于单用户、单任务的操作系统(比如CP/M和DOS操作系统)，不需要复杂的硬件支持。单一连续分区的缺点是：一个作业运行时要占用整个内存的地址空间，即使很小的程序也是如此，对内存造成了很大的浪费，内存的利用率很低。,4.2.2固定分区分配为了便于管理整个内存，需建立一个表格来登记和管理整个内存。在这个表中登记了每一个分区的大小，起始地址和分配状态，如表4.1和图4.8所示。当有作业装入时，系统便可以搜索这个表，找出一个大小合适的分区分配给它。当程序运行结束时，可以把它所占用的空间再释放回去。地址重定位可以采用静态地址定位或是动态地址定位的方法。,表4.1分区状态表,图4.8固定分区的内存分配情况,为了实现多道程序设计，可以按等待作业的类型设置多个等待队列，也可以把所有的等待作业设置为一个等待队列。如图4.9所示为多道程序情况下固定分区的情况，左边为多个等待队列情况下的固定分区，右边为单个等待队列情况下的固定分区。,图4.9多道程序情况下的固定分区原理,固定分区的优点是：与单一连续分配方法相比，固定分区法的内存利用率提高了；可以支持多道程序；实现简单，开销小。固定分区的缺点：必须预先能够估计作业要占用多大的内存空间，有时候这是难以做到的；区内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。,4.2.3可变分区(动态分区分配)1空闲存储区表若采用固定分区法，则作业运行时所需内存一般不会刚好等于某一个分区的大小，因此分区内部的“内零头”被白白浪费了；另一方面，固定分区的分区数在系统启动以后不能任意改变，当系统中运行的作业数大于分区数时，就不可避免地会有一些作业分配不到分区，即使所有作业所需存储空间总和小于内存总和也不行。,可变分区存储管理法并不预先将内存划分成分区，而是等到作业运行需要内存时才向系统申请，从空闲的内存区中挖一块出来，其大小等于作业所需内存的大小，这样就不会产生“内零头”。管理空闲内存区的数据结构可采用链接法和连续线性表格法。每一个空闲分区用一个map结构管理：structmapunsignedm_size;/空闲分区的长度char*m_addr;/空闲分区的起始地址；structmapcoremapN;,图4.10所示为空闲分区表的初始状态，图4.11为某一时刻空闲分区表的状态。图中，m_size是空闲分区的长度，m_addr是空闲分区的起始地址。各个空闲分区按起始地址由低到高的顺序登记在空闲存储区表中，m_size为0的表项是空白表项，它们集中在表的后部。,图4.10空闲分区表的初始状态,图4.11某一时刻空闲分区表的状态,2分区分配算法寻找某个空闲分区，其大小必须大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。选择分区的算法有四种：最先适应算法、最佳适应算法、最差适应算法和循环最先适应算法。,1)最先适应算法(first-fit)最先适应算法是将所有的空闲分区按照地址递增的顺序排列，然后按照分区的先后次序从头开始查找，符合要求的第一个分区就是要找的分区。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。,(1)分配算法：当为作业分配大小为size的空间时，总是从表的低地址部分开始查找，当第一次找到大于等于申请大小的空间时，就按所需要的大小分配空间给作业，若分配后还有剩余空间，就修改原来的m_size和m_addr，以记录余下的零头；如果作业所需要的空间刚好等于该空间的大小，那么该空间的m_size就为0；然后要删除表中的这些空间，即将各个非零的表项上移。程序描述如下：,int*ffmalloc(mp,size)structmap*mp;unsignedintsize;registerintregint;registerstructmap*bp;/从mp开始，只要size不等于0，逐个地址检查for(bp=mp;bp-m_size;bp+)if(bp-m_size=size)/只要空间足够大,structmapunsignedm_size;char*m_addr;；,regint=bp-m_addr;/把老的起始地址保存到abp-m_addr+=size;/起始地址加size，把此块一分为二if(bp-m_size-=size)=0)/如果块大小相同为0dobp+;(bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);,return(regint);return(0);,(2)释放算法：某一个作业释放以前所分配到的内存就是将该内存区归还给操作系统，使其成为空闲区而可以被其他作业使用。回收时如果释放区与临近的空闲区相连接，要将它们合并成较大的空闲区，否则空闲区将被分割得越来越小，最终导致不能利用。另外，空闲区个数越来越多，也会使得空闲区登记表溢出。,释放算法分四种情况：仅与前面一个空闲区相连，如图4.12(a)所示。合并前空闲区和释放区以构成一块大的新空闲区，并修改空闲区表项。与前面空闲区和后面空闲区都相连，如图4.12(b)所示。将三块空闲区合并成一块空闲区。,仅仅与后空闲区相连，如图4.12(c)所示。与后空闲区合并，使后空闲区表项的m_addr为释放区的起始地址，m_size为释放区与后空闲区的长度之和。与前后空闲区都不相连，如图4.12(d)所示。在前、后空闲区表项中间插入一个新的表项，其m_addr为释放区的起始地址，m_size为释放区的长度。,图4.12释放区与前后空闲区相邻的情况,程序描述如下：mfree(unsignedsize,char*StartAddr)structmap*bp;char*addr,*taddr;unsignedTmpSize;addr=StartAddr;,structmapunsignedm_size;char*m_addr;；,for(bp=coremap;bp-m_addrm_size!=0;bp+)if(bpcoremapwhile(bp-m_size),bp+;(bp-1)-m_addr=bp-m_addr;(bp-1)-m_size=bp-m_size;elseif(addr+size=bp-m_addrbp-m_size+=size;elseif(size)do/单独插入空闲分区表,而不与前后相连taddr=bp-m_addr;bp-m_addr=addr;addr=taddr;TmpSize=bp-m_size;,bp-m_size=size;bp+;while(size=TmpSize);,最先适应算法的优点：分配简单而且合并相邻的空闲区也比较容易，该算法的实质是尽可能利用存储区低地址的空闲区，而尽量在高地址部分保存较大的空闲区，以便一旦有分配大的空闲区的要求时，容易得到满足。在释放内存分区时，如果有相邻的空闲区就进行合并，使其成为一个较大的空闲区。,最先适应算法的缺点：由于查找总是从表首开始，前面的空闲区被分割得很小时，能满足分配要求的可能性就较小，查找次数就较多。系统中作业越多，这个问题就越来越严重。针对这个问题，对最先适应法稍加改进，就有了循环最先适应法。会产生碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的利用率。,如图4.13所示是某一个时刻J1、J2、J3、J4四个作业在内存中的分配情况、空闲区表和已分配区表，它们的长度分别是15KB、10KB、12KB、10KB。J5和J6两个新作业的长度分别为5KB和13KB，分配内存后的内存分配情况、空闲区表和已分配区表如图4.14所示。,图4.13最先适应算法分配前的状态,图4.14最先适应算法分配后的状态,2)循环最先适应算法(next-fit，下次适应算法)相对于最先适应算法，下次适应算法按分区的先后次序，从上次分配的分区开始查找，到最后分区时再回到开头，符合要求的第一个分区就是找到的分区。,循环最先适应算法分配时总是从起始查找指针所指向的表项开始，第一次找到满足要求的空闲区时，就分配所需要的空闲区，然后修改表项，并调整起始查找指针，使其指向队列中被分配的后面的那块空闲区。循环最先适应法的实质是起始查找指针所指的空闲区和其后的空闲区群常为较长时间未被分割过的空闲区，它们已经合并成为大的空闲区的可能性较大，与最先适应算法相比，它在没有增加多少代价的情况下却明显地提高了分配查找的速度。循环最先适应算法的释放算法与最先适应算法的基本相同。,3)最佳适应算法(best-fit)最佳适应算法的思想是将所有的空闲分区按照其容量递增的顺序排列，当要求分配一个空白分区时，由小到大进行查找。,最佳适应算法的空闲存储区管理表的组织方法可以采用顺序结构，也可以采用链接结构。最佳适应算法的优点：由于算法是在所有大于或者等于要求分配长度的空闲区中挑选一个最小的分区，所以分配后所剩余的空白块会最小。平均而言，只要查找一半的表格便能找到最佳适应的空白区。如果有一个空白区的容量正好满足要求，则它必被选中。,最佳适应算法的缺点：由于空闲区是按大小而不是按地址的顺序排列的，因此释放时，要在整个链表上搜索地址相邻的空闲区，合并后又要插入到合适的位置。空白区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用。其内存分配前的状态如图4.13所示，J5和J6是两个新作业，对它们分配内存后的内存分配情况、空闲区表和已分配区表如图4.15所示。,4)最坏适应算法(worst-fit)最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲分区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。算法基本不留下小空闲分区，但较大的空闲分区不会被保留。,最坏适应算法的实现与前面的最佳适应算法类似。最坏适应算法的优点：分配的时候只需查找一次就可以成功，分配的算法很快。最坏适应算法的缺点：最后剩余的分区会越来越小，无法运行大程序。其内存分配前的状态如图4.13所示，J5和J6是两个新作业，对它们分配内存后的内存分配情况、空闲区表和已分配区表如图4.16所示。,图4.15最佳适应算法分配后的状态,图4.16最差适应算法分配后的状态,4.2.4可再定位式分区(可重定位分区分配)可再定位分区分配即浮动分区分配，是解决碎片问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续区域，而留下一个较大的空白区。这好像在一个队列中有些人出列以后，指挥员命令队列向前(或向右)靠拢一样。这种过程我们称之为“靠拢”或“紧凑”，如图4.17所示。,图4.17可再定位分区分配的靠拢过程,为解决程序浮动问题，可使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始启动执行。但是这种办法有两个缺点：一是要花费较多的处理机时间；二是如果该程序已经执行了一段时间，则不能再从头开始，否则将引起混乱。较好的办法是采用动态再定位技术。,4.2.5伙伴系统（BuddySystem）伙伴系统提供了一个在固定大小和可变大小之间折衷的方案。内存被划分成大小为2的整次幂的单元，初始只有一个包含所有内存的单元。当要将内存分配给进程时，分配大于该进程大小的最小2的整次幂单元。例如，一个需50K内存进程要放入大小为64K的内存单元。如果没有这样的内存单元，大于该进程需求的最小可利用空间被分成原来一半大小的“伙伴”单元，继续分割其中一个伙伴单元，直到创建一个大小合适的分配单元位置。当进程释放内存时，如果互成“伙伴”关系的两个单元均被释放，这两个单元就结合成一个两倍大小的单元。图4.18说明了分配和释放内存时，是如何分割和连接分配单元的。给定大小为2n，伙伴系统维持了一个最大长度为2n的空闲数据块，每种大小的单元各有一个（假定内存大小为28，则大小为28到21的分配单元都有可能得到）。由于有一个单独的各种大小空闲块，伙伴系统分配或释放内存效率较高。然而，由于存在内部碎片和外部碎片，所以伙伴系统内存利用率不高。,图4.18伙伴系统,4.2.6多重分区可变分区虽然解决了多道程序运行的情况，但是总是有碎片的问题，而且一个程序总是一定要放在一个分区中。为了解决这个问题，就引入了多重分区的分配方案。所谓多重分区，就是把一个程序放在多个分区中，这样当一个作业在一个分区中装不下时，可以把它装入到另外一个分区，依此类推。采用多重分区分配方案，可以使存储空间的利用率得到提高，但是实现起来比较困难，所以这里不再赘述。,4.3页式存储管理,4.3.1基本原理把作业的虚拟地址空间划分成若干个长度相等的页(pages)，也可以称为“虚页”，每一个程序的虚页都从0开始编号。主存也划分成若干个与虚页长度相等的页框(pageframe)，也称为页面或实页。在静态页式存储管理系统中，作业加载时可以将任意一页放入内存中的任意一个页框，而且这些页框不必连续，从而实现了不连续分配。,但是要求一个作业在运行前将其所有的虚页全部都装入主存的块中，当然这就要求主存中有足够多的空闲块，否则程序便不能运行。如图4.18所示是分页存储管理的基本原理。,图4.19分页存储管理的基本原理,在分页系统中，页的大小往往都是2的整数次幂，因此在分页系统中，地址的结构由两部分构成：P(页号)和D(页内偏移量)，如图4.19所示。页内偏移量的值为02n-1。P=INTA/LD=AmodL注:A为逻辑地址,页面大小为L,图4.20页的划分,对于分页系统来说，程序在虚拟地址空间是连续的，但却要映射到物理内存中不连续的空闲frame中，所以需要系统在内存中开辟一个页表区来建立每一个作业的虚页号到物理内存的frame号之间的映射关系，这个表格就叫做页变换表(pagemanagementtable)，也叫页表。页表中的内容分为三部分：页号、块号和页内偏移量。程序执行的时候，对于每一条访问内存的指令，分页系统的地址变化过程如图4.20所示。,图4.21分页式存储管理的地址变换过程,过程说明：(1)由硬件机构自动将虚拟地址字分成虚页号和页内偏移量两个部分，虚页号送给累加器，它和页表起始地址之和就是所要查找的表项。(2)由页表控制寄存器中的页表起始地址和虚拟地址字中的虚页号查找页表，对应的虚页号的页表地址为：页表起始地址虚页号页表表项长度。(3)将页表中取出的frame号和虚拟地址字中的页内偏移量一起装入到地址寄存器，根据地址寄存器中的地址值来访问内存。,4.3.2页式存储管理的地址变换1页式管理的数据结构页式存储管理系统中，当进程建立时，操作系统为进程中所有的页分配页块。当进程撤消时需收回所有分配给它的物理页块。,为了完成上述功能，在一个页式存储管理系统中，一般要采用如下的数据结构：(1)进程页表：是逻辑页号(本进程的地址空间)到物理页面号(实际内存空间)的映射。(2)物理页面表(空闲内存页表)：描述物理内存空间的分配使用状况。整个系统有一个物理页面表。其数据结构是位示图(如图4.22所示)和空闲页面链表，用来记录内存中每个页的使用情况和当前空闲页的总数。,图4.23位示图,(3)请求表：描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里。整个系统有一个请求表。,2.地址变换机构前面已经指出，在页式存储系统中，指令所给出的地址分为两部分：逻辑页号和页内偏移量。CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内偏移量相加即可形成物理地址，如图4.23所示。,程序装入后执行时，应该需要内存管理单元(MemoryManagementUnit，MMU)的支持，根据进程页表进行执行时的动态地址映射和保护。映射的过程如上所述。MMU的位置和功能如图4.24所示。,图4.24MMU的位置和功能,MMU是MemoryManagementUnit的缩写，中文名是存储器管理单元，它是中央处理器（CPU）中用来管理虚拟存储器、物理存储器的控制线路，同时也负责虚拟地址映射为物理地址，以及提供硬件机制的内存访问授权。,图4.25页式地址变换,页面变换（页表建立）的过程是：先要得到进程所需要的页数，参照空闲内存页表，看是否有这么多的空闲页，如果有，则将N个页面分配给这个进程，并修改空闲内存页表，将程序一次性全部装入用户区内存，同时建立起这个进程的进程页表，也就是页面变换表。如果没有N个空闲页面，则被拒绝或者排队等待。,4.3.3硬件支持从上面的介绍可以看出，每访问一次指令或者数据，至少需要访问两次内存，第一次是查找页表，第二次才是真正访问指令或者数据。为了加快页式存储管理的速度，往往也需要硬件支持，主要是页表基址寄存器、页表长度寄存器和关联存储器等一些寄存器。,1系统设置一对寄存器(1)页表基址寄存器(PageTableBaseRegister，PTBR)用户程序在执行过程中每次访问内存时(即每次地址映射时)，MMU需要根据当前进程的进程页表基址寄存器值和此次地址映射的逻辑页号，访问当前进程的进程页表(在内存)，得到此次地址映射的物理页号，再根据逻辑地址中页内偏移量得到真正的物理地址。在进程切换时页表基址寄存器的内容才被保存和恢复，其内容是当前进程的进程页表的内存起始地址。页表基址寄存器的工作原理如图4.26所示。,图4.26进程页表基址寄存器的工作原理,由图4.24可以看出以下4点：每次进程切换时不用保存和恢复当前新老进程的整个进程页表，只需保存和恢复PTBR。进程页表是由硬件访问的，这意味着进程页表的格式是由硬件规定的。对进程页表的访问是直接存取。用户程序执行时的每次内存访问，都至少访问内存两次，第一次访问进程页表，第二次才是访问此次要访问的页本身，这意味着用户程序的执行时间将增加一倍。,(2)页表长度寄存器为了实现存储保护，在页表基址寄存器的基础上，还需要一个页表长度寄存器，它用来存放当前进程页表的长度。在每次访问内存之前，先检查所取得指令的地址是否超过了进程页表的长度。如果在范围之内，则正常访问内存；如果在长度范围之外，则拒绝此次访问。,直接采用上述机构进行地址变换实际上是不可取的。由于页表是驻留在内存中的，为了进行地址变换，对于每一条访问内存的指令，系统至少要访问内存两次，这样程序执行的速度只能是原来的1/2。,2关联存储器快表为缩短查找时间，可以将页表装入到关联存储器，按内容查找逻辑页号到物理页号的映射。很多页式系统都有一组关联存储器(TranslationLookasideBuffer，TLB)，用来存放当前运行作业的页表表项，以加速地址变换过程，这种页表称为快表，它是介于内存与寄存器之间的存储机制。内存中的页表有时也称为慢表。利用快表进行地址变换的过程如图4.25所示。,图4.27利用快表进行地址变换的过程,页表,两级和多级页表,两级页表解决大页表占用大的连续存储空间的问题；关于“页表”的分页存放“页表”外层页表(页目录)；逻辑地址：外层页号+外层页内地址+页内地址多级页表,页框为4K;页目录项(4Byte)用来寻址一个页表；页表项(4Byte)用来指定一个物理内存页面。图中二级目录的寻址空间范围是?,该页目录表寻址的所有页表共可以寻址1024*1024*4096=4G内存空间。,4.28地址变换示意图(CPU的寄存器CR3用来确定当前页目录的物理地址),4.29页目录和页表表项结构,每个表项由页框地址、访问标志位、脏（已改写）标志位和存在标志位等构成。,4.3.5优缺点分页式存储管理的优点：(1)没有外碎片，每个内碎片不超过页的大小。(2)一个程序不必连续存放。(3)便于改变程序占用空间的大小(主要指随着程序运行而动态生成的数据增多，要求地址空间相应增长，通常由系统调用完成而不是操作系统自动完成)。,分页式存储管理的缺点：(1)程序要全部装入内存。(2)采用动态地址变换机构会增加计算机的成本和降低处理机的速度。(3)各种表格要占用一定的内存空间，而且要花费一定的时间来建立和管理这些表格。(4)存储扩充问题没有得到解决。(5)不易实现共享。(6)不便于动态连接。,4.4段式存储管理,通常，一个作业是由若干个自然段组成的。因而，用户希望能把自己的作业按照逻辑关系划分为若干个段，每个段都有自己的名字和长度。要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，每个段都从0开始编址。这样，用户程序在执行中可用段名和段内地址进行访问。例如，下述的两条指令便是使用的段名和段内地址。,LOADL，A|(D)STOREI，B|(C)其中，前一条指令的含义是将分段A中D单元内的值读入寄存器L；后一条指令的含义是将寄存器I的内容存入分段B中的C单元内。,段式存储管理(simplesegmentation)可以实现共享。通常，在实现程序和数据的共享时，都是以信息的逻辑单位为基础的，比如共享某个例程和函数。段式存储管理可以实现分段保护。在多道程序环境下，为了防止其他程序对某程序在内存中的数据有意无意的破坏，必须采取保护措施。段式存储管理可以实现动态链接。段式存储管理使得段可以动态增长。,4.4.1基本思想在页式存储管理思想中，作业的地址空间是连续的一维地址空间，程序的各个目标模块都由链接程序装配成一个可执行的程序后装入内存执行。,我们根据程序的模块结构，把作业地址空间划分为大小不同的一些块，我们把这些大小不同的块叫做段。每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的，通常分为主程序段、子程序段、库函数段和数据段等等。同时在物理内存中，也分成一些和这些块一样大的块。分段的基本原理如图4.26所示。,图4.26分段的基本原理,作业在装入的时候是一次性全部装入的，如果不是一次性装入，就叫做请求分段式的管理。将程序的地址空间划分为若干个段(segment)，程序加载时，为每个段分配其所需的一个连续内存分区，而进程中的各个段可以不连续地存放在内存的不同分区中。物理内存的管理采用动态分区的思想，即在为某个段分配物理内存时，可以采用最先适应法、下次适应法和最佳适应等方法。,在收回某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。分段式存储管理也需要硬件支持，以实现逻辑地址到物理地址的映射。分段式存储管理的基本原理如图4.27所示。,图4.27分段式存储管理的基本原理,在分段式存储管理的思想中，程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段，其优点是可以分别进行编写和编译；可以针对不同类型的段采取不同的保护；可以以段为单位来进行共享，包括通过动态链接进行代码共享。在分段存储管理系统中，作业地址空间的每一个单元均采用二维地址(S，W)，其中，S为段号，W为段内地址或者偏移量，如图4.28所示。,图4.28进程段地址,4.4.2分段式管理的数据结构(1)进程段表：也叫段变换表(SMT)，如图4.29所示。它描述组成进程地址空间的各段。它可以是指向系统段表中表项的索引，每段都有段基址(baseaddress)。(2)系统段表：描述系统所有占用的段。(3)空闲段表：描述了内存中所有空闲段，可以结合到系统段表中。内存的分配算法可以采用最先适应法、最佳适应法和最坏适应法。,图4.29段式地址变换,4.4.3分段式管理的地址变换为了实现从逻辑地址到物理地址的变换功能，在系统中设置了段表基址寄存器和段表长度寄存器。在进行地址变换时，系统将逻辑地址中的段号S与段表长度STL进行比较。若SSTL，表示段号太大，则越界访问，产生越界中断；若未越界，则根据段表的起始地址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后再检查段内地址D是否超过该段的段长SL。若DSL，同样发出越界中断；若未越界，则将该段的基址D与段内地址相加，即得到要访问的内存物理地址。,和分页式存储管理系统一样，当段表放在内存中时，分段式每访问一个数据或者指令，都需至少访问内存两次，从而成倍地降低了计算机的速率。解决的办法和分页存储管理的思想类似，即再增设一个关联寄存器，用于保存最近常用的段表项。由于一般情况下段比页大，因而段表项的数目比页表数目少，其所需的关联寄存器也相对较小，可以显著地减少存取数据的时间。,4.4.4分段式管理的硬件支持如上面所述，和分页式存储管理的思想类似，也可以设置一对寄存器：段表基址寄存器和段表长度寄存器。段表基址寄存器用于保存正在运行进程的段表的基址，而段表长度寄存器用于保存正在运行进程的段表的长度。,同样，和分页式存储管理的思想类似，也可以设置联想存储器，它是介于内存与寄存器之间的存储机制，和分页式存储管理系统一样也叫快表。它的用途是保存正在运行进程的段表的子集(部分表项)，其特点是可按内容并行查找。引入快表的作用是为了提高地址映射速度，实现段的共享和段的保护。快表中的项目包括：段号、段基址、段长度、标识(状态)位、访问位和淘汰位。,4.4.5分段式管理的优缺点分段式存储管理的优点：没有内碎片，外碎片可以通过内存紧凑来消除；便于改变进程占用空间的大小；便于实现共享和保护，即允许若干个进程共享一个或者多个段，对段进行保护。如图4.30所示是分段系统中共享一个compiler编译器程序的例子。分段式存储管理的缺点：作业需要全部装入内存，不能实现存储扩充。,图4.30分段系统中共享compilor的示意图,4.4.6分页式管理和分段式管理的比较(1)分页是出于系统管理的需要，分段是出于用户应用的需要。(2)页的大小是系统固定的，而段的大小则通常不固定。(3)逻辑地址表示：分页是一维的，各个模块在链接时必须组织在同一个地址空间；而分段是二维的，各个模块在链接时可以把每个段组织成一个地址空间。(4)通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。(5)分段式存储管理可以实现内存共享，而分页式存储管理则不能实现内存共享。但是两者都不能实现存储扩充。分页式管理和分段式管理的比较如图4.31所示。,图4.31页式管理与段式管理的比较,4.5段页式存储管理,4.4.1基本思想段页式存储管理是对虚拟页式和虚拟段式存储管理的结合，这种思想结合了二者的优点，克服了二者的缺点。这种思想将用户程序分为若干个段，再把每个段划分成若干个页，并为每一个段赋予一个段名。,也就是说将用户程序按段式划分，而将物理内存按页式划分，即以页为单位进行分配。换句话来说，段页式管理对用户来讲是按段的逻辑关系进行划分的，而对系统来讲是按页划分每一段的。在段页式存储管理中，其地址结构由段号、段内页号和页内地址三部分组成，如图4.32所示。,图4.32段页式存储管理的地址结构,在段页式存储管理中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。由于允许将一个段中的页进行不连续分配，因而使段表的内容有所变化：它不再是段内起始地址和段长，而是页表起始地址和页表长度。如图4.33所示是段页式存储管理中利用段表和页表进行逻辑地址到物理地址的映射过程。,图4.33段页式存储管理的地址映射,4.4.2段页式存储管理的地址变换如图4.33所示，为了实现段页式存储管理的机制，需要在系统中设置以下几个数据结构：(1)段表：记录每一段的页表起始地址和页表长度。(2)页表：记录每一个段所对应的逻辑页号与内存块号的对应关系，每一段有一个页表，而一个程序可能有多个页表。(3)空闲内存页表：其结构同分页式存储管理，因为空闲内存采用分页式的存储管理。(4)物理内存分配：同分页式存储管理。,4.4.3硬件支持在段页式系统中，为了便于实现地址变换，必须配置一个段表基址寄存器(在其中存放段表起始地址)和一个段表长度寄存器(在其中存放段长SL)。进行地址变换时，首先利用段号S，将它与段长SL进行比较。若S0。工作集大小范围：1|W(t,)|min(,n)，其中n是进程的总页面数。,(3)工作集大小的变化：进程开始执行后，随着访问新页面而逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；当局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。工作集大小的变化如图4.39所示。,图4.39工作集大小的变化,(4)利用工作集进行常驻集调整的策略：记录一个进程的工作集变化。定期从常驻集中删除不在工作集中的页面。总是让常驻集包含工作集。,(5)工作集的困难：工作集的过去变化未必能够预示工作集的将来大小或组成页面的变化。记录工作集变化要求开销太大。对工作集窗口大小的取值难以优化，而且通常该值是不断变化的。,4缺页率算法(PageFaultFrequency，PFF)(1)PFF算法：页面被访问时的处理：每个页面设立使用位(usebit)，在该页被访问时设置usebit=1。缺页时的处理：每次缺页时，由操作系统计算与上次缺页的“虚拟时间”间隔t。缺页时对常驻集的调整：定义一个“虚拟时间”间隔的阈值(threshold)F，依据t和F来修改常驻集。,(2)和页面缓冲算法(pagebuffering)配合使用，可以获得良好的性能。(3)缺页率算法的主要缺点：当局部性区域的位置改变时，工作集的变化处于过渡阶段，其快速扩张使较多新页面添加到进程的常驻集中。其中较少使用的页面至少还要经过一段F虚拟时间才会被淘汰，因而带来较多不必要的调页开销。,4.可变采样间隔算法(Variable-intervalSampledWorkingSet，VSWS)(1)VSWS算法：使用3个参数：采样间隔时间的下限M，采样间隔时间的上限L，一个采样间隔内允许发生的缺页次数的上限Q。,常驻集的调整：每个页面设立使用位(userbit)，在每个采样间隔的开始设置各页的userbit=0，而在每个采样间隔的结束只保留userbit=1的页面在常驻集中，其余页面从常驻集中删除。采样间隔划分：每次缺页时，对缺页次数加1。(2)VSWS算法的优点：在局部性区域位置改变时，缺页率上升，通过缩短采样间隔，删除无用页面，可降低常驻集扩张的峰值。,6虚拟存储中的负载控制负载控制讨论的是操作系统要在内存中驻留多少个并发进程才是较好的。1)改善时间性能的途径降低缺页率：缺页率越低，虚拟存储器的平均访问时间延长得越小。提高外存的访问速度：外存和内存的访问时间比值越大，则达到同样的时间延长比例所要求的缺页率就越低。,2)负载控制(loadcontrol)策略负载控制策略是：在避免出现抖动的前提下，尽可能提高进程并发水平。(1)基于工作集策略的算法(如PFF,VSWS)：它们隐含负载控制策略，只有那些常驻集足够大的进程才能运行，从而实现对负载的自动和动态控制。,(2)“L=S判据”策略(Denning,1980)：让缺页的平均间隔时间(是指真实时间而不是虚拟时间)等于对每次缺页的处理时间(即缺页率保持在最佳水平)，这时CPU的利用率达到最大。一种类似的策略称为“50%判据”策略，即让外存交换设备保持50%的利用率，这时CPU也达到最高的利用率。,(3)基于轮转置换算法的负载控制策略：定义一个轮转计数，描述轮转的速率(即扫描环形页面链的速率)。当轮转计数少于一定的阈值时，表明缺页较少或存在足够的空闲页面。当轮转计数大于阈值时，表明系统的进程并发水平过高，需降低系统负载。,4.7.4虚拟段式存储管理1段表内容为实现虚拟段式存储管理的各项功能和管理需要，在进程段表中添加了如下各项：(1)标志位：如存在位(presentbit)，修改位(modifiedbit/dirtybit)，扩充位(该段是否增加过长度)。(2)访问统计位：如使用位(usebit)。(3)存取权限位：如读R，写W，执行X。(4)外存地址：本段在外存的起始地址。,2越界中断处理进程在执行过程中，有时需要扩大分段，如数据段的扩充。由于要访问的地址超出原有的段长，所以引发越界中断。操作系统处理中断时，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理。,3缺段中断处理在请求分段系统中，采用的是请求调段策略。CPU的硬件逻辑要根据段表表项进行地址变换或者产生缺段中断。请求分段存储管理与请求分页存储管理不同之处在于，指令和操作系统一定不会跨越在段边界上。但是，在请求分段系统中，一般会增加存取权限的违法中断和段的越界中断。,在请求调段时：先检查内存中是否有足够的空闲空间，若有，则装入该段，修改有关数据结构，中断返回；若没有，则检查内存中空闲区的总和是否满足要求，如是，则应采用紧缩技术，再转；否则，淘汰一些段，再转。,4请求分段系统的内存分配策略1)段的动态链接在程序开始运行时，只将主程序段装配好并调入内存，其他各段的装配是在主程序段的运行过程中逐步完成的。,2)链接间接字机器指令可采用直接寻址或间接寻址方式。采用间接寻址时，间接地址指示的单元的内容称为间接字，在间接字中，包含了直接地址及附加的状态位。其格式如图4.40所示。,图4.40链接间接字格式,3)链接中断处理链接中断处理的步骤是：(1)根据链接间接字找出要访问段的符号名和段内地址。(2)分配段号，检查该段是否在内存。若不在内存，则从外存调入，并登记段表，修改内存分配表。(3)修改间接字：修改链接标志位为0，并修改直接地址。(4)重新启动被中断的指令执行。,4.8高速缓冲存储器,4.8.1高速缓存的组织由于CPU的指令处理速度与内存中指令的访问速度存在差异(可达到一个数量级的差异，如IntelPentiumPro平均一个时钟周期可执行3条指令，)，因此为提高CPU的利用率，在CPU与内存之间组织了一个高速缓存结构，如图4.41所示。,图4.41高速缓存的组织结构,高速缓存由三部分组成：高速缓冲存储器、缓存目录和缓冲控制器。(1)高速缓冲存储器：主要作用是缓存内