虚拟存储管理

操作系统第三讲,虚拟存储管理,前面所介绍的各种存储器管理方式有一个共同的特点，即它们都要求将一个作业全部装入内存后方能运行，于是，出现了下面这样两种情况：(1)有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。,虚拟存储器的引入,1常规存储器管理方式的特征(1)一次性。在前面所介绍的几种存储管理方式中，都要求将作业全部装入内存后方能运行，即作业在运行前需一次性地全部装入内存，而正是这一特征导致了上述两种情况的发生。此外，还有许多作业在每次运行时，并非其全部程序和数据都要用到。如果一次性地装入其全部程序，也是一种对内存空间的浪费。,(2)驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。尽管运行中的进程会因I/O而长期等待，或有的程序模块在运行过一次后就不再需要(运行)了，但它们都仍将继续占用宝贵的内存资源。,现在要研究的问题是：一次性及驻留性在程序运行时是否是必需的？,程序局部性原理,在一段时间内一个程序的执行往往呈现出高度,的局部性，表现在时间与空间两方面,时间局部性,一条指令被执行了，则在不久的将来它可能再,被执行,空间局部性,若某一存储单元被使用，则在一定时间内，与,该存储单元相邻的单元可能被使用,七、虚拟存储,连续性；驻留性；一次性；,离散性交换性多次性,以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术,1、概述,问题的提出,程序大于内存,程序暂时不执行或运行完是否还要占用内存,虚拟存储器的基本思想是？,虚拟存储器支持多道程序设计技术,程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换,虚拟存储技术,虚存：把内存与外存有机的结合起来使用，从而,得到一个容量很大的“内存”，这就是虚存,实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作；当没有足够的内存空间时，系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其它进程使用。（虚拟存储技术的概念）,目的：,提高内存利用率,概述（续2）,内存,磁盘控制器,MMU总线,虚拟地址CPU,物理地址,MMU：内存管理单元,虚拟存储器的特征,1多次性多次性是指一个作业被分成多次调入内存运行。多次性是虚拟存储器最重要的特征，任何其它的存储管理方式都不具有这一特征。因此，我们也可以认为虚拟存储器是具有多次性特征的存储器系统。2对换性对换性是指允许在作业的运行过程中进行换进(从外存调至内存)、换出(至外存的对换区)；甚至还允许将暂时不运行的进程调至外存，待它们重又具备运行条件时再调入内存。3虚拟性虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要的目标。,2、虚拟页式存储管理,（1）基本思想,在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,页号、驻留位、内存块号、保护位、访问位、修改位驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过保护位：读/写/执行禁止缓存位：采用内存映射I/O的机器中需要,页号,中断位内存块号保护位禁止缓存位访问位修改位,（2）页表表项设计,XXXX7X,5XXX340612,60K-64K56K-60K52K-56K48K-52K44K-48K40K-44K,36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K,物理地址空间,虚地址空间虚页,页框28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K,15141312,1110987654,3210,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,110在/不在内存,页表,虚地址8196,物理地址24580,（3）缺页中断（PageFault）处理,在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去,如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号,若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存,（4）页面淘汰算法,理想淘汰算法最佳页面算法（OPT：Optimal）淘汰以后不再需要的或最远的将来才会,用到的页面,实现？作用？,先进先出页面淘汰算法（FIFO）,选择在内存中驻留时间最长的页并淘汰之策略模型：超市撤换商品,页面淘汰算法（续1）,最近未使用页面淘汰算法,（NRUNotRecentlyUsed）,选择在最近一段时间内未使用过的一页并淘汰,之,实现：设置两位,访问位（R），修改位（M）启动一个进程时，R、M置0,R被定期清零,发生缺页中断时，操作系统检查R，M：,第0类：无访问，无修改第1类：无访问，有修改第2类：有访问，无修改第3类：有访问，有修改,操作系统随机从编号最小的非空类中选择一页淘汰,页面淘汰算法（续2）,是最佳淘汰页,并不是很好的淘汰页,该页有可能再被访问,该页可能再被访问,在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。在该算法中，除须考虑页面的使用情况外，还须再增加一个因素，即置换代价，这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。,页面淘汰算法（续3）,第二次机会淘汰算法,(SCR-SecondChance),按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0,实现：时钟（Clock）算法,页面淘汰算法（续4）,最近最久未使用页面淘汰算法,（LRULeastRecentlyUsed）,选择最后一次访问时间距离当前时间最,长的一页并淘汰之,即淘汰没有使用的时间最长的页,实现代价很高,时间戳或硬件方法,硬件方法：,在一个有n个页框的机器中，LRU硬件可以维持一个n*n位的矩阵，开始时所有位都是0。当访问到页K时，硬件首先把k行的位都设置成1，再把k列的位都设置成0.任何时刻，二进制值最小的行就是最久未使用的，第二小的行是下一个最久未使用的，以此类推。,页面淘汰算法（续5）,LRU的软件解决方案：,最不经常使用（NFU-NotFrequentlyUsed）,选择访问次数最少的页面淘汰之,实现：软件计数器，一页一个，初值为0。每次时钟中断时，计数器加R。发生缺页中断时，选择计数器值最小的一页淘汰,改进（模拟LRU）：计数器在加R前先右移一位,R位加到计数器的最左端,称为老化算法,发生缺页时，淘汰计数器值最小的页面,页05的R位时钟周期为0,页,012345,1000000011000000111000001111000001111000,0000000010000000110000000110000010110000,1000000001000000001000000001000010001000,0000000000000000100000000100000000100000,页05的R位时钟周期为2,页05的R位时钟周期为4,1000000011000000011000001011000001011000,1000000001000000101000001010000000101000,例1：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5，按照FIFO、LRU、OPT计算缺页次数,页面淘汰算法（续6）,LRU4321页14321页2432页343xxxx,4412x,3341x,543543354435x,215215321432xxx,共缺页中断10次,页面淘汰算法（续8）,OPT4321页14321页2433页344xxxx,4134,3134,5534x,4534,3534,2254x,15115544x,共缺页中断7次,页面淘汰算法（续9）,例2：某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？用FIFO算法计算缺页次数,页面淘汰算法（续10）,注：FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加,页面淘汰算法（续11）m=3时，缺页中断9次m=4时，缺页中断10次,分配给进程的物理页面数页面本身的大小程序的编制方法页面淘汰算法,（5）影响缺页次数的因素,试分析上述因素如何影响缺页次数？,程序编制方法1：Forj:=1to128Fori:=1to128Ai,j:=0;,程序编制方法2：Fori:=1to128Forj:=1to128Ai,j:=0;,影响缺页次数的因素（续1）例子3：内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放,你能看出两种程序编制方法有什么区别么？试分析哪种方法较好？,（1）颠簸（抖动）,在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动,原因：,页面淘汰算法不合理,分配给进程的物理页面数太少,3、性能问题,基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断,如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数,（2）工作集（WorkingSet）模型,对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集,内容取决于页的三个因素：,访页序列特性时刻Ti,窗口长度(),工作集（WorkingSet）模型（续1）,|t2,|t1ws(t1)=1,2,5,6,7ws(t2)=3,4,工作集（WorkingSet）模型（续2）例：26157775162341234443434441327,（1）段表内容,增加：,特征位（在/不在内存，是否可共享）存取权限位（读，写，执行）,标志位（是否修改过，能否移动）扩充位（固定长/可扩充）,4、虚拟段式存储管理,进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理,（2）越界中断处理,检查内存中是否有足够的空闲空间,若有，则装入该段，修改有关数据结,构，中断返回,若没有，检查内存中空闲区的总和是否,满足要求，是则应采用紧缩技术，转；否则，淘汰一（些）段，转,（3）缺段中断处理,大型程序：,若干程序段，若干数据段,一些熟知的事实：,进程的某些程序段在进程运行期间可能,根本不用,互斥执行的程序段没有必要同时驻留内,存,有些程序段执行一次后不再用到,（4）段的动态链接,静态链接：为了程序正确执行，必须由连接装配程序把它们连接成一个可运行的目标程序，并在程序运行前都装入内存。问题：花费时间，浪费空间,动态链接：,在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接,段的动态链接（续1）,LOAD,100,LOAD,100,600,600,800,直接寻址,间接寻址,100,100,数据,间接字,数据,段的动态链接（续2）链接间接字和链接中断机器指令：直接寻址，间接寻址,L,直接地址,段的动态链接（续3）采用间接寻址时，间接地址指示的单元的内容称为间接字，在间接字中，包含了直接地址，还包含了附加的状态位。格式为：,L：链接标志位L=0：该段已经建立了链接L=1：该段尚未链接,处理机在执行间接指令时，其硬件能自动对链接字中连接标志位进行判断。当L=1时，硬件自动发链接中断，并停止执行该间接指令，转去执行链接中断处理程序。处理完后（L已被中断处理程序改为0），再重新执行该间接指令；若L=0，则根据间接字中的直接地址去取数据,编译程序的准备工作：,段的动态链接（续4）,.,.,.,.,编译前,LOAD1,A|LOAD*1,3|100,100,1,3678,678,7“A|”,编译后,链接前,段的动态链接（续5）,100,链接后,678,7“A|,0,4120,段的动态链接（续6）3段LOAD*1,3|100,120,：12345678,段的动态链接（续7）4段,链接中断处理,根据链接间接字找出要访问段的符号名和段内地址,分配段号，检查该段是否在内存，若不在，则从外存调入，并登记段表，修改内存分配表,修改间接字：修改连接标志位为0，修改直接地址,重新启动被中断的指令执行,段的动态链接（续8）,页面尺寸,TLB的大小、位置、访问方式局部与全局分配策略装入策略与清除策略多级页表内存锁定,（5）其他有关设计问题,页面尺寸,确定页面大小对于分页的硬件设计非常重要要考虑的因素：,内部碎片页表长度,缺页次数（缺页率）,Intel80 x86/Pentium：4096或4M多页面大小的研究与使用,其他有关设计问题（续1）,快表TL