第4章--存储管理计算机操作系统第三版.ppt

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