计算机操作系统27，28

第二十七课虚拟内存Virtual Memory一、什么是虚拟内存一句话虚拟内存是一种让程序感觉自己拥有比实际内存更大空间的技术。例如你的电脑实际8GB RAM但是程序看到几十GB地址空间为什么因为操作系统把一部分内容放内存。一部分内容放硬盘。需要时再调入。类似你的书桌。桌子只能放10本书。但是你有100本书。怎么办不会把100本全部摊桌上。而是桌上放正在看的10本。其他放书柜。需要再换。对应书桌 内存 书柜 外存硬盘 换书 页面调入调出二、为什么需要虚拟内存主要有三个原因。1. 运行大程序以前程序必须全部装入内存。现在不用。例如大型软件100GB。电脑16GB内存。仍然可以运行。因为只加载当前需要部分。2. 提高内存利用率如果10个程序。每个只用20%。以前全部加载浪费。现在只加载需要部分。可以运行更多程序。3. 保护进程每个程序拥有自己的虚拟地址空间。互不影响。三、虚拟内存的核心思想记住一句话离散装入按需调入。什么意思离散装入程序不用连续放。还是分页。按需调入需要哪一页。才加载哪一页。所以虚拟内存建立在分页基础上。四、请求分页系统★★★★★现代操作系统主要使用请求分页存储管理。名字拆开请求需要时才加载。分页程序分成页面。系统开始运行只加载部分页面。例如程序有100页。启动只加载10页。其他不加载。运行访问第50页。发现没有。怎么办产生缺页中断五、什么是缺页中断重点缺页意思当前需要的页面不在内存。例如程序访问页20。页表发现页20 × 不在内存于是发生缺页中断。流程CPU访问页面 ↓ 检查页表 ↓ 发现页面不在内存 ↓ 缺页中断 ↓ 操作系统处理 ↓ 从硬盘调入页面 ↓ 更新页表 ↓ 继续执行六、缺页中断为什么特殊普通中断例如键盘输入。CPU暂停。处理。缺页中断更复杂。因为它需要访问外存。外存很慢。所以缺页代价很高。七、页表中的关键位为了支持虚拟内存页表增加一些信息。① 状态位存在位表示页面是否在内存。例如1在内存 0不在内存② 访问字段记录页面最近是否被访问。后面页面置换算法会使用。③ 修改位表示页面是否被修改。为什么重要因为如果页面没修改。换出去不用写回硬盘。八、虚拟内存工作流程完整过程程序运行 ↓ CPU产生逻辑地址 ↓ 查页表 ↓ 页面存在 ↓ 是 ↓ 访问内存 否 ↓ 缺页中断 ↓ 寻找空闲页框 ↓ 调入页面 ↓ 更新页表 ↓ 继续运行九、局部性原理★★★★★为什么虚拟内存有效因为程序运行有规律。这个规律叫局部性原理。分两种1. 时间局部性意思最近访问过的数据很可能马上再次访问。例如循环for(i0;i100;i){sum;}sum一直使用。2. 空间局部性意思当前访问附近的数据也可能被访问。例如数组a[0]a[1]a[2]通常连续访问。因为存在局部性。所以不用一次加载全部程序。十、虚拟内存的问题虚拟内存很好。但是有一个风险。如果内存太小。程序频繁换入换出。会发生什么CPU大部分时间不是运行程序。而是在搬页面。这种现象叫抖动Thrashing例如学生桌子太小。一本书刚拿出来。马上又放回去。换另一本。一直整理。没有学习。计算机也是一样。十一、本课重点总结★★★★★必须掌握虚拟内存定义让程序逻辑上拥有比物理内存更大的空间。核心思想按需调入 离散存储请求分页需要哪页加载哪页。缺页中断页面不在内存。产生中断。局部性原理为什么虚拟内存有效时间局部性空间局部性抖动频繁页面交换。导致系统性能下降。十二、口诀虚拟内存程序不用全装入需要哪页调哪页。缺页页不在产生中断调入后继续干。局部性刚用还会用附近也可能用。第二十八课页面置换算法Page Replacement Algorithm一、为什么需要页面置换假设内存只有3个页框。现在已经装入页1 页2 页3来了页4。怎么办内存满了。必须选择一个页面换出去。这个过程叫页面置换Page Replacement二、页面置换的目标目标很简单尽量减少缺页次数。为什么因为缺页需要访问硬盘。而硬盘非常慢。所以好的算法应该预测哪个页面以后最不需要。三、算法一最佳置换算法 OPT★★★★★OPTOptimal。中文最佳置换。思想淘汰未来最长时间不会被访问的页面。注意关键词未来。例如当前内存1 2 3下一次访问4未来访问序列1 2 5 1 3 4问换谁看三个页面未来什么时候再次出现。页1马上出现。页2后面出现。页3较晚出现。所以淘汰页3。四、OPT的特点优点理论上最好。缺页次数最低。缺点现实中无法实现。为什么因为操作系统不知道未来。所以OPT主要用于比较其他算法。考试经常问哪个算法缺页最少答案OPT。五、算法二FIFO★★★★★FIFOFirst In First Out。中文先进先出。思想谁最早进入内存就淘汰谁。类似排队买票。最早排队的人先离开。例如三个页框。访问1 2 3 4过程开始空。访问1[1]访问2[1 2]访问3[1 2 3]访问4满了。谁最早页1。淘汰页1。结果[4 2 3]六、FIFO的问题Belady异常★★★★★这是考试重点。正常想内存越大。缺页越少。但是FIFO可能反而更多。这叫Belady异常。例如3个页框缺页9次。增加到4个页框缺页10次。反而增加。为什么因为FIFO只看进入时间。不看使用情况。七、算法三LRU★★★★★LRULeast Recently Used。中文最近最久未使用。思想淘汰最长时间没有被使用的页面。它比FIFO聪明。因为利用局部性原理。例如当前内存1 2 3访问页4。看最近使用情况。如果页1很久没访问。页2刚访问。页3也刚访问。淘汰页1。八、LRU为什么有效因为程序具有时间局部性。如果一个页面很久没使用。那么近期大概率也不会使用。所以LRU性能接近OPT。九、三种算法比较★★★★★算法依据优点缺点OPT未来访问最好无法实现FIFO进入时间简单可能Belady异常LRU过去访问效果好实现复杂口诀OPT看未来 FIFO看年龄 LRU看最近十、缺页次数计算方法重点考试通常给访问序列。例如页访问7 0 1 2 0 3 0 4页框3个。问FIFO缺页次数。步骤画表。例如访问 7 0 1 2 0 3 框1 7 7 7 2 2 2 框2 0 0 0 0 3 框3 1 1 1 1每次新页面进入算一次缺页。十一、一个简单例子页面1 2 3 1 4三个页框。访问1缺页。内存1访问2缺页。1 2访问3缺页。1 2 3访问1已经存在。不缺页。访问4没有。缺页。总缺页4次。十二、LRU和FIFO容易混这是很多人的坑。FIFO问谁进去最早例如进入顺序 1 2 3换1。LRU问谁最近最久没用例如最近3刚用 2刚用 1很久没用换1。可能结果一样。但是判断方法不同。十三、Clock算法了解真实系统很少直接使用纯LRU。因为记录访问时间成本高。所以出现Clock算法。思想模拟LRU。每个页面有一个访问位0 / 1访问设置1。置换寻找访问位为0的页面。408一般重点OPT、FIFO、LRU。十四、本课重点总结★★★★★必须掌握OPT淘汰未来最长时间不用。理论最优。FIFO淘汰最早进入内存页面。可能产生Belady异常。LRU淘汰最近最长时间没使用页面。利用局部性。缺页次数计算画表模拟。十五、最终口诀页面置换最佳看未来 先进看进入 最近看过去