操作系统存储管理之虚拟存储

虚拟存储思想

连续内存分配分页机制分段机制和段页机制中,我们知道了程序的逻辑到物理地址的转换过程,虽然这些机制解决很多内存管理的问题,但是有一个问题并没有解决,就是物理内存和程序的实际大小还是一一对应,一个程序被加载,它的所有内容都被加载到内存中了,这样随着进程的增多,就面临着内存不足,虚拟内存的思想就是不完全依赖于内存的物理大小,计算机能够运行进程所需要内存可以大于物理内存,怎么实现呢?我们只需要将进程经常使用的指令存在内存中,一些不经常使用甚至不使用的数据不放入到内存(这是可能的,因为程序的有一些逻辑不会被执行,或者很少被执行),而是将它存储在我们的硬盘中,需要时,我们才从硬盘中读取该部分数据加载到内存中供CPU使用,这样,我们就可以满足用进程所需的内存远远大于较小的物理内存的情况,这就是虚拟存储的主要思想

按需调页

一般操作系统中,采用的是结合分页机制来实现虚拟内存,当操作系统将一个逻辑地址转换成物理地址时,逻辑地址属于的页帧会出现三种情况:

  • 该页已经存在于内存中,这种情况和分页机制一模一样
  • 该页是错误的页,这种情况在分页机制中也已经存在
  • 该页是正确的页,但是页面不在内存中,需要把页换入内存

因此,虚拟存储主要需要解决第三种情况,就是要实现第三种方式。那么CPU怎么知道该页表项不存在对应的页帧呢?我们知道在页表项中有很多标志位,其中有一个标志位为有效位,CPU在执行指令的时候,访问到页表项中有效位为某一个值时,产生一个中断,这个中断就为缺页,然后在中断响应程序中来处理这个中断,中断响应程序运行在内核中,它是操作系统的内核进程。其实产生缺页中断不止第三种情况才会产生,只要内存中没有查找到叶帧,都会产生缺页中断,也就是第二、三种情况都会产生缺页中断,到底是哪种错误,由我们的中断程序来判断,如果终端程序判断到页错误,则可能会将进程停止或者其他处理,这取决于操作系统。除了刚才提到的页表项中的有效位来标识该页是否有效外(是否存在对应的叶帧),页表项还有其他的标志位,这些标志位在虚拟内存管理当中有也是有很重要作用的

页表项

在i386中,我们MMU对页表项的格式是有固定的规定的,因此我们的中断程序也应该准守这个规定的格式

  • A:访问位:被访问的次数或者访问情况
  • D:修改位,在内存中是否被修改过,如果它是从硬盘中换入的,如果被修改了,再换出时就需要写回,没有修改就不用重新写
  • R/W:如果等于1,表示页面可以被读、写或执行。如果为0,表示页面只读或可执行

另外,页表项中还有外存的地址,就是缺页时该页内容在硬盘上的地址

中断处理过程

如果产生了缺页异常,并且页是有效的,如果在内存中还有空闲的叶帧,整个中断处理的过程为:

  1. 找到一个空的叶帧(可能在空闲叶帧链表中)
  2. 将页表项中外存地址中的内容换入到叶帧中
  3. 重置页表
  4. 将相应页表项的有效位置为v
  5. 重新启动产生缺页指令的进程,并且重新开始执行该指令

注意一条指令可以产生多次缺页中断。如果没有空闲叶帧,就需要置换,从内存中换出,然后将需要的换入到内存中,置换又分为两种,一种是局部置换,指的是在进程创建时,系统给内存分配了固定数量的页,置换时只能在这些页中置换;另一种是全局置换,就是换入时在整个内存中寻找置换的页,局部置换还是全局置换和系统有关,后面的介绍基于局部置换。局部置换下中断处理的过程为:

  1. 找到内存中没有被使用的页
  2. 如果该页的修改位为0,则直接换入
  3. 如果修改位为1,则先换出,再换入
  4. 修改页表,换入的和换出的页表项都需要修改
  5. 重新启动产生缺页指令的进程,并且重新开始执行该指令

缺页的次数直接影响了系统的性能,因此我们的操作系统应该降低缺页率,降低缺页率需要合理的分配叶帧,同时我们的页面置换算法也应该合理,接下来,就来看页面置换算法和叶帧分配算法

页面置换算法

我们在请调和局部置换的条件下来讨论页面置换算法,请调的意思是,进程创建时并不分配页帧,而是执行的时候再按需调入或者置换,而且是局部置换,也就是一个进程能够使用的叶帧是固定数量的

先来先置换算法(FIFO)

一个进程3个叶帧,最初叶帧内容为空,然后按照页的访问串来访问,每次换入时选择最早换入的叶帧进行置换,访问完所有的页,发生缺页的次数为9次,如果是给每个进程分配4个叶帧:

4个叶帧的情况还比3个叶帧时缺页次数多一次,由此可知,先来先置换由于访问串的不同,可能存在不同的情况,因此这种算法不是一种理想的算法。

最佳页面算法

最佳页面算法基本思想是置换在将来最长时间不会访问的页,比如对于上面的第二种情况,这种算法的过程为:

一共只有6次缺页,但是这种算法是理论上可以实现,因为对于操作系统来说,基本不可能预测进程执行顺序,比如对于我们的手机,进程的执行顺序和我们用户的操作有关,因此操作系统不能知道进程的具体访问串。但是这个算法可以作为其他算法一个标杆

最近最少使用算法

这种算法的思想是选择过去没有被使用的时间最长的页面进行置换

这种算法的缺页次数为8,和我们的标杆算法近似接近,但是这种算法是可以很容易实现的,因此这个算法是操作系统实现页面置换算法的基本算法,基于这种算法,又有不同的算法

基于计数器

在页表项中增加一个计数器,记录最后一次访问的时间,时间最早页就是将要被置换的页

基于双向链表

链表的一端表示最近一次访问的页,另一端为最近没有被访问时间最长的页,就会有两种情况,当前访问页在链表中,需要将它取出来重新放进链表头,如果没有,并且链表是满的,就将最长时间一端的移除,然后将新的页放进另一端,但是这种算法可能需要更新链表,就是在链表中有,但是需要将它重新放到链表头,效率就比较低

基于访问位

上面我们知道访问位可能是1位,也可以扩展到8位,我们可以用这8位来表示该页的访问情况,如果没有被访问,则为全0,如果访问了,就将最高位置为1,在一次时钟周期内,就将该8位右移一位,如果这个周期内被访问了,继续将最高位置为1,也就是我们的8位上每一位分别表示上8个时钟周期是否被访问,在选择时,可以直接通过选择访问位值最小的来进行置换

二次机会

根据时钟值和访问位(只需要1位)来决定置换,按照时钟值从远到近排序,但是这种情况会给每一个页两次机会,从时间最久的一端遍历,如果访问位为1,将1变为0,如果是0,就选择这页进行置换

计数算法

页表项增加计数器,这个计数器不是时间,而是一个数字,访问一次该计数器加1,基于这个数,有两种实现

  1. 选择最小值的页进行置换,但是这个值会随着进程执行不断的衰减,防止某个页一直被置换
  2. 认为过去使用得多,将来可能不会被使用,因此置换计数最大的页

这种算法不如最近最少使用算法,因此一般不采用

叶帧分配算法

在请调和局部置换的条件下,进程创建时给进程分配多少叶帧也是非常关键的,比如某一个指令就需要6页,而操作系统只分配3个页给该进程,那么缺页的概率就非常大,所以我们要选择合适的方案来给进程分配适当的页

等分

如果现在有100个叶帧,20个进程,那么将100叶帧等分给20进程,每个进程5个叶帧

等比

按照进程大小比例来分,比如有10个叶帧,一个进程大小为4,一个进程大小为6,则给第一个分配4个叶帧,第二个进程分配6个叶帧

基于优先级

优先级越高的进程分配的叶帧数越多

抖动

如果缺页率过高,CPU的利用率就会降低,为什么呢,因为我们的进程在发送缺页时,会发生中断,而该进程就进入等待队里了,就绪队列的进程越来越少,CPU就认为现在需要使用CPU的进程越来越少,那么就会创建新的进程,而进程越多,内存占用就越高,就会造成更多缺页,这样恶性循环,就会造成CPU的使用率越来越低,在CPU的使用率突然下降的那一段就是抖动

工作集防止抖动

工作集是指在某段时间间隔∆里,进程实际要访问的页面的集合

比如在10次访问中,t1时刻工作集大小为5,在t2时刻,工作集大小为2。操作系统可以通过最近的工作集来给进程分配大于工作集的叶帧数,如果某个时刻,所有进程的工作集之和大于了可用的叶帧数,那么操作系统可以选择一个进程,将它放入等待队列,并把它的叶帧让出来给其他进程使用。操作系统要做的事就是将缺页率降低,但是不能完全降低到没有,如果完全没有,虚拟存储的作用就不复存在了,因此一般需要将缺页率控制在一个区间范围内

坚持原创分享,您的支持将鼓励我不断前行!