专升本操作系统 第四章存储管理.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四章,存 储 管 理,操作系统,Operating System,教学目的,存储器是作业驻留和活动的地方，和,cpu,一样对系统性能影响很大的瓶颈资源之一。如何让容量有限的内存被多任务安全高效共享是现代操作系统内存管理的核心任务,因此，本章着重介绍多种存储管理的方式，如分区管理，分页管理等,教学难点,页式存储管理,段式存储管理,存储管理,4.1,存储管理的概念,4.2,分区管理,4.3,分页管理,4.4,分段管理,4.5,段页式管理,存储管理的基本概念,物理内存：由系统实际提供的存储单元（通常为字节）所组成,物理内存是系统硬件（存储单元）支持的实实在在的内存，地址是一维的，存储容量受到实际存储单元的限制,虚拟内存只考虑互相关联的信息之间的相对位置，其容量只受到计算机的地址位数的限制，如处理器有,32,位地址，则它的虚拟地址空间为,2,（,32,），约,4G,虚拟地址到物理地址的映射,源程序经过编译链接后，形成一个以地址,0,位始地址的虚拟内存，每条指令或每个数据单元都在虚拟内存中拥有确定的地址，该地址称为虚拟地址。,当内存分配区确定后，就要将虚拟地址变换为内存中的物理地址，该变换过程就称为地址映射或重定位,静态映射,假设目标程序分配的内存起始地址为,BA,，每条指令或数据的虚拟地址为,VA,，则该指令或数据映射的内存地址就为,MA=BA+VA,目标程序中的所有地址部分都以,BA,为基地址进行修改,动态映射,动态映射是在目标程序执行过程中，在,CPU,访问内存之前，由硬件地址映射机构来完成将要访问的指令或数据的虚拟地址映射为内存的物理地址,地址映射机构通常由一个或多个公用的基地址寄存器,BR,和一个或多个虚拟地址寄存器,VR,组成,动态映射,BR,存放当前程序分配的内存空间的起始地址，,VR,存放当前被映射的虚拟地址，映射得到的物理地址,MA=BR+VR,只要改变,BR,的内容，就可以改变程序的内存空间，实现程序在内存中的搬家，所以,BR,又称为重定位寄存器,0 0,100 +1100,200 1200,LOAD A 200,3456,VR 200,BR 1000,Load A 200,3456,存储管理,分区管理,分页管理,分段管理,段页式管理,存储器的分区管理,基本思想,：把内存划分为若干个大小不等的区域，每个区域称为一个分区,有可变分区和固定分区两种方案,固定分区,固定分区,就是把内存划分为若干个大小不等的分区，分区的大小和分区总数可由操作员或操作系统在系统初启时建立好，一旦建好，每个分区的大小和分区的总数都是固定不变的,固定分区管理通过数据结构,分区说明表来实现,固定分区示例,区号,分区大小,起始地址,使用状态,0,32K,0K,1,1,8K,32K,1,2,16K,40K,0,3,32K,56K,1,4,64K,88K,0,OS,作业,A,（,6K,）,作业,B,（,28K,）,1,分区,2,分区,3,分区,4,分区,0,32k,40k,56k,88k,可变分区管理,与固定分区的,3,点不同：,1,、可变分区的分区建立不是在系统初启时，而是在系统运行中，在作业装入时动态建立,2,、分区的大小，不是事先设定的，而是根据作业对内存的需求量而分配的,3,、分区的个数也是变换不定的,OS,224k,OS,A,（,90k,）,134K,Os,（,90k,）,B 50k,84k,OS,A,（,90K,B,（,50K,84k,0,32,256,A 90k,B 50k,C 100k,可变分区的数据结构,位图,链表,11100011,11111000,11111000,00000000,OS,作业,A,空,作业,B,作业,C,空,作业,D,空,可变分区的管理分配策略,最先适应法,FF,最佳适应法,BF,最坏适应法,WF,三种策略比较,WF,最快能找到要分配的空闲区，它总是查找空闲链表的第一个空闲区，若能满足则分配,在内存分配上，,FF,最快，因为,BF,和,WF,均要把分配剩余的空闲区按其大小插入到空闲表的合适位置，而,FF,不改变分配剩余部分在空闲链表的位置,在内存回收上，,FF,最佳。,FF,很容易实现邻接空闲区的合并，并且不需要改变合并后的空闲区在空闲链表中的位置,FF,尽可能的分配低地址空间，保留高地址的空闲区，用于大作业分配,三种策略比较,F1,（,100k,F2,（,50k,A 30k,B 70k,C 50k,A,（,30K,）,B,（,70k,）,C,（,50K,）,B 70k,30k,A 30k,20k,分配前,WF BF FF,存储管理,分区管理,分页管理,分段管理,段页式管理,分页与分区的比较,分区的缺点,1,、当不存在能满足作业需求量的连续区时，即使空闲空间总量大于作业需求量，也不能分配,2,、导致了内存碎片问题，使得内存利用率不高,3,、合并内存碎片也要耗费大量的,CPU,时间,4,、各个作业对用于不同的分区，不利用程序段的共享,分页管理取消了存储分配连续性要求，使得一个作业的地址空间在内存中是若干个不一定连续的区域,静态分页存储管理,先来看一个饭店安排客房的例子,假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现又有一个旅游团要求入住。接待员统计了一下，说：“贵团全体都能住下，但是不能住同一楼层，更没有几个挨着的。”,对于饭店这样的安排，客人不会感到奇怪，因为旅游团的大多数团员都是两人一组；而饭店每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。,分页的基本原理,内存分配与饭店安排房间有所类似。,把作业的虚拟空间划分为若干个大小相等的块，成为页（,Page,），对所有的页从,0,依次编号，于是作业的虚拟地址可以用页号,P,和页内地址,d,来表示。,于此对应，内存空间也划分为与页大小相等的若干块，成为页帧（,Page frame,），系统以页为单位给作业分配帧，帧之间可以是不连续的，这样可以减少内存碎片，最多存在小于帧大小的内碎片，不会产生外碎片,分页的基本原理,一个作业只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。同时为这个作业建立一个页号与块号的对照表，称为页表。这好像饭店的客户登记表一样,每个块的大小是固定的，一般是,0.5KB4KB,之间的数值，而且必须是,2,的幂次,分页的基本原理,一个作业只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。同时为这个作业建立一个页号与块号的对照表，称为页表。这好像饭店的客户登记表一样,每个块的大小是固定的，一般是,0.5KB4KB,之间的数值，而且必须是,2,的幂次,思考：为什么大小要在这个范围内？,分页存储管理示例,地址转换,页式存储管理对作业的地址转换采用动态重定位技术。,设每页大小为,aKB,物理地址,=,物理块首址,+,块内地址,=,物理块号*,a+,页内地址,逻辑地址,=,逻辑页首址,+,页内地址,=,逻辑页号*,a+,页内地址,从上述过程中可以看出，分页管理每取一个数据时，都要访问两次内存，一次是访问内存中的页表，得到数据的物理地址，另一次是根据得到的物理地址，从内存中取得数据,为了提高地址变换的速度，在地址变换机构中，增加一个高速可并行查找的联想存储器，构成一张快表,分页系统地址转换过程,由指令产生逻辑地址,若逻辑页号不小于页表长度寄存器的值，则产生越界中断，否则，转（,3,）,由逻辑页号查快表，若成功，则读出物理块号，转（,5,），否则，转（,4,）,由逻辑页号查页表，从相应页表目取出该页相应的物理块号，把逻辑页号与物理块号至于快表表目中，若此时快表已满，则先按淘汰算法淘汰一个快表表目,把物理块号与页内地址写入物理地址寄存器的相应位置得物理地址,地址变换示例,作业号,页表起始,申请帧数,分配状态,A,14000,5,已分,1,、系统从作业申请表中，取出作业,A,的页表起址,14000,放入页表起址寄存器,PAR,中，把申请帧数放入,PLR,2,、由,PAR,得到,A,的页表地址为,14000,3,、将虚地址,5000,转换为页号,P,和页内地址,D,，即,P=4,，,d=904,4,、将页号与,PLR,比较，进行地址越界检查,5,、若为有效地址，则从相应的页号,4,中，取出帧号,21,6,、由块号*块长度,+,块内地址，即,21*1024+904=22408,，即为虚地址,5000,对应的物理地址,设页的长度为,1kb,，作业,A,中有一条,load 1,，,5000,取数指令,页的分配与回收,最简单的管理内存的方法是：位示图,位示图中的每一位与一个主存块对应，其值为,0,时，表示对应的主存块空闲；其值为,1,时，表示对应的主存块已分配,位示图的优点是占用主存空间少，可常驻内存，加快分配进程；,不足之处：不太直观，要进行图中每个位元素的下标值到其所对应的主存块的块号的转换,示例,设主存储器的可分配区域被分为,256,块，则只需要,33B,的位示图来作为主存分配表。其中,8,个字长,32,位的字可以描述全部,256,个块的分配使用情况，另有一个字节记录剩余的空闲块数。,页的分配与回收,还有可以采用顺序分配算法,先查看空闲块数是否能满足作业要求。若不能满足，则不进行分配，作业不能装入主存：若能满足，则根据需求从位示图中找出一些为,0,的位，把这些位置成,1,，从空闲块中减去本次占用的块数，按公式“块号,=,字号*字长,+,位号”计算出这些位所对应的主存块号，把作业装入到这些块，并为作业建一张页表,动态分配存储管理,静态分页管理要求每个作业在分配到所申请的全部帧后才能装入运行。,静态缺点：当前可用帧数小于作业的需求量时，作业不能运行；作业的大小也受到了帧总数的限制,而动态分页的思想是：每次只装入一部分，其他部分在执行过程中动态装入,动态分页管理的任务,调入策略：,当作业需要的信息不在内存中时，系统才把所需的页调入内存,替换策略：,解决当前内存中没有空闲帧时，如何淘汰内存中已占据的帧,地址变换：,完成将虚地址变换为对应的物理地址,主存页面分配策略,平均分配：,将内存中所以物理块等分给进入系统中的进程的做法，简单易行，但会导致“内碎片”增加和缺页率提高,按进程长度比例分配,设,Si,为进程,Pi,逻辑空间页面数，定义,S=,Si,；,m,为内存空间物理块总数，则分配给进程,Pi,的内存物理块数,Ai,为：,Ai=,Si,/S*m,按进程优先级分配,按长度和优先级分配,页面调度算法,调度算法的好坏，直接影响系统的效率,抖动：,刚被调出的帧马上要访问，调入内存后不久又要被调出，如此反复的调入调出,页面调度算法,最佳淘汰算法,OPT,淘汰算法,Belady,于,1966,提出的一种理论上的算法。每次都淘汰以后永不使用的，或者最长时间后才会被访问的页面,虽然可以保证最低的缺页率，但无法实现，因为它必须知道页面“将来”的访问情况,页面调度算法,先进先出淘汰算法,FIFO,总是淘汰最先进入内存的页面。,实现简单，只需把进程已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存最老的页面,效率不高，而且会造成,Belady,现象,Belady,现象,一般而言，内存帧数越多，一个作业发生缺页的次数越少,但,Belady,提出反例,一个作业有,5,个页，编号从,0,到,4,，页的引用顺序为,012301401234,，采用,FIFO,替换算法，当存储帧数为,3,的，缺页次数为,9,，内存帧数为,4,的缺页反而为,10,页面调度算法,最近最久未用淘汰算法,LRU,总是淘汰内存中最长时间没有被访问的帧，即淘汰最后一次访问时间距当前时间间隔最长的页面,LRU,的开销很大，必须要有硬件的支持，完全由软件实现其速度至少会减少,10,倍，所以用,LRU,的近似算法更实用,页面调度算法,二次机会淘汰算法,SC,通过对,FIFO,进行简单的改造，结合页表中的访问位而得来一种淘汰算法。,该算法首先检查位于,FIFO,链链首的页，如果它的访问位为,0,，则选择该页淘汰；如果它的访问位为,1,，则清除其访问位，将它移至,FIFO,链链尾。如此重复。,页面调度算法,时钟淘汰算法,最近未用淘汰算法,例题,已知某作业执行时页面访问次序为：,70120304230321201701,，该作业得到,3,个空闲内存块，开始时，前三页已装入内存。要求：,（,1,）试计算采用,FIFO,淘汰算法和,LRU,算法进行页面调度时产生的缺页中断次数,（,2,）求出各自的缺页中断率,例题,解：（,1,）,FIFO,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,7,7,7,0,0,1,例题,解：（,1,）,FIFO,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,7,7,7,2,2,2,2,4,4,4,0,0,0,0,0,0,0,7,7,7,0,0,0,0,3,3,3,2,2,2,2,2,1,1,1,1,1,0,0,1,1,1,1,0,0,0,3,3,3,3,3,2,2,2,2,2,1,例题,解：（,1,）,FIFO,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,p p p p p p p p p p p p,一共产生,12,次缺页,7,7,7,2,2,2,2,4,4,4,0,0,0,0,0,0,0,7,7,7,0,0,0,0,3,3,3,2,2,2,2,2,1,1,1,1,1,0,0,1,1,1,1,0,0,0,3,3,3,3,3,2,2,2,2,2,1,例题,LRU,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,1,1,1,0,0,7,例题,LRU,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,1,1,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,0,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,7,0,1,2,2,3,0,4,2,2,0,3,3,1,2,0,1,7,例题,LRU,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,p p p p p p p p p,一共产生,9,次缺页,1,1,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,0,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,7,0,1,2,2,3,0,4,2,2,0,3,3,1,2,0,1,7,例题,（,2,）,FIFO,缺页率为：,12/20*100%=60%,LRU,缺页率为：,9/20*100%=45%,存储管理,分区管理,分页管理,分段管理,段页式管理,分段式存储管理基本思想,分页和分区存储管理对用户提供的是一个线性的地址空间，即作业的地址都是从,0,开始顺序编址,但是，一个作业的地址空间都有一定的逻辑关系，例如可以划分为主程序、子程序和各种数据结构（数组、栈、文件等），因此，如果按照各个逻辑结构来申请作业的地址空间并进行管理，将非常有利于程序设计。,基本思想：将作业按逻辑上有完整意义的段划分，每段都有自己的名字，以段为单位分配内存并进行内外存交换,段式管理的基本原理,将程序的地址空间划分为若干个段,(segment),，这样就使得每个进程都有一个二维的地址空间（段号,+,段内相对地址）,为每个段分配一个连续的分区，而进程中的各个段可以不连续的存放在内存的不同分区中。,程序加载时，操作系统为所有段分配其所需的内存，各段之间不必连续，物理内存的管理采用动态分区的管理方法。,段式物理地址分配回收,分配,：在为某个段分配物理内存时，可以采用最先适应法、最坏适应法和最佳适应法等,回收,：回收某个段占用的空间时，要注意将回收的空间与其相邻的空间合并,段式管理的数据结构,为了实现段式管理，操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射，并跟踪物理内存的使用情况，以便在装入新的段的时候，合理的分配内存空间,数据结构,进程段表,：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段都有段基址（,base address,）,系统段表：,系统所占用段,空闲段表,：内存中所有空闲段，可以结合到系统段表中,系统段表和空闲段表通常是结合为一张表,存储管理过程,分段式存储管理中以段为单位进行内存分配，每段分配一个连续的内存区，各段之间的内存区不一定连续，且各个内存区也不等长。,内存的分配和释放是需要动态进行的。当要求调入某段时，若内存中有的足够空闲区满足该段的长度，则可以采用与分区式管理相同的几种分配和释放算结；,若内存中没有足够的空间，那采用几种的替换算法，多次替换直到换到能满足调入段的长度为止,段表,段号,装入标志位,段长,内存始址,0,Y,（表示某段已调入内存）,2k,2k,1,Y,3k,8k,2,N,1k,系统为每个运行的作业建立一个段表,段式管理的地址变换,在段式管理系统中，整个的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成,为了完成进程逻辑地址到物理地址的映射，处理器会查找内存中的段表，由段号得到段的首地址，加上段内地址，就得到实际的物理地址,这个过程也是由处理器的硬件直接完成的，操作系统只需在进程切换时，将进程段表的首地址装入处理器特定寄存器中。这个寄存器一般被称为段表地址寄存器,段式地址切换,段表地址寄存器 内存,段表,34c4,虚拟地址,段号 段内地址,段表起始地址,1,1c4,段号,始地址,0,1500,1,3400,与页式系统类似，段表放在内存中，每访问一次数据都要两次访问内存，从而降低了计算机的速度。解决这个问题的方法也是在处理器增加一个高速关联处理器，用于保存经常使用的段表项,由于一般段表项的数目比页表项的数目少的多，其所需的关联存储器也相对小的多，因此可以显著减少存储数据的时间,页式和段式的区别,相似之处：,两者都采用离散分配方式，且都通过地址映射机构来实现地址变换,不同之处：,1,、页是信息的物理单位，分页也是为了实现离散分配方式，以减少内存的碎片，提高内存的利用率。可以这么说分页是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组相对完整的信息。分段的目的是为了更好的满足用户的需要,页式和段式的区别,2,、页的大小是固定的，且由系统决定。而段的长度是不固定的，且决定于用户所编写的程序，通常由编译系统在对源程序进行编译时根据信息的性质来划分,3,、页的地址空间是一维的，即单一的线性地址空间，程序员只需要利用一个标识符，即可以表示一个地址。分段的地址是二维，程序员在标示一个地址时，即需要给出段名还有段内地址,分段式管理的优点,没有内碎片，外碎片可以通过内存紧缩来消除；,便于实现内存共享和保护（可以分别编写和编译源程序的一个文件，并且可以针对不同类型的段采用不同的保护，也可以按段位单位来进行共享）；,便于实现动态链接,缺点,提高了硬件的成本,段的长度受到了内存可用大小的限制，因为段是管理也是一次性将进程装入内存,增加了系统的复杂性,有可以产生抖动现象。与动态分页式管理一样，若替换算法不恰当，则可能产生抖动现象,存储管理,分区管理,分页管理,分段管理,段页式管理,段页式的基本思想,由于分段式着眼于方便用户，为用户提供二维的虚拟地址空间，,分页式以提高内存利用率为动力，有效的克服了碎片，,因此，若将分段与分页结合起来，进行优势互补，这就是段页式存储管理,段页式存储管理的地址空间,作用的地址空间也是二维的，是按段划分的。但是每个段再划分为若干个大小相同的页，其地址结构由段号、段内页号和页内地址组成,程序员可见和使用的仍然是段号和段内相对地址，但是地址变换机构将会自动将段内相对地址的高几位解释为段内页号，将剩余的低位解释为页内相对地址,由于作用的地址空间最小单位不是段而是页，从而内存也可以按也划分，并按页为单位装入。这样一个段可以装入到若干个不连续的页内，段的大小也可以不受内存可用去的限制了,动态地址变换,系统为每个作业建立一张段表，每个段建立一张页表，段表中的地址是页表的起始地址，页表中的地址为页面号,内存空间,段表,寄存器,0,段页表（上）,1,号段表（下）,段表始址,段号,页表长度,页表始址,0,2,1,2,页号,其他,页面,0,1,页号,其他,页面,0,1,地址变换,寄存器 段表,段号,1,号页表,页号,页内相对地址,段表始址,段号,页表长度,页表始址,0,1,2,2,s,p,d,页号,其他,页面,0,1,作业,1.,名词解释,静态重定位、覆盖技术,2.,简答,（,1,）在可变分区管理下，采用移动技术有什么优点？,（,2,）分段式存储管理的优缺点是什么？,3.,应用题,课本,P91,页,1,，,2,，,3,