第4章 存储器管理
4.1 复习笔记
一、存储器的层次结构
1多层结构的存储器系统
如图4-1所示，在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。
图4-1 计算机系统存储层次示意
2三级存储系统
（1）Cache-主存存储体系
目的：弥补主存速度的不足。
（2）主存-辅存存储体系
目的：弥补主存容量的不足。
二、程序的装入和链接
在多道程序环境下，要使程序运行，必须先将它装入内存，然后再将其变为一个可以执行的程序，通常都要经过以下几个步骤：编译、链接和装入。图4-2显示出了三步过程。
图4-2 对用户程序的处理步骤
1程序的装入
程序的装入指的是由装入程序将装入模块装入内存，有以下三种方式：
（1）绝对装入方式。
（2）可重定位装入方式。
（3）动态运行时的装入方式。
【说明】动态运行装入需要一个重定位寄存器的支持。
2程序的链接
（1）静态链接方式。
（2）装入时动态链接。
（3）运行时动态链接。
三、连续分配存储管理方式
1单一连续分配
2固定分区分配
（1）划分分区的方法
①分区大小相等。
②分区大小不等。
（2）内部碎片
程序小于固定分区大小时，也会占用一个完整的分区空间，此时分区内部就存在空间浪费，称为内部碎片。
3动态分区分配
（1）动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。
（2）回收内存时可能的情况；
①回收区与插入点的前一个空闲分区F1相邻接，见图4-3（a）。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
②回收分区与插入点的后一空闲分区F2相邻接，见图4-3（b）。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
③回收区同时与插入点的前、后两个分区邻接，见图4-3（c）。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
图4-3 内存回收时的情况
④回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
4基于顺序搜索的动态分区分配算法
（1）顺序搜索的定义
顺序搜索是指依次搜索空闲分区链上的空闲分区，去寻找一个大小能满足要求的分区。
（2）基于顺序搜索的动态分区算法的分类
①首次适应（first fit，FF）算法。
②循环首次适应（next fit，NF）算法。
③最佳适应（best fit，BF）算法。
④最坏适应（worst fit，WF）算法。
【说明】其中，首次适应算法是最简单、最好最快的算法。
5基于索引搜索的动态分区分配算法
（1）快速适应算法。
（2）伙伴系统。
（3）哈希算法。
6逻辑地址空间与物理地址空间
（1）编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址（逻辑地址）。
（2）链接程序依次按照各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。
（3）物理地址空间是指内存中物理单元的集合。
（4）通过地址转换将逻辑地址转换为物理地址的过程称为地址重定位。
四、对换（交换）和覆盖
1覆盖的基本思想
将用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段。首先将即将访问的段调入覆盖区，其他段存于外存。在需要时，系统将其调入覆盖区，覆盖原有段。
2对换
（1）换入
把准备好竞争CPU运行的程序从辅存移到内存的过程称为换入。
（2）换出
把处于阻塞状态的程序从内存移到辅存的过程称为换出。
3对换与覆盖的区别
（1）覆盖用于同一个作业或进程中。
（2）交换用于不同的作业或进程中。
五、分页存储管理方式
1分页存储管理的基本方法
（1）页面和物理块
①页面
分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。
②物理块
把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框。
（2）地址结构
分页地址中的地址结构如下：
前一部分为页号P，后一部分为位（偏）移量W，即页内地址。图中的地址长度为32位，其中0～11位为页内地址，即每页的大小为4KB；12～31位为页号，地址空间最多允许有1M页。
（3）页表
系统为每个进程建立了一张页表。如图4-4所示。页表的作用是实现从页号到物理块号的地址映射。
图4-4 页表的作用
2地址变换机构
（1）地址变换机构的基本任务
借助页表，将逻辑地址中的页号转换为内存中的物理块号。
（2）基本的地址变换机构
页表的功能可以由一组专门的寄存器来实现。图4-5显示出了分页系统的地址变换机构。
图4-5 分页系统的地址变换机构
（3）具有快表的地址变换机构
①快表（TLB）是一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”。
②增加快表原因：页表是存放在内存中的，则CPU每存取一个数据时，都要两次访问内存。为了提高地址变换速度，增设快表。
【说明】两次访存指：第一次访问内存得到物理地址；第二次根据物理地址访问对应的内存单元。
③TLB中用于存放当前访问的若干页表项。
图4-6显示了具有快表的地址变换机构。
图4-6 具有快表的地址变换机构
【说明】读者应能清晰描述出地址变换的过程，这是重要考点。
3访问内存的有效时间
（1）定义
从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所花费的总时间，称为内存的有效访问时间（EAT）。
（2）基本分页管理的有效时间
假设访问一次内存的时间为t，在基本分页存储管理方式中，存取一条指令或一个数据至少需要两次访存。则EAT=t+t=2t。
（3）引入快表管理的有效时间
①命中率是指使用快表并在其中成功查找到所需页面的表项的比率。
②在引入快表的分页存储管理方式中，有效访问时间的计算公式即为：
EAT=a×λ+(t+λ)(1-a)+t=2t+λ-t×a
上式中，λ表示查找快表所需要的时间，a表示命中率，t表示访问一次内存所需要的时间。
【说明】快表的有效性基于局部性原理。
4两级和多级页表
（1）两级页表
两级页表的逻辑地址结构如图4-7所示。
图4-7 两级页表结构
（2）多级页表
①建立多级页表的目的是建立索引，不用浪费主存空间去存储无用的页表项。
②顶级页表最多只能有1个页面。
【说明】页式地址空间是一维的。
六、分段存储管理方式
1分段存储管理方式的引入
分段管理方式满足了方便编程、信息共享、信息保护、动态增长、动态链接的需要。
2分段系统的基本原理
（1）分段
在分段存储管理方式中，作业的地址空间被划分为若干个段。逻辑地址由段号和段内地址所组成。
图4-8 分段系统中的逻辑地址结构
（2）段表
①每个段在表中占有一个表项，其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度，如图4-9所示。
②段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但更常见的是将段表放在内存中。
③段表用于实现从逻辑段到物理内存区的映射。
图4-9 利用段表实现地址映射
（3）地址变换机构
①在进行地址变换时，系统将逻辑地址中的段号S与段表长度TL进行比较
a．若S>TL，表示段号太大，是访问越界，于是产生越界中断信号。
b．若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。
②检查段内地址d是否超过该段的段长SL
a．若超过，即d>SL，同样发出越界中断信号。
b．若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址。图4-10显示了分段系统的地址变换过程。
图4-10 分段系统的地址变换过程
【说明】段式地址空间是二维的。
3段页式存储管理方式
（1）分页、分段式存储管理方式的优点
①分页式存储管理方式以页面作为内存分配的基本单位，能有效地提高内存利用率。
②分段式存储管理以段作为内存分配的基本单位，能够更好地满足用户多方面的需要。
（2）段页式存储管理方式的基本原理
①段页式系统的基本原理是分段和分页原理的结合
即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。图4-11（a）显示了一个作业地址空间的结构。该作业有三个段：主程序段、子程序段和数据段；页面大小为4KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，如图4-11（b）所示。
图4-11 作业地址空间和地址结构
②段页式系统利用段表和页表实现地址映射
图4-12示出了利用段表和页表进行从用户地址空间到物理（内存）空间的映射。
图4-12 利用段表和页表实现地址映射
【注意】段页式存储管理下，在一个进程中，段表只有一个，页表可能有多个。
（4）地址变换过程
①地址变换机构
a．进行地址变换时，首先利用段号S，将它与段长TL进行比较。
b．若S<TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址。
c．并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。图4-13示出了段页式系统中的地址变换机构。
图4-13 段页式系统中的地址变换机构
②内存访问过程
在段页式系统中，为了获得一条指令或数据，需三次访问内存：
a．访问内存中的段表，从中取得页表始址；
b．访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；
c．从第二次访问所得的地址中取出指令或数据。
③在段页式系统中也可增设高速缓冲寄存器（Cache），以提高平均访问速度。
【说明】段页式地址空间是二维的。