当前位置:2019年全年资料内部公开 > 缺页中断 >

操作系统C 第4章 存储管理5专用课件ppt

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  回 顾 基本分页分段存储管理方式如何实现地址映射? 基本分页分段存储管理方式有哪些特征? 什么是局部性原理? 什么是虚拟存储器,虚拟存储器有哪些特征? 4.7 请求分页式存储管理方式 基本的分页和分段系统具有:一次性和驻留性不支持虚拟存储器功能,根据局部性原理程序的一次性和驻流性是不必要的,为了实现虚拟存储器功能而采用请求分页和请求分段系统实现 请求分页式存储管理是建立在基本分页系统基础上的,为了支持虚拟存储器功能而增加了请求调页和页面置换功能。 4.7.1 请求分页中的硬件支持 1 页表机制 物理块号 状态位P 访问字段A 修改位M 外存地址 状态位P:用于指示该页是否已经调入了内存 ,供访问 时参考。 访问字段A:用于记录本页在一定时间内被访问的次数,或最近已经有多长时间未被访问。供页面置换时参考。 修改位M:表示该页调入内存后是否被修改过。置换时参考 外存地址:该页在外存上的物理地址,调入时参考 2 缺页中断机构 所要访问的页面不在内存时,便产生一缺页中断,请求OS将该页调入内存。 与一般中断的相同之处: 保存CPU环境; 分析中断原因; 转入缺页中断处理程序; 恢复CPU环境。 与一般中断不同之处: 指令执行期间产生和处理中断 一条指令在执行期间可能产生多次中断,如下图 3 地址变换机构 请求分页中的地址变换机构 4.7.2 内存分配策略和分配算法 在请求分页存储管理方式中,为进程分配内存时,涉及到三个问题: 最小物理块数的确定 物理块的分配策略 物理块的分配算法 1 最小物理块号的确定 指能保证进程正常运行所需要的最小物理块数 2 物理块的分配策略 可采用两种内存分配策略:固定分配和可变分配策略。 置换时也可以采用两种策略:全局置换和局部置换。 于是可以组合成以下三种策略 (1)固定分配局部置换 为每个进程分配一定数目的物理块数,运行期间所占内存空间不变。当发现缺页时置换该进程中的一个物理块。 缺点:难于确定应该为每个进程分配多少物理块 (2)可变分配全局置换 为系统中的每个进程分配一定数目的物理块,OS系统本身保持一个空闲物理块队列,进程缺页时即分配空闲物理块队列中的一个装入。当空闲队列用完时,OS在从内存中选择一页调出。 (3)可变分配局部置换 首先为每个进程分配一定数目的物理块,当缺页时,将该进程的一页换出,如果某进程频繁的发生缺页中断,则再给该进程分配一定的物理块,直到缺页率降低到某一个适当的值。相反,如果进程运行期间缺页率特别低,则适当较少其物理块数。 3 物理块分配算法 平均分配算法:将可用的物理块平均分配给哥哥进程。 按比例分配算法:根据进程的大小按比例分配物理块。 考虑优先权的分配算法:将可供分配的物理块分成两部分,一部分按比例分配给进程,另一部分根据优先权,适当的增加其相应的份额。 4.7.3 调页策略 1 何时调入页面 预调页策略:将那些预计在不久的将来会被访问的页面预先调入内存。若干连续区域,一同调入 请求调页策略:当进程在运行过程中,需要访问某部分程序和数据时,发现不在内存,便立即提出请求,由操作系统将页面调入。 4.8 页面置换算法 把选择换出页面的算法称为页面置换算法。 一个好的页面置换算法,应该具有较低的页面置换频率。 从理论上来说,应该将那些以后不会再使用的或者长时间不用的页面替换。 4.8.1 最佳置换算法和先进先出置换算法 1 最佳置换算法 将以后永不使用或最长时间内不再被访问的页面调出。 2 先进先出页面置换算法 举例说明最佳置换算法和先进先出页面置换算法 假定系统为某进程分配了三个物理块,并考虑有以下的页号引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 进程运行时,先将7,0,1三个页面装入,以后使用的页面将根据不同的置换算法进行 4.8.2 最近最久未使用(LRU)置换算法 1 LRU置换算法描述: 根据页面调入内存后的使用情况进行决策,由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似。 赋予每个页面一个访问字段,用来记录一个页面上次被访问以来所经历的时间t. 2 LRU置换算法的硬件支持 移位寄存器: 为每个页面配置一个移位寄存器R=Rn-1Rn-2…R0 当进程访问某物理块时,将Rn-1位置1 每隔一定时间(如100ms)将寄存器右移一位 2) 栈: 利用栈保存当前使用的各个页面的页号。 每当进程访问某页时,将该页号从栈中取出,压入栈顶。 栈顶始终最新被访问的页面,栈底是最久未使用的页面。 4.8.3 Clock置换算法 1 简单Clock置换算法 每页置一个访问位,内存中各页面链接成一个循环队列; 一个页面首次装入内存时,其访问位为0; 任何一页被访问时,其访问位置1; 淘汰页面时,从替换指针所在当前位置开始检查访问位,如果为0,则替换;如果为1,则改访问位为0,暂时不换,将替换指针指向下一个访问位; 若找到访问位为0的表项,则替换该页,若没有则从头开始查找。 2 改进型Clock置换算法 除了需要考虑页面的使用情况外,还要考虑页面是否被修改过(置换代价) 把同时满足这两个条件的页面最为首选淘汰的页面。 1类(A=0,M=0)未访问,未修改;第1类页面 2类(A=0,M=1)未访问,已修改;第2类页面 3类(A=1,M=0)已访问,未修改;第3类页面 4类(A=1,M=1)已访问,已修改;第4类页面 改进型Clock置换算法的执行过程 第一步:从指针指示的当前位置开始,扫描队列,寻找A=0, M=0的第1类页面; 第二步:若没有找到第1类页面,则开始第二轮查找,寻找A=0, M=1的第2类页面。同时将扫描过的页面的访问位A都置0; 第三步:若没有找到第2类页面。则重复上面第一步,找第1类页面; 第四步:若仍失败,则再找第2类页面,此时肯定会找到。 思考题 在一个请求分页系统中,假如系统分配给一个作业的物理块数为4,并且此作业的页面走向为: 4,3,2,1,4,3,5,4,3,2,1,5 试用FIFO和LRU两种算法分别计算出程序访问 过程中所发生的缺页次数? 总结与回顾 请求分页存储管理方式的地址转换过程? 4.9 请求分段存储管理方式 4.9.1 请求分段中的硬件支持 1 段表机制 段名 段长 段的基址 存取方式 访问字段A 修改位M 存在位P 增补位 外存地址 存取方式:本段是只读、执行、读写等。 存在位:本段是否在内存。 增补位:本段在执行过程中是否做过动态增长。 4.9.2 分段的共享与保护 1 共享段表 段号,段长,内存地址,存在位,外存地址 共享进程记数Count: 存取控制字段:不同的进程有不同的存取权限 段号:不同的进程以不同的段号去访问 2 共享段的分配和回收 1)共享段的分配 2)共享段的回收 3 分段保护 1)越界检查 2)存取控制检查 3)环保护机制 本 章 总 结 存储管理方式? 如何实现各种存储管理方式的地址映射 习 题 1 整体对换从逻辑上扩充了内存,因此也实现了虚拟存储器的功能? 习 题 2 对于一个页表存放在内存中的分页系统: (1)如果访问内存需要0.2us,有效访问时间是什么? (2) 如果加一个块表 ,且假定在块表中找到页表项的几率高达90%,则有效访问时间又是多少(快表访问时间不计) 习 题 3 什么是动态链接,何种内存分配方式可以实现这种链接技术? 习 题 4 在一采取局部置换策略的请求分页系统中,分配给某个作业的内存块数为4,其中存放的四个页面的情况如表所示。表中数据为十进制,进程运行时从0开始计时。请问如果系统采取下列置换算法,将选择哪一页进行置换。FIFO、LRU和改进的Clock算法 习 题 5 某页式虚拟存储管理系统中,页面大小为1KB,一进程分配到的块数为3,并按下列地址顺序引用内存单元:3635,3632,1140,3584,2892,3640,0040,2148,1700,2145,3209,0000,1102,1100,上述为十进制,内存未装入任何页。 (1)给出使用LRU算法时的缺页次数,并与FIFO算法比较 (2)使用流程图的方式解释地址变换的过程 习 题 6 假如一个程序的段表如下,其中存在位为1表示段在内存,存取控制字段W表示可写,R表示只读,E表示可执行。对下面的指令,在执行时会产生什么样的结果? STORE R1,[0,70] STORE R1,[1,20] LOAD R1[3,20] LOAD R1[3,100] JMP [2,100] 习 题 7 现有一请求调页系统,页表保存在寄存器中。若一个被替换的页未被修改,则处理一个页面中断需要8ms;若页面被修改过,则处理一个页面中断需要20ms,内存的存取时间为1us,访问页表的时间可以忽略不计,假定70%被替换的页面被修改过,为保证有效的存取时间不超过2us,可接收的最大缺页率是多少? 实验 页面置换算法模拟 一.?目的要求: 1、通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法 2、通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 二. 实验内容: 编写一个请求分页存储管理中的页面置换算法模拟程序 例题1: 在某个请求页式管理系统,用户编程空间有40个页面,每个页面200H个字节,假定某时刻用户页表中虚页号和物理块号对照表如下: 求虚地址0A3CH,223CH对应的物理地址。 36 14 8 20 5 物理块号 20 17 5 2 0 虚页号 例题2: 在某个采用页式存储管理的系统中,现有J1,J2和J3共三个作业,其中J2有4个页面,被分别装入到主存的第3、4、6、8块中。假定页面和存储块的大小均为1024B,主存容量为10KB。 (1)写出J2的页面映像表。 (2)当J2在CPU上运行时,执行到其地址空间(逻辑地址)第500号时遇到一条传送指令(地址用十进制表示): MOV 2100, 3100 请你用地址变换图计算出MOV指令中两个操作数的物理地址。 2 缺段中断机构 3 地址变换机构 1 1 163 20 3 3 0 0 158 26 0 2 0 1 161 160 1 1 1 0 157 60 2 0 修改位 访问位 最后访问时间 装入时间 虚页号 物理块 R 40 5000 0 4 R 80 8000 1 3 E 200 3000 1 2 R 30 1000 1 1 W 100 500 0 0 其他 存取控制 段长 内存始址 存在位 段号 * 最近最久未使用置换算法(LRU)是一种较好的算法,但要求较多的硬件支持,在实际应用中多采用LRU的近似算法Clock置换算法。 *

http://boardflip.com/queyezhongduan/215.html
点击次数:??更新时间2019-06-07??【打印此页】??【关闭
  • Copyright © 2002-2017 DEDECMS. 织梦科技 版权所有  
  • 点击这里给我发消息
在线交流 
客服咨询
【我们的专业】
【效果的保证】
【百度百科】
【因为有我】
【所以精彩】