第8章_虚拟存储管理

1、812 虚拟存储器虚拟存储器 n实现方法：实现方法：一个进程在运行之时，没有必要全部装入内存，而只把当前运行所需要的页（段）装入内存便可启动运行，而其余部分则存放在磁盘上。程序在运行时，如果所需要的页（段）已经调入内存，便可以继续执行下去。如果所需要的页（段）不在内存，此时程序应利用操作系统所提供的请求调页（段）功能，将该页（段）调入内存，以使程序能够运行下去。如果此时分配给该程序的内存已全部占用，不能装入新的页（段），则需要利用系统的置换功能，把内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间，再将所要装入的页（段）调入内存，使程序能够继续运行下去。 812 虚拟存储器虚拟存储器 n

2、虚拟存储器的定义：虚拟存储器的定义：是指仅把进程的一部分装入内存便可运行的存储器系统，它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。n虚拟存储器的逻辑容量：虚拟存储器的逻辑容量：虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决定。82 请求分页式存储管理方式请求分页式存储管理方式 请求分页式存储管理是在分页式存储管理的基础上，增加了请求调页功能、页面置换功能而形成的页式虚拟存储系统。它是目前常用的一种虚拟存储器的方式。82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 n基本原理：基本原理：在请求分页式存储管理系统中，进程运行之前将一部分页面

3、装入内存，另外一部分页面则装入外存。在进程运行过程中，如果所访问的页面不在内存中，则发生缺页中断，进入操作系统，由操作系统进行页面的动态调度。其方法如下：u找到被访问页面在外存中的地址；u在内存中找一个空闲块，如果没有，则按照淘汰算法选择一个内存块，将此块内容写回外存，修改页表；u读入所需的页面，修改页表；u重新启动进程，执行被中断的指令。 82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 n页表机制：页表机制：纯分页的页表只有两项：页号和物理块。而请求分页存储管理增加了调入功能和置换功能，故需在页表中增加若干项，供程序在换进换出时参考。下面所示是一请求分页系统中的页表：页号

4、物理块号 状态位P 访问字段A 修改位M 外存地址u状态位状态位P：用于指示该页是否已调入内存，0表示该页已在内存，1表示该页不在内存，供程序访问时参考； u访问字段访问字段A：用于记录该页在一段时间内被访问的次数，或最近已有多长时间未被访问，供置换算法选择页面时参考； 82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 u修改位修改位M：用于记录该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一个副本，因此，若未被修改，在置换该页时就不需将该页写回到磁盘上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写回磁盘上，以保证磁盘上所保留的始终是最新副本

5、。 u外存地址：外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。 82 2 页面分配策略页面分配策略 n内存页面分配策略：内存页面分配策略：u平均分配平均分配 ：将内存中的所有可供分配的物理块，平均分配给各个进程。这是最简单的分配方式，它看起来很公平，但实际上很不公平，因为它没有考虑进程的大小等因素。u按进程大小比例分配按进程大小比例分配 ：系统按进程的大小按比例分配物理块。若m为可用物理块总和，S为各进程页面总和，si为第i个进程的页面数，则为第i个进程分配的页面数为：u按进程优先级比例分配 ：为照顾重要的、紧迫的进程，使其能够尽快的完成，可以为其分配较多的内存物理块

6、。 )(mSsINTaii82 2 页面分配策略页面分配策略 n外存块的分配策略：外存块的分配策略：u静态分配静态分配 ：一个进程在运行前，将其所有页面全部装入外存。当某一外存页面被调入内存时，所占用外存页面并不释放。这样，当该页面以后被淘汰时，如果它在内存中未被修改过，则不必写回外存，因为外存中有一个和它完全相同的副本，这可以减少因页面调度而引起的系统开销，代价是牺牲一定的外存空间。u动态分配动态分配 ：一个进程在运行前，仅将未装入内存的那部分页面装入外存。当某一外存页面被调入内存，释放所占用的外存空间。这样，当该页面以后被淘汰时，不管它在内存中是否被修改过，都必须重新为其申请外存物理块，将

7、该页重新写回外存。这种方法的优点是节省外存空间，但会增加由页面调度而引起的系统开销。82 3 页面调入时机页面调入时机 n请求调页策略：请求调页策略：当发生缺页中断时进行调度，即当访问某一页而该页不在内存时，立即提出请求，由系统将所需页面调入内存。显然，采用纯请求调页策略，被调入内存的页面一定会被用到，不会发生无意义的页面调度。但是，请求调页策略也有一个缺点，从缺页中断发生到页面被调入内存，发生缺页中断的进程必须等待，影响了进程的推进速度。 n预调页策略：预调页策略：由于在外存上查找所缺的页，须经历较长的时间。如果一个进程存放在外存中的许多页在一个连续的区域中，每次调入若干个页会比每次调入一页

8、更高效些。但如果调入的一批页面中的大多数都未被访问，则这种调入又是低效的。可见，如果预测比较准确，会大大降低缺页中断率，从而提高进程的推进速度。82 4 页面置换算法页面置换算法 n最佳置换算法（最佳置换算法（OPT，Optimal）：）：最佳置换算法置换那些以后永不再使用的或者在最长的时间以后才会用到的页面。显然，这种算法的缺页率最低。然而，该算法只是一种理论上的算法，因为很难估计哪一个页面是以后永远不再使用或在最长时间以后才会用到的页面，所以，这种算法是不能实现的。尽管如此，该算法仍然是有意义的，可以把它作为衡量其它算法优劣的一个标准。82 4 页面置换算法页面置换算法 【例8-1】假定系

9、统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置换算法，计算缺页中断次数和缺页中断率。 解：页面置换过程如下表所示：页面访问序列页面访问序列50120304230321201501500000223332220100115122233222000101100511304440331222555+-+-+-+-+-+-缺页中断次数=9缺页中断率=9/20=45% 82 4 页面置换算法页面置换算法 n先进先出置换算法（先进先出置换算法（FIFO，First-In First-Out） ：先进先出置换算法总是置换

10、最先进入内存的页面。该算法实现简单，只须把一个进程已调入内存的页面，按照进入内存的先后顺序排成一个队列，当一个页面由外存调入内存时排入队尾，需要淘汰时取队首的页面。82 4 页面置换算法页面置换算法 【例8-2】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先进先出置换算法，计算缺页中断次数和缺页中断率。 解：页面置换过程如下表所示：页面访问序列页面访问序列5012030423032120150150122304230001222501501123042333011125050012304222300012

11、5+-+-+-+缺页中断次数=15缺页中断率=15/20=75% 82 4 页面置换算法页面置换算法 Belady异常现象：异常现象：一般而言，分配给进程的物理块越多，运行时的缺页次数应该越少。但是Belady在1969年发现了一个反例，使用FIFO算法时，四个物理块时的缺页次数比三个物理块时的多，这种反常的现象称为Belady异常。如下面两表所示，一个进程有5个页面，页面访问序列如下：Belady异常现象（3个物理块的FIFO现象） 82 4 页面置换算法页面置换算法 Belady异常现象（4个物理块的FIFO现象） 由表中可见，3个物理块时缺页次数是9次，缺页中断率为9/12=75%；而4

12、个物理块时的缺页次数是10次，缺页中断率为10/1283.3%。82 4 页面置换算法页面置换算法 n最近最久未使用置换算法（最近最久未使用置换算法（LRU，Least Recently Used）：）：该算法的基本思想是：如果某一页面被访问了，那么它很可能马上又被访问；反之，如果某一页面很久没有被访问，那么最近也不会再次被访问。因此，该算法为每一个页面设置一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面予以淘汰。uLRU的实现：的实现：p记时法：记时法：系统为每一页面增设一个记时器。每当一个页面被访问时，当时的

13、绝对时钟内容被拷贝到对应的记时器中，这样系统记录了内存所有页面最后一次被访问的时间。淘汰页面时，选取记时器中值最小的页面淘汰。82 4 页面置换算法页面置换算法 uLRU的缺点：的缺点：虽然LRU在理论上是可以实现的，但代价太高。为了实现LRU，需要在内存维持一个包含所有页的链表，最近使用的页面在表头，最近未使用的页面在表尾。而每次访问页面时都需要对链表进行更新。在链表中找到所需的页，将它移动到表头是一个非常费时的操作，即使使用硬件实现也是一样。 82 4 页面置换算法页面置换算法 【例8-3】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2

14、、1、2、0、1、5、0、1。采用最近最久未使用置换算法，计算缺页中断次数和缺页中断率。 解：页面置换过程如下表所示：页面访问序列页面访问序列50120304230321201501501203042303212015015012030423032120150501223042203312015+-+-+-+-+-+-缺页中断次数=12缺页中断率=12/20=60% 82 4 页面置换算法页面置换算法 n最近未使用置换算法最近未使用置换算法（NRU，Not Recently Used） ：为了克服LRU的缺点，最近未使用置换算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个

15、循环队列。当某页被访问时，其访问位置1。在选择一页淘汰时，检查其访问位，如果是0，则淘汰该页；若为1，则把其置0，暂不换出该页，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回队首再去检查第一个页面。 事实上，NRU算法不但希望淘汰最近未使用的页，而且还希望被挑选的页在内存驻留期间，其页面内的数据未被修改过。淘汰该页时，由于该页未被修改过，因此不必写盘，从而减少了磁盘的I/O操作次数。为此，要为每页增设两个硬件位：访问位和修改位：82 4 页面置换算法页面置换算法 访问位A=0：该页尚未被访问过 =1：该页已经被访问过修改位M=0：该页尚未被修改过

16、=1：该页已经被修改过访问位和修改位的组合有以下四种：u1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页；u2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页；u3类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再次被访问；u4类（A=1，M=1）：最近已被访问且被修改，该页可能再次被访问。82 4 页面置换算法页面置换算法 开始时，所有页的访问位、修改位都置为0。当访问某页时，将该页访问位置1。当某页的数据被修改，则该页的修改位置1。当要选择一页淘汰时，挑选内存中现有的类别最低的页淘汰。 82 4 页面置换算法页面置换算法 nClo

17、ck置换算法：置换算法：最近未使用置换算法是一种比较合理的算法，但它经常要在链表中移动页面，大大降低了系统效率。为了克服这个缺陷，把所有的页面保存在一个类似时钟表面的环形链表中，用一个表针指向可能淘汰的页面，如下图所示 ABCDEFGHIJK82 4 页面置换算法页面置换算法 当发生缺页时，该算法首先检查表针指向的页面，如果其访问位是0，则淘汰该页，并把新的页面插入到这个位置，然后把表针前移一个位置；如果访问位是1则把其置0，并把表针前移一个位置，重复这个过程直到找到一个访问位为0的页为止。了解了这个算法的工作方式，我们就知道这种算法为什么被称为Clock算法了。它与最久未使用置换算法的区别仅

18、仅是实现方法上的不同。 82 5 请求分页系统的性能分析请求分页系统的性能分析 请求分页式存储管理系统的性能优越，较好地解决了存储扩充问题。因此，它是目前最常用的存储管理方式。但进程在运行时所产生的缺页中断，会影响程序的运行速度及系统性能。而缺页率的高低又与分配给进程的物理块数直接相关。因此，本节所要介绍的主要内容，是分析缺页率对系统性能的影响程度，以及应为每个进程分配多少物理块数目，才能把缺页率保持在一个合理的水平上。82 5 请求分页系统的性能分析请求分页系统的性能分析 n缺页率对有效访问时间的影响缺页率对有效访问时间的影响 ：u有效访问时间：有效访问时间：设p为缺页率，t为存储器访问时间

19、，则有效访问时间为： 有效访问时间=（1p）t+p缺页中断时间u缺页中断时间的组成：缺页中断时间的组成：缺页中断时间主要由三部分组成：p缺页中断服务时间； p将所缺的页读入的时间； p进程重新执行时间。82 5 请求分页系统的性能分析请求分页系统的性能分析 u缺页中断率对访问时间的影响：其中缺页中断服务时间和进程重新执行时间之和可以不超过1ms,而将一磁盘块读入内存的时间大概是24ms。所以缺页中断时间约为25ms。如果存储器的平均访问时间为100 ns，于是可得： 有效访问时间=（1p） 0.1+p25000 =0.1+24999.9p 如果希望在缺页时，仅使有效访问时间延长不超过10%，则

20、可计算出缺页率p 0.1(1+10%)0.1+24999.9p 即0000004. 09 .2499901. 0p83 1 请求分段存储管理的基本概念请求分段存储管理的基本概念 n基本原理：基本原理：在请求分段式存储管理系统中，进程运行之前一部分段装入内存，另外一部分段则装入外存。在进程运行过程中，如果所访问的段不在内存中，则发生缺段中断，进入操作系统，由操作系统进行段的动态调度。n段表机制：段表机制：请求分段的段表是在纯分段的段表机制的基础上形成的。需在段表中增加若干项，供程序在换进换出时参考。下面所示是一请求分段系统中的段表：段名段长 段基址 存取方式 访问字段 修改位 存在位 增补位 外

21、存地址p存取方式：存取方式：用于标识本段的存取属性，存取属性包括只执行、只读还是读/写；83 1 请求分段存储管理的基本概念请求分段存储管理的基本概念 p存取方式：存取方式：用于标识本段的存取属性，存取属性包括只执行、只读还是读/写；p访问字段：访问字段：用于记录该段在一段时间内被访问的次数，或最近已有多长时间未被访问，供置换算法选择段时参考；p修改位：修改位：表示该段在调入内存后是否被修改过。由于内存中的每一段都在外存上保留一个副本，因此，若未被修改，在置换该段时就不需将该段写回到磁盘上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该段重写回磁盘上，以保证磁盘上所保留的始终是最新副

22、本；83 1 请求分段存储管理的基本概念请求分段存储管理的基本概念 p存在位：存在位：说明本段是否已调入内存；p增补位：增补位：用于表示本段在运行过程中，是否进行过动态增长；p外存地址：外存地址：用于指出该段在外存上的起始地址，通常是起始物理块号，供调入该段时使用。83 1 请求分段存储管理的基本概念请求分段存储管理的基本概念 n地址变换机构：地址变换机构：请求分段系统中的地址变换机构，是在分段系统的地址变换机构的基础上形成的。由于被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存时，必须先将所缺的段调入内存，在修改了段表之后，才能利用段表进行地址变换。下图给出了请求分段系统

23、的地址变换过程。83 2 分段共享与保护分段共享与保护 n分段共享：分段共享：在系统中配置一张共享段表，所有共享段都在共享段表中占有一个表项。共享段表除具有段表中的表项外，还记录有共享此段的每个进程的情况，其中包括：u共享进程数共享进程数count：记录共享该段的进程数，只有当count为0时，才由系统回收该段所占存储区；u存取控制字段：存取控制字段：记录不同进程的不同存取权限。如对于拥有该段的进程，则允许读和写，而对于其它进程，则可能只允许读，或者只允许执行。 842 Linux的页表机制的页表机制n页表：页表：在Linux系统中，页的大小为4KB，因此每个进程的虚存空间要有1M个页面。如果

24、采用一级页表描述这种映射关系，每个进程的页表就要有1M个表项。显然，用大量的内存资源来存放页表的方法是不可取的，所以，Linux采用三级页表的方式。u页目录（页目录（PGD）：）：第一级页表为页目录，每个活动进程有一个页目录。页目录的大小为一页的尺寸，页目录的每一项指向页中间目录中的一页。每个活动进程的页目录都必须在内存中。u页中间目录（页中间目录（PMD）：）：第二级页表为页中间目录。页中间目录可以有多个页，页中间目录的每一项指向页表中的一页。u页表（页表（PT）：）：第三级目录为页表。页表也可以有多个页，页表中的每一项指向该进程的一个虚拟页。 842 Linux的页表机制的页表机制u把虚拟

25、地址中的最高位段与寄存器中的PGD基地址相加，在PGD中找到相应的表项，该表项指向相应的PMD基地址；u把虚拟地址中的第二个位段与PMD的基地址相加，在PMD中找到相应的表项，该表项指向相应的PT基地址；u把虚拟地址中的第三个位段与PT的基地址相加，在PT中找到相应的表项，该表项指向相应的物理页面；u把虚拟地址中的最低位段与物理页面的基地址相加，得到相应的物理地址。843 Linux内存页的分配内存页的分配 为了提高往内存中读入页和从内存中写出页的效率，Linux采用了一种机制，即把连续的页映射到连续的物理块中。基于这个目的，它采用了一种伙伴系统。内核维护一系列大小固定的连续物理块组，一组可以

26、包含1、2、4、8、16或32个物理块。当一页在内存中被分配或被释放时，可用的组使用伙伴算法被分割或合并。844 Linux内存页的置换算法内存页的置换算法 Linux的页面置换算法采用最近最少使用置换算法（NRU）。在简单的最近最少使用置换算法中，内存中的每一页都有一个访问位和一个修改位。在Linux系统中，用一个8位的age变量取代了访问位。每当一页被访问时，age变量增1。在后台，Linux周期性地扫描全局页池，并将所有大于0的age变量减1。Age的值为0的页在较长一段时间内未被访问过，是用于置换的最佳候选页。age的值越大，该页最近被使用的频率越高，从而越不适合于被置换。85 Windows存储管理存储管理 Windows有一个非常成功的虚拟存储系统。有大量的Win32函数和六个内核线程在进行存储管理。它采用的是