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

1,5.2.2 段式管理,页式管理缺点：对用户而言不自然,0,1,2,主程序,SIN(共子程序),作业1,作业2,2,整个作业的地址空间是二维的,如下图:,分段MAIN (主程序),分段X (子程序),分段A (数据),分段B (工作区),段式管理的特点：,按作业的自然段将其逻辑空间分成若干段，作业以段为单位分配内存。,3,一、空间安排,用户作业逻辑空间由若干自然段组成。 逻辑地址：段号与段内偏移，记做S，d。编译及装配时把所有地址记成(S,d)的形式。 物理内存空间管理：与多道可变划分区法一样，系统以段为单位分配物理内存。,4,主程序,子程序1,子程序2,栈,数据,逻辑空间,子程序2,主程序,栈,数据,OS,子程序1,物理空间,5,二、动态地址转换,保护码,段长,本段内存始地址,段表：由如下格式的段表项组成，作业每段由一个段表项表示。,段表放于系统空间，进程PCB表中存有段表始地址、段表长度。 段表始地址寄存器、段表长度寄存器。,6,段号,保护码,段长,段内存始址,.,.,.,.,保护码,段长,段内存始址,.,.,.,S,d,段表始址,段表长度,+,+,PA,越界,地址转换过程,LA,段表,7,8,三、共享,9,A段,SQRT,SQRT,B段,SQRT,J1 J2,段表 主存,两个作业共享SQRT段的示例,A段,B段,逻辑段空间,（1）SQRT（A，Y） （2）IF X0 THEN GOTO L （3） （4） （5）L：”报告出错” （6） ,注意：若共享的段引用自身的某个地址，则各进程必须用同一段号来共享这一段。,J1,J2,10,1、分配单位不同： 页是信息的物理单位，为实现离散存储，提高内存利用率而引入； 段是信息的逻辑单位，为满足用户要求而引入。 2、大小不同： 页的大小固定且由系统确定； 段长不定，取决于用户程序，并在编译时划分。 3、维数不同： 分页的作业地址空间是一维的； 分段的作业地址空间是二维的。,四 页式管理和段式管理的比较,11,对于用户而言，段页式管理与段式相同，用户逻辑地址只涉及段号与段内位移。 对于物理内存管理而言，它与页式系统相同。 系统内的逻辑地址：段号 段内位移 段号页号页内位移。记做：S,P,d。,5.2.3 段页式管理,特点：将作业分成若干段，每段用页式管理实现内存分配。,一、空间安排,12,作业空间的内部表示,主程序 子程序 数据,保护码 长度 页表始地,OS,段表,页表,主存,作业,段表+页表,13,二、动态地址转换,段号,页号,保护码,页帧号,.,.,.,.,S,p,d,段表始址,段表长度,+,越界,+,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,实现该虚存管理的基本方法是： 在页式（段式、段页式）管理的基础上，仅将进程的一部分页（段）放于主存。页（段）表项中注明该页或段是否在主存。 程序执行时，如果访问的页（段）不存在主存，根据页（段）表项的指示，将其从外存调入主存，如果此时无可用的内存空间，则先淘汰若干页帧或段。,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,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,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,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 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1,41,实现： 每一页面设一计数器。每访存一次，将所有计数器加1，所访存的页面计数器清0，淘汰计数器值等于的页面。,特点： 开销太大，不实用。,42,每访问一页，将当前硬时钟值记录在页表项中，操作系统定时(以T为周期)检查驻留集页表项的时钟值，若:当前时钟值-页表项中时钟值，则淘汰之。,(二) SWS(Sampled Warking Set),定时检查计数器，淘汰计数器值大于等于的页面。这样硬件消耗仍很大。,43,费用小，但效果不好。D为两次页故障距离，1/D为当前页故障率，f为阈值。 1/Df，则淘汰驻留集中使用位为0的页。 1/Df，增加驻留集大小，加入故障页， 所有驻留集中页的使用位清0。,(三) VMIN(Variable Minimal replacement),若某页距下次访问的距离大于，则将其淘汰(不能实用)；与相同时，VMIN与WS的故障数相同，但VMIN的平均驻留集要小。,(四) PFF(Page Fault Frequency),44,实用OS选择动态驻留集FIFO(SWS)的变种 设立两个队列：自由链表和修改链表。 定时作页淘汰：淘汰时不立即