页面置换算法

• 此处主要讨论内存-辅存层次的页面置换算法,其是实现虚拟内存的关键之一

• 进程运行时,如果其访问的页面不在内存中,则需要将其从外存调入

• 如果调入之前,内存中已经没有空闲的时候,就需要从内存中调出一页程序或数据,送入磁盘的对换区

• 页面置换算法:选择调出页面的算法

页面算法评价

• 好的页面算法具有较低的页面更换评率
  • 做页面调换的时候,算法应该将之后较长时间不会再次访问的页面调出
  • 而不是(尽量不要)调出还会被频繁使用的那些页面,否则容易引起抖动

最佳置换算法OPT

• 最佳置换算法选择的被淘汰页面

  • 在最长时间内不再被访问的页面(包括以后永不使用的页面)，以便保证获得最低的缺页率。

    • 假设长度为n(访问次数)的有序(区分顺序的)访问序列为$L=0,1,\cdots ,n-1$

      • 即L的元素值i表示第i次访问操作,有顺序区别

    • 假设第i次访存$(i\in [0,n-1))$时发现

      • 分配给进程p的s=3个页架中都有内容,且分别记为

        • $v_1,\cdots ,v_s$
        • 这时需要页面置换,采用OPT算法操作

      • 设$v=v(i)$表示第i次想要访问的页面是v

        • v不一定存在于进程的p的s个页架中,如果不存在,需要从辅存调入

      • 子序列$L(i)=i,\cdots ,n-1$,相当于L的后缀(从第i个元素到最后一个元素)

      • 序列$Lv(i)=v(i),\cdots ,v(n-1)$,表示L(i)包含的各个访存操作要访问的页面号

      • 记$\delta =\delta (i,v_j)=Next(i,v_j)$表示:进程p第i次要求访存,从要发生页面置换的时刻算起,下一次(最近)再访问到页面$v_j$需要的等待时间(跳数,或间隔数)

        • $i\in [0,n-1]$

      • 在OPT算法中

        • $j\in [1,s];$

        • $v_j是页架中已经存在的页面$

        • $\delta (i,v_j)$的计算,

          • 如果子序列$L_i$包含的访存操作要访问的页面序列$Lv(i)$中不存在$v_j$
          • 那么$\delta (i,v_j)=+\infty$,这表示进程p的第i次以及之后的访存都不再访问页面$v_j$
          • 这里就是用跳数$\delta$来衡量’时间’的

        • 在实际笔算的过程中,可通过列表(二维)来求解

          • 在不至于引起混淆的情况下,可以省略掉第一个参数i

      • 计算$M=max(\delta (v_j)),j\in [1,s]$

        • 具体步骤是,分别计算并统计$\delta (v_j),j\in [1,s]$,比较出最大的值,作为M

        • 假设$v_m$满足$\delta (v_m)=M$

        • 被替换的页面就是$v_m$

• 然而，由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，

• 因而该算法无法实现。

• 但可利用该算法去评价其他算法

• 该算法可以对某一个给定的页面访问序列做模拟替换操作(实际上访问序列是难以确定)

例

• 假定页面访问序列为

  • 7,0,1,2,0,3,0,1,2
  • Note:不同的序列(长短/结尾)的不同,都会导致求解过程的不同
  • 访问序列长度为n=20

• 进程p运行时，先将7,0,1三个页面依次装入内存。

  • 由于最初分配个进程p的3个内存页面全为空,因此第一次访问一定会发生缺页

  • 本例中,头3次访问的页面都是互不相同的,因此前三次都发生缺页

    • 但是由于分配的3个页面都是空的,所以这三次缺页都不需要用置换算操作
    • 只需要将缺页的页面调入这三个页架中即可

  • 从第4次访存开始,3个页面都已经有内容了,如果发生缺页,就会调用置换算法执行页面置换

  • 本例中,第4次访存将执行页面置换

    • 采用OPT算法,

    • n次访问的页面序列Lv(i)	Note	7	0	1	2	0	3	0	1	2
      b1		7	7	7	2	2	3	3	3	2
      b2			0	0	0	0	0	0	0	0
      b2				1	1	1	1	1	1	1
      $v_1,v_2,v_3$					7,0,1		2,0,1			3,0,1
      $(\delta (v_1),\delta (v_2),\delta (v_3));$ $\delta (v_j),j\in [1,s]$					($\infty$,2,5)		($\infty ,2,3$)			($\infty$,$\infty$,$\infty$)
      $v_m	使得max(\delta(v_j))$					7		2
      是否缺页	1表示缺页	1	1	1	1		1			1
      是否执行OPT算法	1表示需要执行				1		1			1
      Note										@1

      • @1处表示,当OPT算法执行到结尾的时候,同时发生缺页,那么有可能出现多个替换(淘汰)优先级一致的情况,那么可以随意从中选择一个物理块调换即可

先进先出算法FIFO

• FIFO
• 比较简单,不赘述

最近最久未使用算法LRU

• LRU
• 选择最近最长时间未访问过的页面予以淘汰
  • 它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。
• 该算法为每个页面设置一个访问字段(记录淘汰权重值)，用来记录页面自上次被访问以来所经历的时间，
  • 淘汰页面时选择现有页面中值最大的予以淘汰
  • 更详细的细节参考组成原理中cache的LRU替换算法介绍(比较接近于Clock算法)
• 性能接近OPT算法,实现起来开销较大
  • 需要寄存器和栈等硬件支持

时钟置换算法(CLOCK/NRU)

• CLOCK算法,也叫最近未用算法(NRU)
• 为每帧设置一位访问位，当某页首次被装入或被访问时，其访问位被置为1。
  • 而没有被访问的页架中的旧页面访问位保持不变
• 对于置换算法，将内存中的所有页面视为一个循环队列,并有一个替换指针p(队列内)与之相关联，
• 分配个进程P的页架中包含s个页面,那么应该有s个访问位标记,供CLOCK算法参考
• 当某一页被替换时，该指针p被设置指向被替换页面的下一页。
  • 这使得指针避开最近调入的页面(这是合适的)
    • 如果指针停留在刚调入页面的k,(新调入的页面标记位是1,显然不可能被调出)
    • 因此指向k的下一个页面会更合适(有可能直接将页面调出)
  • 只有需要替换(淘汰)页面的时候,算法扫描s个页架时,才有可能变动指针p
    • 假设算法确定页面q为被淘汰的页面,那么这个页面将载入新的页面,并且指针并设定指向为q的下一个页面
  • 访存命中并不会修改指针p,而仅仅修改被命中的页面的标志位为1

访问位的修改@页面的换出

• 在选择一页淘汰时，只需检查页的访问位。

首次扫描@修改

• 若为1，则**将它置为0**，暂不换出，给予该页第二次驻留内存的机会，再依次顺序检查下一个页面。
• 若为0，就选择该页换出：

二次扫描

• 当首次扫描中,检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去循环检查。

  • 第二轮扫描时,可以保证队列中存在标记位是0的位

• 由于该算法是循环地检查各个页面的使用情况，故称CLOCK算法。

• 但是，因为该算法只有一位访问位，而置换时将未使用过的页面换出，故又称最近未用(NRU)算法。

• 假设页面访问顺序为7,0,1,2,0,3,0,4,2,3,0,3,2,1,3,2，

  • 采用简单CL0CK置换算法，分配4个页帧，每个页对应的结构为(页面号，访问位)，置换过程

页架未满

• 首次访问7,0,1,2时，产生缺页中断，依次调入主存，访问位都置为1。

页架已满

• 访问0时，
  • 已存在，访问位置为1。
• 访问3时，
  • 产生第5次缺页中断，替换指针初始指向帧1，此时所有帧的访问位均为1，
  • 替换指针完整地扫描一周，把所有帧的访问位都置为0，然后回到最初的位置(帧1)，
  • 替换帧1中的页(置换页面操作和置访问位为1)
• 访问0时，
• 已存在，访问位置为1。
• 访问4时，
  • 产生第6次缺页中断，替换指针指向帧2（上次替换位置的下一帧），帧2的访问位为1，将其修改为0，继续扫描，帧3的访问位为0，替换帧3中的页，
  • 然后依次访问2,3,0,3,2，均已存在，每次访问都将其访问位置为1。
• 访问1时
  • 产生缺页中断，替换指针指向帧4，此时所有帧的访问位均为1，又完整扫描一周并置访问位为0，回到帧4，替换之。访问3时，已存在，访问位置为1。
• 访问2时
  • 产生缺页中断，替换指针指向帧1，帧1的访问位为1，将其修改为0，继续扫描，帧2的访问位为0，替换帧2中的页。

小结

• 在页架满的情况下,只有访存的结果只有两种可能
  • 命中,不需要置换
    • 修改标记位即可
    • 指针不动
  • 未命中,需要置换
    • 指针从原位位置开始扫描,扫过的页架的标记位tag执行取反操作
      • 取反操作是对1变0,0变1的一种概括而已
      • 对于0变1的情况可理解为,旧页面被淘汰,新页面刚刚进入,就被访问了,所以访问位立即置为1
    • 在遇到第一个标记位发生0$\to$1变化的页架时,该页架就是要被置换的页架
    • 置换完毕后还要将指针移动到下一个页架,便于下次扫描直接从所指的地方开始启动

改进型CLOCK算法$CLOC{K}^{+}$

• 将一个页面换出时

  • 若该页已被修改过，则要将该页写回磁盘，
  • 若该页未被修改过，则不必将它写回磁盘。

• 可见，对于修改过的页面，替换代价更大。

• 在改进型CLOCK算法中，除考虑页面使用情况外，还增加了置换代价位,即修改位。

  • 在选择页面换出时，优先考虑既未使用过又未修改过的页面。

• 由访问位A和修改位M可以组合成下面四种类型的页面：

  • A=0,M=0:最近未被访问且未被修改，是最佳淘汰页。
  • A=0,M=1:最近未被访问，但已被修改，是次一些的淘汰页
  • A=1,M=0:最近已被访问，但未被修改，可能再被访问,不轻易淘汰
  • A=1,M=1:最近已被访问且已被修改，可能再被访问;最不应该淘汰
  • A的权重更大一点,如果A=1的保留优先级更高,A=0,M=1虽然淘汰代价比较高,但是被再次访问的概率不如A=1的情况,所以仍然先淘汰前者
  • 总之,先看A,如果A相同,再看M

• 内存中的每页必定都是这四类页面之一。

• 在进行页面置换时，可采用与简单CLOCK算法类似的算法，差别在于该算法要同时检查访问位和修改位。

• 算法执行过程如下：

  • 1)从指针的当前位置开始，扫描循环队列，

    • 寻找A=0且M=0的1类页面，将遇到的第一个1类页面作为选中的淘汰页。
    • 在第一次扫描期间不改变访问位A.

  • 2)若第1)步失败，则进行第二轮扫描，寻找A=0且M=1的2类页面。

    • 将遇到的第一个2类页面作为淘汰页。
    • 在第二轮扫描期间，将所有扫描过的页面的访问位都置为0。

  • 3)若第2)步也失败，则将指针返回到开始的位置，并将所有帧的访问位置为0。

    • 这就把问题转化为前两种情况
      • 优先重复第1)步，
      • 并且若有必要，重复第2)步，
    • 容易发现此时一定能找到被淘汰的页。

• 改进型CLOCK算法优于简单CLOCK算法的地方在于，可减少磁盘的I/O操作次数。

  • 但为了找到一个可置换的页，可能要经过几轮扫描，即实现算法本身的开销将有所增加。
  • 操作系统中的页面置换算法都有一个原则，即尽可能保留访问过的页面，而淘汰未访问的页面。

• 简单的CLOCK算法只考虑页面是否被访问过；

  • 改进型CLOCK算法对这两类页面做了细分，分为修改过的页面和未修改的页面。
  • 因此，若有未使用过的页面，则当然优先将其中未修改过的页面换出。
  • 若全部页面都用过(A=1)，还是优先将其中未修改过的页面换出。

抖动

• 在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。
• 系统发生抖动的根本原因是，
  • 系统中同时运行的进程太多，
  • 分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统将所缺页面调入内存。
• 这会使得在系统中排队等待页面调入调出的进程数目增加。
• 显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生处理机的有效利用率急剧下降并趋于零的情况。
• 抖动是进程运行时出现的严重问题，必须采取相应的措施解决它。
• 由于抖动的发生与系统为进程分配物理块的多少有关，于是又提出了关于进程工作集的概念。

工作集

• 工作集是指在某段时间间隔内，进程要访问的页面集合。
• 基于局部性原理，可以用最近访问过的页面来确定工作集。
• 一般来说，工作集W可由时间t和工作集窗口$\tau$大小来确定。
  • 例如，某进程对页面的访问次序如下：
    • 1,4,2,3,5,3,2,2,1,1,1,3,4,5,4,4,2,1,1,3,3
• 假设系统为该进程设定的工作集窗口大小$\tau$为5，
  • 则在$t_1$时刻，进程的工作集为{2,3,5}，
  • 在$t_2$时刻，进程的工作集为{1,2,3,4}。
  • 工作集对工作集窗口内的元素要去重处理得到
    • 集合内元素不重复
• 实际应用中，工作集窗口会设置得很大，即对于局部性好的程序，工作集大小一般会比工作集窗口小很多。
• 工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此，若分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页，所以为了防止这种抖动现象，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。
• 工作集模型的原理是，让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。
  • 落在工作集内的页面需要调入驻留集中，而落在工作集外的页面可从驻留集中换出。
  • 若还有空闲物理块，则可再调一个进程到内存。
  • 若所有进程的工作集之和超过了可用物理块总数，则操作系统会暂停一个进程，将其页面调出并将物理块分配给其他进程，防止出现抖动现象。

MMF@内存映射文件

• 内存映射文件(Memory-Mapped Files)与虚拟内存相似
• 将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，
• 便可以直接访问被映射的文件，而不必执行文件I/O操作，
• 也无须对文件内容进行缓存处理。
• 这种特性非常适合用来管理大尺寸文件。
• 使用内存映射文件所进行的任何实际交互都是在内存中进行的，并且是以标准的内存地址形式来访问的。
• 磁盘的周期性分页是由操作系统在后台隐蔽实现的，对应用程序而言是完全透明的。
• 系统内存中的所有页面都由虚拟存储器负责管理，虚拟存储器以统一的方式处理所有磁盘I/O.
• 当进程退出或显式地解除文件映射时，所有被改动的页面会被写回磁盘文件。
• 多个进程允许并发地内存映射同一文件，以便允许数据共享。
• 很多时候，共享内存是通过内存映射来实现的。
• 进程可以通过共享内存来通信，而共享内存是通过映射相同文件到通信进程的虚拟地址空间实现的。
• 内存映射文件充当通信进程之间的共享内存区域 .
• 一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。

虚拟存储器性能影响因素

• 根据局部性原理，页面较大则缺页率较低，页面较小则缺页率较高。
• 页面较小时，
  • 一方面减少了内存碎片，有利于提高内存利用率：
  • 另一方面，也会使每个进程要求较多的页面，导致页表过长，占用大量内存。
• 页面较大时，
  • 虽然可以减少页表长度，但会使页内碎片增大。
  • 分配给进程的物理块数越多，缺页率就越低，
  • 但是当物理块超过某个数目时，再为进程增加一个物理块对缺页率的改善是不明显的。
  • 可见，此时已没有必要再为它分配更多的物理块，否则也只能是浪费内存空间。
  • 只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。
• 好的页面置换算法可使进程在运行过程中具有较低的缺页率。
  • 选择LRU、CLOCK等置换算法，将未来有可能访问的页面尽量保留在内存中，从而提高页面的访问速度。
  • 延迟写回磁盘
    • 换出已修改过的页面时，应当写回磁盘，如果每当一个页面被换出时就将它写回磁盘，那么每换出一个页面就需要启动一次磁盘，效率极低。
    • 为此在系统中建立一个已修改换出页面的链表，对每个要被换出的页面（已修改)，可以暂不将它们写回磁盘，而将它们挂在该链表上
    • 仅当被换出页面数达到给定值时，才将它们一起写回磁盘，这样就可显著减少磁盘I/O的次数，即减少已修改页面换出的开销。
      • 此外，如果有进程在这批数据还未写回磁盘时需要再次访问这些页面，就不需从外存调入，而直接从己修改换出页面链表上获取，这样也可以减少页面从磁盘读入内存的频率，减少页面换进的开销。
  • 编写程序的局部化程度越高，执行时的缺页率就越低。
  • 如果存储采用的是按行存储，访问时就要尽量采用相同的访问方式，避免按列访问造成缺页率过高的现象。