内存是计算机很重要的一个资源，因为程序只有被加载到内存中才可以运行；此外，CPU所需要的指令与数据也都是来自内存的。可以说，内存是影响计算机性能的一个很重要的因素。
随着技术的发展，现在计算机的内存容量已经有了很大的增长，但是程序大小的增长速度比内存容量的增长速度要快得多。正如帕金森定律所指出，“不论存储器有多大，程序都可以把它填满”。所以问题来了，当一个程序大小超过内存容量时，如何把调入内存中？这篇文章将总结内存管理的一些技术。
在介绍内存管理的细节前，先要了解一下分层存储器体系（一图胜千言）。
上图很清晰的描述了计算机的分层存储体系。
操作系统将这个存储体系对象抽象为一个有用的模型并管理这个模型。操作系统中管理这个模型的部分称为存储管理器。它负责管理内存，记录哪些内存是正在使用的，哪些是空闲的；在进程需要时为其分配内存，在进程使用完后释放内存。
分层存储体系这个模型并不是一开始就有的，而是随着计算机的发展来一步步完善，最终才形成了现在的体系。所以，分层存储体系的发展历史也是这篇文章的一个线索。
无存储器抽象
早期的计算机是没有存储器抽象的，直接将物理内存暴露给程序。可以把内存想象成中医中放草药的盒子，每个盒子都有标记放的是哪种草药，当有两种草药同时放到一个盒子中去，就会出现医疗事故。
所以，这种情况下的内存管理是有问题的：
- 在内存中同时运行两个程序是不可能的。一个程序在1000位置写入一个新的值，将会被新程序写的值所覆盖。这个跟一个盒子里是不能同时放两种草药是一样的
重定位问题：假设内存中有两个程序A、B，如果使用绝对物理地址，那么，在程序B
执行JMP 28指令时，就会跳转到A程序的ADD指令，引发程序崩溃。B程序想要的跳的指令时CMP。CMP 指令地址是16412，而B使用了28,28是绝对地址。
47352085344489238.jpg
存储器抽象--地址空间
为了解决保护和重定位的问题，人们创造了一个新的内存抽象：地址空间。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他的地址空间。
地址空间在现实生活中有多的应用。比如电话的区号，北京是010，上海是021。这样即使同一个电话号码，区号不同也能区分开来。
考虑上个例子中的程序A、B，如果使用地址空间的话，B程序跳转28，就不会跳转到A程序的指令了。因为两个28分别属于不同地址空间。
了解地址空间这个概念，接下来看一下计算机是如何实现将两个28映射到不同地址空间里的。
经典的办法是给每个CPU配置两个寄存---基址寄存器和界限寄存器。基址寄存器记录程序的起始物理地址，界限寄存器记录程序的长度。
还是用这个图举例，程序A的基址为0，界限为16384，程序B基址为16384，界限值为32768。每次一个进程访问内存时，取一条指令，读或写一个数据字，CPU硬件会把地址发送到内存总线前自动把基址值加到进程发出的地址上。比如，进程A发出的访问地址是28，而A的基址是0，那么，A实际访问的物理地址就是28，而进程B的基址为16384，加上28，得到的地址为16412，进程B实际访问的地址是16412.这样就解决了之前提到过的绝对物理地址所带来的问题。
按照帕金森定律，“不论存储器有多大，程序都可以把它填满”。当程序大小超过内存容量时，计算机应该如何管理内存？
有两种处理内存超载的通用方法。一种是交换技术，即把一个进程完整调入内存，使该进程运行一段数据啊in，然后存回磁盘。空闲进程主要存在于磁盘上，所以，当他们不运行的时候不会占用内存。另一种是虚拟内存，该策略允许程序在只有一部分被调入内存的情况下运行。
我们重点关注虚拟内存。大体包含以下内容：
- 分页
- 页面置换算法
- 分页系统的设计与实现问题
- 分段
- 分段的问题
- 分段与分页的结合
虚拟内存基本思想是每个程序都有自己的地址空间，这个空间被分割成多个块。每个块称作一页或页面。每一页有连续的地址范围。这些页被映射到物理内存，但是并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件执行必要的映射。当程序引用到一部分不在物理内存中的的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
- 分页：
1、虚拟地址空间：由程序产生的地址称为虚拟地址，它们构成了一个虚拟地址空间。在使用虚拟内存的情况下，虚拟地址被送到内存管理单元，然后内存管理单元将虚拟地址映射为物理内存地址。
2、虚拟地址空间按照固定大小划分成称为页面的若干单元。在物理内存中对应的单元称为页框。记录页面与页框对应关系的叫作页表。
3、举例说明虚拟地址到物理地址的映射过程：
a.程序访问如下指令：MOV REG， 0
b.将虚拟地址送到MMU
c.MMU通过虚拟地址找到对应的页表项,比如虚拟地址0落在页表项0（0~4095）
d.通过页表中虚拟地址与物理地址的映射关系，找到对应的页框，比如页框可能是2（8192~12287）。MMU把地址变换为8192，并把地址8192送到总线上。
这样就完成了虚拟地址到物理地址的转换。
4、总结：虚拟地址被划分成虚拟页号（高位部分）和偏移量（地位部分）。虚拟页号可以用作页表项的索引，以找到虚拟页面对应的页表项。由页表项找到页框号（如果有的话），然后把页框号拼接到 偏移量的高位端，已替换掉虚拟页号，形成物理地址。
一图胜千言
address.jpg
- 页面置换
当程序访问到一个未被映射的页面时，就会引发缺页中断。操作系统找到一个页框并将它的内容写入磁盘中。然后将需要访问的页面读到刚刚回收的页框中，并重新启引起缺页中断的指令。
那么，操作系统在选择页框时，依据的原则是什么呢？这就是页面置换算法。
1、最优页面置换算法：替换掉下次访问距离当前时间最长的页框。该算法无法实现，因为当缺页中断发生时，操作系统无法知道下一个页面将在什么时候被访问
2、最近未使用页面置换算法：替换掉最久没有使用的页面
3、先进先出页面置换算法：这个很好理解，就是替换掉存在时间最长的页面。这个算法有一个缺点就是可能抛弃重要的页面
4、最近最少使用页面置换算法：置换未使用时间最长的页面。这个算法非常优秀，但是很难实现。为了完全实现该算法，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是在每次访问内存时都必须更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作，即使使用硬件实现也一样费时。
5、时钟页面置换算法：后续补充。
6、工作集时钟算法：好的有效算法。后续补充。
- 分页置换存在的问题
1、页面大小带来的问题：如果页面太大，容易造成内部碎片；而页面太小，则需要的页表越大。
- 分段：
概念：分段允许程序员将内存看成由多个地址空间或段组成，段的大小是不相等的，并且是动态的。段的优点是动态的，比如堆栈段的长度在数据被压入时会增长，在数据被弹出时会减小。
分段系统中的地址转换过程如下图
485849422475090016.jpg
- 分段的问题：
1、分段会造成外部碎片。
2、如果一个 段太大，把它整个保存在内存中可能不方便甚至是不可能的
- 段页结合：
结合分段与分页的优点：分页对程序员是透明的，它消除了外部碎片，因而可以更有效地使用内存。此外，由于移入或移出内存的块是固定的、大小不等的，因而有可能开发出更精致的存储管理算法。分段对程序员是可见的，它具有处理不断增长的数据结构的能力以及支持共享和保护的能力。
段页式地址转换过程如下图：
507791915898811223.jpg
过程：
1、根据段号找到段描述符
2、检查该段的页表是否在内存中。如果在，就找到它的位置。如果不在，就产生一个段错误。
3、检查所请求虚拟页面的页表项，如果该页面不在内存中就产生一个缺页中断，如果在内存就从页表项中取出这个页面在内存中的起始地址。
4、把偏移量加到页面的起始地址上，得到要访问的字在内存中的地址。
5、进行读写操作
至此，对操作系统中的内存管理有了一个大体的了解，如内存模型对象的发展过程，每种内存管理的优缺点。同时我感受到了提出问题，解决问题这条线索也是阅读计算机书籍的一个思路。
