第五章存储管理

第五章存储管理存储管理的目的：1、为用户使用存储器提供方便。使用户使用计算机的过程不考虑存储器的申请、分配、保存、回收等问题，体现在以下方面：（1）每个用户均以独立方式编成，而不必关心其程序在存储空间上的物理位置；（2）为用户提供充分大的内存空间。2、充分发挥内存的利用率：既要为用户程序分配足够大的内存空间，又不至于浪费。3、扩充内存容量的方法：物理扩充与逻辑扩充4、信息保护：市内存中的数据不被非法修改。5.1存储管理的功能一、虚拟存储器基本思想：利用大容量的外存空间来逻辑扩充内存，使得产生一个不受实际内存容量大小限制的逻辑的虚拟存储器，以便充分发挥内存利用率，使系统有效地支持多道程序的并发执行以及解除对用户作业大小的限制。

1、虚拟存储器实现的可能性（1）现代计算机系统的物理存储器分成内存和外存。因内存价格昂贵，不可能用大容量的内存来存储所有被访问的或暂时不被访问的程序和数据，而外存价格低，适于存储大量的信息。（2）程序执行的局部性原理（3）编译、链接通常由用户编写的源程序，首先要有编译程序编译成可执行代码，然后，由链接程序把一个进程的不同程序段连接起来以完成要求的功能。显然，对于不同的程序段，应具有不同的地址。

a、物理地址：物理存储器中存储单元的编号。优点：速度快；缺点：影响并发执行的进程数；大进程无法运行。

b、编译链接程序将用户进程编译链接到一个以0位始址的线性或多维地址空间。静态链接：在程序执行前由链接程序对进程所含目标代码进行连接；动态链接：在程序执行过程中根据需要而进行的连接。虚拟存储器（P106第一行）：将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。虚拟地址（逻辑地址）物理地址（4）地址变换：由逻辑地址向物理地址的转换过程。二、地址变换(P106)

内存空间（物理地址空间）：内存地址的集合。虚拟空间的划分：使编译链接程序可以把不同的程序模块连接到一个统一的虚拟空间。地址重定位：把虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存地址的过程叫地址重定位或地址映射。1、静态地址重定位（P107）(1)方法：是在虚拟空间中程序执行之前由OS的重定位装入程序完成地址映射工作。(2)特点：优点：不需要硬件支持缺点：①使用静态重定位法进行地址变换无法实现虚拟存贮器，因静态重定位将程序一旦装入内存之后不能再移动，并且必须在程序执行之前将有关部分全部装入。②进程必须占用连续的内存空间，难实现数据共享。2、动态地址重定位：（1）方法：在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址变成内存地址，动态重定位依靠硬件地址变换机构完成。（2）动态地址重定位机构基地址寄存器BR（始址）、虚地址寄存器

VR偏移）则：内存地址MAMA=（BR）+（VR）（3）址映射过程：①设置基地址寄存器BR，虚地址寄存器VR②将程序段装入内存，将其占用的区域的首地址送BR；③在程序执行过程中，将要访问的虚地址送入VR中；④地址变换机构把VR和BR的内容相加，得访问的物理地址（4）动态重定位优点：①可以对内存进行非连续分配②动态重定位提供了实现虚拟存贮器的基础③有利于程序段共享三、内外存数据传输的控制(P108)（1）把即将执行的程序和数据段调入内存；（2）把处于等待状态的程序、数据段调出内存，为此目的，有两种方法实现内存与外存间的控制即覆盖与交换。1、覆盖（overlay）：由用户程序自己控制内外存之间的数据交换，它要求用户清楚了解程序的结构，并指定各程序段调入内存的先后次序。2、交换（swapping）：包括换进与换出，它是指由操作系统把那些在内存中处于等待状态的进程换出内存，以及把那些等待事件已经发生，处于就绪态的进程换入内存，以及那些即将执行的程序数据调入内存。3、请求调入方式：在程序执行时，如访问的程序段或数据段不在内存中，则操作系统自动地从外存将有关程序、数据调入内存。4、预调入方式：由OS预测在不远的将来会访问到的那些程序、数据部分，并在他们被访问之前由系统选择适当的时机将它们调入内存的方法。5、区分交换与覆盖：（1）交换不需要程序员给出程序、数据段的交换方法、过程，而覆盖要求明确给出程序段之间的覆盖结构（2）交换主要是在进程之间进行，而覆盖主要是在一个进程内或一个作业内进行，同时覆盖程序段与被覆盖程序段是无关的。6、

区分请求式调入与预调入（1）二者一般是在一个进程内的不同程序段、数据段间进行；（2）请求式调入命中率为100%，但程序执行速度慢，预调方式命中率≤100%四、内存分配与回收1、任务：存贮管理模块为每一个并发执行的进程分配内存空间，另外，当进程执行结束后，存贮管理模块又要及时回收该进程所使用的内存资源，以便给其他进程分配本内存。2、设计内存分配和回收方法时，要考虑的策略及数据结构如下：（1）分配结构：空闲区表、空闲区队列（链）（2）放置策略：选择空闲区方法（3）交换策略（4）调入策略（5）回收策略五、内存信息的共享和保护内存信息共享内存保护常用的内存信息保护方式：1、

上下界保护法：方法：为每个进程设置一对上下界寄存器，存贮被保护程序和数据段的起始地址和终止地址。程序执行过程中，在对内存进行访问操作时进行地址合法性检查，即检查经过重定位后的内存地址是否在上下界寄存器所规定范围内。若在规定范围内，则访问是合法的。否则是非法的，并产生访地越界中断。2、保护键法：方法：为每一个被保护存贮块分配一个单独的保护键。在程序状态字中设置相应的保护键开关字段，对不同进程赋予不同的开关代码，与保护的存贮块中的保护键匹配，保护键可设置成对RW同时进行保护或只对R、W进行单独保护的。如果开关字与保护键匹配或存贮块未受到保护，则访问该存贮块是允许的，否则产生访问出错中断。3、界限寄存器与CPU的用户态或核态工作方式相结合的保护方式，在这种方式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存区域。内存空间：由若干存储单元组成的，每个存贮单元有一编号，这一编号可唯一标识一个存贮单元，称内存地址。逻辑空间：源程序经过汇编或编译后，形成目标程序，每个目标程序均以0为基址顺序进行编址，原来用符号名访问的单元用数据——单元号取代，这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间。

5.2分区存贮管理一、分区管理的基本原理：给内存中的每一个进程划分一块适当大小的存贮区，以连续存放各进程的程序与数据，使各进程得以并发执行。1、固定分区法：（也称静态分区管理）（1）方法：将内存区域固定地划分为若干大小不等的区域，分区划分的原则由系统操作员或OS决定。（2）数据结构——PPT（partitiondescribetable)

分区说明表（3）特点每个分区在表中对应一个表目（行），表目内容包括区号、大小、起始地址，使用状态等。2、

动态分区法：（可变分区管理）（1）方法：作业执行前不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变，（2）数据结构：（分区说明表）(P112)①可用表②自由表③请求表二、分区的分配与回收：1、

固定分区时的分配与回收、（1）分配：当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小，存贮管理程序根据请求查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。分配算法如图5.102、

动态分区的分配与回收（1）动态分配与回收要解决以下三个问题：①对于请求表中的要求内存长度，从可用分区表或自链中寻找出合适的空闲区进行分配。②分配空闲区之后，更新可用表或自由链。③进程或作业释放内存资源时，各相邻的空闲区进行链接合并，更新可用分区表或自由链。（2）常用的三种分配算法：

A、

最先适应算法：（FFA）

①可用分区表或自由链的组织：按起始地址递增的次序将可用分区或自由链排列起来。②分配：从头搜索可用分区表或自由链，一旦找到大于或等于所要求内存长度的分区，则结束搜索。然后从所找到的分区中划出所要求的内存长度分配给用户进程，并把余下的部分（进行合并后）留在可用表中。③特点：内存利用率低，易产生碎片算法实现简单，速度快。

B、最佳适应算法：①可用分区组织：按空闲分区的从小到大次序组织可用分区表或自由链。②分配：当用户作业或进程申请一个空闲分区时，存贮管理程序从表头开始查找，当找到第一个满足要求的时，停止查找，如果该分区长度大于请

求表中的请求长度，则将减去请求长度后的剩余空闲区部分留在可用表中③特点：优点：自由分区表或可用链中尾部的空闲区容量大，便于大服务业运行。缺点：更容易形成碎片。

C、最坏适应算法：（MF）①空闲分区组织：按空闲分区容量从大到小次序组织可用表或自由键。②分配：当用户作业或进程请求一个空闲区时，先检查可用分区表或自由链的第一个空闲区的大小是否大于或等于所要求内存长度，若第一个的长度小于分配请求，则分配失败，否则从空闲区可用分区表或自由链中分配相应的存贮空间给用户，然后修改和调整空闲区可用表或自由键。③特点：优——不易产生碎片

缺——大作业往往无法运行。3、动态分区时的回收与拼接可用分区拼接(P114)图5.12(四种情形)

4、几种分配算法的比较：从查找速度，释放速度、空闲区利用三方面进行比较（1）最先适应算法：搜索速度，回收速度快，同时尽可能地利用了低地址空闲，保证了高地址端有较大的空闲区来放置要求内存较多的进程作业。（2）最佳适应算法：找到的空闲区最佳（3）最坏适应算法：克服了碎片问题，但大作业往往无法运行。三、有关分区管理其他问题的讨论：1、关于虚存的讨论：在分区管理中，每个用户进程所需内存容量是受分区大小限制的2、关于内存扩充所谓内存扩充，是指通过覆盖或交换技术来扩充内存。3、关于地址变换和内存保护。地址变换分：静态地址重定位动态地址重定位内存保护4、

分区存贮管理的主要优缺点：（1）优点：①实现了多个服务业或进程对内存的共享，有助于多道程序设计，从而提高了系统资源的利用率②该方法要求的硬件支持少，管理算法简单（2）缺点：①内存利用率仍然不高②作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。③难以实现各分区间的信息共享。

5.3覆盖与交换技术

一、覆盖技术1、

概念：所谓覆盖，指一内存区可以被不同的程序段重复使用，当某一程序段不再需要时，另一程序段可以占用它的位置，把可以在其上进行覆盖的内存区域称为“覆盖区”，而可以相互覆盖的程序为“覆盖”。2、基本思想：①程序的执行具有局部性特征程序在CPU上执行，在一个绝对时刻，CPU只能执行一条指令，在一个相对较短的时间段内，又只有一个和谐段被执行。②程序的划分：

由于程序的执行具有局部性特征，因此在程序执行前没有必要将程序全部加载到内存，而且只装入一个或若干个程序段。为此，需将程序进行划分，将那些不会同时执行的程序段共享同一内存区①程序段的执行与覆盖：当内存中的程序段执行结束，再将外存中它的后键程序段加载内存，原来的程序段被覆盖。3、覆盖的实现要求：（1）要求程序员提供一个清楚的覆盖结构，搞清楚程序应分为多少段，每段的前起后键各是什么。（2）要求程序员清楚了解程序所属进程的虚拟空间以及各程序段所在虚拟空间位置。（3）要求程序员了解系统和内存的内部结构和地址划分情况4、例（备课本）二、交换技术：1、概念：交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。2、引入交换原因：多道程序系统中，同时执行好几个作业或进程，但是同时存在于内存中的作业或进程，有的处于执行状态或变绪状态，而有的则于等待状态，一般来说，等待较长，如果让处于等待状态的进程继续驻留内存，将会造成存储空间浪费，因此，应把处于等待态进程换出内存。3、交换与覆盖区别：①交换不需要程序员给出程序段之间的覆盖结构，而覆盖要求明确给是等程序段之间的覆盖结构。②交换是进程之间或作业之间进行，而覆盖主要在同一作业内来进程内进行内。同时覆盖程度段与被覆盖程序段之间是无关的。

5.4分页管理分区管理的缺陷：系统对于每个存储要求，都分配一片连续的内存空间，导致碎片的产生和内存利用率不高。一、实现原理1、作业（进程）空间的划分：（1）系统将作业（进程）地址空间分成一些大小相等的块，每一块称为一个页，叫逻辑页。长度为1KB-4KB.（2）例：如作业被分成L页，编号为1,2,3,…,L-1，每一个自然数叫页号或逻辑页号，其逻辑地址由页号和页内偏移地址确定；表示成序偶（p,d）即：

2、内存空间的划分：将内存空间分成大小可与逻辑页相等的若干块，每块叫内存块（物理页）。设内存总容量为2S，页长为2r，则内存页数目为2s-r=m，从低地址开始编号为0,1,2,…,m-1，其中每一个整数叫物理页号。物理地址=块号x页长+偏移3、作业空间与内存空间的关系（1）页表:当作业（进程）运行时，先将其各逻辑页加载道内存的物理页中，作业（进程）的所有逻辑页号是连续的，而该进程获得的物理页号是不连续的，为此需要建立一个数据结构——页表，反映逻辑页与物力页间的对应关系。pd逻辑地址=px页长+d逻辑页号物理页号（2）页表控制寄存器：包括页表基地址和页表长度，有的系统建立一个总页表。二、地址映射（1）指令本身得到逻辑地址，分离出逻辑页号L和页内地址b；（2）将L与长度寄存器值m比较，若0<=L<=m，则从始址寄存器取得页表始址，找到与L相应的物理页号L；若L不满足0<=L<=m，则发出越界访问错误信息；（3）由物理页号L与b进行地址合成，得到逻辑地址所指示的物理单元；（4）进行操作，取指令；（5）转（1）。三、快表进程标志页表始址长度（1）目的：提高地址映射速度；（2）设快表的方法：设置一组寄存器，用以存储当前进程的页表的一部分，这样有效地避免地址映射过程中频繁地访问内存中的页表。（3）快表的组成：

a、一个快表通常含8-16个寄存器。

b、每个寄存器组存储页表的一个表目，包括逻辑页号、物理页号、访问值和状态四项，前两项由页表直接取得，状态项表示该表目是否空表目，访问值表示该页表当前被访问的频率获该表目建立的次序，的便于置换快表的表目。四、引入快表之后的地址映射过程：（1）指令产生逻辑地址L,b；（2）由逻辑页号l查页表的物理页页号l；

如找不到，则：

a、由逻辑页号l和页表长度寄存器中的内容m比较，判断是否满足0<=l<=m，如不满足则产生越界错误；

b、如满足0<=l<=m，由逻辑页号l和页表首址寄存器内容查页表的物理页号L，将逻辑页号l和物理页号L一起置于快表中，若此时快表已满，则淘汰一个；

c、转步骤(2)。（3）由物理页号L和页内地址b合成的物理地址。五、数据结构、存储分配：1、内存分块（页）表MBT

整个系统一个，用于记录所有内存快的使用情况，表目数等于内存块总数，各内存块按序对应一个表目，表目号即块号。

2、页表PMT

每个用户进程一个，用以记录进程实体的地址空间与内存空间之间的对应关系，地址空间中的各内存块号状态

占用者名

……

……

……页按序对应表目中的一个表目，表目号等于逻辑页号，表长等于逻辑页总数。3、计数变量freeblocks：记录当前空闲块数目。4、存储块分页算法（略）六、关于碎片一个作业占有的各块除最后一块外均不存在碎片，最后一块存在碎片，小于块长。

5.5分段管理与段页式管理

一、分段管理（一）分段的引入1、分页管理的优点：实现了内存分配的非连续性，解决了碎片问题，从而大大提高了内存利用率。

缺点：对作业或进城实体的分页不是按其内部的逻辑结构和关系；一页中的内容通常不是完整的程序和数据逻辑段，导致一个逻辑段可能被分成若干页，不通逻辑段也可能在同一个页内，这使程序段或数据段的共享、保护变得困难。

2、引入：为了解决页式存储管理中共享数据和程序段的困难，引入一种以作业（进程）逻辑段为单位分配内存的方法，这就是分段管理。（二）实现原理：1、思想：把作业（进程）按内容或过程（函数）关系分成段，每段叫做逻辑段，每段有其段名，在分配内存时，以逻辑段为单位分配。2、实现：（1）内存空间的划分：内存空间被动态地分成若干长度不等的区域，每个区域等于相应程序段长度，叫物理段。物理地址：每个物理段中存储单元地址由两个值决定，即段首址和段内偏移。物理地址=段首址+段内偏移=（2）进程空间的划分：

进程空间被静态地划分成长度不等的区域，每个区域为一个逻辑段，它是具有一定功能和结构的相对独立的程序单位。

逻辑地址：源程序经过编译后的地址，由段号和段内偏移量组成。

段名：每个逻辑段有一个符号名称，用以标志该段。段首址段内偏移段号：将一个作业（进程）的所有逻辑段从0开始编号，这个自然数叫段号。（3）进程空间与内存空间的对应关系：

进程的一个逻辑段与内存中的一个物理段相对应，一个进程的多个逻辑段可存于内存中若干部相连的物理段中。（4）所需表目

A、段表：用于记录一个进程各段在内存的起始地址和长度，从而反映逻辑空间与物理空间的关系。

逻辑段号

内存始址

长度

B、段表控制寄存器（一个系统一个该表）

①物理段始址寄存器

②段长度寄存器

C、进程表：用于记录个进程段表始址及长度，位于

OS空间。

D、空闲表：用于记录内存中空闲的物理区域，便于进行内存分配。

进程标识

段表始址

表长度始址

长度

E、一组联想寄存器——快表

用于保存正在运行的进程段表的一部分（投影）。（5）

地址映射：①指令产生逻辑地址（段号S、段内偏移量lad）；②由段号查快表得到段首址、段长；

若找不到，则：

a、由段号S与段表长度寄存器内容l进行比较，是否满足0<=S<=l，如不满足则越界；

b、由段号及段表首址寄存器内容查内存中的段表，得到段号S对应的物理段始址和长度，将首址和长度写入快表（可能存在淘汰）

c、转②③由段内地址lad和长度leng比较，是否满足

0<=lad<=leng，如不满足则越界。④由段首址与段内地址相加得物理地址。（三）

分段与分页的共享：1、分段的共享：

为了实现不同进程对内存中同一物理段的共享，方法是通过它的段表来实现，一两个进程共享一段为例：设甲进程的段号Si，乙进程的段号为Sj，若Si、

Sj对应同一个物理段的始址和长度，则甲乙两进程实现对该物理段的共享。2、分页的共享：与分段的共享相同，即让一个进程的一个逻辑页号Pi与另一个进程的逻辑页号Pj对应同一个物理页号

PP，则实现了两个进程对PP的共享。二、段页式管理（一）基本原理：1、思想：用分段向用户提供二维的编程空间，以方便用户编程，利用分页来管理内存空间，以提高内存的利用率。2、实现：（1）内存空间的划分：

内存空间被静态地划分成若干长度相等的区域，每个区域长为2i，称为一个物理页面。

（2）进程空间的划分：与段页式存储管理相同，进程空间被静态地划分为长度不等的区域——逻辑段，与页式存储相同，在进行进程存储管理时，每段空间被静态地分成若干长度若干长度为2i的区域，每个区域称为一个逻辑页面。逻辑地址：

（3）内存空间与进程空间之间的对应关系：段号

逻辑页号

页内地址进程空间的一个逻辑页面对应内存空间的一个物理页面，同一段的逻辑页面是连续的，而对应的物理页面是不连续的。（如图所示：备课本）（4）所需表目：

A、段表：每个进程一个，用于记录进程各段的页表始址和页表长度；B、页表：此表每个段一个，用于记录段中各逻辑页与物理页号之间的对应关系；C、进程表：用于记录各进程段表的首址及长度，一个系统。D、空闲表：用于记录内存页中空闲页情况。（5）所需寄存器：

A、段表首址寄存器B、段表长度寄存器C、快表（6）地址映射

A、由指令产生逻辑地址，包括段号s、逻辑页号lp、页内偏移lad；B、由段号s和逻辑页号查快表得物理页号，如果找不到：

a、由段号和页表长度寄存器中的内容l进行比较，判断是否满足0<=s<=l，如果不满足则越界，产生中断；b、由段号和段表始址寄存器内容查段表得页表首址和页表长度；c、由逻辑页号lp与页表长度l’相比较，判断0<=lp<=l’,如不满足则越界，产生中断；d、由逻辑页号与页表首址查对应的物理页号；e、将段号、逻辑页号和物理页号合在一起送入快表；

f、转b；C、由物理页号和页内地址合成为物理地址。（二）特点1、优点：（1）方便用户、使用户对进程在内存中的映射可见；（2）内存利用率高，克服了碎片问题。2、缺点：方法复杂，软件、硬件开销大。

动态页式存储管理（P122）(虚拟页式存储管理)一、类型：1、请求页式存储管理：进程执行前只让程序、数据的一部分内容进入内存，其他部分则在执行过程中动态调入，当访问某条指令时发现它在外存而不在内存，则发生缺页中断，系统将外存中相应的页面调入内存。2、预调入方式：在缺页中断发生之前，事先调入处于外存中的还未被访问的页面。二、问题：为了实现虚拟存储管理，需要解决以下问题：1、页表的改进2、置换算法的选择：当内存中无空闲页面时，把调入的页放在什么地方。三、请求页式管理中的置换算法1、随机淘汰算法2、轮转法和FIFO

特点：内存利用率不高；缺页中断率高，有时甚至产生Belady现象。

页号

页面号

中段位外存地址改变位（1）Belady现象：是一种异常现象，由于缺页中断发生时，置换算法的不合理及程序执行顺序的随机性，呆滞给进程分配的内存页面越多，而缺页中断不但不降低反而升高的现象。例1、例2、（见备课本）3、最近最久未使用页面淘汰算法（P126