存储器及其管理方式

“计算机存储器包括主存和辅存，本文中存储器管理的对象主要是主存，也称内存。它的主要功能包括分配和回收主存空间、提高主存利用率、扩充主存、对主存信息实现有效保护。”

—

存储器

存储器是计算机系统的重要组成部分，我们知道处理器直接决定着计算机性能的好坏，存储器肩负着为处理器的高速运算提供数据中转、暂存的重任。所以，必须整体提升处理器和存储器的效率，才能将计算机的整体性能得到提升。

随着CPU的高速发展，存储器也在不断地发展，尽管如此，仍不能满足现代软件的发展需求，因此，存储器仍然是一种紧缺资源。如何对存储器进行分配和管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。

通常计算机的存储层次具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在现代大多数计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等六层。如下图：

在计算机系统存储层次中，对于不同的存储，所采用的访问机制是不同的，所需耗费的时间也是不同的。存储层次越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。进程可以在时钟周期内使用一条load或store指令对主存进行访问，但对辅存的访问则需要通过I/O 设备来实现，因此，访问中将涉及到中断、设备驱动程序以及物理设备的运行，所耗费的时间也远远高于对主存的访问。另外，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在；固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。

主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器，CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。CPU 与外围设备交换的信息一般也依托于主存储器地址空间。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。

寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。

高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。根据程序执行的局部性原理，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。

通常，进程的程序和数据是存放在主存储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。当CPU访问一组特定信息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主存，否则，再从主存中读出信息。

磁盘缓存：由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。

磁盘作为保存大量数据的存储设备，存储数据的数量级可以达到几百到几千兆字节，不过，从磁盘读取信息时间为毫秒级，比主存、寄存器慢很多。

可移动存储介质（包括U盘、移动硬盘、软盘、光盘、存储卡），具有体积小、容量大的特点，作为信息交换的一种便捷介质，如今已经得到广泛应用。

实际上，存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU寄存器保存着最常用的数据。高速缓存存储器作为一部分存储在相对慢速的主存储器中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘上的数据的缓冲区域。

注：本文中存储器管理的主要对象是内存，后续将会有关于磁盘、文件等存储的介绍。

02

—

内存管理

在计算机系统内，进程可以看成是程序的抽象，程序的功能是由多个进程的执行来实现的，而主存是用于保存进程运行时的程序和数据，在进程整个生命周期中（创建、执行、结束），内存都扮演着非常重要的角色。

程序需要经过编译、链接、装入等过程，才能变成可执行程序。源程序经过编译后，可得到一组目标模块；再利用链接程序将这组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块；由装入程序将装入模块装入内存。从进程开始到结束，内存需要进行分配和回收，以便程序的运行和空间的回收。那如何分配内存空间呢？通常包括连续分配和离散分配。

连续分配指为用户进程分配的必须是一个连续的内存空间。主要包括单一连续分配方式、固定分区分配、动态分区分配、伙伴系统、哈希算法、可重定位分区分配、对换等。具体介绍参见《计算机操作系统》，其中对换技术为了解决内存紧张问题，提高了内存的利用率，并且广泛的应用于现代的操作系统中。

连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。

如果离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式。

~分页存储方式~

页面

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0 开始，如第0 页、第1 页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框，也同样为它们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。

在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应是2 的幂，通常为512 B～8 KB。

分页的地址结构如下：

它含有两部分：前一部分为页号P，后一部分为位移量W(或称为页内地址)。

页表

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

地址变换机构

为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的基本任务是实现从逻辑地址到物理地址的转换。而页表的作用就是实现从页号到物理块号的地址映射，因此，地址变换任务是借助于页表来完成的。

由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W 拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”。

~分段存储方式~

分页存储管理方式的主要动力，是提高内存利用率，那么，引入分段存储管理方式的目的，则主要是为了满足用户(程序员)在编程和使用上多方面的要求。主要包括下述一系列需求：

方便编程

用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0 开始编址，并有自己的名字和长度。要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。

信息共享

在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。段就是信息的逻辑单位，为了实现段的共享，希望存储管理能与用户程序分段的组织方式相适应。

信息保护

信息保护同样是对信息的逻辑单位进行保护，因此，分段管理方式能更有效和方便地实现信息保护功能。

动态增长

在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切地知道数据段会增长到多大。前述的其它几种存储管理方式，都难以应付这种动态增长的情况，而分段存储管理方式却能较好地解决这一问题。

动态链接

动态链接是指在作业运行之前，并不把几个目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段(目标程序)调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。

段

分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D 及栈段S等。每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。

段表

在动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行，亦即，能从物理内存中找出每个逻辑段所对应的位置，应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但更常见的是将段表放在内存中。

地址变换机构

为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，表示段号太大，是访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后，再检查段内地址d是否超过该段的段长SL。若超过，即d>SL，同样发出越界中断信号；若未越界，则将该段的基址d 与段内地址相加，即可得到要访问的内存物理地址。

像分页系统一样，当段表放在内存中时，每要访问一个数据，都须访问两次内存，从而极大地降低了计算机的速率。解决的方法也和分页系统类似，再增设一个联想存储器，用于保存最近常用的段表项。

~段页式存储方式~

页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。如果能对两种存储管理方式“各取所长”，则可以将两者结合成一种新的存储管理方式系统。这种新系统既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样很好地解决内存的外部碎片问题，以及可为各个分段离散地分配内存等问题。把这种结合起来形成的新系统称为“段页式系统”。

段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。

上图展示出了一个作业地址空间的结构。该作业有三个段，页面大小为4 KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成。

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

在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍须再三次访问内存。

~虚拟存储器~

基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。这样，便可使一个大的用户程序能在较小的内存空间中运行；也可在内存中同时装入更多的进程使它们并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多。但须说明，用户所看到的大容量只是一种感觉，是虚的，故人们把这样的存储器称为虚拟存储器。

综上所述，虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

调页策略

为了确定系统将进程运行时所缺的页面调入内存的时机，可采取预调页策略或请求调页策略，现分述如下：

预调页策略

如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。

请求调页策略

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS 将其所需页面调入内存。由请求调页策略所确定调入的页，是一定会被访问的。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O 的启动频率。

在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘I/O 速度比文件区的高。

每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O 将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。

页面置换

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

这些算法包括：最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法、最近最久未使用(LRU)置换算法、Clock置换算法、其它置换算法（最少使用(LFU：Least Frequently Used)置换算法、页面缓冲算法(PBA：Page Buffering Algorithm)）等，具体介绍详见《计算机操作系统》。

03

—

关键概念

局部性原理

一个编写良好的计算机程序常常具有良好的局部性。也就是，它们倾向于引用临近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理，是一个持久的概念。早在1968年，Denning.P 就曾指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。这一概念，对硬件和软件系统的设计和性能都有着极大的影响。

局部性通常由两种不同的形式：时间局部性和空间局部性。在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用。在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

一般而言，有良好局部性的程序比局部性差的程序运行得更快。现代计算机系统的各个层次，从硬件到操作系统、再到应用程序，它们的设计都利用了局部性。在硬件层，局部性原理运行计算机设计者通过引入高速缓存来保存最近被引用的指令和数据项，从而提高对主存的访问速度。在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存。类似地，操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块。局部性原理在应用程序的设计中也扮演着重要的角色。例如，Web浏览器将最近被引用的文档放到本地磁盘上，利用的就是时间局部性。大容量的Web服务器将最近被请求的文档放在前端磁盘高速缓存中，这些缓存能满足对这些文档的请求，而不需要服务器的任何干预。

缓存及相关算法

缓存（cache）原本是指计算机高速缓存，用来缓解CPU与内存之间的速度差异。不过，现在缓存的概念已被扩充，用于协调两个不同硬件或程序之间的数据传输速度差异的结构。如：Redis用于缓存存储在数据库中的数据，因为直接读取数据库的成本较大，而读取redis比较快。通常缓存的空间也是有限的，无法缓存所有数据，所以需要有某种机制来更新缓存，即缓存置换。常见的缓存置换算法包括：先进先出算法、最近最少使用算法、最久未使用算法等。

地址映射

为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。从逻辑地址到物理地址的运行时映射是由内存管理单元（MMU）的硬件设备来完成。

交换

在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。为了解决这一问题，在系统中又增设了对换(也称交换)设施。所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。

缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。

1. 《计算机操作系统 第三版》
2. 《深入理解计算机系统》
3. https://zhuanlan.zhihu.com/p/34414738
4. https://tech.meituan.com/2015/01/22/linker.html
5. https://www.ezlippi.com/blog/2015/02/cache.html
6. https://mp.weixin.qq.com/s/fS5eBp84xRswtWtR3UcOxQ
7. http://luodw.cc/2016/08/13/linux-cache/
8. http://stor.51cto.com/art/201808/580956.htm
9. https://www.polarxiong.com/archives/%E5%A4%9A%E7%BA%A7%E9%A1%B5%E8%A1%A8%E5%A6%82%E4%BD%95%E8%8A%82%E7%BA%A6%E5%86%85%E5%AD%98.html