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