15.2.2 5.2.2 段式管理段式管理页式管理缺点：页式管理缺点：对用户而言不自然对用户而言不自然 0 1 2 3 4 5 程程序序段段数数据据段段 0 1 2主程序主程序SIN 0 1 2主程序主程序SIN( (共子程序共子程序) )作业作业1 1作业作业2 22 整个作业的地址空间是二维的整个作业的地址空间是二维的, ,如下图如下图: :Y:Y:0 0500500C:C:0 0200200D:D:0 0300300CallCallLoadLoadstorestore0 01k1k分段分段MAINMAIN( (主程序主程序) )分段分段X X( (子程序子程序) )分段分段A A( (数据数据) )分段分段B B( (工作区工作区) )段式管理的特点：段式管理的特点： 按作业的自然段将其逻辑空间分成若干段，作按作业的自然段将其逻辑空间分成若干段，作业以段为单位分配内存。业以段为单位分配内存。3 一、空间安排 用户作业逻辑空间由若干自然段组成。用户作业逻辑空间由若干自然段组成。 逻辑地址：段号与段内偏移，记做逻辑地址：段号与段内偏移，记做S S，d d。编译及装配时把所有地址记成编译及装配时把所有地址记成(S,d)(S,d)的形式。的形式。 物理内存空间管理：与多道可变划分区法物理内存空间管理：与多道可变划分区法一样，系统以段为单位分配物理内存。一样，系统以段为单位分配物理内存。主程序主程序子程序子程序1子程序子程序2栈栈数据数据4 主程序 子程序1 子程序2栈数据逻辑空间逻辑空间 子程序2主程序栈数据OS 子程序1物理空间物理空间5二、动态地址转换保护码段长本段内存始地址 段表：由如下格式的段表项组成，作业由如下格式的段表项组成，作业每段由一个段表项表示。每段由一个段表项表示。 段表放于系统空间，进程段表放于系统空间，进程PCBPCB表中存有段表中存有段表始地址、段表长度。表始地址、段表长度。 段表始地址寄存器、段表长度寄存器。段表始地址寄存器、段表长度寄存器。6段号段号保护码保护码段长段长段内存始址段内存始址.保护码保护码段长段长段内存始址段内存始址.Sd段表始址段表始址段表长度段表长度+PA越界越界地址转换过程地址转换过程LALA段表段表78 三、共享主程序主程序SIN数据数据主程序主程序子程序子程序1SIN子程序子程序2SIN J1 J2段表段表主存主存两个作业共享两个作业共享SINSIN段的示例段的示例9 A段段SQRTSQRT B段段SQRT J1 J2段表段表主存主存两个作业共享两个作业共享SQRTSQRT段的示例段的示例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段表始址段表始址段表长度段表长度+越界越界+ 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=875ns15段表段表主程序子程序数据作业1主程序子程序数据作业2段表段表页表页表OS主存SINSINSINSINSINSINSINSIN16总结：总结：“放放” 连续存放：连续存放： 单道连续分配；单道连续分配； 多道连续固定分区；多道连续固定分区； 多道连续可变分区。多道连续可变分区。 不连续存放：不连续存放： 页式存储；页式存储； 段式存储；段式存储； 段页式存储。段页式存储。175.3.1 5.3.1 虚存的基本思想虚存的基本思想虚拟存储管理虚拟存储管理(虚存虚存)：把作业的一部分装入内存便可把作业的一部分装入内存便可运行作业的存储器系统。它具有部分装入、请求调入运行作业的存储器系统。它具有部分装入、请求调入和置换功能，它把辅存和主存一起管理，能从逻辑上和置换功能，它把辅存和主存一起管理，能从逻辑上对内存容量进行扩充。对内存容量进行扩充。 影响虚存大小因素：有效地址长度，外存的容量，影响虚存大小因素：有效地址长度，外存的容量，传送速度，使用频率。传送速度，使用频率。5.35.3虚拟存储管理虚拟存储管理目的：目的：提供用户进程一个巨大的虚拟存储空间。提供用户进程一个巨大的虚拟存储空间。手段：手段：利用外存利用外存( (磁盘磁盘) )实现此虚空间。实现此虚空间。18实现该虚存管理的基本方法是：n 在页式（段式、段页式）管理的基础上，在页式（段式、段页式）管理的基础上，仅将进程的一部分页（段）放于主存。页仅将进程的一部分页（段）放于主存。页（段）表项中注明该页或段是否在主存。（段）表项中注明该页或段是否在主存。n 程序执行时，如果访问的页（段）不存程序执行时，如果访问的页（段）不存在主存，根据页（段）表项的指示，将其从在主存，根据页（段）表项的指示，将其从外存调入主存，如果此时无可用的内存空间，外存调入主存，如果此时无可用的内存空间，则先淘汰若干页帧或段。则先淘汰若干页帧或段。19交换区（交换区（SWAPSWAP）：）： 引入原因：引入原因：执行程序文件中的初始值不能被修改；执行程序文件中的初始值不能被修改； 主要作用：主要作用：用于存放那些可读写的进程页面。用于存放那些可读写的进程页面。两种页类型：两种页类型： 回写回写swapswap文件页：文件页：对可读写的进程页面，初始对可读写的进程页面，初始值从执行程序文件获得，一旦修改，写回时则写值从执行程序文件获得，一旦修改，写回时则写到交换区，再度使用时，则从交换区中取出；到交换区，再度使用时，则从交换区中取出； 零页：零页：在执行文件中说明是初始值为在执行文件中说明是初始值为0 0的工作区；的工作区；回写时也要写到交换空间中。回写时也要写到交换空间中。5.3.2 5.3.2 页式虚存管理页式虚存管理20一、页表项结构:合法位合法位 修改位修改位 页类型页类型 保护码保护码 外存块号外存块号 页帧号页帧号合法位：合法位：表示该页在内存，为表示该页在内存，为1 1或或0 0。修改位：修改位：表示该页被修改过，在释放或淘汰时应表示该页被修改过，在释放或淘汰时应 写回外存。写回外存。页类型：页类型：零页时，表示该页在分配物理页帧时应零页时，表示该页在分配物理页帧时应 清清0 0页帧空间页帧空间; ;回写回写swapswap区页，表示回区页，表示回 写写swapswap区；没设置类型时，正常方式处理区；没设置类型时，正常方式处理保护码：保护码：R,W,ER,W,E保护说明。保护说明。外存块号：外存块号：该页所在外存的块号。该页所在外存的块号。页页 帧帧 号：号：当在合法位置上时，代表该页所在内当在合法位置上时，代表该页所在内 存的页帧号。存的页帧号。21二、页表建立 分配分配pidpid给子进程，分配给子进程，分配PCBPCB空间空间; ; 初始化初始化PCBPCB（进程标识，调度信息）（进程标识，调度信息）; ; 分配子进程页表空间分配子进程页表空间; ; 复制父进程的程序区页表项，使程序复制父进程的程序区页表项，使程序共享共享; ;1.利用父进程页表生成进程页表(如UNIX的fork()初始化页表方法：在进程创建时建立页表，页表项在初始时，在进程创建时建立页表，页表项在初始时，合法位、修改位及页帧号都为合法位、修改位及页帧号都为0 0。22复制父进程的数据区和栈区，为数据区和复制父进程的数据区和栈区，为数据区和栈区分配栈区分配swapswap空间，复制并修改数据区和空间，复制并修改数据区和栈区页表项内容栈区页表项内容; ;继承父进程对其他资源的访问现场继承父进程对其他资源的访问现场; ;父进程父进程PCBPCB中现场区初始化子进程的现场中现场区初始化子进程的现场区，且使子进程区，且使子进程fork( )fork( )返回值为零返回值为零; ;将子进程挂到就绪队列将子进程挂到就绪队列; ;返回子进程返回子进程pidpid给父进程。给父进程。23为为执执行行程程序序页页面面创创建建页页表表项项，将将保保护护码码置置为为可可执执行行，辅辅存存块块号号置置为为该该页页对对应应执执行行程程序序文文件的辅存块号。（不必回写）。件的辅存块号。（不必回写）。为为所所有有初初始始数数据据页页创创建建页页表表项项，保保护护码码置置为为可可读读写写，页页类类型型说说明明为为回回写写swapswap页页，辅辅存存块块号号为为该该页页对对应应文文件件的的辅辅存存块块号号，待待该该页页回回写写时，再分配时，再分配swapswap区空间，修改辅存块号栏。区空间，修改辅存块号栏。为为所所有有零零数数据据页页面面创创建建页页表表项项，保保护护码码为为可可读读写写，页页类类型型说说明明为为零零页页，辅辅存存块块号号栏栏为为空空。当当第第一一次次访访问问该该页页时时，分分配配主主存存页页帧帧并并清清0 0；回回写写时时，再再分分配配swapswap区区空空间间，填填写写辅辅存存块块号栏。号栏。2.用一个可执行的文件来初始化页表。24三、硬件动态地址转换三、硬件动态地址转换页表始址页表始址B 页表长度页表长度L3L?3L?+ +页表寄存器页表寄存器越界中断越界中断逻辑地址逻辑地址V（3，d）页帧号页帧号页号页号物理地址物理地址26480123是是否否（8，d）A0A2A1A30页框号页框号123456789偏移偏移d快表快表否否是是读页号读页号是否在是否在是否在是否在内存内存内存内存1110缺页异常缺页异常（页故障）（页故障）页表页表合法位合法位是是否否25 1. 1.根据发生页故障的虚地址得到页表项。根据发生页故障的虚地址得到页表项。 2.2.申请一个可用的页帧申请一个可用的页帧( (根据所采用的替换策根据所采用的替换策略可能需要引起淘汰某一页略可能需要引起淘汰某一页);); 3. 3.检查页类型检查页类型: : (1) (1) 若为零页，则将页帧清若为零页，则将页帧清0 0，将页帧号填，将页帧号填 入页表项的页帧号一栏，置合法位为入页表项的页帧号一栏，置合法位为1 1。 (2)(2) 若非零页，则调用若非零页，则调用I/OI/O子系统将辅存块号子系统将辅存块号所指的页面读到页帧中，将页帧号填入页表项，所指的页面读到页帧中，将页帧号填入页表项，合法位置合法位置1 1，结束。，结束。 四、缺页处理 中断处理程序处理过程：中断处理程序处理过程：26 五、页淘汰淘汰一页的主要工作有：淘汰一页的主要工作有：1.1.查查P P页表项的修改位，若未修改，则合法位页表项的修改位，若未修改，则合法位 清清0 0，将页帧送回空闲页帧队列。，将页帧送回空闲页帧队列。2.2.若已修改，则检查若已修改，则检查P P的类型栏。的类型栏。3.3.若是零页或回写若是零页或回写swapswap区页，则申请一块区页，则申请一块swapswap区区空间，将空间，将P P页表项的辅存块号置上并清除页类型。页表项的辅存块号置上并清除页类型。4.4.调用调用I/0I/0子系统，将页帧上的数据写到辅存块号子系统，将页帧上的数据写到辅存块号所指的辅存空间中，对合法位清所指的辅存空间中，对合法位清0 0，将页帧送回空，将页帧送回空闲页帧队列。闲页帧队列。275.3.3 页面替换策略页面替换策略虚存的作用：虚存的作用： 解决主存空间不足；解决主存空间不足； 让更多的进程并发运行，提高系统的让更多的进程并发运行，提高系统的吞吐率。吞吐率。页故障引发：页故障引发： Page Out/Page InPage Out/Page In； 访问辅存。访问辅存。28页面替换策略中的基本概念 驻留集驻留集( (工作集工作集) )：进程的合法页集合；进程的合法页集合； 访问串：访问串：进程访问虚空间的地址踪迹。进程访问虚空间的地址踪迹。 举例：某进程依次访问如下地址，举例：某进程依次访问如下地址，01000100，04320432，01010101，06120612，01020102，01030103， 页式虚存管理以页为基本单位，只需页号页式虚存管理以页为基本单位，只需页号即可。设页面大小为即可。设页面大小为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的关系：的关系： 进程刚创建时，驻留集为空。即进程刚创建时，驻留集为空。即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 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=0.2310/13=0.2332FIFO方法的特点： 实现方便。不需要额外硬件。实现方便。不需要额外硬件。 效果不好，有效果不好，有BeladyBelady奇异。奇异。Belady奇异：指替换策略不满足随着指替换策略不满足随着驻留集的增大，页故障数一定减少的驻留集的增大，页故障数一定减少的规律。规律。33 (二) OPT(Optimal replacement)举例：驻留集大小为举例：驻留集大小为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.2.770701201201203203243243243203203203O O O O O O O淘汰下次访问距当前最远的那些页中序号最小的页。34 OPT方法特点： 最优的固定驻留集大小替换策略。最优的固定驻留集大小替换策略。 不可实现。不可实现。 OPT OPT策略对任意一个访问串的控制均有最策略对任意一个访问串的控制均有最小的时空积（进程所占空间与时间的乘积）。小的时空积（进程所占空间与时间的乘积）。 由于需要预先得知整个访问串的序，故由于需要预先得知整个访问串的序，故不能用于实践不能用于实践, ,仅作为一种标准，用以测量仅作为一种标准，用以测量其他可行策略的性能。其他可行策略的性能。35 (三) LRU(Least Recently Used) 淘汰上次使用距当前最远的页。举例：驻留集大小为举例：驻留集大小为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.2.770701201201203203403402432032032032O O O O O O O O O36LRU策略是一种栈算法。满足：满足：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策略是栈算法。策略是栈算法。37LRU策略的特点：要硬件配合，实现费用高，要硬件配合，实现费用高，但效果适中。但效果适中。实现方法实现方法1 1：给每个页帧设一个计数器，每给每个页帧设一个计数器，每访问一页，对应页帧计数清访问一页，对应页帧计数清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 时出现时出现的页故障一定会出现在驻留集为的页故障一定会出现在驻留集为m m 时。时。LRULRU没有没有BeladyBelady奇异奇异。38 (四) 实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬件每为页帧在页表项中增加一位使用位，硬件每访存一次，即将对应页的使用位置访存一次，即将对应页的使用位置1 1，操作，操作系统页面管理程序定时将所有使用位清系统页面管理程序定时将所有使用位清0 0。淘汰时任选一个使用位为淘汰时任选一个使用位为0 0的页。的页。 操作系统选择淘汰页时，尽量避免选被操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改位修改过的页。因此，首先选择使用和修改位都为都为0 0的页；若没有，再选修改位为的页；若没有，再选修改位为1 1，使用，使用位为位为0 0的页；再选使用位为的页；再选使用位为1 1，修改位为，修改位为0 0的的页；最后按页；最后按FIFOFIFO选两者均为选两者均为1 1的页。的页。39程序行态：指程序访存布局特性和行为特性。指程序访存布局特性和行为特性。 局部性行态局部性行态: :一段时间内程序访存有局部性一段时间内程序访存有局部性. . 阶段转换行态阶段转换行态: :从一个局部集向另一个局部从一个局部集向另一个局部 集过渡是突然的集过渡是突然的. . 局部集一般不超过程序总页数的局部集一般不超过程序总页数的20%20%。 二、驻留集可变的替换策略引入原因：若驻留集小于局部集时引起抖动，若驻留集小于局部集时引起抖动，而驻留集大于局部集又是浪费。同时局部集而驻留集大于局部集又是浪费。同时局部集又有大有小。又有大有小。因此，应随着程序访问虚存的局部集大小变因此，应随着程序访问虚存的局部集大小变化而改变驻留集。化而改变驻留集。40 若驻留集中的某页有若驻留集中的某页有个访问间隔没个访问间隔没被访问，则将其淘汰。被访问，则将其淘汰。 举例：取举例：取=5=5，访问串为，访问串为 (一) WS(working set)1 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 102130213021321041实现： 每一页面设一计数器。每访存一次，每一页面设一计数器。每访存一次，将所有计数器加将所有计数器加1 1，所访存的页面计数器，所访存的页面计数器清清0 0，淘汰计数器值等于，淘汰计数器值等于的页面。的页面。特点： 开销太大，不实用。开销太大，不实用。42 每访问一页，将当前硬时钟值记录在每访问一页，将当前硬时钟值记录在页表项中，操作系统定时页表项中，操作系统定时( (以以T T为周期为周期) )检检查驻留集页表项的时钟值，若查驻留集页表项的时钟值，若: :当前时钟当前时钟值值- -页表项中时钟值页表项中时钟值，则淘汰之。，则淘汰之。 (二) SWS(Sampled Warking Set) 定时检查计数器，淘汰计数器值大于定时检查计数器，淘汰计数器值大于等于等于的页面。这样硬件消耗仍很大。的页面。这样硬件消耗仍很大。43 费用小，但效果不好。费用小，但效果不好。D D为两次页故障距离，为两次页故障距离，1/1/D D为当前页故障率，为当前页故障率，f f为阈值。为阈值。 1/1/D Df f，则淘汰驻留集中使用位为则淘汰驻留集中使用位为0 0的页。的页。 1/1/D Df f，增加驻留集大小，加入故障页，增加驻留集大小，加入故障页，所有驻留集中页的使用位清所有驻留集中页的使用位清0 0。 (三) VMIN(Variable Minimal replacement) 若某页距下次访问的距离大于若某页距下次访问的距离大于，则将其，则将其淘汰淘汰( (不能实用不能实用) )；与；与相同时，相同时，VMINVMIN与与WSWS的故的故障数相同，但障数相同，但VMINVMIN的平均驻留集要小。的平均驻留集要小。 (四) PFF(Page Fault Frequency)44 实用实用OSOS选择动态驻留集选择动态驻留集FIFO(SWS)FIFO(SWS)的变种的变种 设立两个队列：自由链表和修改链表。设立两个队列：自由链表和修改链表。 定时作页淘汰：淘汰时不立即删除页中数据，定时作页淘汰：淘汰时不立即删除页中数据，要根据页面是否修改挂入自由链要根据页面是否修改挂入自由链/ /修改链，修改修改链，修改链过长时，回写页面后改挂到自由链中。链过长时，回写页面后改挂到自由链中。 paging inpaging in要用空页时要用空页时, ,选自由链的第一页帧，选自由链的第一页帧，这时页中数据被覆盖这时页中数据被覆盖, ,改变该页帧原页面页表项改变该页帧原页面页表项状态等信息。状态等信息。 在自由链在自由链/ /修改链中的页面再次被访问时，则修改链中的页面再次被访问时，则将该页从链中摘除将该页从链中摘除, ,该页又能通过页表项访问到。该页又能通过页表项访问到。 三、替换策略选择45预调请调与预调的区别：请调与预调的区别： 存储管理：用时分配调入与预分配调入；存储管理：用时分配调入与预分配调入； 替换策略：要时页淘汰与预淘汰。替换策略：要时页淘汰与预淘汰。固定驻留集大小时，一般驻留集未满时，固定驻留集大小时，一般驻留集未满时，采用预调；待驻留集满即改为请调。采用预调；待驻留集满即改为请调。46n作业：作业：P131 5.7，5.13， 5.18(，FIFO)补课通知补课通知14周星期三周星期三5,6节，地点：公共教学楼节，地点：公共教学楼108