内存管理之内存的扩充、分配
一、覆盖与交换
- 覆盖与交换技术是在多道程序环境下用于扩充内存的两种方法。
1、覆盖
- 这种技术主要用于
早期计算机中，早期计算机主存容量远比现在的要小，主存虽然仅存放一道用户程序，但存储空间放不下用户进程的现象经常发生，而覆盖技术就可以解决这种矛盾。
1.1、思想
- 覆盖技术的思想：
由于程序运行时并非任何时候都要访问程序及数据的各个部分，因此可以将用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段；将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要的时候调入覆盖区，覆盖覆盖区原有的段。
1.2、特点
-
打破了必须将一个进程的全部信息装入主存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行，此外，内存能够更新的只有覆盖区的段，不在覆盖区的段会常驻内存。
2、交换
- 交换，也称作对换。
2.1、思想
- 交换技术的思想：
将处于等待状态或在 CPU 调度原则下被剥夺运行权力的程序从内存移到辅存以腾出内存空间，此过程称为换出；把准备好竞争处理机的程序从辅存移到内存，此过程称为换入。理想情况下，内存管理器的交换过程速度足够快，总有进程在内存中可以执行。
2.2、注意问题
- 交换技术，需要注意以下几方面的问题：
· 交换需要备份存储，通常是快速磁盘——必须足够大，并提供对这些内存映像的直接访问。
· 为有效使用 CPU，需使每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间。转移时间与所交换的内存空间成正比。
· 若换出进程，则必须确保该进程完全处于空闲状态。
· 交换空间通常作为磁盘的一整块，且独立于文件系统。
· 交换通常有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停。
· 普通的交换使用不同，但交换策略的某些变体在许多系统中，如 UNIX 系统中仍发挥作用。
3、覆盖和交换的区别
-
交换技术主要在不同进程或作业之间进行，而覆盖则用于同一个程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构，使得其对用户和程序员不透明，所以对于主存无法存放用户程序矛盾，现代操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史；而交换技术在现代操作系统中仍具有较强生命力。
二、内存分配
- 内存分配管理可以大致分为
连续分配管理方式和非连续分配管理方式两种。 - 所谓连续分配管理方式，是
指为一个用户程序分配一个连续的内存空间；而非连续分配管理方式则允许将一个程序分散地装入不相邻地内存分区。
1、连续分配
- 在连续分配管理方式中，主要包括
单一连续分配、固定分区分配和动态分区分配。
1.1、单一连续分配
-
将内存划分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；用户区为用户提供的、除系统区外的内存空间。由于内存中永远只有一道程序，因此不会出现访问越界干扰其他程序的情况，故而无需进行内存保护。 - 优点：
简单、无外部碎片，可采用覆盖技术，无需额外技术支持。 - 缺点：
只能用于单用户、单任务的操作系统中，有内部碎片，存储器利用率极低。
1.2、固定分区分配
- 最简单的一种
多道程序存储管理方式。 -
将用户内存空间划分为若干固定大小的内存区，每个分区只装入一道作业；每当有空闲分区，便从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。 - 进行分区是有两种方法：
分区大小相等和分区大小不等。前者用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性；后者将内存划分为多个较小的分区、适量的中等分区和少量大分区。如下图：
1.2.1、内存分配
-
为便于内存分配，将分区按大小排队，并建立分区说明表，表项由分区的起始地址、大小及状态构成。每当有用户程序要装入时，检索分区说明表，寻找合适的分区并将其对应分区的状态设置为“已分配”，若没有合适的分区，则拒绝为用户程序分配内存。分区说明表和存储空间分配情况如下图：
1.2.2、存在的问题
- 此种分区方式主要存在如下两个问题：
①程序可能太大放不进任何一个分区，此时用户不得不用覆盖技术使用内存空间。
②主存利用率低，当程序小于固定分区时，也占用一个完整的分区，这样分区内部存在空间浪费，此种现象称为内部碎片。 - 此种分区方式下，不能实现多进程共享一个主存区。固定分区很少用于现在的通用操作系统，但在某些用于控制多个相同对象的控制系统中仍在发挥着一定的作用。
1.3、动态分区
- 也成为
可变分区分配，是一种动态规划内存的分区方法。 - 该方法中，
不预先划分内存，而是在进程装入内存时，根据进程大小动态地建立分区，并使分区大小正适合进程的需要。故而，系统分区的大小和数目是可变的。
1.3.1、存在的问题
- 动态分区分配方法存在的一个问题就是，
随着时间的推移，内存中会出现越来越多的小内存块，也就是所谓的外部碎片——指所有分区外的存储空间会变成越来越多的碎片，与上面固定分区中提及的内部碎片相反；外部碎片的出现，会导致内存利用率降低。 - 解决外部碎片可通过
紧凑（Compaction）技术来解决，也就是操作系统不时地对进程进行移动和整理，需要动态重定位寄存器的支持，并且相对费时。
1.3.2、分区分配算法
- 在为进程分配内存分区时，需要依据一定的策略，常用的算法有
首次适应算法、最佳适应算法、最坏适应算法和邻近适应算法。
1）首次适应：
- First fit 算法，
空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。 - 最简单、最好和最快的算法，但是会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，增加了查找的开销。
2）最佳适应
- Best fit 算法，
空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。 - 每次的最佳分配都会留下很小的难以利用的内存块，产生更多的外部碎片，导致性能下降。
3）最坏适应
- Worst fit，又称为
最大适应（Largest Fit）算法，空闲分区以容量递减得次序链接，找到第一个能满足要求得空闲分区，即挑出最大的空闲分区。 - 该算法选择最大可用块，似乎不容易产生碎片，但会很快导致没有可用的大内存块，因此性能也非常差。
4）邻近适应
- Next fit，又称为
循环首次适应算法，由首次适应算法演变而来，区别在于，分配内存时从上次查找结束的位置开始继续查找。 - 该算法试图解决首次适应算法的不足，但是常常导致在内存的末尾分配空间分裂成小碎片，反而比首次适应算法的结果要差。
1.4、三种连续分配管理方式的比较
- 这三种内存管理方式的共同特点就是：
用户进程在主存中是连续存放的。
2、非连续分配管理方式
- 由于非连续分配管理方式中，将作业要求的内存空间分散地分配在内存的各个区域，因此需要额外的空间存储分散区域的索引，从而存储密度会比连续分配管理方式的低。
- 非连续分配管理方式依据分区大小是否固定分为
分页存储管理方式和分段存储管理方式。分页存储管理方式中，又- 根据运行作业时是否要把所有页面都装入内存才能运行，分为基本分页存储管理和请求分页存储管理。
2.1、基本分页存储管理
-
将主存空间划分为大小相等且固定的块，块相对较小，作为主存基本单位，进程以块为单位进行划分，进程在执行时以块为单位逐个申请块空间。 - 相对于固定分区技术，分页管理不会产生外部碎片，块的大小相对分区要小很多，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，是内部碎片—相对进程来说很小；
每个进程平均只产生半个块大小的内部碎片，这种碎片称为页内碎片。
2.1.1、相关基本概念
1）页面及其大小
-
进程中的块称为页（Page），内存中的块称为页框（Page Frame，或页帧），外存也以同样的单位进行划分，直接称块（Block）。进程申请空间时，为每个页面分配主存中的可用页框，也即页和页框一一对应。出于方便地址转换，页面大小为 2 的整数幂，通常为 512B~8 KB。页面太小会使进程页数过多导致页表过长，占用内存、增加硬件地址转换的开销，从而降低页面换入/换出效率；页面太长，会使页内碎片增大，降低内存利用率；故而页面大小要适中，在空间效率和时间效率之间权衡。
2）地址结构
- 分页地址的地址结构如下：
- 由页号和位移量两部分构成；位移量所对应的低12位为页内地址，也即每页大小为 4KB；剩下的高20位为页号，也即是地址空间最多允许有 1M 页。
3）页表
-
系统为每个进程建立一张页面映像表，称为页表。页表记录页面在内存中对应的物理块号，一般存于内存中；从页表的内容可以知道，也表示用于寻找进程的每个页面在内存中对应的物理块。 -
每个页表项由页号和物理内存中块号组成；页表项的块号与地址的位移量构成物理地址。
- 配置页表后，进程执行时，通过页表就可以找到每页在内存中的物理块号，也即是页号到物理块号的地址映射。
2.1.2、基本地址变换机构
-
地址变换机构借助页表将逻辑地址转换成内存中的物理地址。
- 系统通常设有
页表寄存器（Page-Table Register，PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的起始地址和长度存放在进程的 PCB 中，进程执行时，将页表始地址和长度存入页表寄存器。 - 若页面大小 L，逻辑地址 A 到物理地址 E 的变换过程（数据都是十进制）：
①计算页号 P=A/L 和页内偏移量 W=A%L。
②比较页号 P 和页表长度 M，若 P>=M 则发生越界中断，否则继续执行。
③页表中页号 P 对应页表项地址 = 页表始地址 F + 页号 P * 页表项长度，取出该页表项内容 b，即为物理块号。
注意：页表长度指一共有多少页，页表项长度指页地址占据多大存储空间。
④计算 E=b*L+W，得到物理地址 E 去访问内存。 - 以上整个过程由硬件自动完成。页式管理只需给出一个整数就能确定对应得物理地址，由于页面大小是固定的。因此，页式管理中的地址空间是一维的。
1）如何确定页表项大小
- 某计算机 32 位逻辑地址空间、字节编址单位、一页 4KB，页表项需要多大？
- 地址空间共有 4GB/4KB = 1M 页，故需要 20 位才能保证表示范围能容纳所有页面，又因为以字节作为编制单位，所以页表项大小要大于 3B，可选择更大的页表项让一个页面能够正好容下整数个页表项，进而方便存储，如 4B，一页正好可装下 1K 个页表项。
2）页式管理存在的问题
① 每次访存都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则会降低访存速度。
② 每个进程引入页表，用于存储映射机制，页表不能太大，否则降低内存利用率。
2.1.3、带 TLB 的地址变换机构
- 为提高访存速度（页表全存在内存中，取一个数据或一条指令至少要访问两次内存：访问页表和取数据或取指令），在
地址变换机构中增设一个具有并行查找能力的高速缓冲存储器——快表，也叫相联存储器（Translation Look aside Buffer，TLB），存放当前访问的若干页表项，加速地址变换过程；与此相对，主存中的页表称为慢表。
- 此时地址变换过程：
①CPU 给出逻辑地址，由硬件进行地址转换，将页号送入高速缓寄存器，将此页号与快表中的所有页号比较。
②若找到匹配的页号，则直接从高速缓存寄存器中取出对应的页框号，与页内偏移量组成物理地址；这样，一次访存就可以取出数据。
③若没有找到匹配的页号，则访问主存中的页表，读出页表项后，将其存入快表，便以后面可能的再次访问；调入新的页表项时，若快表已满，则需要按照一定的算法对旧的快表项进行替换。
2.1.4、两级页表（Two-Level Page Table）
- 目前大多数计算机都是 64 位的，也就是说其逻辑地址空间达到 2^64，此种环境下，页表变得非常大，需要占用相当大的内存空间，而且还是要连续的。为解决这个问题，可采用措施：
1）采用离散分配方式来解决难以找到一块连续的大内存空间的问题；
2）只将当前需要的部分页表项调入内存，其余页表项驻留在磁盘上，需要时再调入。 - 对于第一种措施的具体做法就是：
将页表再分页并离散地存储在不同的物理块中，并为离散分配地页表再建立一张页表，称为外层页表（Outer Page Table），外层页表地页表项记录了页表页面地物理块号。外层页表又称作一级页表，内层页表也就是二级页表。此时逻辑地址结构如下：
- 外层页号又叫做一级页号，外层页内地址又叫做二级页号，页内地址就是页内偏移。映射过程如下图：
- 为了地址变换实现的方便，在地址变换机构中同样需要增设一个
外层页表寄存器存放外层页表的始址，并利用逻辑地址中的外层页号作为外层页表的索引，从中找到指定页表分页的始址，再利用二级页号（外层页内地址）作为指定分页的索引找到指定的页表项，其中就含有该页在内存中的物理块号，用该块号与页内地址构成物理地址。
- 由上也可以看出，
建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序查找页表项。不过，如上做法还未解决用较少地内存空间去存放大页表地问题。为此，需要进一步的措施。在采用两级页表的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表只需调入一页或几页；为了确定某页是否已经调入内存，还应在外层页表中增设一个状态位 S，1 表示已经调入，0 表示未调入；进程运行时，地址变换机构根据逻辑地址中的外部页号，去查找外层页表，若所找到的页表项状态位为 0，则产生中断信号，请求操作系统将该页表分页调入内存。 - 两级页表对 32 位计算机是合适的，而对 64 位则不够；近年来的 64位OS 中，都是将直接寻址的存储器空间减少为 45 位长度左右，然后再用三级页表实现分页存储管理。
2.2、基本分段存储管理
- 分页管理方式是从计算机角度考虑设计的，目的在于提高内存的利用率，以提升计算机的性能，分页通过硬件实现，对用户完全透明。
分段管理方式则是考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
2.2.1、分段
- 在段式存储管理方式下，
作业或进程的地址空间被划分为若干段，每段定义了一组逻辑信息；一般按照进程的自然段来划分，例如进程由一个主程序、两个子程序、栈和一段数据组成，那么便可以划分为主程序段MAIN、子程序段X、子程序段Y、栈段S和数据段D。虽然每个段都有段名，但是为方便通常用段号替代段名，每段从 0 开始编址，并采用一段连续的地址空间；段长由段的逻辑信息决定，故而各段段长并不一致，同理整个进程或作业有多少段也是动态的。
整个作业的逻辑地址由段号和段内地址组成：
- 如图示例，段号 16 位，段内地址也就是段内偏移量也是 16 位，所以一个作业最多有 2^16=65,536 段，而每段的最大段长为 64KB。
- 页式存储管理方式下，逻辑地址的页号和页内偏移量对用户和程序员透明，
而段式存储管理方式下，段号和段内偏移量必须由用户提供，高级程序设计语言中，这个工作由编译程序完成，编译程序能自动根据源程序的情况而产生若干段。
2.2.2、段表
- 像页式存储管理方式有页表那样，段式存储管理下，
系统也为每个进程建立一张段映射表，即段表。段表项为进程一个段在内存中的起始地址（基址）和段长。段表内容如下：
- 段表可以存在一组寄存器中，这样有利于提高地址转换过程；但通常是存放在内存中。段表实现从逻辑段到物理内存区的映射。
2.2.3、地址变换机构
- 为实现进程的逻辑地址到物理地址的变换功能，在系统设置了段表寄存器，用于存放段表始地址F和段表长度M。逻辑地址A到物理地址E的变换过程如下：
①从逻辑地址 A 取出段号 S，段内偏移量 W。
②比较段号 S 和段表长度 M，若 S>=M，产生越界中断，否则继续执行。
③段表中段号为营的段表项始地址=段表始址F+段号S*段表项长度，取出对应段表项的段长C。若段内偏移量>=C，则发生越界中断，否则继续执行。
④取出段表项中该段的始址b，计算E=b+W 形成物理地址，然后根据物理地址去访存。
2.2.4、段的共享与保护
-
段的共享通过两个作业的段表中相应表项指向共享的段的同一个物理副本来实现。当一个作业正从共享段读取数据时，必须防止另一个作业修改此共享段的数据。不能修改的代码称为纯代码或可重入代码，这不属于临界资源，这样的代码和不能修改的数据可以共享，而可以修改的代码和数据不能共享。 - 与分页管理类似，分段管理的保护方法主要有：
①存取控制保护
②地址越界保护 -
所谓越界保护是将段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断；再将段表项中的段长和逻辑地址中的段内偏移量进行比较，若段内偏移量大于段长，也会产生越界中断。分页管理中的地址越界只需判断页号是否越界，而页内偏移量是不可能越界的。 - 段式管理不能通过给出一个整数便确定对应的物理地址，由于每段的长度不固定，无法通过整数除法得出段号，无法通过求余得出页内偏移量，所以段号和段内偏移量一定要显示给出，因此分段管理的地址空间是二维的。
2.3、分页和分段的区别
- 分段和分页系统有许多相似之处：都采用离散分配方式，都通过地址映射机构实现地址变换；但也有着概念上的区别，主要如下：
1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外部碎片，提高内存利用率；或者说，分页仅仅是由于系统管理的需要而不是用户的需要，段是信息的逻辑单位，含有一组相对完整的信息；分段的目的为了更好地满足用户的需要。
2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能一种大小的页面；而段长却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
3）分页的作业地址空间是一维，即单一的线性地址空间，程序员只需利用一个记忆符，就可表示一个地址；而分段的作业地址空间是二维的，程序员在标识一个地址时，既需要给出段名，又需给出段内地址。
2.4、段页式管理方式
- 页式存储管理能有效提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享；将两种存储管理方式综合起来形成段页式存储管理方式。
2.4.1、基本原理
- 在段页式系统中，
作业的地址空间首先被划分为若干逻辑段，每段有自己的段号，然后将每个段分成若干大小固定的页。内存管理方式和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。段页式系统中，作业的逻辑地址分为段号、页号和页内偏移量（页内地址）：
- 同样的，段页式系统中，也有一种用于逻辑地址到物理地址映射的表。系统为每个进程建立一个段表，每个分段有一张页表。段表项中至少包括段号、页表长度和页表始址，页表项中至少包括页号和块号。
- 而为了地址转换的实现，系统中应当设置有段表寄存器，其中存放段表始地址和段表长度，段表寄存器的作用是在段表或页表中寻址和判断是否越界。
- 一个进程中段表只有一个，而页表可以有多个。
- 进行地址变换时，
首先通过段表查到页表始地址，然后通过页表找到页帧号，最后形成物理地址。如上图所示，进行一次访问实际需要三次访问主存，因此同样可以使用快表来加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。段页式管理的地址空间也是二维的。