第四章存储管理.ppt

第四章存储管理,主要解决三个问题:内存的分配和回收:分配算法及使用的数据结构.回收算法.内存信息的保护:使内存信息不受到干扰和破坏内存空间的扩充:提供虚拟存储器.,1.概论一.内存管理目标1.方便用户使用使用户在编程时,不必关心程序在内存中存放的物理位置.不必关心程序在内存中放不放得下的问题.2.提高内存的利用率不浪费内存空间,尽可能容纳多道程序运行.二.存储管理功能(1)地址映射将程序地址空间中使用的逻辑地址变换成主存中的地址的过程.(2)主存分配按照一定的算法把某一空闲的主存区分配给作业或进程。,(3)存储保护保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。(4)提供虚拟存储技术向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确运行。三.信息存储结构1.寄存器:暂时存放临时数据:通用寄存器,指令寄存器,控制寄存器,程序状态字寄存器,中断字寄存器,基址寄存器,限长寄存器.,2.主存寄存器:暂时存放数据和程序.直接被cpu操作.3.高速缓冲存储器:暂时存放从内存中取出的数据.速度比内存快.4.外存储器:永久存放信息.容量大,存取的速度慢.四.地址重定位1.什么是地址重定位将程序地址空间中使用的逻辑地址变换成主存中物理地址的过程称为地址重定位（或地址映射，地址变换）。地址重定位方式:静态地址重定位.动态地址重定位2.静态地址重定位在程序装入内存时,由装配程序完成从逻辑地址到物理地址的转换的过程。,优点：实现简单，不要硬件的支持。缺点：程序一旦装入内存，移动就比较困难。,3.动态地址重定位动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换。系统中设置了重定位寄存器。,动态地址重定位是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间。重定位寄存器的内容由操作系统用特权指令来设置。实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。特点:需要重定位机构的支持。作业可以在内存移动:只要改变重定位寄存器的内容,便可以把作业定位到新的空间中.适应动态存储分配。实现存储管理的软件较为复杂。,五.信息的保护防止存储区中的各程序在执行时,相互干扰和破坏,而对它们采取的保护措施.保护方法:在cpu中设置一对上下界限寄存器;或者,一对基址寄存器和限长寄存器控制程序的存储区.保证程序执行时不越界.,下界寄存器存放程序装入内存后的开始地址（首址）上界寄存器存放程序装入内存后的末地址判别式：（下界寄存器）物理地址（上界寄存器）,基址寄存器：存放程序的起始地址。限长寄存器：程序的长度（单位：字节）判别式：0程序地址f.size将r与f2合并,r.addr;r.size+f2.size=f.sizec.f1、r、f2合并,f1.addr;f1.size+r.size+f2.size=f1.sizeD.r作为一个空闲区，并插入到空闲区表的适当位置。,(5)地址重定位和存储保护采用:动态地址重定位方式装入作业.保护:(基址寄存器)绝对地址(限长寄存器)(6)碎片问题及解决方法碎片(零头):内存中不能被任何作业或进程占用的空闲区。坏处:造成内存空间的浪费,降低内存的利用率.如何解决碎片问题？采用拼接技术或门限值控制拼接技术:移动已分配区信息，使分散的碎片连成一片.存在的问题:移动时要消耗大量的资源和时间,增加了系统开销.,利用门限值限制对空闲区的划分:由os规定一个门限值(如:1kB),当对空闲区划分时,检查剩余部分不得小于等于所规定的门限值,否则不能划分该空闲区.,4.分区分配的优缺点优点:(1)实现了内存的共享,有助于多道程序设计.内存的利用率:动态分区分配比静态分区分配高.(2)与分页和分段方法相比,空闲表或队列占用内存空间小;算法实现简单.(3)实现存储保护和地址重定位比较简单.缺点:(1)对内存的利用都存在碎片问题.(2)作业在运行之前,要求必须将某个作业全部装入到一个连续的分区中,这样,作业中可能不执行的信息(如:出错处理子程序)也被装入了.(3)内存不能扩充.作业的地址空间受到内存空间的限制.,二.分页存储管理1.问题的提出分区存储管理的主要问题:要求作业整体装入内存.会造成:由于整体装入作业,作业中此次执行用不到的信息,也被装入了,会造成空间的浪费.由于整体装入作业,若作业的容量比内存容量大.作业就有可能不能进入内存了.为解决以上问题,提出了:分页存储管理:部分装入作业,且各部分可存放在不连续的空间内;当执行时,需要作业的那一部分,就从外存调入,不需要不调入,直至作业执行完为止.页式存储管理要解决如下问题:页式存储管理系统的地址映射；调入策略；淘汰策略；放置策略。,2.页式系统的基本概念,（1）页面程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。（2）主存块主存被分成与页面大小相等的块，称为主存块，又称为实页。,页式系统分配:将程序的若干页面,装入到内存内不相邻(或相邻)的各个块中的过程.,3.内存空间的分配与回收分配与回收的数据结构:位示图:登记内存中各块的已分或未分情况,以及当前剩余空闲块数.例:设将内存中可供分配的区域分成256块,则可建立字长为32位的8个字的位示图,供系统分配与回收使用.,0/10/10/10/10/10/1,0/10/10/10/10/10/1,0/10/10/10/10/10/1,0/10/10/10/10/10/1,012293031,空闲块数,01.7,分配过程:.先查当前空闲块数是否满足作业的要求,满足分配;.若满足,再查位示图中为0的位,依该位的位号和字号,按下列公式计算块号:块号=字号字长+位号.置占用标记”1”,从当前总空闲块数-本次已分块数.装入作业的页到对应的内存块中,并建立相应的页表回收过程:根据归还的块号计算该块在位示图中对应的位置,并置标记”0”;将回收块数加到当前的空闲块数中.确定归还的块号在位示图中对应位置的计算:字号=i/字长其中:i为归还的块号.:取整.位号=imod字长,4.页式地址变换(1).页表为了实现从地址空间到物理主存的映象，系统建立的记录页面与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表.,页的大小是为2n(n为位数),(2).虚地址结构(程序字)虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移量）。页号占虚地址的高位部分，页内地址占虚地址的低位部分；页内地址的大小（位数）由页面大小决定。假定页面大小1024字节，虚地址共占用2个字节(16位)1kB=-1024B=2页号页内地址（位移量）PW151090,10,(3)页式地址变换过程和步骤变换过程:,注:1kB=22kB=2,10,11,变换步骤:,H,CPU给出操作数地址(为3BADH)；由分页机构自动地把逻辑地址分为两部分，得到页号p和页内相对位移w(p=7，w=3ADH)；根据页表始址寄存器指示的页表始地址，以页号为索引，找到第7页所对应的块号(为0BH)；最后，将块号0BH和页内位移量w拼接在一起，就形成了访问主存的物理地址(5BADH)例：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址3412转换成内存地址。程序地址以十进制数给出页号虚地址页大小位移量虚地址mod页大小,根据题意产生页表；以页号查页表，得到对应页的内存块号内存地址块号页大小位移量,虚地址3412P341220481W3412mod20481364MR=9*2048+1364=19796虚地址3412的内存地址是：19796,5.快表快表可以加快页表的查询速度.在页式存储技术中，当程序执行一条访问内存指令时，至少要访问内存两次。一次查询内存中的页表,确定物理地址;二次是根据物理地址取操作数.为了提高存取速度,将页表做成快表.快表:用寄存器组成页表。快表不在内存,而是在高速存储器中.6.内存的越界保护访问页号满足判别式为合法的访问，否则非法。0页号用户程序的总页数,三.虚拟分页存储管理(请求分页管理,动态分页管理)解决的问题:作业部分装入内存并执行,当需要某一页时,从外存调入内存,直至作业执行完成.好处:作业的地址空间不受内存空间的限制.好像为用户提供容量很大的内存-虚拟存储器.减少存储空间的浪费.1.什么是虚拟存储器?利用作业部分装入内存的技术,边执行边装入所需的页;使逻辑地址空间大于内存的物理空间的作业也能运行.对用户来说,好像系统有一个容量很大的存储器,称这种存储器为虚拟存储器.实现虚拟存储的物质基础:要有一定容量的主存.要有相当大容量的外存,足以容纳所有的并发作业.要有地址变换机构.,2.虚拟分页存储主要解决的问题(1)系统如何知道所需页不在主存?如果不在主存,怎样在外存中找到所需的页并装入主存?扩充页表的结构:,中断位：1:页在内存，0:页不在内存引用位：0:没有进程访问1:有进程访问修改位：0:调入内存后没有修改1:页调入内存后修改过辅存地址:所缺的页在辅存的地址.(2)若作业所需的页装入内存时,内存没有空间怎么办?淘汰内存中暂时不执行的页,让其装入.-由淘汰算法完成.,3.页面调度算法页面的调入算法和调出算法.,(1)调入策略a.预调系统根据进程运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。但难以实现。b.请调进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。,(2)调出算法(淘汰算法)a.先进先出淘汰算法(FIFO算法)思想:最先进入内存的页，先淘汰出内存。理由：最早调入内存的页，不再被使用的可能性,比近期调入内存的大。优点:算法简单，实现容易。缺点:调度具有不合理性.先进入内存的页,可能正在被多个进程所调用,因此时间长一些.调度效率比较差.b.最久未使用淘汰算法（LRU算法）思想:总是选择最近长时间未使用的页淘汰之。(即:在本次发生缺页中断之前的最近一段时间内未被使用,且时间最长的页,在最近的将来被使用的可能性最小,故淘汰之)理由:如果某页被访问，可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。缺点:算法难以实现.,例:依次要访问的页号为:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2.现有3个主存块可供使用.把开始的3个页先装入内存.按FIFO,LRU调入和调出情况及中断次数如下:,7,0,1,FIFO:,K,701,201,201,231,230,430,420,423,023,023,023,013,012,2,0,3,0,4,2,3,0,3,2,2,1,调出7调出0调出1调出2调出3调出0调入2调入3调入0调入4调入2调入3,调出4调出2调出3调入0调入1调入2,共中断9次缺页中断率f=9/13=70%,7,0,1,701,012,120,调出7调出1调出2调出3调出0调入2调入3调入4调入2调入3,调出4调出0调入0调入1,203,230,304,042,423,230,203,032,312,321,共中断7次缺页中断率f=7/13=54%,LRU:,2,0,3,0,4,2,3,0,3,2,1,2,队头,队尾,队头页是最久未使用页,队尾页是当前使用页,c.最近最不经常使用调度算法(LFU)思想:总是选择内存中最近一段时间内访问次数最少的页淘汰之.(是LRU的近似算法)缺点:实现比较困难,开销大.d.最佳调度算法(OPT)思想:当淘汰一页时,一定淘汰以后不再使用的页,或者以后相当长时间内不再使用的页.缺点:是一种理想算法,实现极为困难.很难预测将来哪些页不再使用.,访问页号内存中页被调出的页5535,305,3,022,3,0512,3,1032,3,142,3,4122,3,432,3,400.3.42,设有3块内存，依次访问的作业：5,3,0,2,1,3,4,2,3,0.按Opt算法调度。依据排列调入的页，查以后不再使用或以后长时间不再使用的页淘汰。,(3)缺页中断率:衡量一个淘汰算法的优劣缺页中断率:f=F/A.其中:F:中断次数.A:访问页面的总次数.尽量减少F,降低f.影响f的因素:a.分配给作业的内存块数.分配给作业的内存块数越多,F减少,f越小.一般:对共有n页的作业,分配n/2块时,效率最高.b.页面大小.页面大,信息量大,作业的页数减少,缺页中断次数减少,f就小.c.页面调度算法调度算法不同,中断次数不同,f不同:OPT最小,FIFO约为OPT的3倍;LRU比FIFO要小.d.与编程的方法有关,例:将128128数组置初值为0,数组每个元素占一个字.设页面为128个字.数组每一行的元素存入一页中,能提供程序使用的内存块只有一块,开始将第一页装入内存.varA:array1.128ofarray1.128ofinteger;forj:=1to128dofori:=1to128doAi,j:=0;按列清0:每执行Ai,j:=0就产生一次中断.第一次,A1,1:=0,但下一个元素A2,1不在该页中,产生缺页中断,这样,共产生128128-1次中断.若按行清0:fori:=1to128doforj:=1to128doAi,j:=0;每装入一页,就能对一行中128个元素逐一清0之后,才产生缺页中断.共产生中断次数128-1.,4.多级页表:windows2000采用二级页表结构:,页号1页号2页内地址k,0910192031,01.i.1023,一级页表,01.i.1023,二级页表,01.i.1023,01.j.1023,01.k.4095,主存块,5.系统的抖动(颠簸)简单地说，主存和辅存之间的频繁页面的置换现像称为“抖动”危害:花费系统开销,导致系统效率急剧下降.解决抖动问题:选择好页面调度算法,避免抖动.抖动发生时,采用相应的技术测试并消除.,6.请求页式管理的优缺点优点:为用户提供了大容量的虚拟存储器.更有效地利用了内存空间.多道程序运行的程度更高.更加方便用户,特别是大作业用户.缺点:为处理页面中断要花费系统的开销.为防止系统抖动,要采取一些附加措施,进一步增加了系统的复杂性.,练习题一.单选题1.存储管理的目标是（）。A.方便用户B.提高内存的利用率C.方便用户和提高内存的利用率D.增加内存的实际容量2.动态地址重定位需要由（）来实现。A.硬件B.软件C.操作系统D.硬件和软件相互配合3.碎片现象的存在使（）。A.内存空间利用率降低B.内存空间利用率提高C.内存空间利用率不影响D.外存利用率得到改善4.可变式分区管理中，（）采用按分区大小递增次序安排空闲区的链表结构。A.最环适应算法B.LRUC.首次适应算法D.最佳适应算法5.在分页存储管理中，采用（）实现地址变换。A.位示图B.页表C.空闲区表D.A和C6.系统“抖