虚拟内存管理.pdf

1 操作系统操作系统 第六讲 虚拟内存管理 第2部分 陈渝 清华大学计算机系 2014年秋季 2 提提纲 页面置换算法 功能与目标 实验设置与评价方法 局部页面置换算法 最优页面置换算法 (opt, optimal) 先进先出算法 (fifo) 最近最久未使用算法 (lru, least recently used) 时钟页面置换算法 (clock) 最不常用算法 (lfu, least frequently used) belady现象 lru、fifo和clock的比较 全局页面置换算法 工作集模型 工作集页置换算法 缺页率置换算法 3 2015/1/23 功能目标功能目标 功能：当缺页中断发生，需要调入新的页面而内存功能：当缺页中断发生，需要调入新的页面而内存 已满时，选择内存当中哪个物理页面被置换。已满时，选择内存当中哪个物理页面被置换。 目标：目标：尽可能地减少页面的换进换出次数尽可能地减少页面的换进换出次数（即缺页（即缺页 中断的次数）。具体来说，把未来不再使用的或短中断的次数）。具体来说，把未来不再使用的或短 期内较少使用的页面换出，通常只能在局部性原理期内较少使用的页面换出，通常只能在局部性原理 指导下依据过去的统计数据来进行预测；指导下依据过去的统计数据来进行预测； 页面锁定页面锁定(frame locking)：用于描述必须常驻内存的：用于描述必须常驻内存的 操作系统的关键部分或时间关键操作系统的关键部分或时间关键(time-critical)的应的应 用进程。实现的方法是：在页表中添加锁定标志位用进程。实现的方法是：在页表中添加锁定标志位 (lock bit)。 4 实验设置与置与评价方法价方法 记录一个进程对页访问的一个轨迹 举例: (虚拟) 地址跟踪(页号, 位移). (3,0), (1,9), (4,1), (2,1), (5,3), (2,0), (1,9), (2,4), (3,1), (4,8) 生成页面轨迹 3, 1, 4, 2, 5, 2, 1, 2, 3, 4 (替换如 c, a, d, b, e, b, a, b, c, d) 模拟一个页面置换的行为并且记录产生页缺失数的数量 更少的缺失, 更好的性能 5 2015/1/25 1. 最优页面置换算法最优页面置换算法 基本思路：当一个缺页中断发生时，对于保存基本思路：当一个缺页中断发生时，对于保存 在内存当中的每一个逻辑页面，计算在它的下在内存当中的每一个逻辑页面，计算在它的下 一次访问之前，还需等待多长时间，从中选择一次访问之前，还需等待多长时间，从中选择 等待时间最长的那个，作为被置换的页面。等待时间最长的那个，作为被置换的页面。 这只是一种理想情况，在实际系统中是无法实这只是一种理想情况，在实际系统中是无法实 现的，因为操作系统无从知道每一个页面要等现的，因为操作系统无从知道每一个页面要等 待多长时间以后才会再次被访问。待多长时间以后才会再次被访问。 可用作其他算法的性能评价的依据（在一个模可用作其他算法的性能评价的依据（在一个模 拟器上运行某个程序，并记录每一次的页面访拟器上运行某个程序，并记录每一次的页面访 问情况，在第二遍运行时即可使用最优算法问情况，在第二遍运行时即可使用最优算法 ）。）。 6 1 最优页面置换算法最优页面置换算法(clairvoyant) 置换的页面是在将来最长时间不需要的页面 c adb eb abc d faults page frames 0 1 2 3 a b c d 1 234 56 7 89 100 requests time a = 7 b = 6 c = 9 d = 10 time page needed next a b c d a b c d a b c d a b c d a b c e a b c e a b c e a b c e a b c e 7 2015/1/27 2. 先进先出算法先进先出算法 先进先出算法（先进先出算法（first-in first-out, fifo）；）； 基本思路：选择在内存中驻留时间最长的页面基本思路：选择在内存中驻留时间最长的页面 并淘汰之。具体来说，系统维护着一个链表，并淘汰之。具体来说，系统维护着一个链表， 记录了所有位于内存当中的逻辑页面。从链表记录了所有位于内存当中的逻辑页面。从链表 的排列顺序来看，链首页面的驻留时间最长，的排列顺序来看，链首页面的驻留时间最长， 链尾页面的驻留时间最短。当发生一个缺页中链尾页面的驻留时间最短。当发生一个缺页中 断时，把链首页面淘汰出局，并把新的页面添断时，把链首页面淘汰出局，并把新的页面添 加到链表的末尾。加到链表的末尾。 性能较差，调出的页面有可能是经常要访问的性能较差，调出的页面有可能是经常要访问的 页面，并且有页面，并且有belady现象现象。fifo算法很少单独算法很少单独 使用。使用。 8 fifo 简单实现 一个单一指针足够 在4个页帧中执行: 假定初始 a-b-c-d 顺序 c a d b e b a bc d faults page frames 0 1 2 3 a b c d 1 234 56 7 8 9 100 requests time physical memory 0 2 3 frame list a b c d a b c d a b c d a b c d e b c d e b c d e a c d e a b d e a b c d a b c 9 2015/1/29 3. 最近最久未使用算法最近最久未使用算法 最近最久未使用算法最近最久未使用算法 (least recently used, lru); 基本思路：当一个缺页中断发生时，选择最久未基本思路：当一个缺页中断发生时，选择最久未 使用的那个页面，并淘汰之。使用的那个页面，并淘汰之。 它是对最优页面置换算法的一个近似，其依据是它是对最优页面置换算法的一个近似，其依据是 程序的局部性原理，即在最近一小段时间（最近程序的局部性原理，即在最近一小段时间（最近 几条指令）内，如果某些页面被频繁地访问，那几条指令）内，如果某些页面被频繁地访问，那 么在将来的一小段时间内，它们还可能会再一次么在将来的一小段时间内，它们还可能会再一次 被频繁地访问。反过来说，如果在过去某些页面被频繁地访问。反过来说，如果在过去某些页面 长时间未被访问，那么在将来它们还可能会长时长时间未被访问，那么在将来它们还可能会长时 间地得不到访问。间地得不到访问。 10 最近最未被使用算法最近最未被使用算法(lru)最久未使用算法最久未使用算法 置换的页面是最长时间没有被引用的 c a d b e b a b c d faults page frames 0 1 2 3 a b c d 1 23 4 5 6 7 8 9 100 requests time a = 2 b = 4 c = 1 d = 3 time page last used a = 7 b = 8 e = 5 d = 3 a = 7 b = 8 e = 5 c = 9 a b c d a b c d a b c d a b c d a b e d a b e d a b e d a b e d a b e c a b d c 11 2015/1/211 lru算法需要记录各个页面使用时间的先后顺序，算法需要记录各个页面使用时间的先后顺序， 开销比较大。两种可能的实现方法是：开销比较大。两种可能的实现方法是： 系统维护一个页面链表，最近刚刚使用过的页面系统维护一个页面链表，最近刚刚使用过的页面 作为首结点，最久未使用的页面作为尾结点。每作为首结点，最久未使用的页面作为尾结点。每 一次访问内存时，找到相应的页面，把它从链表一次访问内存时，找到相应的页面，把它从链表 中摘下来，再移动到链表之首。每次缺页中断发中摘下来，再移动到链表之首。每次缺页中断发 生时，淘汰链表末尾的页面。生时，淘汰链表末尾的页面。 设置一个活动页面栈，当访问某页时，将此页号设置一个活动页面栈，当访问某页时，将此页号 压入栈顶，然后，考察栈内是否有与此页面相同压入栈顶，然后，考察栈内是否有与此页面相同 的页号，若有则抽出。当需要淘汰一个页面时，的页号，若有则抽出。当需要淘汰一个页面时， 总是选择栈底的页面，它就是最久未使用的。总是选择栈底的页面，它就是最久未使用的。 3.least recently used (lru) page replacement 12 用用栈实现lru算法算法 保持一个最近使用页面的“栈” c a d b eb a b c d a a a a a a a a a a b bb bb b b b bb c cc c e e e e e d faults page frames d d d d d d d d cc 0 1 2 3 a b c d 1 23 4 5 6 7 8 9 100 requests time c c a c a d c a d b a d b e a d e b d e b a d e a b e a b c a b c d lru page stack page to replace cde 13 2015/1/213 4. 时钟页面置换算法时钟页面置换算法 clock页面置换算法，页面置换算法，lru的近似，对的近似，对fifo的一的一 种改进；种改进； 基本思路：基本思路： 需要用到页表项当中的访问位，当一个页面被装入内需要用到页表项当中的访问位，当一个页面被装入内 存时，把该位初始化为存时，把该位初始化为0。然后如果这个页面被访问。然后如果这个页面被访问 （读（读/写写),则把该位置为则把该位置为1； 把各个页面组织成环形链表（类似钟表面），把指针把各个页面组织成环形链表（类似钟表面），把指针 指向最老的页面（最先进来）；指向最老的页面（最先进来）； 当发生一个缺页中断时，考察指针所指向的最老页面，当发生一个缺页中断时，考察指针所指向的最老页面， 若它的访问位为若它的访问位为0，立即淘汰；若访问位为，立即淘汰；若访问位为1，则把该，则把该 位置为位置为0，然后指针往下移动一格。如此下去，直到，然后指针往下移动一格。如此下去，直到 找到被淘汰的页面，然后把指针移动到它的下一格。找到被淘汰的页面，然后把指针移动到它的下一格。 14 近似近似 lru: 时钟页面置换算法时钟页面置换算法 维持一个环形页面链表保存在内存中 用一个时钟（或者使用/引用）位来标记一个页面是否经常被访问 当一个页面被引用的时候，这个位被设置（为1） 时钟头扫遍页面寻找一个带有 used bit=0 替换在一个周转内没有被引用过的页面 func clock_replacement begin while (victim page not found) do if(used bit for current page = 0) then replace current page ( 基本思路：当一个缺页中断发生时，选择访问基本思路：当一个缺页中断发生时，选择访问 次数最少的那个页面，并淘汰之。次数最少的那个页面，并淘汰之。 实现方法：对每个页面设置一个访问计数器，实现方法：对每个页面设置一个访问计数器， 每当一个页面被访问时，该页面的访问计数器每当一个页面被访问时，该页面的访问计数器 加加 1。在发生缺页中断时，淘汰计数值最小的。在发生缺页中断时，淘汰计数值最小的 那个页面。那个页面。 lru和和lfu的区别：的区别：lru考察的是考察的是多久未访问多久未访问, 时间越短越好；而时间越短越好；而lfu考察的是考察的是访问的次数访问的次数或或 频度，访问次数越多越好。频度，访问次数越多越好。 问题：一个页面在进程开始时使用问题：一个页面在进程开始时使用 得很多，但以后就不使用了。实现得很多，但以后就不使用了。实现 也费时费力。也费时费力。 解决方法：定期把次数寄存器右移解决方法：定期把次数寄存器右移 一位。一位。 19 5. lfu 问题? 执行在4个页帧中: 假设最初的访问次数: a-8 b- 5 c- 6 d-2 c a d b e b a bc d faults page frames 0 1 2 3 a b c d 1 234 56 7 8 9 100 requests time a b c d a b c d a b c d a b c d e b c d e b c d e a c d e a b d e a b c d a b c 20 2015/1/220 belady现象现象：在采用：在采用fifo算法时，有时会出现算法时，有时会出现 分配的物理页面数增加，缺页率反而提高的异分配的物理页面数增加，缺页率反而提高的异 常现象；常现象； belady现象的原因现象的原因：fifo算法的置换特征与进算法的置换特征与进 程访问内存的动态特征是矛盾的，与置换算法程访问内存的动态特征是矛盾的，与置换算法 的目标是不一致的（即替换较少使用的页面的目标是不一致的（即替换较少使用的页面 ），）， 因此，被它置换出去的页面并不一定是进程不因此，被它置换出去的页面并不一定是进程不 会访问的。会访问的。 21 belady现象现象 fifo123412512345 pf head1 x head x 1 2tail head x 1 3 2 x 2 4 3 x 3 1 4 x 4 2 1 x 1 5 2 1 5 2 1 5 2 x 2 3 5 x 5 4 3 5 4 3 访问顺序 : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 frame size: 3 page fault: 9 fifo page replacement 22 belady 现象现象 fifo123412512345 pf head1 x head x 1 2tail head x 1 3 2 x 2 4 3 head1 2 4 3 1 x 3 5 4 2 2 4 3 1 x 4 1 5 3 x 5 2 1 4 x 1 3 2 5 x 2 4 3 1 x 3 5 4 2 访问顺序 : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 帧大小: 4 页缺失: 10 fifo page replacement 23 belady 现象现象 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 2 3 4 1 2 5 1 2 3 2 2 3 4 1 2 5 1 2 3 4 3 4 1 2 5 1 2 3 4 5 x x x x x x x v v x x x 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 2 3 4 4 4 5 1 2 2 2 2 3 4 1 2 5 1 2 3 3 3 4 1 2 5 1 2 3 4 4 1 2 5 1 2 3 4 5 x x x x v v x v v x x x lru page replacement 时钟/第二次机会页面置换是怎么样的？ 为什么lru页面置换算法没有belady现象？ frame size: 3 page fault: 10frame size: 4 page fault: 8 24 2015/1/224 lru算法和算法和fifo本质上都是先进先出的思路，本质上都是先进先出的思路， 只不过只不过lru是针对页面的是针对页面的最近访问时间最近访问时间来进行来进行 排序，所以需要在每一次页面访问的时候动态排序，所以需要在每一次页面访问的时候动态 地调整各个页面之间的先后顺序（有一个页面地调整各个页面之间的先后顺序（有一个页面 的最近访问时间变了）；而的最近访问时间变了）；而fifo是针对是针对页面进页面进 入内存的时间入内存的时间来进行排序，这个时间是固定不来进行排序，这个时间是固定不 变的，所以各页面之间的先后顺序是固定的。变的，所以各页面之间的先后顺序是固定的。 如果一个页面在进入内存后没有被访问，那么如果一个页面在进入内存后没有被访问，那么 它的最近访问时间就是它进入内存的时间。换它的最近访问时间就是它进入内存的时间。换 句话说，如果内存当中的所有页面都未曾访问句话说，如果内存当中的所有页面都未曾访问 过，那么过，那么lru算法就退化为算法就退化为fifo算法。算法。 例如：给进程分配例如：给进程分配3个物理页面，逻辑页面的访个物理页面，逻辑页面的访 问顺序为问顺序为1、2、3、4、5、6、1、2、3 lru、fifo和和clock的比较的比较 25 2015/1/225 lru算法性能较好，但系统开销较大；算法性能较好，但系统开销较大；fifo算算 法系统开销较小，但可能会发生法系统开销较小，但可能会发生belady现象。现象。 因此，折衷的办法就是因此，折衷的办法就是clock算法，在每一次页算法，在每一次页 面访问时，它不必去动态地调整该页面在链表面访问时，它不必去动态地调整该页面在链表 当中的顺序，而仅仅是做一个标记，然后等到当中的顺序，而仅仅是做一个标记，然后等到 发生缺页中断的时候，再把它移动到链表末尾。发生缺页中断的时候，再把它移动到链表末尾。 对于内存当中那些未被访问的页面，对于内存当中那些未被访问的页面，clock算法算法 的表现和的表现和lru算法一样好；而对于那些曾经被算法一样好；而对于那些曾经被 访问过的页面，它不能象访问过的页面，它不能象lru算法那样，记住算法那样，记住 它们的准确位置。它们的准确位置。 26 outline 页面置换算法 功能与目标 实验设置与评价方法 局部页面置换算法 最优页面置换算法 (opt, optimal) 先进先出算法 (fifo) 最近最久未使用算法 (lru, least recently used) 时钟页面置换算法 (clock) 最不常用算法 (lfu, least frequently used) belady现象 lru、fifo和clock的比较 全局页面置换算法 局部页替换算法的问题 工作集模型 工作集页置换算法 缺页率置换算法 抖动问题 27 faults page frames 0 1 2 3 a b c a b c d a b c d a b c d faults page frames 0 1 2 a b c 1 2 3 4 5 6 7 89 1011 120 requests time a a a d d d c c c b b b b b b b aa a d d d c c c c c c c b bb a a a d a a a a aa a a a a a a b bb bbb b b b b b b c cc c c c c c c c c c dd d dd d d d d 局部页替换的问题局部页替换的问题 fifo 页面置换算法: 假设初始顺序 a-b-c 28 工作集模型工作集模型 假设最近引用的页面很有可能不久后再次引用. 并且只保存最近在内存中引用的页面 (称为工作 集) 因此页可能被移除即使在没有页面缺失的情况下 给一个进程分配的帧数量将随时间变化 一个进程只被允许执行它放入到内存中的工作集 工作集模型实现内部的加载控制 29 2015/1/229 5.5 工作集模型工作集模型 前面介绍的各种页面置换算法，都是基于一个前提前面介绍的各种页面置换算法，都是基于一个前提, 即程序的局部性原理。但是此原理是否成立？即程序的局部性原理。但是此原理是否成立？ 如果局部性原理不成立，那么各种页面置换算法如果局部性原理不成立，那么各种页面置换算法 就没有什么分别，也没有什么意义。例如：假设就没有什么分别，也没有什么意义。例如：假设 进程对逻辑页面的访问顺序是进程对逻辑页面的访问顺序是1、2、3、4、5、6、 7、8、9，即单调递增，那么在物理页面数有限，即单调递增，那么在物理页面数有限 的前提下，不管采用何种置换算法，每次的页面的前提下，不管采用何种置换算法，每次的页面 访问都必然导致缺页中断。访问都必然导致缺页中断。 如果局部性原理是成立的，那么如何来证明它的如果局部性原理是成立的，那么如何来证明它的 存在，如何来对它进行定量地分析？存在，如何来对它进行定量地分析？这就是工作这就是工作 集模型！集模型！ 30 2015/1/230 工作集工作集：一个进程当前正在使用的逻辑页面集合，：一个进程当前正在使用的逻辑页面集合， 可以用一个二元函数可以用一个二元函数w(t, )来表示：来表示： t是当前的执行时刻；是当前的执行时刻； 称为工作集窗口（称为工作集窗口（working-set window ），即），即 一个定长的页面访问的时间窗口；一个定长的页面访问的时间窗口； w(t, )在当前时刻在当前时刻 t 之前的之前的 时间窗口当中的时间窗口当中的 所有页面所组成的集合（随着所有页面所组成的集合（随着 t 的变化，该集合的变化，该集合 也在不断地变化）；也在不断地变化）； | w(t, ) | 指工作集的大小，即页面数目。指工作集的大小，即页面数目。 1. 工作集工作集 31 2015/1/231 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 7 如果如果 时间窗口的长度为时间窗口的长度为10，那么：，那么： w(t1, ) = 1, 2, 5, 6, 7 w(t2, ) = 3, 4 一个例子一个例子 页面访问顺序：页面访问顺序： t1 t2 32 2015/1/232 工作集大小的变化：进程开始执行后，随着访问新页工作集大小的变化：进程开始执行后，随着访问新页 面逐步建立较稳定的工作集。当内存访问的局部性区面逐步建立较稳定的工作集。当内存访问的局部性区 域的位置大致稳定时，工作集大小也大致稳定；局部域的位置大致稳定时，工作集大小也大致稳定；局部 性区域的位置改变时，工作集快速扩张和收缩过渡到性区域的位置改变时，工作集快速扩张和收缩过渡到 下一个稳定值。下一个稳定值。 工作集大小 过渡阶段 时间 稳定阶段 33 2015/1/233 2. 常驻集常驻集 常驻集是指在当前时刻，进程实际驻留在内存当中常驻集是指在当前时刻，进程实际驻留在内存当中 的页面集合。的页面集合。 工作集是进程在运行过程中固有的性质，而常驻工作集是进程在运行过程中固有的性质，而常驻 集取决于系统分配给进程的物理页面数目，以及集取决于系统分配给进程的物理页面数目，以及 所采用的页面置换算法；所采用的页面置换算法； 如果一个进程的整个工作集都在内存当中，即常如果一个进程的整个工作集都在内存当中，即常 驻集驻集 （）工作集，那么进程将很顺利地运行，（）工作集，那么进程将很顺利地运行， 而不会造成太多的缺页中断（直到工作集发生剧而不会造成太多的缺页中断（直到工作集发生剧 烈变动，从而过渡到另一个状态）；烈变动，从而过渡到另一个状态）； 当进程常驻集的大小达到某个数目之后，再给它当进程常驻集的大小达到某个数目之后，再给它 分配更多的物理页面，缺页率也不会明显下降。分配更多的物理页面，缺页率也不会明显下降。 34 工作集工作集页替替换 追踪之前 个的引用 在之前 个内存访问的页引用是工作集， 被称为窗口大 小 example: = 4 references: c c d b c e c e a d faults pages in memory page a page b page c page d 1 2 3 4 5 6 7 8 9 10 0 requests time page e t = 0 t = -1 t = -2 35 2015/1/235 可变分配策略可变分配策略：常驻集大小可变。例如：每个进程在刚开始：常驻集大小可变。例如：每个进程在刚开始 运行的时候，先根据程序大小给它分配一定数目的物理页面，运行的时候，先根据程序大小给它分配一定数目的物理页面， 然后在进程运行过程中，再动态地调整常驻集的大小。然后在进程运行过程中，再动态地调整常驻集的大小。 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的可采用全局页面置换的方式，当发生一个缺页中断时，被置换的 页面可以是在其它进程当中，各个并发进程竞争地使用物理页面。页面可以是在其它进程当中，各个并发进程竞争地使用物理页面。 优缺点：性能较好，但增加了系统开销。优缺点：性能较好，但增加了系统开销。 具体实现：可以使用缺页率算法具体实现：可以使用缺页率算法(pff, page fault frequency)来动态来动态 调整常驻集的大小。调整常驻集的大小。 缺页率页面置换算法 36 2015/1/236 缺页率缺页率 缺页率表示“缺页次数缺页率表示“缺页次数 / 内存访问次数”内存访问次数”(比率比率)或或 “缺“缺 页的平均时间间隔的倒数”。影响缺页率的因素：页的平均时间间隔的倒数”。影响缺页率的因素： 页面置换算法页面置换算法 分配给进程的物理页面数目分配给进程的物理页面数目 页面本身的大小页面本身的大小 程序的编写方法程序的编写方法 37 2015/1/237 若运行的程序的缺页率过高，则通过增加工作集来分配更多的物理页面；若运行的程序的缺页率过高，则通过增加工作集来分配更多的物理页面； 若运行的程序的缺页率过低，则通过减少工作集来减少它的物理页面数。若运行的程序的缺页率过低，则通过减少工作集来减少它的物理页面数。 力图使运行的每个程序的缺页率保持在一个合理的范围内。力图使运行的每个程序的缺页率保持在一个合理的范围内。 缺页率算法缺页率算法 38 缺缺页率率页面置面置换算法算法 一个交替的工作集计算 明确的试图最小化页缺失 当缺页率高的时候-增加工作集