第3章内存管理3.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.4,页式管理,3.4.1,页式管理的实现原理,页式管理的引入,分区存储管理的主要问题是碎片问题。,问题描述,在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户程序利用而浪费。,问题产生原因,作业要求分配的空间连续,主存有足够的空间但因不连续而不能分配,解决问题的思路,程序适应主存。将程序分开存放,分页存储管理技术。,1,分页的思想,页,(,虚拟页,),：,程序地址空间分成大小相等的页面,块,(,内存块、页块、页祯、内存页面,),：,把内存分成与页面大小相等的块思想：,当,一个,用户程序装入内存时，,针对每一页分配一个内存块。一个作业的若干连续的页，可以分配到内存中若干不连续的块中。,2,页式存储管理的数据结构：页表,页表包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息，是,OS,进行分页管理的依据。,3,3.4.2,页式地址变换,虚地址（线性地址、逻辑地址）,分页地址映射机制,虚地址切分：页号与页内位移,划分页号和页内地址的依椐：页的大小。,页内地址占虚地址的低位部分，页号占虚地址的高位部分。,假设,CPU,字长为,16,位，页的长度为,1KB,，则地址的分割为：页号的最低位等于页长度的,2,的幂指数，所以页号,P,从第,10,位开始。,2,X,=,页长度,1K,，,X,即为页号的最低位。,说明,页号的地址位数决定了页的多少，即地址空间中最多可容纳的页面数（,2,X,）,页内位移位数确定了每个页面的大小。,4,CPU,字长为,16,位，,页长为,1K,的地址分割,5,二进制表示虚地址,页号,页内位移,十六进制表示页号、页内位移,6,3,、地址变换,使用二进制方法求物理地址,将逻辑地址线性分割求出页号,P,和页内位移,W,：,若逻辑地址以十六进制、八进制的形式给出，将逻辑地址转换成二进制；,按页的大小分离出页号,P,和位移量,W,（,低位部分是位移量，高位部分是页号）；,将位移量直接复制到内存地址寄存器的低位部分；,以页号查页表，得到对应块号，将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,7,mov,dx,3badh,页号,0,1,2,3,4,5,6,7,页号,块号,0,F,1,8,2,3,3,5,4,9,5,4,6,A,7,B,0,0,1,1,1,0,1,1,1,0,1,0,1,1,0,1,块号,OS,0,1,2,3,4,5,6,7,9,8,B,A,C,D,0,10,11,15,P=7H,W=3ADH,0,0,0,0,0,1,0,1,1,0,1,1,1,0,1,0,1,1,0,1,虚地址,3BAD,，,页面大小,2K,，,用二进制方法求物理地址,物理地址,=5BADH,8,使用十进制方法求物理地址,根据逻辑地址求出页号,P,和页内位移,W,；,页号,P=,逻辑地址,%,页大小,(%,表示整除,),页内位移,W=,逻辑地址,mod,页大小,根据页号查页表得块号,B,；,物理地址,=,块号,B,页大小,+,页内位移,W,公式说明,物理地址块起始地址块内位移,W,块起始地址块长,块号,块长,=,页长,块内位移页内位移,9,块号,OS,0,1,2,3,4,5,6,7,9,8,B,A,C,D,第,0,块起始地址：,0,第,1,块起始地址：块号*页长,=1*2K,块大小：,2K,0,2K,4K,第,2,块起始地址：块号*页长,=2*2K,块起始地址计算,mov,dx,3badh,页号,0,1,2,3,4,5,6,7,10,【,例,】,：有一系统采用页式存储管理，有一作业大小是,8KB,，,页大小为,2KB,，,依次装入内存的第,7,、,9,、,A,、,5,块，试将虚地址,0AFEH,，,1ADDH,转换成内存地址。,解：,求虚地址,0AFEH,的物理地址：,0000,1,010 1111 1110,P,1 W,010 1111 1110,MR,0,100 1,010 1111 1110,4AFEH,求虚地址,1ADDH,的物理地址：,0001 1,010 1101,1101,P,3 W,010 1101 1101,MR,0010 1,010 1101 1101,2ADDH,11,【,例,】,：有一系统采用页式存储管理，有一作业大小是,8KB,，,页大小为,2KB,，,依次装入内存的第,7,、,9,、,10,、,5,块，试将虚地址,7145,，,3412,转换成内存地址。,解：,转换虚地址,3412,：,P,3412,2048,1,W,3412 mod 2048,1364,MR=9*2048+1364=19796,转换虚地址,7145,：,P,7145,2048,3,W,7145 mod 2048,1001,MR=5*2048+1001=11241,问题：块号若为十六进制的字母表示，,MR,如何计算？,(,十六进制转换成十进制,),12,例：考虑一个由8,个页面，每页有,1024,个字节组成的逻辑空间，把它装入到有,32,个物理块的存储器中，问：,（,1,）逻辑地址至少需要多少二进制位表示？,（,2,）物理地址至少需要多少二进制位表示？,分析：,逻辑地址结构由两个部分组成：,前一部分表示该地址所在页面的页号,P,；,后一部分表示页内地址,(,页内位移,)W,。,物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。,解：,因为页面数为,8=23,，故需要,3,位二进制数表示。每页有,1024,个字节，,1024=210,，于是页内地址需要,10,位二进制数表示。,32,个物理块，需要,5,位二进制数表示（,32=25,）。,（,1,）页的逻辑地址由页号和页内地址组成，所以需要,3+10=13,位二进制数表示。,（,2,）页的物理地址由块号和页内地址的拼接，所以需要,5+10=15,位二进制数表示。,3.4.3,相联存储器和快表,问题提出,在页式存储技术中，每访问一次内存，就要做两次访问内存的工作：,查页表时（页表在内存中）；,访问程序时。,为了提高查页表的速度，将当前常用的一部分页表内容存放到高速缓存（,相联存储器,）中，存放在相联存储器中的页表称之为,快表,(TLB-translation,lookaside,buffer),。,查表时首先在快表中查，只有当快表中没有时才访问内存中的页表，从而减少在内存查表的次数，达到提高查找速度的目的。,14,具有快表的地址变换机构,500-,页表起始地址,7-,页表长度,15,引入快表后的地址变换,将逻辑地址分为页号和页内位移。,将页号与相连存储器中的所有页号作比较，若有匹配，则取出对应的块号，并与页内位移拼接；若无匹配，则访问内存中的页表，取出块号，与页内位移拼接，并将该页表项放入快表。,用物理地址访问内存。,16,3.3.4,页的共享与保护,页面共享（各进程中统一页号）,17,分页管理的存储保护有两种方式：,一是由,CPU,提供的越界保护，当地址映射机构分离出页号和页内位移后，若,0,页号用户程序的总页数则访问合法，否则访问越界。,二是由操作系统在页表中为页的存取权限设置的保护位，表示该页的存取控制权限，如,r,表示可读，,w,表示可读，,e,表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制,。,18,3.5,分段内存管理,3.5.1,段式管理的引入,问题的提出,由于分页方式只考虑程序空间按页的尺寸切分，没有考虑各连续的页之间是否在逻辑上也是连续的。,逻辑上的不连续导致,请调一页，可能只用到该页中的一部分；,不方便实现段的共享和保护。,解决办法,段式管理,保留程序在逻辑上的完整性,19,逻辑地址,程序中的逻辑地址由段号和段内位移两部分（二维）组成。段,程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、数据等都可各成一段。每个段的大小可以不相等。,段号,将一个程序的所有逻辑段从,0,开始编号，称为段号。,段内地址,每一个逻辑段都是从,0,开始编址，称为段内地址。,20,代码段,数据段,栈段,段号,S,段内位移,W,程序逻辑地址,段式地址,程序逻辑地址：,S,：,XXXX,21,段式管理的基本原理,段表,地址映射：,由逻辑地址得到段号,S,和段内位移,W,；,查段表得到物理起址,B,，,加上,W,即得物理地址。,段号 段首址 段长 中断位 引用位 改变位 保护位,22,23,段的共享与保护,段的共享,实现：段表中设置指向共享段的地址指针,24,段,保护：,地址越界保护,：段起址,物理地址段起址,+,段长,段式管理中，地址越界引发的中断称为越段中断。但如果系统允许段动态增长，则应修改段表中的段长表项值。此时的段表数据结构如表所示。,设置段的存取保护位,:,可读、可写、可执行等。,相比较页的存取保护，段的存取保护更易于实现，解决了分页管理中由于页在逻辑上不具备逻辑完整性，当一页的内容涉及多个逻辑模块时，该页的存取控制难以实现的难题。,段号,段长度,起始地 址,允许动态增长,内,/,外存,访问位,25,3.5.4,分段和分页的比较,不同,（,1,）段根据用户的需要划分，便于存储保护和信息的共享；页是为了管理内存的方便而划分的，页的保护和共享受到限制。,（,2,）页的大小固定不变，由系统决定；段的大小是不固定的，由其完成的功能决定。,（,3,）段式提供的是二维地址空间；页式提供的是一维地址空间。,（,4,）段式管理可能产生内存外碎片，页式管理消除了外碎片，但有页内碎片。,26,相同,（,5,）段式与页式一样，都需要在进程运行前，全部信息装内存，内存利用不够充分。,（,6,）段式与页式一样，为实现地址变换，,CPU,要花费较大的开销，为实现管理要提供更多的表格。,（,7,）段式与页式一样，寻址都需要访问二次内存，如果要提高访问速度，都需要在相联存储器中设置快表。,27,3.6,内存扩充,3.6.1,覆盖技术,问题的提出,物理存储器的结构是个一维的线性空间，容量是有限的。,用户程序,用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。,解决办法,内存扩充,28,实现内存扩充的方法：,采用覆盖技术,采用交换技术,采用虚拟存储技术,29,覆盖技术,在为程序分配内存空间时，操作系统将程序结构分层，根据程序结构将第,0,层设置为常驻内存区。从第一层起，为该层中的多个模块设置一个共享覆盖区，其容量与该层中最大模块的容量相当。程序执行到哪个模块就将该模块送到它所共享的覆盖区中。,3.6.1,覆盖技术,30,A,、,B,、,C,、,D,、,E,、,F,总计,190K,，,实际分配,110K,31采用交换技术,在系统盘上开辟一个专门的空间作为内存的扩充，这部分磁盘空间称为,“,交换区,”,或,“,对换区,”,，由内存管理模块进行管理。,交换区的作用是当内存空间不够时，将暂时不用的进程映像调到磁盘交换区，以腾出内存空间，当再度用到被调出的这部分进程映像时再将其调回内存。,3.6.2,交换技术,32,交换技术,33,1,虚拟存储器的基本思想,问题,作业在运行时暂时不用的程序和数据，全部驻留于内存中降低了内存利用率。,解决方法,当作业开始运行时，将当前使用的部分先装入内存，其余部分先存放在外存中，等到用到这些信息时，再由系统自动把它们装入到内存中，这就是虚拟存储器的基本思想。,概念：虚拟存储器（虚拟内存）,是操作系统采用虚拟技术，在不改变物理内存实际大小的情况下提供的逻辑上被扩充了的内存。这种物理上不具备而逻辑上具备的内存就是虚拟内存。,3.6.3,虚拟存储技术,34,2.,虚拟存储技术的依据,局部性理论（,8/2,原理）,时间局部性,:,是指程序即将用到的信息可能就是目前正在使用的信息。,空间局部性,:,是指程序即将用到的信息可能与目前正在使用的信息在空间上相邻或者临近。,局部性理论的应用意义,虚拟存储管理：,程序执行时往往会,遵循局部原理,(,时间、空间,),访问内存，将部分进程存入内存，结合外存实现虚拟存储,。,35,3.,虚拟存储技术的硬件技术基础,相当数量的外存,足以存放多个用户程序,一定容量的内存,程序运行过程中，必须有一部分放在内存,地址变换机构,实现逻辑地址到物理地址的变换,36,4.,常用的虚拟存储技术,请求分页存储管理,请求分段存储管理,请求段页式存储管理,37,3.7,请求页式管理,3.7.1,请求页式管理的思想及实现,分页内存管理方式,静态分页管理,动态分页管理,静态分页管理,基本思想：进程开始执行前，将全部页装入内存。,动态分页管理（请求页式管理）,基本思想：进程开始执行前，只需装入即将运行的页面，然后根据需要载入其他页面。,38,请求分页管理要解决的问题,不在内存的页什么时候调入内存？（调入策略）,如何知道要访问的页不在内存？不在内存的页在外存的什么地方？,(,页表,),当页调入内存时，内存没有空闲块时，应覆盖（淘汰）哪些页？（淘汰策略）,被覆盖（淘汰）的页是否需要回写到辅存？（页表）,39,请求页式管理的调入策略,预测调页：分析预测，运行前调入,系统根据作业运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。,缺点,:,系统无法预计系统中作业的运行情况，难以实现。,请求调页（请求分页）：缺页请求，运行时调入,进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求将它所请求的页调入内存。,40,请求页式管理的页表结构,页表：反映该页是否在内存，在外存的位置，在内存的时间的长短，是否需要回写等。,页号：,块号：,中断位：,0,表示该页在内存，,1,示该页不在内存（需要缺页中断）,辅存地址：该页在辅存的位置,修改位：,0,表示该页调入内存后没有修改，,1,表示页调入内存后修改过,引用位：,0,表示最近没有被访问，,1,表示最近被访问过,页号 块号 中断位 辅存地址 修改位 引用位,请求分页的页表结构,41,3.7.2,多级页表,二级页表,问题：页表占用存储空间太大,解决：将页表也分页后，对页表占用的存储空间的分配也采用动态方式分配（部分分配），提高内存利用率。,页表页：将页表分页，称为页表页，大小与页面长度相同。,页目录表：为页表页建立的地址索引表称为页目录表。,二级页表机制：页,目录表是一级页表、页表页是二级页表，共同构成二级页表机制。,42,二级页表结构,43,具有二级页表的地址结构,44,二级页表机制的地址变换,45,3.7.4,请求页式管理的页面置换算法,当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法。,常用算法：,先进先出算法,FIFO,：淘汰先调入内存的页,最久未使用淘汰算法,LRU,：淘汰未被访问的页中时间最长的页,最近未使用淘汰算法,NUR,：淘汰第,1,个最近未被访问的页（淘汰页表中第一个访问位为,0,的页）,最不经常使用页面淘汰算法（,LFU,）：淘汰那些到当前时间为止访问次数最少的页。页表中增加一个访问记数器。,最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。,页面淘汰算法优劣的衡量标准：缺页中断率,f,f,f,a,（,a,是总的页面访问次数，,f,是缺页中断次数）,46,【,例,】,一个进程已分到,4,个页帧（块）（,M=4,），,其页表如下表所示，当进程访问第,4,页时产生缺页中断，请分别用,FIFO,、,LRU,、,NRU,算法决定将哪一页淘汰？是否需要回写？,页表：页号 页帧 装入时间 最近访问时间 访问位 修改位,2 0 60 161 0 1,1 1 130 160 0 0,0 2 26 162 1 0,3 3 20 163 1 1,FIFO,：,淘汰最先调入的页面（页帧为,3,的页）,修改位为,1,，,要回写。,LRU,：,淘汰最久未访问的页（页帧为,1,的页）,修改位为,0,，,不要回写。,NRU,：,淘汰最近未使用的页，淘汰第一个访问位为,0,的页（页帧为,0,的页）,修改位为,1,，,要回写。,47,【,例,】,对访问串：,1,、,2,、,3,、,4,、,1,、,2,、,5,、,1,、,2,、,3,、,4,、,5,，指出在驻留集大小分别为,3,和,4,时，使用,FIFO,（,先进先出,）和,LRU,（,最久未使用,）,置换算法的缺页率，结果说明了什么？,（设驻留,集,M,表示分给该作业的内存块数）,分析：,48,M=3,，,FIFO,淘汰先调入内存的页,M=4，FIFO,49,刚被访问,最久未被访问,M=3,，,LRU,淘汰最久未使用的页,M=4，LRU,调整,顺序,50,解,FIFO,：,M,3,f,f,a,9,12,75%,M,4,f,10,12,83%,LRU,：,M,3,f,f,a,10,12,83%,M,4,f,f,a,8,12,67%,Belady,异常现象：对于,FIFO,算法，有时会出现当,M,增加时缺页次数不是减少，反而增加的现象。,51,课堂练习：,设页面走向为：,2,、,3,、,2,、,1,、,5,、,2,、,4,、,5,、,3,、,2,、,5,、,2,，,页帧,M=3,，,试用,FIFO,和,LRU,两种算法分别计算访问过程中的缺页率。,52,3.7.5,几个需要注意的问题,5.,抖动,主存和辅存之间的频繁的页面置换 现象称为抖动，也称为颠簸，其导致系统效率急剧下降。,产生抖动的原因：,系统的淘汰算法不合理从而导致刚淘汰的页面马上又要访问的频繁的页面置换状态。,系统在考虑置换算法时既要考虑有尽可能少的缺页率、置换算法的简单性、还要尽量避免系统抖动,。,53,3.9,请求段式管理,3.9.1,请求段式管理的思想及实现,段式存储也可实现虚拟存储管理，我们称之为请求段式管理。请求段式管理的基本思想是：把作业的所有分段的副本都存放在外存上，当作业被调度投入运行时，首先把当前需要用的一段或几段装入内存，在执行过程中，访问到不在内存的段时，再通过缺段中断机构把它从外存上调入。,因此，段表必须在静态段式存储管理的基础上加以扩充。如在段表中必须附加说明哪些段已在主存，哪些段不在主存，各段在外存中的起始地址，相应的段是否已被修改过，段是否可移动、可扩充，段能否共享等。,54,请求段表的结构,55,请求段式管理的地址变换过程,(*),56,3.9,请求段页式内存管理,3.9.1,请求段页式管理的基本思想,问题引入,段式管理优点：能够反映程序的逻辑结构。,页式管理优点：有利于提高内存利用率。,请求段式管理优点：保留段式优点，且只部分调入,请求段式管理,问题,：调入段时需全部调入，会产生碎片。,请求页式管理优点：保留页式优点，且只部分调入,请求页式管理,问题,：逻辑上没有完整性，不利于共享。,解决：保留上述方式优点，克服缺点,段、页相结合,57,3.9.1,请求段页式管理的实现原理,地址的构成,逻辑上分段：便于共享和保护,虚地址组成（二维）：段号、段内位移（页号、页内位移）,内存分块：便于分配和内存的利用。,段号,S,段内位移,页号,P,页内位移,W,分解为,58,段表、段页表（页表）,段号,状态,页表大小,页表起址,给进程分配的段表,页号状态,块号,给第,X,段分配的页表,(,段页表,),59,地址变换过程,进程,A,对应的程序空间,分段,0,1,2,给进程,A,分配的段表,段页式内存管理的段表、页表和内存的关系,逻辑上分段,物理上分块,60,段页式管理地址映射,根据程序的逻辑地址得到段号和段内位移，并将段内位移根据页容量分解为页号和页内位移。,根据该进程的段表寄存器得到段表起始地址，在段表中查找该段号的表项，得到页表起始地址。,根据页号在页表中查找该页对应的内存块号。,根据块号计算得到该块的起始地址。,将块的起始地址加上页内位移，得到物理地址。,61,段页式存储管理中每次存取须经过三次主存访问,第一次：访问段表，得到页表起始地址；,第二次：访问页表，得到主存块号；,第三次：存取。,62,