Chapter 22 Beyond Physical Memory: Strategies
第 22 章 超越物理内存：策略
In a virtual memory manager, life is easy when you have a lot of free memory. A page fault occurs, you find a free page on the free-page list, and assign it to the faulting page. Hey, Operating System, congratulations! You did it again.
只需要一直恭喜就好了...
但是内存不够的时候会变得 fun...由于 memory pressure 迫使 OS paging out 一些页...确定要 evict 哪个页...封装在操作系统的替换策略...
1. 缓存管理
深入研究策略之前，描述一下问题：
公式：AMAT = P(Hit) * TM + P(Miss) * TD)
where TM represents the cost of accessing memory, TD the cost of accessing disk, and PMiss the probability of not finding the data in the cache (a miss); PMiss varies from 0.0 to 1.0, and sometimes we refer to a percent miss rate instead of a probability (e.g., a 10% miss rate means PMiss = 0.10). Note you always pay the cost of accessing the data in memory; when you miss, however, you must additionally pay the cost of fetching the data from disk...
外国人数学果然不太好？？
1.1. 遗憾
现代系统中 磁盘访问的成本非常高...及时很小概率的未命中，也会拉低正在运行的程序的总体 AMAT...
2. 最优替换策略
能够达到总体 miss 数量最少，但是很难实现...
替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低...
Think about it like this: if you have to throw out some page, why not throw out the one that is needed the furthest from now?
2.1. 例子
在一开始会发生三次未命中，这是必要的，因为 cache 一开始是空的...
这种未命中称作冷启动未命中...cold-start miss 或 强制未命中... compulsory miss
总之就是能够预知未来的访问情况？所以能够 page out 一些最后访问的 page...
2.2. 遗憾
未来是不可阈值的...所以这只能充作一个标准（标准答案）来了解我们当前的方案得分如何？
Unfortunately, as we saw before in the development of scheduling policies, the future is not generally known; you can’t build the optimal policy for a general-purpose operating system1 . Thus, in developing a real, deployable policy, we will focus on approaches that find some other way to decide which page to evict. The optimal policy will thus serve only as a comparison point, to know how close we are to “perfect”.
3. 简单策略：FIFO
先进先出的策略...
先 in 的 先 out...
利用 queue 来管理...
避免尝试达到最优的复杂性
一般来说认为刚访问完的不会立即访问？
不会连着两次访问？这种也只能是蒙的，现实谁知道呢？
3.1. 评分
这样的策略显然不如 optimal policy...但是也很高！
4. 另一简单策略：随机
内存满的时候，随机选择一个页进行替换，随机具有类似FIFO的属性，实现起来简单...
4.1. 事实
Random的表现完全取决于多幸运（或者多不幸）...
5. 利用历史数据：LRU
FIFO 和 Random 都无法避免 page out 一个重要的页...
5.1. 更智能
使用历史信息频率...如果一个页被访问了多次，也许不应该被替换...
A more commonlyused property of a page is its recency of access; the more recently a page has been accessed, perhaps the more likely it will be accessed again.
5.2. 局部性原则 principle of locality
which basically is just an observation about programs and their behavior
空间局部性
spatial locality
时间局部性
temporal locality
5.3. Least-Frequently-Used LFU
与之相反 还有
Most-Frequently-Used MFU
大多数情况下不好，因为忽略了 程序的局部性原则
5.4. Least-Recently-Used LRU
同理还有 Most-Recently-Used MRU
6. 工作负载
workload
分析程序的局部性...
7. 基于历史信息的算法
LRU这样的算法通常由于 FIFO 或 Random...
那么如何实现？
7.1. 如何知道历史信息
每次也访问，我们都要记录下来，这引发新的问题：
用什么数据结构？
时间 空间 复杂度？
这样的策略是高性能消耗的！
那么我们能不能通过实现类似 LRU 的策略，一方面减少性能消耗，一方面得到优秀的表现
8. 近似LRU
这更为可行...实际上也是现代操作系统的做法...
8.1. 增加一个 use bit
需要增加一个使用位/引用位 reference bit
8.2. 时钟算法
clock algorithm
Imagine all the pages of the system arranged in a circular list. A clock hand points to some particular page to begin with (it doesn’t really matter which). When a replacement must occur, the OS checks if the currently-pointed to page P has a use bit of 1 or 0. If 1, this implies that page P was recently used and thus is not a good candidate for replacement. Thus, the use bit for P is set to 0 (cleared), and the clock hand is incremented to the next page (P + 1). The algorithm continues until it finds a use bit that is set to 0, implying this page has not been recently used (or, in the worst case, that all pages have been and that we have now searched through the entire set of pages, clearing all the bits).
这是一个早期的成熟算法，在最坏的情况下，也只会遍历一次内存...
9. 考虑脏页
时钟算法的修改
9.1. 考虑改页变脏
对内存中的页是否被修改的额外考虑。
如果页被修改 modified，并因此变脏，则踢出他就必须将他写回磁盘...这很昂贵...
如果页没有被修改，因此是干净的 clean...踢出就没有成本...物理帧可以简单地重用于其他目的而无需额外的I/O...
Thus, some VM systems prefer to evict clean pages over dirty pages.
10. 其他虚拟内存策略
页面替换不是唯一策略（but most important）
10.1. 操作系统必须决定何时将页载入内存...
页选择 page selection
按需分页 demand paging
预取 prefetching 操作系统猜测一个页面即将被使用 从而提前载入...
10.2. 操作系统如何将页面写入disk...
可以简单的一次写出一个，但是更多会手机一些待完成写入，并高效一次性写入disk
This behavior is usually called clustering or simply grouping of writes, and is effective because of the nature of disk drives, which perform a single large write more efficiently than many small ones.
聚集写入 或是 分组写入
11. 抖动
内存被超额请求时，OS 应该做什么？
11.1. thrashing
不断进行换页...给定一组进程，系统可以决定不运行部分进程，希望减少的进程工作集...以便写入
it called 准入控制 admission control
11.2. 更严格地方法
某些版本的 Linux 会运行 out-of-memory killer，这个守护进程选择一个内存密集型进程并杀死他...
但是可能误杀很重要的程序...
过度分页的最佳方案往往很简单：购买更多内存
12. 作业（模拟作业）
此模拟器 paging-policy.py 允许您尝试不同的页面替换策略。
这里省略具体问题...以及解决方案...
Last updated