操作系统内存管理
操作系统内存管理的目的是将线性物理地址用抽象的逻辑地址空间，从而保护物理地址。此外，可以独立地址空间，共享内存以及虚拟化。
操作系统内存管理方式：
1、重定位；
2、分段；
3、分页；
4、虚拟存储；
就是将程序地址重定位到另一个地址。最早在连续内存管理中使用
通常来讲，连续内存分配我们地址空间生成时主要有几个节点：
1）编译 ，绝对装入
假如起始地址已知，会根据相对地址，在编译时生成绝对地址。比如最早的功能手机，都是这样的，时不允许自安装什么软件的。
2、加载
在编译时如果起始位置未知，就进行重定位。加载时，生成绝对地址。也称静态重定位
3、执行时
执行时代码可移动，实现重定位，也称为动态重定位
内存分配主要有连续和非连续内存分配两种方式。
连续是最早的内存分配方式，主要是要为程序找到一片连续的内存空间，这要求还是很高的。此外不同的连续内存分配还会出现内存利用率低，容易产生碎片等缺点。
因为，目前都是采用非连续内存分配。
基于此，非连续内存分配目标：
1、提高系统内存利用率；
2、共享某些内存；
3、支持动态加载和动态链接；
选择非连续内存块大小方法主要有段式和页式两种方法。
段式存储管理：
将进程地址空间划分成多个段，比如数据段，代码段，堆栈等等。
段和段的地址可以是不连续的，但段内的是一块连续空间。每个段的地址都是从0开始，并有偏移地址。逻辑地址由二元组 (s,addr) 表示。其中 s 表示段号，addr 表示段内偏移量。
整个进程地址空间是个二维数组。
此外，系统会为每个进程维护一个段表.当我们在执行程序时，会首先根据段号到进程段表中找到段基址和长度，然后MMU会判断是否越界，如果没问题，会根据基址和偏移得到实际物理地址。
段式存储可以实现信息的保护和共享。
MMU会对检查段表项的保护位，如果越界就会报异常。此外，使用可重入代码时，只需在段表中为其设置一个段表项，并将执行时用到的部分数据copy到局部数据区，可以实现信息共享。
页式存储管理
页帧Frame：物理地址分配的基本单元；
页面Page：逻辑地址分配的基本单元；
要完成页面到页帧的转换需要通过页表，页表保存了逻辑地址和物理地址的映射关系。页表的机制会存储在页表基址寄存器中，它会随着进程的运行不断地变化。
页分配相比于段，可以让进程地址空间更不需要连续空间，不会产生碎片化。但其一个问题是，由于页比较小，可能使得页表变得特别大，使得访问性能变差。不过我们可以通过缓存（块表TLB）或者多级页表来提高访问效率。
多级页表如果是所有页表都不存在的话，实际存储空间并没有减少。但是在实际使用中，进程不需要使用全部地址空间，有些页表可以暂时不存在。比如都过存在位表示某个页表不存在，这样是可以有效减少页表的存储。
下面是一个二级页表的示例。一级页表的页表项是二级页表的起始页号，再加上偏移就可以得到实际物理地址。
段页式存储管理
该种方法式段式和页式的结合。每个逻辑地址由段号，页号以及页内偏移地址组成。
首先会根据段号在段表中找到段表项。根据段表项找到页号，根据页号在对应页表（根据页表起始位置寻址）中找到物理存储块，根据偏移地址算出实际物理地址。
虚拟存储
上面讲了段式、页式、段页式各种内存空间分配方法，但是他们都会存在一个问题，即物理内存不够，他们都需要一次性全部加载到内存中。虚拟存储就是为了解决这个问题，它会利用外存，且允许部分程序和数据装载到内存中，并通过缺页异常完成页面置换等手段，解决物理内存不够的问题。
可能，你会想内存和外存这种不断装载，不怕性能差吗？这主要是利用了局部性原理，即时间局部性（一条指令前后执行时间较短），空间局部性（前后指令几乎在某个部分区域），分支局限性（一条跳转指令的多次执行，会跳到同一个位置）。
虚拟存储的概念：
1、在装载程序时只将部分需要的程序和数据放到内存中；
2、在执行时如果遇到需要的数据不在内存中，操作系统会将程序或数据放到内存中；
3、操作系统会将内存中用不到的内存或数据放到外存中。
那对于2，3步骤系统是怎么做的呢？
第2步主要是通过缺页异常请求，它使用的是虚拟页式存储。它相对于页式存储管理，区别是它不会一次性把所有页表项都加载到内存中，只会加载一部分，通过设置标志位决定是否有效。
当我们执行CPU指令时，会根据页号找到对应页表项，如果无效，就会抛出缺页异常，这时会触发操作系统的进程，会将外存的页加载进来。如果加载过程发现没有空闲物理页了，会执行页面置换，把某个页面移到外部去。如果目标页面修改位有效，还要将其更新到外存。
上面提到了置换，主要通过操作系统的页面置换算法来实现。目前提供了几种比较常用的算法，比如FIFO，LRU，OPT，CLOCK等等。
OPT：是一种最优页面置换算法。即每次都算出每个页面的下次访问时间。这是一种理想化的算法，实际是上是无法实现的，因此无法预知逻辑页面的等待时间。
FIFO：最简单的算法，根据先入先出来决定置换，但这种算法并不能反映真实的程序执行情况。操作系统会维护一个逻辑页面的链表，缺页的时候会直接从链首取。
LRU：这个在其他地方经常遇见，最近最少访问，会找到最近最少访问的页面，进行置换。
CLOCK:记录页面访问的大致情况。它会将整个页面做成圆形链表。在访问页面时，会将页标项的访问位置为1。缺页时，会从当前位置扫描链表，找到访问位为0的，遇到1时，会将访问位置为0，然后接着找，直到遇到为0的进行置换。
内存回收
内存管理不得不提到内存淘汰机制。Linux也会对内存进行回收。
其基本流程是当内存不够用时，会进行内存回收，内存回收包括后台回收和直接内存回收，后台回收会启动一个特殊线程，叫kswapd ，如果后台回收仍然不够时或者说后台回收的速度赶不上内存申请的速度，就会触发直接内存回收，该过程的回收时同步的方式进行的。如果还是不够内存会首先kill掉占用内存大的进程，如果还是不够，直接就OOM。
后台回收会定期扫描内存页，会通过不同的阈值来触发后台内存回收。
内存回收的对象主要是文件页和匿名页。
文件页(file)：之前在介绍零拷贝技术时，说到了PageCache，为了加快速度，会将文件数据缓存到内存中，这部分数据就是文件页缓存。回收的方式是，如果是干净页，直接释放掉对应缓存；如果是dirty，要先将页数据写回到磁盘中，再释放掉对应的缓存。
匿名页（anon)：有些数据并不是文件缓存的数据，而是进程产生的，比如堆、栈等数据，这部分数据暂时用不上，但未来可能还会用，会先将其放到磁盘中，未来可能的时间再加载到内存中。这是通过Linux的Swap机制实现的。
针对这两种不同的页，分别维护了两个链表，一个是活跃链表（active_lists)，一个是不活跃链表(inactive_list)，这是一种改进的LRU算法。如果访问数据不在链表中，则直接加入到不活跃链表中，如果数据第二次被访问到，会加入到活跃链表。在进行内存淘汰时，直接淘汰不活跃链表的数据即可。
haibo@haiboInxiaomi:~$ cat /proc/meminfo |grep -i Active
Active: 2716196 kB
Inactive: 8889912 kB
Active(anon): 2500 kB
Inactive(anon): 4911780 kB
Active(file): 2713696 kB
Inactive(file): 3978132 kB
通过两张链表可以有效避免了预读失效和缓存污染的问题。
预读失效：我们都知道，程序具备局部性原理，在读取存储器数据时，是以页或者块为单位进行读取的，一次会读取连续空间的数据，即时有些数据本次不会用到，Linux默认的页是4KB ，当然页可以配置大页（ Huge pages，2MB或者1G),Mysql页（Innodb)的大小是16KB。但在极端情况下，可能会出现一个问题，就是预读的数据永远都不会被访问到。如果是利用传统的LRU，访问就加到链表头部的话，可能会导致很多热点数据被挤到链表尾部，导致热点数据可能会被淘汰。当然，还要提到一点，由于局部性原理，预读失效的概率并不大。
Linux通过两个队列，首先将数据预读数据放到不活跃链表，尽可能缩短了不活跃的预读数据缓存时间，首先被淘汰。
缓存污染：缓存污染指的是大量数据占据了链表头部，导致热点数据被淘汰。其实也是预读引起的。对于上面的链表，预读出来的数据是放到不活跃链表，如果被访问到就直接放到活跃链表中，就仍然存在缓存污染的危险。针对这个问题，linux的做法是只有第二次被访问到，才会被加入到活跃链表中，即提高了加入活跃链表中的门槛。在一定程度上，有效地降低了缓存污染的问题。
参考资料：
微信分享/微信扫码阅读
