设为首页 | 加入收藏夹

八文网 - 汇聚八方文档 - 做最优秀的免费文档下载网站

操作系统

文档类型：

Microsoft PowerPoint PPT 演示文稿文档大小：216KB

操作系统, Fall 2002
2.1 进程概念
第三章存储管理(四)
3.7 虚拟存储(Virtual Memory)提出和相关概念硬件支持软件支持OS的虚拟存储管理软件取决与硬件是否支持页式,段式或段页式纯段式系统越来越少,段通常被分页=》虚拟存储管理的问题主要就是虚拟页式存储管理的问题
虚拟存储管理软件的目标:使缺页率(Page Fault Rate)最小缺页率缺页次数内存访问次数或缺页的平均时间间隔
缺页率与页面大小的关系:
页面很小:每个进程的内存页较多,通过调页很快适应局部性原理的要求,缺页率低
页面很大:进程使用的大部分地址空间都在内存,缺页率低
页面中等大小:局部性区域只占每页的较小部分,缺页率高缺页率(续)
缺页率与分配给进程的内存页面数目的关系:数目越多,缺页率越低页面数目的下限应该是一条指令及其操作数可能涉及的页面数目的上限应该是足以保证每条指令都能被执行虚拟存储管理软件的各个方面调页策略(Fetch Policy)分配策略(Placement Policy)置换策略(Replacement Policy)
常驻集和工作集管理(Resident Set and Working Set Management)清除策略(Cleaning Policy)负载控制(Load Control)调页策略决定何时将页面载入内存
两种常用策略:
请求调页(demand paging):只通过响应缺页中断调入需要的页面,也只调入发生缺页时所需的页面进程开始运行时会有许多缺页,对外存IO次数多,开销较大(一次IO操作包括旋转等待时间和读写时间)
预先调页(prepaging):在发生缺页需要调入某页时,一次调入该页以及相邻的几个页提高调页的IO效率
效率不能保证:额外装入的页面可能没用分配策略决定进程各部分驻留在内存的哪个位置对纯段式系统重要(涉及外碎片,紧缩操作等)最佳适配、首先适配.对纯页式或段页式系统不成问题放哪地址转换,内存存取等都一样工作置换策略需要调入页面而内存已满时,决定置换(淘汰)内存中的哪个页面常要进行置换(为提高并发程度,OS总是载入尽量多的进程)
不是所有内存中的页面都可以被置换:
有些帧给锁定(locked)了:OS内核、关键控制结构,IO缓冲区等
常驻集策略决定了不同的置换范围:被置换的页面局限在本进程,或允许在其他进程基本置换算法最优算法(OPT)最久未使用算法( LRU)先进先出算法(FIFO)
第二次机会算法(Second Chance)时钟算法(Clock)最近未使用算法( NRU)最优算法(OPT, optimal)淘汰未来不再使用或还要最长时间才会使用的那个页面最佳,但不可能实现(实际执行中无法预知)可用作其他算法的性能评价依据最久未使用算法( LRU, Least Recently Used)淘汰内存中最久未使用的页面性能接近最佳算法(局部性原理的合理近似)
例:一个进程有5个页面,OS规定每个进程最多占有3个帧最久未使用算法(LRU)需要记录页面使用时间的先后关系,实现开销太大
链表:每次内存访问后在链表中找到对应的页面,把它移到表头,因此表尾的就是最久未使用的
硬件计数器:每执行一条指令计数器就加1;每次内存访问后将当前计数器的值写到相应的页表表项里、计数器值最小的就是最久未使用的
硬件矩阵:n×n矩阵(设有n个帧)初始值都是0,每访问页k,就先把k行的位都设为1,然后把k列的位都设为0.二进制值最小的行就是最久未使用的先进先出算法( FIFO, First-In First-Out)淘汰内存中最老(建立最早)的页面实现简单可通过链表来表示各页的建立时间先后,新来的到表尾,表头就是最老的性能较差较早调入的页往往是经常被访问的页,这些页在FIFO算法下被反复调入和调出有Belady现象_FIFO算法与Belady现象Belady现象采用FIFO算法时,如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多,缺页率反而提高的异常现象.
Belady现象的描述一个进程P要访问M个页,OS分配N个内存页面给进程P;对一个访问序列S,发生缺页次数为PE(S,N).当N增大时,PE(S, N)时而增大,时而减小.
例:P80图3-28Belady现象的原因FIFO算法的置换特征与进程访问内存的动态特征是矛盾的,即被置换的页面并不是进程不会访问的.
FIFO算法与LRU算法比较
例:LRU能识别出2和5是最常用的页面,而FIFO不行FIFO性能要差淘汰不但老而(最近)没用的页面
原理:用链表来表示各页的建立时间先后,新来的到表尾,表头就是最老的(同FIFO)
选择淘汰页面时,若表头页面的R位(访问位)是0,则淘汰之,否则将其R位设为0,并把它放到表尾,然后继续从表头搜索(页面装入时设R=1)环形链表实现的第二次机会算法环形链表头尾相邻,因此只需要移动一个指针性能近似LRU,实现开销小
例:调入页面727前后Clock与LRU,FIFO比较号表示R=1,箭头表示指针Clock通过设置R位保护了常用的页面最近未使用算法( NRU, Not Recently Used)不但考虑R位、还考虑M位、淘汰由RM组成的二进制数的值最小的一个页面
R=0:表示最近可能不会用到(局部性原理)
M=0:表示调出时不用写回到外存
基于Clock的算法过程:从指针位置开始扫描链表,扫描过程中不改变R位.淘汰遇到的第一个R=0M=0的页面.
若第1步失败,则再次扫描,淘汰遇到的第一个R=0M=1的页面.每个页面检查过后将R设为0.
若第2步失败,重复1和2(如果需要).谢谢!

ppt文档的标签：操作系统

更多推荐标签：金属力学性能助理实习报告威海市运输协议财政学第四版土方投标书中间业务开展第九天堂特殊工种学习矿山转让协议专案投资报告香港政府招标异能少年经济预测方法经贸科技关于环境保护反对语言暴力周李恒课题项目申报室内装饰调研购房诚意金学校考核细则态鹊纬转洹八八网挑战杯答辩学院评语范文行政管理费敏豪生奇游记选取投资论文学习商贸俄语