第六章主存管理

研究三方面的问题：

取（fetch）

放（placement）

替换（replacement）请调、预调连续、非连续第六章存储器管理第六章存储器管理6.1主存管理功能6.2程序的装入和链接6.3连续分配主存管理方式6.4覆盖和对换技术6.5分页存储器管理方式6.6分段存储管理方式6.7段页式存储管理方式主存分配地址转换和重定位存储保护和主存共享存储扩充（虚拟存储技术）6.1主存管理功能6.2程序的装入和链接

1.程序的装入绝对装入方式静态重定位装入方式动态运行时装入方式源程序目标模块装入模块编译链接装入内存图示如下：JUMP1424LOAD22241024142422240LOAD1，250036510002500500010000LOAD1,125003651100012500015000绝对装入方式静态重定位装入方式JUMP1424LOAD2224102414242224静态重定位装入：在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。这种转换工作是在作业开始前集中完成的，在作业执行过程中无需再进行地址转换。所以称为“静态重定位”。（1）静态链接2.程序的链接

程序的连接方式有三种：静态链接、装入时动态链接和运行时链接。CallB模块B模块C0L-10M-10N-1JSR“L”模块B模块C0L-1LL+M-1L+ML+M+N-1链接目标模块装入模块如：CALLB

JSR”L”需要解决的问题：相对地址的修改；外部调用符号的变换（2）装入时动态链接

目标模块在装入内存的过程中链接，即边装入边链接。优点：便于修改和更新便于实现目标模块的共享6.2程序的装入和链接（3）运行时动态链接将某些目标模块的链接延迟到运行该模块时才进行。即采用部分装入运行方式。优点：节省内存空间便于实现目标模块的共享连续分配方式是指为一个用户程序分配一个连续的内存空间。分为：单一连续分配、固定分区分配、动态分区分配和动态重定位分区分配四种方式。1.单一（单道）连续分配方式主存系统区用户区6.3连续分配主存管理方式内存空间安排特点：任一时刻内存只有一道作业，该作业连续存放于内存中。只适合单用户、单任务环境。操作系统用户程序0aa+1n界地址寄存器6.3连续分配的主存管理方式界地址寄存器主存A>a?cputruefalse地址A终止程序运行越界检查机构：用户程序每访问一次主存，越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止其执行。（1）分区划分方法分区大小相等分区大小不相等2.（多道）固定分区分配管理方式分区号大小始地址状态11530已分配23065未分配3100125已分配（2）分配方法

数据结构：存储分块表MBT（如下表）特点：分区数和分区大小固定。优点：简单、易实现。缺点：存在内部碎片，主存利用率不高。上下界寄存器和地址检查机构。当作业被调度运行时，作业在内存中的上下界地址寄存器限定的地址范围内。每次内存访问时，地址检查机构作越界检查。作业程序是绝对地址或静态重定位装入。CPU主存下界寄存器上界寄存器><TrueTrue地址AF F程序性中断（3）地址访问保护有两种方式：基址寄存器、长度寄存器和动态地址转换机构。当作业被调度运行时，将作业所占内存基址及长度送基址、长度寄存器，每次内存访问时，先看访问地址是否小于长度，然后+基址进行访存。用户程序代码是可动态浮动的。CPU主存基地址寄存器长度寄存器<+True地址AF 程序性中断所谓程序浮动是指程序可以随机地从主存的一个区域移动到另一个区域，程序被移动后仍不影响它的执行。若作业执行时，被改变的有效区域依然能正确执行，则称程序是可浮动的。（4）存储碎片

OS12k4k3K内部碎片OS4k6k12k作业长度：5K、8K、12K外部碎片内部碎片：存在于一个存储分区内，当内存某存储区大于其存放作业空间而剩下的那部分存储空间。

外部碎片：通常指一个暂时不能使用的存储分区。当内存某存储分区容不下要运行的作业时发生。3.可变分区多道管理技术（1）概念主存事先并未划分成一个个分区，当作业进入主存时，按作业的实际大小建立和分配分区。（2）特点分区数可变分区大小不固定可能存在大小不等的外部碎片例：假设任一时间段内，内存中每一作业的运行时间相等。作业到来次序所需存储量运行时间160102100533020470855015OS040256J1J2J3J4J53.可变分区多道管理技术（3）数据结构常用的数据结构有以下两种：存储分块表空闲分区表或空闲分区链3.可变分区多道管理技术分区号大小始地址115K30K1040K253K3100K125K………空闲分区表分区号大小始地址514K30K924K65K642K100K………已使用分区表存储分块表（表的维护较困难，存在表格碎片）已使用分区表UBT（分区状态为忙）空闲分区表FBT（分区状态为可用）06K28k8K4k20K28k4k18k头指针8KB20KB6KB18k已分配未分配空闲分区链（单向链）指向下一个分区的指针分区大小空闲分区链（双向链）前向指针后向指针N+2N+2N个可用字节表示分区的大小00表示分区的状态1）首次适应算法以空闲分区链为例，每次从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。（一般要求空闲分区链以某种顺序链接，如地址递增。）通常有三种分配算法：（4）存储分配算法缺点：低地址端留下许多很小的、难以利用的空闲分区。运行一段时间后，使得查找的开销增加。优点：内存的高地址端保留了较大的空间。首次适应算法的内存分配过程从空闲分区表的开始或空闲分区链的链首查找。置空闲分区号F=1空闲分区表（链）检索完？F.size≥Xk?F.size-Xk≤size?F=F+1

从分区中划出Xk大小的分区

修改空闲分区表和已使用分区表返回失败返回noyes

将分区分配给请求的进程yesnoyesnosize为事先规定不再划分的剩余分区的大小。当前进程申请一Xk大小的内存分区2）循环首次适应算法

设置查找指针，每次分配内存时，从查找指针开始查找空闲分区表或空闲分区链。优点：内存的空闲分区利用均匀（4）存储分配算法3）最佳适应算法

将满足需求的最小空闲分区分配给请求内存分配的进程。（一般要求空闲分区按由小到大的顺序排列）缺点：将在内存中留下许多碎片(内部碎片)。4）最坏适应算法在所有未分配的分区中挑选最大的，且满足作业主存要求的分区分配给当前作业。（4）存储分配算法优点：能使分配后的剩余分区足够大，内部碎片减少缺点：运行一段时间后，难以找到用户程序需要的较大空闲分区。（5）基本操作主要的操作有：分配内存和回收内存。

1）分配内存选择一种分配算法将满足条件的内存分区分配给当前申请的进程。2）内存回收待回收的分区可能存在的情况有以下四种：回收区不与任何空闲分区邻（如图（1））回收区与插入点的前一个空闲分区相邻（如图（2））回收区与插入点的后一分区相邻（如图（3））回收区与插入点的前、后两个分区同时相邻（如图（4））F1R作业作业R作业作业RF2F1RF2图（1）图（2）图（3）图（4）回收过程的流程图：申请回收分区RSIZE=R的大小LOC=R的始址置R的状态为空表目R与F2相邻？R与F1相邻？在空闲分区表中找一空表目该分区的大小=SIZE始址=LOC状态=可用SIZE=SIZE+F2的大小R与F1相邻？置F2的状态为空表目F1的大小=F1的大小+SIZEF2的大小=SIZEF2的始址=LOC返回yesnoyesnonoyes（1）紧凑

通过移动的方法，把内存中分散的各个小的存储分区拼凑成大存储区的过程。4.动态重定位的可变分区分配OS用户程序A用户程序B用户程序C用户程序DOS用户程序A用户程序B用户程序C用户程序D紧凑紧凑后需要对移动了的数据和程序进行重定位。重定位：逻辑地址到物理地址的变换过程。（1）基本概念物理地址/绝对地址:指令或数据的主存地址。4.动态重定位的可变分区分配逻辑地址：指目标程序所限定地址集合中的地址。逻辑地址是相对于某个基准量（通常为零）编址时所使用的地址，因此，也称相对地址。相对地址空间：是指相对地址的全体。也称逻辑地址空间或用户地址空间。0LOAD1，250036510002500500010000LOAD1,125003651100012500015000静态重定位：在装入一个作业时，由装入链接程序在程序执行前进行的重定位，即把作业中的指令地址和数据地址全部转换成绝对地址。静态重定位是由重定位装配程序完成，一般不支持程序浮动。

4.动态重定位的可变分区分配动态重定位：在装入一个作业时，不进行地址转换，而是直接把作业直接装入到分配的主存区域中。在作业指令执行时，由硬件地址转换机构将指令或数据的地址转换成绝对地址。地址变换是在程序执行期间，随着对每条指令或数据的访问而进行。动态重定位的特点：动态重定位由硬件机构完成，硬件机构包括重定位寄存器和加法器。在程序执行的过程中进行逻辑地址到物理地址的转换。目标程序可以在内存中移动且可以不连续。0LOAD1，250036510002500500010000LOAD1，12500365110001250015000重定位寄存器100002500+相对地址（绝对地址或物理地址）地址空间（相对地址或逻辑地址）（2）动态重定位的过程如下：重定位硬件（3）动态重定位分区分配算法

请求分配u.size分区检查空闲分区表（链）找到≥u.size的空闲分区？按动态分区方式进行分配修改相关数据结构返回分区号和始址空闲分区总和≥u.size？进行紧凑修改相关数据结构失败返回是否是否

6.4覆盖和对换技术因内存空间小于作业的程序空间而引入覆盖。将主存的用户空间划分成一个固定区和多个覆盖区。主程序放固定区依次调用的子程序则放在同一个覆盖区操作系统提供覆盖系统调用函数，在转子程序前调用1.覆盖技术覆盖（overlap）A(4k)E(10k)D(6k)C(4k)B(6k)F(8k)操作系统固定区(4k)覆盖区(6k)覆盖区(10k)覆盖技术是早期扩大内存容量的一种技术，并在单道连续存储管理中使用。覆盖顺序和结构由程序员规定。基本思想：将处于等待状态(等I/O)的进程或暂时不用的程序或数据从主存换出到辅存的对换区，把将要执行的进程移入主存。2.对换（交换）技术为了支持交换，必须在系统空间设立I/O缓冲区。6.4覆盖和对换技术2.对换技术（1）对换的形式进程对换：即整体对换，以进程为对换单位，目标是提高主存的利用率。部分对换：包括页面对换和分段对换，目的是支持虚拟存储器系统。文件区：管理的目标是提高文件存储空间的利用率。对换区：采用动态分区分配的管理方式，目的是提高交换速度。外存（2）对换空间的管理1）目标：提高换进、换出的速度。2）数据结构：对换区的空闲分区表（或链），每个表项应包括分区的首址和大小。（即开始盘块号和盘块数）3）对换区的分配和回收对换区的分配一般采用连续分配方式，与动态分区的内存分配与回收基本相同。2.对换技术（3）进程的换进与换出1）进程的换进从交换区中寻找处于“就绪”状态且换出时间最长的进程换进。申请内存空间执行换入操作成功2.对换技术2）进程的换出选择处于阻塞或挂起状态且优先级最低的进程换出。（注：正在被共享的程序段或数据不能换出）申请对换区空间执行换出操作成功2.对换技术注意：对换技术没有从逻辑上扩充主存空间给用户使用（即不提供虚拟地址空间）！！6.5基本分页存储管理方式（不支持页面对换功能）1.基本概念页：将进程的逻辑地址空间分成若干大小相等的片，这样的片称为页面，页面从0开始连续编号，如0，1，2，……物理块：将内存地址空间分成与页面大小相同的存储块，称之为物理块或页框，物理块或页框也从0开始连续编号，也称页帧。有效地址：也称“虚拟地址”或“相对地址”，有效地址用一数对(p,d)表示，结构如下：回收：当进程结束时，系统回收它的所有物理页帧入空闲队列。分配：初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列获得相应数量的页帧。2.动态地址转换机构

因分页存储器管理方式中逻辑地址与物理地址之间失去自然联系，故要通过页表，并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存。6.5基本分页存储管理方式（不支持页面对换功能）页表：放在系统空间的页表区，存储逻辑页与物理页帧之间的对应关系。PCB表中有一指针指向页表，即每一进程拥有一张页表。18530498765432103210逻辑空间物理空间页表页号有效地址结构：6.5基本分页存储管理方式

逻辑地址=p(页号)*页面大小+d(页内位移)

物理地址=f(页帧号))*页面大小+d(同上)p=线性逻辑地址/页面大小；

d=线性逻辑地址-p*页面大小。例如：页面的大小为1KB，求逻辑地址4101的页号和页内位移。15141312111098665432100001000000000101得到页号p=4，页内位移d=56.5基本分页存储管理方式为了减少页号和页内位移的计算时间，一般规定页面的大小为2的幂（与机器内部的二进制数的表示一致），且页长在29~212之间，这样可以根据页面的长度方便地计算出页号和页内位移（获取p和d的除、乘法通过移位就能实现）。页号和页内位移在机器指令的地址中各占几位取决于页的大小。页号和页内位移的分割由硬件完成。（1）基本地址变换机构3.地址变换页表始址页表长度p（3）d88d≤越界中断有效地址物理地址+0123页表寄存器页表页表寄存器PTR：存放页表在内存的首地址和页表的长度。页表一般常驻内存问题：CPU在这样的地址变换机构存取一个数据时，需要访问内存几次？快表：由一组高速缓冲寄存器组成，用来存放当前访问过的页表项，以减少地址转换过程中的时间花费。快表的表目结构：系统中快表的表目一般有64~256个，快表的访问速度比普通主存要高出一个数量级，以并行的方式查找快表中的各表目。

（2）带有快表的地址变换机构页号物理块号进程号访问权限如何用快表实现逻辑地址到物理地址的转换？带有快表的地址转换过程(联想存储器可以看成是页表的cache)PdN k-1 0fdn k-1 0P2f2P1f1......Pf......Pmfmf页表始地+页表联想存储器带有快表的地址变换过程如下：CPU给出有效地址P是否在快表？读出物理块号查找页表将新页号写入快表（若快表已满需要进行置换）Pd读出物理块号P是否越界？否是否越界中断是物理寄存器在进程被调度占用cpu时，将进程页表始址装入页表地址寄存器。命中率：选用8-12项组成的联想存储器，并采用适当的替换策略，在联想存储器中匹配成功的可能性可达80-90%。等效访问时间：设访存时间为750ns，搜索联想存储器的时间为50ns，命中率为80%，则（这里假设先查联想存储器再查页表）：

80%*（750+50）+20%*（750+50+750）

=950ns（2）带有快表的地址变换机构4.可用空间管理可用bitmap数组或空闲页帧链来管理可用页帧。6.5基本分页存储管理方式5.共享与保护

通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。

例：EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA3OSDATA1EDIT101234567891011EDIT2EDIT3DATA2DATA3P1 P2 P33461346734610页表存储保护越界保护：设置页表长度寄存器，查页表前，先检查页号是否越界。操作访问保护：在每个页表项中增设一存储保护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报错。例：设为每一页表项增加三位，R位表示读权限，W位表示写权限，E位表示执行权限。

R W E 0 0 0不可进行任何操作

0 0 1可以执行,不可以读写

0 1 0只可以写

假设：有一个32位的分页存储器管理系统，页面的大小规定为1KB，每个页表项占4个字节，求页表所占的最大内存空间？6.两级页表32位计算机系统的逻辑地址空间应是232，页表长度为：232/210=222，则页表所占的内存空间就是222×22=224个字节，即16MB。4.两级页表（1）原理：将页表分成与内存物理块大小相等的页，在内存中采用离散方式存放；只把当前使用的那部分页表项调入内存。（2）两级页表的逻辑结构外层页表：将页表进行分页，并为其建立一张页表。每个页表分页在外层页表中占一表项，表项的内容为页表页在内存中对应的物理块号。01…114115…10241025…

…………………01234...114…102410111068012…n第0号第n号第1号外层页表（页目录）页表01…页表分页外层页号外层页内地址页内地址

（3）两级页表的地址变换1）逻辑地址结构2）地址变换过程外层页号P1外层页内地址P2页内地址d外部页表寄存器外层页表页表项块号

d++外部页表的始址物理寄存器P2P1例1：若在一个两级页表的存储器管理系统中，某指令对应的有效地值为（1，10，253），页面大小为1K,根据下表求该指令的物理地址。6113…2081号页表分页…11211205…1106…10第1205号物理块第208号物理块10511…AbdcIntx=20;dfgAsfsdagdhhgj253物理块号为208，块内位移为253物理地址=1024×208+253例2：已知某系统的页面大小为4KB，每个页表项大小占4B，现采用多层分页策略映射64位有效地址空间。请问：若限定最高层页表的大小占1页，应采用几层分页策略？6层4.5分段存储管理方式1.为什么要引入分段存储管理方式分段共享和保护动态链接动态增长方便编程2.分段管理的基本原理将进程的地址空间划分为若干个逻辑段，段的长度由逻辑信息本身的长度决定。每一段占一个连续内存分区。分段在编译时由编译程序完成。

3.分段管理的逻辑地址结构

段号段内位移

例：…CALL[X]|<Y>…LOAD1,[A]|6STORE1,[B]|C…分段MAIN…Y………C…分段X（子程序）分段A

（数据）分段B（工作区）15163104.分段管理的地址变换和数据结构

（1）段表

系统为每个进程建立一张段映射表，称为段表。段长基地址30K40K20K80K15K120K……012…段号段表30K20K40K80K

15K120K内存段表放于系统空间，进程PCB表中存有段表始地址、段表长度。+（2）分段管理的地址变换机构段长基地址30K40K20K80K15K4K……

段号2段内位移量100段表始址段表长度012…段号+物理地址（4196）段表寄存器逻辑地址≤越界5.分页与分段的比较页是信息的物理单位；而段是信息的逻辑单位页的大小固定；而段的大小是由它代表的逻辑信息来决定分页管理的地址空间是一维的，而分段管理的地址空间是二维的4.5分段存储管理方式6.分段管理的共享和保护（1）段的共享

对于那些被多个程序共享的段，在内存中只保留一个副本。副本采用可重入代码。

4.5分段存储管理方式可重入代码：又称“纯代码”，是一种允许多个进程同时访问的代码。可重入代码在被访问过程中不允许任何进程对其进行修改。段1段表1段2段n段1段2段n段表2……………内存进程1地址空间进程2地址空间共享段共享段分段共享的示意如下图：（2）段的保护段式管理的保护方式主要有两种：地址越界保护（上、下界寄存器或基址+限长寄存器）存储保护键法（每个存储块分配一个单独的保护键，每个进入系统的作业也赋予一保护键，相当于钥匙。）存取控制4.5分段存储管理方式4.6段页式存储管理方式1.基本原理首先，将用户程序中所包含的具有独立逻辑功能的程序或数据分成若干个段，并拥有各自的段号。然后再将每个段划分成若干个页，最后不足一页的部分也占一页。2.数据结构（1）段表（2）段页表（3）段表寄存器三者的关系如下图：

段表长度段表始址段号状态页表长度页表始址01510241062056页号状态块号0……页号状态块号0…………………内存段表0号段页表1号段页表段表寄存器4.6段页式