os中的分页算法

分页算法的背景

• 为什么要有分页算法？

  为了打破线性地址和真实物理地址一一绑定的关系，

• 为什么要打破这样的关系？

  连续内存模型无法很好的处理一些碎片问题，例如100MB内存中实际空间只用了70MB，但是剩下30MB均为碎片内存，很可能无法读入一个20MB的程序，即使内存空间剩余量远不止20MB。

• 期望的模型？

  能有一种离散的内存模型，同一个程序可以按一定单位分布在内存不同处。

离散内存管理

段式管理

操作系统将内存以段（Segment）为单位划分，例如分为代码段，数据段，堆栈等，这样去划分一个程序，就初步做到了将一个进程离散的分割，经过这样的分割，内存的逻辑地址也就自然而然的分为两部分，前一部分为段基址，后一部分为段内便宜，元组模型为：<segment-number, offset>。

当CPU得到一个逻辑地址时，定位过程如图所示：

分段算法下的逻辑地址处理算法

首先一个逻辑地址分为两部分，s代表segment表中的偏移量，d代表基于segement的基址，还需要便宜多少的地址，对一个逻辑地址，首先根据s得到段基址base，之后判断d是否有超过这个段所限制的偏移量，如果没有超过，则将base和d相加得到物理地址。

段式管理的优点

• 将内存分为几个大块，可以根据每个块的特性，进行专门的管理，例如访问控制等。

• 一个进程可以分割为多个部分进行离散存储，可以一定程度上缓解内存碎片的问题。

段式管理的不足

• 对内存单位的划分太过于粗糙，内存碎片问题仍然存在。

• 在一个段内，空间利用率仍然是个头疼的问题，例如一个64mb的段，在这个段内，又回到了连续内存分配中出现的老问题，first fitting？best fitting？least fitting？

段页式管理

段的存在使得操作系统在大体上可以对不同内存区域进行定制化管理，也使得程序无需在一个连续内存上全部加载，但是这样的控制粒度来说还是太粗了，所以空间碎片问题还是大量存在，而页式管理就能更加精细的对内存进行管理。

开启分页功能的操作系统的内存访问方式如下，由段基址+段内偏移得到一个逻辑地址，再有这个逻辑地址查询页表找到对应的页表项，这个页表项所指向的地址才是真正的物理地址，所以段基址+段内偏移所得到的地址也称作为虚拟地址。

一级分页算法

所谓一级分页算法，就是在MMU计算得出线性地址和实际物理地址之间只有一层映射关系，也就是做了一层『目录』，如图所示

一级分页算法示意图

cpu得到一个逻辑地址，逻辑地址分为两部分，第一部分p为在页表中的偏移量，根据页表基址+偏移量p得到一个地址f，d为在此页表项基址f基础之上的偏移量，页表（page table）的地址一般放在寄存器中。

为什么要做这样的一层映射？

• 解除了线性地址和物理地址一一绑定的关系，连续的逻辑地址映射到离散的物理地址，用户所见的地址仍然是连续的，与过去『线性地址==物理地址』无差异，用户层面对此改变无感知，但是操作系统底层的存储由连续存储转变为了离散存储，这样的好处就是避免了碎片化内存管理的问题：『明明当前所剩内存空间足够，但却没有一块完整的区域能够加载新进程』。

• 所有程序理论上都可以占用整个内存空间，为后续支持虚拟内存技术做下铺垫（最大限度的利用os的资源）。

这样做随之而来带来的问题是什么？

• 每一次的内存访问都需要经过页表再进行物理地址访问，等于说一次内存访问需要原来两次内存访问的开销。

• 需要更多的内存管理开销，额外维护了一张页表，当前操作系统每一页的大小为4kb，即2的12次方，在32位操作系统中，一共有2的（32-12）次方个页需要维护，即有2的20次方个页，每个页需要有一个指针指向其所在位置，在32位操作系统中，一个指针的大小为4字节，所以维护一张页表需要4字节*2^20，总共4MB。32系统总内存为4GB，4MB的页表还在接受范围之内。

• 一级页表需要全部预加载，因为一个进程理论上可能需要用到整个4GB的地址空间，所以无论是什么样的进程，4MB的页表必须加载入内存。当程序非常小，例如hello world这种几KB的程序也同样需要4MB的页表，非常浪费。

• 每一个进程都需要一张这样的页表，当进程数增加时，页表开销增大。

改进目标？

• 做一层缓存，将那些访问过的地址进行缓存，尽可能减少页表计算的开销。

• 页表需要动态分配，如同lazy initialize一样，而不是全部预加载。

• 页表太大，每一个进程都得对应一张这样的页表，进程多了所占用的内存还是非常可观的，最好能减小页表大小。

TLB（translation look-aside buffer）

开门见山的说，TLB是硬件层面的缓存，而不是软件层面的缓存，原因如下。

在应用层中，对热点数据的缓存是非常常见的做法，例如java中可以用一个简单的hashmap做缓存，也有redis这种内存数据库来做缓存的，核心的解决思路都是一样的，对热点数据进行记录，以节约下次查询时的访问开销，做法也大同小异，无非是在内存中构建一个key-value的数据结构。但是在分页机制中，用内存作为缓存的落脚点几乎没什么意义，原先的流程是查询页表再去访问物理地址，页表本身就在内存中，如果还是在内存中简单加入一个key-value的键值对去做缓存，访问流程变成了首先去查询缓存，如果命中，则访问物理地址，如果没有命中，则访问页表进行地址计算，内存访问开销并没有什么实质性的提升，反而内存的访问次数还多了一次。这个问题出现的本质原因就是在于传统应用层做缓存是为了能够减少对底层存储系统的访问（例如数据库，数据库的吞吐量远低于内存），但是在分页算法中，本身就是在访问内存，所以直接在内存中做缓存是毫无意义的。

正因为如此，在CPU中就加入了一个TLB这样的硬件缓存设备，访问速度很快，功耗和成本也高，所以TLB不会太大。

其访问过程没有太多好说的，就是一个硬件方面的缓存处理。

TLB示意图

多级分页算法

所谓的多级分页算法，就是在原有一层映射的基础上，再增加一层映射，以二级页表为例，如图所示

多级分页算法示意图

二级分页算法下逻辑地址的划分

一个逻辑地址被分为了三部分，p1代表第一级页目录的偏移量，p2代表页表项的偏移量，得到一个页地址后，再偏移d个单位即为真实物理地址。

多级页表具体是如何实现的？

• 以二级页表为例，还是32位系统，页的大小仍然是4kb，也就是2的12次方，还是需要2的20次方个地址需要保存，高20位以10位为截断点，即第一级页表，也就是页目录项，数量为2的10次方，第二级页表，也就是页表，数量也为2的10次方，即均为1024个指针，可以理解为一个大小为1024*4字节即4kb的数组,数组的每一项都是一个int指针，指向一个同样大小为4kb的数组的起始地址。

简单的说，在二级分页中，地址的变化是 段基址+段偏移——>线性地址——>找到对应页目录——>找到对应页表项——>真实物理地址。

多级页表有解决一级分页的问题吗？

• 与一级分页算法相同，第一级页表必须全部预加载，但是二级之后的页表无须预加载，而此时的一级页表大小远远小于在一级分页算法中的页表大小，以二级分页为例，第一级页表（页表项）包含2的10次方个地址，每个地址大小为4字节，所以整个第一节页表的大小为4KB，相较于一级分页算法的4MB有了非常显著的缩小。

反置页表

在计算机的世界中，为了解决一个问题，随之必然而然的就会带了一个新的问题，这是亘古不变的哲理，取舍就在于新问题和老问题你可以容忍哪一个了。

多级页表的引入是为了解决一级分页中的一些问题，也一定程度上缓解了原算法的一些问题，但是随之而来的问题也很明显，每一个进程都各自拥有一份多级页表，当虚拟地址空间增大到64bit，进程数量增加，分级级数时（例如四级五级分页），对内存造成的压力会随之增加的，这个问题的根本原因就在于，在多级分页算法中，page table的大小与逻辑地址空间是正相关的，而反置页表算法的解决思路是与“物理地址空间”绑定，页表的大小只与物理地址空间有关。

算法示意图如下：

反置页表算法示意图

逻辑地址被分为三部分，pid代表进程id，p代表page-number，d表示偏移量，其中<pid,page-number>用于在page table做匹配，如果匹配到了，那么该元组在page table中的偏移量i即作为页帧base地址，与d组成物理地址，作为对比，原先的分页算法将逻辑地址分为<virtual page-number (p), offset (d)>。通常会用hash算法提升这个匹配过程的效率，但即使这样，匹配效率也无法和原先的算法相比。

这样的算法的确解决了虚拟空间地址膨胀而导致页表所占内存急剧上升的问题，但是随之而来带来的缺陷也是非常明显，以我的理解，这样通过进程id和物理页帧做关联，一个物理页帧只和一个进程相绑定，一些内存共享，内存映射实现的复杂度肯定会随之而上升。Linux并没有采用反置页表这种算法，而是采取了多级分页算法。

总结

前两年上完操作系统的课感觉迷迷糊糊的有点懂，最近去回顾这些知识发现自己的理解还不够到位，于是就想整理下这些知识点。整个内存管理涉及到的一些算法我在这稍微整理了下，本来是想整理下一级分页和多级分页的差异，后续看着文章不够完整又补充了TLB和反置页表的资料，这篇文章不是引人入胜的从无到有的基础讲解，在我的理解看来更像是一篇对比，或者说各个算法不断冲突解决矛盾的，操作系统的哲学也就在这里，不断的产生的矛盾，不断的去解决，所有的方案都是在折中。