虚拟存储管理

虚拟存储管理第一页，共八十一页，编辑于2023年，星期一引言

上一章介绍了实存储管理技术，各种实存储管理技术有一个共同的特点，即它们都要求把进程全部装入内存才能运行。在运行过程中，往往可能出现两种情况：要求运行的进程所需的内存空间之和大于系统的内存空间，只能有部分进程能够装入内存运行，而其它进程只有留在外存中等待；逻辑地址空间大于存储空间的进程无法在系统中运行。为了解决以上问题，可有两种解决方案：一是从物理上增加内存容量。但这受到机器寻址能力的限制，不能无限扩充，而且无疑会增加系统成本；二是从逻辑上扩充内存容量，这就是本章所要讨论的“虚拟存储”管理技术。第二页，共八十一页，编辑于2023年，星期一8．1虚拟存储器的基本概念

虚拟存储管理要研究的问题是：

1.作业信息不全部装入主存，能否保证作业的正确运行？回答是肯定的,1968年P.Denning研究了程序执行时的局部性原理。

2.以CPU时间和外存空间换取昂贵内存空间，如何进行动态调度？第三页，共八十一页，编辑于2023年，星期一8．1虚拟存储器的基本概念程序的局部性原理：

指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中。具体地表现为时间局部性和空间局部性。第四页，共八十一页，编辑于2023年，星期一8．1．1局部性原理

程序执行呈现局部性规律的原因：程序执行时，大多数情况下是顺序执行的。很少出现连续的过程调用，相反，程序中过程调用的深度限制在小范围内，一段时间内，指令引用被局限在很少几个过程中。程序中有许多循环语句，这些语句会重复多次执行。程序中对数据结构的操作，往往局限在很小的范围内。第五页，共八十一页，编辑于2023年，星期一8．1．1局部性原理

局部性原理的表现形式：时间局限性：如果某条指令被执行，则在不久的将来，该指令可能被再次执行；如果某个数据结构被访问，则在不久的将来，该数据结构可能再次被访问。产生时间局限性的主要原因是程序中存在着大量的循环操作。空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也可能被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围内。产生空间局限性的主要原因是程序的顺序执行。实现虚拟存储器的理论基础：局部性原理。第六页，共八十一页，编辑于2023年，星期一8．1．2虚拟存储器

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

虚拟存储器的定义：是指仅把进程的一部分装入内存便可运行的存储器系统，它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储器的逻辑容量：虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决定。

第八页，共八十一页，编辑于2023年，星期一8．1．2虚拟存储器虚拟存储管理主要采用以下技术实现：

•请求分页虚拟存储管理

•请求分段虚拟存储管理

•请求段页式虚拟存储管理第九页，共八十一页，编辑于2023年，星期一8．2请求分页式存储管理方式

请求分页式存储管理是在分页式存储管理的基础上，增加了请求调页功能、页面置换功能而形成的页式虚拟存储系统。它是目前常用的一种虚拟存储器的方式。第十页，共八十一页，编辑于2023年，星期一8．2请求分页式存储管理方式基本原理：在请求分页式存储管理系统中，进程运行之前将一部分页面装入内存，另外一部分页面则装入外存。在进程运行过程中，如果所访问的页面不在内存中，则发生缺页中断，进入操作系统，由操作系统进行页面的动态调度。系统需要解决下面三个问题：系统如何获知进程当前所需页面不在主存。当发现缺页时，如何把所缺页面调入主存。当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。第十一页，共八十一页，编辑于2023年，星期一8．2．1请求分页式存储管理的基本概念

其方法如下：找到被访问页面在外存中的地址；在内存中找一个空闲块，如果没有，则按照淘汰算法选择一个内存块，将此块内容写回外存，修改页表；读入所需的页面，修改页表；重新启动进程，执行被中断的指令。

第十二页，共八十一页，编辑于2023年，星期一8．2．1请求分页式存储管理的基本概念

页表机制：纯分页的页表只有两项：页号和物理块。而请求分页存储管理增加了调入功能和置换功能，故需在页表中增加若干项，供程序在换进换出时参考。下面所示是一请求分页系统中的页表：页号物理块号状态位P访问字段A修改位M外存地址状态位P：记录该页是否在内存。P=0该页在内存；

P=1该页不在内存。访问字段A：记录该页多长时间没有被访问。修改位M：记录该页在内存期间是否被修改过。

M=1该页调入内存后被修改过；

M=0该页调入内存后未被修改过。外存地址：该页在外存上的地址第十三页，共八十一页，编辑于2023年，星期一8．2．1请求分页式存储管理的基本概念

请求分页存储管理示意图：物理地址空间页面映射表存储空间页号块号状态作业10110430001作业20123作业30123410610329011011103212700412345678910111213第十四页，共八十一页，编辑于2023年，星期一8．2．1请求分页式存储管理的基本概念

地址变换机构：请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，为实现虚拟存储器而增加了产生和处理缺页中断、页面置换等功能而形成的。下图给出了请求分页系统的地址变换过程。第十五页，共八十一页，编辑于2023年，星期一8．2．1请求分页式存储管理的基本概念

否否否是是产生缺页中断否是否是程序请求访问一页页号>页表长度？越界中断CPU检索快表页表项是否在快表中？访问页表页是否在内存中？修改快表修改访问位和修改位保留CPU现场缺页中断处理从外存中找到该页内存满否？选择一页换出该页修改否？将该页写回外存CPU从外存读缺页启动I/O硬件形成物理地址地址变换结束将一页从外存换入内存修改页表是第十六页，共八十一页，编辑于2023年，星期一查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无第十七页，共八十一页，编辑于2023年，星期一8．2．2页面分配策略

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

第十八页，共八十一页，编辑于2023年，星期一8．2．2页面分配策略

外存块的分配策略：静态分配：一个进程在运行前，将其所有页面全部装入外存。当某一外存页面被调入内存时，所占用外存页面并不释放。这样，当该页面以后被淘汰时，如果它在内存中未被修改过，则不必写回外存，因为外存中有一个和它完全相同的副本，这可以减少因页面调度而引起的系统开销，代价是牺牲一定的外存空间。动态分配：一个进程在运行前，仅将未装入内存的那部分页面装入外存。当某一外存页面被调入内存，释放所占用的外存空间。这样，当该页面以后被淘汰时，不管它在内存中是否被修改过，都必须重新为其申请外存物理块，将该页重新写回外存。这种方法的优点是节省外存空间，但会增加由页面调度而引起的系统开销。第十九页，共八十一页，编辑于2023年，星期一8．2．3页面调入时机

请求调页策略：发生缺页时，调入内存。根据局部性原理,一段时间后,缺页中断会下降到很低水平,程序进入相对平稳阶段。

缺点：处理缺页中断和调页的系统开销较大，每次仅调一页,增加了磁盘I/O次数。预调页策略：预计要访问的页，提前调入内存。每次调入若干页面,而不是仅调一页。一次调入多页能减少磁盘I/O启动次数。缺点：如果调入的一批页面中多数未被使用,则效率就很低了，可见预调页要建立在预测的基础上第二十页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法目标：把未来不再使用的或短时间内不再使用的页调出。最佳置换算法OPT先进先出置换算法FIFO最近最久未使用置换算法LRU时钟置换算法第二十一页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

最佳置换算法（OPT，Optimal）：最佳置换算法置换那些以后永不再使用的或者在最长的时间以后才会用到的页面。显然，这种算法的缺页率最低。然而，该算法只是一种理论上的算法，因为很难估计哪一个页面是以后永远不再使用或在最长时间以后才会用到的页面，所以，这种算法是不能实现的。尽管如此，该算法仍然是有意义的，可以把它作为衡量其它算法优劣的一个标准。第二十二页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

【例8-1】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501501113333333322225555000004440000000000522222222221111111++++-+-+--+--+---+--缺页中断次数=9缺页中断率=9/20=45%

第二十三页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

先进先出置换算法（FIFO，First-InFirst-Out）

：先进先出置换算法总是置换最先进入内存的页面。该算法实现简单，只须把一个进程已调入内存的页面，按照进入内存的先后顺序排成一个队列，当一个页面由外存调入内存时排入队尾，需要淘汰时取队首的页面。第二十四页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

【例8-2】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先进先出置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501501223042300012225015011230423330111250500123042223000125++++-++++++--++--+++缺页中断次数=15缺页中断率=15/20=75%

第二十五页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

Belady异常现象：一般而言，分配给进程的物理块越多，运行时的缺页次数应该越少。但是Belady在1969年发现了一个反例，使用FIFO算法时，四个物理块时的缺页次数比三个物理块时的多，这种反常的现象称为Belady异常。如下面两表所示，一个进程有5个页面，页面访问序列如下：Belady异常现象（3个物理块的FIFO现象）

第二十六页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

Belady异常现象（4个物理块的FIFO现象）

由表中可见，3个物理块时缺页次数是9次，缺页中断率为9/12=75%；而4个物理块时的缺页次数是10次，缺页中断率为10/12≈83.3%。第二十七页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

最近最久未使用置换算法（LRU，LeastRecentlyUsed）：该算法的基本思想是：如果某一页面被访问了，那么它很可能马上又被访问；反之，如果某一页面很久没有被访问，那么最近也不会再次被访问。因此，该算法为每一个页面设置一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面予以淘汰。LRU的实现：记时法：系统为每一页面增设一个记时器。每当一个页面被访问时，当时的绝对时钟内容被拷贝到对应的记时器中，这样系统记录了内存所有页面最后一次被访问的时间。淘汰页面时，选取记时器中值最小的页面淘汰。第二十八页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

堆栈法：用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放最新被访问页面的页面号，而栈底放着最近最久未使用的页面号。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。注意：不是通常意义上的栈

第二十九页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

LRU的缺点：虽然LRU在理论上是可以实现的，但代价太高。为了实现LRU，需要在内存维持一个包含所有页的链表，最近使用的页面在表头，最近未使用的页面在表尾。而每次访问页面时都需要对链表进行更新。在链表中找到所需的页，将它移动到表头是一个非常费时的操作，即使使用硬件实现也是一样。

第三十页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

【例8-3】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501501203042303212015015012030423032120150501223042203312015++++-+-++++--+-+-+--缺页中断次数=12缺页中断率=12/20=60%

第三十一页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

Clock置换算法（最近未使用算法

(NRU)）：最近最久未使用置换算法是一种比较合理的算法，但它经常要在链表中移动页面，大大降低了系统效率。为了克服这个缺陷，把所有的页面保存在一个类似时钟表面的环形链表中，用一个表针指向可能淘汰的页面，如下图所示ABCDEFGHIJK设置一个访问位:0表示最近未使用

1表示最近使用过第三十二页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

当发生缺页时，该算法首先检查表针指向的页面，如果其访问位是0，则淘汰该页，并把新的页面插入到这个位置，然后把表针前移一个位置；如果访问位是1则把其置0，暂不换出，并把表针前移一个位置，重复这个过程直到找到一个访问位为0的页为止。了解了这个算法的工作方式，我们就知道这种算法为什么被称为Clock算法了。但因该算法只有一位访问位，只能用它表示该页是否使用过，而置换时将未使用过的页面换出去，故又把该算法称为最近未使用算法（NRU）。ABCDEFGHIJK第三十三页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法CLOCK算法执行过程第三十四页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

改进CLOCK置换算法事实上，时钟算法不但希望淘汰最近未访问的页，而且还希望被挑选的页在内存驻留期间，其页面内的数据未被修改过。淘汰该页时，由于该页未被修改过，因此不必写盘，从而减少了磁盘的I/O操作次数。为此，要为每页增设两个硬件位：访问位和修改位：第三十五页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

访问位A=0：该页尚未被访问过

=1：该页已经被访问过修改位M=0：该页尚未被修改过

=1：该页已经被修改过访问位和修改位的组合有以下四种：1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页；2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页；3类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再次被访问；4类（A=1，M=1）：最近已被访问且被修改，该页可能再次被访问。第三十六页，共八十一页，编辑于2023年，星期一8．2．4页面置换算法

改进CLOCK算法执行过程①从当前位置扫描循环队列，寻找<1>类页面,找到后立即置换

。②若步骤①失败，开始第二轮扫描，寻找<2>类页面找到后立即置换

。并将所经过的页面的访问位置0。③若步骤②也失败，重复步骤①，若仍失败，再重复步骤②。第三十七页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

请求分页式存储管理系统的性能优越，较好地解决了存储扩充问题。因此，它是目前最常用的存储管理方式。但进程在运行时所产生的缺页中断，会影响程序的运行速度及系统性能。而缺页率的高低又与分配给进程的物理块数直接相关。因此，本节所要介绍的主要内容是分析:

1.缺页率对系统性能的影响程度

2.为每个进程分配多少物理块数目，才能把缺页率保持在一个合理的水平上。第三十八页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

缺页率对有效访问时间的影响

：有效访问时间：设p为缺页率，t为存储器访问时间，则有效访问时间为：

有效访问时间=（1－p）×t+p×缺页中断时间缺页中断时间的组成：缺页中断时间主要由三部分组成：缺页中断服务时间；将所缺的页读入的时间；进程重新执行时间。第三十九页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

缺页中断率对访问时间的影响：其中缺页中断服务时间和进程重新执行时间之和可以不超过1ms,而将一磁盘块读入内存的时间大概是24ms。所以缺页中断时间约为25ms。如果存储器的平均访问时间为100ns，于是可得：有效访问时间=（1－p）×0.1+p×25000=0.1+24999.9p

如果希望在缺页时，仅使有效访问时间延长不超过10%，则可计算出缺页率p0.1×(1+10%)0.1+24999.9p即第四十页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

由此可知，要求在2500000次的访问中，才发生一次缺页，即请求分页式存储管理应保持非常低的缺页率，否则将使程序的执行速度受到严重影响。此外，提高磁盘I/O速度，对改善请求分页系统的性能至关重要。为此，应选用高速磁盘和高速磁盘接口。第四十一页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析例：现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页被修改过，则处理一个缺页中断需要20ms。内存存取时间为1s,访问页表的时间可以忽略不计。假设70%被替换的页被修改过，为保证有效存取时间不超过2s，则可接受的最大缺页率是多少？p*(0.7*20+0.3*8)+(1-p)*0.001<=0.002P<=1/163990.00006第四十二页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析“抖动”问题在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动原因：页面淘汰算法不合理分配给进程的物理页面数太少第四十三页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析驻留集

虚拟页式存储管理中给进程分配的物理块的集合；驻留集大小即是这个集合的元素个数驻留集大小与系统效率每个进程的驻留集越小，则同时驻留内存的进程就越多，CPU利用率越高进程的驻留集太小的话，则缺页率高，使调页的开销增大进程的驻留集大小达到一定数目之后，再给它分配更多页面，缺页率不再明显下降第四十四页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

拐点物理块数n缺页率第四十五页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

工作集：

1968年由Denning提出，引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整驻留集大小工作集定义：工作集就是进程在某段时间段Δ里实际要访问的页面的集合。第四十六页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析工作集（WorkingSet）模型

基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断抖动

进程要有效地运行，其工作集必须在内存中第四十七页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析

工作集：工作集就是进程在某段时间段Δ里实际要访问的页面的集合。具体地说，运行进程在时间t－Δ到t这个时间段内所访问的页面的集合称为该进程在时间t的工作集，记为，变量Δ称为工作集“窗口尺寸”（WindowsSize）。通常还把工作集中所包含的页面数称为“工作集尺寸”，记为例：

26157775162341234443434441327||t1||t2ws(t1,△)={1,2,5,6,7}ws(t2,△)={3,4}第四十八页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析△大小确定如果△过大，甚至把作业地址空间全包括在内，就成了实存管理;如果△过小，则会引起频繁缺页,降低了系统的效率。第四十九页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析工作集大小的变化

进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。第五十页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析利用工作集来进行驻留集调整的策略：记录一个进程的工作集变化定期删除驻留集中不在工作集中的页面总是让驻留集包含工作集（不能包含时则增大驻留集）第五十一页，共八十一页，编辑于2023年，星期一8．2．5请求分页系统的性能分析影响缺页次数的因素(1)分配给进程的物理块数 一个程序运行时遇到缺页中断的次数，是和分配给该道程序的物理块数成反比的，但当主存容量达到某个值时，缺页次数减少不再明显。多数程序都有一个确定值——拐点(2)页面本身的大小 页面大，页表小，省空间且查找快；缺页次数相对也少；一次换页的时间长，页内碎片空间浪费的可能性较大。页面小则相反.(3)页面置换算法(页面淘汰算法)

选择最合适的置换算法。(4)程序的编制方法 尽可能使编出的程序具有高度的局部性，则执行时可经常集中在几个页面上进行访问，减少缺页率.第五十二页，共八十一页，编辑于2023年，星期一8．3请求分段式存储管理方式

请求分段存储管理系统是在分段存储管理系统的基础上实现的虚拟存储器。它以段为单位进行换入换出。在程序运行之前不必调入所有的段，而只调入若干个段，便可启动运行。当所访问的段不在内存时可请求操作系统将所缺的段调入内存。为实现请求分段存储管理，与请求分页存储管理类似，需要硬件的支持和相应的软件。第五十三页，共八十一页，编辑于2023年，星期一8．3．1请求分段存储管理的基本概念

基本原理：在请求分段式存储管理系统中，进程运行之前一部分段装入内存，另外一部分段则装入外存。在进程运行过程中，如果所访问的段不在内存中，则发生缺段中断，进入操作系统，由操作系统进行段的动态调度。段表机制：请求分段的段表是在纯分段的段表机制的基础上形成的。需在段表中增加若干项，供程序在换进换出时参考。下面所示是一请求分段系统中的段表：段名段长段基址存取方式访问字段修改位存在位增补位外存地址第五十四页，共八十一页，编辑于2023年，星期一8．3．1请求分段存储管理的基本概念

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

存在位：说明本段是否已调入内存；增补位：用于表示本段在运行过程中，是否进行过动态增长；外存地址：用于指出该段在外存上的起始地址，通常是起始物理块号，供调入该段时使用。第五十六页，共八十一页，编辑于2023年，星期一8．3．1请求分段存储管理的基本概念

请求分段存储管理系统的示意图：200K存储空间030K90K150K(MAIN)=020K（X）=18K（S）=310K作业空间10K0（S）=312K0（D）=28K0（X）=120K0（MAIN）=0状态段表基址段长段号20K030K8K190K12K2150K10K3200K0010第五十七页，共八十一页，编辑于2023年，星期一8．3．1请求分段存储管理的基本概念

地址变换机构：请求分段系统中的地址变换机构，是在分段系统的地址变换机构的基础上形成的。由于被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存时，必须先将所缺的段调入内存，在修改了段表之后，才能利用段表进行地址变换。下图给出了请求分段系统的地址变换过程。第五十八页，共八十一页，编辑于2023年，星期一8．3．1请求分段存储管理的基本概念

是访问（s，w）w段表长？否越界中断处理符合存取方式？保护中断处理否是段s在主存？缺段中断处理否是修改访问字段，如果写访问，置修改位=1形成访问内存地址：（A）=内存始址+偏移量w返回第五十九页，共八十一页，编辑于2023年，星期一8．3．2分段共享与保护

分段共享：在系统中配置一张共享段表，所有共享段都在共享段表中占有一个表项。共享段表除具有段表中的表项外，还记录有共享此段的每个进程的情况，其中包括：共享进程数count：记录共享该段的进程数，只有当count为0时，才由系统回收该段所占存储区；存取控制字段：记录不同进程的不同存取权限。如对于拥有该段的进程，则允许读和写，而对于其它进程，则可能只允许读，或者只允许执行。段名段长段基址状态外存始址共享进程计数count状态进程名进程号段号存取控制……第六十页，共八十一页，编辑于2023年，星期一8．3．2分段共享与保护

分段保护：由于进程的每个段在逻辑上是独立的，因而比较容易实现信息保护。常用的分段保护方法有越界检查和存取控制检查等。越界检查：在进行存储访问时，首先将逻辑地址空间的段号与段表长度进行比较，如果段号等于或大于段表长度，将发出地址越界中断信号；其次，还要检查段内地址是否等于或大于段长，若是等于或大于段长，将产生地址越界中断信号，从而保证了每个进程只能在自己的地址空间内运行。存取控制检查：在段表的每个表项中，都设置了一个“存取控制”字段，用于规定该段的访问方式。通常有只读、只执行和读/写等三种。第六十一页，共八十一页，编辑于2023年，星期一练习：一个程序的段表如下表，其中存在位为0表示段在内存，存取控制字段中W表示可写，R表示可读，E表示可执行。对下面的5条指令，在执行时会产生什么样的结果？（0表示在内存中，1表示在外存）STORER1,[0,70]STORER1,[1,20]LOADR1,[3,20]LOADR1,[3,100]JMP[2,100]段号存在位内存始址段长存取控制01500100W10100030R203000200E30800080R41500040R缺段中断只读，保护性中断合法，形成物理地址8020，将该单元内容读入寄存器R1中越界中断合法，跳到3100处继续执行答：第六十二页，共八十一页，编辑于2023年，星期一8．4Linux存储管理

Linux操作系统采用虚拟存储管理机制，即置换和请求分页存储管理技术。尽管Linux的存储管理的基本原理与前面所论述的存储管理方法是相同的，但它也有自己独特的特点。总体而言，Linux的存储管理方案非常复杂。下面就其存储管理的主要特征进行简单的论述。第六十三页，共八十一页，编辑于2023年，星期一8．4．1Linux的内存空间在x86平台的Linux系统中，地址码采用32位，因此每个进程的虚存空间可以达到4GB。Linux内核将这4GB的空间分为两部分：最高地址的1GB是系统空间，供内核本身使用；而较低地址的3GB空间是用户空间。系统空间由所有进程共享，而用户空间理论上虽然可以达到3GB，但实际的用户空间要受到物理存储器（包括内存和磁盘的交换空间）和用户竞争存储器的限制。第六十四页，共八十一页，编辑于2023年，星期一8．4．2Linux的页表机制页表：在Linux系统中，页的大小为4KB，因此每个进程的虚存空间要有1M个页面。如果采用一级页表描述这种映射关系，每个进程的页表就要有1M个表项。显然，用大量的内存资源来存放页表的方法是不可取的，所以，Linux采用三级页表的方式。页目录（PGD）：第一级页表为页目录，每个活动进程有一个页目录。页目录的大小为一页的尺寸，页目录的每一项指向页中间目录中的一页。每个活动进程的页目录都必须在内存中。页中间目录（PMD）：第二级页表为页中间目录。页中间目录可以有多个页，页中间目录的每一项指向页表中的一页。页表（PT）：第三级目录为页表。页表也可以有多个页，页表中的每一项指向该进程的一个虚拟页。

第六十五页，共八十一页，编辑于2023年，星期一8．4．2Linux的页表机制页目录（PGD）：第一级页表为页目录，每个活动进程有一个页目录。页目录的大小为一页的尺寸，页目录的每一项指向页中间目录中的一页。每个活动进程的页目录都必须在内存中。页中间目录（PMD）：第二级页表为页中间目录。页中间目录可以有多个页，页中间目录的每一项指向页表中的一页。第六十六页，共八十一页，编辑于2023年，星期一8．4．2Linux的页表机制地址转换：Linux虚拟内存的地址转换分为四步，如下图所示：PMD寄存器PGD下标PMD下标PT下标页内偏移量虚拟地址PGD……PT…物理页面…PGD基地址++++第六十七页，共八十一页，编辑于2023年，星期一8．4．2Linux的页表机制把虚拟地址中的最高位段与寄存器中的PGD基地址相加，在PGD中找到相应的表项，该表项指向相应的PMD基地址；把虚拟地址中的第二个位段与PMD的基地址相加，在PMD中找到相应的表项，该表项指向相应的PT基地址；把虚拟地址中的第三个位段与PT的基地址相加，在PT中找到相应的表项，该表项指向相应的物理页面；把虚拟地址中的最低位段与物理页面的基地址相加，得到相应的物理地址。第六十八页，共八十一页，编辑于2023年，星期一8．4．3Linux内存页的分配为了提高往内存中读入页和从内存中写出页的效率，Linux采用了一种机制，即把连续的页映射到连续的物理块中。基于这个目的，它采用了一种伙伴系统。内核维护一系列大小固定的连续物理块组，一组可以包含1、2、4、8、16或32个物理块。当一页在内存中被分配或被释放时，可用的组使用伙伴算法被分割或合并。第六十九页，共八十一页，编辑于2023年，星期一8．4．4Linux内存页的置换算法

Linux的页面置换算法采用最近最少使用置换算法（NRU）。在简单的最近最少使用置换算法中，内存中的每一页都有一个访问位和一个修改位。在Linux系统中，用一个8位的age变量取代了访问位。每当一页被访问时，age变量增1。在后台，Linux周期性地扫描全局页池，并将所有大于0的age变量减1。age的值为0的页在较长一段时间内未被访问过，是用于置换的最佳候选页。age的值越大，该页最近被使用的频率越高，从而越不适合于被置换。第七十页，共八十一页，编辑于2023年，星期一8．5Windows存储管理

Windows有一个非常成功的虚拟存储系统。有大量的Win32函数和六个内核线程在进行存储管理。它采用的是页式虚拟存储管理。第七十一页，共八十一页，编辑于2023年，星期一8．5．1Windows的虚拟地址空间在Windows中，每一个用户进程都有自己的虚拟地址空间。虚拟地址的长度是32位，因此每个进程有4GB（232B）的虚拟地址空间。低2GB为用户地址空间，用于进程代码和数据；高2GB为核心地址空间，它处于保护模式。其中的用户地址空间可被用户态和核心态线程存取，并且对每个进程都是不同的；而核心地址空间只能被核心态线程存取，并且对每个线程都是相同的。这两个地址空间的布局如图12．6所示。虚拟地址空间采用分页存储管理，每一页的大小是固定的（Pentium是4KB）。第七十二页，共八十一页，编辑于2023年，星期一8．5．1Windows的虚拟地址空间2GB04GB非页池页池用户页表栈、数据等HAL+操作系统用户地址空间第七十三页，共八十一页，编辑于2023年，星期一8．5．2页面状态