一、存储器的基础知识

首先，一般的存储器我们就会认为它包含着三部分：

寄存器：速度最快，但是造价高。
主存储器：速度次之，被通俗称为内存。
外存：速度最慢，用于存储文件数据，因为上边两种一旦断电，数据就会丢失。这个用来做持久化存储的。

因此，我们的存储器往往是使用三层结构的。

1.1 程序的装入和链接

在操作系统的角度而言，我们面对存储器就是面对程序的装入和连接，一般地，用户程序向要在系统上运行，就要经历下面几个步骤：

• 编译：对用户源程序进行遍历，形成若干个目标模块。
• 链接：将目标模块以及他们所需要的库函数链接在一起，形成完整的模块。形成逻辑地址，完成重定位。
• 装入：将模块装入内存,完成逻辑地址到物理地址的变换。

1.1.1 绝对装入

  用户程序中使用的地址称为相对地址或逻辑地址或虚拟地址。在早期，当程序装入内存时，指令存储在内存中的物理地址与其逻辑地址完全相同。这种程序的装入方式称为绝对装入方式(Absolute Loading Mode)。

1.1.2 可重定位装入方式（避免地址叠加）

  采用可重定位的装入方式(Relocation loading Mode)时，如果能够将不同的的程序装入到地址范围不同的物理内存空间，避免分配给各个程序的内存空间叠加(相交或“撞车”)，就能实现将多个程序安全装入内存，使它们共享内存空间，从而支持多任务系统。

特点：如果使用可重定位装入方式，就必须要解决：逻辑地址对物理地址之间的转换。

1.1.3 静态装入

  静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。链接器是一个独立程序，将一个或多个库或目标文件(先前由编译器或汇编器生成)链接到一块生成可执行程序。

特点：在程序运行前一次性装入

1.1.4 动态装入

  随着内存技术的发展，为了让更多的程序投入有限的内存并发运行，操作系统只将运行程序所必须的模块装入内存，其他诸如帮助系统等不常用的程序模块不装入内存，进而只装入能够使程序运行起来的那部分模块，更加节省了空间。

特点：在程序运行时，分批装入到内存中

1.1.5 静态链接

  静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。链接器是一个独立程序，将一个或多个库或目标文件(先前由编译器或汇编器生成)链接到一块生成可执行程序。

1.1.6 动态链接

  载入时动态链接是在将功能模块读入内存时把动态库中调用到的相关模块的内容载入内存。载入时动态链接是分别载入，当把一个模块载入内存时检查有调用关系的模块并将其载入内存，比静态链接节省了许多开销。运行时动态链接则是把当前模块调用的模块推迟到调用的时候再载入。在运行时和运行前进行链接。

二、连续分配存储管理方式

连续分配方式，是指为一个用户程序分配一个连续的内存空间。

操作系统将内存分为系统区和用户区两部分：

• 系统区仅提供给OS使用，通常是放在内存的低址部分，用户区指系统区以外的全部内存空间，提供给用户使用，通常在高地址部分。
• 内存会被分成为系统区和用户区，比例为1:3。
• 内存分配方式指的是对用户区的分配方式。原因是用户提交的任务只能在用户区运行。

2.1 单一连续分配

  内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分，用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。因为内存中永远只有一道程序，肯定不会因为访问越界而干扰其他程序。
这种方式优点是简单、无外部碎片，可以采用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，由内部碎片，存储器的利用率极低。

2.2 固定分区方式

为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。

分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。

1 划分内存分区的方法

• 1)分区大小相等：内存分区大小一致，可能浪费空间；也可能空间不够。
• 2)分区大小不等：含较多的较小分区、适量的中等分区和少量的大分区。

系统对内存的管理和控制通过数据结构—分区说明表进行。 分区说明表说明各分区号、分区大小、起始地址和是否是空闲区(分区状态)。内存的分配释放、存储保护以及地址变换等都通过分区说明表进行。

内存分区的分配：

• 1)为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区表。
• 2)分配
• 3)回收
  

2.3 动态分区

  固定分区的重大意义在于操作系统开始支持多任务，但是仍然存在内存浪费的问题。原因是内存分区在先，而运行程序在后，对于每个待运行的程序而言内存分区的大小并非量身定做。于是就出现了当运行某个任务时只能将该任务装载到内存空间中更大的分区。尽管浪费没有单一连续分区严重，但是内存的使用率仍然很低。如果内存分区的划分不是预先划定，而是根据所要运行的程序的大小分配内存，在内存分配阶段就不会出现内存碎片。于是，动态分区技术应运而生。

1)动态分区的基本思想：在作业执行前不直接建立分区，分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变。
2)动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小，按需分配。
3)采用的数据结构：内存分配表，由两个表格组成。一个是已分配区表，另一张是空闲区表。

动态分区就有两张表来进行说明了。

动态分区分配内存时从可用表或自由链中寻找空闲区的常用方法

1)首次适应算法(First Ft Algorithm, FFA)：首次适应法要求空闲分区按起始地址递增的次序排列。分配内存时顺序查找，找到大小能满足的第一个空闲分区。
2)最佳适应算法(Best Fit Algorithm, BFA)：要求按空闲区容量形成分区连，找到第一个能满足要求的空闲分区。
3)最坏适应算法(Worst Fit Algorithm, WFA)：要求空闲区按容量递减的顺序组成空闲区可用表或自由链，找到第一个能满足要求的空闲分区。
4)邻近适应算法(Next Fit Algorithm, NFA)：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时候从上次查找结束的位置开始继续查找。

  最佳适应算法虽然称为“最佳”，但是性能通常很差，因为每次最佳的分配会留下很小的难以利用的内存块，它会产生最多的外部碎片。首次适应算法不仅是最简单的，而且通常也是最好和最快的。不过首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此页增加了查找的开销。

碎片问题
  经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求； 但其总和满足分配要求。这些空闲块被称为碎片。通过在内存移动程序的技术将所有小的空闲区域合并为大的空闲区域，这种技术称为紧凑技术，也称为紧缩技术、紧致技术、浮动技术、搬家技术。

2.4 可重定位分区分配

  动态分区很完美地在内存初次分配阶段解决了内存空间浪费的问题。但是，内存是需要重复利用的。随着任务的不断运行完毕，内存空间会被回收；同时，操作系统又会不断接收新的任务，内存空间会被分配。
  于是，当运行一个新任务时，只能从回收回来的分区上分配内存，一方面动态分区技术在一定程度上退化为固定分区，另一方面分配后余下的碎片(小块的内存空间)就被保留了下来，较小的内存空间被分配出去的可能性很小，造成了浪费(碎片）。
  最终，内存空间会存在很多小块的空闲空间，而不再有大块的空闲空间，于是当较大型的任务到达时，没有足够的空间供分配（尽管这些小块的空闲内存空间之和比任务所需的空间大）
  针对动态分区中碎片之和大于任务所需空间的情况，考虑对内存空间采用紧凑技术进行整理，将已进入内存的任务所占有的内存空间尽量搬到较低的地址，相对的，空闲碎片的会被换到了高地址空间。当所有进入内存的任务都被搬到较低的地址后，空闲碎片都被移动到了内存空间的高地址空间。于是，所有的碎片被整合成了一个大块，从而可以装载任务。这就是可重定位的动态分区。将碎片合成一大块—可重定位的动态分区

实现

• 1）动态重定位依靠硬件地址变换机构完成。
• 2）地址重定位机构需要基地址寄存器(BR)和程序虚地址寄存器(VR)。
• 指令或数据的虚地址(VA)，也称为逻辑地址(LA)。内存地址MA(MA)，也称物理地址(PA)

实现逻辑地址到物理地址的转换，可以通过公式MA＝(BR)十(VR)完成。

下图所示为指令或数据的逻辑地址到物理地址的转换过程：

优点

• 1)可以对内存进行非连续分配。
• 2)动态重定位提供了实现虚拟存储器的基础。
• 3)有利于程序段的共享。

动态重定位分区的分配算法：

• 1)主干是动态分区的分配算法。
• 2)在动态分区的基础上增加了紧凑技术。
• 3)内存分配算法，如下图所示。
  

三、非连续分配存储管理方式

  上面的存储都是连续的内存分配技术，我们的分页存储是离散的，与其花费巨大的代价搬家，不如离散地存储在这些碎片中。

• 一种离散存储的方法是面向系统的，将内存用户空间划分为大小相等(2nB，如4KB)的物理块；
• 另一种方法是面向用户的，将内存空间划分为物理段，32位系统中，以高16位表示段号，低16位表示段内地址。

这就是汇编语言中定义一个段时大小不可以超过64KB的根本原因。

离散存储思想产生的原因：

• (1)紧凑技术的弊端：尽管可重定位分区方式下的紧凑技术使得碎片得以利用，提高了内存空间的利用率。但这是以牺牲时间进行搬家而获得的，代价是很高的。
• (2)求变创新：从内存连续分配的思想上突破、创新，提出离散的内存分配方式，从而使存在大量碎片和无足够大的连续空间供分配这一矛盾得以缓解。

离散存储的基本概念
  将一个进程直接分散地装入到许多不相邻的分区中，而无须“紧凑”的分配方式，称为离散分配。离散分配的种类包括分页存储管理、分段存储管理和段页式存储管理。不具备页面对换功能的分页存储管理方式称为基本分页存储管理方式。将一个进程直接分散地装入到许多不相邻的分区中，而无须“紧凑”的分配方式，称为离散分配。离散分配的种类包括分页存储管理、分段存储管理和段页式存储管理。不具备页面对换功能的分页存储管理方式称为基本分页存储管理方式。

  非连续分配允许一个程序分散地装入到不相邻的内存分区中。当然，这也需要额外空间去存储分散区域的索引，使得非连续分配方式的存储密度低于连续存储方式。
  非连续分配管理方式根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。分页存储管理方式中，又根据运行作业时是否把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

3.1 基本分页存储管理

  固定分区分配会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免内存碎片的产生，这就引入了分页的思想：把主内存空间划分为大小相等且固定得块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

  分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。但它又有本质的不同点：块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按照块申请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存空间时，才会产生主存碎片，所以尽管会产生内部碎片，但是这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片（也称为页内碎片）。

3.1.1 分页存储管理的几个基本概念

页面和页面大小：

  进程中的块称为页，内存中的块称为页框或页帧。外存也以同样的单位进行划分，直接称为块。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。为方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，如果页面太小，会使进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入换出的效率；页面过大又会使页内碎片增大，降低内存的利用率。所以页面大小应该适中，考虑到空间效率和时间效率的权衡。
地址结构：

分页存储管理的逻辑地址结构如图所示：

地址结构包含两部分：页号P和偏移量W。地址长度为32位，其中每页大小为4KB(0-11位)，地址空间最多允许有$2^{20}$页，要注意到地质结构决定了虚拟内存的寻址空间有多大。

页表：

为了方便在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立了一张页表，记录页面在内存中对应的物理块号，页表一般存放在内存中。

在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。

  页表是由页表项组成的，这里区分一下页表项和地质结构，页表项和地址都是由两部分构成，且第一部分都是页号，但页表项的第二部分是物理内存中的块号，而地址的第二部分是页内偏移；页表项的第二部分与地址的第二部分共同组成物理地址，

  进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采用硬件来实现。页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。

   在现代的操作系统中，同一时间运行多个进程是再正常不过的了。为了解决直接操作内存带来的各种问题，引入的地址空间(Address Space),这允许每个进程拥有自己的地址。这还需要硬件上存在两个寄存器，基址寄存器(base register)和界址寄存器(limit register),第一个寄存器保存进程的开始地址，第二个寄存器保存上界，防止内存溢出。在内存抽象的情况下，当执行地址变换机构的任务是将逻辑地址转换为内存中的物理地址，地址变换是借助于页表实现的，如下图所示：

基本地址变换机构
  地址变换机构的任务是将逻辑地址转换为内存中物理地址，地址变换是借助于页表实现的，上图给出了分页存储管理系统中的地址变换机构：
   在系统中通常设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的其实地址和页表长度存放在进程控制块中，当进程执行时，才将页表起始地址和长度存入页表寄存器。设页面大小未L，逻辑地址A到物理地址E的变换过程如下（逻辑地址、页号、每页的长度都是十进制数）：

• 计算页号$P$（$P=A/L$）和页内偏移量W（$W=A\%L$）。
• 比较页号$P$和页表长度$M$，若$P\ge M$，则产生越界中断，否则继续执行。
• 页表中页号P对应的$页表项地址=页表起始地址+页号\ast 页表项长度$，取出该页表项内容$b$，即为物理块号。要注意区分页表长度和页表项长度的区别，页表长度的值是指一共有多少页，页表项长度是指页地址占多大的存储空间。
• 计算$E=b\ast L+W$，用得到的物理地址E去访问内存。

以上整个地址变换过程均是由硬件自动完成的。

  由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。

  分页存储管理方式存在的两个主要问题：一是每次访问操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访问速度会降低；二是每个进程引入了页表，用于存储映射机制，页表不能太大，否则内存利用率将会降低。

3.1.2 具有快表的地址变换机构

  由上面介绍的地址变换过程可知，若页表全部放在内存中，则存区一个数据或一条指令至少要访问两次内存：一次是访问页表，确定所存取的数据或指令的物理地址，第二次才根据该地址存区数据或指令。显然，这种方法比通常执行指令的速度慢了一半。因此，在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器(快表)，又称为联想寄存器（TLB），用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表也常称为慢表。

在具有快表的分页机制中，地址的变换过程如下：

• CPU给出逻辑地址后，由硬件进行地址转换并将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
• 如果找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅一次访存便可实现。
• 如果没有找到，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。

  快表的有效性是基于局部性原理。为了压缩页表，还引入了多级页表的思路。建立多级页表的目的在于建立索引，这样在不浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项。

3.2 分段存储管理

  分页存储管理是从计算机的角度考虑设计的，以提高内存的利用率，提升计算的性能，且分页通过硬件机制实现，对用户完全透明；而分段管理方式的提出则是考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要，

  分段：用户把自己的作业按照逻辑关系划分为若干个段，每个段都从0开始编址，并分配一段连续的地址空间（段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的）并有自己的段号和段内偏移量。因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，这不仅可以方便程序员编程，也可使程序非常直观，更具可读性。

  在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。

  分页系统中的“页”只是存放信息的物理单位(块)，并无完整的逻辑意义，这样，一个可被共享的过程往往可能需要占用数十个页面，这为实现共享增加了困难。信息保护同样是以信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位进行保护的。
在实际应用中，往往存在着一些段，尤其是数据段，在它们的使用过程中，由于数据量的不断增加，而使数据段动态增长，相应地它所需要的存储空间也会动态增加。然而，对于数据段究竟会增长到多大，事先又很难确切地知道。对此，很难采取预先多分配的方法进行解决。

3.2.1 分段系统的基本原理

  在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及堆栈段S等。

段表

在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区。进程中的各个段，可以离散地装入内存中不同的分区中。为保证程序能正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置，这就需要段表了。

地址变换机构

为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表起始地址F和段表长度M。其从逻辑地址A到物理地址E之间的变换过程如下：

• 从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W，比较段号S和段表长度M，若$S\ge M$，则产生越界中断，否则继续执行。
• 段表中段号S对应的$段表项地址=段表起始地址F+段号S\ast 段表项长度$，取出该段表项的前几位得到段长C。若段内偏移量大于等于段长，则产生越界中断，否则继续执行。
• 取出段表项中该段的其实地址，计算$E=b+W$，用得到的物理地址E去访问内存。

  与分页管理类似，分段管理的保护方法主要有两种：一种是存取控制保护，另一种是地址越界保护。地址越界保护是利用段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度则产生越界中断；再利用段表项中的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，也会产生越界中断，分页管理中的地址越界保护只需要判断页号是否越界，页内偏移是不可能越界的。
  与页式管理不同，段式管理不能够给出一个整数就可以确定对应的物理地址，这是因为每段的长度是不固定的，不能通过整数除法得出段号，通过求余得出段内偏移，所以段号和段内偏移一定要显示给出（段号，段内偏移），因此分段管理的地址空间是二维的。

分页和分段的总结

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

3.3 段页式存储管理

  页式存储管理能有效提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享，因此，段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。图(a)示出了一个作业地址空间的结构。该作业有三个段：主程序段、子程序段和数据段；页面大小为 4 KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，如图(b)所示。

  在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。图示出了利用段表和页表进行从用户地址空间到物理(内存)空间的映射。

地址变换过程：

在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长M。进行地址变换时，首先利用段号S，将它与段长M进行比较。若S < M，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。图示出了段页式系统中的地址变换机构。

四、虚拟内存管理

  传统存储管理方式的特征：上述的各种内存管理策略都是为了同时将多个进程保存在内存中以便允许多道程序设计，它们都具有以下两个共同的特征：

1）一次性：作业必须一次性全部装入内存后，方能开始运行。这会导致两种情况发生：

• 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行；
• 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。

2）驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程，会因等待I/O而被阻塞，可能处于长期等待状态。

4.1 局部性原理

  局部性原理：要真正理解虚拟内存技术的思想，首先了解计算机中著名的局部性原理。快表、页面=高速缓存以及虚拟内存技术从广义上讲，都属于高速缓存技术，这个技术所依赖的就是局部性原理。

局部性原理表现在以下两个方面：
时间局部性：如果程序中的某条指令一旦执行，不久后该指令可能再次执行；如果某数据被访问过，不久后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在这大量的循环操作。
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式聚簇存储的。

  时间局部性是通过将近来使用的指令和数据保存在高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现，虚拟内存技术实际上就是建立了“内存一一外存”的两级存储器结构，利用局部性原理实现高速缓存。

4.2 虚拟存储器的定义

  基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。当用户看到自己的程序能在系统中正常运行时，他会认为，该系统所具有的内存容量一定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。

  之所以称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后(对用户完全透明)，给用户的感觉好像存在一个比实际物理内存大得多的存储器。虚拟存储器的大小由计算机的地址结构决定，并非是内存和外存的简单相加。
  虚拟存储器具有以下三个主要特征：

• 多次性，是指无需在作业运行时一次性地全部装入内存，二是允许被分成多次调入内存运行。
• 对换性，是指无需在作业运行时一直常驻内存，二是允许在作业的运行过程中，进行换入和换出。
• 虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。

虚拟内存技术的实现
主要有三种实现方式：请求分页存储管理、请求分段存储管理、请求段页式存储管理。
虚拟内存的实现需要建立在离散分配的内存管理方式的基础上，不管是哪种实现方式，都需要一定的硬件支持。一般需要的支持有以下几个方面：

• 一定容量的内存和外存。
• 页表机制（或段表机制），作为主要的数据结构。
• 缺页中断机构。当用户程序要访问的部分未调入内存，则产生中断。
• 地址变换机构，逻辑地址到物理地址的变换。

为了实现请求分页，系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。

在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项：

• 状态为P：用于指示该页是否已调入内存，供程序访问时参考。
• 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面参考。
• 修改位M：标识该页在调入内存后是否被修改过。
• 外存地址：用于指出该页在外存上的地址，通常是物理块号，共调入该页时参考。

一个显而易见的事实是，随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，从而会降低进程的执行速度。最小物理块数是指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。

  考虑优先权的分配算法。在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额。在有的系统中，如重要的实时控制系统，则可能是完全按优先权为各进程分配其物理块的。

4.3 页面调入策略

  为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是：
(1) 系统应在何时调入所需页面： 预调页策略和请求调页策略。
(2) 系统应从何处调入这些页面：系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘(换出)，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。
3) 是如何进行调入的：每当程序所要访问的页面未在内存时(存在位为“0”)，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序

4.4 缺页中断机构

  在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺额页调入内存。此时应将缺页的进程阻塞(调页完成唤醒)，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）。
缺页中断作为中断同样要经历：保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤，但与一般的中断相比，它有以下两个明显的区别：

• 在指令执行期间产生和处理中断信号，而非一条指令执行完后，属于内部中断。
• 一条指令在执行期间，可能产生多次缺页中断。

4.5 地址变换机构

  请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的。
在进行地址变换时，先检索快表：

• 若找到要访问的页，便修改页表项中的访问位（写指令还须重置修改位），然后利用页表项中给出的物理块号和页内地址形成物理地址。
• 若未找到该页的页表项，应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已调入内存，未调入则产生缺页中断，请求从外存把该页调入内存。

4.6 页面置换算法

  在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏将直接影响到系统的性能。

4.6.1 最佳(Optimal，OPT)置换算法

  最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。

  该算法是无法实现的，但是会利用该算法去评价其它算法。

4.6.2 先进先出(FIFO)页面置换算法

  FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。

  FIFO算法会差生所分配的物理块数增大而页故障数不减反增的异常现象，这是Belady于1969年发现的，称为Belady异常。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远也不会出现Belady异常。

  淘汰最先进入内存的页面，但可能那些页面也会被再次使用。所以这个算法也不太行。

4.6.3 LRU(Least Recently Used)最近最久未使用置换算法

  FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。
  LRU算法选择最近最长时间未被访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

  可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程，它分有五个物理块，所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，6

  LRU算法性能较好，但需要寄存器和栈的硬件支持。主要代价来自于页面排序。

4.6.4 时钟（CLOCK）置换算法

  LRU算法的性能接近OPT，但实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK的变体。因为算法要循环扫描缓冲区，像时钟一样转动，所以叫做CLOCK算法。
  简单CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，它的使用位也被置为1。对于页面替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一帧替换；如果所有帧的使用位均为1，则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used，NRU)算法。
CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOKC算法更加高校。在使用位的基础上再增加一个修改位。则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一(u为使用位，m为修改位)：

• 最近未被访问，也未被修改(u=0,m=0)
• 最近被访问，但未被修改(u=1,m=0)
• 最近未被访问，但被修改(u=0,m=1)
• 最近被访问，被修改(u=1,m=1)

算法执行如下的操作步骤：

• 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧（u=0，m=0）用于替换。
• 如果上一步失败，则重新扫描，查找（u=0，m=1）的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置为0.
• 如果上一步失败，指针将回到它的初始位置，并且集合中所有帧的使用位均为0。重复第一步，并且如果有必要，重复第二步。这样将可以找到供替换的帧。

  改进型的CLOCK算法优于简单的CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。

  操作系统中使用任何经过优化而有效的页面置换算法都有一个原则，就是尽可能保留曾经使用过的页面，而淘汰未使用的页面，认为这样可以在总体上减少换页次数。CLOCK算法只考虑到是否被访问过，那么被访问过的当然可能留下，未使用过的就淘汰，而改进型CLOCK算法把使用过的页面又细分了一下，分为使用过但未修改过的和使用过而且修改过，所以，如果有未使用过的页面，那么当然首先把它换出，如果全部页面都使用过，当然优先把未修改过的页面换出。

4.7 抖动

  由于请求分页式虚拟存储器系统的性能优越，在正常运行情况下，它能有效地减少内存碎片，提高处理机的利用率和吞吐量，故是目前最常用的一种系统。但如果在系统中运行的进程太多，进程在运行中会频繁地发生缺页情况，这又会对系统的性能产生很大的影响，故还须对请求分页系统的性能做简单的分析。
在页面置换过程中的一种最糟糕的情形时，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。

  由于虚拟存储器系统能从逻辑上扩大内存，这时，只需装入一个进程的部分程序和数据便可开始运行，故人们希望在系统中能运行更多的进程，即增加多道程序度，以提高处理机的利用率。但处理机的实际利用率却如图中的实线所示。

产生“抖动”的原因：

  频繁发生缺页中断的主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提高系统效率。发生“抖动”的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。

4.8 工作集

  工作集（驻留集）是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。
  工作集模型的原理是：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有的工作集之和增加以至于超过了可用物理块的总数，那么操作系统就会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

  因此，正确选择工作集的大小，对存储器的利用率和系统吞吐量的提高，都将产生重要影响。

五、总结

  用于多道程序操作系统的存储管理算法种类很多， 包括从最简单的分区方法到复杂的段页式管理。 在一个特定系统中采用什么策略的决定性因素是硬件提供的支持。由 CPU 生成的所有地址都必须进行合法性检查，并尽可能映射到物理地址上，由于效率原因，这种检查用软件不能实现，因此必须用硬件来完成。
  各种存储管理算法（如常驻监控程序、MFT、MVT、分页、分段以及段页结合） 在很多方面各有差别， 在比较不同存储管理算法时主要是从硬件支持、 性能、碎片、重定位、交换、共享和保护这七个方面来考虑。
  虚拟存储技术允许把大的逻辑地址空间映射到较小的物理内存上， 这样就提高了多道程序并发执行的程度，增加了 CPU 的利用率。
  请求分页式存储管理是根据实际程序执行的顺序，动态申请存储块的，并不是把所有页面都放入内存中。这种方式允许一个程序，即使它的整个存储映像并没有同时在内存中，也能正确运行，只要缺页率足够低，其性能还是很好的。 请求分页可用来减少分配给一个进程的块数，这就允许更多进程同时执行，而且允许程序所需内存量超出可用内存总量。所以，各个程序是在虚拟存储器中运行的。
当总内存的需求量超出实际内存量时，为释放内存块给新的页面，需要进行页面淘汰。有各种页面淘汰算法可供使用，例如：FIFO 算法、OPT 算法、LRU算法等。
  除了页面替换算法外，还需要块分配策略。分配可以是固定的，如局部页面替换，也可以是动态的，如全局替换。工作集模型就是一个常用的块分配策略。如果一个进程的内存块数不足以应付工作集的大小，那么它就发生抖动。
   段式虚拟存储管理是在分段管理基础上加入虚拟存储技术形成的， 一个作业的各个模块可根据调用需要进行动态连接和动态装入。把段页式存储管理和虚存技术结合起来，就形成了带虚存的段页式系统，它兼顾了分段式存储管理在逻辑上的优点和请求调页式存储管理在存储管理方面的长处，是最通用、最灵活的方式。
  内存管理是操作系统中很重要的一部分，要熟悉各种概念，理解掌握各种内存管理方法以及它们的特点。掌握并会应用各种内存置换算法解决相关的问题。

参考资料：
1、《王道操作系统2019》
2、操作系统第六篇【存储器管理】

最后

以上就是危机小熊猫为你收集整理的【操作系统】内存管理知识一、存储器的基础知识二、连续分配存储管理方式三、非连续分配存储管理方式四、虚拟内存管理五、总结的全部内容，希望文章能够帮你解决【操作系统】内存管理知识一、存储器的基础知识二、连续分配存储管理方式三、非连续分配存储管理方式四、虚拟内存管理五、总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。