概述
在早期的时候,程序的规模很小,虽然那时候的物理内存也很小,但是也可以容纳下当时的程序。然而,随着技术的发展,应用程序的规模愈来愈大,于是就有了一个难题:应用程序太大,以至于物理内存无法容纳下这样的程序了。通常的做法是将程序分割为许多片段,片段0首先在物理内存中执行,当他执行完成时调用下一个片段1,虽然片段在物理内存中的交换是由操作系统完成的,但是程序员必须手动的对程序进行分割,这是一个费时费力的工作。为了解决这一问题,就有了虚拟内存。
在支持虚拟内存的计算机中,一个程序是运行在虚拟存储器空间的,其大小由处理器的位数决定,其中的某一个地址就称为虚拟地址。和虚拟存储器对应的就是物理存储器,它是现实世界中能够直接使用的存储器。其中的某一个地址便称为物理地址。物理存储器的大小不能超过处理器最大可寻址的空间。
由于虚拟地址无法直接访问物理存储器,所以需要先进行地址转换。负责地址转换的部件,一般被称为内存管理单元MMU,如下图所示:
使用虚拟地址的好处,第一个就是用户在编写程序时,不需要考虑地址的限制,每个程序都认为只有自己在处理器中运行,它占有处理器的所有地址空间。
此外,使用虚拟内存还可以实现程序的保护。即使两个程序使用相同的虚拟地址,它们也会对应到不同的物理地址,因此可以保证每个程序的内容不会被其他的程序改写。而且,通过这种方式,还可以实现程序之间的共享,只需要让两个程序的虚拟地址映射到同一个物理地址便可以实现。
地址转换
这里我们讲述基于分页的虚拟存储器,这也是最常见的虚拟存储器。在这种分页机制下,虚拟地址空间以页(page)为单位进行划分,典型的页大小为4KB。相应的物理地址空间也进行同样大小的划分,由于历史原因,物理地址空间中不叫做页,而称为frame,它和页大小必须相等。
当程序开始运行的时候,会将当前需要的部分内容从硬盘中搬移到物理内存中,每次搬移的单位就是一个页大小。由于只有在需要的时候才将一个页的内容放到物理内存中,因此这种方式页称为demand page。
对于一个虚拟地址VA来说,VA[11:0]用来表示页内的位置,称为page offset,VA内剩余的部分用来表示哪个页,也称为VPN(Virtual Page Number)。相应的,对于一个物理地址PA来说,PA[11:0]表示frame内的偏移,称为frame offset,而PA剩余的部分用来表示哪个frame,也称为PFN(physical frame number)。由于页和frame的大小相同,所以VA到PA的转换实际就是VPN到PFN的转换,offset部分是保持不变的。
当处理器将一个虚拟地址VA送到MMU后,MMU会查询是否存在有效的frame,和该VA所对应的页相对应。如果存在,则相应的物理地址便会得到,如果不存在,MMU就会触发一个Page Fault的异常送给处理器。这个时候处理器就需要转到Page Fault对应的异常处理程序中处理这个事情(这个异常处理程序其实就是操作系统的代码)。
单级页表
在虚拟存储系统中,都是使用一张表格来存储从虚拟地址到物理地址的对应关系,这个表格称为页表(Page Table, PT)。
这个表格一般存放在物理内存中,使用虚拟地址来寻址,表格中被寻址到的内容就是这个虚拟地址所对应的物理地址。每个程序都有自己的页表,将这个程序中的虚拟地址映射到物理内存中的某个地址。为了指示一个程序的页表在物理内存中的位置,在处理器中一般都会包括一个寄存器,用来存放当前运行程序的页表在物理内存中的起始地址,这个寄存器称为页表寄存器(Page Table Register, PTR),每次操作系统将一个程序调入物理内存中执行的时候,就会将寄存器PTR设置好。
上图展示了通过页表进行地址转换的过程,首先,通过PTR得到页表在物理内存中的位置,然后将虚拟地址送给MMU,并以此为索引查表,如果对应valid为1,则表示该虚拟地址所对应的页已经被操作系统映射到物理内存中的某个frame。如果valid为0,则表示该虚拟地址对应的页还未被操作系统映射到物理内存中的某个frame,此时会产生page fault,需要操作系统从更下一级的存储器中将这个页对应的内容搬运到物理内存中。
需要注意的是,页表的结构是不同于cache的,在页表中包括了所有VPN的映射关系,所以可以直接使用VPN进行寻址,而不需要使用TAG。
下面来考虑页表的大小。假设页大小为4KB,虚拟地址空间的大小为4GB,则页表的每一个表项,其大小为1(valid)+20(PFN)=21位,实际情况下,每一个表项还会有一些额外的bit,并且,由于处理器一般是按照字节寻址的,所以每一个表项的实际占用空间,一般情况下为4Byte。这样的表项一共有4GB/4KB=1M,所以页表的大小应该为1M×4Byte=4MB。
由于每个进程都有一个页表,因此,当处理器中并发运行的进程数目较多时,页表的空间占用便不能忽略不计了(对于64位的处理器更是如此)。
为了减少进程的页表对于存储空间的需求,多级页表应运而生。
多级页表
多级页表如上图所示。它分为第一级页表和第二级页表。第一级页表中的每一项,都指向一个第二级页表的基地址。而第二级页表中的每一项,则代表一个虚拟地址到物理地址的映射关系。
这样,要得到一个虚拟地址对应的数据,首先需要访问第一级页表,得到这个虚拟地址所属的第二级页表的基地址,然后再去第二级页表中才可以得到这个虚拟地址对应的物理地址,这个时候就可以在物理内存中取出相应的数据了。
举例来说,对于一个32位虚拟地址、页大小为4KB的系统来说,如果采用线性页表,则页表中的表项个数为1M。将其分为1024等份,每一个等份就是一个第二级页表,共有1024个第二级页表,对应这第一级页表中的1024个表项。也就是说,第一级页表需要10位地址进行寻址,每个第二级页表中,表项的个数是1M/1024=1024个,也需要10位地址才能寻址第二级页表。如下图所示:
在这种多级页表结构中,仍然需要使用一个寄存器来存储第一级页表在物理内存中的基地址,即PTR寄存器。
下面,对虚拟存储器的优点进行一个总结:
- 让每个程序都有独立的地址空间。
- 引入虚拟地址到物理地址的映射,为物理内存的管理带来了方便,可以灵活地对其进行分配和释放。
- 在处理器中如果存在多个进程,为这些进程分配的物理内存之和可能大于实际可用的物理内存,虚拟存储器的管理使得这种情况下各个进程仍然能够正常运行。此时为各个进程分配的只是虚拟存储器的页,这些页可能存在于物理内存中,也可能临时存在于更下一级的硬盘中。在硬盘中的这部分空间称为swap空间。当物理内存不够用时,将物理内存中的一些不常用的页保存到硬盘上的swap空间,而需要使用到这些页时,再将其从硬盘的swap空间加载到物理内存。因此,处理器中等效可以使用的物理内存的总量是物理内存的大小+硬盘中swap空间的大小。
将一个页从物理内存中写到硬盘的swap空间的过程称为Page Out,将一个页从硬盘的swap空间放回物理内存的过程称为Page In。该过程如下图所示:
- 利用虚拟存储器,可以管理每一个页的访问权限,从硬件的角度来看,单纯的物理内存本身不具备各种权限的属性,它的任何地址都可以被读写。而操作系统则要求在物理内存内实现不同的访问权限,例如代码段的属性是可读可执行,但不能被修改;而一个进程的数据段要求是可读可写的;同时用户进程不能访问属于内核的地址空间。这些权限的管理就是通过页表实现的,通过在页表中设置每个页的属性,操作系统和MMU可以控制每个页的访问权限,这样就实现了程序的权限管理。
page fault
page fault是异常的一种,通常它的处理过程不是由硬件完成,而是由软件完成的。
在现代处理器中,一旦虚拟地址在访问页表时,发现对应的PTE还未保存相应的映射关系(即valid=0),那么硬件就会产生一个page fault类型的异常,处理器会跳转到这个异常处理程序的入口地址,异常处理程序会根据某种替换算法,从物理内存中找到一个空闲的地方,将需要的页从硬盘中搬移进来,并将这个新的对应关系写到页表中相应的PTE内。
需要注意的是,直接使用虚拟地址并不能知道一个页位于硬盘的哪一个位置,也需要一种机制来记录一个进程的每个页位于硬盘中的位置。通常,操作系统会在硬盘中为一个进程的所有页开辟一块空间,这就是之前所说的swap空间,在这个空间中存储一个进程所有的页,操作系统在开辟swap空间的同时,还会使用一个表格来记录每个页在硬盘中存储的位置,这个表的结构其实和页表类似,可以单独存在。
事实上,物理内存可以理解为硬盘的cache。现考虑如下场景:
一个程序的某个内容既存在于物理内存,也存在于硬盘中,当这个物理内存中的内容被修改时,硬盘中的内容就过时了。针对这一情况,有两种处理方法:
- 写通,将这个地址的修改内容立即更新到硬盘中,考虑到硬盘的访问时间非常慢,这种方法不太可取。
- 写回,只有等到这个地址的内容在物理内存中要被替换时,才将这个内容写回到硬盘中,这种方式减少了硬盘的访问次数,因而被广泛使用。
为了支持写回这一策略,需要在页表的每个PTE中增加一个脏的状态位,当一个页内的某个地址被写入时,这个脏的状态位会被置1。当操作系统需要将一个页进行替换前,会首先去页表中检查它对应PTE的脏状态位,若为1,则需要先将这个页的内容写回到硬盘中;若为0,则表示这个页从来没有被修改过,那么就可以直接将其覆盖了,因为在硬盘中还保存着这个页的内容。