内存管理基础

程序的装入与连接

将用户的源程序变成一个可在内存执行的程序的步骤：

1. 编译，由编译程序将源代码编译成目标模块；
2. 链接，由链接程序将编译后的目标模块和它们的库函数链接成完整的装入模块；
3. 装入，由装入程序将装入模块装入内存；

逻辑地址：编译后，每个目标模块都从0单元开始编址，这称为目标模块的相对地址（逻辑地址），编程使用的地址，有了逻辑地址才能使用虚拟内存

物理地址：内存单元真正的地址，当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转化为物理地址

内存保护：

内存分配前，需要保证操作系统不受用户进程影响，用户进程不受其他进程影响，所有需要进行内存保护：

• 在CPU中设置上，下限寄存器,存放用户作业在主内存中的上限和下限地址，每当CPU访问内存地址时，都会和这连个寄存器地址比较，不能越界；
• 采用界地址寄存器和重定位寄存器，界限地址寄存器存放最大的逻辑地址，重定位寄存器存放最小的物理地址；内存管理机构将CPU要执行的逻辑地址和界地址寄存器比较，如果不越界，则加上重定位寄存器的值映射成物理地址，再交给内存单元；
  

内存分配方式：

连续分配方式：

为用户程序分配一个连续的内存空间

1. 单一连续分配

将内存分为系统区，用户区，系统区供操作系统使用，除系统区外剩下的部分为用户区，用户区只能放一个程序（单用户，单任务）；

2. 固定分区分配

将用户区分为若干个分区，每个分区可以放一个作业，固定分区分配有两种实现方式：

• 大小相等分区
• 大小不等分区

• 程序可能太大不能放入内存分区
• 程序太小会造成内存分区的浪费内部碎片
• 不能实现多进程共享一块内存分区

3. 动态分区分配

将用户区内存根据进程的大小动态的建立分区，分区的大小和数目可变；

特点：

会产生外部碎片（撤销大进程，放入小进程多出来的空间就是外部碎片），可以通过紧凑（操作系统不时的对进程进行移动和整理）来解决外部碎片；

非连续分配方式：

一个程序分散的装入不连续的内存分区

1. 分页存储方式

把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位，每个进程已块为单位进行划分，进程执行时逐个申请块空间；

分页存储方式的概念：

• 页（页面）：一个进程的逻辑地址空间分成若干个大小相等的页，并为各页加以编号，第0页，第1页，第2页；

• 块（页框，页帧）：内存空间分成和页面大小相同的若干个存储块，以块为单位，将进程中的若干个页分别装入不相邻的物理块中；由于进程的最后一页可能装不满一个进程块，所以会产生页内碎片

• 页面大小：页面如果太小，一方面可以减小页内碎片，提高内存利用率，另一方面会使进程占用过多的内存块，导致页表过长，降低页面换进换出的效率；如果页面太大，可以提高页面换进换出的效率，但是会使页内碎片增大；使用页面的大小应该适中，通常是512B-8KB（2的幂）

• 地址结构（逻辑地址）：包含两部分，第一部分是页号P，第二部分是位移量W（页内地址），地址结构决定了虚拟内存的寻址空间有多大；
  

  分页存储方式的逻辑地址

• 页表：页面映射表，进程在执行时，通过查找该表，即可找到每一页在内存中的物理块；

地址转换：

借助页表将逻辑地址转为物理地址

• 根据逻辑地址A和页面大小L计算页号（A/L）和页内偏移量(A%L)；
• 判断页号是否越界，越界则中断；
• 根据页表寄存器计算出当前页号在页表中的位置(页表起始地址+页号*页表项长度)，找到对应的物理块号，即物理地址

2. 分段存储方式

分段存储管理的提出主要是为了满足编程，信息保护和共享，动态增长及动态链接的需要；
将用户进程按照逻辑结构划分为多个段（段内要求连续，段间不要求连续），用户进程由主程序，两个子程序，栈，数据组成，可以将程序分成五个段；

• 逻辑地址：
  

• 段表：段表记录段在内存中的起始地址和段长度，执行中的进程通过查找段表，找到每个段对应的内存区；
  

地址转换：

• 从逻辑地址中取出段号和偏移量
• 段号越界中断的判断
• 计算段号S在段表中的位置：段表起始地址F + 段号S*段表项长度,找到位置后查找段长C，再次进行中断判断：段内偏移量＞段长C，则中断
• 根据段表中的基址（始址）b，物理地址E = b + w；

3. 段页式存储方式：

页式存储能提高内存的利用率，段式存储能反应程序的逻辑结构，有利于数据共享，段页式存储将这两种存储方式结合起来

段页式存储实现思路：

将用户程序首先分成逻辑段，每个段有段号，再将逻辑段分成固定大小的页；将内存空间按照页式存储一样分成和页面大小相等的存储块；

逻辑地址：

段号+页号+页偏移量

段页式存储管理地址转换：

• 首先用逻辑地址中的段号S和段表长度做中断判断
• 然后利用段号S和段表起始地址查询段表中的页表始址
• 页号P和页表始址计算出页表项位置及其对应的物理块

虚拟内存

局部性原理：

• 事件局部性：程序的某条指令被执行，不久后该指令可能再次被执行；某数据被访问，不久后可能再次被访问；
• 空间局部性：一旦程序访问了某个存储单元，不久后其附近的存储单元也会被访问，即在一段时间内所访问的地址可能集中在一定范围内；

虚拟内存的定义：

基于局部性，在程序装入内存时，可以将一部分（即将执行的部分）装入内存，其余部分（暂不执行的部分）留在外存，就可以启动程序；在程序执行过程中，如果需要访问的信息不在内存，操作系统就会将外存的部分调入内存，相反，如果内存中的某部分暂不使用就会调出内存到外存中；

系统提供了部分装入，请求调入，置换功能，给用户的感觉就是在使用一个比实际物理内存大的多的存储器,虚拟内存的大小由计算机的逻辑地址决定

请求分页管理方式：

请求分页管理方式建立在基本分页管理方式的基础上，增加了调页功能和页面置换功能,是目前最常用的一种实现虚拟内存的方式；

• 调页功能：程序在执行时，当所访问的页面不在内存中，就会使用调页功能将其调入内存；

• 页面置换功能：将暂时不用的页面换出到外存上

页面置换算法（决定换入哪页，换出哪也）：

1. 最佳置换算法（OPT）：

选择以后永不使用的页面，或是在最长时间内部不再被访问的页面，保证最低的缺页率，由于人们无法预知进程在内存中的若干页面中哪个是未来最长时间不再被访问的，所以该算法无法实现；

2. 先进先出页面置换算法（FIFO）：

优先淘汰最早进入内存的页面，该算法实现简单，可以使用队列来做，但是该算法与进程的实际运行规律不符合，有些页面会经常访问；
FIFO算法会出现 物理块数增加，故障页数也增加的异常现象（BeLady现象）

3. 最近最久未使用置换算法（LRU）：

选择最近最长时间未被访问过的页面予以淘汰，该算法为每一个页面设置一个字段，用来记录从上次被访问到现在的时间，淘汰页面时选择现有页面中最大值；
LRU算法性能较好，但需要寄存器和栈的硬件支持，不会出现BeLady异常

4. 时钟置换算法（Clock）：

LRU算法的性能好但是实现难，开销大，Clock算法是一种LRU近似算法；

1. 简单的Clock算法：

为每一页设置一个访问位,再将内存中所有页面连成一个循环队列，当一个页面被访问时，将其访问位置为1，在选择淘汰页面时，按着FIFO检查队列中的页面，如果其访问位是0，就换出，如果是1，就置为0，暂不换出，给该页第二次驻留的机会，访问下一个；

2. 改进的Clock算法：

在改进Clock算法中，除了考虑页面使用情况，还增加了一个因素置换代价，选择淘汰页面，既要选择未被使用的，又要选择未被修改的；

将页面分为四类：

1. 未被访问，未被修改；最佳淘汰（A = 0，M = 0）
2. 未被访问，已被修改；不是很好的淘汰页（A = 0，M = 1）
3. 已被访问，未被修改；可能再被访问（A = 1，M = 0）
4. 已被访问，已被修改；可能再被访问（A = 1，M = 1）

改进Clock算法思想：

1. 遍历循环队列，寻找最佳淘汰（A = 0，M = 0），找到则淘汰
2. 如果第一步没有找到，开始第二轮扫描，寻找第二类页面（A = 0，M = 1），找到的第一个作为淘汰页，并且将扫描过的所有页面访问位都设置为0；
3. 如果第二步还没有找到，就再次重复第一步，如果还没有，再次重复第二步，此时肯定会找到；

页面分配策略：

1. 固定分配局部置换：为每一个进程分配固定的物理块，物理块的数量在程序的整个运行过程都不变，如果程序发生缺页，则会在当前程序的页面中选出一个页面淘汰，置换外存需要的页面；

这种策略难以确定物理块的数量，过多会导致CPU利用率下降，过少会导致程序频繁缺页，页面切入切出的概率增大

2. 可变分配全局置换：首先为进程分配一定数量的物理块，操作系统会预留一些空闲的物理块，如果一个进程发生缺页，就会在预留的物理块队列中取出一个空闲物理块分配给它使用；

这种方式比较灵活，可以动态增加进程物理块的数量，但是盲目的增加物理块会降低系统的并发能力

3. 可变分配局部置换：为每一个进程分配一定数量的物理块，当进程缺页时，只能置换当前进程的页面，如果进程频繁的发生缺页置换，系统就会再次为它分配一些物理块，如果一个进程缺页率减少，系统就会减少此进程的物理块数量；

可以动态的增加和减少物理块，保证了系统的并发能力

调入页面的时机

1. 预调页策略：预计在不久后会访问的页面预先调入内存，这种策略主要用于进程的首次调入，成功率只有50%；

2. 请求调页策略：进程在运行中需要访问的页面不在内存中则会发出页面调入的请求，这种策略易于实现，目前大多虚拟存储器采用此策略；

从何处调入页面

外存分为两部分：文件区（存放文件），对换区（存放对换页面）

• 对换区空间充足：全部从对换区调入

• 对换区空间不足：不会被修改的文件从文件区调入，可能被修改的部分，先调到对换区，再从对换区调入；

• UNIX方式：为运行过的页面从文件区调入，运行过但又被换出的页面从对换区调入；