存储管理补丁+部分练习.ppt

存储管理补丁 颠簸（抖动） 某进程由于缺页而产生置换，但在不久又需求刚换出的页面，需要再次置换，这种频繁的页调度行为称为颠簸 若一个进程在换页上使用的时间多于执行时间，称这个进程在颠簸 系统颠簸原因 采用全局置换算法可能导致系统颠簸 实例 早期调页系统中使用全局置换算法，OS发现CPU利用率降低，则向系统引入新进程以增加多道程序。 问题：某进程需要更多帧保证运行时，需要换页设备为其抢占他人空间，导致被抢占空间的进程需要等待换页设备 随着等待换页设备进程的增加，就绪队列逐渐缩短，CPU利用率随之降低，OS检测到该情况后会主动增加多道程序的程度，新进程的加入会需求新帧，进一步增加了等待换页设备的队列 上述过程的不断出现导致了系统颠簸的产生，系统吞吐量陡降，缺页率显著增加，有效访问时间增加，系统忙于调页而不能完成一样工作 系统颠簸（抖动） 多道程序的程度 CPU利用率 颠簸 系统颠簸（抖动） 颠簸预防 缺页率策略 颠簸具有较高的缺页率，缺页率较高表明系统需要更多帧，若缺页率太低，说明进程可能获得太多的帧 为所期待的缺页率设置上下限，若超过上限，为该进程分配更多帧；反之从该进程移走帧 此方法可以检测和控制缺页率以防止颠簸，但在缺页增加且没有可用帧时必须选择一个进程终止，再将其释放的帧分配给那些具有高缺页率的进程 工作集理论 定义 最近n次内存访问的页面集合，数字n被称为工作集窗口，也就是工作集的大小 经常被使用的页面会在工作集中，而若一个页面不再被使用，将会被从工作集中丢弃。当一个进程寻址一个不在工作集内的页面时，会产生一个缺页中断。在处理缺页中断时，更新工作集并在需要时从磁盘中读入此页面 工作集理论 工作集模型的原理 让操作系统监视各个进程的工作集，主要是监视各个工作集的大小。若有空闲的物理块，则可以再调一个进程到内存以增加多道度；若工作集的大小总和增加超过了所有可用物理块的数量总和，那么OS可以选择一个内存中的进程对换到磁盘中去，以减少内存中的进程数量来防止抖动的发生。 正确选择工作集窗口大小，对存储器的有效利用率和系统吞吐量的提高都将产生重要影响。一方面，如果窗口选的很大，进程虽不易产生缺页，但存储器也得不到充分利用；另一方面，如果窗口过小，则会使进程在运行过程中频繁产生缺页中断，反而降低了系统吞吐量。 页面置换算法 在一个请求分页存储管理系统中，一个作业的页面访问序列为4、3 、2 、1 、4 、3 、 5 、 4 、 3 、 2 、 1 、 5，当分配给该作业的物理帧分别为3、4时，试计算下述页面置换算法的缺页率（设开始时主存中无页面，初始装入视为缺页），并比较结果。 最佳置换算法OPT FIFO置换算法 LRU置换算法 页面置换算法 顺序 块 1 块 2 块 3 缺页 4 4 Y 3 4 3 Y 2 4 3 2 Y 1 4 3 1 Y 4 3 5 4 3 5 Y 4 3 2 2 3 5 Y 1 2 1 5 Y 5 3个物理帧时，使用OPT算法的缺页率为7/12 页面置换算法 4个物理帧时，使用OPT算法的缺页率为6/12 结论：增加分配给作业的物理帧数可以降低缺页率 顺序 块 1 块 2 块 3 块 4 缺页 4 4 Y 3 4 3 Y 2 4 3 2 Y 1 4 3 2 1 Y 4 3 5 4 3 2 5 Y 4 3 2 1 1 3 2 5 Y 5 页面置换算法 顺序 块 1 块 2 块 3 缺页 4 4 Y 3 4 3 Y 2 4 3 2 Y 1 1 3 2 Y 4 1 4 2 Y 3 1 4 3 Y 5 5 4 3 Y 4 3 2 5 2 3 Y 1 5 2 1 Y 5 3个物理帧时，使用FIFO算法的缺页率为9/12 页面置换算法 4个物理帧时，使用FIFO算法的缺页率为10/12 结论：增加分配给作业的物理帧数反而使缺页率上升，这种异常现象称为Belady现象 顺序 块 1 块 2 块 3 块 4 缺页 4 4 Y 3 4 3 Y 2 4 3 2 Y 1 4 3 2 1 Y 4 3 5 5 3 2 1 Y 4 5 4 2 1 Y 3 5 4 3 1 Y 2 5 4 3 2 Y 1 1 4 3 2 Y 5 1 5 3 2 Y 页面置换算法 顺序 块 1 块 2 块 3 缺页 4 4 Y 3 4 3 Y 2 4 3 2 Y 1 1 3 2 Y 4 1 4 2 Y 3 1 4 3 Y 5 5 4 3 Y 4 3 2 2 4 3 Y 1 2 1 3 Y 5 2 1 5 Y 3个物理帧时，使用LRU算法的缺页率为10/12 页面置换算法 4个物理帧时，使用LRU算法的缺页率为8/12 结论：增加分配给作业的物理帧数可以降低缺页率 顺序 块 1 块 2 块 3 块 4 缺页 4 4 Y 3 4 3 Y 2 4 3