第七讲存储器管理.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七讲 存储器管理,中国科学技术大学计算机系,陈香兰,xlanchen,2013Fall,内容提要,存储器的层次结构,程序执行的基础知识、程序的装入和链接,连续分配存储管理方式,分页存储管理方式,分段存储管理,段页式存储管理,连续内存分配方式,（,contiguous memory allocation,）,Reading,：,Operating System Concepts,，,p284-,连续分配存储管理方式,单一连续,固定分区,动态分区,对换,内存通常被划分为两个分区（,partitions,）,:,系统区：常驻操作系统,，通常位于内存低端,用户区：提供给用户（进程）使用，,常位于内存高端,连续内存分配是指：,从用户区中为每个进程分配一个单独的、连续的内存空间,。,主要有以下两种方式,单一连续分配方式,多分区式分配方式,固定分区式,动态分区式（可变分区式）,单一连续分配方式,最简单,只能用于单用户、单任务系统,存储保护机制,存储管理单元，,MMU,或者不采用任何存储保护机制,出于信任，或采用再启动方式，,多分区式分配方式,支持多道程序，,用户区被进一步划分为若干个分区,每一个分区装载一个进程,多道程序度与分区的个数有关,根据分区大小是固定的还是可变的,固定分区方式,大小固定；等大小,or,不等大小,动态分区方式（可变分区方式）,动态,&,可变：内存的划分是动态的，分区的大小随进程的大小确定，分区的数目随系统的运行而不断变化,固定分区分配方式,支持多道程序，用于,60,年代,IBM,360,的,MFT,中,分区的划分方法，两种,等大小,不等大小,但分区的大小一旦确定就不再发生变化,分配算法：,按大小顺序建立分区使用表,0,分区号,大小（,KB,）,起始地址,(K),状态,1,15,30,已分配,2,30,45,已分配,3,50,75,已分配,4,100,125,已分配,操作系统,作业,A,作业,B,作业,C,30K,45K,75K,125K,225K,固定分区使用表,分配算法,缺点,内存利用率低,定义：内部碎片和外部碎片,内部碎片：已经分配出去但得不到利用的存储区域,外部碎片：不能被利用的小分区,解决方案：动态分区,动态分区分配方式,能根据进程实际需要的内存大小，动态分配,能减少内部碎片,关键,数据结构：记录内存的使用情况，特别是空闲内存,分配算法,分配和回收操作,数据结构,空闲分区表,，占用额外的空间,空闲分区链,，利用空闲分区,序号,分区大小,起始地址,状态,前向指针,N,个字节可用,后向指针,N,2,N,2,0,0,分区分配算法,在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法,首次适应算法,FF,：,First Fit,循环首次适应算法,最佳适应算法：,Best Fit=smallest,最差适应算法：,Worst Fist,largest,分区分配操作,分配,设请求的分区大小为,u.size,；,利用某种分配算法，找到待分配的分区，大小为,m.size,根据上述分区分配算法，有,m.size,u.size,判断,m.size-u.size,与,min_size,的大小,min_size,为事先约定的最小分区大小,，分割，分割出来的分配出去，余下的加入空闲数据结构,否则，直接分配,将分配到的分区的首地址返回,可以看出，动态分区分配方式中内部碎片最大不超过,min_size,回收，要考虑合并,向前合并,只需修改前一个空闲分区表项中的大小,向后合并（图）,只需修改后一个空闲分区表项中的起始地址和大小,与前后同时合并,修改前一个空闲分区表项中的大小，并取消后一个分区表项,无相邻空闲分区，无需合并,建立一个新的表项，填写相关信息，插入,上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置,动态分区分配分析,随着分配的进行，空闲分区可能分散在内存的各处,尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片,OS,process 5,process 8,process 2,OS,process 5,process 2,OS,process 5,process 2,OS,process 5,process 9,process 2,process 9,process 10,解决方案之一：紧凑,Compaction,针对外部碎片：采用紧凑的方法,紧凑：通过移动进程在内存中的位置，把多个分散的小分区拼成大分区,需要动态重定位技术支持,动态重定位分区分配算法：引入紧凑和动态重定位技术的动态分区分配算法,基本与动态分区分配算法相同,Swapping,对换,最早用于,MIT,的,CTSS,中,单用户时间片对换,对换是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存,能提高内存利用率,对换的单位：,进程：整体对换；进程对换,页、段：部分对换,对换技术需要实现三个方面的功能,对换空间的管理,进程的换出,进程的换入,Backing store,，对换空间,Fast disk,large enough to accommodate copies of all memory images for all users;must provide direct access to these memory images.,为提高速度，考虑连续分配方式，忽略碎片问题,需提供数据结构对空闲盘块进行管理,方法类似动态分区分配方法,进程的换出,第一步：选择被换出的进程,Some approaches,RR scheduling:swapped out when a quantum expires,Priority-based scheduling:Roll out,roll in,Lower-priority process is swapped out so higher-priority process can be loaded and executed.,第二步：换出,确定要换出的内容,非共享的程序和数据段的换出,共享的程序和数据段的换出：计数器,申请对换空间，换出，并修改相关数据结构,进程的换入,第一步：选择被换入的进程,考虑“静止就绪状态”的进程,其他原则,第二部：申请内存并换入,申请成功,申请失败：利用对换技术腾出内存,Schematic View of Swapping,Swapping(cont.),Context switch,Swapped in&out cost too much,Assume:process size 1MB,disk transfer rate 5MB/sec,average latency 8ms,Transfer time=1MB/(5MB/sec)=1/5 sec=200 ms,Swap time=208 ms,Swap out&in=416,Major part of swap time is transfer time,For RR scheduling,time quantum should 416ms,Problems exist for pending I/O processes swapping,内容提要,存储器的层次结构,程序执行的基础知识、程序的装入和链接,连续分配存储管理方式,离散分配方式（,Discrete Memory Allocation,）,分页存储管理方式,碎片,页,分段存储管理,从逻辑上进行分段,段页式存储管理,内容提要,存储器的层次结构,程序执行的基础知识、程序的装入和链接,连续分配存储管理方式,离散分配方式（,Discrete Memory Allocation,）,分页存储管理方式,碎片,3,b,Effective memory-access time,time needed for every data/instruction access,需要,2,次访存,Access the page table&Access the data/instruction,Solution:,A special fast-lookup hardware cache called,associative registers,or,translation look-aside buffers(,TLBs,),联想存储器，快表,Associative registers,Each register:a key&a value,Parallel search(high speed),Expensive,typically 82048 entries,Address translation(A,A),If A is in associative register,get frame#out.,Otherwise get frame#from page table in memory,联想存储器，快表,TLB miss,（,TLB,缺失）,If the page number is not in the associative registers,Get&store,Hit ratio,（命中率）,The percentage of times that a page number is found in the associative registers,Context switch,TLB flushed,TLB replacement algorithm,具有块表的地址变换机构,+,Effective Access Time,有效存取时间,设：,Associative Lookup=,time unit;memory cycle time=t time unit;Hit ratio=,Effective Access Time(EAT),EAT=(t+,)+(2t+)(1 ),=2t+t,If,(,20 ns),t(100 ns),1(80%),2(98%),:,TLB hit:20+100=120 ns,TLB miss:20+100+100=220 ns,EAT1=120*0.8+220*0.2=140 ns,EAT2=120*0.98+220*0.02=122 ns,Memory Protection,内存保护,If page size 2,n,page&frame is aligned at 2,n,so,Memory protection implemented by associating protection bit with each frame,Provide read only,read-write,execute-only protection or,Valid-invalid,“valid”:the associated page is in the process logical address space,and is thus a legal page.,“invalid”:the page is not in the process logical address space.,Valid/invalid bit example,Address space 2,14,Page size 2KB,Process size(010468),Page 5 has internal fragmentation,PTLR=6,Page 6&7 are invalid,10486,10240,12287,两级和多级页表,考虑：地址空间：,32,位；页大小,4KB,；有,2,20,即,1M,个页需要页表项：,1M,个设，每个页表项使用,32,位表示，需要,4MB,的空间,解决方案：,进一步离散,两级页表,对页表分页，建立外层页表（页目录）,则上述,4MB,的页表，进一步分为,1K,个页需要,1K,个页目录项假设每个页目录项使用,32,位表示，需要,4KB,因此，逻辑地址,where,p,1,is an index into the outer page table,and,p,2,is the displacement within the page of the outer page table.,page number,page offset,p,1,p,2,d,10,10,12,两级页表举例,具有两级页表的地址变换机构,+,+,多级页表及其性能,Level number=L,effect memory accesses time=(L+1)t,考虑高速缓存技术：,Cache hit rate of 98 percent yields:,effective access time=0.98,120+0.02,520,=128 nanoseconds.which is only a 28 percent slowdown in memory access time.,内容提要,存储器的层次结构,程序执行的基础知识、程序的装入和链接,连续分配存储管理方式,离散分配方式（,Discrete Memory Allocation,）,分页存储管理方式,碎片,页,分段存储管理,从逻辑上进行分段,段页式存储管理,分段存储管理方式,引入分段的目的，是为了满足用户在编程和使用上的需求（逻辑上）,在用户看来：,A program is a collection of segments.A,segment is a logical unit,such as:,main program,procedure,function,method,Object,local variables,global variables,common block,stack,symbol table,逻辑地址空间,A collection of segments,each segment,Two dimensional address space,A logical address,Compiler automatically constructs segments reflecting the input program.,Pascal compiler,FORTRAN compiler,C compiler,such as,gcc,段号,段内,地址,31,16,15,0,Logical view of segmentation,分段的硬件支持,段表,2-D logical address,1-D,physical addresses;,每个段表项包括,段在内存中的基地址,段的长度,Segment-table base register(STBR),Points to the segment tables location in memory.,Segment-table length register(STLR),Indicates number of segments used by a program;Segment number s is legal if s STLR.,段表举例,分段的地址变换机构,段表始址,段表,长度,+,+,段号,S,位移量,W,分页和分段的主要区别,角度和目的不同,分页：面向系统，物理上离散，减少外部和内部碎片，提高内存利用率,页是信息的物理单位,分段：面向用户，逻辑上离散，满足用户的需求,段是信息的逻辑单位，意义相对完整,大小不同,分页：大小固定，由硬件决定,分段：不固定，划分由程序决定，在编译时确定,地址空间的维数不同,分页：,1,维,分段：,2,维，段名段内偏移,分段举例,4300+53=4353,3200+852=4052,How about?,分段的好处,Relocation,，可重定位，方便编程,Dynamic,by segment table,Sharing,shared segments,same segment number,Protection,Use segment table entry,Protection bit,Read-only,execute-only,read/write,Validation bit,0,illegal segment,Protection&sharing at segment level,动态增长,动态链接,段的共享,关于代码的重入,可重入代码，又称为“纯代码”，是一种允许多个进程同时访问的代码。,绝对不允许可重入代码在执行中有任何改变,针对段的内存管理,由于段长不固定，采用动态分区管理方式,分配：,首次适应、最佳适应等等,由于大小不固定，存在外部碎片,可能要考虑“紧凑”,由于采用动态分区管理方式,内部碎片很少,内容提要,存储器的层次结构,程序执行的基础知识、程序的装入和链接,连续分配存储管理方式,离散分配方式（,Discrete Memory Allocation,）,分页存储管理方式,碎片,页,分段存储管理,从逻辑上进行分段,段页式存储管理,段页式存储管理方式,考虑在分段的基础上分页,与单纯的分段相比,在段表项中存放的不是段的起始地址，而是段所对应的页表的起始地址,段页式举例：,IA32,体系结构中的段页机制,IA32,是基于分段的，分页可选,常见的段寄存器如：,CS,DS,ES,FS,GS,SS,IA32,使用全局描述符表,GDT,或者局部描述符表,LDT,每个描述符描述一个段，包括段大小、访问权限、基地址等,使用段选择子索引一个段,IA32,的地址表示为，段：段内偏移,Linear address=segment base+segment offset,在不使用分页机制的情况下，线性地址就是物理地址否则，线性地址通过页表机制转换成物理地址,IA32 address translation,2-level page table,作业,什么是内部碎片；什么是外部碎片,画出最基本的分页地址变换机构。,分页和分段的主要区别是什么？,