页面置换算法
为什么要页面置换
-
缺页中断：
在地址映射过程中，若在页表中发现所要访问的页面不在内存，则产生中断，当发生中断时，系统必须在内存选择一个页面移出内存，以便为调入新的页面让出空间。 -
缺页率的计算：
假设一个进程的逻辑空间为n页，系统为其分配的物理块数为m，如果在进程运行的过程当中，访问页面成功（即所访问的页面在内存中）的次数为S，访问页面失败（即所访问的页面不在内存中）的次数为F，则该进程的页面确实率 f=F/(F+A) -
页面置换算法是选择换出页面的算法，直接影响系统的性能
最佳置换算法
- 最佳置换算法是一种理想化的算法，无法实现，一般作为评价标准。
- 思想：开挂上帝视角，无敌死神之眼，直接判断哪个页面在接下来最长时间将不再被访问，将其替换，此页面相比其他页面再次出现需要的时间长，否则如果换别的，之后频繁出现则要频繁置换
- 举例：假设某进程被分配了三个物理块，并考虑一下页面号引用串 7、0、2、1、0、3、0、4、2、3、0、3
注： “由于数据是自己写的，可能存在不妥，请指正”
先进先出页面置换算法
- 先进先出算法是最早出现的置换算法
- 思想：总是置换最先进入内存的页面，即选择在内存中驻留时间最长的页面置换。就是来的越早越早爬。
- 举例 ：假设某进程被分配了三个物理块，并考虑一下页面号引用串 7、0、1、2、0、3、0、4
- 缺点：在进程当中，有些页面需要经常访问，比如全局变量、常用函数、例程等页面，FIFO算法不能保证这些页面不被淘汰。总之就是很菜，毕竟最老的一批，和它思想一样，把最老的淘汰了。
LRU置换算法
-
硬件支持：需要寄存器
-
思想：上帝视角大削版本，LRU即 Least Recently Used，最近最久未使用，就是说，在需要置换的时候，我们看之前，哪个页面最长时间没有被使用过就将它换出，最佳置换算法是和未来比较，而LRU是比较之前，上帝视角瞬间掉价，但是瘦死的骆驼比马大，还行。
-
举例：假设某进程被分配了三个物理块，并考虑一下页面号引用串 2、3、2、1、5、2、4、5、3、2、5、2（这次换了数据，和上面不一样了，别问，问就是有现成的不用我sb）
这里的写法和前面不一样（至少和书上不一样），因为栈的运用，习惯了，这么写，每次出栈就是置换出的页（出栈底），只是需要注意顺序，每次来新的页面相当于进栈同时出栈，如果页面已经存在还被访问，则重新进栈，但是不需要出栈。还有，这里没有画框框，因为写太丑了。我的问题。
-
还有个LFU算法，最少使用算法。
和LRU算法访问图是一样的，访问时间等方面的区别，建议百度
Clock置换算法
- LRU之前说了需要硬件支持，所以成本比较高，接下来是Clock算法。
舍友要睡了，简单置换算法和改进算法明天写