操作系统段式存储管理与虚存.ppt

1 5.2.2 段式管理 页式管理缺点：对用户而言不自然 0 1 2 3 4 5 程序段数据段 0 1 2 主程序 SIN 0 1 2 主程序 SIN(共子程序) 作业1作业2 2 整个作业的地址空间是二维的,如下图: Y: 0 500 C: 0 200 D: 0 300 Call Load store 0 1k 分段MAIN (主程序) 分段X (子程序) 分段A (数据) 分段B (工作区) 段式管理的特点： 按作业的自然段将其逻辑空间分成若干段，作 业以段为单位分配内存。 3 一、空间安排 用户作业逻辑空间由若干自然段组成。 逻辑地址：段号与段内偏移，记做S，d。 编译及装配时把所有地址记成(S,d)的形式。 物理内存空间管理：与多道可变划分区法 一样，系统以段为单位分配物理内存。 主程序 子程序1 子程序2 栈 数据 4 主程序 子程序1 子程序2 栈 数据 逻辑空间 子程序2 主程序 栈 数据 OS 子程序1 物理空间 5 二、动态地址转换 保护码段长本段内存始地址 段表：由如下格式的段表项组成，作业 每段由一个段表项表示。 段表放于系统空间，进程PCB表中存有段 表始地址、段表长度。 段表始地址寄存器、段表长度寄存器。 6 段号保护码段长段内存始址 保护码段长段内存始址 . Sd 段表始址 段表长度 + + PA 越界 地址转换过程 LA 段表 7 8 三、共享 主程序 SIN 数据 主程序 子程序1 SIN 子程序2 SIN J1 J2 段表 主存 两个作业共享SIN段的示例 9 A段 SQRT SQRT B段 SQRT J1 J2 段表 主存 两个作业共享SQRT段的示例 A段B段 逻 辑 段 空 间 （1）SQRT（A，Y） （2）IF X 段号页号页内位移。记做：S,P,d。 5.2.3 段页式管理 特点：将作业分成若干段，每段用页式管理实 现内存分配。 一、空间安排 12 作业空间的内部表示 主程序 子程序 数据 保护码 长度 页表始地 OS 段表 页表 主存 作业 段表+页表 13 二、动态地址转换 段号 页号 保护码页帧号 Spd 段表始址 段表长度 + 越界 + f f d 段表 页表 14 三、保护与共享 保护与段式管理相同。共享则可以以页为 单位，也可以共享页表。 等效访问时间：设访存时间为750ns，搜索 快表的时间为50ns，命中率为95%，则 95%(750+50)+5%(750+50+750+750） =875ns 15 段表 主程序 子程序 数据 作业1 主程序 子程序 数据 作业2 段表 页表 OS 主存 SIN SIN SIN SIN 16 总结：“放” 连续存放： 单道连续分配； 多道连续固定分区； 多道连续可变分区。 不连续存放： 页式存储； 段式存储； 段页式存储。 17 5.3.1 虚存的基本思想 虚拟存储管理(虚存)：把作业的一部分装入内存便可 运行作业的存储器系统。它具有部分装入、请求调入 和置换功能，它把辅存和主存一起管理，能从逻辑上 对内存容量进行扩充。 影响虚存大小因素：有效地址长度，外存的容量，传 送速度，使用频率。 5.3虚拟存储管理 目的：提供用户进程一个巨大的虚拟存储空间。 手段：利用外存(磁盘)实现此虚空间。 18 实现该虚存管理的基本方法是： n 在页式（段式、段页式）管理的基础上 ，仅将进程的一部分页（段）放于主存。页 （段）表项中注明该页或段是否在主存。 n 程序执行时，如果访问的页（段）不存 在主存，根据页（段）表项的指示，将其从 外存调入主存，如果此时无可用的内存空间 ，则先淘汰若干页帧或段。 19 交换区（SWAP）： 引入原因： 执行程序文件中的初始值不能被修改； 主要作用： 用于存放那些可读写的进程页面。 两种页类型： 回写swap文件页：对可读写的进程页面，初始 值从执行程序文件获得，一旦修改，写回时则写 到交换区，再度使用时，则从交换区中取出； 零页：在执行文件中说明是初始值为0的工作区 ；回写时也要写到交换空间中。 5.3.2 页式虚存管理 20 一、页表项结构: 合法位 修改位 页类型 保护码 外存块号 页帧号 合法位：表示该页在内存，为1或0。 修改位：表示该页被修改过，在释放或淘汰时应 写回外存。 页类型：零页时，表示该页在分配物理页帧时应 清0页帧空间;回写swap区页，表示回 写swap区；没设置类型时，正常方式处理 保护码：R,W,E保护说明。 外存块号：该页所在外存的块号。 页 帧 号：当在合法位置上时，代表该页所在内 存的页帧号。 21 二、页表建立 分配pid给子进程，分配PCB空间; 初始化PCB（进程标识，调度信息）; 分配子进程页表空间; 复制父进程的程序区页表项，使程序 共享; 1.利用父进程页表生成进程页表(如UNIX的fork() 初始化页表方法： 在进程创建时建立页表，页表项在初始时， 合法位、修改位及页帧号都为0。 22 复制父进程的数据区和栈区，为数据区和 栈区分配swap空间，复制并修改数据区和 栈区页表项内容; 继承父进程对其他资源的访问现场; 父进程PCB中现场区初始化子进程的现场 区，且使子进程fork( )返回值为零; 将子进程挂到就绪队列; 返回子进程pid给父进程。 23 为执行程序页面创建页表项，将保护码置为 可执行，辅存块号置为该页对应执行程序文 件的辅存块号。（不必回写）。 为所有初始数据页创建页表项，保护码置为 可读写，页类型说明为回写swap页，辅存块 号为该页对应文件的辅存块号，待该页回写 时，再分配swap区空间，修改辅存块号栏。 为所有零数据页面创建页表项，保护码为可 读写，页类型说明为零页，辅存块号栏为空 。当第一次访问该页时，分配主存页帧并清 0；回写时，再分配swap区空间，填写辅存 块号栏。 2.用一个可执行的文件来初始化页表。 24 三、硬件动态地址转换 页表始址B 页表长度L 3L? + 页表寄存器 越界中断 逻辑地址 V（3，d） 页帧号页号 物理地址 2 6 4 8 0 1 2 3 是 否 （8，d） A0 A2 A1 A3 0 页框号 1 2 3 4 5 6 7 8 9 偏移d 快表 否 是 读页号 是否在是否在 内存内存 1 1 1 0 缺页异常 （页故障） 页表 合法位 是 否 25 1.根据发生页故障的虚地址得到页表项。 2.申请一个可用的页帧(根据所采用的替换策 略可能需要引起淘汰某一页); 3.检查页类型: (1) 若为零页，则将页帧清0，将页帧号填 入页表项的页帧号一栏，置合法位为1。 (2) 若非零页，则调用I/O子系统将辅存块号 所指的页面读到页帧中，将页帧号填入页表项 ，合法位置1，结束。 四、缺页处理 中断处理程序处理过程： 26 五、页淘汰 淘汰一页的主要工作有： 1.查P页表项的修改位，若未修改，则合法位 清0，将页帧送回空闲页帧队列。 2.若已修改，则检查P的类型栏。 3.若是零页或回写swap区页，则申请一块swap区 空间，将P页表项的辅存块号置上并清除页类型。 4.调用I/0子系统，将页帧上的数据写到辅存块号 所指的辅存空间中，对合法位清0，将页帧送回空 闲页帧队列。 27 5.3.3 页面替换策略 虚存的作用： 解决主存空间不足； 让更多的进程并发运行，提高系统的 吞吐率。 页故障引发： Page Out/Page In； 访问辅存。 28 页面替换策略中的基本概念 驻留集(工作集)：进程的合法页集合； 访问串：进程访问虚空间的地址踪迹。 举例：某进程依次访问如下地址，0100， 0432，0101，0612，0102，0103， 页式虚存管理以页为基本单位，只需页号 即可。设页面大小为100，上述访问串可简 化为1，4，1，6，1，1， 29 页面替换策略分成两类： 驻留集大小固定的替换策略； 驻留集大小可变的替换策略。 设驻留集大小为m，s(t)为t时刻的驻留集 ，r(t)为t时刻访问的页号。t取0,1,t， 指访存指令执行时刻。 30 驻留集与paging in/out的关系： 进程刚创建时，驻留集为空。即s(t)=空。 若t+1时刻访问的页在s(t)中时，则访问之。 即若r(t+1)s(t)，则s(t+1)=s(t)。 若t+1时刻访问的页不在s(t)中时，且驻留 集大小小于m，则paging in。即若 r(t+1)!s(t)，且|s(t)|m，则 s(t+1)=s(t)+r(t+1)。 若t+1时刻访问的页不在s(t)中时，且驻留 集大小等于m，则先paging out y页，再 paging in r(t+1)页。 即s(t+1)=s(t)-y+r(t+1)。 一、驻留集大小固定的替换策略 31 (一) FIFO替换算法(替换最早进入的页) 举例：驻留集大小为3，访问串为： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 77 0 7 0 1 2 0 1 2 0 1 2 3 1 2 3 0 4 3 0 4 2 0 4 2 3 0 2 3 0 2 3 0 2 3 O O O O O O O O O O 出现了10次故障 命中率1故障次数/访问串大小110/13=0.23 32 FIFO方法的特点： 实现方便。不需要额外硬件。 效果不好，有Belady奇异。 Belady奇异：指替换策略不满足随着 驻留集的增大，页故障数一定减少的 规律。 33 (二) OPT(Optimal replacement) 举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 77 0 7 0 1 2 0 1 2 0 1 2 0 3 2 0 3 2 4 3 2 4 3 2 4 3 2 0 3 2 0 3 2 0 3 O O O O O O O 淘汰下次访问距当前最远的那些页中序号 最小的页。 34 OPT方法特点： 最优的固定驻留集大小替换策略。 不可实现。 OPT策略对任意一个访问串的控制均有最 小的时空积（进程所占空间与时间的乘积） 。 由于需要预先得知整个访问串的序，故 不能用于实践,仅作为一种标准，用以测量 其他可行策略的性能。 35 (三) LRU(Least Recently Used) 淘汰上次使用距当前最远的页。 举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 77 0 7 0 1 2 0 1 2 0 1 2 0 3 2 0 3 4 0 3 4 0 2 4 3 2 0 3 2 0 3 2 0 3 2 O O O O O O O O O 36 LRU策略是一种栈算法。 满足：S（m,t）属于 S（m+1,t）的替换算 法被称为栈算法。 LRU策略中，当驻留集大小为时,S(m,t) 中保持着最近使用过的m个页帧；当驻留 集大小为m+1时，S(m+1,t)中保持着最近 使用过的m+1个页帧。故S(m,t)属于 S(m+1,t)的LRU策略是栈算法。 37 LRU策略的特点：要硬件配合，实现费用高 ，但效果适中。 实现方法1：给每个页帧设一个计数器，每 访问一页，对应页帧计数清0，其余页帧计 数加1，淘汰计数最大的页帧。 实现方法2：用类似栈的结构来管理和实现 LRU。 栈算法没有Belady奇异。 设nm，对于栈算法有S(m,t)属于 S(n,t)，任取r(t)，若r(t)!S(n,t),则 r(t)!S(m,t)。因此，驻留集为n 时出现 的页故障一定会出现在驻留集为m 时。 LRU没有Belady奇异。 38 (四) 实用方法（兼顾FIFO和LRU策略） 为页帧在页表项中增加一位使用位，硬件每 访存一次，即将对应页的使用位置1，操作 系统页面管理程序定时将所有使用位清0。 淘汰时任选一个使用位为0的页。 操作系统选择淘汰页时，尽量避免选被 修改过的页。因此，首先选择使用和修改位 都为0的页；若没有，再选修改位为1，使用 位为0的页；再选使用位为1，修改位为0的 页；最后按FIFO选两者均为1的页。 39 程序行态：指程序访存布局特性和行为特性。 局部性行态:一段时间内程序访存有局部性. 阶段转换行态:从一个局部集向另一个局部 集过渡是突然的. 局部集一般不超过程序总页数的20%。 二、驻留集可变的替换策略 引入原因：若驻留集小于局部集时引起抖动 ，而驻留集大于局部集又是浪费。同时局部 集又有大有小。 因此，应随着程序访问虚存的局部集大小变 化而改变驻留集。 40 若驻留集中的某页有个访问间隔没 被访问，则将其淘汰。 举例：取=5，访问串为 (一) WS(working set) 1 2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 3 7 0 7 0 1 7 0 1 2 7 0 1 2 7 0 1 2 3 0 1 2 3 0 4 2 3 0 4 2 3 0 4 2 3 0 4 2 3 0 4 2 3 0 2 3 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 0 2 1 3 0 2 1 3 0 2 1 3 2 1 0 41 实现： 每一页面设一计数器。每访存一次 ，将所有计数器加1，所访存的页面计数 器清0，淘汰计数器值等于的页面。 特点： 开销太大，不实用。 42 每访问一页，将当前硬时钟值记录在 页表项中，操作系统定时(以T为周期)检 查驻留集页表项的时钟值，若:当前时钟 值-页表项中时钟值，则淘汰之。 (二) SWS(Sampled Warking Set) 定