虚拟存储管理

操作系统第三讲虚拟存储管理前面所介介绍的各各种存储储器管理理方式有有一个共共同的特特点，即即它们都都要求将将一个作作业全部部装入内内存后方方能运行行，于是是，出现现了下面面这样两两种情况况：(1)有有的作作业很大大，其所所要求的的内存空空间超过过了内存存总容量量，作业业不能全全部被装装入内存存，致使使该作业业无法运运行。(2)有有大量量作业要要求运行行，但由由于内存存容量不不足以容容纳所有有这些作作业，只只能将少少数作业业装入入内存让让它们先先运行，，而将其其它大量量的作业业留在外外存上等等待。虚拟存储储器的引引入1．常规规存储器器管理方方式的特特征(1)一一次性性。在前面所所介绍的的几种存存储管理理方式中中，都要要求将作作业全部部装入内内存后方方能运行行，即作作业在运运行前需需一次性性地全部部装入内内存，而而正是这这一特征征导致了了上述两两种情况况的发生生。此外外，还有有许多作作业在每每次运行行时，并并非其全全部程序序和数据据都要用用到。如如果一次次性地装装入其全全部程序序，也是是一种对对内存空空间的浪浪费。(2)驻驻留性性。作业装入入内存后后，便一一直驻留留在内存存中，直直至作业业运行结结束。尽尽管运行行中的进进程会因因I/O而长期期等待，，或有的的程序模模块在运运行过一一次后就就不再需需要(运运行)了了，但它它们都仍仍将继续续占用宝宝贵的内内存资源源。现在要研研究的问问题是：：一次性性及驻留留性在程程序运行行时是否否是必需需的？程序局部部性原理理在一段时时间内一一个程序序的执行行往往呈呈现出高高度的局部性性，表现现在时间间与空间间两方面面时间局部部性一条指令令被执行行了，则则在不久久的将来来它可能能再被执行空间局部部性若某一存存储单元元被使用用，则在在一定时时间内，，与该存储单单元相邻邻的单元元可能被被使用七、虚拟拟存储连续性；；驻留性；；一次性；；离散性交换性多次性以CPU时间和外存存空间换换取昂贵贵内存空空间，这是是操作系系统中的的资源转转换技术术1、概述问题的提提出程序大于于内存程序暂时时不执行行或运行行完是否否还要占占用内存存虚拟存储储器的基本思想想是？虚拟存储储器支持持多道程程序设计计技术程序、数数据、堆堆栈的大大小可以以超过内内存的大大小，操操作系统统把程序序当前使使用的部部分保留留在内存存，而把把其它部部分保存存在磁盘盘上，并并在需要要时在内内存和磁磁盘之间间动态交交换虚拟存储储技术虚存：把内存与与外存有有机的结结合起来来使用，，从而得到一个个容量很很大的“内存”，这就是是虚存实现思想想：当进程运运行时，，先将一一部分程程序装入入内存，另另一部分分暂时留留在外存存；当要要执行的的指令不在内内存时，，由系统统自动完完成将它它们从外外存调入内存存工作；；当没有有足够的的内存空空间时，，系统自动选选择部分分内存空空间，将将其中原原有的内内容交换到磁磁盘上，，并释放放这些内内存空间间供其它它进程使用。。（虚拟存存储技术术的概念念）目的：提高内存存利用率率概述（续续2）内存

磁盘控制器MMU

总线虚拟地址址CPU物理地址址MMU：内存管管理单元元虚拟存储储器的特特征1．多次次性多次性是是指一个个作业被被分成多多次调入入内存运运行。多多次性是是虚拟存存储器最最重要的的特征，，任何其其它的存存储管理理方式都都不具有有这一特特征。因因此，我我们也可可以认为为虚拟存存储器是是具有多多次性特特征的存存储器系系统。2．对换换性对换性是是指允许许在作业业的运行行过程中中进行换换进(从从外存调调至内存存)、、换出((至外存存的对换换区)；；甚至至还允许许将暂时时不运行行的进程程调至外外存，待待它们重重又具备备运行条条件时再再调入内内存。3．虚拟拟性虚拟性是是指能够够从逻辑辑上扩充充内存容容量，使使用户所所看到的的内存容容量远大大于实际际内存容容量。这这是虚拟拟存储器器所表现现出来的的最重要要的特征征，也是是实现虚虚拟存储储器的最最重要的的目标。。2、虚拟页页式存储储管理（1）基本思想想在进程开开始运行行之前，，不是装装入全部部页面，而是是装入一一个或零零个页面面，之后后根据进程运运行的需需要，动动态装入入其它页页面；当内内存空间间已满，，而又需需要装入入新的页面时时，则根根据某种种算法淘淘汰某个个页面，以便便装入新新的页面面页号、驻驻留位、、内存块块号、保保护位、、访问位、修改改位驻留位（（中断位位）：表表示该页页是在内内存还是是在外存存访问位：：根据访访问位来来决定淘淘汰哪页页（由不不同的算算法决定）修改位：：查看此此页是否否在内存存中被修修改过保护位：：读/写/执行禁止缓存存位：采采用内存存映射I/O的机器中中需要页号中断位内内存块号号保保护位位禁止缓存存位访问位修修改改位（2）页表表表项设计计XXXX 7X

5XXX 3 4 0 6 1 260K--64K56K--60K52K--56K48K--52K44K--48K40K--44K36K--40K32K--36K28K--32K24K--28K20K--24K16K--20K12K--16K8K-12K4K-8K0K-4K物理地址址空间虚地址空空间}虚页页框28K--32K24K--28K20K--24K16K--20K12K--16K8K-12K4K-8K0K-4K0000000000000000111100001011000000000000011110010001110100110101151413121110 9 8 7 6 5 432100010000000000100110000000000100110在/不在内存存页表虚地址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

页343 xxxx4 4 1 2 x3 3 4 1 x5 5 3 4 x43 55 33 44

√√

2 2 5 3x15 11 22 55 x√共缺页中断9次LRU4321页14321页2432页343xxxx4 4 1 2 x3 3 4 1 x543543354435x√√215215321432xxx共缺页中中断10次页面淘汰汰算法（（续8）OPT4321页14321页2433页344xxxx

4134√

3134√

5534 x

4534

√

3534

√

2254 x15115544x√共缺页中中断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）段的动态态链接静态链接接：为了了程序正正确执行行，必须须由连接接装配程序把它它们连接接成一个个可运行行的目标标程序，，并在程序运运行前都都装入内内存。问题：花花费时间间，浪费费空间动态链接接：在程序开开始运行行时，只只将主程程序段装装配好并并调入内存，其其它各段段的装配配是在主主程序段段的运行行过程中逐步步完成。。每当需需要调用用一个新新段时，，再将这个新新段装配配好，并并与主程程序段链链接段的动态态链接（（续1）LOAD100LOAD100600600800直接寻址址间接寻址址100100数据间接字数据段的动态态链接（（续2）链接间接字和链链接中断断机器指令令：直接接寻址，，间接寻寻址L直接地址址段的动态态链接（（续3）采用间接接寻址时时，间接接地址指指示的单单元的内容称为为间接字字，在间间接字中中，包含含了直接地址，，还包含含了附加加的状态态位。格格式 为：L：链接标标志位L=0：该段已已经建立立了链接L=1：该段尚尚未链接接处理机在在执行间间接指令令时，其其硬件能能自动对链接字字中连接接标志位位进行判判断。当当L=1时，硬件件自动发发链接中中断，并并停止执执行该间接指令令，转去去执行链链接中断断处理程程序。处理完后后（L已被中断断处理程程序改为为0），再重新执执行该间间接指令令；若L=0，则根据据间接字中中的直接接地址去去取数据据编译程序序的准备备工作：：段的动态态链接（（续4）............编译前LOAD1,,[A]|<<B>LOAD*1,3|100100136786787“[A]|<<B>””编译后链接前段的动态态链接（（续5）100链接后6787“[A]|<<B>04120段的动态态链接（（续6）3段LOAD*1,3||100120<Y>：12345678段的动态态链接（（续7）

4段链接中断断处理根据链接接间接字字找出要要访问段段的符号号名和段内地址址分配段号号，检查查该段是是否在内内存，若若不在，则从从外存调调入，并并登记段段表，修修改内存分配表表修改间接接字：修修改连接接标志位位为0，修改直接地址址重新启动动被中断断的指令令执行段的动态态链接（（续8）页面尺寸寸TLB的大小、、位置、、访问方方式局部与全全局分配配策略装入策略略与清清除策策略多级页表表内存锁定定（5）其他有关关设计问问题页面尺寸寸确定页面面大小对对于分页页的硬件件设计非非常重要要要考虑的的因素：：内