第4章存储器管理

4.1存储管理的功能

4.2程序的装入和链接

4.3连续分配方式4.4对换4.5基本分页存储管理方式4.6基本分段存储管理方式第四章

存储器管理4.1.1

存储器的层次结构多级存储器结构：寄存器：

容量最小、速度最快高速缓存Cache：

容量远大于寄存器，比主存小两三个数量级内存RAM：

cpu直接从主存储器中取得指令和数据

磁盘：

低速、价廉、容量最大

4.1.2

存储器管理的功能一、地址变换二、内存分配和回收三、内存共享和保护四、内存扩充一、地址变换1.逻辑地址和物理地址逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式其首地址为0，其余指令中的地址都相对于首地址来编址不能用逻辑地址在内存中读取信息物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。用高级语言编程时，要定义变量、函数，程序中有函数调用，有转向等，都是以它们的名字进行的，程序员在一个“名字空间”驾御自己的程序。通常把程序员用的地址空间为名空间。源程序必须经过编译才能执行。程序将被安排成一个从地址0开始的地址空间。这就成为可以执行的目标程序，并存入一个以.exe结尾的文件中。（编译程序不知道以后操作系统将把程序装入何处，只好从0地址开始编址。）目标程序中指令地址都是相对0编址的，使用的是相对地址、逻辑地址。可以执行并不意味着就能执行，还必须由操作系统调入内存才能执行。通常把编译程序形成的从0开始编址的地址空间称为作业的地址空间。(每个可执行程序都有一个自己的地址空间。)逻辑地址(地址空间)示意图2.重定位（地址映射）含义：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址称为地址重定位原因：当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换重定位方式：分为静态重定位和动态重定位

因为多道程序系统中，主存将存放多道作业，而程序员在编写程序时，不可能了解自己的程序将放在主存中何处运行，不可能用绝对地址来编写程序。(1)

静态地址重定位在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作

（2）动态地址重定位在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址.动态重定位依靠硬件地址变换机构完成静态地址重定位示意图0100500mova,(500)2345逻辑地址空间装入程序内存空间mova,(1500)2345100011001500静态重定位静态重定位的优缺点优点：不需要硬件的支持。

缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动，不易实现共享。

+

内存空间

VR

BR…..动态地址重定位动态地址重定位逻辑地址空间动态地址映射的优缺点优点：程序占用的内存空间是动态可变的，可以把程序从某个存储区移到另一个区域一个程序不一定要求占用一个连续的内存空间。可以部分地装入程序运行。便于多个进程共享同一个程序的代码。动态地址重定位的代价：需要硬件的支持。实现存储管理的软件算法较为复杂。4.1.2存储管理功能一、地址变换二、内存分配和回收三、内存共享和保护四、内存扩充为了有效合理地利用内存，设计内存的分配和回收方法时，必须考虑和确定以下几种策略和数据结构：1分配结构：登记内存的使用情况2放置策略：确定调入内存的程序和数据在内存中的位置，即选择内存空闲区的原则3

交换策略：在需要将某个程序段和数据调入内存时如果内存没有足够的空闲区，由交换策略来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。

二、内存分配和回收4调入策略：决定信息装入内存的时机，有两种：在用户请求时调入，称为请调；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为预调

5回收策略：回收时机，以及对所回收的内存空闲区和已存在的内存空闲区的调整4.1.2存储管理功能一、地址变换二、内存分配和回收三、内存共享和保护四、内存扩充三、内存共享和保护内存共享是为了更有效利用内存内存保护是为了保证在内存中的多道程序只能在给定的存储区域内活动并互不产生干扰。包括：防止地址越界防止越权(对共享区有访问权)

最简单、最常用的保护方法是上下界保护法（1）在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址；常用内存保护方法下界寄存器存放程序装入内存后的开始地址（首址）上界寄存器存放程序装入内存后的末地址判别式：下界寄存器≤物理地址＜上界寄存器（2）设置一个寄存器作为基址寄存器，设置另一寄存器作为限长寄存器（指示存储区长度）问：访问作业的逻辑地址分别为2K、10K、20K时是否会越界？4.1.2存储管理功能一、地址变换二、内存分配和回收三、内存共享和保护四、内存扩充四、内存扩充（虚拟存储）通过操作系统利用程序执行的局部性，在内存和外存之间通过不断交换信息，构成一个容量超过内存物理容量的由外存和内存共同组成的虚拟存储器。要实现内存扩充，在程序执行过程中，内存和外存之间必须经常地交换数据。最基本的控制数据流动的方式有：①用户程序自己控制方式，典型的例子是覆盖。②操作系统控制方式，又可进一步分为：交换方式、请调方式、预调入方式。

与实际物理存储器只有一个（单机系统中），且被所有进程共享不一样，每个进程都拥有自己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。若CPU给出的有效地址长度为18位,可以寻址范围为:0--256k;若地址的长度为为20位,则寻址范围为:1024k.库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子24.2

程序的装入和链接图a静态链接，静态装入图b动态链接，动态装入引言：存储器管理方式1连续分配方式：指为一个系统或用户程序分配一个连续的空间，主要有：单一连续区管理方式分区管理方式：通常可分为固定分区方式和可变分区方式2离散分配方式：为了减少因连续分配所产生的碎片，提高内存的利用率产生了离散分配方式，它可将一个用户程序离散地分配到内存中的多个不相连接的区域中。其方式有：分页存储管理方式分段存储管理方式段页式存储管理方式虚拟存储管理方式：为了进一步提高内存利用率，又形成了一种虚拟存储管理方式。其方式有：请求分页管理方式请求分段管理方式请求段页式管理方式4.3连续分配方式

4.3.1单一连续分配内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单用户、单任务的OS。优点：易于管理。缺点：不能充分利用CPU不能充分利用内存（低了内存的利用率）不能充分利用外设实现思想1、地址转换：静态重定位硬件支持：界限寄存器，内容为当前可供用户使用的内存区域的起始地址。绝对地址=逻辑地址+界限寄存器值2、存储保护作业执行时，CPU对每条指令中的绝对地址进行检查。若界限地址≤绝对地址≤内存最大地址则可执行，否则有地址错误，形成“地址越界”中断限定作业在规定的内存区内执行，避免破坏操作系统的信息，达到“存储保护”的目的。3、存储扩充：覆盖技术，使一个大作业能在小的空间中运行固定分区——把主存分成若干个固定大小的存储区。OS20K28K60K124K256K进程A（6K）进程B（25K）进程C（36K）4.3.2固定分区分配

分区说明表基本思想把内存中可分配的用户区预先划分成若干个连续区，每个连续区的大小可以相同，也可以不同（等长或不等长分区）。分区个数固定，每个分区的大小固定

一个分区中装入一个作业，作业在执行过程中不会改变存放区域适用于多道程序设计系统固定分区性能分析在作业大小和出现频率均已知的情况下，固定分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高。但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系统的效率。返回1、动态分区原则：存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。

进程A（8K）进程D（124K）进程B（16K）进程C（64K）…OS进程A进程B进程C进程DOS进程A进程B进程COS进程A进程BOS进程A4.3.3动态分区分配OSA（8K）24K空闲区B（16K）C完成（64K）空闲区D（124K）OSA（8K）8K空闲区B（16K）E（50K）D（124K）14K空闲区F（16K）OSA（8K）8K空闲区空闲区16KE（50K）D（124K）空闲合并124+14=138K进程E（50K）进程F（16K）进入内存进程B（16K）进程D（124K）完成

内存分配变化过程2.

动态分区时的分配与回收（1）使用的数据结构（空闲分区表）

可用表、自由链、请求表（2）常用分区分配算法

①最先适应法：空闲区按地址顺序从小到大登记。依次检查空闲区表目，把第一个找到能容纳申请要求的内存区分配给申请者。

②最佳适应算法：空闲区按其大小递增的顺序组成可用表。把找到的第一个满足要求的空闲区分配。

③最坏适应算法：按空闲区按其大小递减的顺序组成空闲区可用表或自由链，每次分配最大的空闲区。④循环适应算法：每次从上一次查询停止的位置继续向下寻找满足要求的空闲区。最先适应法(first-fit)：该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。最佳适应法(best-fit)：从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。最坏适应法(worst-fit)：基本不留下小空闲分区，但大作业的要求往往难以满足。循环适应法（next-fit）：分区分布均匀，但会缺少较大分区。例：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。（3）分区回收系统回收分区的主要步骤：1检查回收分区是否与空闲区邻接，如邻接则加以合并；2修改说明表碎片问题由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从一个空闲区中切去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。这种不能被任何用户使用的极小的空闲区称为碎片。碎片的出现造成了存储空间的浪费。碎片问题的解决合并（见分区回收）移动(紧凑)通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域，使分散的空闲区集中起来，以容纳新的作业。

紧凑的示意

分区存储管理的优缺点

l

优点：(1)多个程序共享内存，有助于多道程序设计。(2)要求的硬件支持少，管理算法简单，实现容易。l

缺点：(1)内存利用率仍然不高。存在着严重的碎小空闲区(碎片)不能利用的问题，影响了内存的利用率。(2)作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。(3)难以实现各分区间的信息共享

4.4对换对换的引入就是系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。交换技术是利用外存来逻辑地扩充主存对换空间的管理对换区，空闲分区表或分区链，采用连续分配方式，进程的换出和换入换出过程 选择处于阻塞状态且优先级最低的进程作为换出进程，换出后收回内存空间，修改进程的PCB相关信息换入过程 找出“就绪”状态并已经换出的进程，将其中换出时间最久的进程作为换入进程，将其换入直到已无可换入的进程和无可换出的进程4.5基本分页存储管理方式

4.5.1页面与页表

1．内存空间、进程地址空间分页

逻辑页面（页）：将一个进程的地址空间划分成若干个大小相等的区域，称为逻辑页面

物理页面（物理块、页框）：将内存空间划分成与页相同大小的若干个物理块，称为块或页框。页面的大小应选择适中，通常是2的幂，例512B～8KB。

在为进程分配内存时，将进程中的若干页分别装入多个不相邻接的块中。2．地址结构分页地址中的地址结构如下：

它含有两部分：前一部分为页号P，后一部分为位移量W(或称为页内地址)。图中的地址长度为32位，其中0～11位为页内地址，即每页的大小为4KB；12～31位为页号，地址空间最多允许有1M页。

若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址w可按下式求得：

P=int(A/L)

W=A%L其中，int是取整函数，%是取余运算。例：系统页面大小为１KB，设A＝1201B，则P=？,W=？（0,1201）

3．页表系统为每个进程建立一张页面映射表，简称页表。页表保存于内存。每个逻辑页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射页表的作用

作业2(0页)操作系统作业2(1页)作业3(0页)作业1(0页)作业1(1页)作业2(2页)051601224708作业1作业2作业31KB2KB001KB2KB03KB1KB0逻辑地址空间页表物理地址空间页号块号1KB2KB3KB4KB5KB6KB7KB8KB9KB10KB分页存储管理基本原理等分主存：把主存划分成相同大小的存储块。用户逻辑地址空间的分页：逻辑地址空间划分成与物理页大小相同的部分。逻辑地址的表示：虚拟地址A=>（p,d）, p--页面号；d--相对地址（页内地址） 页面大小L，则p=int(A/L)；d=A%L主存分配原则：系统以物理页为单位把主存分给作业或进程，并且分给一个作业或进程的物理页不一定是相邻和连续的。4.5.2地址变换机构1．基本的地址变换机构

1)基本任务：利用页表把程序中的逻辑地址变换成物理地址。2)硬件支持：在系统中设置页表寄存器，用来存放页表的始址和页表的长度。（其值来源于进程的PCB）3)地址映射过程：首先系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理块号。与此同时，将逻辑地址中的页内地址与得到的物理块号一起形成实际物理地址分页系统的地址变换机构

例1：作业地址空间共有7个页，每页的相对地址为0~1023，1024~2047，2048~3071，…，6144~6150。其对应的主存块在页表中已列出。分别为5，7，9，15，13，10，16共7块。假定页表在主存始址为500。若该程序从第0页开始运行，且现程序计数器内容为：练习14.……..109…0硬件动态地址转换机构工作如下：

1、把该作业的页表始址（500）和页表长度（7）放入控制寄存器中。2、将程序计数器内容的页号部分（0）与控制寄存器中的页表长度（7）相比较，若页号<页表长度时转3，否则产生地址越界，终止程序运行。

3、按控制寄存器中的页表始址找到页表，在页表中查逻辑页对应的物理页号（5）

4、把主存块号5与程序计数器中的页内位移相拼接，从而得到该操作所在主存的物理地址：5×1024+100=5220

5、按地址5220访问内存，完成指定操作。练习解答例2：已知某分页系统，主存容量为64k，页面大小为1k，对一个4页大的作业，第0、1、2、3页被分配到内存的2、4、6、7块中。求：将十进制的逻辑地址1023、2500、4500转换成物理地址。解:(1)1023/1K，得到页号为0，页内地址1023。又对应的物理块号为2，故物理地址为2*1k+1023=3071(2)2500/1K，得到页号为2，页内地址452。又对应的物理块号为6，故物理地址为6*1k+452=6596(3)4500/1K，得到页号为4，页内地址404。因为页号不小于页表长度，故产生越界中断。若页的大小为4K，则地址转换机构将逻辑地址0转换成的物理地址为＿＿＿。在一个页式存储管理系统中，页表内容如下所示：

复习：

2．具有快表的地址变换机构

“两次访内”问题:CPU存取一个数据，需两次访问内存。第1次访存取物理块号、第2次取数。使计算机的处理速度降低近1/2。解决方法：增设“快表”一组高速缓冲存储器，称为“联想存储器”或“快表”，用以存放当前访问的那些页表项

引入快表的性能分析

引入快表之后的地址变换过程引入快表的性能分析假定访问主存的时间为200ns，访问高速缓冲存储器的时间为40ns，假设查快表的命中率为90%。将逻辑地址转换成实际物理地址进行存取的平均访问时间为：

（200+40）*90%+（200+200）*10%=256（ns）。不使用快表需两次访问主存的时间：200*2=400ns。可见使用快表与不使用快表相比，访问时间下降了36%。引入“快表”后的地址变换过程

在CPU给出有效地址后，地址变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中。若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；若在快表中未找到对应的页表项，则需再访问内存中的页表，找到后，把从页表中读出的页表项存入快表，以取代一个旧的页表项。具有快表的地址变换机构

4.5.3两级和多级页表解决大页表占用大的连续存储空间的问题CPU具有32位地址时,使用232逻辑地址空间的分页系统,规定页面4KB时,每个进程页表的表项有1M个,若表项占用4个字节,则每个进程需要占用4MB连续内存空间存放页表多级页表概念：页表也进行分页，内存仅存放当前使用的页表,暂时不用部分放在磁盘上,待用到时再调入具体做法：把整个页表进行分页,分成一张张小页表(称为页表页),小页表的大小与页框相同，为进行索引查找,应该为这些小页表建一张页目录表基本分页存储管理 为离散分配的页表再建一张页表，称为：外层页表或页目录表外层页表页表增设外层页表寄存器，存放外层页表的始址外层页号 外层页内地址 页内地址31222112110两级页表结构

两级页表的地址变换机构 二级页表地址变换需三次访问主存：一次访问页目录、一次访问页表页、一次访问指令或数据，访问时间加了两倍外层页号 外层页内地址 页内地址外部页表寄存器＋＋外部页表 页表 物理地址2．多级页表对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，采用两级页表是否仍可适用的问题，须做以下简单分析。如果页面大小仍采用4KB即212B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。

4.5基本分页存储管理方式4.5.4反置页表一、反置页表

用反置页表，为每一个物理页设一个表项，表项中放进程号和页号，系统只维护一张反置页表。由于物理存储空间小于逻辑存储空间，所以使用反置页表减少了页表占用的内存空间。二、反置页表的寻址逻辑地址=进程号+页号+页内偏移地址寻址过程：根据进程号和页号找到物理块号物理地址=物理块首址+页内偏移地址

基本分页的特点优点：存在页内碎片，但碎片相对较小，内存利用率较高实现了离散分配，消除了程序浮动；缺点：需要专门的硬件支持，尤其“快表”；内存访问的效率下降。页式：按内存物理页大小将进程空间分页（用户不可见），内存空间等长段式:

按程序逻辑结构将进程空间分段（用户可见），内存空间不等长4.6基本分段存储管理方式基本分段管理思想的引入基本原理地址变换分段与分页的主要区别段页式存储管理方式4.6基本分段存储管理方式

4.6.1分段存储管理方式的引入1)方便编程通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并有自己的名字和长度。因此，希望要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。例如，下述的两条指令便是使用段名和段内地址：LOADl，[A]|〈D〉；STORE1，[B]|〈C〉；其中，前一条指令的含义是将分段A中D单元内的值读入寄存器1；后一条指令的含义是将寄存器1的内容存入B分段的C单元中。

2)信息共享:共享的实现以是信息的逻辑单位为基础

3)信息保护4)动态增长5)动态链接4.6.2分段系统的基本原理1.分段

一个用户程序可划分为若干段（如一个主程序、一个或几个子程序、数据段等），每个段在逻辑上是完整的（是一个独立的功能模块），都有自己的名字，且都有一段连续的地址空间。地址组成：段号段内地址3116150例：01kCALL[X]|<Y>LOADL,[A]|6STOREL,[B]|<C>分段MAIN(主程)Y:

0640分段X（子程）6：

分段A（数组）05000300分段B2．段表

在系统中为每个进程建立一张段映射表，简称为“段表”。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射。(1)段长(或称段的容量)。该段的长度，即其字节数，在虚存和实存中段长是一样的。(2)主存起始地址。该段装入主存内的起始地址。(3)存取控制权限。为了实现段的保护，规定各段的存取权限。例如，执行E：执行一个程序或子程序，不允许读或写；读R：允许读，不允许写或执行；写W：允许写，不允许读或执行。除此之外，还可以是上述三种权限的组合，当存取要求违反了段的存取权限，则发生保护中断。利用段表实现地址映射

(main)=030k(x)=120k(D)=215k040k80k120k

3．地址变换机构

段表寄存器:用于存放段表始址和段表长度。

越界访问控制:逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较。

分段系统的地址变换过程

段表始址段表长度（4）段表寄存器≤153705物理地址段号3105逻辑地址越界中断段表基址段长150K35K500K9K300K20K100K42K3210段号内存150*1024=153600153600+105=153705练习：对于如下所示的段表，请将逻辑地址（0，137），（1，4000），（2，3600），（5，230）转换成物理地址。解:(1)段号0<段表长，且137<段长10k，故段号、段内地址全部合法。得物理地址为50k+137=51337解:(2)段号1<段表长，段号合法。4000>段长3k，因此产生越界中断。解:(3)段号2<段表长，且3600<段长5k，故段号、段内地址全部合法。得物理地址为70k+3600=75280解:(4)段号5＝段表长，故段号不合法。产生越界中断。

4．分页和分段的主要区别由上所述不难看出，分页和分段系统有许多相似之处。比如，两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，主要表现在下述三个方面。(1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。(2)页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。(3)分页的