进程运行过程中，访问的页面不在内存，调入时内存已无空闲空间，需要将内存中的一页程序或数据调到外存。
页面置换算法(page replacement algorithms)：选择换出哪些页面的算法，其好坏直接影响系统的性能。
应具有较低的缺页率：
页面调入次数（缺页次数）/总的页面使用次数
系统抖动：
为了提高处理机利用率，可增加多道程序并发度；
但进程数目增加过多，每个进程分配得到的物理块太少，在某个临界点上，会出现刚被淘汰的页很快又需重新调入；而调入不久又被淘汰出去；出现频繁缺页
大部分处理器时间都用在来回的页面调度上，这种局面称为系统抖动或颠簸（thrashing)
抖动的后果：
缺页率急剧增加
内存有效存取时间加长，
系统吞吐量骤减；系统已基本不能完成什么任务，而是忙于页面对换操作，cpu虽然忙，但效率急剧下降。
根本原因：
页面淘汰算法不合理；分配给进程的物理页面数(驻留集)太少。
Belady现象：出现分配的页面数增多，缺页率反而提高的异常现象。
描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。
Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征矛盾，即被置换的页面并不是进程不会访问的。
最佳（Optimal）置换算法
换出以后永不再用的，或在最长(未来)时间内不再被访问的页面。
先进先出置换算法（FIFO）
先进入的先淘汰，即选择内存中驻留时间最久的页面予以淘汰
最近最久未使用(LRU)置换算法
无法预测将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法选择最近最久未使用（least recently used）的页面予以淘汰
网友评论