存储系列之 虚拟内存:分页技术 - orange-C

时间:2024-01-29 20:57:50

存储系列之 虚拟内存:分页技术

引言:前面连续几章讲述的文件系统是存储系统的外存管理的一种抽象,而虚拟内存则是存储系统的内存管理的一种抽象。其实这两种原理有相似地地方,当然也就有不同的地方。同时这两者也属于操作系统内核的范畴。 

 

1、虚拟内存的概念

虚拟内存又叫虚拟存储器(Virtual Memory),虚拟内存是计算机系统内存管理的一种技术。

我们都知道,进程运行前必须将程序加载到内存中,而根据Parkinson定律“存储有多大,程序就会有多长”,所以如何有效的管理内存一直是计算机需要解决的问题,也因此提出了很多简单高效的方案,例如虚拟内存是其中之一。所以虚拟内存是因为内存不足而提出来的,而目前这种技术也已经普遍应用在大多数操作系统中,具体实现起来可能稍有不同。

虚拟内存简单的定义就是把进程在内存和磁盘之间换进换出。如何换?页面置换。当然这只是比较常见的方法,也还有其他方法或者几种方法的组合。

2、交换技术

虚拟内存技术提出之前,其实已有另一种更简单更直接的技术:交换技术。

交换技术,就是把各个进程完整地调入内存,运行一段时间后,然后再放回到磁盘上。

而虚拟内存,只需把进程的一部分内容存放在内存中,而且也能保证进程的正常运行。

这两种方式虽然加载的对象大小不相同,但是都需要进程的换进换出。同时,进程的堆栈是实时变化的,那么该如何管理内存空间呢?

 其中,操作系统的内核进程是常驻在内存,一般固定在内存空间地址最低端,如上图。32位系统中,一般情况下固定大小1GB为系统区,而其他3GB为用户区。

2.1 空闲块的管理

内存是动态分配的,那么如何记录当前内存的使用情况?有以下两种方式。

(1)位图法

在位图法中,内存被划分为很多个单元,每个单元对应于位图中的某个数据位,0表示空闲,1表示占用。如下图显示了部分的内存和相应的位图。

分配单元的大小是一个很重要的设计问题,分配单元越小,位图越大。位图法,简单;但是查找一串K个连续的0,比较复杂和缓慢。

 

(2)链表法

 对内存的管理建立一个链表来管理已分配和空闲的内存空间。如上图的(c),P 代表进程Process,H表示空闲Hole,接下来两个字段依次表示起始地址和长度,最后一个字段是指向下一个节点的指针。在这个例子中,链表是按照地址从低到高排序的。这样做的好处是当一个进程运行结束或被置换出去时,可以很方便地来更新链表。

2.2 空闲块的查找

当一个新的程序加载进来的时候又该如何找到空闲的地址空间?通常的分配算法有最先匹配法、下次匹配法、最佳匹配法、最坏匹配法和快速匹配法。这些算法特别是前面几个都有些类似,我们简单介绍下。

最先匹配法的基本思路是:假如进程的大小M,从链表的首节点开始查找,每个空闲块的长和M比较,是否大于或等于它,直到找到第一个符合要求的节点。

下次匹配法是在上次查找的结果基础下继续查找直到匹配成功。

最佳匹配法需要遍历所有节点,找到能装得下的最小空闲块。而最坏匹配法则相反,找能装得下的最大的空闲块。事实上,这两种都有比较而且遍历所有链表,效果不佳。

快速匹配法和其他不太一样,基本思路是:对于一些常用的请求大小例如2K、4K、8K等,为它们分别设置链表。这样查找匹配非常快,但是如果程序结束时或者被置换后,可能需要合并左邻右舍等操作操作复杂,如果不能合并则可能形成小空洞碎片。

对于这些碎片或者说一些不连续的小黑洞,可以采用内存紧缩(memory compation)技术:把所有的进程都尽可能地往内存地址的低端移动,相应地,那些空闲的小分区就会往高端移动,从而在地址高端形成一个较大的空闲区。

3、虚拟内存

上面的交换技术是把程序作为一个整体放入内存。但如果程序太大了,超出了空闲内存的容量,没办法装入,该怎么办?事实上大部分可能是这种情况。

当时人们通常采用的解决方案是覆盖技术,即:把程序划分成若干个部分,每个部分叫做覆盖块(overlay),然后把那些当前需要用到的指令和数据的覆盖块保存在内存中,其他放外存,运行一段时候后,在内外存之间再交换所需的覆盖块。

虽然覆盖块的交换是由操作系统完成,但是覆盖块的划分最开始由程序员来手工完成,这是一项非常复杂的工作,费时费力。后不久人们又想到了一种办法,可以把工作交给计算机完成。

这种方法叫做虚拟存储器(Virtual Memory)(Fotheringham,1961),我们一般称作虚拟内存。它的基本思路是:程序的代码、数据和栈的总大小可以超过实际可用的物理内存的大小。操作系统把当前需要的那些部分保留在内存中,而把其余部分保持在磁盘上。然后在再需要的时候,再把各个程序片段在内存和磁盘之间来回交换。 

3.1 分页

 大部分虚拟存储系统采用的是一种称为分页(paging)的技术。这种方式叫做虚拟页式存储管理。

由程序产生的地址称为虚拟地址(virtual address),它们构成了一个虚拟地址空间(virtual address space)。虚拟地址也叫做线性地址(linear address)。

如果计算机没有使用虚拟存储机制,那么虚拟地址就是最终的物理地址,它被直接放在地址总线上,从而可以对相应地址的内存单元进行读写操作。如果计算机使用了虚拟存储机制,那么虚拟地址不是直接放在地址总线上,而是被送到存储管理单元(Memory Management Unit,MMU),由它负责把虚拟地址映射为物理地址。MMU一般集成在CPU芯片内部,从逻辑上讲,它可以是单独的一个芯片。     

物理内存空间划分为固定大小的内存块,称为物理页面,或者是页框(page frame)。

虚拟地址空间也划分成大小相同的块,称为虚拟页面,或者简称页面(page)。

页面和页框的大小通常是一样的,要求是2的整数次幂,一般在512字节到1G字节之间。程序在换入换出的时候是以页面为单位

MMU可以完成虚拟地址到物理地址的映射,但是我们知道,虚拟地址空间是远远大于物理地址空间即内存空间的,所以也就不能保证所有虚拟地址能找到对应的物理地址,即无法完成映射。此时,MMU会引发一个缺页中断(page fault),把这个问题交给操作系统处理。操作系统从内存中挑选一个使用不多的物理页面,把它的内容写回到磁盘,从而腾出了一个空闲页面,然后把引发缺页中断的那个虚拟页面装入该空闲页面中,并对地址映射进行更新。最后回到被中断的指令重新开始。

下面我们来看看MMU的内部结构,了解一下它的工作原理。举例:页面大小4KB、虚拟地址空间是64KB、物理内存是32KB,因此可得到16个虚拟页面和8个物理页面。如下图所示,虚拟地址8196(二进制是0010 0000 0000 0100),输入的16位虚拟地址被划分为两部分:4位的页号和12位的偏移量。4位的页号可以表示16个页面,12位的偏移量可以寻址4096个字节。

在进行地址映射时,使用虚拟页面号作为索引去访问页表(page table),从而得到相应的物理地址。如果有效位(页表最低位)为0,则产生缺页中断,陷入操作系统中;否则将页表查到的物理页面号加上偏移量,就得到了15位的物理地址。

3.2 页表

如上所述,虚拟地址被分为虚拟页面号(高位)和偏移量(低位)两部分。高4位指定虚拟页面号,也可以是3位、5位或其他,不同的划分表示不同的页面大小。

页表的用途是将虚拟页面映射为相应的物理页面

上述例子中只是16位的虚拟地址空间,那么32位的虚拟地址空间为4GB,64位的地址空间可达16EB(虽然我们普遍不用这么多位),如果将页面映射放在一个页表中,那么页表项将非常庞大。此外由于每个进程都有自己的虚拟地址空间,因此每个进程也有自己的页表。这样,页表的数量和规模将更加庞大。有没有一种大而快速的页面映射解决方案呢?分级。

(1)多级页表

多级页表的基本思路是:虽然进程的虚拟地址空间很大,但是当进程在运行时,并不会用到所有的虚拟地址,所以没必要把所有的页表项都保存在内存中。

如下图,一个典型的二级页表的例子,虚拟地址为32位,页面大小4KB。虚拟页面号为20位,分成两级,最高10位表示页目录,中间10位为页表,从而形成10+10+12的二级页表。 二级页表也可以扩展为三级、四级或更多级。64位处理器典型地划分为9+9+9+9+12的四级页表。更多的级别带来了更多的灵活性,但算法的复杂性也会更高。 

 

(2)页表项

页目录项和页表项具有相同的结构,但不同的CPU对页表项的具体安排会有所不同,我们讨论一些共性。如下图,给出了一个页表项的示例。页表项的长度因机器而异,一般使用的32位即4字节。

 

 物理页面号------最重要的就是物理页面号,页映射的目的就是找到这个值。

有效位------1表示该表项是有效的,可以使用;0则表示该表项对应的虚拟页面现在不在内存中,访问该页面会引起一个缺页中断。

保护位------指出一个页允许什么样的方式访问,最简单的形式是只有一位,0表示读/写,1表示只读;更先进的方式是使用三位,各位分别表示是否启用读、写、执行该页面。

修改位------记录页面的使用情况,在写入一个页时自动设置修改位。如果一个页面已经被修改过(称为“脏页面”),则必须把它写会磁盘。如果没有被修改过(称为“干净页面”),可以直接被覆盖,因为它在磁盘上有备份。修改位也称为脏位,反映了页面的当前状态。

访问位------不论是读还是写,系统都会在该页面被访问时设置访问位。用于页面置换算法中,未被访问的通常认为是不经常使用的而被置换出去。页面置换我们稍后介绍。

禁止缓存位------禁止该页面被高速缓存,对于映射到设备寄存器而不是常规内存的页面很重要。具有独立的I/O空间而不使用内存映射I/O的机器不需要这一位。高速缓存在下一章介绍。

3.3 关联存储器TLB

 从上面我们可以看出,每一次内存访问,都需要两次访问页表,而随着页表的增多,整体性能是会受很大影响的。后面人们发现绝大多数程序运行时,在任意一个阶段都只会访问一小部分的页面,而非所有页面。这就是访问的局部性原理,或者说程序局部性原理。

人们利用这个特性为计算机设计和增加了一种快速查找的硬件,即TLB(Translation lookaside Buffer)或者称为关联存储器(associative memory),用来存放最常用的页表项。这种硬件设备可以直接把虚拟地址映射到物理地址,而不必访问内存,所以简称为快表。TLB通常位于MMU中,只包含了少量的表项,书上说不超过64,网上有的说不超过256,总之非常少。

工作过程:当一个虚拟地址到来时,MMU首先会到TLB中查找,这个查找非常快,因为它是并行的方式,即同时与所有的页表项进行比较。如果找到了,直接取出物理页面号。否则如果权限够的话将再去内存中查找所需的物理页面号;然后,再将找到的物理页面号所在的页表项添加到TLB中,同时驱逐TLB中某一个页表项;最后将被驱逐的页表项的修改位复制到对应的内存中的页表项。 

软件TLB管理

上面我们描述的硬件TLB,TLB的管理和TLB未命中时的处理都交由MMU硬件完成,只有当页面不在内存中时才会陷入到操作系统

而在现代有些机器中,几乎所有的页面管理工作都是有软件来完成,TLB表项也由操作系统负责载入。如果发生TLB未命中,MMU会产生一个TLB中断,把问题交给操作系统。操作系统来对TLB进行页面置换,但是这项工作必须用很少的命令完成,因为TLB未命中的频率远远高于缺页中断的频率。为此,人们也设计出了一些方法来提高未命中的概率,例如在内存固定位置设置一个较大的缓冲区,存放最近常用的TLB表项;或者预测常用的页面预先装入TLB中。

3.4 反置页表

前面我们讲述的页表方案是通过进程的虚拟页面号来组织的,用虚拟页表号来作为访问页表的索引。如果页面大小4KB,32位寻址时,一个进程的页表项个数是100万。如果再按每个页表项长度是4字节,一个进程的页表需要4MB的内存空间。这是32位,如果变成64位寻址,需要的内存显然是个天文数字。

一种解决方案就是反置页表(inverted page table),也称作倒排页表,根据内存的物理页面号来组织页表,用物理页面号作为访问页表的索引。有多少个物理页面,就在页表中设置多少个页表项。而一般情况下物理页面远远小于虚拟页面,所以这种方法节省了大量的内存空间。但同时也带来一个问题,即从虚拟页面号到物理页面号的转换变得复杂。必须搜索整个页表。

摆脱这种困境就是使用TLB。因为TLB存放了我们经常访问的页面。不过如果TLB未命中,则仍然需要对整个反置页表进行搜索。为了加快加快这个过程,人们又想到了一个办法,使用虚拟地址建立一个哈希表。如果两个虚拟页面具有相同的哈希值,那么它们就用链表连起来。(这种方法是不是似曾相识呢:Redis+MySQL,后面提到LRU方法亦是。)

4、其他

以上对虚拟内存的页式存储管理的基本原理已经介绍完成,我们再深入了解几个知识点。最后补充一下其他的存储管理方式。

4.1 页面置换的算法和策略

虚拟内存的核心就是进程的换入换出,也就是缺页中断进行页面置换。问题来了,如何选择被置换的页面?页面的换进换出是需要开销的,所以一个好的页面算法就是尽量减少页面换进换出的次数。

最优算法------易于描述但无法实现,一般用作目标或者说算法性能评价的依据。思路是:对于每一个虚拟页面,都计算出下一次访问的时间,用指令数来计算,然后选择等待时间最长的那个页面。明显的比较理想,虚拟页面多而且下一次访问也是不确定的。

最近未使用算法------Not Recently Used,NRU。按页表项中的访问位和修改位的值对页面进行分成四类,对应四个值,值越小,越没被使用过。然后在值最小的那类再随机抽取一个页面。

先进先出算法------First In First Out,FIFO。把最先访问的页面放在链表的首部,后面访问的再依次排队在链表的首部,最先的变成了尾部,选择的就是链尾页面。该算法可能会淘汰一些不常用的页面,但是也存在淘汰一些常用只是暂时没用的页面。

第二次机会算法------针对FIFO进行了改进,根据FIFO得到一个页面时不是直接淘汰,而是再给一次机会,把它放在链表的首部。

时钟算法------第二次机会需要移动链表节点,时钟算法将链表变成环形,首尾相连。

最近最久未使用------Least Recently Used,LRU。选择最久未被使用的页面。最优算法的一个近似,它的理论依据是程序的局部性原理。如果某个页面被访问了,它很有可能马上被访问;同样如果它很久没被访问,那么将来可能很长时间也不会被访问。在LRU基础上,利用页表项中的访问位和修改位这两个值和二进制移位,得到改进的算法,叫老化算法。减少了LRU链表的操作。

上面讨论的算法是在一个进程内部,如果在相互竞争的进程之间如何分配呢?有两种策略。

局部分配策略------为每个进程分配固定大小的内存空间。

全局分配策略------所有进程可以动态分配内存空间。通常情况下比局部策略更好,置换页面的时候可以考虑整个内存空间,减少缺页发送的次数。

4.2 工作集模型

页式存储管理中,进程启动之初,所有页面都在外存,所以CPU去取第一个页面时,会引发缺页中断。随着是一系列的缺页中断,一段时间后,中断次数会减少。这种策略就叫做请求调页(demand paging),根据需要随要随调。

而前面我们介绍过局部性原理,绝大多数进程实际访问的页面只是很小的一部分,我们把一个进程当前正在使用的页面集合叫做它的工作集(working set)。如果我们在程序运行前就预先装入它的页面,这种技术叫做预先调页(prepaging)。而装入的页面就是进程运行所需的工作集,这种方法叫做工作集模型。为了实现工作集模型,操作系统必须知道哪些页面属于工作集,一种方法就是前面讨论的老化算法。当然,随着时间的变化,进程的工作集也会发生变化。一般工作集具有渐进式、缓慢变化的特点。

但是进程的工作集有时会发送剧烈的变动,它的运行可能进入一个调整期。如果分配给一个进程的物理页面数太少,不能包含整个工作集,这是进程会造成很多的缺页中断,需要频繁的在内存和外存之间置换页面,从而使得进程的运行速度变慢,我们把这种状态称作抖动(Denning)。同时我们也应该要优化我们的代码尽量减少和避免这种情况的发生!

4.3 页面大小

页面大小在页式存储管理系统中是一个非常重要的参数,也是一个可以自定义的参数。查看系统中页的大小:

[root@localhost mysql]# getconf PAGESIZE
4096

内核是以页面作为内存管理的单位,内存分配时,每次分配都是页面大小的整数倍。页面越小,内碎片就会越少。分配的内存一般不会是页面的整数倍,最后一个页面剩下的空间叫做内碎片。页面越小,同时页表就越庞大,进程运行时系统开销也会越大。

另外,在内存和磁盘之间传送数据也是以页面为单位的。所以文件系统的逻辑块大小最好和页面大小保持一致。

大多数计算机使用的页面大小在512字节到1M之间,典型的值是1KB、4KB和8KB。现在随着内存容量越来越大,页面大小也越来越大。

4.4 段式和段页式存储管理

前面介绍都是跟分页方式相关的虚拟内存。事实上,虚拟内存的调度方式有分页式、段式、段页式3种。只是现在大部分的操作系统使用了分页式,而且理解了分页式,再来看其他两种就非常容易了。

(1)段式存储管理

分页式存储管理是一维的,而段式则是二维的。即分页式存储的虚拟地址从0到某一个最大地址,一个接一个。而段式存储提供多个相互独立的地址空间,称为段(segment);每个段的内部都是从0到某一个最大值这样一个线性地址,段的长度可以动态变化。

分段有助于在几个进程之间共享函数和数据,一个典型的例子就是共享库(shared library)。页式存储管理也可以实现共享库,但是要复杂得多,实际上它们都是通过模拟分段来实现的

在具体实现上,段式和页式存储系统是完全不同的:页面是定长的而段不是。所以,随着程序的运行,段式存储很容易形成外碎片(external fragmentation)或者叫做跳棋盘(checkerboarding)。外碎片通常比较小,无法再装入新的段,容易造成浪费。当然这个问题也可以通过前面2.2节讲过的紧缩技术来解决。

(2)段页式存储管理

Intel Pentinum支持16K个段,每个段最多可以容纳4GB的虚拟地址空间。操作系统可以对其进行设置,使他支持纯页式、纯段式或者段页式存储管理。大多数操作系统如Linux和Windows都采用纯页式存储管理。

Pentinum虚拟存储器的核心是两张表,局部描述符(Local Descriptor Table,LDT)和全局描述符(Global Descriptor Table,GDT)。每个进程都有自己的LDT,但是GDT只有一个,为计算机上所有进程共享。LDT描述的是每个程序自己的段,包括代码段、数据段、栈段等,而GDT描述的是系统的段,包括操作系统本身。

 

上图是Pentinum代码段描述符的结构,数据段略有不同。本文不再铺开描述了,有兴趣可以参考:分段机制与GDT|LDT

 

 

推荐阅读:Linux内核之 内存管理 

 

 

参考资料:

《操作系统设计与实现》第三版 上册。

《深入理解LINUX内核》第三版。