os操作系统04.ppt

单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击以编辑,母版标题样式,第四章 存储器管理,4.1,程序的装入和链接,4.2,连续分配方式,4.3,基本分页存储管理方式,4.4,基本分段存储管理方式,4.5,虚拟存储器的基本概念,4.6,请求分页存储管理方式,4.7,页面置换算法,4.8,请求分段存储管理方式,1,图,4-1,对用户程序的处理步骤,4.1,程序的装入和链接,2,1.,绝对装入方式,(,Absolute Loading Mode),程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换,为绝对地址。,4.1.1,程序的装入,3,2.,可重定位装入方式,(,Relocation Loading Mode),图,4-2,作业装入内存时的情况,4,3.,动态运行时装入方式,(,Dynamic Run-time Loading),动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有,地址都仍是相对地址。,5,4.1.2,程序的链接,1.,静态链接方式,(,Static Linking),图,4-3,程序链接示意图,6,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：,(1),对相对地址进行修改。,(2),变换外部调用符号。,7,2.,装入时动态链接,(,Loadtime Dynamic Linking),装入时动态链接方式有以下优点：,便于修改和更新。,(2),便于实现对目标模块的共享。,8,3.,运行时动态链接,(,Run-time Dynamic Linking),近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由,OS,去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不,仅可加快程序的装入过程，而且可节省大量的内存空间。,9,通常被链接的共享代码称为动态链接库,(,DLL,Dynamic-Link Library),或共享库,(,shared library),。,优点,共享,：多个进程可以共用一个,DLL,，,节省内存，减少文件交换。,部分装入,：一个进程可以将多种操作分散在不同的,DLL,中实现，而只将当前操作相应的,DLL,装入内存。,便于局部代码修改,：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其,DLL,，,无需对可执行文件重新编译或链接。,便于运行环境适应,：调用不同的,DLL,，,就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定,的,DLL,，而,OS,和应用程序不必修改。,缺点：,链接开销,：增加了程序执行时的链接开销；,管理开销,：程序由多个文件组成，增加管理复杂度。,10,Windows NT,动态链接库,库程序文件,.,C,：,相当于给出一组函数定义的源代码；,模块定义文件,.,DEF,：,相当于定义链接选项，也可在源代码中定义；如：,DLL,中函数的引入和引出,(,dllimport,和,dllexport,),。,编译程序利用,.,C,文件生成目标模块,.,OBJ,库管理程序利用,.,DEF,文件生成,DLL,输入库,.,LIB,和输出文件,.,EXP,链接程序利用,.,OBJ,和,.,EXP,文件生成动态链接库,.,DLL,。,1.,构造动态链接库,DLL,是包含函数和数据的模块，它的调用模块可为,EXE,或,DLL,，,它由调用模块在运行时加载；加载时，它被映射到调用进程的地址空间。在,VC,中有一类工程用于创建,DLL,。,11,2.,DLL,的装入方法,装入时动态链接,(,load-time),：,在编程时显式调用某个,DLL,函数，该,DLL,函数在可执行文件中称为引入,(,import),函数。,链接时需利用,.,LIB,文件。在可执行文件中为引入的每个,DLL,建立一个,IMAGE_IMPORT_DESCRIPTOR,结构。,在装入时由系统根据该,DLL,映射在进程中的地址改写,Import Address Table,中的各项函数指针。,Hint,是,DLL,函数在,DLL,文件中的序号，当,DLL,文件修改后，就未必指向原先的,DLL,函数。在装入时，系统会查找相应,DLL,，,并把它映射到进程地址空间，获得,DLL,中各函数的入口地址，定位本进程中对这些函数的引用；,12,装入时动态链接过程,注：,Import Address Table,是在装入时依据,DLL,模块的加载位置确定。,13,DLL,函数的调用过程,14,运行时动态链接,(,run-time),：,在编程时通过,LoadLibrary,（,给出,DLL,名称，返回装入和链接之后该,DLL,的句柄）,FreeLibrary,GetProcAddress,（,其参数包括函数的符号名称，返回该函数的入口指针）等,API,来使用,DLL,函数。这时不再需要引入库（,import library,）。,LoadLibrary,或,LoadLibraryEx,把可执行模块映射到调用进程的地址空间,，返回模块句柄；,GetProcAddress,获得,DLL,中特定函数的指针,，返回函数指针；,FreeLibrary,把,DLL,模块的引用计数减,1,；当引用计数为,0,时，,删除,DLL,模块到进程地址空间的映射,；,15,运行时动态链接的例子,HINSTANCE,hInstLibrary,;/,模块句柄定义,DWORD(WINAPI*,InstallStatusMIF,)(char*,char*,char*,char*,char*,char*,char*,BOOL);/,函数指针定义,if(,hInstLibrary,=,LoadLibrary,(ismif32.,dll,)/,映射,InstallStatusMIF,=(DWORD(WINAPI*)(char*,char*,char*,char*,char*,char*,char*,BOOL),GetProcAddress,(,hInstLibrary,InstallStatusMIF,);/,获得函数指针,if(,InstallStatusMIF,),if(,InstallStatusMIF,(“office97”,“Microsoft”,“Office 97”,“999.999”,“ENU”,“1234”,”Completed successfully”,TRUE)!=0)/,调用,DLL,模块中的函数,FreeLibrary,(,hInstLibrary,);/,拆除映射,16,4.2.1,单一连续分配,这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给,OS,使用，通常是放,在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。,4.2,连续分配方式,17,单一连续区存储管理,18,4.2.2,固定分区分配,1.,划分分区的方法,分区大小相等，即使所有的内存分区大小相等。只适合于多个相同程序的并发执行（处理多个类型相同的对象）。,(2),分区大小不等。多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,19,2.,内存分配,图,4-4,固定分区使用表,20,4.2.3,动态分区分配,1.,分区分配中的数据结构,空闲分区表。,(2),空闲分区链。,图,4-5,空闲链结构,21,2.,分区分配算法,首次适应算法,(,最先匹配法,first-fit),：,按分区的先后次序，从头查找，找到符合要求的第一个分区,该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。,但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。,循环首次适应算法,(,下次匹配法,next-fit),：,按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区,该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。,最佳匹配法,(,best-fit),：,找到其大小与要求相差最小的空闲分区,从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。,最坏匹配法,(,worst-fit),：,找到最大的空闲分区,基本不留下小空闲分区，但较大的空闲分区不被保留。,22,3.,分区分配操作,1),分配内存,图,4-6,内存分配流程,23,2),回收内存,图,4-7,内存回收时的情况,24,4.2.4,可重定位分区分配,1.,动态重定位的引入,图,4-8,紧凑的示意,25,2.,动态重定位的实现,图,4-9,动态重定位示意图,26,3.,动态重定位分区分配算法,图,4-10,动态分区分配算法流程图,27,4.2.5,覆盖和交换技术,(,Swapping),28,覆盖,(,overlay),引入：其目标是在较小的可用内存中,运行较大的程序,。常用于多道程序系统，与分区存储管理配合使用。,原理：一个程序的几个代码段或数据段，按照,时间,先后来,占用公共的内存空间,。,将程序的,必要部分,（常用功能）的代码和数据常驻内存；,可选部分,（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；,不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。,(,即,不同时用的模块可共用一个分区,),29,注：另一种覆盖方法：,(100,K),A(20K),占一个分区：,20,K,；,B(50K),、,D(20K),和,E(40K),共用一个分区：,50,K,；,F(30K),和,C(30K),共用一个分区：,30,K,；,覆盖技术,30,缺点：,编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。,从外存装入覆盖文件，以时间延长来换取空间节省。,实现：函数库（操作系统对覆盖不得知），或操作系统支持,DOS,中的,C,采用了覆盖技术，装入时分成两部分，内存低端部分常驻，内存高端部分可被其他程序覆盖。其他程序运行结束后，低端部分会根据需要检查高端，,31,1.,对换的引入,所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施,。,交换技术,(,Swapping),32,原理：,暂停,执行内存中的进程，将整个进程的地址空间,保存到外存,的交换区中（换出,swap out,），,而将外存中由阻塞变为就绪的进程的地址空间,读入,到内存中，并将该进程送到就绪队列（换入,swap in,）。,整体对换或进程对换,页面对换或分段对换 虚拟存储系统,33,2.,对换空间的管理,外存：文件区和交换区 连续分配,交换区的空闲块管理 分区表（链）,为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，,它们的单位是盘块号和盘块数。,交换区的分配和回收 算法,34,3.,进程的换出与换入,(1),进程的换出。,每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的,修改。,35,(2),进程的换入。,系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间,(,换出到磁盘上,),最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换,出的进程为止。,36,实例,Windows 9x,交换文件,WIN386.SWP,系统管理，手工设置大小,Windows NT,系列 交换文件,pagefile,.sys,系统特性,性能选项,虚拟内存,UNIX,，,Linux,交换区或交换文件,37,优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构,缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。,考虑的问题：,程序换入时的重定位；,减少交换中传送的信息量，特别是对大程序；,对外存交换区空间的管理：如动态分区方法；,38,4.3.1,页面与页表,1.,页面,1),页面和物理块,分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从,0,开始，如第,0,页、第,1,页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为,(,物理,),块或页框,(,frame),，,也同样为它们加以编号，如,0,块、,1,块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页,内碎片”。,4.3,基本分页存储管理方式,39,2),页面大小,在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是,2,的幂，,通常为,512,B8 KB,。,40,2.,地址结构,分页地址中的地址结构如下：,页号,P,位移量,W,31,12,11,0,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为,A,，,页面的大,小为,L,，,则页号,P,和页内地址,d,可按下式求得：,41,3.,页表,图,4-11,页表的作用,42,4.3.2,地址变换机构,1.,基本的地址变换机构,图,4-12,分页系统的地址变换机构,43,2.,具有快表的地址变换机构,图,4-13,具有快表的地址变换机构,44,4.3.3,两级和多级页表,现代的大多数计算机系统，都支持非常大的逻辑地址空间,(2,32,2,64,),。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有,32,位逻辑地址空间的分页系统，规定页面大小为,4,KB,即,2,12,B,，,则在每个进程页表中的页表项可达,1,兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用,4,KB,的内存空间，而且还要求是连续的。可以采用这样两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连续的大内存空间的问题：只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要,时再调入。,45,1.,两级页表,(,Two-Level Page Table),逻辑地址结构可描述如下：,46,图,4-14,两级页表结构,47,图,4-15,具有两级页表的地址变换机构,48,2.,多级页表,对于,32,位的机器，采用两级页表结构是合适的；但对于,64,位的机器，如果页面大小仍采用,4,KB,即,2,12,B,，,那么还剩下,52,位，假定仍按物理块的大小,(2,12,位,),来划分页表，则将余下的,42,位用于外层页号。此时在外层页表中可能有,4096,G,个页表项，要占用,16384,GB,的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第,2,级的外层页表来映射它们之间的关系。,对于,64,位的计算机，如果要求它能支持,2,(=1844744,TB),规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。,49,4.4.1,分段存储管理方式的引入,固定,动态,分页提高内存利用率,分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：,1),方便编程,2),信息共享,3),信息保护,4),动态增长,5),动态链接,4.4,基本分段存储管理方式,50,4.4.2,分段系统的基本原理,1.,分段,分段地址中的地址具有如下结构：,段号,段,内地址,31 16 15 0,2.,段表,进程段表,：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址,(,base address),和段长度,系统段表,：系统内所有占用段,空闲段表,：内存中所有空闲段，可以结合到系统段表中,51,图,4-16,利用段表实现地址映射,52,图,4-17,分段系统的地址变换过程,3.,地址变换机构,53,4.,分页和分段的主要区别,(1),页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的,需要。,54,(2),页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。,(3),分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，,既需给出段名，又需给出段内地址。,55,4.4.3,信息共享,图,4-18,分页系统中共享,editor,的示意图,分页 每一进程页表页表项多,56,图,4-19,分段系统中共享,editor,的示意图,分段 每一进程段表只有两项,57,4.4.4,段页式存储管理方式,1.,基本原理,-,页式和段式存储管理的结合。,图,4-20,作业地址空间和地址结构,页式内存利用率，无外部碎片,段式用户需要，易共享与保护，动态链接,58,图,4-21,利用段表和页表实现地址映射,59,2.,地址变换过程,图,4-22,段页式系统中的地址变换机构,先查段表，再查该段的页表。三次内存访问，可设置高速缓冲寄存器,60,4.5.1,虚拟存储器的引入,1.,常规存储器管理方式的特征,一次性。,(2),驻留性。,内存空间浪费,4.5,虚拟存储器的基本概念,61,2.,局部性原理,早在,1968,年，,Denning.P,就曾指出：,(1),程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的,。,(2),过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过,程调用的深度在大多数情况下都不超过,5,。,(3),程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。,(4),程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的,范围内。,62,局限性又表现在下述两个方面：,(1),时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。,(2),空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便,是程序的顺序执行。,63,3.,虚拟存储器定义,所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一,种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。,在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。,缺页或缺段,64,4.5.2,虚拟存储器的实现方法,1.,分页请求系统,硬件支持。,请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求,OS,将所缺的页调入内存；地址变换机构，,它同样是在纯分页地址变换机构的基础上发展形成的。,(2),实现请求分页的软件。,65,4.5.3,虚拟存储器的特征,多次性,一个作业被分成多次调入内存运行,对换性,虚拟存储的调入和调出是对部分虚拟地址空间进行的；,3.,虚拟性,通过物理内存和快速外存相结合，提供大范围的虚拟地址空间,大程序：可在较小的可用内存中执行较大的用户程序；,大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存,并发：可在内存中容纳更多进程并发执行；,易于开发：不必影响编程时的程序结构,66,4.6.1,请求分页中的硬件支持,1.,页表机制,页号,物理块号,状态位,P,访问字段,A,修改位,M,外存地址,4.6,请求分页存储管理方式,纯分页硬件软件,换进换出的基本单位是定长的页面,需要在进程页表中添加若干项,状态位：存在位（,present bit,，,内存页和外存页）,访问字段,A,：,在近期内被访问的次数，或最近一次访问到现在的时间间隔,修改位,(,modified bit),外存地址,67,2.,缺页中断机构,图,4-23,涉及,6,次缺页中断的指令,缺页中断的特殊性,缺页中断在指令执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。,一条指令的执行可能产生多次缺页中断，如：,swap A,B,或,copy A To B,，,指令本身和两个操作数,A,B,都跨越相邻外存页的分界处，则产生,6,次缺页中断。,68,3.,地址变换机构,图,4-24,请求分页中的地址变换过程,页号,快表,页表，,缺页中断,/,修改快表,修改访问位和修改位,缺页中断处理,-,由处理器的地址变换机构产生缺页中断，然后调用操作系统提供的中断处理例程。,69,4.6.2,内存分配策略和分配算法,1.,最小物理块数的确定,是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为,2,。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。,70,2.,物理块的分配策略,在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。,1),固定分配局部置换,(,Fixed Allocation,Local Replacement),每个进程分配一固定页数的内存空间，太少，缺页中断高；太多，浪费，并发减低,2),可变分配全局置换,(,Variable Allocation,Global Replacement),每个进程先分配一定数目的物理块，,OS,保持一个空闲物理块队列。缺页时，从空闲物理块队列中分配一块。,3),可变分配局部置换,(,Variable Allocation,Local Replacement),每个进程先分配一定数目的物理块，缺页时，置换其中一页。若缺页率高，增加该进程分配的物理块。反之，减少分配的物理块。,71,3.,物理块分配算法,1),平均分配算法,这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有,100,个物理块，有,5,个进程在运行时，每个进程可分得,20,个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为,200,页，只分配给它,20,个块，这样，它必然会有很高的缺页率；而另一个进程只有,10,页，却有,10,个物,理块闲置未用。,72,2),按比例分配算法,这是根据进程的大小按比例分配物理块的算法。如果系统中共有,n,个进程，每个进程的页面数为,S,i,，,则系统中各进程页面数的总和为：,又假定系统中可用的物理块总数为,m,，,则每个进程所能分到的物理块数为,b,i,，,将有：,b,应该取整，它必须大于最小物理块数。,73,3),考虑优先权的分配算法,在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其,物理块的。,74,4.6.3,调页策略,1.,何时调入页面,预调页策略,在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。,优点：提高调页的,I/O,效率。,缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。,2),请求调页策略,只调入发生缺页时所需的页面。,优点：容易实现。,缺点：对外存,I/O,次数多，开销较大,75,2.,从何处调入页面,在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件是采用离散分配方式，故对换区的磁盘,I/O,速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：,(1),系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度,。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。,76,(2),系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。,(3),UNIX,方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于,UNIX,系统允许页面共享，因此，某进程所请求的页面有,可能已被其它进程调入内存，此时也就无须再从对换区调入。,77,3.,页面调入过程,每当程序所要访问的页面未在内存时，便向,CPU,发出一缺页中断，中断处理程序首先保留,CPU,环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘,I/O,将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“,1”,，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的,物理地址，再去访问内存数据。,78,4.7,页面置换算法,功能：需要调入页面时，选择内存中哪个物理页面被调出到对换区的算法,称为页面置换算法。,抖动：刚被换出的页很快有被访问，需重新调入；进程运行中，时间花费在页面置换工作上。,目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测,79,4.7.1,最佳置换算法和先进先出置换算法,1.,最佳,(,Optimal),置换算法,最佳置换算法是由,Belady,于,1966,年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长,(,未来,),时间内不再被访问的页面。采用最佳置换算法，,通常可保证获得最低的缺页率。,页面访问序列已知，选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。,80,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：,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,利用最佳页面置换算法时的置换图,81,2.,先进先出,(,FIFO),页面置换算法,图,4-26,利用,FIFO,置换算法时的置换图,选择,建立最早,的页面被置换。可以通过,链队列,来表示各页的建立时间先后。,性能较差,。较早调入的页往往是经常被访问的页，这些页在,FIFO,算法下被反复调入和调出。,82,Belady,现象,：采用,FIFO,算法时，如果对一个进程,未分配它所要求的全部页面,，有时就会出现分配的,页面数增多,，,缺页率反而提高,的异常现象。,Belady,现象的,描述,：一个进程,P,要访问,M,个页，,OS,分配,N,个内存页面给进程,P,；,对一个访问序列,S,，,发生缺页次数为,PE,（,S,N,）。当,N,增大时，,PE(S,N),时而增大，时而减小。,Belady,现象的,原因,：,FIFO,算法的,置换特征,与进程,访问内存的动态特征,是,矛盾,的，即被置换的页面并不是进程不会访问的。,Belady,现象,83,Belady,现象的例子,进程,P,有,5,页程序访问页的顺序为：,1,2,3,4,1,2,5,1,2,3,4,5,；,如果在内存中分配,3,个页面，则缺页情况如下：,12,次访问中有缺页,9,次；,84,如果在内存中分配,4,个页面，则缺页情况如下：,12,次访问中有缺页,10,次；,85,4.7.2,最近最久未使用,(,LRU),置换算法,LRU(Least Recently Used),置换算法的描述,选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。,图,4-27,LRU,页面置换算法,86,2.,LRU,置换算法的硬件支持,1),寄存器,为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器,，可表示为,R=,R,n,-1,R,n-2,R,n-3,R,2,R,1,R,0,每个页面设立移位寄存器：被访问时左边最高位置,1,，定期右移并且最高位补,0,，于是寄存器数值最小的是最久未使用页面。,87,图,4-28,某进程具有,8,个页面时的,LRU,访问情况,88,2),栈,图,4-29,用栈保存当前使用页面时栈的变化情况,一个特殊的栈：把被访问的页面移到栈顶，于是,栈底,的是最久未使用页面。,89,4.7.3,Clock,置换算法,简单的,Clock,置换算法,也称最近未使用算法,(,NRU,Not Recently Used),，,它是,LRU(,最近最久未使用算法,),和,FIFO,的折衷。,图,4-30,简单,Clock,置换算法的流程和示例,90,2.,改进型,Clock,置换算法,由访问位,A,和修改位,M,可以组合成下面四种类型的页面：,1,类,(,A=0,M=0):,表示该页最近既未被访问，又未被修改，是最佳淘汰页。,2,类,(,A=0,M=1),：,表示该页最近未被访问，但已被修改，并不是很好的淘汰页。,3,类,(,A=1,M=0),：,最近已被访问，但未被修改，该页有可能再被访问。,4,类,(,A=1,M=1):,最近已被访问且被修改，该页可能再被访问。,91,其执行过程可分成以下三步：,(1),从指针所指示的当前位置开始，扫描循环队列，寻找,A=0,且,M=0,的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位,A,。,(2),如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找,A=0,且,M=1,的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置,0,。,(3),如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复,0,。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能,找到被淘汰的页。,92,4.7.4,其它置换算法,最少使用,(,LFU,：,Least Frequently Used),置换算法,选择到当前时间为止被访问次数最少的页面被置换；,每页设置访问计数器，每当页面被访问时，该页面的访问计数器加,1,；由于内存具有较高的访问速度，通常采用移位寄存器方式计数。类似,LRU,发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；,2.,页面缓冲算法,(,PBA,：,Page Buffering Algorithm),是对,FIFO,算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；,93,请求分页系统的性能分析,缺页，运行速度和系统性能,每个进程分配的物理页面数目,1,缺页率对有效访问时间的影响,存储器访问时间,ma,，,缺页概率,p,有效访问时间,(1,p)x ma+p x,缺页中断时间,缺页中断时间：缺页中断服务时间，,页面读入时间,，进程重新执行时间,缺页率,p-“,缺页次数,/,内存访问次数”,(,比率,),或“缺页的平均时间间隔的倒数”,页面大小，分配给进程的页面数目,94,2,工作集策略,(,working set strategy),工作集,是一个,进程执行过程中,所,访问页面的集合,常驻集,指虚拟页式管理中给进程分配的物理页面数目。,常驻集与缺页率的关系：,每个进程的常驻集越小，则同时驻留内存的进程就越多，可以提高并行度和处理器利用率；另一方面，进程的缺页率上升，使调页的开销增大。,进程的常驻集达到某个数目之后，再给它分配更多页面，缺页率不再明显下降。,缺页率或缺页的时间间隔与进程所分得的物理页面有关,1968,年由,Denning,提出，引入工作集的目的是依据进程在过去的一段时间内访问的页面来,调整常驻集大小,。,95,工作集大小的变化：进程开始执行后，随着访问新页面逐步建立,较稳定的工作集,。当内存访问的,局部性区域,的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集,快速扩张和收缩过渡,到下一个稳定值。,96,3,抖动产生的原因和预防方法,系统吞吐量多道程序度，抖动,一、抖动产生的原因,随着驻留内存的,进程数目增加,，或者说进程并发水平,(,multiprogramming level),的上升，,处理器利用率先是上升，在某一峰值后，继续增加多道程序度，,CPU,利用率会急剧下降，缺页率增加,。,CP