内存管理的基本思想

每个进程都拥有自己的地址空间( Address space),包括这个进程可以使用的全部地址和其中存储的所有数据；为防止不同进程修改彼此的地址空间，操作系统需要将进程的逻辑地址转换为物理內存中的实际地址,这一过程可以由不同方法实现。
在早期的计算机中,同一时间在机器上运行的只有一个作业,因此这个进程的地址空间与实际物理内存是完全重合的,不需要进行地址转换。

在多道程序设计与操作系统逐渐形成后,操作系统必须将多个程序相互不覆盖地放入物理內存。为了达到这一目的,多种连续內存管理方法和非连续內存管理方法都逐渐被发眀和采用。

在介绍连连续內存管理和非连续內存管理的不同实现方法之前,我们必须先了解“碎片”( fragmentation)的概念和评价一个内存管理方法的标准,这样每学习个新的实现方法后,我们都可以依照这个标准来评价其优缺点,对这个方法有更完全的认识。

碎片即在内存中无法有效利用的部分,分为外部碎片和内部碎片。

• 外部碎片( external fragmentation)指的是因为长度过短而无法被使用的未分配内存；换句话说是因为太短了不中用。
• 内部碎片( internal fragmentation)指的是已分配内存中因为分配长度过长而没有被进程有效利用的内存。分到的空间太长了，根本用不了那么多。

在评价一个用来实现地址转换和内存分配的方法时，我们需要考虑到这个方法是否会造成大量碎片的出现，或者在实际实现的过程中过于复杂、占用过多内存。理想的内存分配和地址转换方法能够达到保护进程不被其它恶意进程读取其内容、保护进程不能修改自己的代码、方便进程在运行过程中获取更多内存或与其它进程共享一部分内存的目的，又不需要过多的内存空间存储地址转换需要的信息或长的时间实现地址转换或内存分配，同时又不产生内部碎片和外部碎片；下面就让我们在一个题目中应用一下我们新学到的评价标准吧！

测试题

蒜头君觉得设计操作系统的内存管理方法是一件很简单的事情，于是设计了下面这个内存管理方法给姜小姐炫耀，请你替姜小姐评价一下这个内存管理方法，指出其三个优缺点。

• 给每个进入系统的进程恰好等于它所需内存大小的内存，进程与进程之间不留空闲的内存区域
• 一个进程运行完毕后就将它的内存回收，将所有它之后的内存都往前移动，直到跟前一个进程无缝衔接为止；
• 在每个进程的进程控制块中都储存这个进程所获得的内存的起始地址和终结地址，在移动进程对应的内存时改变这两个地址，每次进程对内存进行操作时都需要用这两个地址来确认它没有超范围使用内存；
• 一个进程和另一个进程所占的内存不能重叠。

评价

连续内存管理

固定分区存储管理

为实现多道程序在系统中同时运行，必须设计一个内存管理方法使不同程序的数据可以同时存在于内存中而不互扰。早期计算机中为达此目的使用的是连续内存管理。

顾名思义,连续內存管理会将同一个进程的地址空间映射到一段连续的物理内存上。早期被用来实现连续內存管理的方法是固定分区存储管理( fixed partition),即将内存空间分为数目固定的分区,其中每个分区大小都与其它分区不同,一个分区只对应一个迸程,处于不同分区中的进程将并发执行。显然,为了能够有效地将为新进入系统的作业选择分区,我们需要一种记录未被使用的分区的方法,这就是內存分配表。内存分配表中记录了內存中所有被划分的分区的大小及使用情况,可以帮助我们为新进入系统的进程选择分区。

当进程就绪队列不为空，且出现了一个新的可使用分区时，我们有两种选择下一个进程的方法：

• 我们可以让每一个进入系统的进程排在可以容纳该进程的最小分区的队列中，在该分区空闲时选择队列的第一个进程运行；
  但是主要问题是，如果大部分进程所需的内存都处于同一大小区间内，那么等待时间就会很长；
• 我们也可以让所有进程排在同一队列中，在一个分区空闲后我们进入队列，寻找第一个分区可以容纳的进程或分区长度所能容纳的最大进程进入该分区。
  问题是如果我们选择第一个可容纳进程，那么如果该进程所需的内存很小，我们分配的分区中就会产生较大的内部碎片，而如果我们选择后一种，则我们可能面临和前一种方法类似的问题。

不难看出，合理划分内存分区对提高固定分区存储管理的效率非常重要。这一工作往往由系统管理员和操作系统共同完成，但这仍不能完全避免内部碎片问题。更糟糕的是，如果一个进程所需的内存大小大于最大分区的大小，那么系统就必须合并多个分区，而这是需要很多工作来实现的。另一方面，如果系统管理员事先知道最大作业的大小，而将一个分区设为该大小，那么该分区在运行其它进程时很可能产生很大的内部碎片。另外，如果一个进程在运行时发现需要更多空间，那么固定分区的存储方式很难给这个进程分配新的分区。最后，我们知道在现代系统中很多时候进程的数量是很少的，而少部分时候进程数量会很多，造成拥堵，固定分区的管理方法限制了分区的数量，因此不适于处理这种情况。

可变分区存储管理

为了解决前面提到的内部碎片和无法容纳过大进程的问题，我们可以采取一种更具有变通性的方法实现连续内存管理；这种方法就是可变分区存储管理（variable partition）。
这种管理方式按照不同进程所需的内存大小划分分区，并将所有未分配分区存放在一个链表中。
在一个进程结束、被系统撤销后，它所占的分区将被标记为可用，加入未分配分区的链表；如果其毗邻的分区也为未分配分区，那么它们就会被合为一个更大的未分配分区加入链表。
在一个新的进程进入系统时，系统将沿链表寻找可以容纳该进程的未分配分区，将进程需要的大小分配给该进程，将该分区中剩余的内存作为一个新的未分配分区加入链表。下面的图片表示的是可变分区存储管理中分区的回收和合并：

在上面的讨论中，没提到两个问题：

• 在所有大小不小于进程需求的分区中，我们如何选择一个合适的分区分配给这个进程？
• 如果进程所需的内存大小已经超出系统中最大的未分配分区的代销或系统中未分配内存的总量，我们有没有办法让进程不等待而直接开始运行呢？

以后将讲解实现可变内存分配的算法和内存不足时的处理办法。

可变分区存储管理的实现

为了在可变分区存储管理中最有效地分配分区，使新进程在进入系统时即可以找到适合其大小的分区而不产生过多碎片，我们可以采取不同的方法排列未分配分区链表中的分区并选择相应的算法来分配分区。针对未分配分区的分配有五种不同的算法，下面我们将向你一一介绍。

最先适应（first fit）

顺序查找未分配分区的链表，选择第一个能满足长度要求的分区。采取这种算法时未分配区表中的空闲区往往按照地址从低到高排列，这样高地址部分的内存尽量不被分割，可以被留给内存需求大的进程。
尽管这种算法使低地址空间的使用率远高于高地址空间并在低地址空间产生了许多小的未分配分区，在实际的系统中，这种算法由于其快速、便于实现的特点被广泛应用。

下次适应（next fit）

这种算法会保留一个搜索指针，每次总是从上次未分配分区的扫描结束处开始扫描，直到找到第一个能满足长度要求的空闲区。
这种算法相比第一种对存储空间的利用率较为均衡，不会使碎片化的空闲区集中在低地址部分。

最优适应（best fit）

在每一个新进程进入系统时都扫描整个未分配分区链表，寻找最小的可满足该进程内存需求的未分配分区。使用这种算法时往往把分区按大小升序排列，方便找到符合要求的最小分区。
这种算法的问题是每次分配分区后，该分区中大于进程所需内存大小的部分可能很小，因此会在未分配分区链表中加入很多很小的分区，不能被任何进程使用，而导致外部碎片的产生。

最坏适应（worst fit）

与上一种相反，这种算法总是将最大的未分配分区分割给作业使用，这样分配的分区中剩下的分区总不会过小。
使用这种算法时，我们总是将未分配分区按大小降序排列，使找到最长的分区非常快速。

快速适应（quick fit）

快速适应( quick fit):这种算法给一些常用的分区长度设立了单独的链表(如:2KB,4KB和8KB的分区可能分别对应一个单独的链表)。我们把大小接近这些分区的分区也放在这些分区的链表中(如:5KB分区可以放在4KB的链表中)。这样,在一个新进程进入系统中时,我们可以将可以容纳该进程的最小长度的链表的第一个分区分给它。这种算法非常快速,但在归还分区和合并未分配分区时非常复杂。

内存不足的解决办法

连续内存的存储面临一个比较大的问题，即难以获得大小足够的连续内存用于分配给一个进程。这种情况又可以被细分为两种情况：

• 一种情况是，系统中未分配内存的总量大于进程需要的内存；
  我们可以通过合并分区解决内存不足的问题
• 另一种情况是，系统中未分配内存的总量小于进程需要的内存。
  我们必须将一部分现在处于内存中的东西移到外存中。

我们将先讲解解决第一种问题的办法，即移动技术。
移动技术就是通过读出已分配内存中的全部数据并写回内存中的另一位置将进程的内存分区移动到一起，使未分配分区集中到一个位置合为一个大的未分配分区，分配给新进程。
这种方法的问题是很明显的：

• 如果一个进程正在读写它的分区，那么系统就不能移动这个分区；
• 移动过程中，进程也不能读写其内存，这将延长所有进程的响应时间。

因此系统一般会尽量避免移动，只在必须通过移动分区来容纳新进程，或进程撤销后释放出的空闲分区与其它未分配分区不相邻时才移动分区来合并未分配分区。

当系统中的未分配内存总量已经小于进程所需的内存总量时，我们就必须将一部分数据移出内存。在这种情况下我们经常使用的技术是覆盖技术和对换技术，这里我们先来解释覆盖技术。

覆盖技术

覆盖技术要求程序开发者将自己的程序分为几个“覆盖段”，每个覆盖段中含有多个相对独立的程序部分，称为“覆盖”。处于同一覆盖段中的覆盖相互没有依赖关系，所以不需要同时处于内存中。我们以每个覆盖段中最大的覆盖的大小来规定该覆盖段的大小；在每个覆盖段中，所有覆盖按一定的顺序进入内存，这样系统在给这个进程分配内存时，就只需要分配大小等于该进程所有覆盖段大小之和的内存，节省了很多空间。

对换技术

这个技术给程序开发者提高了程序设计的难度，因为他们必须能够将程序分为互相不依赖的模块，并设计不同模块进入内存的顺序，这是十分困难的。因此，这种技术只在早期的计算机中被使用，现在经常被使用的是我们下面要提到的这种技术——对换技术（swapping）。

对换技术的概念非常简单，即将内存中的一部分移出内存，然后将总量小于等于被移出部分的大小的数据从外存移到内存中，但是我们面临着一个很重要的问题，即哪一部分内存应该被移出呢？

在连续内存管理中，由于每个进程都只有一块连续的内存，我们只能将整个进程都移出内存，因此我们一般会选择处于等待态的进程移出内存。如果我们选择运行态或就绪态的进程移出内存，那么这个进程的响应时间就会被延长，影响系统效率。但是如果没有进程处于等待态，我们应该把哪一部分内存移出呢？参考上面的覆盖技术我们可以知道，一个进程并不是同时需要其地址空间的所有部分都处于内存中，因此理想状态下，我们应该可以只把运行需要的部分留在内存中，而系统将自动把其它部分移出。这就是非连续存储管理的意义。

练习

分段内存管理

分段存储管理会将进程的逻辑地址分为两部分，段号和段内位移。每一个进入系统的进程都会拥有自己的段表，表中的每一行都对应着段号等于行号的段的段长和基址，以及一些用于限制这一段的操作权限的保护位（如是否可读、可写）。这样我们就可以通过段号获取逻辑地址所对应的段的基址，然后将段长与位移作比较，如果位移未超过段长则将位移与基质相加，得到实际的物理地址。由于系统对于段号和段内位移的尾数做出了限制，如果在32位系统中段号由i位组成，则用户进程在设计分段时不能设计超出2^i个段，，每段长度不能超过2^(32-i)个字节。

每次进程在对内存进行操作时，都必须用段号作为行号进入该进程的段表，获取基址和段长；如果段号大于该进程的最大段号，或进程对这一地址的操作不被该段允许，或逻辑地址中的段内位移大于段长，则硬件会触发异常，这就是你在写 C 程序时可能会见到的段错误（Segmentation fault）。

下面的图片可以给你一个对于分段存储管理的更加直观的理解：

分段存储的优点是，不同进程间可以共享一段逻辑上相对独立的内存，比如两个运行同一程序的进程可以共享代码分段，两个公用一个库的进程可以共享只包含这个库的段。但分段存储也有一个明显的缺点——与可变分区存储管理相似，它的每一个段大小不固定，因此可能面临内存中存在很多外部碎片，需要移动已有进程才能运行新进程的局面。为了解决这一问题，我们可能希望每一个段都有相同的大小，或可以被分为大小相同的更小单位来存储，这就是我们即将介绍的分页存储管理（Paging）

分页存储管理（Paging）

在介绍分页管理的方法以前,让我们先定义页和页框。

页与段类似,都是进程地址空间中的一部分,但不同于段的是,一个系统中所有页面的大小都是固定、相等的。页面的一般大小都是2的整数次幂字节,因此如果一个页面的大小是2字节,那么在32位系统中,我们就可以用地址最右侧的j位表示页内位移,左侧的32一j位表示页号。为了区分进程地址空间和物理內存,我们将物理內存中同样大小的內存单位称为页框;你可以把地址空间里的页想象成照片,那物理内存就像一个相册,中间有很多大小相同的相框,而相框中包含有什么照片就取决于现在是哪个进程在用这本相册。

为了将地址空间中的页与物理内存里的页框相对应,每一个进程有自己的页表,长度由进程所需的页面数决定,我们可以在第b行查看页面号(逻辑地址)等于b的页面在物理内存中对应的实际页框号。第b行中同时也包含一些其他的信息,

如读写权限位( read bit and write bit)、表示页面是否实际存在于內存中的有效位( valid bit)、表示页面是否被修改过的页面重写标志位( dirty bit)等等,我们会在讲到请求分页虚虛拟存储管理时更具体地讲到这些内容。从页表中获得页框号后,我们可以将页框号与位移合成该逻辑地址对应的物理地址。为了分配页面给不同的进程,系统将需要一个內存物理块表,用來记录页框状态,即哪些页框还未被分配,已分配的页框属于哪些进程等等;在新进程进入系统后,我们将在內存物理块表中寻找未被分配的页框给这个进程使用下面的图片表示了分页存储管理中通过逻辑地址获得物理地址的过程。

分页存储的优点是，由于内存大小是页面大小的整数倍，内存中永远不会像分段处理那样出现外部碎片。不仅如此，由于每个进程无法不通过页表获得物理地址，用户进程自然不能接触其它进程未与之共享的物理地址；而共享本身也变得简单了许多，只需要将不同进程中的两个页面指向同一个页框。当然，它也面临着很严重的问题——页表本身需要很大的空间储存，可能占去很多内存空间。为了解决这个问题，我们将在后几节中介绍多级页表、反置页表和分段与分页结合的存储管理。

分段与分页作为非连续内存管理的两种实现方法在一开始可能比较难区分，因此我们这里将专门对两种方法进行对比：

• 分段与分页都会将一个进程的地址空间分为几个小段，将这些小段分别存储在连续的一段内存中，但同一进程的不同段可能存储在不连续的内存中；
• 它们的不同点在于，分页完全根据一个固定的大小将内存分为大小相等的段，与内存中所存储的内容无关，而分段存储管理是根据内存的逻辑结构将内存分为几个部分。

一种常见的分段方法是将进程内存分为代码、数据、栈和堆四部分，然后将这几个部分分别存放在几段可能相互不连续的内存中；而在分页的存储模式中，栈可能会分布在几个在物理内存中不连续的页面中。另一点不同是，在分页存储管理中，页的划分是用户进程不可见的；而在分段存储管理中，段的划分是用户进程可见的，可以根据自己的需求和逻辑地址结构的限制来自行划分段。

分段和分页也可以被结合起来使用：我们可以将每个段对应一个页表，这样每次需要将内存中的一些部分与外存中的部分对换时，我们可以只对换某一段中的一页，而不是将整个段移出内存，这就解决了分段内存中由段落大小不同造成的外部碎片问题。

练习

虚拟存储、多级页表、反置页表

在上一节中我们已经看到,32位的系统中使用4KB的页面会导致每个进程的页表可以消耗2MB的内存。这对于32位系统2^32字节,也就是4GB的内存来讲已经很大了。在现代的计算机系统的发展中,人们意识到一个进程可能并不随时需要
其全部的程序和数据来运行,因此可以进一步扩大进程的地址空间,将地址空间的一部分储存到磁盘上,只将运行用到的部分放在物理內存中。这种想法允许一个迸程拥有与物理内存大小相同甚至大于物理內存大小的地址空间;因此虚拟存储器诞生了。在将虛拟存储中的逻辑地址转换为物理內存的实际地址时,我们需要的页表的大小是与虚拟存储中的总页面数量成正比的;由于虚拟存储很可能大于物理內存,一个页表消耗的内存可能远高于2MB。为了解决这种过度的内存消耗,我们接下来将介绍两种能够更节约空间地将页面号转换为页框号的方法。

在开始介绍以前，我们要先澄清一个有关虚拟存储器的问题。在国内的很多教材中，虚拟地址，即虚拟存储器所用的地址，和逻辑地址，即进程地址空间中的地址，是两个不同的概念。这种区分主要来源于 x86 架构对于分段存储的实现。在 x86 架构中，逻辑地址使用的是“段：段内位移”的形式，与我们常见的 0xFFFFFFFF 这种形式的地址是不同的。后一种地址与地址空间中每一个位置一一对应，因此如一跟线一样，被称为线性地址。虚拟地址都是针对进程的虚拟地址空间的线性地址，与 x86 架构中的逻辑地址有明显不同；处理器使用的是逻辑地址，但我们也可以通过一定的方式由逻辑地址获得虚拟地址。在本课程中，由于不同的架构不是我们关注的重点，我们将以“逻辑地址”来表示进程地址空间的线性地址，而不把逻辑地址当作“段：段内位移”的形式。

• 我们要介绍的第一种存储方法就是多级页表。多级页表的想法很简单，即将原来的页号分为两部分，用第一部分将原来的大页表分为几个小页表，称为页表页，将每个页表页分别存在内存的一个位置，然后将这些位置与我们用来区分页表页的页面号的第一部分一一对应，形成一个页目录表。我们在转换地址时先通过页号的第一部分页表目录找到一个页表页，然后再用页号的第二部分在该页表页中找到页框号；因此我们将页号的第一部分称为页目录位移，页号的第二部分称为页表页位移。
• 我们还剩下一个问题,我们该如何决定页目录位移包含多少位呢?
  假设在一个32位系统中,每个页面为2^iKB,页表中每行为2^jB,那么内存中总共有2^(22-i)个页面,每个页表页可以装下2^(10+i-j)个页表项。因此我们需要
  2^(22-i-10-i+j)=2^(12-2i+j)个页表页来包含所有页面。因此,我们需要12-2+j位来表示页目录位移,10+i-j位来表示页表页位移,10+i位来表示页位移。我们可以验证一下我们的计算12-2i+j+10+i-j+10+i=32。

多级页表相对于单级页表的优势是，我们不需要将所有页表页留在内存中——我们只需要那些近期使用过或正在使用的页表留在内存中，而这可以帮我们节约大量内存。
但多级页表也面临着一个问题——即使一个页面和它对应的页表页都存在于内存中，我们也需要三次访问内存，才能获得我们需要的数据——

• 第一次访问内存我们从页目录表中获取了该页表页的起始地址，
• 第二次访问内存时我们从页表页获得了页框号，
• 第三次访问内存时我们才获得了我们需要的实际数据。

这本身就需要很多时间；如果在这个过程中，我们发现其中一个页面不在内存中，那么我们还要花更多的时间将页面从磁盘中复制到内存中，多级页表的缺陷就体现出来了。

反置页表

与多级页表并列的另一种方法是反置页表( averted Page Table),它的特点是所有进程都被包含在一张表中。这种方法将逻辑地址中的页号与该进程的进程标识符结合起来作为哈希函数的输入,被哈希函数映射到一个反置页表项上。一个反置页表项包括进程标识符、页号和哈希链指针;哈希指针是一个指向反置页表中的其它项的指针,它被用来解决哈希函数中不同进程的不同逻辑页面指向同一个反置页表项的问题。
如果反置页表项中的进程标识符合页号与逻辑地址中的进程标识符和页号相同,这说明物理內存中的这一页框确实对应着逻辑地址空间中的这一页面,我们可以直接将页框号与页内位移组合在起,获得物理地址。反之,我们就必须沿哈希指针寻找符合该逻辑地址的进程标识符和页号的项,如果我们找不到这样一个项,那就说明该页面不在物理內存中,此时系统就会触发缺页异常,将页面从磁盘中复制到内存中。

反置页表相对于多级页表的优势是很明显的——对于在物理内存中的页面，我们可能只需要访问一次内存；相对于普通页表，它的大小是与物理内存中的页面数量成正比的，因此所占的内存远小于普通页表。但它的问题也非常明显——表中包含的只有在物理内存中的页面，对于不在物理内存中的页面，进程仍需建立普通页表存储，而且反置页表相对其它方式需要更复杂的硬件结构来实现。

总结

固定分区存储管理

• 内存被分为大小不同的固定的几个分区,每个分区只能被分配给一个进程
• 缺点是可能有很多内部碎片,
• 且当进程内存需求大于任何一个分区的大小时需要采用复杂的技术解决这一问题。

可变分区存储管理

• 内存分区大小可变,由进程需要的内存大小决定。
• 空闲的分区按一定顺序被排列在一个链表中,在新进程进入系统时被分配给进程
• 配给进程的空闲分区包含的进程需要的大小以外的内存将作为新的空闲分区加入链表。
• 一个进程撤销后其分区重新成为空闲分区
• 与周围的空闲分区合并后进入链表。
• 主要缺点是一段时间后会产生很多外部碎片,需要移动所有进程来产生足够大的空闲分区分配给新进程。

单级分页存储管理

• 将逻辑地址分为页号与页内位移两部分
• 在转换逻辑地址的过程中,系统将页号作为索引进入每个进程的页表,寻找对应的页框号
• 将页框号与页内位移合成物理地址
• 其优点是不会产生外部碎片,且易于保护进程和在不同进程间共享页面
• 缺点是页表所占的空间与逻辑地址空间大小成正比,所占内存过大

分段存储管理

• 将进程的逻辑地址空间按照程序结构分为几段,每一段在內存中获得一段连续的內存。
• 优点是便于共享,缺点是由于每段的长度不同,容易产生外部碎片。

多级分页存储管理

• 将单级分页存储管理中逻辑地址里的页号进一步分为页目录位移和页表页位移
• 将页目录位移相同的逻辑地址放入同一页表页。
• 通过页目录位移找到页表页起始地址后再从页表页中寻找页框号。
• 其优点是,可以不将所有页表页都留在内存中,节省空
• 其缺点是,每访问一次内存实际都对应三次访问内存,因此效率较低。

反置页表

• 以进程标识符和页号作为哈希函数的输入值,用哈希函数的输出值找到一个反量页表项。
• 对比进程标识符与页号是否相同,如果不同则跟随哈希指针查看。
• 如果相同则将对应的页框号与页内位移组合,获得物理地址。
• 其优点是反置页表的大小与物理内存大小成正比,所占空间远小于一般页表;
• 缺点是反置页表中只存储存在于物理内存中的页面,其他页面仍需设立一般页表来存储。