通过Linux理解操作系统（五）：内存管理（下）

通过Linux理解操作系统（五）：内存管理（下）

Linux是通过怎样的机制完成这些工作做一个简要的介绍。

1、分页和页表

首先，分页的概念相信很多人都不陌生，我这里想说的是“分”的思想，学习计算机两年多，我最大的感受是计算机就是在利用有限的资源干无限的事，而这很多时候都是基于“分而治之”的思想实现的。问题规模太大，太复杂怎么办？就是要分解，分就意味着更简单，更灵活，更容易处理，我这里并不只是指算法设计，而是指解决很多实际的复杂问题，就像现在很火的大数据处理，一台机器根本无法完成这么大量的存储和计算工作，就是需要通过“分”，把数据分到多台机器上存，把计算任务也分到多台机器上完成，才有了问题解决的可能。好吧，扯远了~其实我只是想说作为程序员一定要理解分治的思想。回到正题，我们已经知道每个进程都有4G的地址空间，但是程序在运行的时候并不需要程序中所有的内容，需要的只是当前正在执行的一部分和相关的数据就可以，因此可以将整个地址空间分成一个个连续的大小固定的块（比如4KB），只要那些需要的块在内存中即可，这一个个的块就是页（page），好处就是当程序运行或者停止时，系统不用把整个进程的内容移进移出，而只要移动一个个页就可以，这样既提高了效率又节省了空间，才使得多个进程能够同时存在于内存中。注意，这里的页是指虚拟地址空间里连续的一段，而物理内存中这样连续的段则称为page frame，它们的大小相同，进程的页放进内存中时就放到一个个的page frame中。

有了page的概念后，我们再来看系统是如何实现逻辑地址到物理地址的转换的。Linux为每个进程维护了一个page table，这个表里的每一条记录表示一个page，保存了以下信息：

 page frame number，系统就是由此得到的该页在实际内存中的位置。在32位的机器上，一个逻辑地址有32位，它可以分成两部分，一部分用于表示页号，用于在page table中查找该page的记录，从而得到page frame number，也就是这个page在物理内存的起始位置，还有一部分是页内偏移量，这两者相加就得到了我们实际要访问的物理地址。通过这种方式系统可以实现逻辑地址到物理地址的转换，但是又带来一个问题，由于在程序运行期间需要对page table进行查找，也就是说page table也要存在于内存中，假设一个页有4KB，对于32位的机器，page table中刚好有2^20（1M）条的记录，似乎还可以接受，但是对于64位的机器，则需要2^52条记录，如果光是存个page table就用掉这么多内存，那程序也不用跑了，为了解决这个问题，Linux使用了多级索引技术：

Linux不是直接把整个page table放到内存中，而是根据页的大小将整个page table 又分成一个个小的page table，然后通过索引的方式来进行访问。具体方式如上图，虚拟地址被分成了5个部分，global|upper|middle directory, page和offset，首先根据global directory在global目录里进行查找，global目录里每一条记录保存了一个指向下一级目录的指针，在取得一个指针后，根据这个指针定位到一个下一级的upper目录，然后根据upper directory 又可以在upper目录里得到一个指针来得到一个middle目录，而middle目录里得到的指针才是指向真正的page table，此时再根据page域取得一条page table中的记录。那为什么这样能省内存？假设一个page目录里有n条记录，那么根据gloabl目录可以索引到n个upper目录，而每个upper目录又可以索引到n个middle目录，以此类推，原来一个大的page table分成了n^3个小的page table，通过三级目录一级级往下索引就可以得到我们最终需要的那个page table，而需要放进内存的就只有在查找过程中需要的三个目录和最终的1个page table即可，这样当然就省了很多内存咯。

2、页的回收

在系统运行期间，随着越来越多的程序的启动和运行，越来越多的物理内存会被占用，而系统必须保证有空闲的内存来维持正常的运行，Linux使用了一种叫PFRA（page frame reclaiming algorithm) 的算法将一些暂时没用的page frame释放来腾出空间，的目标就是从内存中选出要释放的page frame。首先linux将所有的page frame分为四类：unreclaimable, swappable, syncable, discardable。unreclaimable表示该页的内容不能被取出，即新的page不能放到这里；swappable表示该页的内容可以被取出内存但需要写到磁盘，而syncable也表示可以取出内存但是只有当这个页的内容被标记为已修改过的才需要写会磁盘，discardable则表示该页的内容可以直接被覆盖而不需要保存到磁盘。这四个类代表了需要完成页的置换操作的难易程度，在发生页的置换时，系统会优先选择容易完成页进行置换。

linux在启动的过程中会开启一个后台进程，这个进程在系统运行过程中每隔一段时间就会对内存的使用情况进行检查，如果它判断当前的内存已经快要不过用了，就会开始运行PFRA算法。

linux将内存中所有page frame组织成两个链表，active list和inactive list，这两个链表也叫做LRU  list，active list里的页是最近被访问过的，而inactive里的则是最近没被问的，所以系统可以从inactive list里选择page frame释放。如上图所示，每个page有2个标识位，编码了4个状态，这四个状态之间可以进行转换，从而导致了一个page会在active list和inactive list之间移动。观察这个图可以发现，当PG_active为0时，页在inactive list上，当PG_active为1时，页在active list上。对于一个在inactive list的页，如果一开始处于状态1，么该页被访问过一次后，它的referenced标识位会变为1，变成状态2，而再被访问一次后，它的active就变成1，referenced变为0（状态3），这样才从inactive 变成了 active，而如果在状态2的时候，在经过一段特定的时间后还没有再被访问一次，则它又会自动回到状态1，也就是说一个页要从inactive变成active，中间需要经过一个中间状态。为什么需要这个中间状态呢，主要是考虑到下面这种情况，有些程序可能会周期性的访问一个内存页，比如说1小时访问一次，那么在这1小时内，它是不需要再被访问到的，如果没有这个中间状态的话，它会直接变成active，所以会一直保存在内存中，而有了这个中间状态，如果这个也在一定时间内没有再被访问一次，它就仍然是inactive的，也就可以被取出内存。当然，有些时候系统可能会急需更多的内存，所以即使是存在active list里的页，有时候也需要被取出内存，图中的refill箭头就表示了直接从active到inactive的状态转换。linux系统通过维护这些状态变换，就可以选择出合适的页来将其取出内存，从而尽量减少发生page fault的机会。