基本分段存储管理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,School of Management,Tianjin,University,SLIDE,*,基本分段存储管理,4.4,基本分段存储管理方式,分段存储管理引入的主要原因,方便编程,信息共享,信息保护,动态增长,动态链接,模块化程序设计的分段结构,分页存储管理,-,一维地址结构,分段存储管理,-,二维地址结构,School of Management,Tianjin,University,基本分段存储管理,模块化程序设计的分段结构,子程序段,X,数组段,A,call X,(,调用,X,段的入口,E),call Y,(,调用,Y,段的入口,F),load 1,A,(,调用数组段,AG),主程序段,E：,F：,子程序段,Y,G：,工作区段,School of Management,Tianjin,University,基本分段存储管理,分段系统的基本原理,每个段定义了一组逻辑信息，主程序段，子程序段，数据段等,用段号代替段名,两维逻辑地址：段号段内地址,许多编译程序支持分段方式，自动根据源程序的情况产生若干个段,段号,段内地址,a:,分段,31 16 15 0,School of Management,Tianjin,University,基本分段存储管理,b:,作业表和,段表,XXX,XXX,始址,第0,段,第,1,段,段号,段表,XXX,XXX,长度,第,2,段,作业名,B,A,段表始址,XXX,表段长度,XX,作业表,XX,XXX,内存空间,(D)=2,Main=0,(X)=1,段号,始址,长度,存取方式,内外,访问位,School of Management,Tianjin,University,基本分段存储管理,地址变换机构,当作业访问某段,(x),时，其逻辑地址,(x,，,W),中的段号,S,先与控制寄存器的段表长度相比较，若,x,段表长度，则产生段号越界中断，停止作业运行。否则将段号,S,与控制寄存器的段表始址相加，形成访问段表的主存地址,School of Management,Tianjin,University,基本分段存储管理,段控制寄存器,段表始址 段表长度,2 100,段号,段长 基址,物理地址,越界,?,段表,1K,6K,600,4K,500,8K,200,9200,段号,s,位移,d,0,1,2,3,School of Management,Tianjin,University,基本分段存储管理,分页与分段的主要区别：,段是信息的,逻辑单位,，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的,物理单位,，是为了管理主存的方便而划分的，对用户是透明的。,页的大小固定不变，由系统决定。段的大小是不固定的，它由其完成的功能决定。,段式向用户提供的是二维地址空间，页式向用户提供的是一维地址空间，其页号和页内偏移是机器硬件的功能。,由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制,。,School of Management,Tianjin,University,基本分段存储管理,段的共享,分段易于实现段的共享，即允许若干个进程共享一个或多个分段,段的共享，是通过不同作业段表中的项指向同一个段基址来实现。,几道作业共享的例行程序就可放在一个段中，只要让各道作业的共享部分有相同的基址,/,限长值。,对共享段的信息必须进行保护,School of Management,Tianjin,University,基本分段存储管理,School of Management,Tianjin,University,基本分段存储管理,21,22,60,71,80,21,22,60,61,70,内存,Ed1,Ed2,Ed40,Data1,Data10,Data1,Data10,页表,Ed1,Ed2,Ed40,Data1,Data10,进程,1,Ed1,Ed2,Ed40,Data1,Data10,School of Management,Tianjin,University,基本分段存储管理,Editor,Data1,Editor,data2,段长,基址,160,80,40,240,160,80,40,380,Editor,Data1,data2,进程,1,进程,2,段表,80,240,280,380,420,分段系统中共享,editor,段的示意图,School of Management,Tianjin,University,段页式存储管理,段页式存储管理方式,引入：分页和分段管理方式各有其优缺点，分页系统能有效提高内存的利用率，而分段则能更好地满足用户的需要，因此可以将两者结合成一种新的存储管理方式系统称为“,段页式系统,”。,基本原理：,一个进程中所包含的具有独立逻辑功能的程序和数据仍被划分为段，并有各自的段号,S,。,把段,S,划成若干个页，和页式系统一样。,School of Management,Tianjin,University,段页式存储管理,段表和页表,在段页式系统中,每个分段又被分成若干个固定大小的页面，那么每个段又必须建立一张,页表,把段中的虚页变换成内存中的实际页面。,每个段有一个页表，,段表,中应有专项指出该段所对应页表的,页表始址,和,页表长度。,段号,(S),段内页号,(P),页内地址,(W),地址结构：,School of Management,Tianjin,University,段号,状态,页表长度,起始地址,0,5,1024,1,7,1029,2,9,1036,段表长度 起始地址,段表地址寄存器,页号,状态,块号,1,1,12,2,1,19,3,1,214,0,8,5,1,10,页号,状态,块号,1,29,3,School of Management,Tianjin,University,段页式存储管理,段页式地址变换过程,配置一个段表寄存器，段表始址和段长,首先用段号和段长进行比较，查看是否越界,未越界，用段表始址和段号查出该段所对应的段表项的位置,通过查段表项得到该段的页表始址，利用段内页号,P,获得对应页的页表项位置,读出该页所在的物理块号,b,，再利用块号,b,和页内地址来构成物理地址,School of Management,Tianjin,University,段页式存储管理,段表地址寄存器,段表长度 起始地址,s p d,页表长,页表基址,物理地址,块号,s p p,P+d,p,虚拟地址,联想存储器,段表,S,段的页表,段页式地址变换机构,School of Management,Tianjin,University,虚拟存储器原理,4.5,虚拟存储器的基本概念,程序的局部性原理：,指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中。又可细分时间局部性和空间局部性。,程序中只有少量分支和过程调用，大都是顺序执行的指令,程序包含若干循环，是由相对较少的指令组成，在循环过程中，计算被限制在程序中很小的相邻部分中。,School of Management,Tianjin,University,虚拟存储器原理,很少出现连续的过程调用，相反，程序中过程调用的深度限制在小范围内，一段时间内，指令引用被局限在很少几个过程中。,对于连续访问数组之类的数据结构，往往是对存储区域中相邻位置的数据的操作。,程序中有些部分是彼此互斥的，不是每次运行时都用到的，如出错处理程序。,基于程序局部性原理和上述情况，就,没有必要,把,一个作业一次性,全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入。,School of Management,Tianjin,University,虚拟存储器原理,虚拟存储器的定义：,在具有层次结构存储器的计算机系统中采用自动实现请求调入功能和部分对换功能，这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为“,虚拟存储器,”。,虚拟存储器是为扩大主存而采用的一种设计技巧，它的容量与主存大小无直接关系，而受限于计算机的地址结构及可用的辅助存储器的容量。,School of Management,Tianjin,University,虚拟存储器原理,虚拟地址空间,处理器,虚地址,存储,管理,部件,实地址,主存,辅存,物理地址空间,虚拟存储器的概念图,School of Management,Tianjin,University,虚拟存储器原理,实现虚拟存储器必须解决好以下有关问题：,主存辅存统一管理问题、,逻辑地址到物理地址的转换问题、,部分装入和部分对换问题。,虚拟存储管理主要采用以下技术实现：,请求分页虚拟存储管理,请求分段虚拟存储管理,请求段页式虚拟存储管理,School of Management,Tianjin,University,虚拟存储器原理,置换时以页面（段）为单位，为了实现请求调页（段）和置换功能，系统必须提供相应的硬件支持和软件支持：,请求分页（段）的页（段）表机制，是在页（段）表机制上增加若干项形成的。,缺页（段）中断机构,地址变换机构,实现请求分页（段）的软件。包括实现请求调页（段）的软件和实现页（段）的置换功能的软件。,School of Management,Tianjin,University,请求分页存储管理,4.6,请求分页存储管理方式,请求分页中的硬件支持,页面机制,页号、驻留位、内存块号、保护位、访问位、修改位,驻留位（中断位）：表示该页是在内存还是在外存,访问位：根据访问位来决定淘汰哪页（由不同的算法决定）,修改位：查看此页是否在内存中被修改过,School of Management,Tianjin,University,请求分页存储管理,保护位：读,/,写,/,执行,禁止缓存位：采用内存映射,I/O,的机器中需要,缺页中断,当要访问的页面不在内存时，便产生一缺页中断，请求,OS,将所缺的页面调入内存。经历保护,CPU,环境、分析中断原因、转入缺页中断处理程序进行处理、恢复,CPU,环境等步骤。,缺页中断具有自己的一些特征：在指令执行期间产生和处理中断信号,页号,中断位,内存块号,保护位,访问位,其它,辅存位,School of Management,Tianjin,University,逻辑空间地址,主存,(,用户区,),CPU,逻辑地址,快表,主存,(,系统区,),运行进程页表,辅存,缺页中断处理,分解地址,访,问,MMU,查快表,命中,不命中,页表命中,发缺页中断,调页,装入、改表,查页表,运行进程页表基址,装入快表,运行进,程映象,进程切换时装入,物理地址,页框 页内地址,页号 页内地址,地址变换机构,School of Management,Tianjin,University,查快表,有登记,无登记,查页表,登记入快表,发缺页中断,在主存,在辅存,形成绝对地址,继续执行指令,重新执行,被中断指令,恢复现场,调整页表和,主存分配表,装入所需页面,主存有空闲块,保护现场,有,选择调出页面,该页是否修改,未修改,已修改,把该页写回,辅存相应位置,操作系统,硬件,逻辑地址,无,School of Management,Tianjin,University,请求分页存储管理,内存分配策略和分配算法,两种内存分配策略：固定和可变分配策略,在进行置换时，也采用两种策略：全局置换和局部置换,(1)固定分配局部置换,(2),可变分配全局置换,(3),可变分配局部置换,School of Management,Tianjin,University,请求分页存储管理,调页策略,何时调入页面：预调页策略和请求调页策略,调入过程：,缺页中断,查找页表，找到该页在外存的物理块,调入并修改页表,如果内存已满，按照某种置换算法从内存中选出一页准备换出,再把做缺的页面调入内存，修改页表中的相应表项,School of Management,Tianjin,University,页面置换算法,4.7,页面置换算法,把选择换出页面的算法称为页面置换算法，应该把那些以后不再会访问的页面换出，或者把那些停留较长时间而不会再访问的页面调出，最终的目的是达到一个较低的页面更换频率。,最佳置换算法和先进先出置换算法,最近最久未使用（,LRU,）置换算法,Clock,置换算法,School of Management,Tianjin,University,页面置换算法,最佳置换和先进先出算法,最佳置换算法,原理：调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。,通常可以获得最低的缺页率（理论上）,无法预知在进程中那个页面是未来最久时间不再被访问，因此，算法无法实现。,7,、,0,、,1,、,2,、,0,、,3,、,0,、,4,、,2,、,3,、,0,、,3,、,2,、,1,、,2,、,0,、,1,、,7,、,0,、,1,School of Management,Tianjin,University,页面置换算法,先进先出页面置换算法（,FIFO,）,这种算法的,基本思想,是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。,引入指针链成队列，只要把进入主存的页面按时间的先后次序链接,新进入的页面从队尾入队,淘汰总是从队列头进行,.,School of Management,Tianjin,University,页面置换算法,7,、,0,、,1,、,2,、,0,、,3,、,0,、,4,、,2,、,3,、,0,、,3,、,2,、,1,、,2,7,0,1,2,0,1,2,3,1,利用,FIFO,置换算法时的置换图,School of Management,Tianjin,University,页面置换算法,最近最久未使用（,LRU,）置换算法,算法淘汰的页面是在最近一段时间里较久未被访问的那页。,根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。,队列中存放当前在主存中的页号，每当访问一页时就调整一次，使队列尾总指向最近访问的页，,队列头,就是最近最少用的页。,发生缺页中断时总,淘汰队列头,所指示的页；执行一次页面访问后，需要从队列中把该页调整到队列尾。,School of Management,Tianjin,University,页面置换算法,7,、,0,、,1,、,2,、,0,、,3,、,0,、,4,、,2,、,3,、,0,、,3,、,2,、,1,、,2,7,0,1,2,0,1,2,0,3,4,0,3,4,0,2,4,3,2,利用,LRU,置换算法时的置换图,School of Management,Tianjin,University,页面置换算法,LRU,算法的实现,赋予每个页面一个访问字段，用来记录上次被访问以来所经历的时间,t,，当需要淘汰一个页面时，比较现有页面中,t,值最大的，即最近最久未使用的页面,硬件支持：,1,寄存器,为每个页设置一个多位寄存器，当页面被访问时，对应的寄存器的最左边位置,1,；,School of Management,Tianjin,University,页面置换算法,每隔时间,t,，将,r,寄存器右移一位；发生缺页中断时，找最小数值的,r,寄存器对应的页面淘汰,例如，,r,寄存器共有四位，页面,P0,、,P1,、,P2,在,T1,、,T2,、,T3,时刻的,r,寄存器内容如下：,页面 时刻,T1 T2 T3,P0 1000 0100 1010,P1 1000 1100 0110,P2 0000 1000 0100,School of Management,Tianjin,University,页面置换算法,栈,用栈来保存当前使用的各个页面的页面号，当进程访问某页面时，将该页面的页面号从栈中移出，压入栈顶。,因此栈顶始终是最新被访问页面的编号,4,，,7,，,0,，,7,，,1,，,0,，,1,，,2,，,1,，,2,，,6,School of Management,Tianjin,University,页面置换算法,时钟,Clock,置换算法,简单,Clock,置换算法,一个页面首次装入主存，其“引用位”置,1,主存中的任何页面被访问时,”,引用位”置,1,淘汰页面时,从指针当前指向的页面开始扫描循环队列，把找到的”引用位”是,1,的页面的”引用位”清,0,跳过这个页面,;,把所找到的”引用位”是,0,的页面淘汰掉,指针推进一步,School of Management,Tianjin,University,页面置换算法,扫描循环队列时，如果找到的所有页面的”引用位”为,1,，指针就会绕整个循环队列一圈，把碰到的所有页面的”引用位”清,0;,指针停在起始位置，并淘汰掉这一页,然后，指针推进一步,School of Management,Tianjin,University,页面置换算法,Page9 use=1,Page19,Use=1,Page1,Use=0,Page45,Use=1,Page191,Use=1,Page556,Use=0,Page13,Use=0,Page67,Use=1,Page33,Use=1,Page222,Use=0,下一个帧指针,n,0,1,2,3,4,5,6,7,8,一个页替换前的缓冲区状态,Page9 use=1,Page19,Use=1,Page1,Use=0,Page45,Use=0,Page191,Use=0,Page727,Use=1,Page13,Use=0,Page67,Use=1,Page33,Use=1,Page222,Use=0,n,0,1,2,3,4,5,6,7,8,下一页替换后的缓冲区状态,第,1,页框,School of Management,Tianjin,University,页面置换算法,改进型,clock,置换算法,首选置换页面：既是未使用过的页面；又是未修改的页面,由访问位,A,和修改位,M,可以组合成下面四种类型的页面：,(1),最近没有被引用,没有被修改,(r=0,m=0),(2),最近没有被引用,但被修改,(r=0,m=1),(3),最近被引用,没有被修改,(r=1,m=0),(4),最近被引用过,也被修改过,(r=1,m=1),School of Management,Tianjin,University,页面置换算法,步,1,：选择最佳淘汰页面，从指针当前位置开始,扫描循环队列。扫描过程中不改变”引用位”，把找到的第一个,r0,m=0,的页面作为淘汰页面。,步,2,：如果步,1,失败，再次从原位置开始，查找,r=0,且,m=1,的页面，把找到的第一个这样的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的”引用位”,r,置,0,步,3,：如果步,2,失败，指针再次回到了起始位置，由于此时所有页面的”引用位”,r,均己为,0,，再转向步,1,操作，必要时再做步,2,操作，这次一定可以挑出一个可淘汰的页面,School of Management,Tianjin,University,页面置换算法,计算缺页中断实例,影响缺页中断次数的原因,：,分配给进程的物理页面数,页面本身的大小,程序的编制方法,页面淘汰算法,假设固定分配,运行,FORTRAN,程序,共有,0.2510,6,次页面引用，页面大小为,256B,。分给进程的页框数分别为,6,、,8,、,10,、,12,和,14,FIFO,所产生的缺页中断基本上是,Opt,的,2,倍,Clock,则比较接近于,LRU,School of Management,Tianjin,University,页面置换算法,0,5,10,15,20,25,35,40,30,0,6,8,10,12,14,FIFO,CLOCK,LRU,OPT,分配的页数,每,千,次,访,问的,缺,页,中,断,数,School of Management,Tianjin,University,请求分段存储管理,4.8,请求分段存储管理方式,为了能实现虚拟存储，段式逻辑地址空间中,的程序段在运行时并不全部装入内存，而是如同,请求式分页存储管理，首先调入一个或若干个程,序段运行，在运行过程中调用到哪段时，就根据,该段长度在内存分配一个连续的分区给它使用。,若内存中没有足够大的空闲分区，则考虑进行段,的紧凑或将某段或某些段淘汰出去。相应于请求,式分页存储管理，这种存储管理技术称为,请求式,分段存储管理。,School of Management,Tianjin,University,请求分段存储管理,请求分段中的硬件支持：,段表机制的扩充：,存取方式：用于标识存取属性，执行，只读还是读,/,写操作,访问字段：记录该段被访问的频率,修改位：表示该段在进入内存后释放已经被修改过,存在位：指示本段是否已调入内存,外存始址：表示本段在外存中的起始地址,段号,扩充位,主存始址,特征,存取权限,辅存始址,标志,限长,School of Management,Tianjin,University,请求分段存储管理,地址中断机构：,当发现要访问的段尚未调入内存时，便由缺段中断机构产生以缺段中断信号，进入缺段中断处理程序，将所需的段调入内存,由于段是程序的逻辑单位，因此不会出现一条指令出现在两个分段中，或一组相关信息被分割在两个段中的情况,但是由于段不是定长的，因此处理过程比缺页中断复杂,School of Management,Tianjin,University,请求分段存储管理,虚段,S,不在内存,阻塞请求进程,内存中有合适的空闲区吗？,从外存读入段,S,修改段表及内存空区链,唤醒请求进程,返回,空区容量总和能否满足？,空区拼接，以形成一个合适的空区,淘汰一个或几个实段，以形成一个合适空区,否,否,是,School of Management,Tianjin,University,请求分段存储管理,地址变换机构,是在分段系统地址变换机构的基础上形成的,若发现要访问的段不在内存，首先必须将所缺的段调入内存，修改段表，然后才能利用段表进行地址变换,增加了一些功能，如缺段中断的请求，及相应的处理过程等,School of Management,Tianjin,University,请求分段存储管理,分段的共享与保护,共享段表,：为了实现分段共享，在系统中配置一张共享段表，每个共享段占有一个表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了使用此共享段的所有进程的情况,School of Management,Tianjin,University,请求分段存储管理,共享进程计数,count,：整型变量记录了由多少个进程需要共享该分段,存取控制字段：对于一个共享段，不同的进程使用不同的存取权限,段号：对于一个共享段，不同的进程可以用不同的段号去访问,共享段的分配与回收,第一次请求调入时，把共享段调入内存一物理区，修改请求调入进程的段表的相应项，还要在共享段表中增加一表项，填写相关数据，把,count,置,1,School of Management,Tianjin,University,请求分段存储管理,当进程不需要该段，应将该段释放，撤销在段表中共享段对应的表项，执行,count,：,=count-1,操作，如果结果为,0,，则系统回收该共享段，以及取消共享段表中所对应的表项,分段的保护,School of Management,Tianjin,University,本章小节,内存的分配管理方式：,连续分配方式,离散分配方式,虚拟存储器单一分配方式,固定分区分配方式,动态分区分配,重定位分区分配“紧凑”,*,基本分页存储管理方式,*,基本分段存储管理方式,基本段页存储管理方式,请求分页存储管理方式,*,页面置换算法,*,请求分段存储管理方式,School of Management,Tianjin,University,习题,考虑下面的访问串：,1,，,2,，,3,，,4,，,2,，,1,，,5,，,6,，,2,，,1,，,2,，,3,，,7,，,6,，,3,，,2,假定有,4,个页块，应用,LRU,页面替换算法，计算会出现（）次缺页中断？,注意：,所给定的页块初始均为空,考虑一个由,8,个页面，每页,1024,个字节组成的逻辑空间，把它映射到容量为,32,个物理块的存储器中，试问逻辑地址和物理地址分别是多少位？并给出当进程访问某个逻辑地址中的数据时，分页地址变换机构的工作过程,School of Management,Tianjin,University,School of Management,Tianjin,University,