软件技术_存储管理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章存储管理,本章基本内容与要求,基本内容,存储器层次结构,存储管理任务,实存储管理,虚拟存储管理,要求,掌握存储管理任务,掌握存储管理、实存储管理、虚拟存储管理,了解存储器层次结构,第一节 存储器层次结构,存储管理目的,1、充分利用内存，为多道程序并发执行提供存储基础,2、尽可能方便用户使用,自动装入用户程序,用户程序中不必考虑硬件细节,3、系统能够解决程序空间比实际内存空间大的问题,4、存储保护与安全,第二节 存储管理任务,主存空间分配:,动态地为不断进进出出的作业分配内存空间。,地址映射:,保证作业运行中能够正确的定位。,内存保护:,保证作业的进程之间既能互相通信而又不互相干扰。,内存“扩充”:,使空间需求量大于用户区容量的作业也能够正常运行。,1.,主存空间分配,合理分配，避免冲突；,算法得当，提高效率；,及时回收，循环利用。,2.,地址映射,目标程序,内,存,地址空间,存储空间,0,x,0,640,k,系统区,存放操作系统,目标程序,用户区,存放用户作业,绝对地址,：主存储器以字节为编址单位，容量为,n,的主存储器中，每个单元有唯一的编号，从0到,n-1，,这个唯一的编号就是主存储器的,绝对地址(物理地址),。,绝对地址,逻辑地址,:在多道程序设计的系统中，操作系统为了方便用户，就允许每个用户都认为自己的作业的程序和数据存放在地址是0开始的连续空间中。这样用户程序中使用的地址就是,逻辑地址(相对地址),。,相对地址,重定位:,当用户程序调入内存时，必须把逻辑地址转换成绝对地址，同时包括对程序中与地址有关的指令进行修改，这一过程叫,“,重定位,”,或,“,地址转换,”,。,重定位的方式有两种:,静态重定位,动态重定位,地址,转换,静态重定位,在装入一个程序时，把程序中的指令地址和数据地址全部转换成绝对地址。这种转换工作是在程序,开始前集中完成,的，在程序执行过程中无需再进行地址转换。所以称为“静态重定位”。,使用一对界地址寄存器，分别存放该程序的起始和终止地址.,x,逻辑地址空间,L,D,上界,下界,界地址寄存器,D,x,L,物理地址空间,x =x +D,物理地址 逻辑地址 下界地址,D=xL,动态重定位,在装入一个程序时，不进行地址转换，而是直接把程序装到分配的主存区域中。在程序执行过程中，每当执行一条指令时都由硬件的地址转换机构转换成绝对地址。这种方式的地址转换是在,程序执行时动态完成,的，所以称为动态重定位。,动态重定位由软件（操作系统）和硬件（地址转换机构）相互配合来实现。,2.,地址映射,程序的起始地址都是从“,0,”开始的，程序中的其它地址都是相对于起始地址计算的，该地址被称为,逻辑地址（或相对地址）。,由这些地址所形成的地址范围称为（作业）,地址空间,。,主存单元的编号称为,物理地址（或绝对地址）,由主存中的一系列单元所限定的地址范围称为,存储空间,。,相对地址到绝对地址的转换，同时程序中与地址有关的指令的修改，这一过程叫做,地址重定位,。,静态重定位,在程序装入时进行,由装配程序进行地址转换,动态重定位,是在程序的执行过程中,当,CPU,访问指令或数据前，由地址变换机构进行地址变换。,3.,内存保护,静态重定位系统中,：,用界地址寄存器判断程序是否在规定的上下界内,动态重定位系统中：,与存储方式有关,保护系统程序区不被用户侵犯。,不允许用户程序读写不属于自己地址空间的数据,4.,内存“扩充”,把内外存联合起来，向用户提供一个容量比实际容量大的多的存储空间。技术：,覆盖,交换,虚拟存储,扩充内存方法,-,覆盖技术,A,20kB,B,50kB,C,20kB,F,30kB,D,20kB,E,40kB,共180,kB,A,B,C,F,D,E,0,20,k,21k,70k,71k,110k,共110,kB,作业必须满足树状的模块结构,要由用户写出覆盖文件,ROOT A-(B-F,C-(D,E),扩充内存方法,-,交换技术,以整个作业为单位进行内外存交换（滚进滚出）,缺点：移动会增加系统开销。,第三节 实存储管理,单一连续分区(,单道环境),固定分区,动态分区,为调入内存的程序提供一个不小于作业地址空间的存储空间，当存储空间不够时，采用覆盖或交换技术扩充内存,1.,单一连续分区,在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。,2.固定分区分配,区号,容量,起始位置,状态,作业名,1,8,k,16,k,占用,作业1,2,16,k,24,k,占用,作业2,3,32,k,40,k,空闲,4,56,k,72,k,占用,作业3,操作系统区,作业1,作业2,作业3,0,16,k,24k,40k,72k,128k,内存状态表,内存,基本原理：,预先把可分配的主存储器空间分割成若干个连续区域，每个区域的大小可以相等，也可以不等。,固定分区的优缺点,优点,实现多个作业共享,分区的分配和回收算法简单,缺点,内存利用不充分，因为每个分区中都会有一部分空间被浪费了。,操作系统区,作业1,作业2,作业3,0,16,k,24k,40k,72k,128k,内存,碎片,3.,动态分区,主存不是预先划分好的，而是当作业装入时，根据作业的需求和主存空间的使用情况来动态决定是否分配。,进程,5,OS,进程,9,进程,10,进程,2,进程,5,OS,进程,9,进程,2,进程,5,OS,进程,2,进程,5,OS,进程,8,进程,2,占用块,进程,5,OS,进程,10,进程,2,空闲块,3.,动态分区,分区分配,空闲分区分配算法,分区的回收,可重定位的动态分区,3.,动态分区,分区分配,采用分区表（或者分区链表）来实现,空闲分区表:表示空闲分区的信息,已分区分配表:已使用分区的信息,3.,动态分区,分区分配,3.,动态分区,2.,空闲分区分配算法,1,）首次适应算法（,First Fit,）,2,）下次适应算法（,Next Fit,）,3,）最坏适应算法（,Worst Fit,）,4,）最佳适应算法（,Best Fit,）,3.,动态分区,2.,空闲分区分配算法,1,）首次适应算法（,First Fit,）,在分区表中顺序查找，找到够大的空闲区就分配。,特点,：简单、快速分配,缺点,:可能形成许多不连续的空闲区，造成许多“碎片”，使主存空间利用率降低。,3.,动态分区2.,空闲分区分配算法,2,）下次适应算法（,Next Fit,）,类似首次适应法，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就把它划分后分配出去。,特点,：,解决了低地址区会产生很多碎片的问题，使内存中空闲分区分布比较均匀，,缺点,:,大的空闲分区在内存中不易保留。,3.,动态分区,2.,空闲分区分配算法,3,）最坏适应算法（,Worst Fit,）,总是挑一个最大的空闲区分给作业使用，使剩下的空间不至于太小。,适用,于请求分配内存大小较均匀的系统,要求,:空白块自大至小排列,3.,动态分区,2.,空闲分区分配算法,4,）最佳适应算法（,Best Fit,）,接到内存申请时在空闲块表中找到一个能满足要求的最小空块进行分配,特点,：用最小空间满足要求,缺点,:,可能形成一些极小的空闲区，以致无法使用，这也会影响主存利用率。,要求,:,空白块自小至大排列,3.,动态分区,3.,分区的回收,当进程结束或终止时，要进行内存回收。如果回收的分区与其它的分区相邻，则合并成一个较大的分区，修改空闲分区表，并检查是否满足阻塞在内存空间的等待进程的需求。,3.,动态分区,4.,可重定位的动态分区,使用紧凑技术，为了消除外部碎片，进一步提高主存的利用率，定时地（或者在主存空间紧张时）把主存中的作业,“,搬家,”,集中在主存的一端，使另一端产生一个大的空闲区，这种技术称为存储器的,紧凑,”,。,紧凑仅仅在动态重定位时才可以用，并且在运行时执行。,P1,P2,P3,P4,P5,P6,占用块,空闲块,P1,P2,P3,P5,动态重定位,Load 1,1000,0289,0,0100,1000,地址空间,Load 1,1000,0289,0,10023,10123,11023,+,10023,存储空间,定位寄存器,每读一条指令，都要变换一次地址。,变换要靠硬件支持.,第四节 虚拟存储管理,1.,虚拟存储器的原理,2.,请求分页存储管理,3.,请求分段存储管理,虚拟存储管理,工作原理：,首先把作业信息保留在磁盘上，当作业请求装入时，只将其中一部分先装入主存，作业执行中若要访问的信息不在主存中，则再设法将这些信息装入主存。,用软件方法扩充内存。,逻辑上扩充了内存空间。,虚拟地址空间的大小受指令中地址长度的限制和外存储容量的限制；,需解决什么时候把哪部分程序装入内存、放在内存什么地方、淘汰策略问题。,内存分页,1.,虚拟存储器的原理,程序局部性原理,在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面,时间局部性：,一条指令被执行了，则在不久的将来它可能再被执行,空间局部性：,若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用,2.,请求分页存储管理,1).,分页管理的基本概念,2).,地址变换机构,3).,页面置换算法,4)分页存储管理的优缺点,饭店房间和内存分页,0页,1页,2页,n,页,0,2,1,3,2,6,3,4,4,9,用户程序,页表,页号 块号,内存,块号,0,1,2,3,4,5,6,7,分页存储管理,页:,将作业的地址空间划分成一系列大小相等的块，称为,页,，所有页按顺序编号为0、1、2、。,页内地址:,每个页内的内容也都从0开始顺序编号，这个编号称为,页内地址,。,块（页框）:,内存空间也划分成与页一样大的,块,，所有的块从低地址到高地址顺序编号为0、1、2、。,页表:,系统为作业建立一个页号与块号的对照表。,页表(,PMT,表),页号与块号的对照表，称为,页表,。,页号 块号 状态,0:该页不在内存,1:该页在内存,在多道程序设计系统中，进入主存的每个作业都有一张页表，由一个硬件“页表,地址,寄存器”来记录每个作业的页表所在位置和长度以便作业转换时同时转换页表。,分页系统中的逻辑地址,页号,p,页内地址,d,逻辑地址可用一个数对表示,p=INT,A,L,逻辑地址,页面大小,d=A MOD L,例:设某系统页面大小位1024字节，若逻辑地址为:2500,则,p=INT(2500/1024)=2,d=2500 MOD 1024=452,即2500处于第2页,第452位置上,2).,分页管理中的地址转换,访问某个逻辑地址时，分页地址变换机构自动将逻辑地址分为页号和页内地址两部分，再以页号为索引去检索页表。,从页表中查到相应页的目录，,将该页对应的块号与页内地址合并构成物理地址,将页号与页表长进行比较，若页号超过了表长，产生越界中断,2).,分页管理中的地址转换,Load,1,2500,23285,地址空间,内存 块号,0,1,8,10,1000,2500,3000,0,3,1,1,0,2,8,1,页号 块号 状态,L,b,+,页表长 页表起始地址,页表地址寄存器,2,452,8,452,23285,8644,PMT,表,p d,p d,地址变换机构,8*1024+452=8644,绝对地址=,块,号*,页面大小,+,页,内地址,作业,(,要求写出计算过程）：,在请求分页系统中，设每页512字节，某时刻系统给用户程序第0、1、2、3页分配的物理块号依次为6、11、3、17，则用户程序中逻辑地址1200经变换后得到的物理地址为,，该地址所在的物理块号为,。,分页式虚拟存储器的实现,首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入主存储器，作业执行时若所访问的页面已经在主存中，则进行地址转换，得到绝对地址，否则产生“缺页中断”由操作系统把当前所需的页面装入主存。,X,X,X,X,7,X,5,X,X,X,3,4,0,6,1,2,60,K-64K,56,K-60K,52,K-56K,48,K-52K,44,K-48K,40,K-44K,36,K-40K,32,K-36K,28,K-32K,24,K-28K,20,K-24K,16,K-20K,12,K-16K,8,K-12K,4,K-8K,0,K-4K,28,K-32K,24,K-28K,20,K-24K,16,K-20K,12,K-16K,8,K-12K,4,K-8K,0,K-4K,虚地址空间,物理地址空间,虚页,分页虚拟存储管理,缺页中断（,Page Fault）,在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去,如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的状态位及相应的内存块号,若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存,3).,页面置换算法,当主页中无空闲块时，为了装入一个页面，就必须按某种算法将主存中某个页调出，调入所需装入的页面。这就是页面调度。算法有：,先进先出调度算法(,FIFO)、,最近最少使用调度算法(,LRU),最近未使用页面置换算法（,NRU,）,最佳页面置换算法,(OPT),(1),先进先出算法,(FIFO),当需要淘汰一页时，选择在主存中驻留时间最长的那页被淘汰掉。,思想:最先进入内存的页面,不再被使用的可能性最大,适用于按线性顺序访问的程序,先进先出算法(,FIFO),设一用户程序共分5页,分配给它的内存块数为3,页面走向,P,为,4 3 2 1 4 3 5 4 3 2 1 5,其页面淘汰过程,:,4,3,2,1,4,3,5,4,3,2,1,5,4,3,2,1,4,3,5,5,5,2,1,1,4,3,2,1,4,3,3,3,5,2,2,4,3,2,1,4,4,4,3,5,5,+,+,+,+,+,+,+,+,+,缺页中断9次,FIFO,页面淘汰算法会产生异常现象，即：当分配给进程的物理页面数增加时，缺页次数,反而增加。,例如：,假设作业共有5个虚页，其页面访问踪迹为：0，1，2，3，0，1，4，0，1，2，3，4。计算当分配3个和4个实页时的缺页中断次数。,页面访问踪迹,0,1,2,3,0,1,4,0,1,2,3,4,三个实页的,分配与淘汰,0,1,2,3,0,1,4,4,4,2,3,3,0,1,2,3,0,1,1,1,4,2,2,0,1,2,3,0,0,0,1,4,4,9次缺页中断,页面访问踪迹,0,1,2,3,0,1,4,0,1,2,3,4,四个实页的,分配与淘汰,0,1,2,3,3,3,4,0,1,2,3,4,0,1,2,2,2,3,4,0,1,2,3,0,1,1,1,2,3,4,0,1,2,0,0,0,1,2,3,4,0,1,10次缺页中断,(2),最近最少使用算法,(LRU),当需要淘汰一页时，选择在最近一段时间内最久未用的页淘汰掉。,UNIX,操作系统采用的就是这种算法。方法：,设置记时器:在页表的每个入口，设一个“访问时间”区域,当一个页面被访问时，时钟寄存器里的内容被拷贝到这个区域。置换时替换最小时间值的页面。,利用堆栈:当页面被访问时，将它从堆栈底部移到顶部。栈顶页面常常是最常用的页面，而底部的就是,LRU,页,。,(3),最近未使用页面置换算法（,NRU,）,是,LRU,算法的近似：将内存中的页面组成一循环链表，每一页面对应一访问位，当某页面被访问时，将其访问位自动置“,1,”。如果指针指向页面的访问位为“,0,”（代表最近没有被访问），则置换该页；否则，将访问位置为“,0,”，页面继续留在内存按照相同规则替换下一页。如果一页经常被用到，则它永远不会被换出。,NRU,页面替换过程,入口,查询指针前进一步,指向下一个表目,页面引用位,=0?,选择该页面淘汰,返回,置页面,访问位=0,是,否,0,1,2,4,0,3,4,2,1,5,6,5,0,7,1,0,8,块号 页号 引用位 指针,q,第6页请求进入,NRU,页面替换过程,入口,查询指针前进一步,指向下一个表目,页面引用位,=0?,选择该页面淘汰,返回,置页面,访问位=0,是,否,0,1,2,4,0,3,4,2,1,5,6,5,0,7,1,0,8,块号 页号 引用位 指针,q,6,1,1,第1页请求访问,第5页请求进入,NRU,页面替换过程,入口,查询指针前进一步,指向下一个表目,页面引用位,=0?,选择该页面淘汰,返回,置页面,访问位=0,是,否,0,1,2,4,0,3,4,2,1,5,6,6,1,7,1,1,8,块号 页号 引用位 指针,q,0,NRU,页面替换过程,入口,查询指针前进一步,指向下一个表目,页面引用位,=0?,选择该页面淘汰,返回,置页面,访问位=0,是,否,0,1,2,4,0,3,4,2,1,5,6,6,1,7,1,0,8,块号 页号 引用位 指针,q,1,5,引用位周期性清零,NRU,页面替换过程,入口,查询指针前进一步,指向下一个表目,页面引用位,=0?,选择该页面淘汰,返回,置页面,访问位=0是,否,0,1,2,4,0,3,4,2,0,5,6,6,0,7,1,0,8,块号 页号 引用位 指针,q,5,(4),最佳页面置换算法,(OPT),该算法思想是从主存中移出永不再用的页面，至少是选择很远的将来才用的页面淘汰之。,其实，这是一个不实用的算法，因为页面 走向是不可预知的。所以该算法常用做性能评价的依据。,OPT,算法具有最低的缺页率。,4).,分页存储管理的优缺点,优点,分页存储管理的优点是不需要移动就可解决碎片问题；,提高主存的利用率；,可提供大容量的多个虚拟存储器；,提高了多道程序运行的程度；,对大作业而言，更加方便用户。,缺点,由于采用了动态地址变换机构，增加了计算机的成本处理速度降低；,对于请求分页系统，为处理页面中断增加了系统开销；,在进程的最后一个页框中可能有内部碎片的存在。,从分页到分段,第0页,第1页,第2页,第3页,第4页,第5页,第6页,第7页,第8页,第9页,内存,作业逻辑结构,主程序段,子程序段,数据区段,工作区段,内存,作业逻辑结构,主程序段,子程序段,数据区段,工作区段,用户希望,第0段,第1段,第2段,第3段,3.,请求分段存储管理,分段存储管理中,作业的地址空间被划分为若干个段,每段定义一组逻辑信息,如:主程序段,子程序段,数据段等,规定一个段号,每段地址空间都从0开始.,段号,s,段内地址,w,逻辑地址可用两部分表示,内存分配:,以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放,段表(,SMT,表),段号 段长度 起始地址 状态,0:该段不在内存,1:该段在内存,它记录了段号，段的首（地）址和长度之间的关系,每一个程序设置一个段表，放在内存,属于进程的现场信息,分段管理中的地址转换,逻辑地址,段号,s,段内地址,w,内存,0,1,k,6144,1,1,500,4096,1,2,300,8192,1,3,200,9200,0,L,b,+,段表长 段表起始地址,段表地址寄存器,2,100,8292,12345,SMT,表,b,+,8,kB,段号 长度 起址 状态,段号2,段表地址,绝对地址=根据段号找到段表中的起始地址+段内地址,分段式虚拟存储器的实现,段式虚拟存储管理,以,段式存储管理,为基础，在磁盘上保留作业的各个分段信息，作业执行时把需要执行的一段或几段装入主存。在实际使用中，也要进行查表和地址转换以及“缺段中断”和调度(包括调出、装入、移动等)工作。,3).,分段管理的优缺点,优点：,1),便于模块化处理,可以把每个程序模块构成各自独立的分段，赋予不同的名字，可采用保护措施保障一个程序模块不会受到其他模块的影响。,2,）消除内部碎片,段多长，主存就分多长。,3,）动态链接方便,一个作业可能用到数百个程序，但不见得全用。如果用静态链接花费时间长，占用主存多；而动态链接很好地解决了这个问题。,缺点：,1,）提高硬件成本，需要更多的硬件支持，地址变换代价增加，使系统更加复杂。,2,）在辅存中管理不定长度的分段困难很多，存储位置不易确定。,3,）分段尺寸受主存大小限制，段太大就不易在主存中找到合适的空白块。,4,）由于段长不固定，又会产生外部碎片。,4).,分段与分页的区别,1),页不是完整的逻辑信息总体的结合，而段是信息的逻辑单位，它是有意义的一组信息。,2),页的大小一样，由系统决定。段的大小不一，决定于用户编写的程序。,3),逻辑地址表示不一样，分页是一维的，分段是两维的。,4),段是用户可见的，（分段可以在用户编程时确定，也可以在编译程序对源程序编译时根据信息的性质来划分），而页是用户看不见的，是操作系统分的。用户可感知段，但分页活动用户是看不见的，而仅仅用于主存管理。,回想一下,存储器层次结构,存储管理任务,实存储管理,虚拟存储管理,请求分页,请求分段,作业,P175 15，16,