《计算机操作系统》汤小丹报告.ppt

6.4 “抖动”与工作集 请求分页系统是目前最常用的一种存储管理方式。但程序在运行中所产生的缺页情况，会影响程序的运行速度即系统性能；而缺页率的高低又将直接与每个进程所占用的物理块数目有关。为此，应分析缺页率对系统性能的影响，以及应为每个进程所分配的物理块数目，使得缺页率保持在一个合理的水平上。 缺页率对有效访问时间的影响 有效访问时间可表示为： 有效访问时间=(1-p)×ma+p×td=ma+(td-ma)P p:出现缺页的概率; ma:存储器访问时间,一般在10ns到数百ns之间; td :缺页中断时间，主要由缺页中断服务,缺页读入和进程重新执行三部分时间构成. 设:ma=10ns; td =25ms 假设希望在缺页时,有效访问时间延长不超过10%,则有0.1+24999.9p0.11 即: p0.0000004 这说明,要求在250万次访问中,才发生1页缺页,即应保持非常低的缺页率,否则程序的执行速度将受到严重影响. 工作集（1） 缺页率，或者缺页的时间间隔与进程分得的物理块数目密切相关（如图所示）。 之所以会形成图示曲线的原因，是由于缺页率的大小与进程运行时的工作集有关。工作集理论由Denning提出并推广。他认为程序在运行时对页面的访问是不均匀的，若能预知程序在某段时间间隔内要访问哪些页面，并将他们提前调入内存，就会大大降低缺页率。 缺页率 上限 下限 物理块数n 所谓工作集是指在某段时间间隔⊿内，进程实际要访问的页面的集合。虽然程序只需少量的几页在内存就可运行，但为使程序能有效运行，较少地产生缺页，就必须使程序的工作集全部在内存。由于无法预知程序在不同时刻将访问哪些页面，故只能利用程序过去某段时间内的行为，作为程序将来某段时间内的行为的近似 设某进程在时间t的工作集为w(t,⊿)，⊿称为工作集窗口尺寸。w(t,⊿)是二元函数，与时间t和窗口尺寸有关，工作集w是工作集窗口⊿的非降函数，即w(t,⊿) ? w(t,⊿+1)。 正确选择工作集窗口的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。 引用页序列 窗口大小：3 窗口大小：4 窗口大小：5 24 24 24 24 15 15，24 15，24 15，24 18 18，15，24 18，15，24 18，15，24 23 23，18，15 23，18，15，24 23，18，15，24 24 24，23，18 —— —— 17 17，24，23 17，24，23，18 17，24，23，18，15 18 18，17，24 —— —— 24 —— —— —— 18 —— —— —— 17 —— —— —— 15 15，17，18 15，17，18，24 —— 24 —— —— —— * 产生抖动的原因和预防方法 一、产生抖动的原因 在系统中，运行进 程的大部分时间都用 于进行页面的换入换 出，而几乎不能完成 任何有效的工作。称 这时的进程是处于抖 动状态。 CPU利用率 多道程序度 二、抖动的预防：目前预防抖动的方法有多种，这些方法的共同点都是通过调节多道程序度来实现的。 1、采用局部置换策略：某进程发现缺页后，仅在自己的内存空间范围内置换页面，不允许从其他进程获得新的物理块。 2、在CPU调度程序中引入工作集算法：仅当每个进程在内存中都有足够大的驻留集时，方能再从外存上调入新的作业。 3、L=S准则：产生缺页的平均时间L等于系统处理进程缺页的平均时间。此时的CPU利用得最好。 4、挂起若干进程：以便腾出内存空间来分配给抖动的进程。 6.5 请求分段存储管理方式 在分页系统基础上建立的虚拟存储器，是以页面为单位进行换入换出的。在分段的基础上实现的虚拟存储器，则是以分段为单位进行换入换出的。在请求分段系统中，程序运行之前只需调入若干个分段，便可启动运行。当所访问的段不在内存时可请求OS将所缺的段调入内存。 * 1 请求分段中的硬件支持 一、段表机制：段表是请求分段式管理中所需的主要的数据结构，为适应程序在运行过程中，对段的调进调出，需在段表的原有结构上增加若干项。段表项的结构如下： 段名 段长 段的 基址 存取 方式 访问 字段A 修改 字段M 存在 位p 增补位 外存 起址 用于标识本分段的存取属性是只执行、只读、还是允许读写 用于记录本段被访问的频繁程度 用于表示本段进入内存后是否被修改过。 指示本段是否已调入内存 用于表示本段在运行过程中，是否进行过动态增长 指示本段在外存的起始地址，即起始盘块号。 二、缺段中断机构：在请求分段系统中，采用的是请求调段策略。即每当进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理