第第5章章 存储管理存储管理5.1 存储管理的功能存储管理的功能5.2 分区存储管理分区存储管理5.3 覆盖与交换技术覆盖与交换技术5.4 页式管理页式管理5.5 段式与段页式管理段式与段页式管理5.6 本章小结本章小结5.1 存储管理的功能存储管理的功能存储管理的功能如下存储管理的功能如下: 1.主存空间的分配与回收主存空间的分配与回收 2.地址转换地址转换 3.主存空间的共享和保护主存空间的共享和保护 4.主存空间的扩充主存空间的扩充5.1.2 重定位重定位一一.绝对地址和逻辑地址绝对地址和逻辑地址内存地址的集合称为内存空间或物理地址空间。内存内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的称为内存地址的编中，每一个存储单元都与相应的称为内存地址的编号相对应。显然，内存空间是一维线性空间。号相对应。显然，内存空间是一维线性空间。二二.虚存的一维线性空间或多维线性空间变换到内存虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性空间的唯一的一维物理线性空间1.虚拟空间的划分问题虚拟空间的划分问题2.把虚拟空间中已链接把虚拟空间中已链接和划分好的内容装入和划分好的内容装入内存，并将虚拟地址内存，并将虚拟地址映射为内存地址的问题。映射为内存地址的问题。1. 静态地址重定位静态地址重定位在虚空间程序执行之前由装配程序完成地址映射工作在虚空间程序执行之前由装配程序完成地址映射工作.静态重定位的优点是不需要硬件支持。静态重定位的优点是不需要硬件支持。缺点缺点:不能移动不能移动在程序执行之前将有关部分全部装入在程序执行之前将有关部分全部装入必须占用连续的内存空间，这就难以做到程序和数必须占用连续的内存空间，这就难以做到程序和数据的共享。据的共享。2. 动态地址重定位动态地址重定位动态地址重定位（动态地址重定位（dynamic address relocation）是在）是在程序执行过程中，在程序执行过程中，在CPU访问内存之前，将要访问访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。靠硬件地址变换机构完成。地址重定位机构需要一个地址重定位机构需要一个(或多个或多个)基地址寄存器基地址寄存器BR和和一个一个(或多个或多个)程序虚拟地址寄存器程序虚拟地址寄存器VR。指令或数据。指令或数据的内存地址的内存地址MA与虚拟地址的关系为与虚拟地址的关系为: MA=(BR)+ (VR)这里，这里，(BR)与与(VR)分别表示寄存器分别表示寄存器BR与与VR中的内容。中的内容。图图5.3 动态地址重定位动态地址重定位动态重定位的主要优点有动态重定位的主要优点有:(1) 可以对内存进行非连续分配。可以对内存进行非连续分配。 (2) 动态重定位提供了实现虚拟存储器的基础。动态重定位提供了实现虚拟存储器的基础。 (3) 有利于程序段的共享。有利于程序段的共享。5.1.3 内外存数据传输的控制内外存数据传输的控制1.是用户程序自己控制是用户程序自己控制:覆盖技术覆盖技术2.是操作系统控制是操作系统控制:交换交换(swapping)方式方式请求调入请求调入(on demand)方式和预调入方式和预调入(on prefetch)方方式。式。5.1.4 内存的分配与回收内存的分配与回收几种策略和数据结构几种策略和数据结构:(1)分配结构分配结构(2) 放置策略放置策略(3) 交换策略交换策略 (4) 调入策略。调入策略。(5) 回收策略回收策略5.1.5 内存信息的共享与保护内存信息的共享与保护常用的内存信息保护方法有硬件法、软件法和软硬件常用的内存信息保护方法有硬件法、软件法和软硬件结合三种。结合三种。1.上下界保护法是一种常用的硬件保护法上下界保护法是一种常用的硬件保护法2.保护键法。保护键法。图图5.5 保护键保护法保护键保护法3.界限寄存器与界限寄存器与CPU的用户态或核心态工作方式相结的用户态或核心态工作方式相结合的保护方式。合的保护方式。 在这种保护模式下，用户态进程只能访问那些在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。进程则可以访问整个内存地址空间。UNIX系统就系统就是采用的这种内存保护方式。是采用的这种内存保护方式。5.2 分区存储管理分区存储管理5.2.1 分区管理基本原理分区管理基本原理 分区管理的基本原理是给每一个内存中的进程分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区划分一块适当大小的存储区,以连续存储各进程的程以连续存储各进程的程序和数据，使各进程得以并发执行。序和数据，使各进程得以并发执行。 按分区的时机，分区管理可以分为固定分区和按分区的时机，分区管理可以分为固定分区和动态分区两种方法。动态分区两种方法。1. 固定分区法固定分区法 把内存区固定地划分为若干个大小不等的区域。把内存区固定地划分为若干个大小不等的区域。划分的原则由系统操作员或操作系统决定。分区一划分的原则由系统操作员或操作系统决定。分区一旦划分结束，在整个执行过程中每个分区的长度和旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。内存的总分区个数将保持不变。 系统对内存的管理和控制通过数据结构系统对内存的管理和控制通过数据结构分分区说明表进行，区说明表进行，图图5.6 固定分区法固定分区法2. 动态分区法动态分区法 动态分区法在作业执行前并不建立分区，分区动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了固随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率费现象，从而提高了内存的利用率图图5.7 内存初始分配情况内存初始分配情况图图5.8 内存分配变化过程内存分配变化过程内存管理用数据结构内存管理用数据结构:可用分区表可用分区表:每个表目记录一个空闲区每个表目记录一个空闲区可用分区自由链可用分区自由链:查找比可用表困难，但不必占用查找比可用表困难，但不必占用额外的内存区。额外的内存区。请求表请求表:请求表的每个表目描述请求内存资源的作请求表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。业或进程号以及所请求的内存大小。图图5.9 可用表、自由链及请求表可用表、自由链及请求表图图5.10 固定分区分配算法固定分区分配算法5.2.2 分区的分配与回收分区的分配与回收1. 固定分区时的分配与回收固定分区时的分配与回收2. 动态分区时的分配与回收动态分区时的分配与回收动态分区时的分配与回收主要解决三个问题动态分区时的分配与回收主要解决三个问题: (1) 对于请求表中的要求内存长度，从可用表或自由对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。链中寻找出合适的空闲区分配程序。(2) 分配空闲区之后，更新可用表或自由链。分配空闲区之后，更新可用表或自由链。(3) 进程或作业释放内存资源时，和相邻的空闲区进进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。行链接合并，更新可用表或自由链。动态分区时的分配方法：动态分区时的分配方法：最先适应法最先适应法(first fit algorithm)最佳适应法最佳适应法(best fit algorithm)最坏适应法最坏适应法(worst fit algoriathm)(1) 最先适应法最先适应法按起始地址递增的次序排列按起始地址递增的次序排列(2) 最佳适应算法最佳适应算法最佳适应算法要求从小到大的次序组成空闲区可用表最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。或自由链。(3) 最坏适应算法最坏适应算法最坏适应算法要求空闲区按其大小递减的顺序组成空最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。闲区可用表或自由链。图图5.11 最先适应算法最先适应算法4. 几种分配算法的比较几种分配算法的比较思考：三种分配算法的各自特点思考：三种分配算法的各自特点从查找速度、释放速度及空闲区的利用等三个方面对从查找速度、释放速度及空闲区的利用等三个方面对上述三种算法进行比较。上述三种算法进行比较。内存回收内存回收4种情况：种情况：如果释放区与上下两空闲区相邻如果释放区与上下两空闲区相邻如果释放区只与上空闲区相邻如果释放区只与上空闲区相邻如果释放区与下空闲区相邻如果释放区与下空闲区相邻如果释放区不与任何空闲区相邻如果释放区不与任何空闲区相邻图图5.12 空闲区的合并空闲区的合并5.2.3 有关分区管理其他问题的讨论有关分区管理其他问题的讨论1. 关于虚存的实现关于虚存的实现2. 关于内存扩充关于内存扩充3. 关于地址变换和内存保护关于地址变换和内存保护设设CPU指令所要访问的虚拟地址为指令所要访问的虚拟地址为D静态重定位静态重定位:在上下限寄存器中值之间在上下限寄存器中值之间动态重定位动态重定位若若DVR (VR是限长寄存器中的限长值是限长寄存器中的限长值)，则说明地址越界，则说明地址越界若若D=VR，则该地址是合法的，由硬件完成对该虚拟地址的，则该地址是合法的，由硬件完成对该虚拟地址的动态重定位。动态重定位。保护键法也可用来对内存各分区提供保护。保护键法也可用来对内存各分区提供保护。4. 分区存储管理的主要优缺点分区存储管理的主要优缺点分区存储管理的主要优点如下分区存储管理的主要优点如下:(1) 实现了多个作业或进程对内存的共享，有助于多实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。道程序设计，从而提高了系统的资源利用率。(2) 该方法要求的硬件支持少，管理算法简单，因而该方法要求的硬件支持少，管理算法简单，因而实现容易。实现容易。主要缺点有主要缺点有:(1) 内存利用率仍然不高。和单一连续分配算法一样，内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未用过的信息。而且，还存在存储器中可能含有从未用过的信息。而且，还存在着严重的碎小空闲区着严重的碎小空闲区(碎片碎片)不能利用的问题。不能利用的问题。(2) 作业或进程的大小受分区大小控制，除非配合采作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。用覆盖和交换技术。(3) 难以实现各分区间的信息共享。难以实现各分区间的信息共享。5.3.1 覆盖技术覆盖技术 把程序划分为若干个功能上相对独立的程序段，把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。共享同一块内存区。 覆盖技术要求程序员提供一个清楚的覆盖结构，覆盖技术要求程序员提供一个清楚的覆盖结构，程序员负担较重。程序员负担较重。5.3 覆盖与交换技术覆盖与交换技术图图5.13 覆盖示例覆盖示例5.3.2 交换技术交换技术 交换是指先将内存某部分的程序或数据写入外交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。据到内存中来，并让其执行的一种内存扩充技术。 交换主要是在进程或作业之间进行，而覆盖则交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或进程内进行。主要在同一个作业或进程内进行。 交换进程由换出和换入两个过程组成。其中换交换进程由换出和换入两个过程组成。其中换出出(swap out)过程把内存中的数据和程序换到外存过程把内存中的数据和程序换到外存交换区，而换入交换区，而换入(swap in)过程把外存交换区中的数过程把外存交换区中的数据和程序换到内存分区中。据和程序换到内存分区中。 1.各进程的虚拟空间被划分成若干个长度相等的页各进程的虚拟空间被划分成若干个长度相等的页(page)。进。进程的虚地址变为页号程的虚地址变为页号p与页内地址的与页内地址的d所组成。所组成。2.把内存空间也按页的大小划分为片或页面把内存空间也按页的大小划分为片或页面(page frame)。3.用户进程在内存空间内除了在每个页面内地址连续之外，每用户进程在内存空间内除了在每个页面内地址连续之外，每个页面之间不再连续。个页面之间不再连续。 19 10 9 0图图5.14 页的划分页的划分页号P页内地址d5.4 页页 式式 管管 理理5.4.1 页式管理的基本原理页式管理的基本原理优点：优点：第一是实现了内存中碎片的减少，因为任一碎片都会第一是实现了内存中碎片的减少，因为任一碎片都会小于一个页面。小于一个页面。第二是实现了由连续存储到非连续存储这个飞跃，为第二是实现了由连续存储到非连续存储这个飞跃，为在内存中局部地、动态地存储那些反复执行或即将在内存中局部地、动态地存储那些反复执行或即将执行的程序和数据段打下了基础。执行的程序和数据段打下了基础。5.4.2 静态页面管理静态页面管理 静态页面管理方法在作业或进程开始执行之前，静态页面管理方法在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的各把该作业或进程的程序段和数据全部装入内存的各个页面中，并通过页表个页面中，并通过页表(page mapping table)和硬件和硬件地址变换机构实现虚拟地址到内存物理地址的地址地址变换机构实现虚拟地址到内存物理地址的地址映射。映射。(1) 页表页表最简单的页表由页号与页面号组成。页式管理时每个最简单的页表由页号与页面号组成。页式管理时每个进程至少拥有一个页表。进程至少拥有一个页表。图图5.15 基本页表示例基本页表示例页号页面号1. 内存页面分配与回收内存页面分配与回收(2) 请求表请求表请求表用来确定作业或进程的虚拟空间的各页在内存请求表用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。请求表整个系统一张，如图中的实际对应位置。请求表整个系统一张，如图5.16所示。所示。图图5.16 请求表示例请求表示例(3) 存储页面表存储页面表存储页面表也是整个系统一张，存储页面表指存储页面表也是整个系统一张，存储页面表指出内存各页面是否已被分配出去出内存各页面是否已被分配出去, 以及未分配页面的总数。以及未分配页面的总数。位示图位示图空闲页面链空闲页面链图图5.17 位示图位示图图图5.18 页面分配算法流图页面分配算法流图2. 分配算法分配算法图图5.19 页号与页面号页号与页面号设每个页面长度为设每个页面长度为1K，指令，指令LOAD 1，2500的虚地址的虚地址为为100，怎样通过图，怎样通过图5.19所示页表来找到该指令所对所示页表来找到该指令所对应的物理地址呢应的物理地址呢? 页号页面号0213283. 地址变换地址变换图图5.20 地址变换地址变换取一个数据或指令至少要访问内存两次以上取一个数据或指令至少要访问内存两次以上办法办法1：就是把页表放在寄存器中而不是内存中，但：就是把页表放在寄存器中而不是内存中，但由于寄存器价格太贵，这样做是不可取的由于寄存器价格太贵，这样做是不可取的办法办法2：是在地址变换机构中加入一个高速联想存储：是在地址变换机构中加入一个高速联想存储器，构成一张快表。在快表中，存入那些当前执行器，构成一张快表。在快表中，存入那些当前执行进程中最常用的页号与所对应的页面号，从而以提进程中最常用的页号与所对应的页面号，从而以提高查找速度。高查找速度。静态页式管理静态页式管理优点：解决了分区管理时的碎片问题。优点：解决了分区管理时的碎片问题。缺点：在执行前全部装入内存缺点：在执行前全部装入内存 作业或进程的大小仍受内存可用页面数的限制作业或进程的大小仍受内存可用页面数的限制5.4.3 动态页式管理动态页式管理分为请求页式管理和预调入页式管理。分为请求页式管理和预调入页式管理。共同点：请求页式管理和预调入页式管理在作业或进程开始共同点：请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。工作区部分。其他部分则在执行过程中动态装入。主要区别：在调入方式上主要区别：在调入方式上 请求页式管理：当需要执行某条指令而又发现它不在内存时请求页式管理：当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其他的数据或指令时，这些指或当执行某条指令需要访问其他的数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外存中令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。相应的页面调入内存。 预调入方式：系统对那些在外存中的页进行调入顺序计算，预调入方式：系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。此顺序将它们顺次调入和调出内存。问题问题1：虚页不在内存中的：虚页不在内存中的-扩充页表的方法解决。扩充页表的方法解决。增设该页是否在内存的中断位以及该页在外存中的增设该页是否在内存的中断位以及该页在外存中的副本起始地址。扩充后的页表如图副本起始地址。扩充后的页表如图5.21。图图5.21 加入中断处理后的页表加入中断处理后的页表页号页面号中断位外存始址0123问题问题2：虚页不在内存时的处理。：虚页不在内存时的处理。第一，采用何种方式把所缺的页调入内存。第一，采用何种方式把所缺的页调入内存。 -产生缺页中断信号，由中断处理程序做出相产生缺页中断信号，由中断处理程序做出相应的处理应的处理第二，如果内存中没有空闲页面时，把调进来的页放第二，如果内存中没有空闲页面时，把调进来的页放在什么地方。在什么地方。 -置换算法置换算法在页表中还应增加一项以记录该页是否曾被改变。增在页表中还应增加一项以记录该页是否曾被改变。增加改变位后的页表项如图加改变位后的页表项如图5.22所示。所示。图图5.22 加入改变位后的页表加入改变位后的页表页号页面号中断位外存始址改变位0123图图5.23 动态页式管理流图动态页式管理流图置换算法置换算法 抖动抖动(thrashing)现象：如果置换算法选择不当，有现象：如果置换算法选择不当，有可能产生刚被调出内存的页又要马上被调回内存，可能产生刚被调出内存的页又要马上被调回内存，调回内存不久又马上被调出内存，如此反复的局面。调回内存不久又马上被调出内存，如此反复的局面。这使得整个系统的页面调度非常频繁，以致大部分这使得整个系统的页面调度非常频繁，以致大部分时间都花费在主存和辅存之间的来回调入调出上。时间都花费在主存和辅存之间的来回调入调出上。这种现象被称为抖动这种现象被称为抖动(thrashing)现象。现象。5.4.4 请求页式管理中的置换算法请求页式管理中的置换算法(1) 随机淘汰算法。随机淘汰算法。 (2) 轮转法和先进先出算法。轮转法和先进先出算法。由实验和测试发现由实验和测试发现FIFO算法和算法和RR算法的内存利用率算法的内存利用率不高。不高。先进先出算法的另一个缺点是它有一种陷阱现象在未先进先出算法的另一个缺点是它有一种陷阱现象在未给进程或作业分配足它所要求的页面数时，有时会给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为现象。这种现象称为Belady现象。现象。图图5.24 FIFO算法的算法的Belady现象现象下面的例子可以用来说明下面的例子可以用来说明FIFO算法的正常换页情况算法的正常换页情况和和Belady现象。例现象。例: 设进程设进程P共有共有8页，且已在内存页，且已在内存中分配有中分配有3个页面，程序访问内存的顺序个页面，程序访问内存的顺序(访问串访问串)为为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。图图5.25 Belady现象示例现象示例(1)缺页率为缺页率为12/17=70.5%7 01203042303212017 7722224440000000000033322222iiii111100033333222图图5.26 Belady现象示例现象示例(2)如果给进程如果给进程P分配分配4个页面，共发生个页面，共发生9次缺页，其缺页次缺页，其缺页率为率为9/17=52.9%7 01203042303212017 7777333333333222000000444444444411111111000000022222222221111123412512345111444555555222111113333332222244设进程设进程P可分为可分为5页，访问串为页，访问串为1，2，3，4，1，2，5，1，2，3，4，5。当进程。当进程P分得分得3个页面时，执行个页面时，执行过程中内存页面变化如图过程中内存页面变化如图5.27所示。所示。图图5.27 Belady现象示例现象示例(3)缺页缺页9次，其缺页率为次，其缺页率为9/12=75%。如果为进程如果为进程P分配分配4个内存页面个内存页面图图5.28 Belady现象示例现象示例(4)缺页次数为缺页次数为10次。即缺页率次。即缺页率=10/12=83.3%。先进先出算法产生先进先出算法产生Belady现象的原因在于它根本没有现象的原因在于它根本没有考虑程序执行的动态特征。考虑程序执行的动态特征。123412512345111111555544222222111153333332222444444333(3) 最近最久未使用页面置换算法最近最久未使用页面置换算法(least recently used)。 该算法的基本思想是该算法的基本思想是: 当需要淘汰某一页时，选择离当当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。前时间最近的一段时间内最久没有使用过的页先淘汰。常用的近似算法有常用的近似算法有:a) 最不经常使用页面淘汰算法最不经常使用页面淘汰算法LFU(least frequently used)。增设一个访问计数器。增设一个访问计数器b) 最近没有使用页面淘汰算法最近没有使用页面淘汰算法NUR。该算法在需要淘汰。该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。增设一个访问位选一页淘汰。增设一个访问位(4) 理想型淘汰算法理想型淘汰算法OPT(optimal replacement algorithm)。5.4.5 存储保护存储保护页式管理可以为内存提供两种方式的保护。一种是地页式管理可以为内存提供两种方式的保护。一种是地址越界保护，另一种是通过页表控制对内存信息的址越界保护，另一种是通过页表控制对内存信息的存取操作方式以提供保护。存取操作方式以提供保护。地址越界保护可由地址变换机构中的控制寄存器的值地址越界保护可由地址变换机构中的控制寄存器的值页表长度和所要访问的虚地址相比较来完成。页表长度和所要访问的虚地址相比较来完成。存取控制保护的实现则是在页表中增加相应的保护位存取控制保护的实现则是在页表中增加相应的保护位即可。即可。5.4.6 页式管理的优缺点页式管理的优缺点优点优点:(1) 有效地解决了碎片问题。有效地解决了碎片问题。(2) 动态页式管理提供了内存和外存统一管理的虚存动态页式管理提供了内存和外存统一管理的虚存实现方式实现方式主要缺点是主要缺点是:(1)要求有相应的硬件支持要求有相应的硬件支持(2) 增加了系统开销增加了系统开销 (3) 请求调页的算法如选择不当，有可能产生抖动现请求调页的算法如选择不当，有可能产生抖动现象。象。(4) 虽然消除了碎片，但每个作业或进程的最后一页虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用。如果页面较大内总有一部分空间得不到利用。如果页面较大 ，则这一部分的损失仍然较大。则这一部分的损失仍然较大。5.5 段式与段页式管理段式与段页式管理5.5.1 段式管理的基本思想段式管理的基本思想段式管理的基本思想是段式管理的基本思想是: 把程序按内容或过程把程序按内容或过程(函数函数)关系分成段，每段有自己的名字。一个用户作业或关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。就是一个二维虚拟存储器。段式管理程序以段为单位分配内存段式管理程序以段为单位分配内存有利于有利于:不同作业或进程之间共享不同作业或进程之间共享 动态链接动态链接5.5.2 段式管理的实现原理段式管理的实现原理1. 段式虚存空间段式虚存空间每个段是一个首地址为零的、连续的一维线性空间。每个段是一个首地址为零的、连续的一维线性空间。段式管理把一个进程的虚地址空间设计成二维结构，段式管理把一个进程的虚地址空间设计成二维结构，即段号即段号s 与段内相对地址与段内相对地址w。段号S段内地址W2. 段式管理的内存分配与释放段式管理的内存分配与释放段式管理中以段为单位分配内存，每段分配一个连段式管理中以段为单位分配内存，每段分配一个连续的内存区。续的内存区。同一进程所包含的各段之间不要求连续。同一进程所包含的各段之间不要求连续。段式管理的内存分配与释放与可变分区相同段式管理的内存分配与释放与可变分区相同另一种情况另一种情况:内存中没有足够的空闲区满足调入段的内存要求时内存中没有足够的空闲区满足调入段的内存要求时 -置换算法置换算法一次调入时所需淘汰的段数与段的大小有关一次调入时所需淘汰的段数与段的大小有关 图图5.29 缺段中断处理过程缺段中断处理过程 图图5.30 段表段表段号始址长度存取方式内外访问位3. 段式管理的地址变换段式管理的地址变换(1) 段表段表(segment mapping table)(2) 动态地址变换动态地址变换 通过访问段表寄存器，得到该进程的段表始址通过访问段表寄存器，得到该进程的段表始址从而可开始访问段表。由虚地址中的段号从而可开始访问段表。由虚地址中的段号s为索引，为索引，查段表。若该段在内存，则判断其存取控制方式是查段表。若该段在内存，则判断其存取控制方式是否有错。如果存取控制方式正确，则从段表相应表否有错。如果存取控制方式正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相目中查出该段在内存的起始地址，并将其和段内相对地址对地址w相加，从而得到实际内存地址。相加，从而得到实际内存地址。 不在内存，则产生缺段中断不在内存，则产生缺段中断,找到足够长度的找到足够长度的空闲区来装入所需要的段。如果内存中的可用空闲空闲区来装入所需要的段。如果内存中的可用空闲区总数小于所要求的段长时，则检查段表中访问位，区总数小于所要求的段长时，则检查段表中访问位，以淘汰那些访问概率低的段并将需要段调入。以淘汰那些访问概率低的段并将需要段调入。 段式管理时的地址变换过程也必须经过二次以段式管理时的地址变换过程也必须经过二次以上的内存访问。上的内存访问。 高速联想寄存器的方法也可以用在高速联想寄存器的方法也可以用在段式地址变换中。段式地址变换中。图图5.31 段式地址变换过程段式地址变换过程图图5.32 段式系统中共享内存副本段式系统中共享内存副本4. 段的共享与保护段的共享与保护(1) 段的共享段的共享段表中可设段表中可设立相应的共立相应的共享位来判别享位来判别该段是否正该段是否正被某个进程被某个进程调用调用(2) 段的保护段的保护段式管理的保护主要有两种。段式管理的保护主要有两种。一种是地址越界保护法，一种是地址越界保护法， 段表中的段长项与虚拟地址中的段内相对地址段表中的段长项与虚拟地址中的段内相对地址比较进行的。若段内相对地址大于段长，系统就会比较进行的。若段内相对地址大于段长，系统就会产生保护中断。不过，在允许段动态增长的系统中，产生保护中断。不过，在允许段动态增长的系统中，段内相对地址大于段长是允许的。为此，段表中设段内相对地址大于段长是允许的。为此，段表中设置相应的增补位以指示该段是否允许该段动态增长。置相应的增补位以指示该段是否允许该段动态增长。另一种是存取方式控制保护法。另一种是存取方式控制保护法。5.5.3 段式管理的优缺点段式管理的优缺点(1) 段式管理也提供了内外存统一管理的虚存实现段式管理也提供了内外存统一管理的虚存实现(2) 在段式管理中，段长可根据需要动态增长。在段式管理中，段长可根据需要动态增长。 (3)便于对具有完整逻辑功能的信息段进行共享。便于对具有完整逻辑功能的信息段进行共享。(4) 便于实现动态链接。便于实现动态链接。要求有更多的硬件支持。这就提高了机器成本。要求有更多的硬件支持。这就提高了机器成本。在碎片问题以及为了消除碎片所进行的合并等问题上较分页在碎片问题以及为了消除碎片所进行的合并等问题上较分页式管理要差。式管理要差。允许段的动态增长也会给系统管理带来一定的难度和开销。允许段的动态增长也会给系统管理带来一定的难度和开销。段式管理的另一个缺点就是每个段的长度受内存可用区大小段式管理的另一个缺点就是每个段的长度受内存可用区大小的限制。的限制。和页式管理一样，段式管理系统在选择淘汰算法时也必须十和页式管理一样，段式管理系统在选择淘汰算法时也必须十分慎重，否则也有可能产生抖动现象。分慎重，否则也有可能产生抖动现象。5.5.4 段页式管理的基本思想段页式管理的基本思想5.5.5 段页式管理的实现原理段页式管理的实现原理1. 虚地址的构成虚地址的构成虚拟地址由三部分组成虚拟地址由三部分组成: 即段号即段号s，页号，页号p和页内相对和页内相对地址地址d。如下所示。如下所示:图图5.33 段页式管理中段表、页表与内存的关系段页式管理中段表、页表与内存的关系2. 段表和页表段表和页表3. 动态地址变换过程动态地址变换过程至少需要访问三次以上的内存。至少需要访问三次以上的内存。为了提高地址转换速度，设置快速联想寄存器就显得为了提高地址转换速度，设置快速联想寄存器就显得比段式管理或页式管理时更加需要。比段式管理或页式管理时更加需要。图图5.34 段页式地址变换段页式地址变换段页式管理的地址变换机构段页式管理的地址变换机构段页式管理优缺点段页式管理优缺点:具有页式管理和段式管理二者的优点。具有页式管理和段式管理二者的优点。但反过来说，由于管理软件的增加，复杂性和开销也但反过来说，由于管理软件的增加，复杂性和开销也就随之增加了。另外，需要的硬件以及占用的内存就随之增加了。另外，需要的硬件以及占用的内存也有所增加。更重要的是，如果不采用联想寄存器也有所增加。更重要的是，如果不采用联想寄存器的方式提高的方式提高CPU的访内速度，将会使得执行速度大的访内速度，将会使得执行速度大大下降。大下降。5.6 局部性原理和抖动问题局部性原理和抖动问题动态页式管理，段式管理以及段页式管理都提供了一动态页式管理，段式管理以及段页式管理都提供了一种将内存和外存统一管理的实现方法。然而，由于种将内存和外存统一管理的实现方法。然而，由于上述实现方法实质上要在内存和外存之间交换信息，上述实现方法实质上要在内存和外存之间交换信息，因此，就要不断地启动外部设备以及相应的处理过因此，就要不断地启动外部设备以及相应的处理过程。一般来说，计算机系统的外部存储器具有较大程。一般来说，计算机系统的外部存储器具有较大的容量而访问速度并不高。为了进行数据的读写而的容量而访问速度并不高。为了进行数据的读写而涉及到的一系列处理程序也要耗去大量的时间。如涉及到的一系列处理程序也要耗去大量的时间。如果内存和外存之间数据交换频繁，势必会造成对输果内存和外存之间数据交换频繁，势必会造成对输入入/输出设备的巨大压力和使得机器的主要开销大输出设备的巨大压力和使得机器的主要开销大多用在反复调入调出数据和程序段上，从而无法完多用在反复调入调出数据和程序段上，从而无法完成用户所要求的工作。因此，要求在内存中存放一成用户所要求的工作。因此，要求在内存中存放一个不小于最低限度的程序段或数据，而且它们必须个不小于最低限度的程序段或数据，而且它们必须是那些正在被调用，或那些即将被调用的部分。是那些正在被调用，或那些即将被调用的部分。由模拟实验知道，在几乎所有的程序的执行中，在一由模拟实验知道，在几乎所有的程序的执行中，在一段时间内，段时间内，CPU总是集中地访问程序中的某一个部总是集中地访问程序中的某一个部分而不是随机地对程序所有部分具有平均访问概率。分而不是随机地对程序所有部分具有平均访问概率。把这种现象称为局部性原理。与把这种现象称为局部性原理。与CPU访问该局部内访问该局部内的程序和数据的次数相比，该局部段的移动速率相的程序和数据的次数相比，该局部段的移动速率相当慢。这就使得前面所讨论的页式管理、段式管理当慢。这就使得前面所讨论的页式管理、段式管理以及段页式管理所实现的虚存系统成为可能。以及段页式管理所实现的虚存系统成为可能。但是，如果不能正确地将那些系统所需要的局部段放但是，如果不能正确地将那些系统所需要的局部段放入内存的话，则显然系统的效率会大大降低，甚至入内存的话，则显然系统的效率会大大降低，甚至无法有效地工作。无法有效地工作。试验表明，任何程序在局部性放入时，都有一个临界试验表明，任何程序在局部性放入时，都有一个临界值要求。当内存分配小于这个临界值时，内存和外值要求。当内存分配小于这个临界值时，内存和外存之间的交换频率将会急剧增加，而内存分配大于存之间的交换频率将会急剧增加，而内存分配大于这个临界值时，再增加内存分配也不能显著减少交这个临界值时，再增加内存分配也不能显著减少交换次数。换次数。这个内存要求的临界值被称为工作集。图这个内存要求的临界值被称为工作集。图5.35说明这说明这种情况。种情况。图图5.35 内存与交换次数的关系内存与交换次数的关系一个进程执行过程中缺页一个进程执行过程中缺页(missing page)的发生有两的发生有两种可能。一种是并发进程所要求的工作集总和大于种可能。一种是并发进程所要求的工作集总和大于内存可提供的可用区。这时，系统将无法正常工作，内存可提供的可用区。这时，系统将无法正常工作，因为缺乏足够的空间装入所需要的程序和数据。另因为缺乏足够的空间装入所需要的程序和数据。另一种可能性是，虽然存储管理程序为每个并发进程一种可能性是，虽然存储管理程序为每个并发进程分配了足够的工作集，但系统无法在开始执行前选分配了足够的工作集，但系统无法在开始执行前选择适当的程序段和数据进入内存。这种情况下，只择适当的程序段和数据进入内存。这种情况下，只能依靠执行过程中，当能依靠执行过程中，当CPU发现所要访问的指令或发现所要访问的指令或数据不在内存时，由硬件中断后转入中断处理程序，数据不在内存时，由硬件中断后转入中断处理程序，将所需要的程序段和数据调入。这是一种很自然的将所需要的程序段和数据调入。这是一种很自然的处理方法。处理方法。当给进程分配的内存小于所要求的工作集时，由于内当给进程分配的内存小于所要求的工作集时，由于内存外存之间交换频繁，访问外存时间和输入存外存之间交换频繁，访问外存时间和输入/输出输出处理时间大大增加，反而造成处理时间大大增加，反而造成CPU因等待数据空转，因等待数据空转，使得整个系统性能大大下降，这就造成了系统抖动。使得整个系统性能大大下降，这就造成了系统抖动。可以利用统计模型进一步分析工作集与抖动之间的关可以利用统计模型进一步分析工作集与抖动之间的关系。系。设设r为为CPU在内存中存取一个内存单元的时间，在内存中存取一个内存单元的时间，t为从为从外存中读出一页数据所需时间，外存中读出一页数据所需时间，p(s)为为CPU访问内访问内存时，所访问的页正好不在内存的概率，这里存时，所访问的页正好不在内存的概率，这里s是是当前进程在内存中的工作集。当前进程在内存中的工作集。显然，在虚存情况下存取一个内存单元的平均时间可显然，在虚存情况下存取一个内存单元的平均时间可描述为描述为T=r+p(s)*t由程序模拟可知，由程序模拟可知，p(s)=ae-bs这里，这里， 0a1b，ae-bsr/p(s) 时才会发生。而时才会发生。而p(s)等于等于ae-bs是一个与工作集是一个与工作集s、参数、参数a和和b有关的概率值。有关的概率值。p(s)是是可以改变的。对于给定的系统来说，可以改变的。对于给定的系统来说，t和和r则是一个则是一个很难改变的数字。显然，解决抖动问题的最关键办很难改变的数字。显然，解决抖动问题的最关键办法是将法是将p(s)减少到使减少到使t=r/p(s)。这只需要。这只需要:(1) 增加增加s，也就是扩大工作集，或是，也就是扩大工作集，或是(2) 改变参数改变参数a和和b，也就是选择不同的淘汰算法以解，也就是选择不同的淘汰算法以解决抖动问题。决抖动问题。在物理系统中，为了防止抖动的产生，在进行淘汰或在物理系统中，为了防止抖动的产生，在进行淘汰或置换时，一般总是把缺页进程锁住，不让其换出，置换时，一般总是把缺页进程锁住，不让其换出，而调入的页或段总是占据那些暂时得不到执行的进而调入的页或段总是占据那些暂时得不到执行的进程所占有的内存区域，从而扩大缺页进程的工作集。程所占有的内存区域，从而扩大缺页进程的工作集。UNIX System 中就是采用的这种方法。中就是采用的这种方法。本本 章章 小小 结结本章介绍了各种常用的内存管理方法，它们是分区式本章介绍了各种常用的内存管理方法，它们是分区式管理、页式管理、段式管理和段页式管理。内存管管理、页式管理、段式管理和段页式管理。内存管理的核心问题是如何解决内存和外存的统一，以及理的核心问题是如何解决内存和外存的统一，以及它们之间的数据交换问题。内存和外存的统一管理它们之间的数据交换问题。内存和外存的统一管理使得内存的利用率得到提高，用户程序不再受内存使得内存的利用率得到提高，用户程序不再受内存可用区大小的限制。与此相关联，内存管理要解决可用区大小的限制。与此相关联，内存管理要解决内存扩充、内存的分配与释放、虚拟地址到内存物内存扩充、内存的分配与释放、虚拟地址到内存物理地址的变换、内存保护与共享、内外存之间数据理地址的变换、内存保护与共享、内外存之间数据交换的控制等问题。交换的控制等问题。图图5.36系统地对几种存储管理方法所提供的功能和所系统地对几种存储管理方法所提供的功能和所需硬件支持作了一个比较。需硬件支持作了一个比较。图图5.36 各种存储方法比较各种存储方法比较习习 题题5.1 存储管理的主要功能是什么？存储管理的主要功能是什么？5.2 什么是虚拟存储器，其特点是什么？什么是虚拟存储器，其特点是什么？5.3 实现地址重定位的方法有哪几类？形式化地描述实现地址重定位的方法有哪几类？形式化地描述动态重定位过程。动态重定位过程。5.4 常用的内存信息保护方法有哪几种？它们各自的常用的内存信息保护方法有哪几种？它们各自的特点是什么？特点是什么？5.5 如果把如果把DOS的执行模式改为保护模式，起码应作的执行模式改为保护模式，起码应作怎样的修改？怎样的修改？5.6 动态分区式管理的常用内存分配算法有哪几种？动态分区式管理的常用内存分配算法有哪几种？比较它们各自的优缺点。比较它们各自的优缺点。5.7 5.2节讨论的分区式管理可以实现虚存吗？如果不节讨论的分区式管理可以实现虚存吗？如果不能，需怎样修改？试设计一个分区式管理实现虚存能，需怎样修改？试设计一个分区式管理实现虚存的程序流程图。如果能，试说明理由。的程序流程图。如果能，试说明理由。5.8 简述什么是覆盖？什么是交换？覆盖和交换的区简述什么是覆盖？什么是交换？覆盖和交换的区别是什么？别是什么？5.9 什么是页式管理？静态页式管理可以实现虚存吗什么是页式管理？静态页式管理可以实现虚存吗？5.10 什么是请求页式管理？试设计和描述一个请求页什么是请求页式管理？试设计和描述一个请求页式管理时的内存页面分配和回收算法（包括缺页处式管理时的内存页面分配和回收算法（包括缺页处理部分理部分)。5.11 请求页式管理中有哪几种常用的页面置换算法？请求页式管理中有哪几种常用的页面置换算法？试比较它们的优缺点。试比较它们的优缺点。5.12 什么是什么是Belady现象？找一个现象？找一个Belady现象的例子。现象的例子。5.13 描述一个包括页面分配与回收、页面置换和存储描述一个包括页面分配与回收、页面置换和存储保护的请求页式存储管理系统。保护的请求页式存储管理系统。5.14 什么是段式管理？它与页式管理有何区别？什么是段式管理？它与页式管理有何区别？5.15 段式管理可以实现虚存吗？如果可以，简述实现段式管理可以实现虚存吗？如果可以，简述实现方法。方法。5.16 为什么要提出段页式管理？它与段式管理及页式为什么要提出段页式管理？它与段式管理及页式管理有何区别？管理有何区别？5.17 为什么说段页式管理时的虚地址仍是二维的？为什么说段页式管理时的虚地址仍是二维的？5.18 段页式管理的主要缺点是什么？有什么改进办法段页式管理的主要缺点是什么？有什么改进办法？5.19 什么是局部性原理？什么是抖动？你有什么办法什么是局部性原理？什么是抖动？你有什么办法减少系统的抖动现象？减少系统的抖动现象？