Linux虚拟内存

一、局部性原理

在《详解操作系统分页》中，通过将部分页表放入到TLB中加快访问速度，这些页表称为快表，但哪些页表应该放入到TLB(Cache)中呢？

1.1 缓存Cache(一般的)

CPU访问数据的时候，首先到相应的缓存里面查找数据，如果缓存中没有，则访问内存获取，同时将从内存中获取到的数据存入到缓存中

Cache结构

如上图所示，假设Cache的每一格是8Bytes，每一个缓存行是64Bytes，Cache的读写是以缓存行(CacheLine)为单位的，当CPU从内存读取数据时，并不只是将所需要的数据读取到Cache中，而是将读取到的数据的起始位置到后面64Bytes的数据当作一个缓存行写入到内存中。例如内存中放有一个64Bytes*8的二维数组，CPU每次行列顺序读取数组，读一次内存就可以将一行的数据加载进内存，这样可以加快CPU的访问速度

修改缓存数据

读缓存不会有数据不一致的情况，但是写缓存，就会导致缓存里面的数据与内存中的数据不一致，又如下两种方案：

Write through(直接写)

修改缓存数据的同时修改内存数据，这种方式会导致CPU执行效率变低
Write back(回写)

先只修改缓存数据，直到该数据要被清除缓存时在修改内存中的数据，保证数据最终一致性

清除缓存数据

缓存的容量很小，当缓存满的时候，就需要将缓存中的数据淘汰，装入新的数据

对于淘汰算法，将会在下面虚拟内存的页面置换算法中详解介绍

1.2 局部性原理

对于一个程序而言，有些代码可能永远都不会被访问，而有些局部数据会经常访问，但是将哪些数据放入内存中？

局部性原理提供了以下方案

时间局部性(Temporl locality)

如果某个信息这次被访问，那它有可能在不久的未来被多次访问
空间局部性(Spatial locality)

如果某个位置的信息被访问，那和它相邻的信息也有可能被访问到
内存局部性(Memory locality)

访问内存时，大概率会访问连续的块，而不是单一的内存地址，其实就是空间局部性在内存上的体现
分支局部性(Branch locality)

计算机大部分指令是顺序执行，顺序执行和非顺序执行的比例大致是5:1，顺序执行的指令是空间连续的
等距局部性(Equidistant locality)

如果某个位置被访问，那和它相邻等距离的连续连续地址极有可能被访问到

二、虚拟内存

2.1 部分装入和部分对换

部分装入
- 进程运行时仅加载部分进入内存，而不必全部装入
- 其余部分暂时存放在swap space
部分兑换
- 可以将进程部分对换出内存，用以腾出内存空间
- 对换出的部分暂时存放在swap space

缓存—主存—辅存之间的关系

2.2 虚拟内存概念

Virtual Memory is a technique that allows the execution of processes that are not completely in Memory

虚拟内存是一种允许执行进程无需完全在内存中技术(部分装入)
One major advantage of this scheme is that programs can be larger than physical memory

这种方案最大的优势是程序总内存可以比实际的物理内存大(4G内存可以运行8G的程序)
Further,virtual memory abstracts main memory into an extremely large,uniform array of storage,separating logical memory as viewed by the user from physical memory

虚拟内存技术将主存抽象成一个很大的、统一的数组，将逻辑内存和物理内存分离开来(对用户包括开发人员来说，只需要关注逻辑内存，无需关注物理内存)
This technique frees programs from the concerns of memory-storage limitations

这种技术将程序从内存存储的限制中解放出来，程序不需要再关心内存不够用的情况

三、请求调页

在《详解操作系统分页》的4.5节多级页表中展示了Linxu系统采用的是四级页表的方式，而不是分段的方式进行内存管理

虚拟内存技术是基于分页来实现的

3.1 DEMADN PAGING

With demand-paged virtual memory,pages are loaded only when they are demanded during program execution

在请求调页的虚拟内存中，只有当执行程序请求的时候，页面才会被加载进内存
Pages that are never accssed are thus never loaded into physical memory

从来没有被请求访问的页面也因此从来不会被加载进内存

如上图所示，物理内存中只存了程序A、C、F三个页，当程序需要H页时，发现页表中页表号7对应的页框为空，则需要将H页从磁盘中加载进物理内存的页框中，同时更新页表中对应的页框号和valid-invalid bit，这整个过程就称为调页。

3.2 请求调页步骤

上图中的load M对应的是Logic Memory，也是一个page存储在内存中

1、根据逻辑地址表从页表中获取对应的页表项

2、页表项为i(invalid)，则陷入page fault(缺页中断)

3、操作系统收到中断后，查找磁盘中的请求页

4、将磁盘上的页加载进主存中空闲的页框

5、更新页表的页表项

6、返回逻辑地址对应的指令

3.3 请求调页的性能

假设访问内存时间为ma，处理一次缺页中断的时间记作page fault time，令p为缺页中断的出现几率，则有效访问时间的计算公式：

effective access time = ma * (1-p) + page fault time * p
如果ma = 200ns，page fault time = 8ms，p=0.001，则

effective access time = 8200ns

缺页中断率P对性能影响重大

四、页面置换算法

不论是内存还是缓存，都有存储空间被用完的时候，如果这时候又有新的数据需要加载进内存或缓存，那么需要将哪些数据从内存或缓存中移除呢，这就是页面置换算法需要解决的问题

4.1 页面置换

当进程在执行过程中出现了缺页中断，在请求调页的时候发现内存已经没有空闲的页框可用，操作系统在此时会做出一个处理：页面置换

将内存中的页从页框移除转移到磁盘中存储，这个过程就是前面说到的swap out过程

页面置换过程

1、将内存页框中的页交换至磁盘

2、更新该页在页表中的状态(变成不可用)

3、将请求的新页从磁盘加载进内存

4、更新新页在页表中的状态为可用

4.2 FIFO(先进先出)

总是淘汰最先进入内存的页面，因为它呆在内存中的时间最久
假设操作系统给一个进程分配了3个页框，按照下面的页号顺序访问，一共需要访问20个页，计算缺页中断率P

进程一共只有3个页框，前面页号7、0、1都是通过缺页中断加载进内存的，当访问第四个2号页时，页框中没有，发生缺页中断，按照FIFO的规则，需要将7号页交换出内存，将2号页加载进内存；当访问第五个0号页时，内存中有该页则直接访问，；当访问第六个3号页时，再次发生缺页中断…………依次类推直到访问到最后一个页，一共发生了15次缺页中断

缺页中断率P = 15 / 20 = 75%

这种方案是最简单、最容易被实现的

4.3 OPTIMAL(最优)

总是淘汰将来最长时间不会再使用的页面

按照上面FIFO的例子计算缺页中断率P

前面三个页7、0、1加载进内存发生三次缺页中断，当需要使用2号页时，则根据后面需要访问页的面顺序，发现0页号在2号页后面就会被使用，然后是1号页被使用，最后才是7号页被使用，那么按照OPTIMAL规则应该将7号置换出内存，将2号页加载进内存…………依次类推直到访问到最后一个页，一共发生了9次缺页中断

缺页中断率P = 9 / 20 = 45%

这种方案现实中是无法实现的，操作系统没办法预测将来需要哪些页

4.4 LRU(最近最少使用)

LRU(LEAST RECENT UNUSED)总是淘汰最近最少使用的页面

根据以前的页面使用的情况，将最近最少使用的页面置换出内存

按照上面FIFO的例子计算缺页中断率P

前面三个页7、0、1加载进内存同样发生三次缺页中断，当需要使用2号页时，按照LRU的规则，发现7号页时最近最少使用，将其置换出内存，将2号页加载进内存，接下来访问0号页，在内存中可以直接访问，此时内存的页框中有0、1、2三个页，当需要访问3号

页时，发现1号页是最近最久没有使用的，将其置换出内存…………以此类推直到访问到最后一个页，一共发生了12次缺页中断

缺页中断率P = 12 / 20 = 60%

另外还有一个算法Clock(second Chance)，该算法是基于LRU实现的

五、系统抖动

5.1 THRASHING(抖动)

If the process does not have the number of frames it need to support pages in active use,it will quickly page-fault.At the point,it must replace some pages.However,since all its pages are in active use,it must replace a page that will be needed again,and again,replacing pages that it must bring back in immediately

如果进程没有足够的页框去存放常用页，就会经常陷入缺页中断，这时候，必须将其中一些页置换出内存，然而所有的页都是常用，下次又要使用刚刚置换出去的页，它又要通过缺页中断被再次加载进内存，往复循环。
This high paging activity is called thrashing.A process is thrashing if it is spending more time paging than executing

这种高频率的调页称为抖动，进程抖动会造成CPU处理消耗更多的时间来处理缺页中断而不是执行程序

5.2 系统抖动的原因

并发进程数量过多

下图展示了操作系统多道程序的数量与CPU使用率的关系，一开始随着并发进程数量的增加，CPU使用率越来越高，但得到一定的程度之后，进程数继续增加，每个进程分配的页框数就变小了，不足以存放常用页，就会导致频繁的缺页中断，CPU利用率急剧下降
进程页框分配不合理

假设进程A常用页有5个，但操作系统只给其分配了3个页框，也会导致频繁的缺页中断，消耗CPU时间

5.3 解决方案

PFF(page fault frequency) 称作页面故障率，基于下图的数据，可以实施一个防止抖动的策略：操作系统动态调节分配给进程的页框数量

上图展示了给进程分配的页框数量和缺页中断率的关系，给进程分配的页框越多，缺页中断率就越低，但也不能把所有页框都分配给少量的几个进程导致其他进程出现系统抖动，于是操作操作系统会把进程的页框数量控制在上图的upper bound 和lower bound之间，将整个系统中进程的缺页中断率控制在一个可控的范围。