操作系统chapter4存储器管理.pptx

第四章第四章 存储器管理存储器管理 4.1 4.1 存储器的层次结构存储器的层次结构4.24.2 程序的装入和链接程序的装入和链接 4.34.3 连续分配方式连续分配方式 4.44.4 基本分页存储管理方式基本分页存储管理方式 4.54.5 基本分段存储管理方式基本分段存储管理方式 4.64.6 虚拟存储器的基本概念虚拟存储器的基本概念 4.74.7 请求分页存储管理方式请求分页存储管理方式 4.84.8 页面置换算法页面置换算法 4.9 4.9 请求分段存储管理方式请求分段存储管理方式 4.1程序的装入和链接程序的装入和链接图 4-1 对用户程序的处理步骤 4.1.1程序的装入程序的装入1.绝对装入方式绝对装入方式(AbsoluteLoadingMode)程程序序中中所所使使用用的的绝绝对对地地址址，既既可可在在编编译译或或汇汇编编时时给给出出，也也可可由由程程序序员员直直接接赋赋予予。但但在在由由程程序序员员直直接接给给出出绝绝对对地地址址时时，不不仅仅要要求求程程序序员员熟熟悉悉内内存存的的使使用用情情况况，而而且且一一旦旦程程序序或或数数据据被被修修改改后后，可可能能要要改改变变程程序序中中的的所所有有地地址址。因因此此，通通常常是是宁宁可可在在程程序序中中采采用用符符号号地地址址，然然后后在在编编译译或或汇汇编编时时，再将这些符号地址转换为绝对地址。再将这些符号地址转换为绝对地址。2.可重定位装入方式可重定位装入方式(RelocationLoadingMode)图 4-2 作业装入内存时的情况 3.动态运行时装入方式动态运行时装入方式(DenamleRun-timeLoading)动动态态运运行行时时的的装装入入程程序序，在在把把装装入入模模块块装装入入内内存存后后，并并不不立立即即把把装装入入模模块块中中的的相相对对地地址址转转换换为为绝绝对对地地址址，而而是是把把这这种种地地址址转转换换推推迟迟到到程程序序真真正正要要执执行行时时才才进进行行。因因此，此，装入内存后的所有地址都仍是相对地址。装入内存后的所有地址都仍是相对地址。4.1.2程序的链接程序的链接1.静态链接方式静态链接方式(StaticLinking)图 4-3 程序链接示意图 静静态态链链接接将将目目标标模模块块装装配配成成一一个个装装入入模模块块时时，须须解解决以下两个问题：决以下两个问题：(1)对相对地址进行修改。对相对地址进行修改。(2)变换外部调用符号。变换外部调用符号。2.装入时装入时动态链接动态链接(Loadtime Dynamic Linking)优点：优点：（1）便于修改和更新。便于修改和更新。(2)便于实现对目标模块的共享。便于实现对目标模块的共享。3.运行时动态链接运行时动态链接(Run-timeDynamicLinking)近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4.2连续分配方式连续分配方式4.2.1单一连续分配单一连续分配这这是是最最简简单单的的一一种种存存储储管管理理方方式式，但但只只能能用用于于单单用用户户、单单任任务务的的操操作作系系统统中中。采采用用这这种种存存储储管管理理方方式式时时，可可把把内内存存分分为为系系统统区区和和用用户户区区两两部部分分，系系统统区区仅仅提提供供给给OS使使用用，通通常常是是放放在在内内存存的的低低址址部部分分；用用户户区区是是指指除除系系统统区区以以外外的的全部内存空间，全部内存空间，提供给用户使用。提供给用户使用。4.2.2固定分区分配固定分区分配1.划分分区的方法划分分区的方法(1)分区大小相等，即使所有的内存分区大小相等。(2)分区大小不等。2.内存分配内存分配图 4-5 固定分区使用表 4.2.3动态分区分配动态分区分配1.分区分配中的数据结构分区分配中的数据结构(1)空闲分区表。空闲分区表。(2)空闲分区链。空闲分区链。图图4-6空闲链结构空闲链结构3.分区分配操作分区分配操作1)分配内存 图 4-7 内存分配流程2)回收内存 图 4-7 内存回收时的情况 4.3.4可重定位分区分配可重定位分区分配1.动态重定位的引入动态重定位的引入图 4-8 紧凑的示意 操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a)紧凑前(b)紧凑后2.动态重定位的实现动态重定位的实现图 4-10 动态重定位示意图 3.动态重定位分区分配算法动态重定位分区分配算法图 4-11 动态分区分配算法流程图 4.3.5对换对换(Swapping)1.对换的引入对换的引入所所谓谓“对对换换”，是是指指把把内内存存中中暂暂时时不不能能运运行行的的进进程程或或者者暂暂时时不不用用的的程程序序和和数数据据，调调出出到到外外存存上上，以以便便腾腾出出足足够够的的内内存存空空间间，再再把把已已具具备备运运行行条条件件的的进进程程或或进进程程所所需需要要的的程程序序和和数数据据，调调入入内内存存。对对换换是是提提高高内内存存利利用用率率的的有有效效措措施。施。2.对换空间的管理对换空间的管理为为了了能能对对对对换换区区中中的的空空闲闲盘盘块块进进行行管管理理，在在系系统统中中应应配配置置相相应应的的数数据据结结构构，以以记记录录外外存存的的使使用用情情况况。其其形形式式与与内内存存在在动动态态分分区区分分配配方方式式中中所所用用数数据据结结构构相相似似，即即同同样样可可以以用用空空闲闲分分区区表表或或空空闲闲分分区区链链。在在空空闲闲分分区区表表中中的的每每个个表表目目中中应应包包含含两两项项，即即对对换换区区的的首首址址及及其其大大小小，它它们们的的单单位位是盘块号和盘块数。是盘块号和盘块数。3.进程的换出与换入进程的换出与换入(1)进程的换出。进程的换出。每每当当一一进进程程由由于于创创建建子子进进程程而而需需要要更更多多的的内内存存空空间间，但但又又无无足足够够的的内内存存空空间间等等情情况况发发生生时时，系系统统应应将将某某进进程程换换出出。其其过过程程是是：系系统统首首先先选选择择处处于于阻阻塞塞状状态态且且优优先先级级最最低低的的进进程程作作为为换换出出进进程程，然然后后启启动动盘盘块块，将将该该进进程程的的程程序序和和数数据据传传送送到到磁磁盘盘的的对对换换区区上上。若若传传送送过过程程未未出出现现错错误误，便便可可回回收收该该进进程程所所占占用用的的内内存存空空间间，并并对对该该进进程程的的进进程程控控制制块做相应的修改。块做相应的修改。(2)进程的换入。进程的换入。系系统统应应定定时时地地查查看看所所有有进进程程的的状状态态，从从中中找找出出“就就绪绪”状状态态但但已已换换出出的的进进程程，将将其其中中换换出出时时间间(换换出出到到磁磁盘盘上上)最最久久的的进进程程作作为为换换入入进进程程，将将之之换换入入，直直至至已已无无可可换换入入的的进程或无可换出的进程为止。进程或无可换出的进程为止。4.4基本分页存储管理方式基本分页存储管理方式4.4.1页面与页表页面与页表1.页面页面1)页面和物理块页面和物理块分分页页存存储储管管理理，是是将将一一个个进进程程的的逻逻辑辑地地址址空空间间分分成成若若干干个个大大小小相相等等的的片片，称称为为页页面面或或页页，并并为为各各页页加加以以编编号号，从从0开开始始，如如第第0页页、第第1页页等等。相相应应地地，也也把把内内存存空空间间分分成成与与页页面面相相同同大大小小的的若若干干个个存存储储块块，称称为为(物物理理)块块或或页页框框(frame)，也也同同样样为为它它们们加加以以编编号号，如如0块块、1块块等等等等。在在为为进进程程分分配配内内存存时时，以以块块为为单单位位将将进进程程中中的的若若干干个个页页分分别别装装入入到到多多个个可可以以不不相相邻邻接接的的物物理理块块中中。由由于于进进程程的的最最后后一一页页经经常常装装不不满满一一块块而而形形成成了了不不可可利用的碎片，称之为利用的碎片，称之为“页内碎片页内碎片”。2)页面大小页面大小在在分分页页系系统统中中的的页页面面其其大大小小应应适适中中。页页面面若若太太小小，一一方方面面虽虽然然可可使使内内存存碎碎片片减减小小，从从而而减减少少了了内内存存碎碎片片的的总总空空间间，有有利利于于提提高高内内存存利利用用率率，但但另另一一方方面面也也会会使使每每个个进进程程占占用用较较多多的的页页面面，从从而而导导致致进进程程的的页页表表过过长长，占占用用大大量量内内存存；此此外外，还还会会降降低低页页面面换换进进换换出出的的效效率率。然然而而，如如果果选选择择的的页页面面较较大大，虽虽然然可可以以减减少少页页表表的的长长度度，提提高高页页面面换换进进换换出出的的速速度度，但但却却又又会会使使页页内内碎碎片片增增大大。因因此此，页页面面的的大大小小应应选选择择得得适适中中，且页面大小应是且页面大小应是2的幂，通常为的幂，通常为512B8KB。2.地址结构地址结构分页地址中的地址结构如下：分页地址中的地址结构如下：页号P位移量W3112110对对某某特特定定机机器器，其其地地址址结结构构是是一一定定的的。若若给给定定一一个个逻逻辑辑地地址址空空间间中中的的地地址址为为A，页页面面的的大大小小为为L，则则页页号号P和和页页内地址内地址d可按下式求得：可按下式求得：3.页表页表图 4-11 页表的作用 4.4.2地址变换机构地址变换机构1.基本的地址变换机构基本的地址变换机构图 4-12 分页系统的地址变换机构 2.具有快表的地址变换机构具有快表的地址变换机构图 4-13 具有快表的地址变换机构【例1】考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址需要多少二进制位表示？（2）物理地址需要多少二进制位表示？解:因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（1）、页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）、页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。例例2、分页存储管理中页表如图。页面大小为、分页存储管理中页表如图。页面大小为1024B，试将逻辑地址试将逻辑地址1011，2148，4000，5012转化为相应转化为相应的物理地址。的物理地址。物理地址页的大小物理地址页的大小L 块号块号f页内地址页内地址d 解：解：设页号为设页号为p，页内位移为，页内位移为d，则：，则：（1）逻辑地址）逻辑地址1011，pINT(1011/1024)0，d1011 mod 10241011。查页表第。查页表第0页对应第页对应第2块，块，物理地址为物理地址为1024 210113059。（2）对于逻辑地址）对于逻辑地址2148，pINT(2148/1024)2，d2148 mod 1024100。查页表第。查页表第2页对应第页对应第1块，块，物理地址为物理地址为10241001124。（3）对于逻辑地址）对于逻辑地址4000，pINT(4000/1024)3，d4000 mod 1024928。查页表第。查页表第3页对应第页对应第6块，块，物理地址为物理地址为1024 69287072。（4）对于逻辑地址）对于逻辑地址5012，pINT(5012/1024)4，d5012 mod 1024916。因页号超过页表长度，。因页号超过页表长度，该逻辑地址非法。该逻辑地址非法。页号块号021321364.3.3两级和多级页表两级和多级页表现现代代的的大大多多数数计计算算机机系系统统，都都支支持持非非常常大大的的逻逻辑辑地地址址空空间间(232264)。在在这这样样的的环环境境下下，页页表表就就变变得得非非常常大大，要要占占用用相相当当大大的的内内存存空空间间。例例如如，对对于于一一个个具具有有32位位逻逻辑辑地地址址空空间间的的分分页页系系统统，规规定定页页面面大大小小为为4KB即即212B，则则在在每每个个进进程程页页表表中中的的页页表表项项可可达达1兆兆个个之之多多。又又因因为为每每个个页页表表项项占占用用一一个个字字节节，故故每每个个进进程程仅仅仅仅其其页页表表就就要要占占用用4KB的的内内存存空空间间，而而且且还还要要求求是是连连续续的的。可可以以采采用用这这样样两两个个方方法法来来解解决决这这一一问问题题：采采用用离离散散分分配配方方式式来来解解决决难难以以找找到到一一块块连连续续的的大大内内存存空空间间的的问问题题：只只将将当当前前需需要要的的部部分分页页表表项项调调入入内内存存，其其余余的的页页表表项项仍驻留在磁盘上，需要时再调入。仍驻留在磁盘上，需要时再调入。1.两级页表两级页表(Two-LevelPageTable)逻辑地址结构可描述如下：逻辑地址结构可描述如下：图 4-14 两级页表结构 图图4-15具有两级页表的地址变换机构具有两级页表的地址变换机构2.多级页表多级页表对对于于32位位的的机机器器，采采用用两两级级页页表表结结构构是是合合适适的的；但但对对于于64位位的的机机器器，如如果果页页面面大大小小仍仍采采用用4KB即即212B，那那么么还还剩剩下下52位位，假假定定仍仍按按物物理理块块的的大大小小(212位位)来来划划分分页页表表，则则将将余余下下的的42位位用用于于外外层层页页号号。此此时时在在外外层层页页表表中中可可能能有有4096G个个页页表表项项，要要占占用用16384GB的的连连续续内内存存空空间间。必必须须采采用用多多级级页页表表，将将外外层层页页表表再再进进行行分分页页，也也是是将将各各分分页页离离散散地地装装入入到到不不相相邻邻接接的的物物理理块块中中，再再利利用用第第2级级的的外外层层页页表表来来映映射它们之间的关系。射它们之间的关系。对对于于64位位的的计计算算机机，如如果果要要求求它它能能支支持持2(=1844744TB)规规模模的的物物理理存存储储空空间间，则则即即使使是是采采用用三三级级页页表表结结构构也也是是难以办到的；而在当前的实际应用中也无此必要。难以办到的；而在当前的实际应用中也无此必要。4.4基本分段存储管理方式基本分段存储管理方式4.4.1分段存储管理方式的引入分段存储管理方式的引入引引入入分分段段存存储储管管理理方方式式，主主要要是是为为了了满满足足用用户户和和程程序序员员的下述一系列需要：的下述一系列需要：1)方便编程方便编程2)信息共享信息共享3)信息保护信息保护4)动态增长动态增长5)动态链接动态链接4.4.2分段系统的基本原理分段系统的基本原理1.分段分段分段地址中的地址具有如下结构：分段地址中的地址具有如下结构：段号段号段内地址段内地址31161502.段表段表图 4-17 利用段表实现地址映射 图 4-18 分段系统的地址变换过程 3.地址变换机构 4.分页和分段的主要区别分页和分段的主要区别分段分段分页分页划分单位划分单位逻辑上的段逻辑上的段(大小不固定大小不固定)固定大小的页固定大小的页采用目的采用目的满足用户的要求满足用户的要求满足系统的要求（消除满足系统的要求（消除碎片、提高内存利用率碎片、提高内存利用率等）等）地址空间地址空间二维：程序员给出段号二维：程序员给出段号和段内地址和段内地址程序员给出一维地址：程序员给出一维地址：逻辑地址由系统直接划逻辑地址由系统直接划分为分为2部分部分优点优点4.5.3信息共享信息共享图 4-19 分页系统中共享editor的示意图图 4-20 分段系统中共享editor的示意图 4.4.4段页式存储管理方式段页式存储管理方式1.基本原理基本原理图 4-20 作业地址空间和地址结构 图 4-21 利用段表和页表实现地址映射 2.地址变换过程地址变换过程图 4-22 段页式系统中的地址变换机构 4.5虚拟存储器的基本概念虚拟存储器的基本概念4.5.1虚拟存储器的引入虚拟存储器的引入1.常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性。(2)驻留性。2.局部性原理局部性原理早在早在1968年，年，Denning.P就曾指出：就曾指出：(1)程程序序执执行行时时，除除了了少少部部分分的的转转移移和和过过程程调调用用指指令令外，外，在大多数情况下仍是顺序执行的。在大多数情况下仍是顺序执行的。(2)过过程程调调用用将将会会使使程程序序的的执执行行轨轨迹迹由由一一部部分分区区域域转转至至另另一一部部分分区区域域，但但经经研研究究看看出出，过过程程调调用用的的深深度度在在大大多多数数情况下都不超过情况下都不超过5。(3)程程序序中中存存在在许许多多循循环环结结构构，这这些些虽虽然然只只由由少少数数指指令构成，令构成，但是它们将多次执行。但是它们将多次执行。(4)程程序序中中还还包包括括许许多多对对数数据据结结构构的的处处理理，如如对对数数组组进行操作，进行操作，它们往往都局限于很小的范围内。它们往往都局限于很小的范围内。局限性又表现在下述两个方面：局限性又表现在下述两个方面：(1)时时间间局局限限性性。如如果果程程序序中中的的某某条条指指令令一一旦旦执执行行，则则不不久久以以后后该该指指令令可可能能再再次次执执行行；如如果果某某数数据据被被访访问问过过，则则不不久久以以后后该该数数据据可可能能再再次次被被访访问问。产产生生时时间间局局限限性性的的典型原因，是由于在程序中存在着大量的循环操作。典型原因，是由于在程序中存在着大量的循环操作。(2)空空间间局局限限性性。一一旦旦程程序序访访问问了了某某个个存存储储单单元元，在在不不久久之之后后，其其附附近近的的存存储储单单元元也也将将被被访访问问，即即程程序序在在一一段段时时间间内内所所访访问问的的地地址址，可可能能集集中中在在一一定定的的范范围围之之内内，其典型情况便是程序的顺序执行。其典型情况便是程序的顺序执行。3.虚拟存储器定义虚拟存储器定义所所谓谓虚虚拟拟存存储储器器，是是指指具具有有请请求求调调入入功功能能和和置置换换功功能能，能能从从逻逻辑辑上上对对内内存存容容量量加加以以扩扩充充的的一一种种存存储储器器系系统统。其其逻逻辑辑容容量量由由内内存存容容量量和和外外存存容容量量之之和和所所决决定定，其其运运行行速速度度接接近近于于内内存存速速度度，而而每每位位的的成成本本却却又又接接近近于于外外存存。可可见见，虚虚拟拟存存储储技技术术是是一一种种性性能能非非常常优优越越的的存存储储器器管管理理技技术术，故故被被广泛地应用于大、广泛地应用于大、中、中、小型机器和微型机中。小型机器和微型机中。4.5.2虚拟存储器的实现方法虚拟存储器的实现方法1.分页请求系统分页请求系统(1)硬件支持。请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。(2)实现请求分页的软件。4.5.3虚拟存储器的特征虚拟存储器的特征1.多次性多次性2.对换性对换性3、虚拟性虚拟性4.6请求分页存储管理方式请求分页存储管理方式4.6.1请求分页中的硬件支持请求分页中的硬件支持1.页表机制页表机制页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 2.缺页中断机构缺页中断机构图图4-23涉及涉及6次缺页中断的指令次缺页中断的指令3.地址变换机构地址变换机构图 4-24 请求分页中的地址变换过程 4.6.2内存分配策略和分配算法内存分配策略和分配算法1.最小物理块数的确定最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。2.物理块的分配策略物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(Fixed Allocation,Local Replacement)2)可变分配全局置换(Variable Allocation,Global Replacement)3)可变分配局部置换(Variable Allocation,Local Replacemen 3.物理块分配算法物理块分配算法 1)平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。2)按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。3)考虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。4.6.3调页策略调页策略1.何时调入页面何时调入页面1)预调页策略 2)请求调页策略 2.从何处调入页面从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。3.页面调入过程页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。4.7页面置换算法页面置换算法4.7.1最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1.最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。图 4-25 利用最佳页面置换算法时的置换图 2.先进先出先进先出(FIFO)页面置换算法页面置换算法图 4-26 利用FIFO置换算法时的置换图 4.7.2最近最久未使用最近最久未使用(LRU)置换算法置换算法1.LRU(LeastRecentlyUsed)置换算法的描述置换算法的描述图 4-27 LRU页面置换算法 2.LRU置换算法的硬件支持置换算法的硬件支持1)寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0 图 4-28 某进程具有8个页面时的LRU访问情况 2)栈栈图 4-29 用栈保存当前使用页面时栈的变化情况 4.7.3Clock置换算法置换算法1.简单的简单的Clock置换算法置换算法图 4-30 简单Clock置换算法的流程和示例 2.改进型改进型Clock置换算法置换算法 由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。4.7.4其它置换算法其它置换算法1.最少使用(LFU：Least Frequently Used)置换算法2.页面缓冲算法(PBA：Page Buffering Algorithm)4.8请求分段存储管理方式请求分段存储管理方式4.8.1请求分段中的硬件支持请求分段中的硬件支持1.段表机制段表机制段名 段长 段的基址 存取方式 访问字段A 修改位M 存在位P 增补位 外存始址 在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项：(1)存取方式。(2)访问字段A。(3)修改位M。(4)存在位P。(5)增补位。(6)外存始址。2.缺段中断机构缺段中断机构图图4-31请求分段系统中的中断处理过程请求分段系统中的中断处理过程3.地址变换机构地址变换机构图 4-32 请求分段系统的地址变换过程4.8.2分段的共享与保护分段的共享与保护1.共享段表共享段表图 4-33 共享段表项 2.共享段的分配与回收共享段的分配与回收 1)共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作，以表明有两个进程共享该段。2)共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。3.分段保护分段保护1)越界检查 2)存取控制检查(1)只读(2)只执行(3)读/写 3)环保护机构(1)一个程序可以访问驻留在相同环或较低特权环中的数据。(2)一个程序可以调用驻留在相同环或较高特权环中的服务。图 4-34 环保护机构