操作系统段式存储管理与虚存.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,J1J2,段表主存,两个作业共享SQRT段的示例,A段,B段,逻辑段空间,（1）SQRT（A，Y）（2）IFX段号页号页内位移。记做：S,P,d。,5.2.3段页式管理,特点：将作业分成若干段，每段用页式管理实现内存分配。,一、空间安排,12,作业空间的内部表示,主程序子程序数据,保护码长度页表始地,OS,段表,页表,主存,作业,段表+页表,13,二、动态地址转换,段号,页号,保护码,页帧号,.,.,.,.,S,p,d,段表始址,段表长度,+,越界,+,f,fd,段表,页表,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页面替换策略,虚存的作用：解决主存空间不足；让更多的进程并发运行，提高系统的吞吐率。,页故障引发：PageOut/PageIn；访问辅存。,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,驻留集与pagingin/out的关系：进程刚创建时，驻留集为空。即s(t)=空。若t+1时刻访问的页在s(t)中时，则访问之。即若r(t+1)s(t)，则s(t+1)=s(t)。若t+1时刻访问的页不在s(t)中时，且驻留集大小小于m，则pagingin。即若r(t+1)!s(t)，且|s(t)|m，则s(t+1)=s(t)+r(t+1)。若t+1时刻访问的页不在s(t)中时，且驻留集大小等于m，则先pagingouty页，再paginginr(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,OOOOOOOOOO,出现了10次故障,命中率1故障次数/访问串大小110/13=0.23,32,FIFO方法的特点：实现方便。不需要额外硬件。效果不好，有Belady奇异。,Belady奇异：指替换策略不满足随着驻留集的增大，页故障数一定减少的规律。,33,(二)OPT(Optimalreplacement),举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2.,OOOOOOO,淘汰下次访问距当前最远的那些页中序号最小的页。,34,OPT方法特点：最优的固定驻留集大小替换策略。不可实现。,OPT策略对任意一个访问串的控制均有最小的时空积（进程所占空间与时间的乘积）。由于需要预先得知整个访问串的序，故不能用于实践,仅作为一种标准，用以测量其他可行策略的性能。,35,(三)LRU(LeastRecentlyUsed),淘汰上次使用距当前最远的页。,举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2.,OOOOOOOOO,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(workingset),12344444444434443,70120304230321201,41,实现：每一页面设一计数器。每访存一次，将所有计数器加1，所访存的页面计数器清0，淘汰计数器值等于的页面。,特点：开销太大，不实用。,42,每访问一页，将当前硬时钟值记录在页表项中，操作系统定时(以T为周期)检查驻留集页表项的时钟值，若:当前时钟值-页表项中时钟值，则淘汰之。,(二)SWS(SampledWarkingSet),定时检查计数器，淘汰计数器值大于等于的页面。这样硬件消耗仍很大。,43,费用小，但效果不好。D为两次页故障距离，1/D为当前页故障率，f为阈值。1/Df，则淘汰驻留集中使用位为0的页。1/Df，增加驻留集大小，加入故障页，所有驻留集中页的使用位清0。,(三)VMIN(VariableMinimalreplacement),若某页距下次访问的距离大于，则将其淘汰(不能实用)；与相同时，VMIN与WS的故障数相同，但VMIN的平均驻留集要小。,(四)PFF(PageFaultFrequency),44,实用OS选择动态驻留集FIFO(SWS)的变种设立两个队列：自由链表和修改链表。定时作页淘汰：淘汰时不立即删除页中数据，要根据页面是否修改挂入自由链/修改链，修改链过长时，回写页面后改挂到自由链中。pagingin要用空页时,选自由链的第一页帧，这时页中数据被覆盖,改变该页帧原页面页表项状态等信息。在自由链/修改链中的页面再次被访问时，则将该页从链中摘除,该页又能通过页表项访问到。,三、替换策略选择,45,预调请调与预调的区别：存储管理：用时分配调入与预分配调入；替换策略：要时页淘汰与预淘汰。,固定驻留集大小时，一般驻留集未满时，采用预调；待驻留集满即改为请调。,46,作业：P1315.7，5.13，5.18(，FIFO)补课通知14周星期三5,6节，地点：公共教学楼108,