操作系统内存换出---15
- 有换入，就应该有换出!
- get_free_page
- FIFO页面置换
- MIN页面置换
- LRU页面置换
- LRU的准确实现，用时间戳
- LRU准确实现，用页码栈
- LRU近似实现 - 将时间计数变为是和否
- Clock算法的分析与改造
- 置换策略有了，还需要解决一个问题
- get_free_page
- 小结
有换入，就应该有换出!
上一节主要讲了内存的换入，那么有换入就必须要有换出。
要换出就需要考虑该将当前物理内存中那一部分数据换出，这就涉及到相关算法，就和进程的调度算法一样。
get_free_page
get_free_page用于向物理内存申请一个新的空闲页面，该函数中肯定就包含了换出的逻辑，因此我们来研究一下该函数的实现:
代码语言：javascript复制page=get_free_page();
bread_page(page, current->executable->i_dev, nr);并不能总是获得新的页，内存是有限的
FIFO页面置换
FIFO算法好吗?
评价一个算法的好坏，要看该算法在当前场景下，是否符合我们的优化目标，我们的目标是换出一个最不经常会被使用到的页，尽可能减少缺页次数。
但是FIFO算法在挑选要换出的页时候，并没有考虑到当前页是否经常被使用到，因此FIFO算法并不适合当前的场景。
MIN页面置换
min算法需要知道将来每个页的使用时间，将最晚使用到的页先换出，但是这也是该算法的致命缺陷，因为我们无法知道某个页将来什么时候会被使用到。
LRU页面置换
LRU算法高效的原因很大程度上也是因为利用了程序的局部性特点。
LRU的准确实现，用时间戳
每执行一条指令，都需要进行地址翻译，还要去修改上面这张表中的时间戳，并且还需要考虑溢出情况，这样的实现代价显然过于大了。
前面无论是多级页表还是TLB，都是为了尽可能减少访存次数，从而提高指令执行效率，因此这里换出算法的设计也必须要考虑到这一点。
LRU准确实现，用页码栈
每执行一条指令，需要额外访存多次，显然也不是我们想要的结果。
LRU近似实现 - 将时间计数变为是和否
- 一开始，所有物理页对应的引用位都为0，表示最近都没有被使用过
- 当程序访问了其中某个页的时候，会将其对应的引用位设置为1，表示最近使用了
- 而当需要进行换出页时，就将当前指针指向的引用位为1的页清零(下次如果还没被使用，就淘汰你)，然后如果遇到了引用位为0的页，就进行淘汰
Clock算法的分析与改造
由于程序的局部性原理，导致产生缺页现象会比较少。
缺页产生的比较少，就会导致大量页的引用位被设置为了1，这样当产生了缺页后，整个Clock 算法就退化了FIFO算法了，这显然不合适。
原始的Clock 算法其实是用最近没有使用的思想来近似最近最少使用，但是这样容易导致算法退化了FIFO。
为了体现最近最少使用的思想，就额外引入了一个定时清除R位的指针，定时清除指针会定时将当前指向页面的引用位设置为0，然后往后移动一格。
引入了定时清除指针之后，就可以将那些最近没有被使用到的页的引用位清零，这样就避免由于淘汰指针移动过慢，导致大量近期没有被使用到的页的引用位依旧为0，和近期被使用的页的引用位一样，那么当需要进行页淘汰时，就无法区分出哪一个页是最近最少使用的了，加入定时清除R位后，就符合最近最少使用的思想了，大家好好体会一下。
- 定时清除指针工作可以由某个时钟中断完成
- 淘汰指针工作放在缺页时完成
置换策略有了，还需要解决一个问题
如果给一个进程分配的实际物理页数过多，首先由于内存大小是有限的，分配太多，最大进程数就需要减少，并且请求调页的对内存的高效利用体现也就不明显了，甚至他额外带来的开销会更加影响系统运行。
如果给一个进程分配的页框过少，那么会导致进程在运行时缺页率升高，调页频繁，导致系统性能严重受损，毕竟读磁盘可是很慢的。
多进程确实可以提供CPU利用率，但是进程过多，也会导致每个进程分到页框数减小，随之而来的是缺页率飙升，从而大量时间浪费在了页的调度上面，导致CPU利用率急剧下滑。
程序执行都有其局部性，最好的页框分配数就是能够覆盖掉当前进程执行时的局部范围，当然程序的局部范围求解不易，可以利用相关求解工作集的算法进行求解。
相对而言简单一点的算法就是动态计算，首先给出一个基础页框数，然后随着进程的执行，如果缺页比较多了，就多分配几个，如果少了，就少分配几个，随着时间的推移，最终将达到一个稳定界限。
小结
- 用户发出指令 load addr ,解析发现线性地址addr对应的页缺失了，产生对应的页缺失中断
- 中断执行，从磁盘读取对应的页到内存对应的空闲页面中来，并建立好相关的映射 （换入）
- 如果此时内存中的没有空闲页了，那么就需要利用clock算法换出一个页到磁盘中去 (换出)
实现换入换出是为了支持虚拟内存，而实现虚拟内存是为了支持段页结合，实现段页是为了实现操作系统对内存的高效管理。
操作系统高效管理了内存，就可以让程序载入进内存后可以执行起来，程序执行起来后就成为了一个进程。
因此，操作系统本质是以进程带动的，多进程推进的，同时内存有效工作的一张图
