操作系统原理课件第三章 存储管理3

3.5虚拟存储管理技术简单存储：要求将一个进程所需的程序和数据全部装入内存方可执行。这样的系统存在两个很严重的问题。—其一，对于大进程，如果其所需内存空间超过了内存的最大容量，则无法运行。—其二，对于多道程序系统，由于每一个进程需要全部装入内存，使同时驻留内存的进程数量受到限制。虽然也可以通过提高内存容量来解决，但是代价太高。如果能将一部分价格较低的外存空间当作内存使用，从逻辑上扩充内存容量。那么，将获得更高的性价比。虚拟存储技术的理论依据

程序执行的局部性原理：程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。实现虚拟存储的一般过程

进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁盘上。进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；如果其所需要访问的页面（段）尚未装入内存，则发生缺页（段）中断，进程阻塞。此时，系统将启动请求调页（段）功能，将进程所需的页（段）装入内存。实现虚拟存储的一般过程

如果当前内存已满，无法装入新的页（段），则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与调度执行。从外存装入页/段更新页/段表交换页/段内存满？是否缺页/段中断页/段在内存是否进程执行图3.28实现虚拟存储的典型过程？什么是虚拟存储通过系统提供的缺页/段中断功能和交换技术，动态装入进程的程序代码和数据，使得一个大的用户程序能在一个相对较小的内存空间中运行，也使得有限的内存能同时容纳更多的进程。习惯上，人们把这种用户感觉上的、由实际内存和部分外存共同构成的存储空间称为虚拟存储器虚拟存储技术的技术支持

首先，必须有相应的硬件支持，用以实现虚拟分页或虚拟分段存储管理。其次，操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。虚拟存储的基本数据结构

由于虚拟存储系统中，进程的程序代码和数据只有一部分在内存，另一部分保存在外存。在页/段表项中增加一个“存在”字段，其值为0或1。增加一个“修改”字段，表明对应页/段自进入内存以来是否被修改过。只有被修改过的页/段才需要保存到外存，若需要将未修改过的页/段换出内存，只需要将新装入的页/段直接覆盖其存储区域，而不必将其内容保存到外存。

图3.29虚拟分页、分段及段页式存储系统的数据结构页号页框号存在修改其他控制(a)虚拟存储页表项段号段长存在修改其他控制(b)虚拟存储段表项段基址长(c)虚拟存储段页式系统的段表项和页表项段号其他控制页表长度页表基址段表项页号页框号存在修改其他控制页表项虚拟存储的好处第一，可以运行大程序，包括超过内存实际容量的大程序。第二，可以在有限的物理内存中运行更多的程序。多道程序系统的度不再受到物理内存空间的限制。虚拟存储的典型问题

抖动（thrashing）当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。如果系统花费大量的时间把程序和数据频繁地装入和移出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。根本原因：选择的页面或段不恰当。虚拟存储分页技术

建立在简单分页存储管理系统之上，是目前常用的一种虚拟存储管理技术。地址变换基于简单存储分页系统增加了某些功能，如产生和处理缺页中断，以及从内存中换出页面等。进程执行时，首先通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。若快表中不存在该页表项，则再查找页表。检查对应的页面是否在内存中存在。若该页面不在内存，启动缺页中断处理例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将对应的页表项插入快表中，更新快表。若快表中存在该表项，则直接取出其中的页框号，加上页内偏移量，计算出物理地址。访问页表图3.30虚拟存储分页系统地址变换过程物理地址页框号偏移量更新快表页号偏移量逻辑地址检索快表是否是否换出页面处理机处理中断是否处理机从外存取该页将该页装入内存更新页表缺页中断处理？命中？内存满？页在内存缺页中断处理过程（1）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；（2）操作系统通知处理机从外存读取指定的页面；（3）处理机激活I/O设备；（4）检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；（5）利用页面置换算法，选择内存中的某个页面，换出内存；（6）将指定页面从外存装入内存；（7）更新该进程的页表；（8）更新快表；（9）计算物理地址。虚拟存储分段技术

建立在简单存储分段系统基础上，利用动态分区技术分配存储空间，并以段作为交换的单位。进程执行之前，系统为之分配几个必要的内存分区，每一个分区中装入一段。当进程执行过程中，出现缺段中断时，操作系统将为进程装入需要的程序段。虚拟存储分段：数据结构

因此，需要修改段表，增加“存在”字段和“修改”字段，分别标明对应段是否存在于内存，以及内存中的段自装入以来是否被修改过。地址变换与存储保护在简单分段系统的地址变换机构基础上形成的。越界检查：可能产生一个地址越界中断，进入相应的中断处理例程执行。一般地，当地址越界中断处理完毕，该进程将异常结束。操作合法性检查：如果属于非法操作，产生非法访问中断，这时也会让进程异常终止。缺段处理：执行进程被阻塞。并产生一个中断信号，处理机执行缺段中断处理例程。图3.31虚拟存储分段系统地址变换过程物理地址段基址偏移量更新快表否非法访问中断是是否是越界中断处理访问段表段号偏移量逻辑地址检索快表否是缺段中断处理否更新段表？命中？段在内存？地址越界？合法访问图3.31虚拟存储分段系统中的缺段中断的处理过程换出一个或几个段形成一个合适空闲区返回修改段表、空闲分区表从外存读入段s唤醒进程是拼接外零头，形成一个合适的空闲区是段s不在内存阻塞执行进程内存中有合适的空闲区吗？否空闲区容量总和能否满足？否虚拟存储段页式技术

虚拟存储段页式系统中，程序和数据通常以页面为单位被系统装入和移出内存。因此，一般不需要在段表项中增加“存在”字段和“修改”字段，而将它们放在页表中。段表中需要保留基于段的保护与存储共享等目的的存取控制信息，页表中设置基于页的控制信息。

地址变换首先，通过根据段号和页号，查找快表中是否存在对应的页表项。若快表中不存在该页表项，则再查找段表。然后，检索段号对应的段表项，找到对应段的页表起始地址。再根据页号检索该页表，检查对应页面是否在内存。若该页面不在内存，启动缺页中断处理例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将对应的页表项插入快表中，更新快表。若快表中存在该表项，则直接取出其中的页框号，加上页内偏移量，计算出物理地址。图3.32虚拟存储分页系统地址变换过程更新页表缺页中断处理物理地址页框号偏移量更新快表是否访问段表访问页表检索快表段号页内偏移量逻辑地址段内页号否是？命中？页在内存虚拟存储系统的软件策略现代操作系统几乎都采用虚拟存储管理系统一些特殊的操作系统和一些较老的操作系统没有采用虚拟存储技术。例如，MSDOS和早期的UNIX操作系统等。大多采用分段与分页相结合的段页式管理系统。下面以分页存储管理为例，介绍虚拟存储系统采用的软件策略。虚拟存储系统的软件策略驻留集管理(ResidentSetManagement)放置策略(PlacementPolicy)获取策略(FetchPolicy)置换策略(ReplacementPolicy)清除策略(CleaningPolicy)负载控制(LoadControl)驻留集管理

进程的驻留集指，虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分到的物理页框集合。驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。影响页框分配的主要因素

分配给每个活跃进程的页框数越少，同时驻留内存的活跃进程数就越多，进程调度程序能调度就绪进程的概率就越大。然而，这将导致进程发生缺页中断的概率较大；为进程分配过多的页框，并不能显著地降低其缺页中断率。

基本的驻留集管理策略

固定分配策略(Fixed-AllocationPolicy)可变分配策略(Variable-AllocationPolicy)固定分配策略为每个进程分配固定数量的页框。即，每个活跃进程的驻留集尺寸在运行期间固定不变。为进程分配多少个页框是合理的呢？—可以由系统根据进程的类型确定，也可以由编程人员或系统管理员指定。可变分配策略为每个活跃进程分配的页框数在进程的生命周期内是可变的。即，系统可以首先给进程分配一定数量的页框。进程运行期间，可以增加或减少页框。系统可以根据进程的缺页率调整进程的驻留集。—当进程的缺页率很高时，驻留集太小，需要增加页框；—当缺页率一段时间内都保持很低时，可以在不会明显增加进程缺页率的前提下，回收其一部分页框，减小进程的驻留集。可变分配vs.固定分配可变分配策略比固定分配策略更灵活，既可以提高系统的吞吐量，又能保证内存的有效利用。可变分配要求统计进程的缺页率，增加系统额外开销。而准确判断进程缺页率的高低，确定缺页率的阈值是非常困难的。可变分配策略不仅需要操作系统软件专门的支持，而且，还需要处理机平台提供的硬件支持页面放置策略解决的问题：系统应当在内存的什么位置为活跃进程分配页框？一般地，对于一个分页系统或段页式系统，将进程的一个页面装入哪一个页框无关紧要。对于分段系统，需要考虑将一个程序段装入哪一个合适的分区中，可采用的分配算法包括首次适应法、下次适应法、最佳适应法或最差适应法等。页面获取策略解决的问题：系统应当在何时把一个页面装入内存？请求调页(DemandPaging)预调页(Prepaging)请求调页仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。采用请求调页方式，一次装入请求的一个页面，磁盘I/O的启动频率较高，系统的开销较大。预调页方式当进程创建时，预先为进程装入多个页面。缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率页面置换策略

当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。应该解决的基本问题：—当系统欲把一个页面装入内存时，应当在什么范围内判断已经没有空闲页框供分配？—当指定的范围内没有空闲页框时，应当从指定的范围内选择哪个页面移出内存？局部置换策略可以采用局部置换或全局置换策略。局部置换：系统在进程自身的驻留集中判断当前是否存在空闲页框，并在其中进行置换。全局置换策略在整个内存空间内判断有无空闲页框，并允许从其它进程的驻留集中选择一个页面换出内存。分配模式vs.

置换模式固定分配策略局部置换策略全局置换策略可变分配策略可变分配策略+局部置换策略—即可增加或减少分配给每个活跃进程的页框数；当进程的页框全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集中选择一个页面换出内存。

页面置换策略页面置换算法：在指定的置换范围内，决定将哪一个页面换出内存。置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。常用的页面置换算法：最佳置换算法、最近最少使用算法、先进先出算法和时钟算法等最佳置换算法

(OptimalAlgorithm，OPT)

基本思想：被置换的页面是将来不再访问，或在最远的将来才被访问的页面。若采用固定分配策略，最佳置换算法可以保证系统的缺页率最低。但是，无法预知一个进程在内存的若干页面中，哪一个页面是将来不再访问的，甚至最长时间内将不再被访问的，因而该算法是无法实现的。该算法可以用于评价其它置换算法的性能。示例假设系统分配给某进程3个页框，且进程开始运行时，这3个页框是空的。考虑下列页面号引用序列：2、3、2、1、5、2、4、5、3、2、5、222323231235235435435435235235235页面引用序列232152453252

FF

FF

F

F

12次页面引用6次缺页中断（F和F）3次页面置换（F）图3.33采用OPT置换算法的缺页中断与页面置换过程据局部性原理，如果一个页面最近被访问过，那么，它将在不久的将来再次被访问。如果一个页面已经很长时间未被访问过，则在很久的将来，它将不会被访问。因此，可以根据页面的使用历史，判断其将来的行为。最近最少使用置换算法

(LeastRecentlyUsedAlgorithm，LRU)LRU根据页面装入内存以后的使用情况，选择淘汰最近最久未被使用的一个页面。该算法的性能接近OPT算法，但实现较困难。一种方法：为每一个页面增加一个访问字段，用以标注该页最后一次被访问的时间。需要选择淘汰页面时，比较置换范围内的所有页面的最后访问时间，选择访问时间最远的哪个页面。实现该方法的开销非常大，不易实现。LRU置换算法的实现另一种方法：将访问页面组织在一个堆栈中，最近访问的页面位于栈顶，栈底的页面即是最久未被访问的。实践证明，该方法的实现仍然很困难，系统付出的代价也非常大。

22323231251251254254354352352352页面引用序列232152453252

FF

FF

F

F

F

12次页面引用7次缺页中断（F和F）4次页面置换（F）图3.34采用LRU置换算法的缺页中断与页面置换过程先进先出置换算法

(First-inFirst-outAlgorithm，FIFO)淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。实现时，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，使它总是指向最老的页面。22323231531521524524324324354352页面引用序列232152453252

FF

F

F

F

F

F

F

F12次页面引用9次缺页中断（F和F）6次页面置换（F）图3.35采用FIFO置换算法的缺页中断与页面置换过程先进先出置换算法

(First-inFirst-outAlgorithm，FIFO)该算法与进程实际的运行规律不相适应，进程中的某些程序代码或数据可能需要高频使用，该算法将导致这种类型的页面被反复地换进换出，从而降低系统性能。Clock时钟置换算法内存中的每个页面配置一个使用位（U位）；当页面装入内存时，或被引用时，其U位将被设置为1；系统将置换范围内的所有页面组成一个循环队列，并为其设置一个扫描指针；未进行页面置换时，扫描指针总是指向上一次进行页面置换时被置换页面所在位置的下一个位置。时钟置换算法（续）当需要进行页面置换时，系统将移动扫描指针，搜索置换范围内的各个页面，以便找到一个U位为0的页面：如果当前扫描指针所指向的页面的U位为1，那么系统将把该页面的U位设置为0，同时把扫描指针移到下一个位置，继续搜索；如果当前扫描指针所指向的页面的U位为0，那么系统将把该页面作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。页6U=1页123U=1页30U=0页616U=0页77U=1页24U=1页110U=1页16U=0页76U=0...01234567n-1(b)用77号页面替换23号页面以后的情况页6U=1页123U=1页30U=1页616U=1页23U=0页24U=1页110U=1页16U=0页76U=0...01234567n-1(a)当前页面循环队列情况2*2*3*2*3*2*3*1*5*315*2*15*2*4*5*2*4*3*243*2*43*25*3*2*5*页面引用序列232152453252FF

F

F

F

F

F

F12次页面引用8次缺页中断（F和F）5次页面置换（F）图3.37采用Clock置换算法的缺页中断与页面置换过程时钟置换算法的改进系统把一个页面移出内存时，如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则系统必须把它写回辅存。这表明，换出未修改过的页面比换出被修改过的页面开销小。显然，我们可以依据上述结论改进CLOCK算法。改进后的CLOCK算法将在置换范围内首选在最近没有被使用过、在驻留内存期间没有被修改过的页面作为被置换页面。时钟置换算法的改进(续1)为了改进CLOCK算法，系统将为内存的每个页面配置一个修改位（简称为M位）。改进后的CLOCK算法在置换范围内选择被置换页面时将同时考虑U位和M位。一个页面的U位与M位共有四种组合：U=0，M=0：最近没有被使用过，驻留内存期间也没有被修改过；U=1，M=0：最近被使用过，但驻留内存期间没有被修改过；U=0，M=1：最近没有被使用过，但驻留内存期间被修改过；U=1，M=1：最近被使用过，驻留内存期间也被修改过；时钟置换算法的改进(续2)改进后的CLOCK算法将按下列步骤选择被置换页面：1、从扫描指针的当前位置开始，搜索U=0且M=0

的页面。此次搜索不会修改置换范围内的任何一个页面的U位。若找到第一个U=0且M=0的页面，则把该页面选作被置换页面，终止算法。2、如果第一步没有成功，那么扫描指针将回到原位。再次搜索U=0但M=1的页面。如果遇到U位为1的页面，将其U位修改为0。倘若找到第一个U=0但M=1的页面，将该页面选作被置换页面，终止算法。3、如果第二步也没有成功，那么扫描指针将再次回到原位，且置换范围内的所有页面的U位均为0。此时，算法将返回第一步继续执行。页10U=1M=0页565U=1M=1页20U=1M=0页16U=1M=1页19U=0M=0页566U=1M=0页110

U=1M=1页111U=0M=1页112U=0M=1...01234567n-1图3.38改进型clock算法：页面置换之前的情形页面清除策略

页面清除是指，将由页面置换算法选择的被修改的置换页面保存到外存。页面清除策略需要决定系统何时把一个被置换页面写回外存。最直接的页面清除时机是，只有当一个页被选中作为置换页时，才被写回外存，称之为请求清除策略。若被选中的置换页面自进入内存以来被修改过，则需要首先将该页面内容写回外存保存起来，然后，装入进程需要的新页内容。可见，采用请求清除策略时，写出一个被修改过的页面与读入一个新页的操作是成对出现的，而且，写出操作先于读入操作。所以，当正在执行的进程发生缺页中断时，需要阻塞等待一个页面的写出和另一个页面的读入，这可能降低处理机的使用效率。一种有效的页面清除策略是结合页缓冲（PageBuffering）技术。当发生缺页中断时，不必首先写出置换页，然后读入新页。而是，将被选中的置换页暂时保留在内存的一个缓冲区，在以后某个合适的时候将这些被置换页批量写出到外存。减少磁盘I/O的次数，提高处理机的效率。页缓冲技术的实现需要两个链表：未修改页链表和修改页链表。当选中一个被修改过的页作为置换页时，不需要立即、真正地将其写出到外存，而是首先将其插入到修改链表中缓冲存储。修改链表中的页可以周期性地批量写出到外存，并移到未修改表中。未修改表链接被选中的未修改置换页，当其中某页所占用的页框被新页占用时，新页的内容覆盖置换页的内容，置换页被真正从内存清除。采用页缓冲技术，当需要读入一个新页时，首先检查未修改页链表，若该表非空，便可按照FIFO方法，将该链表头指向的第一个页面占用的页框分配给新页。如果未修改表为空，检查修改页链表，将该表中的页面内容批量写出到外存，并将这些页移到未修改表中，按照上述方法重新分配其占用的页框。显然，采用页缓冲技术不仅可以减少写出页面的系统开销，而且可以减少读入页面的开销。因为，当进程再次访问页面缓冲区的页面时，只需要将对应