第4章存储器管理

2023/2/4阜阳师范学院计算机与信息学院1第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配存储管理方式4.4对换4.5分页存储管理方式4.6分段存储管理方式核心考点：1.程序执行的完整过程，静态装入与动态装入、物理地址与逻辑地址2.连续和离散分配方式、内部和外部碎片、段式与页式分配的区别3.分页管理方式中的逻辑地址结构、页表、访存过程以及防存有效时间、快表与多级页表2023/2/4阜阳师范学院计算机与信息学院24.2

程序的装入和链接编译链接装入2023/2/4阜阳师范学院计算机与信息学院34.2

程序的装入和链接4.2.1程序的装入

将一个装入模块装入内存时，有三种方式：绝对装入方式可重定位装入方式与静态重定位动态运行时装入方式与动态重定位2023/2/4阜阳师范学院计算机与信息学院44.2.1程序的装入1.绝对装入方式装入模块装入内存后，程序中的逻辑地址与实际内存地址完全相同，不须对程序和数据的地址进行修改。优点：装入过程简单。缺点：过于依赖于硬件结构，不适于多道程序系统。2023/2/4阜阳师范学院计算机与信息学院5在装入时（程序执行之前）由重定位装配程序一次性实现地址转换，以后不再改变。优点：不需硬件支持，可以装入有限多道程序。缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。2.可重定位装入方式(静态重定位)4.2.1程序的装入2023/2/4阜阳师范学院计算机与信息学院64.2.1程序的装入365LOAD1,2500365LOAD1,12500

~~

~~010002500500010000110001250015000作业地址空间内存空间

在装入时对目标程序中指令和数据的修改过程称为重定位。地址变换在装入时一次完成，以后不再改变，称为静态重定位。2023/2/4阜阳师范学院计算机与信息学院73.动态运行时装入方式（动态重定位）

把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。应设置一个重定位寄存器。优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序。缺点：需要硬件支持，OS实现较复杂。2023/2/4阜阳师范学院计算机与信息学院80100200300.........LOADA，2003456逻辑地址空间110012001300物理地址空间200相对地址+1000重定位寄存器地址映射LOADA,20034562023/2/4阜阳师范学院计算机与信息学院94.2程序的装入和链接4.2.2程序的链接静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装入模块，以后不再拆开。装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。2023/2/4阜阳师范学院计算机与信息学院104.3连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配2023/2/4阜阳师范学院计算机与信息学院114.3连续分配方式4.3.1单一连续分配在内存中仅驻留一道程序，整个用户区为一用户独占。把内存分为系统区和用户区两部分，系统区仅提供给OS使用，用户区是指除系统区以外的全部内存空间。用户程序操作系统0xFFF...0单一连续区存储管理2023/2/4阜阳师范学院计算机与信息学院124.3.2固定分区分配

把内存分为一些大小相等或不等的分区，每个应用进程占用一个分区。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统;

支持多个程序并发执行问题：可能存在内碎片1.基本原理及技术2023/2/4阜阳师范学院计算机与信息学院132.划分分区的方法

把内存划分为若干个固定大小的连续分区

分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）；缺乏灵活性。分区大小不等：划分成含多个小分区、适量的中等分区、少量的大分区。4.3.2固定分区分配2023/2/4阜阳师范学院计算机与信息学院143.内存分配

为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配）。优点：易于实现，开销小。缺点：内碎片造成浪费，分区总数固定，限制了并发执行的程序数目。4.3.2固定分区分配已分配1281284未分配64643已分配32322已分配20121状态起址(K)大小(K)分区号分区使用表作业C作业B作业A操作系统20K32K64K128K256K存储空间分配情况采用的数据结构：

分区使用表－－记录分区的大小和使用情况2023/2/4阜阳师范学院计算机与信息学院15

动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现过程中涉及三个问题：（1）分区分配中的数据结构（2）分区分配算法（3）分区分配操作4.3.3动态分区分配2023/2/4阜阳师范学院计算机与信息学院16

空闲分区表：记录尚未分配出去的分区情况，包含分区序号、起始地址、大小

空闲分区链：实现对空闲分区的分配链接。在分区起始部分设置分配信息：分区大小和状态并设置前向指针，同时在分区尾部设置后向指针1.分区分配中的数据结构2023/2/4阜阳师范学院计算机与信息学院17分配内存设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size-u.sizesize(规定的不再切割的分区大小)，将整个分区分配给请求者，否则从分区中按请求的大小划出一块u.size大小的内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。2.分区分配操作2023/2/4阜阳师范学院计算机与信息学院18回收内存当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，此时可能有四种情况：2023/2/4阜阳师范学院计算机与信息学院19(1)首次适应算法FF(2)

循环首次适应算法(3)最佳适应算法(4)最差适应算法4.3.4顺序搜索算法2023/2/4阜阳师范学院计算机与信息学院20(1)首次适应算法FF（最先匹配法（first-fit））

首址递增排列；查找第一个满足要求的空闲分区(2)循环首次适应算法（下次匹配法（next-fit），又称邻近适应算法）由FF算法演变；为实现算法需要：设置一起始查寻指针、采用循环查找方式4.3.4顺序搜索算法2023/2/4阜阳师范学院计算机与信息学院21(3)最佳适应算法（最佳匹配法(best-fit)）空闲区大小递增排列；查找既能满足要求、又是最小的空闲分区(4)最差适应算法（最坏匹配法(worst-fit)

)

4.3.4顺序搜索算法2023/2/4阜阳师范学院计算机与信息学院22例题1：

某基于动态分区存储管理的计算机，其主存容量为55MB（为初始空间），采用最佳适应（BestFit）算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小9MB2023/2/4阜阳师范学院计算机与信息学院23(5)快速适应算法(6)伙伴系统(7)哈希算法4.3.5索引式搜索算法2023/2/4阜阳师范学院计算机与信息学院24(5)快速适应算法（分类搜索法（quickfit））空闲分区的分类根据进程常用的空间大小进行划分每一类具有相同容量的所有空闲分区，单独设一个空闲分区链表搜索空闲分区分两步：①根据进程长度，从索引表中寻找到能容纳它的最小空闲区链表②从链表中取下第一块进行分配即可不会对任何分区产生分割4.3.5索引式搜索算法2023/2/4阜阳师范学院计算机与信息学院25（6）伙伴系统固定分区方式：限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式：算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统是一种动态存储管理方法，也是对以上两种内存方式的一种折衷方案。4.3.5索引式搜索算法2023/2/4阜阳师范学院计算机与信息学院26伙伴系统规定：无论已分配区或空闲分区，其大小均为2的k次幂，k为整数（1≤k≤m）其中21表示分配的最小分区的大小，2m表示分配的最大分区的大小。何谓“伙伴”：在分配时经常需要将一个大的空闲分区2i+1

分裂成两个大小相等的存储区2i，这两个由同一大分区分裂出来的小分区就称为“一对伙伴”或“互为伙伴”（6）

伙伴系统2023/2/4阜阳师范学院计算机与信息学院27若分配时，将其中的一个用于分配，而把另一个加入2i

的空闲分区链表中在回收空闲分区时，只当其伙伴为空闲分区时才归并为大空闲分区。优点：算法简单、速度快缺点：由于只归并伙伴，而容易产生碎片（6）

伙伴系统2023/2/4阜阳师范学院计算机与信息学院28（7）

哈希算法为了选择合适的空闲链表建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每个表项记录了一个对应的空闲分区链表表头指针。当进行分配时，根据所需空闲分区大小，通过哈希函数计算，得到哈希表中的位置，从而得到相应的空闲链表，实现最佳分配策略2023/2/4阜阳师范学院计算机与信息学院294.3.6动态重定位分区分配1.动态重定位的引入

在连续分配方式中，必须把一个系统程序或用户程序装入到一个连续的内存空间中。如果在系统中有若干个小的分区，其总容量大于要装入的程序，但由于它们不相邻接，使该程序不能装入内存

解决方法：将内存中的所有作业进行移动，使它们全部邻接，这样可把原来分散的小分区拼接成大分区，这种方法称为“拼接”或“紧凑”。缺点：用户程序在内存中的地址发生变化，必须重定位。20KB

0

os

作业1

作业3

作业4

52KB116KB166KB256KB1主存20KB

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存180KB

02023/2/4阜阳师范学院计算机与信息学院302.动态重定位的实现

地址变换过程是在程序执行过程期间，随着对每条指令的访问自动进行的，称为动态重定位。4.3.4动态重定位分区分配movr1,[500]123

movr1,[500]123010050059901000256k-1作业地址空间存储空间重定位寄存器1100150016005001000相对地址+2023/2/4阜阳师范学院计算机与信息学院313.动态重定位分区分配算法

动态重定位分区分配算法与动态分区分配算法基本相同，差别在于增加了紧凑的功能。4.3.6动态重定位分区分配2023/2/4阜阳师范学院计算机与信息学院32对换的引入多道程序环境下存在的问题：阻塞进程占据大量内存空间许多作业在外存而不能进入内存运行对换是提高内存利用率的有效措施4.4对换(Swapping)2023/2/4阜阳师范学院计算机与信息学院334.4.1对换的引入

分类：整体对换(或进程对换)：以整个进程为单位页面对换或分段对换：以页或段为单位实现进程对换，系统必须具备的功能：对换空间的管理进程的换出进程的换入2023/2/4阜阳师范学院计算机与信息学院344.4.2对换空间的管理存储内容驻留时间主要目标分配方式文件区文件较长久提高文件存储空间的利用率离散对换区从内存换出的进程短暂提高进程换入和换出的速度连续

在系统中设置相应的数据结构以记录外存的使用情况；对换空间的分配与回收，与动态分区方式时的内存分配与回收雷同。2023/2/4阜阳师范学院计算机与信息学院35进程的换出系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。进程的换入系统应定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将换出最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。4.4.3进程的换出与换入2023/2/4阜阳师范学院计算机与信息学院36第四章存储器管理4.5基本分页存储管理方式4.6基本分段存储管理方式2023/2/4阜阳师范学院计算机与信息学院374.5.1分页存储管理的基本方法

页面逻辑空间分页：将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。

物理块内存空间分块：把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框。也从0开始编号

内存分配原则

内存的分配以块为单位，并允许将一个进程的若干页分别装入到多个不相邻接的物理块中。页表系统为每个进程建立了一张页面映射表——页表；其作用就是实现从页号到物理块号的地址映射。……59483623120页号块号页表29105内存0346781页面大小页面（和块）的大小是由硬件确定的，应是2的幂，通常是1KB8KBn页1页…5页4页3页2页0页用户进程2023/2/4阜阳师范学院计算机与信息学院382.地址结构位移量/页内地址d页号P3112110公式A－逻辑地址页号：P=INT[A/L]L－页面大小页内地址：d=[A]MODL4.5.1分页存储管理的基本方法地址长度32位:011位为位移量(页内地址)，即每页的大小为4KB1231位为页号，地址空间最多允许有1M页2023/2/4阜阳师范学院计算机与信息学院393.页表页表是系统为每个进程建立的一张页面映像表，用来记录相应页面在内存中对应的物理块号。页表的作用就是实现从页号到物理块号的地址映射。页表项包含页号、块号和存取控制字段(读/写、只读、只执行)

4.5.1分页存储管理的基本方法n页…5页4页3页2页1页0页用户程序……59483623120页号块号页表内存203456789101页表的作用：2023/2/4阜阳师范学院计算机与信息学院401.基本的地址变换机构页表可以由一组专门的寄存器来实现，一个页表项用一个寄存器。但寄存器成本高，系统页表可能很大，所以页表大多常驻内存。在系统中只设置一个页表寄存器PTR，在其中存放页表在内存中的始址和页表的长度。4.5.2地址变换机构2023/2/4阜阳师范学院计算机与信息学院414.5基本分页存储管理方式页表长度页表始址页表寄存器①页内地址页号(3)逻辑地址A②<越界中断③页表+4b32110块号页号④物理地址块内地址块号⑤某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、4500转换为物理地址★逻辑地址1023：1023/1K得页号为0，页内地址为1023，查页表找到对应得物理块为2，故物理地址为2*1K+1023=3071。★逻辑地址2500：2500/1K得页号为2，页内地址为452，查页表找到对应得物理块为6，故物理地址为6*1K+452=6596。★逻辑地址4500：4500/1K得页号为4，页内地址为404，页号大于页表长度，产生越界中断

2023/2/4阜阳师范学院计算机与信息学院42补充题

假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…15。设某作业有4页，其页号为0，1，2，3，被分别装入主存的2、4、1、6块。试问（计算结果按十进制表示）：（1）该作业的总长度是多少字节？（2）写出该作业每一页在主存中的起始地址；（3）对多个逻辑地址100、4146、8192、16384，试计算出相应的内存地址2023/2/4阜阳师范学院计算机与信息学院43例题2设某计算机的逻辑地址空间为64KB，按字节编址。若某进程最多需要6页数据存储空间，页的大小为1KB，当进程要访问逻辑地址为17CAH的数据，请问该逻辑地址对应的页号是（）52023/2/4阜阳师范学院计算机与信息学院442.具有快表的地址变换机构

CPU在每存取一个数据时，需要两次访问内存：第一次：访问页表，找到指定页的物理块号，将块号与页内偏移量拼接形成物理地址。第二次：从第一次所得地址中获得所需数据，或向此地址中写入数据。解决方法：在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想存储器”或“快表”。4.5.2地址变换机构页表长度页表始址页表寄存器页内地址页号(3)逻辑地址Adb物理地址<+越界中断b1块号页号页表具有快表的分页系统的地址变换机构：b

块号页号快表输入寄存器4.5.3访问内存的有效时间内存的有效访问时间EAT（EffectiveAccessTime）从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间基本分页存储管理方式，访问的页在主存中，则EAT=查找页表时间+形成物理地址并访问内存数据时间假设访问一次内存的时间为t，EAT=t+t=2t2023/2/4阜阳师范学院计算机与信息学院454.5.3访问内存的有效时间具有快表的分页存储管理方式访问的页在主存中，且访问页的页表项在快表中。则

EAT=查找快表时间+形成物理地址并访问内存数据时间访问的页在主存中，但访问页的页表项不在快表中。则

EAT=查找快表时间+查找页表时间+更新快表时间+形成物理地址并访问内存数据时间。

假设访问一次内存的时间为t，λ表示查找快表所需时间，α表示命中率：EAT=

(λ+t)ⅹα+（

λ+t+

t）（1-α）

2023/2/4阜阳师范学院计算机与信息学院46所谓命中率：

是指使用快表并在其中成功查找到所需页面的表项的比率。2023/2/4阜阳师范学院计算机与信息学院47例题4某一个页式存储系统具有快表，多数活动页表项都可以存在其中。如果页表存放在内存中，内存访问时间是1us，检索快表的时间为0.2us，若快表的命中率是85%，则有效存取时间是多少？解答：EAT=（0.2+1）ⅹ85%+（0.2+1+1）（1-85%）

=1.35us2023/2/4阜阳师范学院计算机与信息学院48练习2某一页式系统，其页表存放在主存中：1）若对主存的一次存取需要1.5us，试问实现一次页面访问时存取时间是多少？2）若系统有快表且其平均命中率为85%，而页表项在快表中查找时间可忽略不计，试问此时的存取时间为多少？2023/2/4阜阳师范学院计算机与信息学院494.5.4两级和多级页表

现代计算机系统都支持非常大的逻辑地址空间(232264)，页表就非常大，需占用较大的地址空间。解决方法：采用离散方式只将当前所需页表项调入内存2023/2/4阜阳师范学院计算机与信息学院501.两级页表

例如：32位逻辑地址空间，页面大小为4KB(即12位)，若采用一级页表机构，应有20位页号，即页表项应有1M个；在采用两级页表机构时，再对页表进行分页，使每页包含210(即1024)个页表项，最多允许有210个页表分页。即页内地址外层页内地址外层页号dp2p1312221121104.5.4两级和多级页表………012345671141151468内存空间…641第0页页表012…1023115114第1页页表012…10231468第n页页表012…1023174210781011012n外部页表两级分页结构2023/2/4阜阳师范学院计算机与信息学院51

为实现方便，在地址变换机构中需设一外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用p2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址。外部页表寄存器外部页表页表db物理地址++dP2P1逻辑地址外部页号外部页内地址页内地址具有两级页表的地址变换机构：4.5.4两级和多级页表2023/2/4阜阳师范学院计算机与信息学院522.多级页表

两级页表对32位机器适用，64位呢？页面大小为4KB即212B，还剩52位，按210位来划分页表，则剩余42位用于外层页号，此时外层页表可能有4096G个页表项，要占用16384GB的连续存储空间解决方法：采用多级页表，将外层页表再进行分页。4.5.4两级和多级页表2023/2/4阜阳师范学院计算机与信息学院53例题5某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210B，页表项大小为2B，逻辑地址结构为逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）页目录号页号页内偏移量1284.5.5反置页表（InvertedPageTable）为了减少页表占用的内存空间，引入了反置页表。反置页表是为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所隶属进程的标识符。地址变换：根据进程标识符和页号，去检索反置页表；若检索到匹配的页表项，则页表项的序号i便是该页所在的物理块号若未检索到，则表明此页尚未装入内存2023/2/4阜阳师范学院计算机与信息学院542023/2/4阜阳师范学院计算机与信息学院554.6基本分段存储管理方式4.6.1分段存储管理方式的引入主要是满足用户和编程员的多方面要求：方便编程信息共享信息保护动态增长动态链接2023/2/4阜阳师范学院计算机与信息学院56

4.6.2分段系统的基本原理1.分段

作业地址空间被划分为若干个段，每个段定义了一组逻辑信息，都有自己的名字。通常用段号代替段名，每段从0开始编址，并采用一段连续地址空间。程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。

2023/2/4阜阳师范学院计算机与信息学院57地址结构：逻辑地址由段号(段名)和段内地址所组成段内地址段号3116150

该地址结构允许一个作业最长有64K个段，每段的最大长度为64KB。4.6.2分段系统的基本原理2023/2/4阜阳师范学院计算机与信息学院582.段表

为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(基址)和段的长度。段表可以实现从逻辑段到物理内存区的映射。4.6.2分段系统的基本原理2023/2/4阜阳师范学院计算机与信息学院594.6.2分段系统的基本原理作业空间(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K150K10K120K15K80K20K40K30K0123段号段长基址段表(S)=310K(D)=215K(X)=120K(MAIN)=030K内存空间040K80K120K150K利用段表实现地址映射:2023/2/4阜阳师范学院计算机与信息学院603.地址变换机构

在系统中设置段表寄存器，用于存放段表始址和段表长度，以实现从进程的逻辑地址到物理地址的变换。4.6.2分段系统的基本原理段表长度段表始址控制寄存器物理地址<+越界中断分段系统的地址变换机构：1002段号S位移量W段表92002008K5004K6006K1K段长基址段号0123+82928K82928692主存2023/2/4阜阳师范学院计算机与信息学院614.分页和分段的主要区别相似点：采用离散分配方式，通过地址映射机构实现地址变换不同点：页是信息的物理单位；段是信息的逻辑单位。页的大小固定且由系统确定；段的长度不固定，取决于用户程序。分页的作业地址空间是一维的；分段的作业地址空间是二维的。4.6.2分段系统的基本原理2023/2/4阜阳师范学院计算机与信息学院624.6.3信息共享

分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。data10…data1ed40…ed2ed1进程1data10…data1ed40…ed2ed1进程270…6160…2221页表80…7160…2221页表data10…data1data10…data1ed40…ed2ed1…021226061707180主存2023/2/4阜阳师范学院计算机与信息学院63

在分段系统中，实现共享十分容易，只需在每个进程的段表中为共享程序设置一个段表项。data1editor进程1data2editor进程22404080160基址段长段表3804080160基址段长段表data2…data1editor80240280380420主存4.6.3信