哈工大李治军老师操作系统笔记【23】：内存换出（Learning OS Concepts By Coding Them !）
文章目录
- 0 回顾
- 1 换出
- 1.1 `get_free_page()`
- 1.2 FIFO
- 1.3 MIN
- 1.4 LRU
- 1.5 LRU+时间戳
- 1.6 LRU+页面栈
0 回顾
- 有换入就应该有换出
- 从get_free_page来
- 换入和换出应该合着一起工作
1 换出
get_free_page()是换入的时候得到一个物理空闲页- 并不是总有新的空闲页，因为内存是有限的
- 所以必须要选择一个页换出去，这一部分主要讲的是算法
- 这个算法实现的功能就是：
- 把哪一页从内存当中换到磁盘上，从店面中把哪个商品放到仓库中，腾出地方来，放入别的商品，腾出内存来，换入别的页，所以需要选择一页淘汰，换出到磁盘，应该选择哪一页？
- 这个算法放哪里？放在
get_free_page()，那么，这个出现在哪里？出现在页面中断处理程序，do_no_page里面，就是14号中断的处理程序当中 - 那里做啥事呢？首先申请一个空闲页，然后从磁盘上读入，那么现在申请空闲页的时候，那肯定有个方法，计算一下是不是空闲页不够了，如果不够了，要找一页换出去然后再申请，所以这部分代码就应该放到这里
1.1 get_free_page()
- 缺页中断处理程序中，在从磁盘读入数据之前，首先要通过调用
get_free_page()在物理内存中分配页get_free_page()并不能总是获得新的页，内存是有限的- 需要选择一页淘汰，置换算法
- FIFO
- MIN
- LRU，重点（LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰）
1.2 FIFO
- FIFO
- 使用缺页次数来评价置换算法
- 下例使用FIFO的缺页次数是7（每次缺页都是要去磁盘读写的）
1.3 MIN
- 选最远将使用的页淘汰，是最优方案
- 还是上方的序列，D要换入，但是C距离最远，所以选C换出再D换入
- 但这种算法基本不可能实现，因为无法预测哪一页最晚使用
- 这是个理想算法，操作系统做不到，但可以近似想这个最优来靠近
- 下例使用MIN的缺页次数是5
1.4 LRU
- LRU
- 用过去的历史预测将来
- 局部性原理（正是有了局部性，才可以换入换出）
- LRU是公认的很好的页置换算法
- 我记得有一个算法很容易和LRU搞混，是哪个？
- 下例使用LRU的缺页次数是5，达到了和MIN一样的效果
用过去的历史预测将来，来达到近似MIN
LRU算法：选最近最长一段时间没有使用的页淘汰（最近最少使用）
1.5 LRU+时间戳
- LRU的准确实现，全局时钟+时间戳方案
- 维护一个全局时钟，每页维护维护一个时间戳，表示这一页的最近使用时间
- 则选择最近使用时间最早（最小）的页淘汰，所以把上述的D把C给换掉了
- 算法实现很简单，但是需要遍历找到最小值，时间复杂度较高，不可行
- 每执行一条指令的时候，就要把页的时间戳进行修改
1.6 LRU+页面栈
- LRU的准确实现，页码栈方案
- 新来的页，如果栈空间还够，就加到栈顶
- 新来的页，如果栈空间不够，则淘汰栈底元素，新来的加再加入栈顶
- 已有的页，从栈里原来的位置移到栈顶
- 从栈顶到栈底，是按照最近使用时间戳从大到小的顺序排列的
- 代码实现：双向链表+Map，当年实习面试好像问的就是这个，时间复杂度仍然不低，所以实际操作系统不用这种算法
- 如图，在栈的顶部总是保留最近使用的
- 然后要使用的就上浮，短时间使用的就下降
- 这其实是deque
- 实现代价也不小
- 双向列表+hash表 ； 已经存在的不换出，但是要把他放到首位，其它的依次下沉；如果不存在，就将新的放在首位，末尾移出
