《操作系统段式存储管理与虚存》由会员分享，可在线阅读，更多相关《操作系统段式存储管理与虚存（46页珍藏版）》请在金锄头文库上搜索。
1、15.2.2 段式管理页式管理缺点：对用户而言不自然0 1 23 4 5 程序段数据段0 1 2主程序SIN0 1 2主程序SIN(共子程序)作业1作业22 整个作业的地址空间是二维的,如下图:Y:0500C:0200D:0300CallLoadstore01k分段MAIN (主程序)分段X (子程序)分段A (数据)分段B (工作区)段式管理的特点： 按作业的自然段将其逻辑空间分成若干段，作 业以段为单位分配内存。3一、空间安排 用户作业逻辑空间由若干自然段组成。 逻辑地址：段号与段内偏移，记做S，d。 编译及装配时把所有地址记成(S,d)的形式。 物理内存空间管理：与多道可变划分区法 一样
2、，系统以段为单位分配物理内存。主程序子程序1子程序2 栈数据4主程序子程序1子程序2栈数据逻辑空间子程序2主程序栈数据OS子程序1物理空间5二、动态地址转换保护码段长本段内存始地址 段表：由如下格式的段表项组成，作业 每段由一个段表项表示。 段表放于系统空间，进程PCB表中存有段 表始地址、段表长度。 段表始地址寄存器、段表长度寄存器。6段号保护码段长段内存始址 .保护码段长段内存始址 .Sd段表始址段表长度+PA越界地址转换过程 LA段表78三、共享主程序SIN数据主程序子程序1SIN子程序2SIN J1 J2 段表主存两个作业共享SIN段的示例9A段 SQRTSQRTB段SQRT J1 J
3、2 段表主存两个作业共享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+5
4、0)+5%(750+50+750+750）=875ns15段表主程序子程序数据作业1主程序子程序数据作业2 段表页表OS主存 SINSINSINSIN16总结：“放” 连续存放： 单道连续分配； 多道连续固定分区； 多道连续可变分区。 不连续存放： 页式存储； 段式存储； 段页式存储。175.3.1 虚存的基本思想 虚拟存储管理(虚存)：把作业的一部分装入内存便可 运行作业的存储器系统。它具有部分装入、请求调入 和置换功能，它把辅存和主存一起管理，能从逻辑上 对内存容量进行扩充。 影响虚存大小因素：有效地址长度，外存的容量，传 送速度，使用频率。5.3虚拟存储管理目的：提供用户进程一个巨大的虚
5、拟存储空间。手段：利用外存(磁盘)实现此虚空间。18实现该虚存管理的基本方法是：n 在页式（段式、段页式）管理的基础上 ，仅将进程的一部分页（段）放于主存。页 （段）表项中注明该页或段是否在主存。n 程序执行时，如果访问的页（段）不存 在主存，根据页（段）表项的指示，将其从 外存调入主存，如果此时无可用的内存空间 ，则先淘汰若干页帧或段。19交换区（SWAP）： 引入原因： 执行程序文件中的初始值不能被修改； 主要作用： 用于存放那些可读写的进程页面。 两种页类型： 回写swap文件页：对可读写的进程页面，初始 值从执行程序文件获得，一旦修改，写回时则写 到交换区，再度使用时，则从交换区中取出
6、； 零页：在执行文件中说明是初始值为0的工作区 ；回写时也要写到交换空间中。5.3.2 页式虚存管理20一、页表项结构:合法位 修改位 页类型 保护码 外存块号 页帧号合法位：表示该页在内存，为1或0。 修改位：表示该页被修改过，在释放或淘汰时应 写回外存。 页类型：零页时，表示该页在分配物理页帧时应清0页帧空间;回写swap区页，表示回写swap区；没设置类型时，正常方式处理 保护码：R,W,E保护说明。 外存块号：该页所在外存的块号。 页 帧 号：当在合法位置上时，代表该页所在内存的页帧号。21二、页表建立 分配pid给子进程，分配PCB空间; 初始化PCB（进程标识，调度信息）; 分配子
7、进程页表空间; 复制父进程的程序区页表项，使程序 共享;1.利用父进程页表生成进程页表(如UNIX的fork()初始化页表方法：在进程创建时建立页表，页表项在初始时， 合法位、修改位及页帧号都为0。22复制父进程的数据区和栈区，为数据区和 栈区分配swap空间，复制并修改数据区和 栈区页表项内容; 继承父进程对其他资源的访问现场; 父进程PCB中现场区初始化子进程的现场 区，且使子进程fork( )返回值为零; 将子进程挂到就绪队列; 返回子进程pid给父进程。23 为执行程序页面创建页表项，将保护码置为 可执行，辅存块号置为该页对应执行程序文 件的辅存块号。（不必回写）。 为所有初始数据页创
8、建页表项，保护码置为 可读写，页类型说明为回写swap页，辅存块 号为该页对应文件的辅存块号，待该页回写 时，再分配swap区空间，修改辅存块号栏。 为所有零数据页面创建页表项，保护码为可 读写，页类型说明为零页，辅存块号栏为空 。当第一次访问该页时，分配主存页帧并清 0；回写时，再分配swap区空间，填写辅存 块号栏。2.用一个可执行的文件来初始化页表。24三、硬件动态地址转换页表始址B 页表长度L3L?+页表寄存器越界中断逻辑地址 V（3，d）页帧号页号物理地址26480123是否（8，d）A0A2A1A30页框号1 2 3 4 5 6 7 8 9 偏移d快表否是读页号是否在是否在 内存内
9、存1110缺页异常 （页故障）页表合法位是否251.根据发生页故障的虚地址得到页表项。2.申请一个可用的页帧(根据所采用的替换策 略可能需要引起淘汰某一页);3.检查页类型:(1) 若为零页，则将页帧清0，将页帧号填 入页表项的页帧号一栏，置合法位为1。(2) 若非零页，则调用I/O子系统将辅存块号 所指的页面读到页帧中，将页帧号填入页表项 ，合法位置1，结束。四、缺页处理中断处理程序处理过程：26五、页淘汰淘汰一页的主要工作有：1.查P页表项的修改位，若未修改，则合法位 清0，将页帧送回空闲页帧队列。2.若已修改，则检查P的类型栏。3.若是零页或回写swap区页，则申请一块swap区 空间，
10、将P页表项的辅存块号置上并清除页类型。4.调用I/0子系统，将页帧上的数据写到辅存块号 所指的辅存空间中，对合法位清0，将页帧送回空 闲页帧队列。275.3.3 页面替换策略虚存的作用： 解决主存空间不足； 让更多的进程并发运行，提高系统的 吞吐率。页故障引发： Page Out/Page In； 访问辅存。28页面替换策略中的基本概念驻留集(工作集)：进程的合法页集合；访问串：进程访问虚空间的地址踪迹。举例：某进程依次访问如下地址，0100， 0432，0101，0612，0102，0103，页式虚存管理以页为基本单位，只需页号 即可。设页面大小为100，上述访问串可简 化为1，4，1，6，
11、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)
12、中时，且驻留集大小等于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, 277 07 0 12 0 12 0 12 3 12 3 04 3 04 2 04 2 30 2 30 2 30 2 3O O O O O O O O O O 出现了10次故障命中率1故障次数/访问串大小110/13=0.2332FIFO方法的特点： 实现方便。不需要额外硬件。
13、 效果不好，有Belady奇异。Belady奇异：指替换策略不满足随着 驻留集的增大，页故障数一定减少的 规律。33(二) OPT(Optimal replacement)举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. 77 07 0 12 0 12 0 12 0 32 0 32 4 32 4 32 4 32 0 32 0 32 0 3O O O O O O O淘汰下次访问距当前最远的那些页中序号 最小的页。34OPT方法特点： 最优的固定驻留集大小替换策略。 不可实现。OPT策略对任意一个访问串的控制均有最 小的时空积（进程所占空
14、间与时间的乘积） 。由于需要预先得知整个访问串的序，故 不能用于实践,仅作为一种标准，用以测量 其他可行策略的性能。35(三) LRU(Least Recently Used)淘汰上次使用距当前最远的页。举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. 77 07 0 12 0 12 0 12 0 32 0 34 0 34 0 24 3 20 3 20 3 20 3 2O O O O O O O O O36LRU策略是一种栈算法。满足：S（m,t）属于 S（m+1,t）的替换算 法被称为栈算法。LRU策略中，当驻留集大小为时,S(m,
15、t) 中保持着最近使用过的m个页帧；当驻留 集大小为m+1时，S(m+1,t)中保持着最近 使用过的m+1个页帧。故S(m,t)属于 S(m+1,t)的LRU策略是栈算法。37LRU策略的特点：要硬件配合，实现费用高 ，但效果适中。 实现方法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，操作 系统页面管理程序定时将所有使用
