资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 存储器管理,存储器的层次结构,程序的装入和链接,连续分配方式,基本分页存储管理方式,基本分段存储管理方式,虚拟存储器,请求分页存储管理方式,页面置换算法,请求分段存储管理方式,目的:,内存有限,有效地对内存进行管理,4.1,存储器的层次结构,一 多级存储器结构,CPU,寄存器,高速缓存,主存,磁盘缓存,磁盘,可移动存储介质,速度越快,价格越高,容量越小,可执行存储器,,是,OS,存储管理的对象。,信息掉电即丢失。,对它的访问,通过,OS,指令即可,耗费,时间少,访问速度快,辅存,,对它的,访问通过,I/O,设备来实现,二 寄存器与主存,1,寄存器,寄存器是,CPU,的组成部分,可用来暂存指令、数据和地址。容量小,价格十分昂贵。,在,CPU,的控制部件中,包含的寄存器有,指令寄存器,和,程序计数器,;在中央处理器的算术及逻辑部件中,包含的寄存器有,累加器,。,寄存器是内存阶层中的最顶端,也是系统获得操作资料的,最快速途径,,完全能与,CPU,协调工作。寄存器的长度通常以,“,字,”,作为单位。,2,主存储器,内存指的就是,主板,上的存储部件,用于保存进程,运行时的,程序和数据。,CPU,直接,与之通信,从中读数据送入寄存器,或将寄存器的数据写入内存,,内存的,访问速度远低于,CPU,的指令执行速度,为缓和这一矛盾,引入了高速缓存。,三 高速缓存和磁盘缓存,一 高速缓存,在,CPU,和主存之间增加的用于提高系统执行效率的存储器,即,Cache,。速度比内存快,容量介于寄存器与内存之间。,根据程序执行的,局部性原理,,将主存中,经常被访问的信息,存放在,Cache,中。,CPU,取数据时,先从,Cache,中寻找,若没有,再去内存寻找。,高速缓存可有,多级,,一级高速缓存紧靠内存,速度最快,容量最小;二级高速缓存容量稍大,速度稍低。,二 磁盘缓存,由于,磁盘的,I/O,速度远低于对内存,的访问速度,因此将频繁使用的一部分磁盘数据和信息,暂时存放在磁盘缓存中,以提高访问速度。,磁盘缓存,并不实际存在,,依托于固定磁盘,提供对主存空间的扩充。,它的原理是,:将一段时间内常用的磁盘数据放在内存的某个区域;或将,CPU,处理完后需要输出的数据暂存于内存的某个区域。,4.2,程序的装入和链接,从源程序到程序执行,地址空间的概念,重定位的概念,程序的装入,程序的链接,一 从源程序到程序执行,编译:编译程序,由编译程序,(,Compiler,),将用户源代码编译成若干个目标模块。,链接:链接程序,由链接程序(,Linker,),将编译后形成的一组目标模块,以及它们所需要的库函数链接在一起,形成装入模块。,装入:装入程序,由装入程序,(,Loader,),将装入模块复制到内存中。,库,汇编,编译,主,子1,子2,目标模块,链接程序,装入模块,库,主,子1,子2,装入程序,内存,库,主,子1,子2,二 地址空间,物理(,绝对,)地址,程序执行,每个内存单元的固定顺序地址(编号)。,由物理地址组成的空间集合称为物理空间。,逻辑(,相对,)地址,装入(汇编编译),被链接装配(或汇编、编译)后的目标模块所限定的地址的集合;,相对于某个基准量(通常为:,0,)的编址。,由逻辑地址构成的空间集合称为逻辑空间。,物理地址,内存,00000,00001,00002,.,.,.,01000,01FFF,主,子1,子2,主,子1,子2,逻辑地址,装入模块,000,.,.,.,DFF,主,子1,子2,相对地址,源程序,/,单个目标模块,000,5FF,000,3FF,000,3FF,三重定位,重定位,概念:把程序装入内存时,,修改,程序中所有与地址有关的项。,逻辑地址,变换,为物理地址,。,重定位的类型,静态,重定位:程序执行前,一次性地变换地址并装入内存。,动态,重定位:处理机每次访问内存时,由,动态地址变换机构,(硬件)自动执行地址变换。,作业地址空间 内存空间,装入,365,LOAD 1,2500,5000,2500,1000,365,LOAD 1,2500,15000,12500,10000,11000,365,LOAD 1,12500,15000,12500,10000,11000,内存地址空间,四 程序的装入,就是把链接好的装入模块装入“内存”。,装入方式,绝对装入,可重定位装入,(静态重定位),动态运行时装入,(动态重定位),绝对装入方式,要求:,事先清楚,程序将驻留在内存的什么位置,该内存地址可由程序员给出,也可由编译程序申请。,概念:装入程序直接按照装入模块中的地址,将程序和数据装入内存。,逻辑地址与内存地址相同,,无须进行地址变换。,局限:仅可应用于,单道,程序环境中,静态重定位,在装入程序将,装入模块装入内存,时,进行逻辑地址到物理地址的转换,数据地址,和,指令地址,都要做相应修改,地址变换在程序装入内存时一次完成,一旦程序装入内存,,不允许它在内存空间移动,。,动态重定位,装入程序将装入模块装入内存后,并不立即将相对地址转换为绝对地址,而是将,地址转换推迟到程序执行时,才进行。,为避免程序运行时,进行地址转换影响指令执行的速度,需要,重定位寄存器,的支持,五 程序的链接,链接:,把一个程序相关的一组,目标模块,和,系统调用,模块(库函数)链接形成一个整体,装入模块,的过程。,具体工作:,对相对地址的修改;变换外部调用符号。,链接方式:,静态链接,装入时动态链接,:便于修改和更新;便于共享。,运行时动态链接,:最小化快速装入,节省内存。,静态链接方式,程序运行前,,先将各目标模块及它们所需要的库函数,,链接,成一个完成的可装入模块,以后不再拆开。,要做的两项工作:,1,修改相对地址,2,将,外部调用符号,修改成相对地址,模块,A,Call B;,Return;,0,L-1,模块,B,Call C;,Return;,0,M-1,模块,C,;,Return;,0,N-1,链接,模块,A,JSR“L”;,Return;,0,L-1,模块,B,JSR“L+M”;,Return;,L,L+M-1,模块,C,;,Return;,L+M,L+M+N-1,装入模块,装入时动态链接,并不事先链接成一个可装入模块,源程序经过编译得到的目标模块,在,装入内存时边装入边链接,。,即在装入一个目标模块时,若,发生外部调用事件,,则由装入程序找出相应的外部目标模块,进行链接并装入内存。此时,也应修改目标模块中的相对地址。,优点:,便于修改、更新和共享,将对某些模块的,链接推迟到程序执行时,进行。,即,在程序执行过程中,发现一个被调用模块尚未调入内存,立即由,OS,去找到该模块,并将其装入内存,链接到调用者模块上。,优点,:程序执行时,未用到的模块,都不进入内存,不进行链接。,加快,了程序的装入过程,,节省,了内存空间。,运行时动态链接,4.3,连续分配方式,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,对换,连续分配方式:,为用户程序分配一个,连续,的内存空间。曾在,20,世纪,60-70,年代,被广泛应用,至今仍在内存分配方式中占有一席之地。,一 单一连续分配,单一连续分配的基本思想,把内存分为,系统区,和,用户区,,系统区供,OS,使用,通常放在低址部分;系统区以外的全部内存空间是用户区。,单一连续分配的特点,只能用于,单用户、单任务,的,OS,中。,软件简单,硬件要求低(,无需存储保护,),实例,CP/M,,,MS-DOS,,,RT-11,DOS,内存分区,CP/M,内存分配,系统参数区,BIOS CCP,BDOS,系统区,系统区,二 固定分区分配,基本思想,将内存的用户空间划分成,若干个固定大小的区域,,在每个分区中只允许装入,一道,作业。,特点:,有几个分区,则允许几道作业并发执行,当有空闲分区时,则从外存后备队列选择一个适当大小的作业进入该分区。,划分分区的方法,分区大小,相等,分区大小,不相等,缺乏灵活性:,作业小,造成内存空间的浪费;,作业大,一个分区装不下,作业无法运行。因,此,常用于,工控系统,中。,将用户区划分成具有,多个较小,的分区、,适量的,中等分区,及,少量的大分区,,以满足不同作业的,需求,内存分配管理,分区使用表(,MBT,),分区,按大小排队,由内存分配程序,检索分区使用表,,找到符合要求的分区。,区号,/,键,大小,位置,状态,1,8 K,512K,正使用,2,32 K,520K,正使用,3,32 K,552K,未使用,4,128 K,584K,未使用,5,512 K,712K,正使用,系统区,分区,1,分区,4,分区,5,分区,2,分区,3,系统区,作业,3,分区,4,作业,2,作业,1,分区,3,存储保护与重定位,(地址转换),每个分区(一道程序)对应一对,界地址寄存器,:上,/,下限寄存器。,采用,静态重定位,方式,即由链接,/,装入程序完成。,优缺点,优点:,简单,要求的硬件支持少(一对,R,);,缺点:,存在大的碎片(内碎片),,主存利用率低。,碎片,很多小的内存空间,内碎片,碎片处于,分区内部,外碎片,碎片处于,分区与分区之间,三 动态分区分配,思想,位置和大小都不固定,,根据进程的实际需要,,动态分配内存空间,又称可变分区分配。,例子:一计算机系统有,2560KB,内存,采用可变分区模式管理,,OS,占低地址的,400KB,空间,用户内存为,2160KB,。,如图所示:,OS,P1,OS,P1,P2,OS,P1,P2,P3,OS,P1,P4,空闲,P3,OS,注意,1.,可变分区模式下,,刚开始,,,OS,就绪,但任何用户程序未进入内存前整个,用户内存区是一大空间,。已占用区和空闲分区并不是绝对的。,2.,必须用某种,数据结构,来记录分区的情况。,3.,程序进入内存时的,例行工作,就是分配空闲区和装入程序,并修改相应的数据结构。,4.,一旦一个内存分区被分配给一个进程,该进程被装入时需,重定位,。,数据结构的两种形式,空闲分区表,空闲分区链,空闲分区表用于,记录每个空闲分区,的情况,,每个空闲分区占一个表目,表目中包括分,区序号、分区始址、分区大小等项目,利用,双向链表,形式,记录空闲分区的使用,情况。,每个空闲分区除记录该分区的基本情况外,,还要在头部和尾部分别增加,前向指针,和,后向,指针,,以实现对分区的双向链接,便于检索。,存储分配算法,首次适应算法,循环首次适应算法,最佳适应算法,最快适应算法,快速适应算法,首次适应算法,数据结构,-,空闲分区链,按照,地址递增,的次序链接,算法,-,从链首开始顺序查找,把,找到的第一个能满足申请者要求,的空闲区分配给申请者。若空闲区比作业长度大,则,分割,该空闲区:一部分分配给作业,剩余部分空闲。,若找不到,则内存分配失败,返回。,特点,-,优先,利用内存中,低址,部分的,空闲,分区,优点,-,保留,了高址部分的,大空闲区,,留给以后到达的大作业。,缺点,-,低址,部分不断被划分,,留下,很多难以利用的,小碎片,-,每次查找都是从低址开始,,增加了查找的开销,循环首次适应算法,改进算法,-,分配内存空间时,不再是从链首开始查找,而是,从上次找到的空闲分区的下一个空闲分区开始查找,,直到找到一个能满足要求的空闲分区,然后从中划出与请求大小相等的内存空间分配给作业。,-,采用,循环查找,方式,如果找到链尾仍未找到合适的分区,则返回链首继续查找。,改进数据结构,-,增加一,起始查询指针,,指示下一次起始查询的空闲分区。,优点,-,内存的,空闲分区分布更均匀,,减少了查找空闲分区的时间开销,缺点,-,缺乏大的空闲分区,最佳适应算法,数据结构,-,空闲分区链,空闲分区,按容量由小到大,排列,算法,-,为作业分配内存时,把能,满足要求的最小的空闲分区,分配给作业,缺点,-,每次分配后剩余部分都是最小的,因此会留下许多,难以利用的小碎片,最坏适应算法,数据结构,-,空闲分区链,空闲分区,按容量由大到小,排列,算法,-,为作业分配内存时,扫描空闲分区链表,挑选最大的空闲分区分割给作业。,缺点,-,缺乏大的空闲分区,优点,-,每次分配后剩下的空闲区不会太小,,产生碎片的几率小,-,只要看第一个分区是否满足需要即可,,查找效率很高,快速适应算法,数据结构,1,多个空闲分区链表,空闲分区按容量大小分类,每类对应一个链表。,2,管理索引表,每个表项对应一个分区类型,并记录该链表的表头指针,算法,根据进程长度,寻找到能容纳它们的最小空闲区链表,取下第一块进行分配即可。,优点:,1,)查找效率高,2,)分配空闲分区时,不对分区进行分割,能保留大的分区,,不会产生外部碎片,缺点:,1,)归还分区时算法复杂,系统开销大,2,)分配给进程的分区与进程要求的大小不完全一致,,产生内碎片,。,内存分配,1,检查分区大小与所需空间大小是否“,匹配,”:,M.size,U.size,M.Size,-U.Size,Size,(,不再分割的小分区的尺寸),2,剩余部分,挂接到空闲分区链表上。,查找空闲分区链表第一项,检索完否?,m.sizeu.size?,m.size-u.sizesize?,划出,u.size,大小的分区,修改有关的数据结构,返回,将该分区从链表中移出,继续检索下一个表项,Y,Y,Y,N,N,N,回收内存,回收区,与插入点的前一个空闲分区,相邻接;,回收区,与插入点的后一个空闲分区,相邻接;,回收区,与插入点的前后两个空闲分区,相邻接;,回收区,不与任何一个空闲分区,相邻接;,合并,修改前一分区的大小,合并,修改首地址和大小,合并,首地址为前一分区首地址,,修改大小,去掉后一分区表项,增加新的表项,填写首地址和大小,插入链表中的合适位置,OS区,Job1,Job2,Job3,Job4,Job5,空闲分区链,头指针,Job7,Job6,四可重定位分区分配,动态重定位的引入,随着系统接收的作业的增加,内存中连续的大块分区不复存在,产生了大量的,“碎片”,。,新的作业无法装入,到每个“碎片”小分区上运行,但所有碎片的空间总和可能大于需求。,通过“拼接”,/“,紧凑,”,/“,紧缩”,/“”,澄清“来实现,”,程序的浮动“,/”,动态重定位“。,紧凑,通过移动内存中作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法,称为“拼接”或“紧凑”。,动态重定位的实现,必须由硬件地址变换机构支持实现,重定位,R,重定位寄存器,:存放程序存放的起始地址。,当系统对内存进行了“紧凑”而使若干程序在内存发生移动后,不需要对程序做任何修改,,只要用该程序在内存的新起始地址,去置换原来的起始地址即可,。,可重定位分区分配示意图,OS区,Job2,Job4,Job3,Job1,Job5,Job6,Job7,“,零头”,碎片,OS区,Job2,Job4,Job3,Job1,Job5,Job6,Job7,OS区,Job2,Job4,Job3,Job1,Job5,Job6,Job7,“,零头”,碎片,处理机一侧,存储器一侧,作业,J,内存,365,LOAD 1,2500,5000,2500,1000,365,LOAD 1,2500,15000,12500,10000,11000,2500,相对地址,10000,重定位,寄存器,优缺点分析,优点:消除了“碎片”,,提高了内存利用率,同时提高了系统效率。,缺点,:需要,动态重定位“硬件”机构,支持,增加了系统成本,并轻度降低了程序执行速度,“紧凑”处理,增加了系统开销。,动态重定位分区分配算法流程,查找空闲分区链表第一项,找到连续可用分区?,按动态分区方式,进行分配,修改有关的,数据结构,返回分区号,及首址,进行紧凑,形成连续空闲区,Y,Y,N,N,请求分配,u.size,分区,找到离散可用分区?,修改有关的,数据结构,无法分配,返回,五对换,引入原因:,内存中的某些进程由于等待事件发生而阻塞,但,占用了大量的内存空间,;外存上有许多作业等待调度,因,无内存而不能运行,。,为解决这一矛盾,避免系统资源的浪费,引入了“对换”机制。,对换的概念,把内存中,暂时不能运行的,进程或者暂时不用的程序和数据调出到外存上,以便,腾出,足够的内存空间,把,已具备运行条件,的进程或进程所需要的程序和数据调入内存。,对换是,提高内存使用率,的有效手段。,实现方法,通过外存缓冲,以,进程为单位“滚进滚出,”。一个作业的所有进程不必同时位于内存中。,对换空间的管理,把内存分成,文件区,和,对换区,。前者用来存放文件,后者用来存放兑换出来的进程。,对换区采用,连续分配方式,,空闲盘块的组织、分配和回收与动态分区方式中内存空间的分配与回收方式基本相同。,进程的换出与换入,对换的时机,:创建新进程而内存不足时。,进程的换出,选择处于,阻塞状态且优先级最低,的进程作为换出进程,启动磁盘,将该进程的程序和数据送到磁盘的对换区上,回收该进程占用的,内存空间,。,进程的换入,系统定时查看所有进程的状态,从中找出,“就绪”状态但已换出的进程,,将其中,换出时间最久,的进程作为换入进程,将其换入。,4.4,基本分页存储管理方式,有碎片,系统开销大,连续分配方式,紧凑,离散分配方式,分页,分段,基本分页,请求分页,基本分段,请求分段,页面与页表,地址变换机构,两级和多级页表,基本分页的特点,一页面与页表,页面,页面:逻辑地址空间分成大小相同的页,块(页框):内存空间分成与页面大小相同的块,页面和物理块按顺序编号,页面大小,:,2,n,Bytes,一般在:,512B 8/32K,页面过小,页数过多,页表过长,占用大量内存;,页面过大,内碎片增大,浪费内存,地址结构,逻辑地址物理地址,页表,数据结构:,页号、块号,、存取控制项,页表的作用:实现从页号到物理块号的,地址映射。,位移量,d,物理块号,P,位移量,W,页号,P,11,12,31,每页,4 k,,最多,1M,页,P=,INT,(A/L),w=A,mod,L,0,1,2,3,4,5,6,7,8,9,11,10,内存,第,0,页,第,1,页,第,2,页,第,3,页,第,4,页,第,5,页,第,6,页,用户作业,0,2K-1,第,2,页,(页长,2K,),0,2K-1,4,号页架,(页长,2K,),0,1,2,3,4,5,6,7,8,9,11,10,内存,第,0,页,第,1,页,第,2,页,第,3,页,第,4,页,第,5,页,第,6,页,用户作业,块号,页号,10,5,11,6,9,4,5,3,3,2,7,1,2,0,页表,0000,0000,0000,0000,0101,0001,0000,0000,第,5,页,256,字节的物理地址(页大小:,4K,),第,0,页,第,1,页,第,2,页,第,3,页,第,4,页,第,5,页,第,6,页,第,0,页,第,1,页,第,2,页,第,3,页,第,4,页,第,5,页,第,6,页,二 地址变换机构,基本,的地址变换机构,页表存放在内存系统区,的一个连续空间中;,PCB,和,页表寄存器,PTR,中存有,页表的首地址和页表长度,;,查询页表:,页表首地址,+,页号,x,表项长度,;,地址映射,从逻辑地址到物理地址的变换过程。,页表始址,页表长度,页表寄存器,=,页表,块号,页号,5,3,3,2,7,1,2,0,5,2018,物理地址,3,2018,逻辑地址,越界中断,具有,快表,的地址变换机构,引入,:CPU,存取数据需要两次访问内存,降低 了,CPU,的处理速度,联想寄存器,Cache,;,空间大小:几,K,到几百,K,,,部分表项(,16512,个,),;,原则,:,先查快表,再查页表,;,地址映射过程。,页表始址,页表长度,页表寄存器,页表,块号,页号,5,3,3,2,7,1,2,0,3,1250,物理地址,2,1250,逻辑地址,越界中断,快表,块号,页号,20,5,11,4,5,3,2,0,输入寄存器,当进程访问一页时,系统将页号与快表中的所有项进行并行比较。若,访问的页在快表中,,即可立即进行地址转换。,当,被访问的页不在快表中,时,就要将由慢表找到的内存块号与页号填入快表中,若快表已满,则置换其中最近未被访问的项。,另外,在设置快表的情况下,硬件地址转换机构在进行地址变换时,,同时开始两个变换过程,。,一个是,利用主存页表进行的,正常变换,过程,,另一个,是利用快表进行的,快速变换,过程。一旦快表中有与查找的页号相符合时,则立即停止正常的访主存页表过程。并将快表中的块号与,CPU,给出的页内位移相拼接,得到访问主存的绝对地址,从而结束了快表的查找工作。,三 两级和多级页表,两级页表,解决,大页表占用大的连续存储空间,的问题;,关于,“页表”的分页,存放“页表”,外层页表,;,逻辑地址:,外层页号,+,外层页内地址,+,页内地址,多级,页表,10,位,10,位,12,位,外部页表,块号,页号,3,2,1078,1,1011,0,页表分页,112,2,3,1,2,0,2,1,113,0,0,1,2,3,112,113,1011,外部页表,外部页表,寄存器,物理地址,外部页号,P1,外部页内地址,P2,逻辑地址,页内地址,d,块号,页表,四 基本分页的特点,优点:,存在页内碎片,但碎片相对较小,内存利用率较高;,实现了离散分配,消除了程序浮动;,缺点:,需要专门的硬件支持,尤其“快表”;,内存访问的效率下降。,不足:,不能实现真正的共享,不支持动态链接。,4.4,基本分段存储管理方式,基本分段管理思想的引入,基本原理,地址变换,分段与分页的主要区别,段页式存储管理方式,1,基本分段管理思想的引入,为用户提供一个方便灵活的程序设计环境,而提出来的。,页式管理中,一个页面中可能装有,2,个不同的子程序段的指令代码,,不能通过页面共享来达到共享一个逻辑上完整的子程序或数据块,程序通过分段,(segmentation),划分为多个模块,如代码段、数据段。,可以分别,编写和编译,可以针对不同类型的段采取,不同的保护,可以按段为单位来进行,共享,,包括通过,动态链接进行代码共享,2,分段系统的基本原理,将进程的逻辑地址空间按内容或函数关系,划分为若干个段,(segment),,,每个段定义一组,逻辑上完整,的程序或数据,如一个进程可以被划分为主程序段、子程序段、数据段、堆栈段等。,程序加载时,,以段为单位,分配其所需的内存(内存分区),每个段分得一个连续的分区。所有段都被装入到存储器的可用区域中,并,建立一个段表,每个段是一个,首地址为,0,的,连续的一维线性空间,段长可以动态增长。,段的大小不需要相等,。,基本原理,内存,第,0,段,第,1,段,第,2,段,第,3,段,用户作业,段表,基址,段长,150K,35K,500K,9K,300K,20K,100K,42K,3,2,1,0,段号,第,0,段,第,1,段,第,2,段,第,3,段,段表,段号、段基地址、段的长度、段状态等,段表寄存器,(段表始址和段表长度),利用段表实现地址映射,地址变换及变换机构,基本分段管理的,地址变换,与基本分页管理的变换机构和过程类似。,段表寄存器,存放段表的起始地址和段表长度;,越界访问控制,逻辑地址的段号与段表长度比较;,段内地址与段表中保存的段长比较;,段表始址,段表长度,段表寄存器,153705,物理地址,段号,3,105,逻辑地址,越界中断,段表,基址,段长,150K,35K,500K,9K,300K,20K,100K,42K,3,2,1,0,段号,内存,问题,:每次访问数据,都要两次访问内存,降低了计算机的速率。,解决的办法,:增加联想寄存器。,分段与分页的主要区别,页是信息的,物理,单位,段是信息的,逻辑,单位;,页的大小固定,段的大小动态变化;,分页系统中的逻辑地址空间是一维的,分段系统中的是二维的。,分页系统中不易实现“共享”和“动态链接”,分段则很容易。,内存,段表,基址,段长,180K,100K,300K,20K,100K,42K,2,1,0,段号,第,0,段,Job1,数据,用户,1,编辑进程,第,0,段,Job2,数据,用户,2,编辑进程,基址,段长,380K,30K,300K,20K,100K,42K,2,1,0,段号,第,0,段,Job1,数据,Job2,数据,5,段页式存储管理方式,分页:提高内存利用率,分段:更好的满足用户需要,分页,+,分段?,段号,S,段内页号,P,页内地址,W,段页式存储管理方式,基本思想,结合分页和分段技术;,发挥出分页和分段管理方式各自的优点。,原理,对内存进行分页(物理块,/,页架);,对用户作业先分段,各段再分页。,地址结构与地址变换,段号、段内页号、页内地址三部分,段表和页表,主程序段,数据段,子程序段,段表始址,段表长度,段表,1,3,0,2,1,1,1,0,页表始址,页表长度,状态,段号,段表寄存器,页表,0,3,1,2,1,1,1,0,存储块号,状态,页号,页表,1,1,1,0,存储块号,状态,页号,利用段表和页表实现地址映射,段表始址,段表长度,段表寄存器,逻辑地址,页号,P,页内地址,段号,S,段表,块号,块内地址,物理地址,越界中断,页表,xxxx,2,xxxx,1,xxxx,0,页表始址,段号,2,1,0,块号,页号,段页式系统中的地址变换机构,段页式存储管理的优缺点,同时具备分段和分页管理的优点:,分散存储,,内存利用率较高;,便于代码或数据共享,,支持动态链接等。,访问效率下降:一次访问转换成了,三次,访问。,4.5,虚拟存储器,虚拟存储器的,引入,虚拟存储器的,实现方法,虚拟存储器的,特征,1,虚拟存储器的引入,内存空间的限制与内存的扩充方法,内存空间装不下的大作业如何运行?,作业量大时,如何允许更多的作业并发?,物理扩充:增加硬件投入;,虚拟存储器技术:,利用海量外存的内存“空间”扩展。,常规存储器管理方式的特征,一次性,驻留性,程序执行的局部性原理,程序在执行时将呈现局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分;相应地,它所访问的存储空间也局限于某个区域。,局限性表现在下述两个方面,时间局部性:,一条指令的一次执行和下次执行,一个数据的一次访问和下次访问都集中在一个,较短时期内,;,空间局部性:,当前指令和邻近的几条指令,当前访问的数据和邻近的数据都集中在一个,较小区域内,。,局部性的具体表现,程序在执行时,,大部分是顺序执行的指令,,少部分是转移和过程调用指令。,过程调用的,嵌套深度一般不超过,5,,因此执行的范围不超过这组嵌套的过程。,程序中存在,相当多的循环结构,,它们由少量指令组成,而被多次执行。,程序中存在,相当多对一定数据结构的操作,,如数组操作,往往局限在较小范围内。,虚拟存储器的定义,虚拟存储器是指具有,请求调入,功能和,置换,功能,能从,逻辑,上对内存容量加以,扩充,的一种存储器系统。,物理上不存在,,但可以使用(访问);,允许作业部分装入,,需要时再临时装入所需的部分,直到作业退出,某些部分也有可能没被装入过。,虚拟存储器的实现方法,必须建立在,离散分配,的内存管理技术基础上。,分页请求系统,基本分页系统,+,请求分页功能,+,页面置换功能,硬,/,软件支持:请求分页的页表机制、缺页中断机构、动态地址变换机构,请求分段系统,基本分段系统,+,请求分段功能,+,分段置换功能,;,硬,/,软件支持:请求分段的段表机制、缺段中断机构、动态地址变换机构。,虚拟存储器的特征,多次性,一个作业被分成多次调入内存运行;,对换性,允许在作业的运行过程中进行换进、换出;,虚拟性,能从逻辑上扩充内存容量,是用户“看到”的内存容量远大于实际大小。,该特征是以上两个特征为基础的。,4.6,请求分页存储管理方式,请求分页中的硬件支持,内存分配策略和分配算法,调页策略,请求分页存储管理的基本原理,系统自动地将作业的地址空间,分页,,将系统的主存空间分块,页与块等大小。,在作业运行前,只把初始需要的一部分页面装入内存块里,运行中需要访问自己地址空间中的但当前不在内存的页面时产生,缺页中断,,由缺页中断服务程序将所需的页面调入内存。,若此时内存中没有空闲物理块安置请求调入的新页面,则系统按预定的,置换策略,自动选择一个或一些在内存的页面,把它们换出到外存。,这里的,请求调入,和,置换,功能都是比实分页存储管理增加的内容,是实现虚拟存储的主要功能,请求分页中的硬件支持,页表机制,用于地址转换;,页表表目需要增加,外存块号,、,状态位,、,访问位,或,访问字段,、,修改位,、,存取控制字段,等。,外存块号,指出该页在外存的地址,供调入该页时用;,状态位,指示该页是否在内存,供程序访问时用,也是检查是否缺页的标志位;,访问位或访问字段,则是该页被访问过的标志或该页被访问过的次数;,修改位,表示该页是否被修改过;,存取控制字段,则是用来限制页面被安全共享的。,缺页中断机构,所要访问的,页不在内存,时,便引发一次缺页中断;,与常规中断的不同之处:,在,指令执行期间,产生和处理中断信号;,一条指令在执行期间,可能,产生多次缺页中断,。,地址变换机构,首先检索快表,,若找到,修改表项中的访问位,然后利用表项中给出的页架号和页内地址,形成物理地址。,如果在快表中未找到相应的页表项,,检索内存中的页表,,察看页表中的状态位,若该页已经调入内存,填写快表,当快表满时,应淘汰一个页表项;,若该页尚未调入内存,产生缺页中断,请求,OS,把该页调入。,内存分配策略和分配算法,最小物理块,(页架),数,的确定,保证进程正常运行所需的最少物理块数;,与指令的格式、功能和寻址方式有关。,页架的分配策略,固定分配局部置换,1,为进程分配,固定,数目的物理块,并在进程运行期间保持不变;,2,发生缺页时,从,该进程,在内存的页面中选择一个页面换出。,3,难点:,难于确定某个进程的物理块数。,可变分配全局置换,1,系统中的每个进程占有,一定数量,的物理块,2,OS,保持一个,空闲物理块队列,3,发生,缺页,时,从,系统空闲物理块,队列中,分配给请求进程,4,当空闲队列空时,从内存中选择一页调出,,该页可能是系统中任一进程的页。,可变分配局部置换,1,进程缺页时,,只能从该进程,在内存的页面中,选择一页调出,,不会影响其它进程,2,当进程,缺页率较高或较低,时,能由,OS,对其占据的物理块数,加以调整,。,物理块分配算法,平均分配算法,将系统中所有可供分配的页架,平均分配给各个进程。,按比例分配算法,根据进程的大小按比例分配页架的算法。,考虑优先权的分配算法,将物理块分成两部分,一部分按比例分配,另一部分按优先权高低进行分配。,B,i,=(,s,i,/s,)*m,调页策略,何时调入页面的问题,预调页策略:首次调入内存时,请求调页策略:运行中的发生缺页现象时,预调页策略,也称先行调度,即一页面被访问前就已经预先置入内存,以减少今后的缺页率。,主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用,即每次缺页时装入多个页面。,优点:,提高调页的,I/O,效率。,缺点:,基于预测,若调入的页在以后很少被访,问,则效率低。常用于程序首次装入时的调页。,请求调页策略,当发生页面故障时进行调度,即当进程访问不在内存的页面引发缺页中断时,由系统根据这种访问请求把所缺页面装入内存。,优点:,由请求调入策略装入的页一定会被访问,比较容易实现。在目前的虚拟存储器中,大多采用此策略。,缺点:,每次仅调入一页,增加了磁盘,I/O,的启动频率。,从何处调入页面的问题,1,对换区空间足够大,,则全部从对换区调入所需要的页面,2,缺少足够的对换区空间,,则不会被修改的文件从文件区调入;被修改的文件从对换区调入。,页面的调入过程,响应中断,保存,CPU,环境,查找页表(快表),得到该页在外存中的块号,启动磁盘,I/O,读入,如果内存已满,先置换,再调入,最后修改页表(快表)对应项的内容。,4.7,页面置换算法,最佳置换算法(,Optimal,),先进先出置换算法,(FIFO),最近最久未使用(,LRU,),置换算法,Clock,置换算法,最少使用(,LFU,),置换算法,页面缓冲置换算法,(PBA),选择换出页面的算法,一 最佳淘汰算法,OPT,这是,Belady,于,1966,年提出的一种理论上的算法。该算法,每次都淘汰以后永不使用的,或者过最长的时间后才会被访问的页面,。,显然,采用这种算法会保证最低的缺页率,但它是,无法实现,的,因为它必须知道页面“将来”的访问情况。不过,该算法仍有一定意义,可作为衡量其他算法优劣的一个,标准,。,假定系统为某个进程分配了,三个,物理块,进程的访问顺序为,7,,,0,,,1,,,2,,,0,,,3,,,0,,,4,,,2,,,3,,,0,,,3,,,2,,,1,,,2,,,0,采用,OPT,淘汰算法:,7 7,2,2 2 2 2 2 2 2 2 2 2 2 2,0 0 0 0 0 0,4,4 4,0,0 0 0 0 0,1 1 1,3,3 3 3 3 3 3 3,1,1 1,7,,,0,,,1,,,2,,,0,,,3,,,0,,,4,,,2,,,3,,,0,,,3,,,2,,,1,,,2,,,0,二 先进先出淘汰算法,FIFO,这是最早出现的淘汰算法。,总是,淘汰最先进入内存的页面,。它实现简单,只需把进程中已调入内存的页面,按先后次序链成一个队列,并设置一个所谓的,替换指针,,使它总是指向内存中最老的页面。,缺点:效率不高,,因为它与进程实际的运行规律不相适应,比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。,出现,bleady,现象。,采用,FIFO,淘汰算法,7 7,2,2 2 2,4,4 4,0,0 0 0 0 0,0 0 0 0,3,3 3,2,2 2 2 2,1,1 1,1 1 1,1,0,0 0,3,3 3 3 3,2,2,7,,,0,,,1,,,2,,,0,,,3,,,0,,,4,,,2,,,3,,,0,,,3,,,2,,,1,,,2,,,0,Belady,现象:,采用,FIFO,算法时,如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多,缺页率反而提高的,异常现象,。,Belady,现象的描述:,一个进程,P,要访问,M,个页,,OS,分配,N,个内存页面给进程,P,;,对一个访问序列,S,,,发生缺页次数为,PE,(,S,N,)。当,N,增大时,,PE(S,N),时而增大,时而减小。,Belady,现象的原因:,FIFO,算法的,置换特征与进程访问内存的动态特征是矛盾的,,即被置换的页面并不是进程不会访问的。,三 最近最久未使用算法,(LRU,),根据页面调入内存后的使用情况,选择,内存中最久未使用的页面,被置换。利用“最近的过去”作为“最近的将来”的近似,性能接近最佳算法。,OPT,算法使用页面将要被访问的时间,,LRU,算法使用页面最后一次被访问的时间。二者唯一的差别是:,OPT,是向,后,看的,而,LRU,是向,前,看的,。,7 7,2,2 2 2,4,4 4,0,0 0,1,1 1,0 0 0 0,0 0 0 0,3,3 3 3,3,3,0,1 1 1,3,3 3,2,2 2 2 2 2,2,2,7,,,0,,,1,,,2,,,0,,,3,,,0,,,4,,,2,,,3,,,0,,,3,,,2,,,1,,,2,,,0,LRU,的两个实现算法:,计时法:,对于每一页面增设一个,访问时间计时器,,每当一个页面被访问时,当时的绝对时钟内容被拷贝到对应的访问时间计时器中,这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时,选取访问时间计时器的值最小的页面。(,书中是移位寄存器),为了记录进程在内存中各页的使用情况,为每个页面配置一个,移位寄存器,R=R,n-1,R,n-2,R,n-3,R,2,R,1,R,0,当进程访问某个物理块时,要,将相应寄存器的最高位置成,1,。然后,定时信号每隔一定时间将寄存器,右移,一位。
展开阅读全文