第4章--存储管理ppt课件计算机操作系统汤小丹梁红兵版.ppt

《第4章--存储管理ppt课件计算机操作系统汤小丹梁红兵版.ppt》由会员分享，可在线阅读，更多相关《第4章--存储管理ppt课件计算机操作系统汤小丹梁红兵版.ppt（292页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第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章章 存储管理

2、存储管理 4.1.1 存储体系 存储器的功能是保存指令和数据，它的发展方向是高速、大容量和小体积，诸如内存在访问速度方面的发展有DRAM、SDRAM、SRAM等技术；而磁盘技术的发展方向主要在大容量方面，比如接口标准、存储密度等。第第4 4章章 存储管理存储管理 存储组织的功能是在存储技术和CPU寻址技术许可的范围内组织合理的存储结构，其依据是访问速度的匹配关系、容量要求和价格。常见的存储结构有两种：“寄存器内存外存”结构和“寄存器快速缓存内存外存”结构。 图4.1所示的是“寄存器快速缓存内存外存”结构。外存(secondary storage)快速缓存(cache)寄存器(register)

3、内存(primary storage)图4.1 存储层次结构第第4 4章章 存储管理存储管理 从源程序到程序执行从源程序到程序执行编译：编译程序 由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序 由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序 由装入程序（Loader）将装入模块复制到内存中。库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子2第第4 4章章 存储管理存储管理 地址空间的概念地址空间的概念物理（绝对）地址程序执行 每个内存单元的固定顺序地址（编号）。逻

4、辑（相对）地址装入（汇编编译） 被链接装配（或汇编、编译）后的目标模块所限定的地址的集合； 相对于某个基准量（通常为：0）的编址。物理地址 内存000000000100002.0100001FFF主子1子2主子1子2逻辑地址 装入模块000.FFF主子1子2相对地址源程序/单个目标模块0005FF0005FF0003FF第第4 4章章 存储管理存储管理 4.1.2 地址重定位 可执行文件的建立过程是：源程序编译目标模块(多个目标模块或程序库) 链接可执行文件。当程序执行时由操作系统装入内存而成为进程。 对程序员来说，数据的存放地址是由符号决定的，故称为符号名地址，或者称为名地址。 第第4 4章

5、章 存储管理存储管理 当程序被装入内存时，程序的逻辑地址被转换成内存的物理地址，称为地址重定位地址重定位。 在可执行文件装入时需要解决可执行文件中地址(指令和数据)和内存地址的对应问题。这是由操作系统中的装入程序Loader来完成的，如图4.2所示。图4.2 地址重定位Load A datal源程序编译链接0100BA1000datal 34562003456Load A datal逻辑地址空间地址映射Load A datal3456物理地址空间12001000第第4 4章章 存储管理存储管理 1绝对装入(absolute loading) 在可执行文件中记录内存地址，装入时直接定位于上述内存

6、地址的方式称为绝对装入(或者称为固定地址再定位)。 在这种方式下，程序的地址再定位是在执行之前被确定的，也就是在编译、链接时直接制定程序在执行时访问的实际存储器地址。这样，程序的地址空间和内存地址空间是一一对应的。单片机或者单用户系统常采用这种方式。 固定地址再定位的优点是装入过程简单；缺点是过于依赖于硬件结构，不适合多道程序系统。第第4 4章章 存储管理存储管理 2可重定位装入(relocatable loading) 可重定位装入方式是指在可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应的偏移量。 一个有相对地址空间的程序

7、装入到物理地址空间时，由于两个空间不一致，就需要进行地址变换，或称地址映地址映射，即地址的再定位。射，即地址的再定位。 地址再定位有两种方式：静态再定位和动态再定位。 第第4 4章章 存储管理存储管理 1) 静态再定位 静态再定位是指当程序执行时，由装入程序运行重定位程由装入程序运行重定位程序序，根据作业在内存重分配的起始地址，将可执行的目标代码装入到指定内存中。所谓静态，是指地址定位完成后，在程序的执行期间将不会再发生变化。静态再定位是在程序执行之前进行地址再定位的，这一工作通常是由装配程序完成的。 LOAD 1,50012 3450100500700LOAD 1,5 50012 34505

8、 700程序A的地址空间程序A的存储空间5 5005 1005 000静态重定位示意图 第第4 4章章 存储管理存储管理 静态地址再定位的优点是优点是：无需硬件地址变化机构支持，容易实现；无需硬件支持，它只要求程序本身是可再定位的；它只对那些要修改的地址部分做出某种标识，再由专门设计的程序来完成。在早期的操作系统中大多数都采用这种方法。 静态地址再定位的缺点是缺点是：必须给作业分配一个连续的存储区域，该存储区不能分布在内存的不同区域；在作业的执行期间不能扩充存储空间，也不能在内存中移动，因而不能重新分配内存，不利于内存的有效利用；多个用户很难共享内存中的同一程序，如若共享同一程序，则各用户必须

9、使用自己的副本。 第第4 4章章 存储管理存储管理 2) 动态再定位 动态地址再定位是在程序执行期间，在每次存储在每次存储访问之前进行的访问之前进行的。程序在装入内存时，并不修改程序的逻辑地址值，而是在访问物理内存之前，再实时地将逻辑地址转换成物理地址。在这种情况下，其实现机制要依赖硬件地址变换机构，即通过基地址寄存器BR、变址寄存器VR计算出指令的有效地址，再利用硬件机构实现地址变换，如图4.3所示。第第4 4章章 存储管理存储管理 LOAD-A 200200VRBR1000逻辑地址空间34563002001000物理地址空间LOAD-A 20034561300120011000图4.3 动

10、态地址再定位的原理第第4 4章章 存储管理存储管理 从图4.3中可以看出：当程序开始执行时，系统将程序在内存的起始地址送入BR中。执行指令时，系统将逻辑地址与BR中的起始地址相加，从而得到物理地址。 动态地址再定位的优点是：优点是：程序在执行期间可以换入和换出内存，这样可以缓解内存紧张的矛盾；可以把内存中的碎片集中起来，以充分利用空间；不必给程序分配连续的内存空间，可以较好地利用较小的内存块；若干用户可以共享同一程序。 动态地址再定位的缺点：缺点：需要附加的硬件支持，而且实现存储管理的软件算法比较复杂。第第4 4章章 存储管理存储管理 3动态运行期装入 动态运行期装入(dynamic run-

11、time loading)是指在可执行文件中记录虚拟内存地址，在装入和执行时通过硬件地址变换机构完成虚拟地址到实际内存地址的变换。 动态运行期装入的优点是：操作系统可以将一个程序分散存放于不连续的内存空间，可以通过移动程序来实现共享；能够支持程序执行中产生的地址引用，如指针变量(而不仅是生成可执行文件时的地址引用)。 动态运行期装入的缺点是：需要硬件支持(通常是CPU)，操作系统的实现比较复杂。第第4 4章章 存储管理存储管理 4.1.3 链接 1链接方法 常见的链接方法有静态链接和动态链接两种。 1) 静态链接 静态链接(static linking)是在生成可执行文件时进行的，即在目标模块

12、中记录被调用模块的名字符号地址(symbolic address)，在可执行文件中将该名字改写为指令直接使用的数字地址，如图4.4所示。第第4 4章章 存储管理存储管理 0L1callfunction1Module AModule B function10 function1( ) call LFModule AModule B0L1L function1 function1( ) LFLM1M1F图4.4 静态链接 第第4 4章章 存储管理存储管理 2) 动态链接 动态链接(dynamic-linking)是在运行可执行文件时进行的,亦即，执行过程中，当发现一个被调用模块未装入内存时，立即取

13、找到该模块，并链接到调用者模块上。 通常被链接的共享代码称为动态链接库(Dynamic Link Library，DLL)或共享库(shared library)。第第4 4章章 存储管理存储管理 动态链接的优点是： (1) 共享：多个进程可以共用一个DLL，比较节省内存，从而可以减少文件的交换。 (2) 部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作的DLL装入内存。 (3) 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数(输入和输出)不变，则修改函数及其DLL时，无需对可执行文件重新编译或链接。 (4) 便于适应运行环境：调用不同的DLL，就可以适

14、应多种使用环境并提供不同的功能。 第第4 4章章 存储管理存储管理 动态链接的缺点是：(1) 增加了程序执行时的链接开销。(2) 程序由多个文件组成，因此增加了管理复杂度。第第4 4章章 存储管理存储管理 4.1.5 存储管理的任务 在现代操作系统中，存储管理的主要任务有以下几个方面。 (1) 存储分配和回收：是存储管理的主要内容，用来确定其算法和相应的数据结构。 (2) 地址变换(地址再定位)：可执行文件生成中的链接技术、程序加载时的重定位技术及进程运行时硬件和软件的地址变换技术和机构。第第4 4章章 存储管理存储管理 (3) 存储共享和保护：将代码和数据共享，设定对地址空间的访问权限(读、

15、写、执行)。 (4) 存储器扩充：它涉及存储器的逻辑组织和物理组织，有两种控制方式： 如果由应用程序控制，则采用覆盖技术。 如果由操作系统控制，则采用交换技术(整个进程空间范围内)或请求调入和预调入(部分进程空间)。第第4 4章章 存储管理存储管理 4.1.6 各种存储管理方案 从操作系统的发展历史来看，存储管理主要有以下几个方案： (1) 分区存储管理方案：是一种连续存储管理方案，但需要一次性全部装入内存。 (2) 段式存储管理方案：是一种不连续存储管理方案，段和段之间可以不连续，但需要一次性全部装入内存。 (3) 页式存储管理方案：是一种不连续存储管理方案，也需要一次性全部装入内存。 第第

16、4 4章章 存储管理存储管理 (4) 段页式存储管理方案：是一种不连续存储方案，如果采用纯分页和分段思想，需要一次性全部装入内存；如果采用虚拟存储思想，则不需要一次性全部装入内存。 (5) 交换技术和覆盖技术：是存储扩充的两种技术，其中交换技术的优点是编写程序时不需要特殊的控制，也不会影响程序的结构。 (6) 虚拟存储管理方案：又分为两种，分别是虚拟页式(请求分页)存储管理和虚拟段式(请求分段)存储管理。第第4 4章章 存储管理存储管理 4.2 分区存储管理方案分区存储管理方案 分区存储管理方案的数据结构是分区表或分区链表，主要功能是： (1) 可以只记录空闲分区，也可以同时记录空闲和占用分区

17、。 (2) 分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。 (3) 分区表可以划分为两个表格：空闲分区表和分配分区表，从而减小每个表格的长度。 第第4 4章章 存储管理存储管理 4.2.1 单一连续分区存储管理 单一连续分区存储管理把整个内存空间的最低端和最高端作为操作系统区，中间作为用户程序区。在DOS操作系统中就采用了这种方法，如图4.7所示。第第4 4章章 存储管理存储管理 分配给用户作业的空间操作系统用户程序未用0 xFFF0ROM中的设备驱动程序用户程序位于RAM中的操作系统0 xFFF0图4.7 单一连续分区存储管理的分配方式 第第4 4章章 存储管理存储

18、管理 这种存储分配思想将内存分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。 单一连续分区的优点是：简单，适用于单用户、单任务的操作系统(比如CP/M和DOS操作系统)，不需要复杂的硬件支持。 单一连续分区的缺点是：一个作业运行时要占用整个内存的地址空间，即使很小的程序也是如此，对内存造成了很大的浪费，内存的利用率很低。第第4 4章章 存储管理存储管理 4.2.2 固定分区分配 为了便于管理整个内存，需建立一个表格来登记和管理整个内存。在这个表中登记了每一个分区的大小，起始地址和分配状态，如表4.1和图4.8所示。当有作业装入时，系统便可以搜索这个表，找出一个大小合适

19、的分区分配给它。当程序运行结束时，可以把它所占用的空间再释放回去。地址重定位可以采用静态地址定位或是动态地址定位的方法。第第4 4章章 存储管理存储管理 表4.1 分区状态表 分区号大小起始地址分配状态120 KB100 K已分配240 KB120 K已分配3100 KB160 K未分配4200 KB260 K已分配第第4 4章章 存储管理存储管理 操作系统0下界寄存器作业A作业B作业C460K160K120K100K下界寄存器260K图4.8 固定分区的内存分配情况第第4 4章章 存储管理存储管理 为了实现多道程序设计，可以按等待作业的类型设置多个等待队列，也可以把所有的等待作业设置为一个等

20、待队列。如图4.9所示为多道程序情况下固定分区的情况，左边为多个等待队列情况下的固定分区，右边为单个等待队列情况下的固定分区。第第4 4章章 存储管理存储管理 多个等待队列分区4分区3分区2分区1操作系统分区4分区3分区2分区1操作系统单个等待队列图4.9 多道程序情况下的固定分区原理第第4 4章章 存储管理存储管理 固定分区的优点是：与单一连续分配方法相比，固定分区法的内存利用率提高了；可以支持多道程序；实现简单，开销小。 固定分区的缺点：必须预先能够估计作业要占用多大的内存空间，有时候这是难以做到的；区内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。第第4 4章章 存储管理存储管理

21、 4.2.3 可变分区 (动态分区分配) 1空闲存储区表 若采用固定分区法，则作业运行时所需内存一般不会刚好等于某一个分区的大小，因此分区内部的“内零头”被白白浪费了；另一方面，固定分区的分区数在系统启动以后不能任意改变，当系统中运行的作业数大于分区数时，就不可避免地会有一些作业分配不到分区，即使所有作业所需存储空间总和小于内存总和也不行。 第第4 4章章 存储管理存储管理 可变分区存储管理法并不预先将内存划分成分区，而是等到作业运行需要内存时才向系统申请，从空闲的内存区中挖一块出来，其大小等于作业所需内存的大小，这样就不会产生“内零头”。管理空闲内存区的数据结构可采用链接法和连续线性表格法。

22、每一个空闲分区用一个map结构管理： struct map unsigned m_size; /空闲分区的长度 char * m_addr; /空闲分区的起始地址 ； struct map coremapN;第第4 4章章 存储管理存储管理 图4.10所示为空闲分区表的初始状态，图4.11为某一时刻空闲分区表的状态。图中，m_size是空闲分区的长度，m_addr是空闲分区的起始地址。各个空闲分区按起始地址由低到高的顺序登记在空闲存储区表中，m_size为0的表项是空白表项，它们集中在表的后部。第第4 4章章 存储管理存储管理 m_sizem_addr00空闲区内存图4.10 空闲分区表的初始

23、状态 第第4 4章章 存储管理存储管理 m_sizem_addrm_sizem_addrm_sizem_addr0空闲区已分配区空闲区已分配区已分配区空闲区内存 图4.11 某一时刻空闲分区表的状态 第第4 4章章 存储管理存储管理 2分区分配算法 寻找某个空闲分区，其大小必须大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。 选择分区的算法有四种：最先适应算法、最佳适应算法、最差适应算法和循环最先适应算法。第第4 4章章 存储管理存储管理 1) 最先适应算法(f

24、irst-fit) 最先适应算法是将所有的空闲分区按照地址递增的顺序排列，然后按照分区的先后次序从头开始查找，符合要求的第一个分区就是要找的分区。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。 第第4 4章章 存储管理存储管理 (1) 分配算法： 当为作业分配大小为size的空间时，总是从表的低地址部分开始查找，当第一次找到大于等于申请大小的空间时，就按所需要的大小分配空间给作业，若分配后还有剩余空间，就修改原来的m_size和m_addr，以记录余下的零头；如果作业所需要的空间刚好等于该空间的大小，那么该空间的m_size就为0；然后要删除表中的这些空间，即将各个非零

25、的表项上移。程序描述如下：第第4 4章章 存储管理存储管理 int *ffmalloc( mp , size )struct map *mp;unsigned int size;register int regint;register struct map *bp; /从mp开始，只要size不等于0，逐个地址检查 for(bp=mp; bp-m_size ; bp+ ) if ( bp-m_size = size ) /只要空间足够大struct map unsigned m_size; char * m_addr;；第第4 4章章 存储管理存储管理 regint = bp-m_addr ;

26、 /把老的起始地址保存到把老的起始地址保存到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) 释放算法： 某一个作业释放以前所分配到的内存就是将该内存区归还给操作系统，使其成为空闲区而可以被其他作

27、业使用。回收时如果释放区与临近的空闲区相连接，要将它们合并成较大的空闲区，否则空闲区将被分割得越来越小，最终导致不能利用。另外，空闲区个数越来越多，也会使得空闲区登记表溢出。第第4 4章章 存储管理存储管理 释放算法分四种情况： 仅与前面一个空闲区相连，如图4.12(a)所示。合并前空闲区和释放区以构成一块大的新空闲区，并修改空闲区表项。 与前面空闲区和后面空闲区都相连，如图4.12(b)所示。将三块空闲区合并成一块空闲区。 第第4 4章章 存储管理存储管理 仅仅与后空闲区相连，如图4.12(c)所示。与后空闲区合并，使后空闲区表项的m_addr为释放区的起始地址，m_size为释放区与后空闲

28、区的长度之和。 与前后空闲区都不相连，如图4.12(d)所示。在前、后空闲区表项中间插入一个新的表项，其m_addr为释放区的起始地址，m_size为释放区的长度。 第第4 4章章 存储管理存储管理 后空闲区释放区前空闲区后空闲区释放区前空闲区后空闲区释放区前空闲区后空闲区释放区前空闲区(a)(b)(c)(d)图4.12 释放区与前后空闲区相邻的情况第第4 4章章 存储管理存储管理 程序描述如下：mfree( unsigned size , char * StartAddr ) struct map *bp; char *addr, *taddr; unsigned TmpSize ; add

29、r = StartAddr; struct map unsigned m_size; char * m_addr;；第第4 4章章 存储管理存储管理 for( bp = coremap ; bp-m_addr m_size != 0 ; bp + ) if ( bp coremap & ( 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

30、章章 存储管理存储管理 bp + ; ( bp-1)-m_addr = bp-m_addr ; ( bp-1)-m_size = bp-m_size ; else if ( addr + size = bp-m_addr & bp-m_size ) /与后空闲区相连第第4 4章章 存储管理存储管理 bp-m_addr -= size ; bp-m_size += size ; else if ( size ) do /单独插入空闲分区表,而不与前后相连 taddr = bp-m_addr ; bp-m_addr = addr; addr = taddr; TmpSize = bp-m_size

31、 ;第第4 4章章 存储管理存储管理 bp-m_size = size ; bp + ; while ( size = TmpSize ); 第第4 4章章 存储管理存储管理 最先适应算法的优点：分配简单而且合并相邻的空闲区也比较容易，该算法的实质是尽可能利用存储区低地址的空闲区，而尽量在高地址部分保存较大的空闲区，以便一旦有分配大的空闲区的要求时，容易得到满足。在释放内存分区时，如果有相邻的空闲区就进行合并，使其成为一个较大的空闲区。第第4 4章章 存储管理存储管理 最先适应算法的缺点：由于查找总是从表首开始，前面的空闲区被分割得很小时，能满足分配要求的可能性就较小，查找次数就较多。系统中作

32、业越多，这个问题就越来越严重。针对这个问题，对最先适应法稍加改进，就有了循环最先适应法。会产生碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的利用率。第第4 4章章 存储管理存储管理 如图4.13所示是某一个时刻J1、J2、J3、J4四个作业在内存中的分配情况、空闲区表和已分配区表，它们的长度分别是15 KB、10 KB、12 KB、10 KB。J5和J6两个新作业的长度分别为5 KB和13 KB，分配内存后的内存分配情况、空闲区表和已分配区表如图4.14所示。第第4 4章章 存储管理存储管理 空闲区表起始地址15 K48 K80 K长度23 KB20 KB30 KB状态未分

33、配未分配未分配空空空已分配区表0 K起始地址0 K38 K68 K110 K长度15 KB10 KB12 KB10 KB状态J1J2J3J4空空15 K38 K48 K68 K80 K110 K120 KJ1J2J3J4图4.13 最先适应算法分配前的状态第第4 4章章 存储管理存储管理 空闲区表起始地址33 K48 K80 K长度5 KB20 KB30 KB状态未分配未分配未分配空空空已分配区表起始地址0 K38 K68 K110 K15 K20 K长度15 KB10 KB12 KB10 KB5 KB13 KB状态J1J2J3J4J5J6120 KJ1J2J5J6J3J4110 K80 K6

34、8 K48 K38 K33 K20 K15 K0 K图4.14 最先适应算法分配后的状态第第4 4章章 存储管理存储管理 2) 循环最先适应算法 (next-fit，下次适应算法) 相对于最先适应算法，下次适应算法按分区的先后次序，从上次分配的分区开始查找，到最后分区时再回到开头，符合要求的第一个分区就是找到的分区。 第第4 4章章 存储管理存储管理 循环最先适应算法分配时总是从起始查找指针所指从起始查找指针所指向的表项开始向的表项开始，第一次找到满足要求的空闲区时，就分配所需要的空闲区，然后修改表项，并调整起始查找指针，使其指向队列中被分配的后面的那块空闲区。 循环最先适应法的实质是起始查找

35、指针所指的空闲区和其后的空闲区群常为较长时间未被分割过的空闲区，它们已经合并成为大的空闲区的可能性较大，与最先适应算法相比，它在没有增加多少代价的情况下却明显地提高了分配查找的速度。 循环最先适应算法的释放算法与最先适应算法的基本相同。第第4 4章章 存储管理存储管理 3) 最佳适应算法(best-fit) 最佳适应算法的思想是将所有的空闲分区按照其按照其容量递增的顺序排列容量递增的顺序排列，当要求分配一个空白分区时，由小到大进行查找。 第第4 4章章 存储管理存储管理 最佳适应算法的空闲存储区管理表的组织方法可以采用顺序结构，也可以采用链接结构。 最佳适应算法的优点：由于算法是在所有大于或者

36、等于要求分配长度的空闲区中挑选一个最小的分区，所以分配后所剩余的空白块会最小。平均而言，只要查找一半的表格便能找到最佳适应的空白区。如果有一个空白区的容量正好满足要求，则它必被选中。第第4 4章章 存储管理存储管理 最佳适应算法的缺点：由于空闲区是按大小而不是按地址的顺序排列的，因此释放时，要在整个链表上搜索地址相邻的空闲区，合并后又要插入到合适的位置。空白区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用。 其内存分配前的状态如图4.13所示，J5和J6是两个新作业，对它们分配内存后的内存分配情况、空闲区表和已分配区表如图4.15所示。第第4 4章章 存储管理存储管理

37、 4) 最坏适应算法(worst-fit) 最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲分区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。算法基本不留下小空闲分区，但较大的空闲分区不会被保留。第第4 4章章 存储管理存储管理 最坏适应算法的实现与前面的最佳适应算法类似。 最坏适应算法的优点：分配的时候只需查找一次就可以成功，分配的算法很快。 最坏适应算法的缺点：最后剩余的分区会越来越小，无法运行大程序。 其内存分配前的状态如图4.13所示，J5和J6是两个新作业，对它们分配内存后的内存分配情况、空闲区表

38、和已分配区表如图4.16所示。第第4 4章章 存储管理存储管理 空闲区表起始地址15 K66 K80 K长度23 KB2 KB30 KB状态未分配未分配未分配空空空已分配区表起始地址0 K38 K68 K110 K48 K53 K长度15 KB10 KB12 KB10 KB5 KB13 KB状态J1J2J3J4J5J6120 K110 K80 K68 K66 K48 K38 K15 K0 KJ1J2J5J6J3J453 K图4.15 最佳适应算法分配后的状态第第4 4章章 存储管理存储管理 空闲区表起始地址15 K66 K98 K长度23 KB2 KB12 KB状态未分配未分配未分配空空空已分

39、配区表起始地址0 K38 K68 K110 K80 K85 K长度15 KB10 KB12 KB10 KB5 KB13 KB状态J1J2J3J4J5J6120 K110 K80 K68 K48 K38 K15 K0 KJ1J2J5J6J3J498 K85 K图4.16 最差适应算法分配后的状态第第4 4章章 存储管理存储管理 4.2.4 可再定位式分区(可重定位分区分配) 可再定位分区分配即浮动分区分配，是解决碎片碎片问题问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续区域，而留下一个较大的空白区。这好像在一个队列中有些人出列以后，指挥员命令队列向前(或向右)靠拢一

40、样。这种过程我们称之为“靠拢”或“紧凑紧凑”，如图4.17所示。 第第4 4章章 存储管理存储管理 作业7(256 KB)OS作业1(8 K)作业4(24 K)作业5(128 K)作业6(256 K)OS作业1(8 K)作业4(24 K)作业5(128 K)作业6(256 K)OS作业1(8 K)作业4(24 K)作业5(128 K)作业6(256 K)作业7(256 K)图4.17 可再定位分区分配的靠拢过程第第4 4章章 存储管理存储管理 为解决程序浮动问题，可使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始启动执行。但是这种办法有两个缺点：一是要花费较多的处理机时间；二是

41、如果该程序已经执行了一段时间，则不能再从头开始，否则将引起混乱。 较好的办法是采用动态再定位技术。第第4 4章章 存储管理存储管理 4.2.5 伙伴系统（伙伴系统（Buddy System）伙伴系统提供了一个在固定大小和可变大小之间折衷的方案。内存被划分成大小为2的整次幂的单元，初始只有一个包含所有内存的单元。当要将内存分配给进程时，分配大于该进程大小的最小2的整次幂单元。例如，一个需50K内存进程要放入大小为64K的内存单元。如果没有这样的内存单元，大于该进程需求的最小可利用空间被分成原来一半大小的“伙伴”单元，继续分割其中一个伙伴单元，直到创建一个大小合适的分配单元位置。当进程释放内存时，

42、如果互成“伙伴”关系的两个单元均被释放，这两个单元就结合成一个两倍大小的单元。图4.18说明了分配和释放内存时，是如何分割和连接分配单元的。给定大小为2n，伙伴系统维持了一个最大长度为2n的空闲数据块，每种大小的单元各有一个（假定内存大小为28，则大小为28到21的分配单元都有可能得到）。由于有一个单独的各种大小空闲块，伙伴系统分配或释放内存效率较高。然而，由于存在内部碎片和外部碎片，所以伙伴系统内存利用率不高。第第4 4章章 存储管理存储管理 图图4.18 伙伴系统伙伴系统第第4 4章章 存储管理存储管理 4.2.6 多重分区多重分区 可变分区虽然解决了多道程序运行的情况，但是总是有碎片的问

43、题，而且一个程序总是一定要放在一个分区中。为了解决这个问题，就引入了多重分区的分配方案。 所谓多重分区，就是把一个程序放在多个分区中，这样当一个作业在一个分区中装不下时，可以把它装入到另外一个分区，依此类推。采用多重分区分配方案，可以使存储空间的利用率得到提高，但是实现起来比较困难，所以这里不再赘述。第第4 4章章 存储管理存储管理 4.3 页式存储管理页式存储管理 4.3.1 基本原理 把作业的虚拟地址空间划分成若干个长度相等的页(pages)，也可以称为“虚页”，每一个程序的虚页都从0开始编号。主存也划分成若干个与虚页长度相等的页框(page frame)，也称为页面或实页。在静态页式存储

44、管理系统中，作业加载时可以将任意一页放入内存中的任意一个页框，而且这些页框不必连续，从而实现了不连续分配。第第4 4章章 存储管理存储管理 但是要求一个作业在运行前将其所有的虚页全部都装入主存的块中，当然这就要求主存中有足够多的空闲块，否则程序便不能运行。如图4.18所示是分页存储管理的基本原理。 第第4 4章章 存储管理存储管理 物理地址空间作业2(0页)作业2(1页)作业1(0页)作业1(1页)作业2(2页)作业3(0页)操作系统724120615080页号 块号作业1作业2作业301 K2 K01 K2 K3 K1 K010 K9 K8 K7 K6 K5 K4 K3 K2 K1 K0 K

45、逻辑地址空间页面变换表图4.19 分页存储管理的基本原理第第4 4章章 存储管理存储管理 在分页系统中，页的大小往往都是2的整数次幂，因此在分页系统中，地址的结构由两部分构成：P(页号)和D(页内偏移量)，如图4.19所示。页内偏移量的值为02n-1。 P=INTA/LD=A mod L 注:A为逻辑地址,页面大小为L 页号页内偏移量1910 90图4.20 页的划分第第4 4章章 存储管理存储管理 对于分页系统来说，程序在虚拟地址空间是连续的，但却要映射到物理内存中不连续的空闲frame中，所以需要系统在内存中开辟一个页表区来建立每一个作业的虚页号到物理内存的frame号之间的映射关系，这个

46、表格就叫做页变换表(page management table)，也叫页表。页表中的内容分为三部分：页号、块号和页内偏移量。 程序执行的时候，对于每一条访问内存的指令，分页系统的地址变化过程如图4.20所示。第第4 4章章 存储管理存储管理 图4.21 分页式存储管理的地址变换过程页表始址页表始址页表长度页表长度页表寄存器页表块号页号5332712052018物理地址32018逻辑地址越界中断第第4 4章章 存储管理存储管理 过程说明： (1) 由硬件机构自动将虚拟地址字分成虚页号和页内偏移量两个部分，虚页号送给累加器，它和页表起始地址之和就是所要查找的表项。 (2) 由页表控制寄存器中的页表

47、起始地址和虚拟地址字中的虚页号查找页表，对应的虚页号的页表地址为：页表起始地址虚页号页表表项长度。 (3) 将页表中取出的frame号和虚拟地址字中的页内偏移量一起装入到地址寄存器，根据地址寄存器中的地址值来访问内存。第第4 4章章 存储管理存储管理 4.3.2 页式存储管理的地址变换 1页式管理的数据结构 页式存储管理系统中，当进程建立时，操作系统为进程中所有的页分配页块。当进程撤消时需收回所有分配给它的物理页块。 第第4 4章章 存储管理存储管理 为了完成上述功能，在一个页式存储管理系统中，一般要采用如下的数据结构： (1) 进程页表：是逻辑页号(本进程的地址空间)到物理页面号(实际内存空

48、间)的映射。 (2) 物理页面表(空闲内存页表)：描述物理内存空间的分配使用状况。整个系统有一个物理页面表。其数据结构是位示图(如图4.22所示)和空闲页面链表，用来记录内存中每个页的使用情况和当前空闲页的总数。 第第4 4章章 存储管理存储管理 0/10/10/10/10/1031017空闲块数图4.23 位示图 第第4 4章章 存储管理存储管理 (3) 请求表：描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里。整个系统有一个请求表。第第4 4章章 存储管理存储管理 2. 地址变换机构 前面已经指出，在页式存储系统中，指令所给出的地址分为两部分：逻辑页号和页内偏

49、移量。CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内偏移量相加即可形成物理地址，如图4.23所示。 第第4 4章章 存储管理存储管理 程序装入后执行时，应该需要内存管理单元(Memory Management Unit，MMU)的支持，根据进程页表进行执行时的动态地址映射和保护。映射的过程如上所述。MMU的位置和功能如图4.24所示。第第4 4章章 存储管理存储管理 图4.24 MMU的位置和功能CPUCPU把虚地址送给MMU内存总线MMU把物理地址送给存储器内存管理单元(MMU)磁盘控制器 MMU是Memory Management Unit的缩写

50、，中文名是存储器管理单元，它是中央处理器（CPU）中用来管理虚拟存储器、物理存储器的控制线路，同时也负责虚拟地址映射为物理地址，以及提供硬件机制的内存访问授权。 第第4 4章章 存储管理存储管理 物理地址81C4有效地址21C4823120页面号页号控制寄存器页表长度 页表地址图4.25 页式地址变换 第第4 4章章 存储管理存储管理 页面变换（页表建立）的过程是：先要得到进程所需要的页数，参照空闲内存页表，看是否有这么多的空闲页，如果有，则将N个页面分配给这个进程，并修改空闲内存页表，将程序一次性全部装入用户区内存，同时建立起这个进程的进程页表，也就是页面变换表。如果没有N个空闲页面，则被拒