第4章__存储管理ppt课件计算机操作系统第三版（专业教育）

《第4章__存储管理ppt课件计算机操作系统第三版（专业教育）》由会员分享，可在线阅读，更多相关《第4章__存储管理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 700程序A的地址空间程序A的存

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

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

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

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

12、ddress)，在可执行文件中将该名字改写为指令直接使用的数字地址，如图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，就可以适应多种使用环境并提供不同的功能。第第4 4章章 存储管理存储管理 动态链接的缺点

14、是：(1)增加了程序执行时的链接开销。(2)程序由多个文件组成，因此增加了管理复杂度。第第4 4章章 存储管理存储管理 4.1.5 存储管理的任务 在现代操作系统中，存储管理的主要任务有以下几个方面。(1)存储分配和回收：是存储管理的主要内容，用来确定其算法和相应的数据结构。(2)地址变换(地址再定位)：可执行文件生成中的链接技术、程序加载时的重定位技术及进程运行时硬件和软件的地址变换技术和机构。第第4 4章章 存储管理存储管理 (3)存储共享和保护：将代码和数据共享，设定对地址空间的访问权限(读、写、执行)。(4)存储器扩充：它涉及存储器的逻辑组织和物理组织，有两种控制方式：如果由应用程序控

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

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

17、表，从而减小每个表格的长度。第第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所示。当有作业装入时，系统便可以搜索这个表，找出一个大小合适的分区分配给它。当程序运行结束时，可以把它所占用的空间再释放回去。地址重定位可以采用静态地址定位或是动态地址定位的方法。第第4 4章章 存储管理存

19、储管理 表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章章 存储管理存储管理 为了实现多道程序设计，可以按等待作业的类型设置多个等待队列，也可以把所有的等待作业设置为一个等待队列。如图4.9所示为多道程序情况下固定分区的情况，左边为多个等待队列情况下的固定分区，右边为单个等待队列情况下的固定分区。第第4 4章章 存储

20、管理存储管理 多个等待队列分区4分区3分区2分区1操作系统分区4分区3分区2分区1操作系统单个等待队列图4.9 多道程序情况下的固定分区原理第第4 4章章 存储管理存储管理 固定分区的优点是：与单一连续分配方法相比，固定分区法的内存利用率提高了；可以支持多道程序；实现简单，开销小。固定分区的缺点：必须预先能够估计作业要占用多大的内存空间，有时候这是难以做到的；区内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。第第4 4章章 存储管理存储管理 4.2.3 可变分区(动态分区分配)1空闲存储区表 若采用固定分区法，则作业运行时所需内存一般不会刚好等于某一个分区的大小，因此分区内部的“内零头

21、”被白白浪费了；另一方面，固定分区的分区数在系统启动以后不能任意改变，当系统中运行的作业数大于分区数时，就不可避免地会有一些作业分配不到分区，即使所有作业所需存储空间总和小于内存总和也不行。第第4 4章章 存储管理存储管理 可变分区存储管理法并不预先将内存划分成分区，而是等到作业运行需要内存时才向系统申请，从空闲的内存区中挖一块出来，其大小等于作业所需内存的大小，这样就不会产生“内零头”。管理空闲内存区的数据结构可采用链接法和连续线性表格法。每一个空闲分区用一个map结构管理：struct map unsigned m_size;/空闲分区的长度 char*m_addr;/空闲分区的起始地址

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

23、.11 某一时刻空闲分区表的状态 第第4 4章章 存储管理存储管理 2分区分配算法 寻找某个空闲分区，其大小必须大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。选择分区的算法有四种：最先适应算法、最佳适应算法、最差适应算法和循环最先适应算法。第第4 4章章 存储管理存储管理 1)最先适应算法(first-fit)最先适应算法是将所有的空闲分区按照地址递增的顺序排列，然后按照分区的先后次序从头开始查找，符合要求的第一个分区就是要找的分区。该算法的分配和释放的时间性

24、能较好，较大的空闲分区可以被保留在内存高端。第第4 4章章 存储管理存储管理 (1)分配算法：当为作业分配大小为size的空间时，总是从表的低地址部分开始查找，当第一次找到大于等于申请大小的空间时，就按所需要的大小分配空间给作业，若分配后还有剩余空间，就修改原来的m_size和m_addr，以记录余下的零头；如果作业所需要的空间刚好等于该空间的大小，那么该空间的m_size就为0；然后要删除表中的这些空间，即将各个非零的表项上移。程序描述如下：第第4 4章章 存储管理存储管理 int*ffmalloc(mp,size)struct map*mp;unsigned int size;regist

25、er 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;/把老的起始地址保存到把老的起始地址保存到a bp-m_addr+=size;/起始地址加起始地址加size，把此块一分为二，把此块一分为二 if(bp-m_size-=size)=0)/如果块大小相同为如果块大小相同为0 do

26、 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)所示。合并前空闲区和释

27、放区以构成一块大的新空闲区，并修改空闲区表项。与前面空闲区和后面空闲区都相连，如图4.12(b)所示。将三块空闲区合并成一块空闲区。第第4 4章章 存储管理存储管理 仅仅与后空闲区相连，如图4.12(c)所示。与后空闲区合并，使后空闲区表项的m_addr为释放区的起始地址，m_size为释放区与后空闲区的长度之和。与前后空闲区都不相连，如图4.12(d)所示。在前、后空闲区表项中间插入一个新的表项，其m_addr为释放区的起始地址，m_size为释放区的长度。第第4 4章章 存储管理存储管理 后空闲区释放区前空闲区后空闲区释放区前空闲区后空闲区释放区前空闲区后空闲区释放区前空闲区(a)(b)(

28、c)(d)图4.12 释放区与前后空闲区相邻的情况第第4 4章章 存储管理存储管理 程序描述如下：mfree(unsigned size,char*StartAddr)struct map*bp;char*addr,*taddr;unsigned TmpSize;addr=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;/连接前

29、部空闲区 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;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_a

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

31、配要求的可能性就较小，查找次数就较多。系统中作业越多，这个问题就越来越严重。针对这个问题，对最先适应法稍加改进，就有了循环最先适应法。会产生碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的利用率。第第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

32、 K长度23 KB20 KB30 KB状态未分配未分配未分配空空空已分配区表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

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

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

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

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

37、情况、空闲区表和已分配区表如图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状态未分配未分配未

38、分配空空空已分配区表起始地址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 可再定位式分区(可重定位分区分配)可再定位分区分配即浮动分区分配，是解决碎片碎片问题问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续区域，而留下一个较大的空白区。这好像在一个队列中有些人出列以后，指挥员命令队列向前(或

39、向右)靠拢一样。这种过程我们称之为“靠拢”或“紧凑紧凑”，如图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章章 存储管理存储管理 为解决程序浮动问题，可使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始启动执行。但是这种办法有两个缺点：一是要花费较多的处理机

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

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

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

43、式存储管理系统中，作业加载时可以将任意一页放入内存中的任意一个页框，而且这些页框不必连续，从而实现了不连续分配。第第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

44、 K逻辑地址空间页面变换表图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号之间的映射关系，这

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

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

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

48、(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的缩写，中文名是存储器管理单元，它是

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

50、存储管理存储管理 4.3.3 硬件支持 从上面的介绍可以看出，每访问一次指令或者数据，至少需要访问两次内存，第一次是查找页表，第二次才是真正访问指令或者数据。为了加快页式存储管理的速度，往往也需要硬件支持，主要是页表基址寄存器、页表长度寄存器和关联存储器等一些寄存器。第第4 4章章 存储管理存储管理 1系统设置一对寄存器 (1)页表基址寄存器(Page Table Base Register，PTBR)用户程序在执行过程中每次访问内存时(即每次地址映射时)，MMU需要根据当前进程的进程页表基址寄存器值和此次地址映射的逻辑页号，访问当前进程的进程页表(在内存)，得到此次地址映射的物理页号，再根据

51、逻辑地址中页内偏移量得到真正的物理地址。在进程切换时页表基址寄存器的内容才被保存和恢复，其内容是当前进程的进程页表的内存起始地址。页表基址寄存器的工作原理如图4.26所示。第第4 4章章 存储管理存储管理 物理内存当 前 进 程 页 表MMUPTBR：进程页表基址寄存器逻辑页号当前进程映像查表第一次访存物理页号访存(第二次)物理地址拼合分解逻辑地址页内位移CPUPTBR用户区系统区图4.26 进程页表基址寄存器的工作原理第第4 4章章 存储管理存储管理 由图4.24可以看出以下4点：每次进程切换时不用保存和恢复当前新老进程的整个进程页表，只需保存和恢复PTBR。进程页表是由硬件访问的，这意味着

52、进程页表的格式是由硬件规定的。对进程页表的访问是直接存取。用户程序执行时的每次内存访问，都至少访问内存两次，第一次访问进程页表，第二次才是访问此次要访问的页本身，这意味着用户程序的执行时间将增加一倍。第第4 4章章 存储管理存储管理 (2)页表长度寄存器 为了实现存储保护，在页表基址寄存器的基础上，还需要一个页表长度寄存器，它用来存放当前进程页表的长度。在每次访问内存之前，先检查所取得指令的地址是否超过了进程页表的长度。如果在范围之内，则正常访问内存；如果在长度范围之外，则拒绝此次访问。第第4 4章章 存储管理存储管理 直接采用上述机构进行地址变换实际上是不可取的。由于页表是驻留在内存中的，为

53、了进行地址变换，对于每一条访问内存的指令，系统至少要访问内存两次，这样程序执行的速度只能是原来的1/2。2关联存储器快表 为缩短查找时间，可以将页表装入到关联存储器，按内容查找逻辑页号到物理页号的映射。很多页式系统都有一组关联存储器(Translation Lookaside Buffer，TLB)，用来存放当前运行作业的页表表项，以加速地址变换过程，这种页表称为快表，它是介于内存与寄存器之间的存储机制。内存中的页表有时也称为慢表。利用快表进行地址变换的过程如图4.25所示。第第4 4章章 存储管理存储管理 虚拟地址字快表BP地址寄存器快 表PBDPD页表基址寄存器SL图4.27 利用快表进行

54、地址变换的过程页表页表第第4 4章章 存储管理存储管理 两级和多级页表两级和多级页表两级页表 解决大页表占用大的连续存储空间的问题；关于“页表”的分页存放“页表”外层页表(页目录)；逻辑地址：外层页号+外层页内地址+页内地址多级页表10位10位12位第第4 4章章 存储管理存储管理 页框为4K;页目录项(4Byte)用来寻址一个页表；页表项(4Byte)用来指定一个物理内存页面。图中二级目录的寻址空间范围是图中二级目录的寻址空间范围是?该页目录表寻址的该页目录表寻址的所有页表共可以寻址所有页表共可以寻址1024*1024*4096=4G 内内存空间。存空间。第第4 4章章 存储管理存储管理 4

55、.28 地址变换示意图(CPU的寄存器CR3用来确定当前页目录的物理地址)4.29 页目录和页表表项结构 每个表项由页框地址、访问标志位、脏（已改写）标志位和存在标志位等构成。第第4 4章章 存储管理存储管理 外部页表块号页号321078110110页表分页1122312021113001231121131011第第4 4章章 存储管理存储管理 外部页表外部页表外部页表寄存器寄存器物理地址外部页号P1外部页内地址P2逻辑地址页内地址d页表第第4 4章章 存储管理存储管理 4.3.5 优缺点 分页式存储管理的优点：(1)没有外碎片，每个内碎片不超过页的大小。(2)一个程序不必连续存放。(3)便于

56、改变程序占用空间的大小(主要指随着程序运行而动态生成的数据增多，要求地址空间相应增长，通常由系统调用完成而不是操作系统自动完成)。第第4 4章章 存储管理存储管理 分页式存储管理的缺点：(1)程序要全部装入内存。(2)采用动态地址变换机构会增加计算机的成本和降低处理机的速度。(3)各种表格要占用一定的内存空间，而且要花费一定的时间来建立和管理这些表格。(4)存储扩充问题没有得到解决。(5)不易实现共享。(6)不便于动态连接。第第4 4章章 存储管理存储管理 4.4 段式存储管理段式存储管理 通常，一个作业是由若干个自然段组成的。因而，用户希望能把自己的作业按照逻辑关系划分为若干个段，每个段都有

57、自己的名字和长度。要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，每个段都从0开始编址。这样，用户程序在执行中可用段名和段内地址进行访问。例如，下述的两条指令便是使用的段名和段内地址。第第4 4章章 存储管理存储管理 LOAD L，A|(D)STORE I，B|(C)其中，前一条指令的含义是将分段A中D单元内的值读入寄存器L；后一条指令的含义是将寄存器I的内容存入分段B中的C单元内。第第4 4章章 存储管理存储管理 段式存储管理(simple segmentation)可以实现共享共享。通常，在实现程序和数据的共享时，都是以信息的逻辑单位为基础的，比如共享某个例程和函数。段式存

58、储管理可以实现分段保护分段保护。在多道程序环境下，为了防止其他程序对某程序在内存中的数据有意无意的破坏，必须采取保护措施。段式存储管理可以实现动态链接。段式存储管理使得段可以动态增长。第第4 4章章 存储管理存储管理 4.4.1 基本思想 在页式存储管理思想中，作业的地址空间是连续的一维地址空间，程序的各个目标模块都由链接程序装配成一个可执行的程序后装入内存执行。第第4 4章章 存储管理存储管理 我们根据程序的模块结构，把作业地址空间划分为大小不同的一些块，我们把这些大小不同的块叫做段。每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的，通常分为主程序段

59、、子程序段、库函数段和数据段等等。同时在物理内存中，也分成一些和这些块一样大的块。分段的基本原理如图4.26所示。第第4 4章章 存储管理存储管理 主程序段MKCALLA116CALLYFCALLXE0子程序段X子程序段YL0P0数组A工作区段BS025476N0F116E图4.26 分段的基本原理第第4 4章章 存储管理存储管理 作业在装入的时候是一次性全部装入的，如果不是一次性装入，就叫做请求分段式的管理。将程序的地址空间划分为若干个段(segment)，程序加载时，为每个段分配其所需的一个连续内存分区，而进程中的各个段可以不连续地存放在内存的不同分区中。物理内存的管理采用动态分区的思想，

60、即在为某物理内存的管理采用动态分区的思想，即在为某个段分配物理内存时，可以采用最先适应法、下次适个段分配物理内存时，可以采用最先适应法、下次适应法和最佳适应等方法。应法和最佳适应等方法。第第4 4章章 存储管理存储管理 在收回某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。分段式存储管理也需要硬件支持，以实现逻辑地址到物理地址的映射。分段式存储管理的基本原理如图4.27所示。第第4 4章章 存储管理存储管理 0KN0P0L0N0SK主存1000长度作业1的地址空间PLNS3200150060008000500032005000操作系统60008000LSKP段地址MXYAB逻辑地址

61、图4.27 分段式存储管理的基本原理第第4 4章章 存储管理存储管理 在分段式存储管理的思想中，程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段，其优点是可以分别进行编写和编译；可以针对不同类型的段采取不同的保护；可以以段为单位来进行共享，包括通过动态链接进行代码共享。在分段存储管理系统中，作业地址空间的每一个单元均采用二维地址(S，W)，其中，S为段号，W为段内地址或者偏移量，如图4.28所示。段号(S)段内地址(W)图4.28 进程段地址 第第4 4章章 存储管理存储管理 4.4.2 分段式管理的数据结构 (1)进程段表：也叫段变换表(SMT)，如图4.29

62、所示。它描述组成进程地址空间的各段。它可以是指向系统段表中表项的索引，每段都有段基址(base address)。(2)系统段表：描述系统所有占用的段。(3)空闲段表：描述了内存中所有空闲段，可以结合到系统段表中。内存的分配算法可以采用最先适应法、最佳适应法和最坏适应法。第第4 4章章 存储管理存储管理 35C4段表段号S内存未越界段号0123起始地址1500340042005300段表起始地址寄存器段表长度寄存器11C4偏移量W图4.29 段式地址变换第第4 4章章 存储管理存储管理 4.4.3 分段式管理的地址变换 为了实现从逻辑地址到物理地址的变换功能，在系统中设置了段表基址寄存器和段表

63、长度寄存器。在进行地址变换时，系统将逻辑地址中的段号S与段表长度STL进行比较。若SSTL，表示段号太大，则越界访问，产生越界中断；若未越界，则根据段表的起始地址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后再检查段内地址D是否超过该段的段长SL。若DSL，同样发出越界中断；若未越界，则将该段的基址D与段内地址相加，即得到要访问的内存物理地址。第第4 4章章 存储管理存储管理 和分页式存储管理系统一样，当段表放在内存中时，分段式每访问一个数据或者指令，都需至少访问内存两次，从而成倍地降低了计算机的速率。解决的办法和分页存储管理的思想类似，即再增设一个关联寄存器，用

64、于保存最近常用的段表项。由于一般情况下段比页大，因而段表项的数目比页表数目少，其所需的关联寄存器也相对较小，可以显著地减少存取数据的时间。第第4 4章章 存储管理存储管理 4.4.4 分段式管理的硬件支持 如上面所述，和分页式存储管理的思想类似，也可以设置一对寄存器：段表基址寄存器和段表长度寄存器。段表基址寄存器用于保存正在运行进程的段表的基址，而段表长度寄存器用于保存正在运行进程的段表的长度。第第4 4章章 存储管理存储管理 同样，和分页式存储管理的思想类似，也可以设置联想存储器，它是介于内存与寄存器之间的存储机制，和分页式存储管理系统一样也叫快表。它的用途是保存正在运行进程的段表的子集(部

65、分表项)，其特点是可按内容并行查找。引入快表的作用是为了提高地址映射速度，实现段的共享和段的保护。快表中的项目包括：段号、段基址、段长度、标识(状态)位、访问位和淘汰位。第第4 4章章 存储管理存储管理 4.4.5 分段式管理的优缺点 分段式存储管理的优点：没有内碎片，外碎片可以通过内存紧凑来消除；便于改变进程占用空间的大小；便于实现共享和保护，即允许若干个进程共享一个或者多个段，对段进行保护。如图4.30所示是分段系统中共享一个compiler编译器程序的例子。分段式存储管理的缺点：作业需要全部装入内存，不能实现存储扩充。第第4 4章章 存储管理存储管理 段表进程2段号16040起始地址16

66、0024001604016004400compilor源程序1源程序2compilor源程序2进程1compilor源程序1内存1600240031004400图4.30 分段系统中共享compilor的示意图 第第4 4章章 存储管理存储管理 4.4.6 分页式管理和分段式管理的比较 (1)分页是出于系统管理的需要，分段是出于用户应用的需要。(2)页的大小是系统固定的，而段的大小则通常不固定。(3)逻辑地址表示：分页是一维的，各个模块在链接时必须组织在同一个地址空间；而分段是二维的，各个模块在链接时可以把每个段组织成一个地址空间。(4)通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。(5)分段式存储管理可以实现内存共享，而分页式存储管理则不能实现内存共享。但是两者都不能实现存储扩充。分页式管理和分段式管理的比较如图4.31所示。第第4 4章章 存储管理存储管理 0分段分页Code注：和表示动态数据增加。0LM00N1234567应用程序DataFree SpacesStack图4.31 页式管理与段式管理的比较第第4 4章章 存储管理存储管理 4.5 段页式存储管理段