操作系统课件os04存储管理.ppt

操作系统 Operating Systems WINDOWSWINDOWS UNIXUNIX LINUXLINUX OS2OS2 VxWorksVxWorks Mac OSMac OS 4.7 请求分页存储管理方式 4.7.1 请求分页中的硬件支持 1页表机制 状态位P：用于指示该页是否已调入内存。 供程序访问时参考。 访问字段A：供选择换出页面时参考。 用于记录本页在一段时间内被访问的次数，或记录本 页最近已有多长时间未被访问。 4.7 请求分页存储管理方式 4.7.1 请求分页中的硬件支持 1页表机制 修改位M：供置换页面时参考。 表示该页在调入内存后是否被修改过。 外存地址 用于指出该页在外存上的地址，通常是物理块号 供调入该页时参考。 2缺页中断机构 在请求分页系统中，每当所要访问的页面不在内存时，便 产生一缺页中断，请求OS将所缺之页调入内存。 缺页中断同样需要经历： 1. 保护CPU环境 2. 分析中断原因 3. 转入缺页中断处理程序进行处理 4. 恢复CPU环境 多次缺页中断的指令 如：在执行一条指令 COPY A TO B时，可能要产 生6次缺页中断： l指令本身跨了两个页面 lA和B又分别各是一个数 据块，也都跨了两个页 面。 缺页中断 缺页中断与一般的中断区别： (1)缺页中断是在指令执行期间产生和处理中断信号。 一般中断都是在CPU一条指令执行完后，才检查是否有 中断请求到达。 (2) 一指令在执行期间，可产生多次缺页中断。 系统中硬件机构应能保存多次中断时的状态，并保证 最后返回到中断前产生缺页中断的指令处继续执行。 3地址变换机构 4.7.2 内存分配策略和分配算法 1最小物理块数 是指能保证进程正常运行所需的最小物理块数。 2物理块的分配策略 3物理块分配算法 最小物理块数 当系统为进程分配的物理块数少于此值时，进程将无法运 行。 进程应获得的最少物理块数与计算机的硬件结构有关，取 决于指令的格式、功能和寻址方式。 对于某些功能较强的机器，其指令长度可能是两个或 多于两个字节。 对于这种机器，至少要为每个进程分配6个物理块，以 装入6个页面。 物理块的分配策略 内存分配策略： 固定分配 可变分配 置换策略 全局置换 局部置换 固定分配局部置换 可变分配全局置换 可变分配局部置换 3物理块分配算法 1) 平均分配算法 将系统中所有可供分配的物理块平均分配给各个进程 2) 按比例分配算法 根据进程的大小按比例分配物理块的算法。 3) 考虑优先权的分配算法 把内存中可供分配的所有物理块分成两部分： 一部分按比例地分配给各进程； 另一部分则根据各进程的优先权，适当地增加其相应 份额后，分配给各进程。 4.7.3 调页策略 1) 预调页策略 可采用一种以预测为基础的预调页策略 将那些预计在不久之后便会被访问的页面预先调入内存 主要用于进程的首次调入时，由程序员指出应该先调 入哪些页。 2) 请求调页策略 若发现其所在的页面不在内存，便立即提出请求，由OS将 其所需页面调入内存。 在目前的虚拟存储器中大多采用此策略。 4.8 页面置换算法 1) 最佳页面替换算法OPT 通常可保证获得最低的缺页率。 该算法是无法实现的 2) 先进先出页面替换算法FIFO 3) 最近最久未使用置换算法LRU 4) 时钟页面替换算法 缺页率(缺页中断率) 如果作业p在运行中成功的访问次数为s， 不成功的访问 次数为F，则总的访问次数为：A = s + F 缺页中断率：f = F / A 。 最佳替换算法OPT 所淘汰的页应该是： 以后不再访问的页 或在最长（未来）时间内不再访问的页。 发生了5次页面置换，缺页次数=8；缺页率=8/17 7 0 1 7 722 2 2 0 00 4 0 333 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 11 2 0 0 1 先进先出页面替换算法 基于程序总是按线性顺序来访问物理空间这一假设。 淘汰最先调入主存的页，或在主存中驻留时间最长的页。 只需把一个进程已调入内存的页面，按先后次序链接成一个 队列，并设置一个指针，它总是指向最老的页面 7 0 2 2 47701 2 3 0 0 12 3042 3 0 32 4 0 3 7 0 1 2 0 3 0 4 2 3 0 3 2 1 11 3 0 发生了8次页面置换，缺页次数=11；缺页率=11/14 最 老 的 页 最近最久未使用页面替换算法LRU 该算法的主要出发点是： 用“最近的过去”作为“最近的将来”的近似 如果某页被访问了，则它可能马上还要被访问。 当需要淘汰某一页时，选择离当前时间最近的一段时间内最 久没有使用过的页先淘汰。 或者反过来说，如果某页很长时间未被访问，则它在最近一 段时间也不会被访问。 2硬件支持 须有寄存器或栈的支持： 1) 寄存器 须为每个在内存中的页面配置一个移位寄存器： 进程访问某物理块时，先将寄存器的Rn1位设成1。 定时信号将每隔一定时间将寄存器右移一位。 若将n位寄存器的数看做是一整数，那么，具有最小数值 的寄存器所对应的页面，就是最近最久未使用的页面。 R7R6R5R4R3R2R1R0 000000000 100000000 1 LRU算法实现：栈 最 新 被 访 问 的 页 例子-计算缺页中断次数和被淘汰页面(1) 假设采用固定分配策略，进程分得三个页框,执行中按下列次 序引用5个独立的页面: 2 3 2 1 5 2 4 5 3 2 5 2。 2 3 2 1 5 2 4 5 3 2 5 2 2 3 4 51 2222 33 33 55 3 3 2 4 23 222152 5 2 5 3 3 215 2453 2 5 3 54 2 5 1 OPT LRU 发生了3次页面置换，缺页次数=6；缺页率=6/12 发生了4次页面置换，缺页次数=7；缺页率=7/12 最 新 被 访 问 的 页 例子-计算缺页中断次数和被淘汰页面(2) 2 3 2 1 5 2 4 5 3 2 5 2 2 2 3 5 51 2 231 4 32 315 24 3 5 5 34 2 FIFO 发生了6次页面置换，缺页次数=9；缺页率=9/12 最 老 的 页 时钟页面替换算法 1、简单的Clock置换算法 简单的Clock置换算法（1） 1. 主存中的任何页面被访问时， 其 “访问位”置1。 2. 淘汰页面时， 从指针当前指向的页面开始 扫描循环队列，把所遇到的 “访问位”是1的页面的“访问 位”清0，跳过这个页面; 把所遇到的“访问位”是0的 页面淘汰掉，指针推进一步 。 Page9 use=1 Page19 Use=1Page1 Use=0 Page45 Use=1 Page191 Use=1 Page556 Use=0 Page13 Use=0 Page67 Use=1 Page33 Use=1 Page222 Use=0 查寻指 针 n-1 0 1 2 3 4 5 6 7 8 Page45 Use=0 Page191 Use=0 简单的Clock置换算法（2） 4. 扫描循环队列时，如果 遇到的所有页面的“访问 位”为1，指针就会绕整 个循环队列一圈，把碰 到的所有页面的“访问位 ”清0; 指针停在起始位置，并 淘汰掉这一页， 然后，指针推进一步。 Page1 Use=0 Page45 Use=1 Page191 Use=1 Page556 Use=0 查寻指 针 n-1 0 1 2 3 4 Page45 Use=0 Page191 Use=0 Page556 Use=1 Page1 Use=1 例子-计算缺页中断次数和被淘汰页面(1) 假设采用固定分配策略，进程分得三个页框,执行中按下列次 序引用5个独立的页面: 2 3 2 1 5 2 4 5 3 2 5 2。 2* 3* 5* 11* 2* 2*5* 5*3*3* 3*32* 2*2 2 5* 44* 1 CLOCK *号表示相应的访问位等于1 2 3 2 1 5 2 4 5 3 2 5 2 发生了5次页面置换，缺页次数=8；缺页率=8/12 3* 2* 4 3* 2* 5* 4.9 请求分段存储管理方式 与基本分段的最大区别： 允许部分段运行前不装入 可以在运行过程中按需动态调入。 硬件支持 1. 段表机制 2. 缺段中断机构 3. 地址变换机构 1. 段表机制 (1) 存取方式：标识本段存取属性(读,执行,读/写)。 (2) 访问字段A：用于记录该段被访问的频繁程度。 (3) 修改位M：供置换页面时参考。 (4) 存在位P：供程序访问时参考。 (5) 增补位：用于表示本段在运行过程中是否做过动态增长 。 (6) 外存始址：指示本段在外存中起始盘块号。 段名 段长 段的 基址 存取 方式 访问 字段A 修改 位M 存在 位P 增补 位 外存 始址 2缺段中断机构 3地址变换机构 小结（1） 内存管理概念 程序装入与链接；逻辑地址与物理地址空间； 交换 连续分配管理方式 单一连续分配、固定分区分配、动态分区分配 伙伴系统、可重定位分配分配 非连续分配管理方式 分页管理方式；分段管理方式；段页式管理方式。 小结（2） 虚拟内存管理 虚拟内存基本概念 请求分页管理方式 页面分配策略 页面置换算法 OPT；FIFO；LRU；CLOCK。 请求分段管理方式 作业 1.在一个分页虚存系统中，用户编程空间32个页面，页长 1KB，主存为16KB。如果用户程序有10页长