虚拟存储管理

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