操作系统段式存储管理与虚存课件

1、操作系统段式存储管理与虚存课件15.2.2 5.2.2 页式管理缺点：页式管理缺点：对用户而言不自然对用户而言不自然 0 1 2 3 4 5 数据段数据段 0 1 2主程序主程序SIN 0 1 2主程序主程序SIN( (共子程序共子程序) )作业作业1 1作业作业2 2操作系统段式存储管理与虚存课件2 整个作业的地址空间是二维的整个作业的地址空间是二维的, ,如下图如下图: :Y:Y:0 0500500C:C:0 0200200D:D:0 0300300CallCallLoadLoadstorestore0 01k1k分段分段MAINMAIN( (主程序主程序) )分段分段X X( (子程序子

2、程序) )分段分段A A( (数据数据) )分段分段B B( (工作区工作区) )段式管理的特点：段式管理的特点： 按作业的自然段将其逻辑空间分成若干段，按作业的自然段将其逻辑空间分成若干段，作业以段为单位分配内存。作业以段为单位分配内存。操作系统段式存储管理与虚存课件3 一、空间安排 用户作业逻辑空间由若干自然段组成。用户作业逻辑空间由若干自然段组成。 逻辑地址：段号与段内偏移，记做逻辑地址：段号与段内偏移，记做S S，d d。编。编译及装配时把所有地址记成译及装配时把所有地址记成(S,d)(S,d)的形式。的形式。 物理内存空间管理：与多道可变划分区法一物理内存空间管理：与多道可变划分区法

3、一样，系统以段为单位分配物理内存。样，系统以段为单位分配物理内存。主程序主程序子程序子程序1子程序子程序2栈栈数据数据操作系统段式存储管理与虚存课件4 主程序 子程序1 子程序2栈数据逻辑空间逻辑空间 子程序2主程序栈数据OS 子程序1物理空间物理空间操作系统段式存储管理与虚存课件5二、动态地址转换保护码段长本段内存始地址 段表：由如下格式的段表项组成，作业由如下格式的段表项组成，作业每段由一个段表项表示。每段由一个段表项表示。 段表放于系统空间，进程段表放于系统空间，进程PCBPCB表中存有段表中存有段表始地址、段表长度。表始地址、段表长度。 段表始地址寄存器、段表长度寄存器。段表始地址寄存

4、器、段表长度寄存器。操作系统段式存储管理与虚存课件6段号段号 保护码保护码段长段长段内存始址段内存始址.保护码保护码段长段长段内存始址段内存始址.Sd段表始址段表始址段表长度段表长度+PA越界越界地址转换过程地址转换过程LALA段表段表操作系统段式存储管理与虚存课件7操作系统段式存储管理与虚存课件8 三、共享主程序主程序SIN数据数据主程序主程序子程序子程序1SIN子程序子程序2SIN J1 J2段表段表主存主存两个作业共享两个作业共享SINSIN段的示例段的示例操作系统段式存储管理与虚存课件9 A段段SQRTSQRT B段段SQRT J1 J2段表段表主存主存两个作业共享两个作业共享SQRT

5、SQRT段的示例段的示例A A段段B B段段逻逻辑辑段段空空间间（1）SQRT（A，Y）（2）IF X - 段号段号页号页号页内位移。记做：页内位移。记做：S,P,dS,P,d。5.2.3 5.2.3 段页式管理段页式管理特点：将作业分成若干段，每段用页式管理实将作业分成若干段，每段用页式管理实现内存分配现内存分配。一、空间安排操作系统段式存储管理与虚存课件12作业空间的内部表示 主程序 子程序 数据保护码 长度 页表始地OS段表段表页表页表主存作业段表段表+ +页表页表操作系统段式存储管理与虚存课件13二、动态地址转换段号段号 页号页号 保护码保护码页帧号页帧号.Spd段表始址段表始址段表长

6、度段表长度+越界越界+ f f d段表段表页表页表操作系统段式存储管理与虚存课件14三、保护与共享保护与段式管理相同。共享则可以以保护与段式管理相同。共享则可以以页页为为单位，也可以共享页表。单位，也可以共享页表。等效访问时间：等效访问时间：设访存时间为设访存时间为750ns750ns，搜索，搜索快表的时间为快表的时间为50ns50ns，命中率为，命中率为95%95%，则，则95%95%(750+50)+5%(750+50)+5%(750+50+750+750(750+50+750+750）=875ns=875ns操作系统段式存储管理与虚存课件15段表段表主程序子程序数据作业1主程序子程序数据

7、作业2段表段表页表页表OS主存SINSINSINSINSINSINSINSIN操作系统段式存储管理与虚存课件16总结：总结：“放放” 连续存放：连续存放： 单道连续分配；单道连续分配； 多道连续固定分区；多道连续固定分区； 多道连续可变分区。多道连续可变分区。 不连续存放：不连续存放： 页式存储；页式存储； 段式存储；段式存储； 段页式存储。段页式存储。操作系统段式存储管理与虚存课件175.3.1 5.3.1 虚存的基本思想虚存的基本思想虚拟存储管理虚拟存储管理( (虚存虚存) )：把作业的一部分装入内存便可把作业的一部分装入内存便可运行作业的存储器系统。它具有部分装入、请求调入运行作业的存储

8、器系统。它具有部分装入、请求调入和置换功能，它把辅存和主存一起管理，能从逻辑上和置换功能，它把辅存和主存一起管理，能从逻辑上对内存容量进行扩充。对内存容量进行扩充。 影响虚存大小因素：有效地址长度，外存的容量，影响虚存大小因素：有效地址长度，外存的容量，传送速度，使用频率。传送速度，使用频率。5.35.3虚拟存储管理虚拟存储管理目的：目的：提供用户进程一个巨大的虚拟存储空间。提供用户进程一个巨大的虚拟存储空间。手段：手段：利用外存利用外存( (磁盘磁盘) )实现此虚空间。实现此虚空间。操作系统段式存储管理与虚存课件18实现该虚存管理的基本方法是：n 在页式（段式、段页式）管理的基础上，在页式（

9、段式、段页式）管理的基础上，仅将进程的一部分页（段）放于主存。页仅将进程的一部分页（段）放于主存。页（段）表项中注明该页或段是否在主存。（段）表项中注明该页或段是否在主存。n 程序执行时，如果访问的页（段）不存在程序执行时，如果访问的页（段）不存在主存，根据页（段）表项的指示，将其从主存，根据页（段）表项的指示，将其从外存调入主存，如果此时无可用的内存空外存调入主存，如果此时无可用的内存空间，则先淘汰若干页帧或段。间，则先淘汰若干页帧或段。操作系统段式存储管理与虚存课件19交换区（交换区（SWAPSWAP）：）： 引入原因：引入原因：执行程序文件中的初始值不能被修改；执行程序文件中的初始值不能

10、被修改； 主要作用：主要作用：用于存放那些可读写的进程页面。用于存放那些可读写的进程页面。两种页类型：两种页类型： 回写回写swapswap文件页：文件页：对可读写的进程页面，初始对可读写的进程页面，初始值从执行程序文件获得，一旦修改，写回时则写值从执行程序文件获得，一旦修改，写回时则写到交换区，再度使用时，则从交换区中取出；到交换区，再度使用时，则从交换区中取出； 零页：零页：在执行文件中说明是初始值为在执行文件中说明是初始值为0 0的工作区；的工作区；回写时也要写到交换空间中。回写时也要写到交换空间中。5.3.2 5.3.2 页式虚存管理页式虚存管理操作系统段式存储管理与虚存课件20一、页

11、表项结构:合法位合法位 修改位修改位 页类型页类型 保护码保护码 外存块号外存块号 页帧号页帧号合法位：合法位：表示该页在内存，为表示该页在内存，为1 1或或0 0。修改位：修改位：表示该页被修改过，在释放或淘汰时应表示该页被修改过，在释放或淘汰时应 写回外存。写回外存。页类型：页类型：零页时，表示该页在分配物理页帧时应零页时，表示该页在分配物理页帧时应 清清0 0页帧空间页帧空间; ;回写回写swapswap区页，表示回区页，表示回 写写swapswap区；没设置类型时，正常方式处理区；没设置类型时，正常方式处理保护码：保护码：R,W,ER,W,E保护说明。保护说明。外存块号：外存块号：该页

12、所在外存的块号。该页所在外存的块号。页页 帧帧 号：号：当在合法位置上时，代表该页所在内当在合法位置上时，代表该页所在内 存的页帧号。存的页帧号。操作系统段式存储管理与虚存课件21二、页表建立 分配分配pidpid给子进程，分配给子进程，分配PCBPCB空间空间; ; 初始化初始化PCBPCB（进程标识，调度信息）（进程标识，调度信息）; ; 分配子进程页表空间分配子进程页表空间; ; 复制父进程的程序区页表项，使程序复制父进程的程序区页表项，使程序共享共享; ;1.利用父进程页表生成进程页表(如UNIX的fork()初始化页表方法：在进程创建时建立页表，页表项在初始时，在进程创建时建立页表，

13、页表项在初始时，合法位、修改位及页帧号都为合法位、修改位及页帧号都为0 0。操作系统段式存储管理与虚存课件22 复制父进程的数据区和栈区，为数据区复制父进程的数据区和栈区，为数据区和栈区分配和栈区分配swapswap空间，复制并修改数据空间，复制并修改数据区和栈区页表项内容区和栈区页表项内容; ; 继承父进程对其他资源的访问现场继承父进程对其他资源的访问现场; ; 父进程父进程PCBPCB中现场区初始化子进程的现场中现场区初始化子进程的现场区，且使子进程区，且使子进程fork( )fork( )返回值为零返回值为零; ; 将子进程挂到就绪队列将子进程挂到就绪队列; ; 返回子进程返回子进程pi

14、dpid给父进程。给父进程。操作系统段式存储管理与虚存课件23为执行程序页面创建页表项，将保护码置为为执行程序页面创建页表项，将保护码置为可执行，辅存块号置为该页对应执行程序文可执行，辅存块号置为该页对应执行程序文件的辅存块号。（不必回写）。件的辅存块号。（不必回写）。为所有初始数据页创建页表项，保护码置为为所有初始数据页创建页表项，保护码置为可读写，页类型说明为回写可读写，页类型说明为回写swapswap页，辅存块页，辅存块号为该页对应文件的辅存块号，待该页回写号为该页对应文件的辅存块号，待该页回写时，再分配时，再分配swapswap区空间，修改辅存块号栏。区空间，修改辅存块号栏。为所有零数

15、据页面创建页表项，保护码为可为所有零数据页面创建页表项，保护码为可读写，页类型说明为零页，辅存块号栏为空。读写，页类型说明为零页，辅存块号栏为空。当第一次访问该页时，分配主存页帧并清当第一次访问该页时，分配主存页帧并清0 0；回写时，再分配回写时，再分配swapswap区空间，填写辅存块号区空间，填写辅存块号栏。栏。2.用一个可执行的文件来初始化页表。操作系统段式存储管理与虚存课件24三、硬件动态地址转换三、硬件动态地址转换页表始址页表始址B 页表长度页表长度L3L?3L?+ +页表寄存器页表寄存器越界中断越界中断逻辑地址逻辑地址V（3，d）页帧号页帧号页号页号物理地址物理地址26480123

16、是是否否（8，d）A0A2A1A30页框号页框号123456789偏移偏移d快表快表否否是是读页号读页号1110缺页异常缺页异常（页故障）（页故障）页表页表合法位合法位是是否否操作系统段式存储管理与虚存课件25 1. 1.根据发生页故障的虚地址得到页表项。根据发生页故障的虚地址得到页表项。 2.2.申请一个可用的页帧申请一个可用的页帧( (根据所采用的替换策根据所采用的替换策略可能需要引起淘汰某一页略可能需要引起淘汰某一页);); 3. 3.检查页类型检查页类型: : (1) (1) 若为零页，则将页帧清若为零页，则将页帧清0 0，将页帧号填，将页帧号填 入页表项的页帧号一栏，置合法位为入页表

17、项的页帧号一栏，置合法位为1 1。 (2)(2) 若非零页，则调用若非零页，则调用I/OI/O子系统将辅存块号子系统将辅存块号所指的页面读到页帧中，将页帧号填入页表项，所指的页面读到页帧中，将页帧号填入页表项，合法位置合法位置1 1，结束。，结束。 四、缺页处理 中断处理程序处理过程：中断处理程序处理过程：操作系统段式存储管理与虚存课件26 五、页淘汰淘汰一页的主要工作有：淘汰一页的主要工作有：1.1.查查P P页表项的修改位，若未修改，则合法位页表项的修改位，若未修改，则合法位 清清0 0，将页帧送回空闲页帧队列。，将页帧送回空闲页帧队列。2.2.若已修改，则检查若已修改，则检查P P的类型

18、栏。的类型栏。3.3.若是零页或回写若是零页或回写swapswap区页，则申请一块区页，则申请一块swapswap区区空间，将空间，将P P页表项的辅存块号置上并清除页类型。页表项的辅存块号置上并清除页类型。4.4.调用调用I/0I/0子系统，将页帧上的数据写到辅存块子系统，将页帧上的数据写到辅存块号所指的辅存空间中，对合法位清号所指的辅存空间中，对合法位清0 0，将页帧送，将页帧送回空闲页帧队列。回空闲页帧队列。操作系统段式存储管理与虚存课件275.3.3 页面替换策略页面替换策略虚存的作用：虚存的作用： 解决主存空间不足；解决主存空间不足； 让更多的进程并发运行，提高系统的让更多的进程并发

19、运行，提高系统的吞吐率。吞吐率。页故障引发：页故障引发： Page Out/Page InPage Out/Page In； 访问辅存。访问辅存。操作系统段式存储管理与虚存课件28页面替换策略中的基本概念 驻留集驻留集( (工作集工作集) )：进程的合法页集合；进程的合法页集合； 访问串：访问串：进程访问虚空间的地址踪迹。进程访问虚空间的地址踪迹。 举例：某进程依次访问如下地址，举例：某进程依次访问如下地址，01000100，04320432，01010101，06120612，01020102，01030103， 页式虚存管理以页为基本单位，只需页页式虚存管理以页为基本单位，只需页号即可。设

20、页面大小为号即可。设页面大小为100100，上述访问串可，上述访问串可简化为简化为1 1，4 4，1 1，6 6，1 1，1 1，操作系统段式存储管理与虚存课件29页面替换策略分成两类： 驻留集大小固定的替换策略；驻留集大小固定的替换策略； 驻留集大小可变的替换策略。驻留集大小可变的替换策略。设驻留集大小为设驻留集大小为m，s(t)为为t时刻的驻留集，时刻的驻留集，r(t)为为t时刻访问的页号。时刻访问的页号。t取取0,1,t，指，指访存指令执行时刻。访存指令执行时刻。操作系统段式存储管理与虚存课件30 驻留集与驻留集与paging in/out的关系：的关系： 进程刚创建时，驻留集为空。即进

21、程刚创建时，驻留集为空。即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)

22、页。页。 即即s(t+1)=s(t)-y+r(t+1)。 一、驻留集大小固定的替换策略操作系统段式存储管理与虚存课件31(一) FIFO替换算法(替换最早进入的页)举例：驻留集大小为举例：驻留集大小为3 3，访问串为：，访问串为： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 2770701201201231230430420423023023023O O O O O O O O O O出现了出现了1010次故障次故障命中率命中率1 1故障次数故障次数/ /访问串大小访问串大小1 110/13

23、=0.2310/13=0.23操作系统段式存储管理与虚存课件32FIFO方法的特点： 实现方便。不需要额外硬件。实现方便。不需要额外硬件。 效果不好，有效果不好，有BeladyBelady奇异。奇异。Belady奇异：指替换策略不满足随着指替换策略不满足随着驻留集的增大，页故障数一定减少的驻留集的增大，页故障数一定减少的规律。规律。操作系统段式存储管理与虚存课件33 (二) OPT(Optimal replacement)举例：驻留集大小为举例：驻留集大小为3 3，访问串为，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.7, 0, 1, 2, 0, 3,

24、 0, 4, 2, 3, 0, 3, 2.770701201201203203243243243203203203O O O O O O O淘汰下次访问距当前最远的那些页中序号最小的页。操作系统段式存储管理与虚存课件34 OPT方法特点： 最优的固定驻留集大小替换策略。最优的固定驻留集大小替换策略。 不可实现。不可实现。 OPT OPT策略对任意一个访问串的控制均有策略对任意一个访问串的控制均有最小的时空积（进程所占空间与时间的乘最小的时空积（进程所占空间与时间的乘积）。积）。 由于需要预先得知整个访问串的序，故由于需要预先得知整个访问串的序，故不能用于实践不能用于实践, ,仅作为一种标准，用

25、以测量仅作为一种标准，用以测量其他可行策略的性能。其他可行策略的性能。操作系统段式存储管理与虚存课件35 (三) LRU(Least Recently Used) 淘汰上次使用距当前最远的页。举例：驻留集大小为举例：驻留集大小为3 3，访问串为，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.770701201201203203403402432032032032O O O O O O O O O操作系统段式存储管理与虚存课件36LRU策略是一种栈算法。满足：满足：S（m,t）属于

26、）属于 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策略是栈算法。策略是栈算法。操作系统段式存储管理与虚存课件37LRU策略的特点：要硬件配合，实现费用高，要硬件配合，实现费用高，但效果适中。但效果适中。实现方法实现方法1 1：给每个页帧设一个计数器，每给每个页帧设一个计数器，每

27、访问一页，对应页帧计数清访问一页，对应页帧计数清0 0，其余页帧计，其余页帧计数加数加1 1，淘汰计数最大的页帧。，淘汰计数最大的页帧。实现方法实现方法2 2：用类似栈的结构来管理和实现用类似栈的结构来管理和实现LRULRU。栈算法没有Belady奇异。 设设n nm m，对于栈算法有，对于栈算法有S S( (m m, ,t t) )属于属于S S( (n n, ,t t) )，任取，任取r r( (t t) )，若，若r r( (t t)!)!S S( (n n, ,t t),),则则r r( (t t)!)!S S( (m m, ,t t) )。因此，驻留集为。因此，驻留集为n n 时出现

28、时出现的页故障一定会出现在驻留集为的页故障一定会出现在驻留集为m m 时。时。LRULRU没有没有BeladyBelady奇异奇异。操作系统段式存储管理与虚存课件38 (四) 实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬件为页帧在页表项中增加一位使用位，硬件每访存一次，即将对应页的使用位置每访存一次，即将对应页的使用位置1 1，操，操作系统页面管理程序定时将所有使用位清作系统页面管理程序定时将所有使用位清0 0。淘汰时任选一个使用位为淘汰时任选一个使用位为0 0的页。的页。 操作系统选择淘汰页时，尽量避免选被操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择

29、使用和修改修改过的页。因此，首先选择使用和修改位都为位都为0 0的页；若没有，再选修改位为的页；若没有，再选修改位为1 1，使用位为使用位为0 0的页；再选使用位为的页；再选使用位为1 1，修改位，修改位为为0 0的页；最后按的页；最后按FIFOFIFO选两者均为选两者均为1 1的页。的页。操作系统段式存储管理与虚存课件39程序行态：指程序访存布局特性和行为特性。指程序访存布局特性和行为特性。 局部性行态局部性行态: :一段时间内程序访存有局部性一段时间内程序访存有局部性. . 阶段转换行态阶段转换行态: :从一个局部集向另一个局部从一个局部集向另一个局部 集过渡是突然的集过渡是突然的. .

30、局部集一般不超过程序总页数的局部集一般不超过程序总页数的20%20%。 二、驻留集可变的替换策略引入原因：若驻留集小于局部集时引起抖若驻留集小于局部集时引起抖动，而驻留集大于局部集又是浪费。同时动，而驻留集大于局部集又是浪费。同时局部集又有大有小。局部集又有大有小。因此，应随着程序访问虚存的局部集大小因此，应随着程序访问虚存的局部集大小变化而改变驻留集。变化而改变驻留集。操作系统段式存储管理与虚存课件40 若驻留集中的某页有个访问间隔没若驻留集中的某页有个访问间隔没被访问，则将其淘汰。被访问，则将其淘汰。 举例：取举例：取=5=5，访问串为，访问串为 (一) WS(working set)1

31、2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 37070170127012701230123042304230423042304230237 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1021302130213210操作系统段式存储管理与虚存课件41实现： 每一页面设一计数器。每访存一次，每一页面设一计数器。每访存一次，将所有计数器加将所有计数器加1 1，所访存的页面计数器，所访存的页面计数器清清0 0，淘汰计数器值等于的页面。，淘汰计数器值等于的页面。特点： 开销太大，不实用。开销太大，不实用。操作系统段式存储管理与虚存课件42 每访问一页，将当前硬时钟值记录在每访问一页，将当前硬时钟值记录在页表项中，操作系统定时页表项中，操作系统定时( (以以T T为周期为周期) )检检查驻留集页表项的时钟值，若查驻留集页表项的时钟值，若: :当前时钟当前时钟值值- -页表项中时钟值，则淘汰之。页表项中时钟值，则淘汰之。 (二) SWS(Sampled Warking Set) 定时检查计数器，淘汰计数器值大于定时检查计数器，淘汰计数器值大于等于的页面。这样硬件消耗仍很大。等于的页面。这样硬件消耗仍很大。操作系统段式存储管理与虚存课件43 费用小，但效果不好。费用小，但效果不好。D D为两次页故障距离，为两次页故障距离，1/1/D