第四章存储器管理

【目的要求】
1. [了解]存储器的层次结构；
2. [熟悉]程序的装入和链接方式；
3. [掌握]基于顺序搜索的动态分区分配算法，了解基于索引搜索的动态分区分配算法；
4. [熟悉]多道程序环境下的对换技术；
5. [掌握]分区、页式、段式的实现原理和地址变换过程；
6. [了解]段页式存储管理方式。
【重点与难点】
- 基于顺序搜索的动态分区分配算法
- 页式、段式的实现原理和地址变换过程

4.1 存储器的层次结构

4.1.1 多级存储器结构

4.1.2 主存储器与寄存器

主存储器
寄存器

4.1.3 高速缓存和磁盘缓存

高速缓存
磁盘缓存

4.2 程序的装入和链接

对用户程序的处理步骤

4.2.1 程序的装入

绝对装入方式(Absolute Loading Mode)
可重定位装入方式(Relocation Loading Mode)
- 通常是在装入时对目标程序中的指令和数据进行修改，这个过程称为重定位。因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。
动态运行时装入方式(Denamle Run-time Loading)

4.2.2 程序的链接

静态链接方式(Static Linking)
- 在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。
装入时动态链接(Loadtime Dynamic Linking)
- 优点
  - 便于修改和更新。
  - 便于实现对目标模块的共享。
运行时动态链接(Run-time Dynamic Linking)

4.3 连续分配方式

4.3.1 单一连续分配

采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。

4.3.2 固定分区分配

划分分区的方法
- 分区大小相等，即使所有的内存分区大小相等。
- 分区大小不等。
内存分配

4.3.3 动态分区分配

分区分配中的数据结构
- 空闲分区表。
- 空闲分区链。
分区分配算法
分区分配操作
- 分配内存
- 回收内存

4.3.4 基于顺序搜索的动态分区分配算法

首次适应(first fit，FF)算法。
循环首次适应(next fit，NF)算法（下次适应算法）。
最佳适应(best fit，BF)算法。
最坏适应(worst fit，WF)算法

4.3.5 基于索引搜索的动态分区分配算法

快速适应(quick fit)算法
伙伴系统
哈希算法

4.3.6 动态可重定位分区分配

紧凑
动态重定位
动态重定位分区分配算法

4.4 对换(Swapping)

4.4.1 多道程序环境下的对换技术

对换的引入
- 所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。
对换的类型
- 如果对换是以整个进程为单位的，便称之为“整体对换”。而如果对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“局部对换”。

4.4.2 对换空间的管理

对换空间管理的主要目标
对换区空间盘块管理中的数据结构
对换空间的分配与回收

4.4.3 进程的换出与换入

进程的换出。
进程的换入。

例1. 某OS采用分区存储管理技术。OS在低地址部分占用了100KB的空间，用户区主存从100KB处开始占用了512KB。初始时，用户区全部为空闲，分配时截取空闲区的低地址部分作为已分配区。在执行了如下申请、释放操作序列后：
req(300KB)，req(100KB)，release(300KB)
req(150KB)，req(50KB)， req(90KB)

采用首次适应算法，主存中有哪些空闲区？要求画出主存分布图，并指出空闲区的首址和大小。
采用最佳适应算法，主存中有哪些空闲区？要求画出主存分布图，并指出空闲区的首址和大小。
若随后又要申请80KB，针对上述两种情况产生什么后果？说明了什么问题？

例2. (南京理工大学) 可变分区存储管理系统中，当一个进程归还一个内存分区后，空闲分区的个数会发生什么变化？

4.5 分页存储管理方式

4.5.1 分页存储管理的基本方法

页面和物理块
- 页面: 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0＃块、1＃块等等。
  - 在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。
  - 由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。
- 页面大小: 在分页系统中的页面其大小应适中
  - 因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B~8 KB。
  - 页面页面数分配时间内存碎片内存利用率
    
    太小多长减小高
    
    太大少短变大低
地址结构
- 对某特定机器，其地址结构是一定的。以32位地址为例，分页地址中的地址结构如下所示：
- 若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： $$ P=INT[\frac{A}{L}] $$
页表

页面	页面数	分配时间	内存碎片	内存利用率
太小	多	长	减小	高
太大	少	短	变大	低

4.5.2 地址变换机构

基本的地址变换机构

例1. 已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0，1，2，3页分别被分配到主存的2，4，6，7块中。请将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。

具有快表的地址变换机构
- 快表：是一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”。
- 快表中存放当前访问的那些页表项。
访问内存的有效时间(Effective Access Time,EAT)
- 定义：从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间。
- 基本分页存储管理方式中： $$ EAT = t + t = 2t$$
- 具有快表的分页存储管理方式中： $$ EAT=aλ + (1 - a) (λ + t) + t = 2t + λ - ta $$
- 如果忽略访问快表的时间，则又有：$$ EAT=at + (1 - a) 2t = 2t - at $$
- 说明：t为访问一次内存的时间，λ表示查找快表所需要的时间，a表示快表命中率。

例2. 对于一个将页表存放在内存中的分页系统：

如果访问内存需要0.2μs，有效访问时间为多少？
如果加一快表，且假定在快表中找到页表项的几率高达90%，则有效访问时间又是多少（假定查快表需花的时间为0）？

4.5.3 两级和多级页表

两级页表(Two-Level Page Table)
- 逻辑地址结构:
- 地址变换机构
多级页表

4.5.4 反置页表

反置页表的引入
- 在分页系统中，为每个进程配置一张页表，而每个页表都有许多页表项，因此占用大量的内存空间。为减少页表占用的内存空间，引入了反置页表，为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所属进程的标识符。
地址变换
- 根据进程标识符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表项的序号i便是该页所在的物理块号，若检索了整个反置页表仍未找到匹配的页表项，则表明此页尚未装入内存。对于基本分页系统意味着地址出错，对于请求分页系统，此时应产生缺页中断，系统将把此页调入内存。
缺点
- 由于在反置页表中是为每一个物理块设置一个页表项，当内存容量很大时，页表项的数目还是会非常大的。要利用进程标识符和页号去检索这样大的一张线性表是相当费时的。可以利用Hash算法来进行检索，这样可以很快地找到在反置页表中的相应页表项。

某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。

写出逻辑地址的格式；
若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？
如果物理空间减少一半，页表结构应相应作怎样的改变？

4.6 基本分段存储管理方式

4.6.1 分段存储管理方式的引入

引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：

方便编程
信息共享
信息保护
动态增长
动态链接

4.6.2 分段系统的基本原理

分段
段表
地址变换机构
分页和分段的主要区别
- 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
- 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
- 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。