第7章 存储器管理

.,第7章存储器管理,存储器管理的主要目标是为用户提供方便、安全和充分大的存储器。存储器即主存、内存，分为两大部分：系统区：供操作系统使用用户区：划分为一个或多个区域，供用户进程使用。,.,存储器管理的功能,存储空间的分配和回收：地址变换：将逻辑地址变换为物理地址存储保护：防止因用户程序错误破坏系统或其他用户，防止程序之间的相互干扰存储扩充：在逻辑上为用户提供一个比实际内存更大的存储空间,.,7.1存储器管理的基本概念,逻辑地址：用户编程时所使用的地址。又称相对地址、虚地址。地址空间：逻辑地址的集合。物理地址：内存中的地址。又称绝对地址、实地址。主存空间：物理地址的集合。,.,地址变换,地址变换：将逻辑地址转换为物理地址。又称地址映射、重定位。地址变换分为两类：静态地址变换动态地址变换,.,静态地址变换,静态地址变换：又称静态地址重定位，地址变换在程序装入时一次完成，以后不再改变。特点：不需硬件支持，但程序运行时不能在内存移动，程序需要连续存储空间，难以共享。,.,静态地址变换示意图,movax,50054321,movax,1000+50054321,0100500999,010001100150019991M-1,作业的地址空间,主存空间,重定位装入程序,.,动态地址变换,动态地址变换：又称动态重定位，在程序执行过程中，每次访问内存之前将要访问程序地址转换成内存地址。特点：需要硬件支持，不需连续空间，可以实现虚拟存储。,.,动态地址变换示意图,movax,50054321,0100500999,010001100150019991M-1,作业的地址空间,存储空间,500,1000,逻辑地址,重定位寄存器,.,7.2分区存储管理,分区存储管理是多道程序系统中采用的一种最简单的方法。它把系统的内存划分为若干大小不等的区域，操作系统占一个区域，其他区域由并发进程共享，每个进程占一个区域。分区存储管理分为：固定分区动态分区,.,7.2.1固定分区存储管理,固定分区存储管理方法将内存空间划分为若干个固定大小的分区，每个分区中可以装入一道程序。分区的位置及大小在运行期间不能改变。为了便于管理内存，系统需要建立一张分区使用表，其中记录系统中的分区数目、分区大小、分区起始地址及状态。,.,分区使用表例,操作系统用户作业用户作业,分区号大小起始地址状态18KB20KB已分配232KB28KB已分配332KB60KB未分配4120KB92KB未分配5300KB212KB已分配,用户作业,020KB28KB60KB92KB212KB512KB-1,.,固定分区的内存分配,分区分配：当有用户程序要装入时，由内存分配程序检索分区使用表，从中找出一个能满足要求的空闲分区分配给该程序，然后修改分区说明表中相应表项的状态；若找不到大小足够的分区，则拒绝分配内存。分区回收：当程序执行完毕不再需要内存资源时，释放程序占用的分区，管理程序只需将对应分区的状态置为未分配即可。特点：最早的多道程序存储管理方式，不能充分利用内存，存在内存碎片。,.,7.2.2动态分区存储管理,动态分区存储管理又称为可变分区存储管理，这种存储管理方法的实现思想是根据作业大小动态地建立分区，并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。,.,动态分区中的数据结构,在动态分区中常用的数据结构有：空闲分区表。用一个空闲分区表来登记系统中的空闲分区。其表项类似于固定分区。空闲分区链。将内存中的空闲分区以链表方式链接起来，构成空闲分区链。,.,空闲分区表示意图,分区号大小起始地址18KB24KB212KB128KB38KB248KB45,操作系统空闲(8K)已分(96K)空闲(12K)已分(108K)空闲(8K),024KB32KB128KB140KB248KB256KB-1,.,空闲分区链示意图,操作系统空闲(8K)已分(96K)空闲(12K)已分(108K)空闲(8K),024KB32KB128KB140KB248KB256KB-1,操作系统空闲(8K)已分(96K)空闲(12K)已分(108K)空闲(8K),024KB32KB128KB140KB248KB256KB-1,表头指针,.,分区分配算法,目前常用的分区分配算法有以下几种：首次适应算法循环首次适应算法最佳适应算法最坏适应算法,.,首次适应算法,首次适应算法又称最先适应算法，该算法要求空闲分区按地址递增的次序排列。在进行内存分配时，从空闲分区表（或空闲分区链）首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表（或空闲分区链）中。,.,首次适应算法的特点,特点：优先利用内存低地址端，高地址端有大空闲区。但低地址端有许多小空闲分区时会增加查找开销。,.,循环首次适应算法,循环首次适应算法又称下次适应算法，它是首次适应算法的变形。该算法在为进程分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表（或空闲分区链）中。,.,循环首次适应算法的特点,特点：使存储空间的利用更加均衡，但会使系统缺乏大的空闲分区。,.,最佳适应算法,最佳适应算法要求空闲分区按容量大小递增的次序排列。在进行内存分配时，从空闲分区表（或空闲分区链）首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。如果该空闲分区大于作业的大小，则从该分区中划出一块内存空间分配给请求者，将剩余空闲区仍然留在空闲分区表（或空闲分区链）中。,.,最佳适应算法的特点,按最佳适应算法为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。特点：保留了大的空闲区。但分割后的剩余空闲区很小。,.,最坏适应算法,最坏适应算法要求空闲分区按容量大小递减的次序排列。在进行内存分配时，先检查空闲分区表（或空闲分区链）中的第一个空闲分区，若第一个空闲分区小于作业要求的大小，则分配失败；否则从该空闲分区中划出与作业大小相等的一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表（或空闲分区链）中。,.,最坏适应算法的特点,特点：剩下的空闲区比较大，但当大作业到来时，其存储空间的申请往往得不到满足。,.,如何衡量分配算法的好坏,对于某一个作业序列来说，若某种分配算法能将该作业序列中所有作业安置完毕，则称该分配算法对这一作业序列合适，否则称为不合适。,.,例,下表给出了某系统的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求?,.,例-采用最佳适应算法分配1,申请96K，选中5号分区，5号分区大小与申请空间大小一致，应从空闲分区表中删去该表项；,.,例-采用最佳适应算法分配2,申请20K，选中1号分区，分配后1号分区还剩下12K；,.,例-采用最佳适应算法分配3,申请200K，选中4号分区，分配后剩下18K。,.,例-采用首次适应算法分配1,申请96K，选中4号分区，进行分配后4号分区还剩下122K；,.,例-采用首次适应算法分配2,申请20K，选中1号分区，分配后剩下12K；,.,例-采用首次适应算法分配3,申请200K，现有的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进行内存分配，无法满足该作业序列的需求。,.,分区分配,以首次适应算法及空闲链表为例，申请分区大小为x，e是规定的不再分割的剩余区大小。,.,程序示例1,voidcmalloc(node*head,intx)node*p,*q,*t;p=head;while(p-sizelinkif(p!=null)p-size=p-size-x;if(p-sizelink=p-link;elset=p+p-size-x;elset=0;printf(“本次无法分配！n”);return(t);,.,分区回收,回收分区时，应将空闲区插入适当位置，此时有以下四种：回收分区r上面邻接一个空闲分区回收分区r下面邻接一个空闲分区回收分区r上面、下面各邻接一个空闲分区回收分区r不与任何空闲分区相邻,.,回收分区r上邻接一个空闲分区,此时应将回收区r与上邻接分区F1合并成一个连续的空闲区。合并分区的首地址为空闲区F1的首地址，其大小为二者之和。,.,回收分区r下邻接一个空闲分区,此时应将回收区r与下邻接分区F2合并成一个连续的空闲区。合并分区的首地址为回收分区r的首地址，其大小为二者之和。,.,回收分区r上下邻接空闲分区,此时应将回收区r与上、下邻接分区合并成一个连续的空闲区。合并分区的首地址为与r上邻接空闲区F1的首地址，其大小为三者之和，且应将与r下邻接的空闲区F2从空闲分区表(或空闲分区链)中删去。,.,回收分区r不与任何空闲分区相邻,这时应为回收区单独建立一个新表项，填写分区大小及起始地址等信息，并将其加入到空闲分区表(或空闲分区链)中的适当位置。,问题：回收分区的个数变化情况？,.,程序示例2,voidcfree(node*head,*s)/*head为空闲链表的头指针，s为释放区*/node*p,*q;intn;p=head;n=s-size;while(p!=null,.,内存保护,存储保护是防止一个作业有意或无意破坏操作系统或其他作业。常用的存储保护方法有：上下界寄存器基址限长寄存器除上述保护方案外，还有四种存取权限：禁止做任何操作只能执行只能读读/写,.,上下界寄存器方法,上下界寄存器方法：用上、下界寄存器分别存放作业存储空间的结束地址和开始地址。在作业运行过程中，将每一个访问内存的地址都同这两个寄存器的内容进行比较，若超出了上下界寄存器的范围则产生越界中断。,.,基址限长寄存器方法,基址、限长寄存器方法：用基址和限长寄存器分别存放作业存储空间的起始地址及作业长度。当作业执行时，将每一个访问内存的相对地址和这个限长寄存器比较，若逻辑地址超过限长则产生越界中断。,.,7.2.3碎片问题及拼接技术,分区存储管理中，必须把作业装入到一片连续的内存空间中。这种分配方法能满足多道程序设计的需要，但存在碎片问题。碎片也可称为零头，是指内存中无法被利用的存储空间。,.,内部碎片和外部碎片,内部碎片是指分配给作业的存储空间中未被利用的部分外部碎片是指系统中无法利用的小存储块。前述分区存储管理方法中存在什么碎片？,.,解决碎片问题的办法,拼接：解决碎片问题的办法之一，即通过移动把多个分散的小分区拼接成一个大分区，也可称为紧缩或紧凑。拼接的不足是要耗费大量处理机时间。,.,拼接示意图,拼接前拼接后,.,拼接需要的技术支持,动态重定位：拼接后程序在内存的位置发生变化，因此需要动态重定位技术支持。空闲区放在何处：拼接后的空闲区放在何处不能一概而论，应根据移动信息量的多少来决定。拼接的时机：回收分区时拼接：只有一个空闲区，但拼接频率过高增加系统开销。找不到足够大的空闲区且系统空闲空间总量能满足要求：拼接频率小于前者，空闲区管理稍复杂。也可以只拼接部分空闲区。,.,7.3伙伴系统,固定分区存储管理限制了内存中的进程数，动态分区的拼接需要大量时间，而伙伴系统是一种较为实用的动态存储管理办法。伙伴系统采用伙伴算法对空闲内存进行管理。该方法通过不断对分大的空闲存储块来获得小的空闲存储块。当内存块释放时，应尽可能合并空闲块。,.,伙伴系统的内存分配,设系统初始时可供分配的空间为2m个单元。当进程申请大小为n的空间时，设2i-1n2i，则为进程分配大小为2i的空间。如系统不存在大小为2i的空闲块，则查找系统中是否存在大于2i的空闲块，若找到则对其进行对半划分，直到产生大小为2i的空闲块为止。,.,伙伴系统的内存回收,当一块被分成两个大小相等的块时，这两块称为伙伴。当进程释放存储空间时，应检查释放块的伙伴是否空闲，若空闲则合并。这个较大的空闲块也可能存在空闲伙伴，此时也应合并。重复上述过程，直至没有可以合并的伙伴为止。,.,伙伴地址公式,设某空闲块的开始地址为d，长度为2K，其伙伴的开始地址为：Buddy（k，d）=d+2k，若d%2k+1=0=d-2k，若d%2k+1=2k如果参与分配的2m个单元从a开始，则长度为2K、开始地址为d的块，其伙伴的开始地址为：Buddy（k，d）=d+2k，若（d-a）%2k+1=0=d-2k，若（d-a）%2k+1=2k,.,伙伴系统分配及回收例,设系统中初始内存空间大小为1MB，进程请求和释放空间的操作序列为：进程A申请200KB；B申请120KB；C申请240KB；D申请100KB；进程B释放；E申请60KB；进程A、C释放；进程D释放；进程E释放。,.,E,A释放,分配过程示意图,0128K256K384K512K640K768K896K1M,初始状态,A申请200,B申请120,C申请240,D申请100,B释放,E申请60,C释放,D释放,E释放,512K,256K,A,A,512K,128K,B,A,B,256K,C,A,B,256K,C,D,A,256K,C,D,128K,A,256K,C,D,64,E,256K,C,D,64,E,256K,D,64,256K,512K,E,64,256K,512K,128K,128K,.,伙伴系统的二叉树表示,可以用二叉树表示内存分配情况。叶结点表示存储器中的当前分区，如果两个伙伴是叶子，则至少有一个被分配。右图表示A（200）、B（120）、C（240）、D（100）分配之后的情况。,A,B,D,C,1M,512K,256K,128K,.,伙伴系统的不足,分配和回收时需要对伙伴进行分拆及合并。存储空间有浪费。,.,7.4分页存储管理,分区管理中存在碎片，而紧凑技术开销太大，若能取消作业对存储区的连续性要求，则能较好地解决碎片问题。分页存储管理就是基于这一思想提出的。,.,7.4.1分页存储管理的基本原理,在分页存储管理中，将进程的逻辑地址空间划分成若干大小相等的页（或称页面），相应地将主存空间也划分成与页大小相等的块（或称物理块）。在为进程分配存储空间时，总是以块为单位来分配，可以将进程中的某一页存放到主存的某一空闲块中。分页系统中是否有碎片？页内碎片：由进程最后一页未装满而形成的碎片。,.,页表,为了在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页面映象表，简称页表。页表：记录页面在内存中对应物理块的数据结构。,.,页表的作用,页表的作用是什么？,.,页面大小的选择,页面的大小应适中。若页面太大，以至和一般进程大小相差无几，则页面分配退化为：分区分配，同时页内碎片也较大。若页面太小，虽然可减少页内碎片，但会导致页表增长。因此，页面大小应适中，通常为2的幂，一般在512B到4KB之间。页表一般存放在内存中。也可以在页表中设置存取控制字段，以实现存储保护。,.,存储分块表,存储分块表用来记录内存中各物理块的使用情况及未分配物理块总数。存储分块表可用下述方式表示：位示图：利用二进制的一位表示一个物理块的状态，1表示一分配，0表示未分配。所有物理块状态位的集合构成位示图。空闲存储块链：将所有的空闲存储块用链表链接起来，利用空闲物理块中的单元存放指向下一个物理块的指针。,.,位示图例,位示图占用的存储空间：物理块数/8（字节）,.,请求表,请求表用来登记每个进程的页表在内存中的物理位置及每个页表的长度、状态等。如下图所示。,.,7.4.2存储空间的分配及回收,页面分配：计算进程所需页面数，然后在请求表中登记进程号、请求页面数等。如存储分块表中有足够的空闲块可供进程使用，则在系统中取得页表始址，并在页表中登记页号及其对应的物理块号。否则无法分配。页面回收：将存储分块表中相应的物理块改为未分配，或将回收块加入到空闲存储块链中，并释放页表，修改请求表中的页表始址及状态。,.,7.4.3地址变换机构,地址变换机构的任务是实现逻辑地址到物理地址的变换，即将逻辑地址中的页号转换为内存中的物理块号。,.,分页的逻辑地址结构,分页存储管理系统中，逻辑地址由页号和页内位移组成。其结构如下所示：若A为逻辑地址，L为页面大小，则：页号：P=int(A/L)页内位移：W=A%L,.,基本地址变换机构,页表通常存放在内存中，为了实现方便，系统中设置了一个页表寄存器存放页表在内存的起始地址和页表的长度。进程未执行时，页表的起始地址和长度存放在PCB中。当进程执行时，才将页表始址和长度存入页表寄存器中。,.,地址变换过程,分页地址变换机构自动地将逻辑地址分为页号和页内位移；将页号与页表长度进行比较，如果页号超过了页表长度，则表示本次所访问的地址已超越进程的地址空间，系统产生地址越界中断；若未出现越界，则由页表始址和页号计算出相应页表项的位置，从中得到该页的物理块号；将物理块号与逻辑地址中的页内位移拼接在一起，就形成了访问主存的物理地址。,.,分页系统的地址变换机构图,注意这里的页号字段？,页表寄存器,页表始址页表长度,越界中断,逻辑地址,页号（2）页内位移（452）,页号块号,23851,01234,8452,物理地址,页表,.,分页地址变换例1,设页面大小为1K字节，作业的0、1、2页分别存放在第2、3、8块中。则逻辑地址2500的页号及页内地址为：2500/1024=2（页号）；2500%1024452（页内地址）；查页表可知第2页对应的物理块号为8；将块号8与页内地址452拼接得到物理地址为：810244528644。,.,地址变换例2,一分页系统中逻辑地址长度为16位，页面大小为1KB，现有一逻辑地址0A6FH，且第0、1、2、3页依次存放在物理块3、7、11、10中。逻辑地址0A6FH的二进制表示如下：页号页内地址0000101001101111由此可知逻辑地址0A6FH的页号为2，该页存放在第11号物理块中，用十六进制表示块号为B，所以物理地址为：10111001101111，即2E6FH。,.,联想存储器,因页表放在主存中，故存取数据时CPU至少要访问两次主存。降低了内存访问速度。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器（又称联想存储器或快表），用以存放当前访问的那些页表项。,.,引入快表后的地址变换过程,地址变换机构自动将页号与快表中的所有页号进行并行比较，若其中有与此匹配的页号，则取出该页对应的块号，与页内地址拼接形成物理地址。若页号不在快表中，则再到主存页表中取出物理块号，与页内地址拼接形成物理地址。同时还应将这次所查到的页表项存入快表中，若快表已满，则必须按某种原则淘汰出一个表项以腾出位置。,.,具有联想存储器的地址变换,页表与快表有何不同？,.,联想存储器的大小,由于成本关系，快表大小一般由832个表项组成。由于局部性原理，联想存储器的命中率可达80%-90%。,.,7.4.4多级页表及反向页表,现代计算机系统都支持非常大的逻辑地址空间，致使页表很大，用连续空间存放页表显然不现实。如逻辑地址32位，页面大小4KB，则页表项为1M，若每个页表项占4字节，则页表共需要4MB内存空间。解决方案：用离散方式存储页表仅将当前需要的部分页表项放在内存，其余放在磁盘上，需要时调入。,.,两级页表及多级页表,将页表再分页，使每页与内存物理块大小相同，并为它们进行编号0、1、，同时还为离散存放的页表建立一张页表。例如：32位地址可以划分为,31222112110,一级页号p1二级页号p2页内地址w,.,两级页表结构,第0页页表,内存空间,一级页表,200020242700,27,0123456785901411,012n,0121023,8590,第1页页表,0121023,1411,0121023,第n页页表,.,具有两级页表的地址变换过程,利用逻辑地址中的一级页号作为索引访问一级页表，找到第二级页表的起始地址，再利用第二级页号找到指定页表项，从中取出块号与页内地址拼接形成物理地址。,.,具有两级页表的地址变换机构,第一级页表寄存器,逻辑地址,+,二级页表,一级页表,bw,物理地址,一级页号二级页号页内地址,p1p2w,b,.,多级页表,对两级页表进行扩充，便可得到三级、四级或更多级的页表。多级页表的实现方式与两级页表类似。,.,反向页表,现代操作系统一般允许大逻辑地址空间，如232，这使得页表太大，为解决页表占用大量存储空间的问题，引入了反向页表。反向页表为每个物理块设置一个页表项，并将它们按物理块号大小排序，表项内容为页号及其隶属进程的标识号。,.,反向页表地址变换过程,利用进程标识号及页号检索反向页表，若找到相应的页表项，则将其物理块号与页内地址拼接；否则请求调入该进程相应页，在无调页功能的系统中则出错。由于反向页表中没有存放进程中尚未调入页，因此必须为每个进程建立一张传统页表并存放在外存中，当所访问页不在内存时使用这张页表。页表中包含各页在外存的地址。,.,反向页表的地址变换,逻辑地址,进程标识号页号,反向页表,bw,物理地址,页号页内地址,pw,pidp,进程标识号pid,012bn,.,反向页表的不足,反向页表查找慢：因为进程号及页号不能作为索引，查找时必须在整个反向页表中进行。解决办法：将常用页表项存入快表用散列函数存放反向页表,.,7.4.5存储保护,分页存储管理采用两种方式保护内存：地址越界保护：页表长度与逻辑地址中的页号比较存取控制保护：在页表中增加保护位,.,7.5分段管理,由于分页按物理单位进行，没有考虑程序段的逻辑完整性，给程序段的共享和保护带来不便，另外动态链接及段的动态增长也要求以逻辑上完整的程序段为单位管理。,.,7.5.1分段管理的原理,在分段存储管理系统中，作业的地址空间由若干个逻辑分段组成，每个分段是一组逻辑意义相对完整的信息集合，每个分段都有自己的名字，每个分段都从0开始编址并采用一段连续的地址空间。在进行存储分配时，以段为单位分配内存，每段分配一个连续的内存区，但各段之间不要求连续。,.,作业的地址空间是二维的,作业的地址空间分为多段，每段都从0开始编址，故地址是二维的。,.,分段系统的逻辑地址结构,该地址结构最多允许多少分段?每段最大长度为多少?该地址结构允许作业最多有64K个段，每段的最大长度为64KB。,.,7.5.2分段存储管理的实现,为了实现从逻辑地址到物理地址的变换，必须为每个进程建立一个段表，用来记录每段在内存的起始地址及相关信息。其中每个表项描述一个分段的信息，至少包含：段号段长段在内存的起始地址其他信息段表一般存放在内存。,.,段表的作用,.,地址变换,为实现从逻辑地址到物理地址的转换，在系统中设置了段表寄存器，用于存放段表始址和段表长度。为了提高内存的访问速度，也可以使用快表。,.,地址变换过程,进行地扯变换时，系统将逻辑地址中的段号S与段表长度进行比较，若段号超过了段表长度则产生越界中断；否则根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后再检查段内地址是否超过该段的段长，若超过则同样发出越界中断信号；若未越界，则将该段的起始地址与段内位移相加，从而得到了要访问的物理地址。,.,地址变换机构图,段表寄存器,段表始址段表长度,越界中断,逻辑地址,段号（2）段内位移（100）,段号段长始址,1K6K8004K6008K,012,物理地址,段表,8292,.,分段地址变换例,设作业分为3段，0、1、2段长度分别为1K、800、600，分别存放在内存6K、4K、8K开始的内存区域。逻辑地址（2，100）的段号为2，段内位移为100。查段表可知第2段在内存的起始地址8K。将起始地址与段内位移相加，8K1008292，物理地址为8292。,.,分段与分页的主要区别,分页管理与分段管理有许多相似之处，但两者在概念上也有很多区别，主要表现在：页是信息的物理单位，是为了减少内存碎片及提高内存利用率，是系统管理的需要。段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地满足用户的需要。页的大小固定且由系统决定，由硬件把逻辑地址划分为页号和页内地址两部分。段的长度不固定且由用户所编写的程序决定，通常由编译系统在对源程序进行编译时根据信息的性质来划分。分页系统中作业的地址空间是一维的，分段系统中作业的地址空间是二维的。,.,7.5.3段的共享与保护,分段是信息的逻辑单位，因而实现共享比分页系统方便。在分页存储管理系统中，信息的共享是通过使多个进程页表项指向同一个物理块来实现的。,.,分页系统中信息共享示意图,0216061707180,ed1ed40dat