MemoryManage.md

早期的计算机系统中，主存容量很小，虽然主存中仅存放一道用户程序，但是存储空间放不下用户进程的现象也经常发生，这一矛盾可以用覆盖技术来解决。

覆盖的基本思想是：由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

覆盖技术的特点是打破了必须将一个进程的全部信息装入主存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行。

随着计算机硬件的飞速发展，内存容量也在不断增长，但是仍然不可能将所有用户进程和系统所需要的全部程序和数据放入主存中，所以操作系统必须将内存空间进行合理地划分和有效地动态分配。操作系统对内存的划分和动态分配，就是内存管理的概念。

内存管理的功能有：

• 内存空间的分配与回收：由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率。
• 地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
• 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
• 存储保护：保证各道作业在各自的存储空间内运行，互不干扰。

内存分配管理

现代系统都是多任务系统，我们的进程是在内存中运行的，内存是有限的，我们如何保证可以安全而又高效的在有限的内存中运行多个程序呢？

如果将物理地址直接暴露给进程会带来一些问题：

1. 进程可能会访问禁止访问的空间，如操作系统的地址
2. 运行多个进程是困难的

于是系统给每个进程抽象出一个地址空间。地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间。

在用户空间中，是不能直接操作物理地址，其所能看到的是逻辑地址，通过地址重定位，来达到逻辑地址和物理地址之间的映射。形式化为：

p=f(l,Pi)

其中 l 为逻辑地址，p为物理地址，Pi 表示某个进程。f 为映射算法。为了同时将多个进程保存在内存中以便允许多道程序设计，必须有合理的方案来将内存分配给不同的进程。

连续分配

连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续区。一段时间内只能有一个进程在内存中，因此内存利用率低。内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。这种方式的优点是简单、无外部碎片，可以釆用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。

固定分区。最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中，选择适当大小的作业装入该分区，如此循环。

这种分区方式存在两个问题：一是程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存空间；二是主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存分区空间，这样分区内部有空间浪费，这种现象称为内部碎片。

［内部碎片］

可变分区。根据进程的需要，把内存空间分割出一个分区，分配给进程，剩余的部分成为新的空闲区。动态分区在开始分配时是很好的，但是之后会导致内存中出现许多小的内存块。随着时间的推移，内存中会产生越来越多的碎片，内存的利用率随之下降。这些小的内存块称为外部碎片，指在所有分区外的存储空间会变成越来越多的碎片，这与固定分区中的内部碎片正好相对。

在进程装入或换入主存时，如果内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用。动态分区中有以下几种分配策略：

• 首次适应算法(First Fit)：在空闲区链表中从头开始查找符合申请内存大小的块，直到找到满足条件的为止，该算法不断的从头开始试验申请，所以大部分使用的都是低地址空间的内容，从而留出了高地址空间来满足大的申请需求，但是缺点是会在较低的地址空间中频繁的申请和释放导致低地址空间中的内存碎片，而且每次都查找都从头开始，查找效率比较低。
• 最佳适应算法(Best Fit)：先按照内存块的空闲区大小从小到大进行排序，排序后，每次从头开始匹配，这样匹配出来的结果肯定是最优的，但实际因为比较符合申请内存的大小，会出现很多较小的内存碎片无法使用，并且每次分配后都要重新排序，开销比较大。
• 最坏适应算法(Worst Fit)：按照内存块的空闲区从大到小进程排序，排序后，有进程申请内存时，将表头最大的内存块分配给它，这样如果不能分配则所有不能分配，且将大内存分配给它，若只占用一小部分还可以进行二次分配。
• 下次适应算法(Next Fit)：它是首次适配算法的一个改进，它每次从上一次适配的地方开始向下查找，不需要每次都从头开始，此算法使得内存使用均匀，但是不会有大的内存块来满足内存分配。

非连续分配

非连续分配允许一个程序分散地装入到不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。

分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

基本分页管理方式

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

分页存储的几个基本概念：

• 页面。进程中的块称为页(Page)，内存中的块称为页框（Page Frame，或页帧）。外存也以同样的单位进行划分，直接称为块(Block)。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。
• 页面大小。为方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，如果页面太小，会使进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；页面过大又会使页内碎片增大，降低内存的利用率。
• 地址结构。分页存储管理的逻辑地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量W。地址长度为32位，其中011位为页内地址，即每页大小为4KB；1231位为页号，地址空间最多允许有2²⁰页。
• 页表。为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般存放在内存中。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。

为了将将逻辑地址转换为内存中物理地址，需要进行地址转换，整个地址变换过程均是由硬件自动完成的。具体如下图

例如，若页面大小L为1K字节，页号2对应的物理块为b=8，计算逻辑地址A=2500 的物理地址E的过程如下：P=2500/1K=2，W=2500%1K=452，查找得到页号2对应的物理块的块号为 8，E=8*1024+452=8644。

由上面介绍的地址变换过程可知，若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存：一次是访问页表，确定所存取的数据或指令的物理地址，第二次才根据该地址存取数据或指令。显然，这种方法比通常执行指令的速度慢了一半。

为此，在地址变换机构中增设了一个具有并行查找能力的高速缓冲存储器——快表，又称联想寄存器(TLB)，用来存放当前访问的若干页表项，以加速地址变换的过程。

此外每个进程引入了页表，用于存储映射机制，页表太大的话，内存利用率会降低。以32 位逻辑地址空间、页面大小4KB、页表项大小4B为例，若要实现进程对全部逻辑地址空间的映射，则每个进程需要2²⁰，约100万个页表项。也就是说，每个进程仅页表这一项就需要4MB主存空间，这显然是不切实际的。而即便不考虑对全部逻辑地址空间进行映射的情况，一个逻辑地址空间稍大的进程，其页表大小也可能是过大的。

将页表映射的思想进一步延伸，就可以得到二级分页：假设将页表的10页空间再进行地址映射，建立上一级页表，用于存储页表的映射关系。这里对页表的10个页面进行映射只需要10个页表项，所以上一级页表只需要1页就足够（可以存储2¹⁰=1024个页表项）。在进程执行时，只需要将这1页的上一级页表调入内存即可，进程的页表和进程本身的页面，可以在后面的执行中再调入内存。

建立多级页表的目的在于建立索引，这样不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项。

分段管理方式

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

段式管理方式按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序、两个子程序、栈和一段数据组成，于是可以把这个用户进程划分为5个段，每段从0 开始编址，并分配一段连续的地址空间（段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的）。其逻辑地址由段号S与段内偏移量W两部分组成。

在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在段式系统中，段号和段内偏移量必须由用户显示提供，在髙级程序设计语言中，这个工作由编译程序完成。

每个进程都有一张逻辑空间与内存空间映射的段表，其中每一个段表项对应进程的一个段，段表项记录该段在内存中的起始地址和段的长度。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。可见，段表用于实现从逻辑段到物理内存区的映射，如下图所示。

和基本分页存储一样，分段存储也需要进行地址转换。为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址F和段表长度M。其从逻辑地址A到物理地址E之间的地址变换过程如下：

段页式管理方式

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。

在段页式系统中，作业的地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的存储块，对内存的分配以存储块为单位，如下图所示：

为了实现地址变换，系统为每个进程建立一张段表，而每个分段有一张页表。段表表项中至少包括段号、页表长度和页表起始地址，页表表项中至少包括页号和块号。此外，系统中还应有一个段表寄存器，指出作业的段表起始地址和段表长度。注意：在一个进程中，段表只有一个，而页表可能有多个。

在进行地址变换时，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。如下图所示，进行一次访问实际需要三次访问主存，这里同样可以使用快表以加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。

虚拟存储器

前面的内存管理策略都是为了同时将多个进程保存在内存中以便允许多道程序设计。它们都具有以下两个共同的特征：

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

• 当作业很大，不能全部被装入内存时，将使该作业无法运行；
• 当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。

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

由以上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。

现代系统为了更好地管理存储器并且保证安全，提供了一种对主存的抽象概念，叫做虚拟存储器。为了理解虚拟内存技术的思想，首先必须了解计算机中著名的局部性原理。局部性原理表现在以下两个方面：

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

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

虚拟存储器提供了三个重要的能力：

1. 它将内存看为是磁盘的高速缓存，在内存中只保存活跃的区域，并根据需要在内存和磁盘中来回传送数据，使得主存的使用更加高效。
2. 它为每个进程抽象出了一致的内存空间，使得多进程可以更加简单的运行，简化了存储器的管理。
3. 它保护了每个进程可以单独、高效的运行，每个进程的地址空间不会被其他进程破坏。

虚拟存储的工作原理如下：

每个进程都有一个抽象的地址空间，进程1访问物理内存中的数据时，它获得的地址是抽象的虚拟地址，需要将虚拟地址转化为物理地址。那么就需要硬件**MMU(Memory Management Unit)**来进行地址转换从而得到物理内存的地址。然而物理内存是有限的，如果每个进程都要全部加载到内存中内存肯定不够。

实际上不需要把进程全部内容加载到内存中去，根据二八定理，常用的内容占全部的百分之二十，所以只需要将每个进程常用的加载到内存中，不用的我先暂存到磁盘，如果需要它时在从磁盘中将它加载出来，这就是上图中内存和磁盘的连线关系。

虚拟内存中，允许将一个作业分多次调入内存。釆用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式：

• 请求分页存储管理。
• 请求分段存储管理。
• 请求段页式存储管理。

不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：

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

请求分页存储

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。

请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页面不在内存的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了一些字段，页表项中各个位的作用如下：

1. 页号
2. 块号（页框号）
3. 中断位: 用于判断该页是不是在内存中，如果是0，表示该页不在内存中，会引起一个缺页中断。
4. 保护位(存取控制位): 用于指出该页允许什么类型的访问，如果用一位来标识的话，1表示只读，0表示读写
5. 修改位(脏位): 用于页面的换出，如果某个页面被修改过(即为脏),在淘汰该页面时，必须将其返回写回磁盘，反之，可以直接丢弃该页面
6. 访问位：不管是读还是写(read or set),系统都会设置该页面的访问位。他的值会帮助操作系统在发生缺页中断时，选择要被淘汰的页，即用于页面置换
7. 高速缓存禁止位（辅存地址位):对于映射到设备寄存器而不是常规内存的页面来说，这个位很重要； 例如： 操作系统正在循环等待着某个I/O设备对他的指令做出响应，保证硬件是不断的从设备中读取数据而不是访问一个旧的被高速缓存的副本是非常重要的，通过这一位就可以禁止高速缓存。

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒)，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存)。

页面置换

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

常见的页面调度算法：

1. 随机算法rand（Random Algorithm）

   利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单，而且容易实现。但是，这种算法完全没用利用主存储器中页面调度情况的历史信息，也没有反映程序的局部性，所以命中率较低。

2. 先进先出调度算法（FIFO）

   先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，它没有反映程序的局部性，因为最先调入主存的页面，很可能也是经常要使用的页面。

3. 最近最少使用算法LRU（Least Recently Used Algorithm）

   根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少使用在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。

4. 最近最不频繁使用算法 LFU（Least Frequently Used Algorithm ）

   由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。

［LRU 缺页次数］
［缺页率计算］
［缺页替换影响效率］

概念总结

主存、辅存、虚拟存储

概括的说，CPU对所需要的数据进行计算时，要求很高的存储速度，且不需要能永久保存这些数据，高速存储设备的成本很高。但其他设备对存储速度的要求不像CPU这么高，一般要求永久保存数据。一般低速的存储设备就可以满足，且低速的存储成本也低。

所以有主存和辅存之分：

• 内存（主存）直接给CPU提供存储，高速，低容量，价格贵，不能永久保存数据，断电消失，需要从辅存中重新调入数据。
• 外存（辅存）给主存提供数据，低速，大容量，价格低，能永久保存数据。

所以更高缓存的CPU和更大的内存能够大大提升系统的性能。

• 常见主存有：CPU的高速缓存，电脑的内存条。
• 常见辅存有：硬盘、光盘、U盘、磁盘、移动硬盘等等。

虚拟存储：根据程序执行的互斥性和局部性两个特点，允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好像计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。

虚拟存储（Storage Virtualization）是指将多个不同类型、独立存在的物理存储体，通过软、硬件技术，集成转化为一个逻辑上的虚拟的存储单元，集中管理供用户统一使用。这个虚拟逻辑存储单元的存储容量是它所集中管理的各物理存储体的存储量的总和，而它具有的访问带宽则在一定程度上接近各个物理存储体的访问带宽之和。

［虚拟存储的目的］

更多阅读

浅谈计算机中的存储模型（一）存储体系
浅谈计算机中的存储模型（二）物理内存
浅谈计算机中的存储模型（三）虚拟存储器
分段，分页与段页式存储管理
探究操作系统的内存分配（malloc）对齐策略
Linux内存寻址之分页机制