操作系统PPT参考课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Page,*,Operating System,第四章 存储器管理,操作系统,Page,1,第四章 存储器管理,重点,理解,重定位的基本概念,掌握,动态分区分配方式,掌握理解,分页和分段存储管理方式,理解,虚拟存储器的基本概念,掌握,请求分页系统的基本原理,难点,动态分区分配,算法,分页和分段地址转换,请求分页系统的地址转换及页面置换算法,Page,2,第四章 存储器管理,知识点,重定位的基本概念,动态分区分配方式及分配算法、分区保护,分页存储管理及地址变换、分段存储管理及地址变换，信息共享和保护,虚拟存储器的基本概念、特征，页面置换技术,请求分页系统，页表机制、地址变换及页面置换算法,Page,3,第四章 存储器管理,存储器是计算机系统重要的组成部分,虽然存储器的容量不断扩大，但仍不能满足要求，因此存储器管理是操作系统的重要工作,Page,4,第四章 存储器管理,存储器包括内存（主存）和外存（磁盘）,存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。,内存在访问速度方面的发展：,DRAM,、,SDRAM,、,SRAM,等；,硬盘技术在大容量方面的发展：接口标准、存储密度等；,主存储器管理技术分为两大类,实存储器管理,虚拟存储器管理,Page,5,第四章 存储器管理,存储器的物理组织、多级存储器,存储组织是指在存储技术和,CPU,寻址技术许可的范围内组织合理的存储结构。,其依据是访问速度匹配关系、容量要求和价格。,“寄存器,-,内存,-,外存”结构,“寄存器,-,缓存,-,内存,-,外存”结构；,微机中的存储层次组织：,访问速度越慢，容量越大，价格越便宜；,最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；,Page,6,第四章 存储器管理,快速缓存：,Data Cache,TLB(Translation Lookaside Buffer),内存：,DRAM,SDRAM,等；,外存：软盘、硬盘、光盘、磁带等；,Page,7,第四章 存储器管理,主存储器管理功能,存储分配和回收,分配和回收算法及相应的数据结构,地址变换和重定位,可执行文件生成中的链接技术,程序加载,(,装入,),时的重定位技术,进程运行时硬件和软件的地址变换技术和机构,存储共享和保护,代码和数据共享,地址空间访问权限（读、写、执行）,存储器扩充：存储器的逻辑组织和物理组织；,由应用程序控制：覆盖；,由,OS,控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）,Page,8,第四章 存储器管理,程序的装入和链接,连续分配方式,基本分页存储管理,基本分段存储管理,虚拟存储器的基本概念,请求分页存储管理方式,页面置换算法,请求分段存储管理方式,Page,9,程序的装入和链接,程序的装入,程序的链接,Page,10,程序的装入,多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事就是分配内存,源程序要运行通常经过,编译（,compile,）,链接,(link),装入,(load),等几个步骤,Page,11,4.1,程序的装入和链接,图,4-1,对用户程序的处理步骤,Page,12,4.1.1,程序的装入,1.,绝对装入方式,(Absolute Loading Mode),2.,可重定位装入方式,(Relocation Loading Mode),3.,动态运行时装入方式,(Dynamic Run-time Loading)Page,13,程序的装入,绝对装入方式,(Absolute Loading Mode),事先,确定,了程序将,驻留在内存,的什么,位置,，即在内存中的,绝对地址,装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对程序和数据的地址进行修改,绝对地址的产生,程序员直接赋予。不仅要求程序员熟悉内存使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。通常在程序中采用符号地址，在编译或汇编时，再将符号地址转换为绝对地址。,编译或汇编时产生,Page,14,程序的装入,可重定位装入方式,(Relocation Loading Mode),绝对装入方式只能将目标模块装入到内存中事先指定的位置,在多道程序环境下，不可能预知目标模块放在内存中的地址，因此绝对装入方式不适合在多道环境下使用,程序中,目标模块的地址通常从,0,开始,，其他地址都是相对于,0,计算,相对地址,把在装入时对目标程序中指令和数据的地址修改过程称为,重定位,，又因为,地址变换通常是在装入时一次完成,的，以后不再改变，故称为,静态重定位,Page,15,程序的装入,作业装入内存时的情况,缺点：不断的分配和回收，造成内存中小空闲块很多，总空闲空间量够，但分配不了,办法：紧凑（移动），但该装入方法不支持,Page,16,LOAD 1,2500,365,5000,2500,1000,0,作业地址空间,365,10000,11000,12500,15000,内存空间,LOAD 1,12500,365,20000,21000,22500,25000,内存空间,LOAD 1,2,2500,将程序加载到,10000,？,程序的装入,将程序移动到,20000,？,Page,17,程序的装入,动态运行时装入方式,(Denamic Run-time Loading),可重定位方式不允许程序运行时,在内存中移动位置,动态运行时的装入程序，是在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种,地址转换推迟到程序真正要,执行,时才进行,。因此，,装入,内存后的所有地址都,仍是相对地址,Page,18,程序的装入和链接,程序的装入,程序的链接,Page,19,4.1,程序的装入和链接,图,4-1,对用户程序的处理步骤,Page,20,4.1.2,程序的链接,1.,静态链接方式,(Static Linking),2.,装入时动态链接,(Load-time Dynamic Linking),3.,运行时动态链接,(Run-time Dynamic Linking),Page,21,程序的链接,静态链接方式,(Static Linking),在程序,运行前,，先将各目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题,对相对地址进行修改,变换外部调用符号,Page,22,程序的链接,模块,A,CALL B,；,Return,；,0,L,1,模块,B,CALL C,；,Return,；,0,M,1,模块,C,Return,；,0,N,1,(,a,),目标模块,(,外存,),装入前链接修改地址,0,模块,A,JSR“L”,Return,；,L,1,模块,B,JSR“L,M”,Return,；,L,L,M,1,L,M,L,M,N,1,模块,C,Return,；,(,b,),装入模块,（外存）,Page,23,程序的链接,装入时动态链接,(Load,time Dynamic Linking),将用户的源程序编译后所得的一组目标模块在装入内存时采用,边装入边链接,的方式,便于修改和更新,便于实现对目标模块的共享,Page,24,模块,A,CALL B,；,Return,；,0,L,1,模块,B,CALL C,；,Return,；,0,M,1,模块,C,Return,；,0,N,1,外存,0,模块,A,JSR“L”,Return,；,L,1,模块,B,JSR“L,M”,Return,；,L,L,M,1,L,M,L,M,N,1,模块,C,Return,；,内存,程序的链接,装入时链接修改地址,Page,25,程序的链接,运行时动态链接,(Run-time Dynamic Linking),应用程序在每次运行的模块可能不相同,运行时动态链接方式将对某些模块的,链接推迟到,执行,时才进行,，即在执行过程中，当发现一个被调用模块,尚未装入内存,时，立即由,OS,去找到该模块并将之装入内存，把它链接到调用者模块上,凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可,加快程序的装入过程,，而且可,节省大量的内存空间,Page,26,模块,A,CALL B,；,Return,；,0,L,1,模块,B,CALL C,；,Return,；,0,M,1,模块,C,Return,；,0,N,1,外存,0,模块,A,JSR“L”,Return,；,L,1,内存,执行时链接修改地址,Page,27,第四章 存储器管理,程序的装入和链接,连续分配方式,基本分页存储管理,基本分段存储管理,虚拟存储器的基本概念,请求分页存储管理方式,页面置换算法,请求分段存储管理方式,Page,28,连续分配方式,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,对换（,Swapping,）,Page,29,单一连续分配,连续分配方式为,一个用户,程序分配一个连续的内存空间,单一连续分配,是最简单的一种存储管理方式，但只能用于,单用户、单任务,的操作系统中,把内存分为,系统区：,OS,使用，通常放在内存低址部分,用户区：,用户可使用的全部内存空间,存储器保护机构不健全，易造成系统破坏,优点：易于管理,缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存,Page,30,单一连续分配,用户程序,位于,RAM,中的,操作系统,0,xFFF,.,0,位于,RAM,中的,操作系统,用户程序,0,ROM,中的,设备驱动程序,用户程序,位于,RAM,中的,操作系统,0,单一连续区存储管理,Page,31,连续分配方式,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,对换（,Swapping,）,Page,32,固定分区分配,最简单的可运行,多道程序,的存储管理方式,内存用户空间划分为若干个,固定大小的区域,，每个分区中只装入,一道,作业,划分分区的方法,分区大小相等,：,即使所有的内存分区大小相等,太大：浪费,太小：不够用,分区大小不等,：,划分为多个大、中、小搭配的分区,根据程序大小决定所使用的分区,大班在大教室、小班在小教室,Page,33,内存分配,分区的信息根据分区使用表管理,固定分区分配,20,使用界地址寄存器,采用静态重定位,问题：并发进程数受分区个数的制约！,出现：有内存却不能运行程序或大进程无法运行！,Page,34,连续分配方式,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,对换（,Swapping,）,Page,35,动态分区分配,根据进程的实际需要，动态地为之分配内存空间,分配中数据结构,空闲分区表,记录每个空闲分区的情况,空闲分区链,实现对空闲分区的分配和链接,Page,36,动态分区分配,分区分配算法,首次适应算法,FF,循环首次适应算法,最佳适应算法,最差适应算法,Page,37,动态分区分配,分区分配算法,首次适应算法,FF,空闲分区链以,地址递增顺序,链接,分配时从,链首开始查找,，找到一个大小可满足的空闲分区，划出一块给请求者,优点：简单；优先利用低地址空闲区，保留高地址大空闲区,缺点：会造成在低地址部分很多难以利用的小空闲分区，查找效率低,循环首次适应算法,每次分配时,从上一次找到,空闲分区的,下一个空闲区开始查找,优点：减少查找空闲分区开销，空闲分区分布更均匀,缺点：缺乏大的空闲区,Page,38,动态分区分配,最佳适应算法,空闲区按容量由小到大排序,每次分配时，把能满足要求、又是,最小,的分区分配给作业,优点：不缺乏大的空闲区,缺点：会在存储器中留直许多难以利用的小分区,“,零头（或碎片）,”；查找效率低,最差适应算法,空闲区按容量由大到小排序,每次分配时，把能满足要求、又是,最大,的分区分配给作业,优点：剩余的空间最大化，不出现太小的“,零头,”,缺点：缺乏大的空闲区,首次适应被认为最好、最快，其次是循环，最佳最差（每次分配后剩下小碎片，难再分，不得不经常压缩内存，反而浪费,CPU,）,Page,39,动态分区分配,分区分配操作,分配内存从头开始查表,检索完否？,m.size,u.size?,m.size,u.sizesize?,从该分区中划出,u.size,大小的分区,将该分区分配给请求者修,改有关数据结构,返回,返回,继续检索下一个表项,将该分区从链中移出,Y,N,N,Y,Y,N,解决碎片问题,Page,40,动态分区分配,分区分配操作,回收内存,进程运行结束释放内存时，系统根据回收区的首地址，把它插入到空闲链表中。根据回收区的位置，有四种情况需处理：,回收区与插入点的,前一个,空闲分区相邻接,回收区与插入点的,后一个,空闲分区相邻接,回收区同时与插入点的,前、后,两个分区相邻接,回收区不与任何空闲区邻接,Page,41动态分区分配,空闲区,回收区,回收区,空闲区,空闲区,回收区,空闲区,回收区,情况,1,情况,2,情况,3,情况,4,Page,42,2),回收内存,回收区,F1,F2,回收区,F2,回收区,F1,回收区,回收区,Page,43,动态分区分配,分区式存储管理的优缺点,优点：,便于动态申请内存,便于共享内存,便于动态链接,缺点：,碎片问题,(,外碎片,),，要求连续的内存空间，内存利用率不高，受实际内存容量限制,Page,44,动态分区分配,碎片问题,经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片,造成存储资源的浪费,碎片问题的解决,紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域,（紧缩技术，紧致技术，浮动技术，搬家技术）,问题：开销大；移动时机,Page,45,连续分配方式,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,对换（,Swapping,）,Page,46,4.2.4,可重定位分区分配,1.,动态重定位的引入,操作系统,用户程序,1,10kb,用户程序,3,30kb,用户程序,6,14kb,用户程序,9,26kb,80kb,用户程序,9,用户程序,6,用户程序,3,用户程序,1,操作系统,紧凑,Page,47,可重定位分区分配,动态重定位的引入,连续分配存在的问题,必须有足够大的连续空间才能分配,解决方法,：“拼接”,或,“紧凑”,的引入,Page,48,可重定位分区分配,动态重定位的实现,作业装入内存后的所有地址仍是,相对地址,，将,相对地址,转换,成,物理地址,的工作,在指令执行时,进行,需要有硬件地址变换机构的支持,Page,49,3.,动态重定位分区分配算法,动态重定位分区分配算法，与动态分区分配算法基本上相同；,差别仅在于：在这种分配算法中，增加了,“紧凑”,功能，通常是在找不到足够大的空闲分区来满足用户需求时，进行紧凑。图,4-10,示出了动态重定位分区分配算法框图。,Page,50,可重定位分区分配,动态重定位分区分配算法,在一个分区释放后立即移动,当请求得不到满足时再移动,Page,51,可重定位分区分配,可重定位分区的优缺点,优点,:,解决了可变分区分配所引入的,“,外零头,”,问题。,消除内存碎片，提高内存利用率。,缺点,:,提高硬件成本，紧凑时花费时间。,Page,52,连续分配方式,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,对换（,Swapping,）,Page,53,4.2.5,对换,(Swapping),1.,对换的引入,对换（也称交换）技术，最早用在单用户系统，在内存中仅驻留一道用户作业。所有其它作业都驻留在外存的后备队列上，只调入一个作业进入内存运行；此作业的时间片用完时，该作业调至外存，再将后备队列上的另一个作业调入内存；也让它运行一个时间片的时间，然后又将它调出，再调下一个作业进入内存。因为其效率太低，其,CPU,大约有一半的时间，都处于空闲状态。,Page,54,对换（,Swapping,）,对换的引入,所谓“,对换,”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是,提高内存利用率,的有效措施,如果对换是以整个进程为单位，称为“,整体对换,”或“,进程对换,”,如果对换是以“,页,”或“,段,”为单位进行的，则称为“,页面对换,”或“,分段对换,”又统称为“,部分对换,”,Page,55,4.2.5,对换,(Swapping),1.,对换的引入,对换是以整个进程为单位，便称之为,“整体对换”或“进程对换”,，解决内存紧张问题；,对换是以,“页”或“段”,为单位，则分别称之为,“页面对换”或“分段对换”,，又统称为,“部分对换”,；,为了实现进程对换，系统必须能实现以下三方面的功能：（,1,）,对换空间的管理；（,2,）进程的换出；（,3,）进程的换入。,Page,56,对换（,Swapping,）,对换空间的管理,外存中对换区主要存放从内存中换出的进程，对换空间管理的,主要目标,是,提高进程换入和换出的速度,对换区中空闲盘块的管理,：在系统中配置相应的数据结构，记录外存的使用情况。形式与内存在动态分区分配方式中所用数据结构相似，即用,空闲分区表或空闲分区链,。在空闲分区表中的每个表目中应包含两项，即,对换区的首址,及其,大小,，它们的单位是盘块号和盘块数,对换区的分配采用,连续分配方式,，分配算法可以是,首次适应算法,、,循环首次适应算法,或,最佳适应算法,Page,57,2.,对换空间的管理,由于对对换区的分配，是采用连续分配方式，对换区 的回收操作也可分为下述四种情况，即：,（,1,）回收区与插入点的前一分区,F1,相邻接；,（,2,）回收区与插入点的后一分区,F2,相邻接；,（,3,）回收区还同时与,F1,和,F2,二个分区相邻接；,（,4,）回收区的前、后没有与之相邻接的空闲分区。,对这几种情况的处理方法也与动态分区分配式的方法相同。,回收区,F1,F2,回收区,F2,回收区,F1,回收区,回收区,Page,58,对换（,Swapping,）,进程的换出与换入,进程的换出,系统先,选择,处于,“阻塞”状态,且,优先级最低,的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的,对换区,上。若传送未出现错误，便回收其所占用的内存空间，并对该进程的,进程控制块,做相应的修改,进程的换入,系统应定时地查看所有进程的状态，从中找出,“就绪”状态,但已换出的进程，将其中,换出时间,(,换出到磁盘上,)最久,的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止,Page,59,可重定位分区分配,可重定位分区的优缺点,优点,:,解决了可变分区分配所引入的,“,外零头,”,问题。,消除内存碎片，提高内存利用率。,缺点,:,提高硬件成本，紧凑时花费时间。,Page,60,可重定位分区分配,多重分区,即一个程序可以占据主存中不连续的多个分区,可以解决碎片问题,支持结构化程序设计，操作系统往往把一道作业分成若干片段如子程序、主程序、数据组等。,需要硬件支持（多对界地址寄存器，,重定位寄存器,）,管理复杂,Page,61,可重定位分区分配,多重分区,Page,62,分区的保护,为,了防止一道作业有意或无意地破坏操作系统或其它作业。一般说来，没有硬件支持，实现有效的存储保护是困难的。通常采取：,界限寄存器方式,保护键方式,两种措施，或二者兼而有之。,可重定位分区分配,Page,63,保护过程,防止地址越界,一般由硬件提供一对寄存器：,基址寄存器：存放起始地址,限长寄存器：存放长度,（上界寄存器,/,下界寄存器）,可重定位分区分配,Page,64,界限寄存器保护,60K,访问地址,=124K,则产生访问地址界中断,可重定位分区分配,Page,65,基址、限长寄存器保护,相对地址,限长寄存器的值,则产生访问地址界中断,可重定位分区分配,Page,66,防止操作越权,对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权,即读写保护,可重定位分区分配,Page,67,保护键方式,可重定位分区分配,Page,68,4.3,基本分页存储管理方式,连续分配方式会形成许多“碎片”，通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出很大开销。,根据离散分配时所用基本单位的不同，又可把离散分配方式分以下三种：,1,、分页存储管理,2,、分段存储管理,3,、段页式存储管理,Page,69,存储器管理,连续分配方式,离散分配方式,分页存储管理,分段存储管理,基本分页存储管理,请求分页存储管理,基本分段存储管理,请求分段存储管理,基本分页存储管理,基本分段存储管理,请求分页存储管理,请求分段存储管理,段页式存储管理,虚拟存储器,页面置换算法,Page,70,第四章 存储器管理,程序的装入和链接,连续分配方式,基本分页存储管理,基本分段存储管理,虚拟存储器的基本概念,请求分页存储管理方式,页面置换算法,请求分段存储管理方式,Page,71,4.3,基本分页存储管理方式,在分页存储管理的方式中，如果不具备页面,对换,功能，则称为,基本的（纯）分页管理方式,，它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后方能运行。,Page,72,基本分页存储管理,页面与页表,地址变换机构,两级和多级页表,Page,73,离散分配方式,连续分配方式,要求为一个进程分配连续的内存空间，会形成许多“,碎片,”，,尽管采用,“,紧凑,”,技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高,如果允许一个进程直接分散地装入到许多不相邻接的分区中，称为,离散分配方式,离散分配方式有,分页存储管理方式,和,分段存储管理方式,分页：把用户程序按逻辑页划分成大小相等的部分，称为页或虚页。从,0,开始编制页号，页内地址是相对于,0,编址。,Page,74,页面与页表,页面,页面和物理块,页面：,将一个进程的逻辑地址空间分成若干个大小相等的片，称为,页面或页,，并加以编号，从,0,开始编制页号，页内地址是相对于,0,编址。,物理块：,内存按页的大小划分为大小相等的区域，,称为物理块（物理页面，页框,(frame),，帧），,同样加以编号，如,0,块、,1,块等等,在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“,页内碎片,”,Page,75,页面与页表,页面,页面大小,页面的大小应选择的适中，且页面大小应是,2,的幂，通常为,512 B8 KB,页面若太小,虽然可使内存,碎片减小,，从而减少了内存碎片的总空间，有利于,提高内存利用率,，但也会使每个进程占用较多的页面，从而导致进程的,页表过长,，占用大量内存；此外，还会,降低页面换进换出的效率,如果选择的页面较大,虽然可以,减少页表的长度,，提高页面换进换出的速度，但却又会使,页内碎片增大,。,Page,76,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为,A,，页面的大小为,L,，则页号,P,和页内地址,d,可按下式求得：,例如：其系统的页面大小为,1KB,，设,A=2170B,，则由下式可以求得,P=,，,d=,。,2.,地址结构,分页地址中的地址结构如下：,页号,P,位移量,W,31,12,11,0,页内地址,2,12,=4*2,10,4KB,2,20,=2,10,*2,10,1M,2,122,2048,-,122,Page,77,页面与页表,例：系统页面大小为,1KB,，逻辑地址为,2170,，求页号与页内偏移量,页号,P=INT2170/1024=2,页内偏移量,d=2170 mod 1024=122,第,0,页,01023,第,1,页,10242047,第,2,页,20483071,表示为,(2,122),Page,78,页面与页表,主存分配,把用户程序的任一页分配到内存中的任一物理块，从而实现非连续的内存分配。,问题,如何管理、如何进行地址变换。,Page,79,页面与页表,页表,分页系统中，将进程的每一页,离散地,存储在内存的任一物理块中，为每个进程建立一张,页面映像表,，简称,页表,作用：实现,页号到物理块号的映射,Page,80,页面与页表,页表,列,出了用户程序的逻辑地址与其在主存中的物理地址间的对应关系。,一个页表中包含若干个表目，表目的,自然序号,对应于用户程序中的,页号,，表目中的,块号,是该页对应的,物理块号,。,页表的每一个表目除了包含,指向页框的指针,外，还包括一个,存取控制字段,。,表目也称为,页描述子,。,Page,81,页面与页表,进程,A,页表,0,0,页号,块号,1,1,2,4,3,5,4,8,5,9,程序,A 0,0,程序,A 1,1,程序,B 0,2,程序,B 1,3,程序,A 2,4,程序,A 3,5,程序,B 2,6,程序,B 3,7,程序,A 4,8,内存,程序,A 5,9,程序,A,0,页,1,页,2,页,3,页,4,页,5,页,n,页,程序,B,0,页,1,页,2,页,3,页,4,页,5,页,m,页,进程,B,页表,0,2,页号,块号,1,3,2,6,3,7,Page,82,基本分页存储管理,页面与页表,地址变换机构,两级和多级页表,Page,83,地址变换机构,基本地址变换机构,实现从,逻辑地址,到,物理地址,的转换，将逻辑地址中的,页号,转换为内存中的,物理块号,，通过,页表,来完成,页表的实现,寄存器：变换速度快、成本高，适应小型系统。,页表驻留在内存：速度较低、成本低，适应大系统。,页表大多驻留在内存中，在系统中设置,页表寄存器,PTR(Page Table Register),，在其中存放页表在内存中的,始址,和,页表的长度,进程未执行时，页表的始址和页表长度存放在本进程的,PCB,中，当调度程序调度到某进程时，才将这两个数据装入页表寄存器,Page,84,地址变换机构,地址结构,例如：,32,位地址，,011,为偏移量，,1231,为页号，最大可以有,1M,（,2,20,）页，每页,4KB,（,2,12,）。,页号,P,偏移量,W,31,12,11,0,Page,85,4.3.2,地址变换机构,1.,基本的地址变换机构,每个进程对应一页表，其信息（如长度、始址）放在,PCB,中，执行时将其首地址装入,页表寄存器,。,当进程要访问某个进程逻辑地址中的数据时，分为,页号,和,页内地址,两部分；,如果页号大于或等于页表长度，则表示本次所访问的地址已经超越进程的地址空间。,Page,86,地址变换机构,Page,87,地址变换机构,地址变换过程,指令,LOAD 1,2500,的地址变换过程（块大小为,1024B,）,Page,88,地址变换过程,把虚拟地址,2500,转换成页号,P=2,，位移量,W=452,；,如果页号,2,大于页表大小，则中断；否则继续；,页号,2,与页表起址,1000,运算（,1000+2*20,，设页描述子大小为,20,）得到页描述子地址为,1040,；,从页描述子中读取块号,8,；,根据页描述子的“存取控制”判断该指令是否被允许访问内存，如果不允许，则中断；否则继续；,块号,8,与位移量,452,运算（,8*1024+452=9644,，,1024,为页面大小）得到物理地址,9644,；,执行,LOAD,操作。,地址变换机构,Page,89,2.,具有快表的地址变换机构,由于页表是存放在内存中的，这使,CPU,每次要存取一个数据时，都要,两次,访问内存。,第一次,是访问内存中的页表，从中找到该页的物理块号，将此块号与页内偏移量,W,拼接以形成物理地址。,第二次,访问内存时，才是从第一步所得地址中获得所需数据（或向此地址中写入数据），并将此页号与高速缓存中的所有页码进行比较。,Page,90,地址变换机构,具有快表的地址变换机构,由于页表是存放在内存中，因此每次,CPU,存取一个数据要,两次访问内存,为提高地址变换速度，在地址变换机构中增设一个具有,并行查询能力,的高速缓冲寄存器，又称为“,联想寄存器,”（,Associative Memory,）或“,快表,”，用以存放当前访问的那些页表项,快表通常可存放,16-512,个表项，如果设计得当，命中率可达,90,以上,Page,91,地址变换机构,页表寄存器,页表始址,页表长度,页号,页,内地址,逻辑地址,L,越界中断,块号,b,页表,页号,页号,输,入,寄,存,器,块号,b,b,快表,d,物理地址,具有快表的地址变换机构,Page,92,例：有一页式系统，其页表存放在主存中：,如果对主存的一次存取需要,1.5s,试问实现一次页面访问的存取时间是多少,?,如果系统加有快表,平均命中率为,85%,当页表项在快表中时,其查找时间忽略为,0,试问此时的存取时间是多少,?,Page,93,答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。,页表在主存的存取访问时间,=1.5*2=3(s),增加快表后的存取访问时间,=0.85*1.5+(1-0.85)*2*1.5=1.725(s),Page,94,基本分页存储管理,页面与页表,地址变换机构,两级和多级页表,Page,95,两级和多级页表,两级和多级页表,现代的大多数计算机系统，都支持非常大的逻辑地址空间,(,2,32,2,64,),。在这样的环境下，页表就变得非常大，要占用相当大的内存空间,例如，对于一个具有,32,位逻辑地址空间的分页系统，若规定页面大小为,4 KB,即,2,12,B,，则在每个进程页表中的页表项可达,1M(2,20,),个之多。若每个表项占用,4,个字节,(32bit),，故每个进程仅仅其页表就要占用,4 MB,的内存空间，而且还,要求,是,连续,的,页号,P,偏移量,W,31,12,11,0,2,32,/2,12,=2,20,32/8=4,4*1M=4M,Page,96,两级和多级页表,可以采用这样两个方法来解决这一问题,采用,离散分配方式,来解决难以找到一块连续的大内存空间的问题,只将当前需要的,部分页表项调入内存,，其余的页表项仍驻留在磁盘上，需要时再调入,Page,97,两级和多级页表,两级页表,(Two-Level Page Table),可利用,将页表分页,，并离散地将各个页面分别存放在不同的物理块中，同样要为离散分配的页表再建立一张页表，称为,外层页表,（,Outer Page Table,）,，每个页表项中记录了页表页面的物理块号,2,10,=1024,2,10,=1024,2,12,4KB,2,10,=1024=1K,2,10,=1024=1K,2,12,=4*1024=4K,Page,98,两级和多级页表,1011,1078,0,1,2,1742,n,第,0,页页表,1,4,6,0,1,2,1023,第,1,页页表,114,115,0,1,1023,外部页表,0,1,2,3,4,5,6,7,114,115,1468,第,n,页页表,1468,0,1,2,1023,内存空间,两级页表结构,每个物理块为,4KB,，恰好放一个,1,页页表（,1024,个项，,每项,4BYTE,），共需,1024,个这样的块,Page,99,两级和多级页表,具有两级页表的地址变换机构,Page,100,两级和多级页表,多级页表,对于,32,位的机器，采用两级页表结构是合适的；但对于,64,位的机器，如果页面大小仍采用,4 KB,即,2,12,B,，那么还剩下,52,位，假定仍按物理块的大小,(2,12,位,),来划分页表，则将,余下的,42,位,用于外层页号。此时在外层页表中可能有,4096 G,个页表项，要占用,16384 GB,的连续内存空间。必须采用多级页表，,将外层页表再进行分页,，也是将各分页离散地装入到不相邻接的物理块中，再利用第,2,级的外层页表来映射它们之间的关系,Page,101,具有,64,位地址的分页存储管理,2,42,=4096G,2,10,=1024,212,=4KB,64,两级和多级页表,对于,64,位的计算机，如果要求它能支持,2,64,(=1844744 TB),规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要,Page,102,例,某虚拟存储器的用户编程空间共,32,个页面，每页为,1KB,，内存为,16KB,。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：,页号,物理块号,0,5,1,10,2,4,3,7,则逻辑地址,0A5C,（,H,）所对应的物理地址为：,_,Page,103,0A5C,0000,10,10,0101,1100,页号为,2,，,对应块号为,4,，有：,物理地址：,0001,，,00,10,0101,1100,即：,125C,页号,物理块号,0,5,1,10,2,4,3,7,Page,104,第四章 存储器管理,程序的装入和链接,连续分配方式,基本分页存储管理,基本分段存储管理,虚拟存储器的基本概念,请求分页存储管理方式,页面置换算法,请求分段存储管理方式,Page,105,THE END,