初窥OS段页式管理概貌

Posted on Edited on

“那是在一个还只有汇编语言的时代，一只满怀梦想的新手程序猿刚刚完成了一个小程序。“保存，运行，完美！”。可是好奇心强的他发现一些很有意思的事情:

  • 为何一个64kb的程序能够在一个只有32kb内存的电脑里运行?
  • 为什么运行中的程序能够互不干扰,结束后又能继续运行新的程序?”

于是新奇的翻开书,发现了操作系统背着程序员偷偷做的一系列幕后工作。。。

地址空间

这一切让我先从我们平常最熟悉的程序开始说起,以便先了解两个基本的概念：

1.虚拟地址

data segment
tab db 'hello world$'  ;
data ends
code segment
assume cs:code, ds:data  ;
start:
        mov ax,data
        mov ds,ax        
        lea dx,tab
        mov ah,9h
        int 21h
        mov ah,4ch
        int 21h        
 code  ends
        end start

  • 这是一个用汇编写的HelloWorld程序。程序中有数据段(datasegment)和代码段(code segment),关于段页式管理的部分后面再说。这里每行代码的的偏移地址我们记做它为虚拟地址，因为这个地址只是在程序中是从0开始增加,运行时会被映射而产生变化的地址,所以它并不是真实的物理地址而是属于逻辑上划分的。(多亏有虚拟空间这个东西,要不我们以后写代码还得考虑每条的地理位置简直心累！)

  • 例如第一个mov指令(mov ax,data)，我们可以看作在代码段内的偏移地址为0，而第二条指令(mov ds,ax)的偏移地址则应该为:上一条的虚拟地址+上一条指令的长度。

2.虚拟内存

  • 在最早的计算机中是没有存储器这个抽象的概念，这就意味这每个程序猿在写程序的时候直接用的是物理地址！在这种简单粗暴的寻址方式下出现的就是无数令人抓狂的问题。程序中的每条指令需要在内存中有固定的位置，如果位置上有别人正在运行,那么就是一切崩溃的开始。甚至用户程序可能一个不小心就会毁掉操作系统！

  • 所以为了宇宙和平！操作系统为每个进程提供相互独立的内存地址空间就变的刻不容缓。于是乎出现了一种存储器抽象:地址空间。它可以令操作系统在程序运行时完成对进程的保护和重定位,使得进程之间的运行相互不干扰，我们在程序之中只需要像上面的汇编一样代码从地址0开始一行一行的编写代码，等需要运行的时候再由操作系统将准备运行的程序进行重定位到内存上一个空闲的地方。这是不是很棒！

  • 尽管地址空间解决了很大一部分问题,但是为了满足日益膨胀的软件规模,现有的内存已经或多或少不够用了,聪明的计算机大神们为了解决这些问题又用了一种新的技术:虚拟内存。虚拟内存的出现使得我们可以运行比内存容量大的多的程序。虚拟内存让每个程序有了自己的地址空间(上面提到的那个玩意儿)，这个空间被分成了多个块，每一块称作“页面“，可以理解所谓分页就是将我们的程序中的代码在逻辑上分成一块一块的，每一块的划分单位就是页面。运行程序时页面经由硬件执行必要的映射，使得我们程序中的虚拟地址成为我们计算机内存中真正的物理地址,完成了将程序的一部分真正的映射到了内存中

    这就是这篇文章要介绍的分页管理!看到这里脑中对虚拟内存和页面还没有概念？别着急，接着往下看就慢慢清楚了！)

让程序跑起来!

这里写图片描述

  • 图中左边是我们是页表(可以理解为一张记录页面与页框映射关系的一样表)。如果我们以4K为页面的大小单元的话(不是必须,但为普遍),我们的程序就需要:64/4=16个页面(就这样被切成了16块(｀･д･´))。但是，糟糕的问题是,真实的计算机中只有右边那可怜的32K内存,所以实际上它只能在真实的内存中保存8个页框(通常页面和页框的大小是相等的，因为他们需要进行后面提到的映射)。

  • 假设程序刚开始运行时可能会用到程序中0页,1页，2页，3页，4页，5页，9页，11页中的代码。那么当程序运行的时候在真实内存中就需要更新页表(就是将我们需要用到的页面和叶框建立映射关系),并将我们需要用到的页加载到实际内存中,这样就建立好了映射关系(图中的箭头)。图中左边为已经建立好映射关系的页表。

这里是第一种情况—命中

  • **注意!程序开始运行了!当我们的程序运行到0~4K行代码的时候,程序中使用到的一条 虚拟地址 会被送到一个叫内存管理单元(MMU)**的地方,MMU发现这条虚拟地址位于页表的第0页，于是它查询页表(页面就是页表中的索引，页表的索引从0开始,例如页面2就是页表中的第三项)发现第0页中存在内容(不存在内容的地方都打上的x),然后读取内容(页框编号)，接着这条虚拟地址中页面编号的部分就被替换为取出的页框编号部分,形成了真实的物理地址!

下面是另一种情况—缺页

  • 那么当我们的程序运行到24k~28k（页面7）的时候,传送的虚拟地址经MMU查询页表后发现页表中没有这个内容（标志为x）,也就是说真实内存中没有对应的页框！这时候MMU发出一个缺页中断,使得CPU陷入到操作系统。操作系统会在页表中通过页表置换算法找到一个可以移除的表项，然后将导致陷入中断的的那部分程序加载入内存,更新页表,使得页面7有了对应的页框，然后重新启动引起陷阱的指令，这样就完成了页表的更新。当然被如果程序运行到了被移除的那个表项对应的页面上就会又掉进陷阱(陷入操作系统)，继续更新页表。。。

(这就是分页的基本过程，看完如果没有深入骨髓的理解就请点击右上角。。。好吧，我就随便说说哈。。。这里只需要有个大致的理解页面管理系统是如何运作的就好。

接下来就是细腻的重点——页表

话不多说直接上图:
这里写图片描述
注:在我们刚刚的程序中主机有16位地址线。

  • 在虚拟地址中,16位的虚拟地址前4位(足够能表示我们分出来的16个页面)作为页面的编号,后12位(表示内存大小为4096个字节)则为偏移地址。

    地址映射的步骤

  • 那让我们看看如果在程序中有个语句要访问地址:8196(二进制为:0010 00000000000100,注意中间那个忧伤的空格)这个地址时事实又是怎么样的呢？

1.MMU发现8196这个地址存在于第3页(8k~12k),查询得到内容为110(也就是6)

2.检查页表第3表项中的状态标志(测试状态标志再后面，别着急后面会说明页表项)发现标志为’1’(即该页面对应的页框存在于内存中),一切测试通过!

3.最重要的最后一步:将得到的3位页框编号加上虚拟地址中的12位偏移地址，这样就形成了15位的物理地址，虚拟地址就这样完成了从8196映射到了内存中24580(位于页7 24k~28k)这个物理地址了!

以上就是分页管理映射的大概流程。

接下来需要知道的是—页表项

在上一个图中我们当我们取得一个页框的时候并不能仅仅只是进行数位的替换,还需要测试页表项的许多位，
继续放图:
这里写图片描述

  • 高速缓存位:可以禁止页面被缓存,CPU希望IO等设备从接口直接取得数据,而不是从内存中一个缓存的副本中。

  • 访问位:当前页被访问时会被设置，此位可以帮助操作系统的页面置换算法。

  • 修改位:当前页内容被修改后该位会被设置,当页面置换算法决定需要从表项中移除此页面时如果发现被修改了则需要将修改后的数据重新写入硬盘中。如果没被修改则可以直接丢弃。

  • 保护位:说明了当前页面允许执行的操作（读/写/执行 等，这个位在平常的系统权限管理中相当重要!）。

  • 是否存在位:表明了当前页框是否存在于内存当中,此位可以用来判断是否缺页。

以上的这些位都是在查询页表的过程中被测试的。比如代码段的页面会被设置为只读，如果一不小心程序企图写入这个页面，那么操作系统就会发出一个信号给进程并停止进程，告诉它”你摊上大事了!”

更快!更快!更快!——快表

  • 在使用分页管理后使得内存的管理更加方便了，但是有一个问题一直在头上萦绕不去”如果我们每次关于内存的操作都要完整的查询一次整个页表的话那无疑是非常没有效率并且非常笨的”。机智的计算机大神们在这个问题出现后’噔’的一下计算机大神们就想出了可以利用**检测缓冲区(TLB也就是”快表”)**这个设备解决这个问题。

  • 快表就是将少量且常用的页面放在一个区域(硬件或内存,取决于具体实现)中,每次的查询操作会先在快表中寻找,如果命中且符合测试条件(即测试各种标志位),则直接在快表中取出页框号,然后执行地址映射的流程。如果在快表内未命中则会进行正常的页表查询(在内存中),并在快表中淘汰一个页表项给这个新的页面替换。

  • TLB可以使用硬件也可以使用软件实现。

1.当在软件TLB中未差找到页表项但是内存中有时，就会发生一个”软中断“,接着就会更新一下TLB(从内存中将页表项读入TLB)。

2.如果在 TLB和 内存中都未找到页表项时就会发生一个”硬中断“,此时则会从硬盘中读取页面并更新TLB。所以我们页可以想象到硬中断相比软中断来说要耗费巨大的时间。

拥抱更大的内存!

32位计算机的到来

时代在进步，很快计算机发展到了32位，这也使得有了更大虚拟地址空间和物理内存。再像之前那样将所有表项都放在一个页表中显然会带来效率等各种问题(比如32位机支持最大4GB内存,那么我们需要的页表项的数目为:(410241024)/4=1048576项,足足有一百多万项!)。于是又一个解决办法出现了。。。

—多级页表

嘿!上图:
这里写图片描述
多级页表就如名字一样有很多层的划分，这里以2级页表举例(再多也一样，只是更加复杂)

  • 想一下当我们还在16位CPU的时代，通过将后12位作为偏移地址，前4为作为页面编号解决了分页问题，成功的跑起了那个小程序。与时俱进的我们怎么能够满足于现状!为了拥抱更大的内存。

  • 我们需要将当前的32位地址进行重新的划分:前10位为目录，中间10位为页面，后12位为偏移地址。(想象一下顶级页表可以有2^10=1024个项，而每个二级页表可以表4k*1024=4MB的空间，也就是说一个顶级页表可以表4MB×1024=4GB的空间，这刚好是32位计算机能支持的最大内存)。

  • 当我们查找一条虚拟地址时，通过:

1.前10位索引查找到顶级页表中的二级页表地址
2.通过虚拟地址的中间10位索引到二级页表中的页表项
3.接下来就使用查找到的页表项中的页框号加上虚拟地址最后的12位偏移地址组成了真实的物理地址!

  • 在一个进程执行的时候它实际上也许只需要几个页表。当程序一不小心访问到其他页面的时候无法通过标志位测试而回给操作系统发出”缺页中断“,操作系统检测到了这个进程又企图访问我们不想让它看到的地方，于是又发给它个信号说”你又摊上大事了!”︴，然后无情关闭了它。

64位需要更机智的页表方法

虽然多级页表在32位机上有一个很好的表现，但是时代又进步了!64位计算机开始普遍。
地址空间增长到了2^64,如果页面大小依旧为4kb，那么需要有一个2^52个表项的页表。再如果每个表项8个字节，那么需要多么大的容量你们可以自己算一算(美到不敢想象～)。
那么问题就又来了。。。
不过既然我们有2^64这么大的虚拟地址空间，而仅仅只有几个G可怜的小内存那么咱们之前用过的分页肯定就是不能继续再使用了。如果我们。。。换一下?是的!
——我们可以改变由虚拟地址映射物理地址的做法而直接由物理地址映射到虚拟地址!这么一变我们的页表就变小的可以接受了。。。这就是

—倒排列表

  • 先抛出缺点:倒排列表虽然会缩小页表的规模，但是它会使得从虚拟地址到物理地址的转化过程变得相当困难(反向查找，想想就难受)。

  • 当然有缺点我们就要克服缺点!这次又该轮到TLB出场了,由TLB缓存住经常使用的页面可以大大加快效率。但是如果发生缺页时我们应该怎么办？一条条翻完整个倒排页表来找嘛？—**怎么会!**那可不得累死了。。。

  • 所以机智的计算机大神们又带来的新的解决方案—散列!通过将虚拟页面进行散列,如果将散列的虚拟页面与物理页面一样多，那么冲突链都会是可以接受的范围。所以通过散列+TLB的方法成功的将我们从超过3000万GB的页表中释放出来!
    这可得好好庆祝下。。。

关于各种页面置换算法

（额。那又是一个大坑。。。

所以这里就贴部分算法的百度连接大家有兴趣的可以看看～

1.最佳页面置换算法
2.最近未使用页面置换算法(么有链接额。。)
3.先进先出页面置换算法
4.第二次机会页面置换算法
5.时钟页面置换算法
6.最近最少使用页面算法
7.工作集页面置换算法
8.工作集时钟页面置换算法(么有链接额。。)

段页式管理

分段的实现我们都不会陌生，程序就是由许许多多的段构成并且在内存中运行的。
段的大小可以是不固定的，相反页的大小是固定的。但是如果在操作系统中只有段的存在必然会与分区管理一样容易产生内存碎片(好慌~)。如果我门将段的管理与页的管理相结合。。。
那么就是又一个新的管理方式!!!(好累。。。)

段页式管理其实就是在段的偏移地址里面容纳了页面号组成了段+页面+偏移地址的虚拟地址格式，所以理解了分页管理这里也很容易。

在操作系统中则为进程维护了一张类似这样的几张表:
这里写图片描述

  • 没错，了解了前面的分页管理方式后我们应该可以很明白的看懂这个的地址转换方式。现在让我们回顾下开头的汇编程序，找到那个code segment,这就是段!当我们程序发现要执行code段的时候将段描述符所指向页表的地址加载入寄存器(方便接下来指令的快速查找)。然后就是通过虚拟地址的中间的页面号在页表中查找对应的页表项。再然后的然后就你就会噢的一下都懂了～

    一切似乎又有了熟悉的味道 。。。

最后附上参考资料:《现代操作系统》-Andrew S.Tanenbaum

如有错误希望能得到指点,不胜感激 :D