第5章存储管理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 存储管理,存储管理主要是研究进程如何占用主存。,包括三个方面的内容：,取：该将哪个进程从辅存调入主存。分“请调”和“预调”。,放：将取来的进程按何种方式放在主存的什么地方。,替换：将哪个进程暂时从主存移到辅存，以让出空间供其他进程占用。,“放”是存储管理的基础。,连续的。即程序和数据必须放在主存的一片连续空间。,不连续的。即程序和数据可以放在主存的多个不相邻的块中。,5.1,连续空间分配,5.1.1,单道连续分配,系统只有单道用户程序，连续存放于主存中。,1.,存储分配与空间保护方法,操作系统,用户程序,0,a,a+1,n,仅将主存空间分成两块，为避免用户程序执行时访问操作系统空间，通过硬件实现存储保护。,界地址寄存器,CPU,Aa,地址,A,T A,F,程序异常处理,主存,越界地址检查机构,2.,覆盖,当作业较大时，存储空间容不下用户程序，可用覆盖解决。,基本思想：把用户程序分成一个固定区和多个覆盖区。将经常活跃的部分放在固定区，其余部分按执行顺序分别占用覆盖区。,例：,A(4k),B(6k),C(4k),D(6k),F(8k),E(10k),操作系统,固定区（,4k,）,覆盖区,0,（,6k,）,覆盖区,1,（,10k,）,过程间的调用关系,主存区域的划分,B,C,E,D,F,（,0,，,0,）,（,0,，,1,）,（,1,，,0,）,（,1,，,1,）,（,1,，,2,）,操作系统,A(4k),C(4k),D(6k),D,E,操作系统,A(4k),C(4k),E(10k),6k,10k,说明：覆盖技术把解决空间不足的问题交给用户，操作系统提供将覆盖段调入主存的系统调用，但用户必须自己说明覆盖段，并安排调入覆盖段。,3.,交换,基本思想：把处于等待状态的作业从主存移到辅存，叫换出；把竞争,CPU,的作业从辅存移到主存，叫换入。,注意：当作业处于等待状态准备出交换时，是否满足换出条件。如果作业正进行,I/O,活动则不能换出，否则该作业的,I/O,数据区将被换入作业占用。也可开辟缓冲区，将输入输出活动在其中进行，此时作业交换不受限。,5.1.2,多道固定划分法,主存可存放多道作业，作业间应进行保护。,1.,存储划分、地址重定位与空间保护方法,操作系统,U1,U2,Un,将用户空间分成长度固定的几块，根据常见作业的大小来划分，系统运行过程中收集统计信息重新修订各块的大小。,相关概念：,地址重定位,：将目标代码中相对于,0,的地址开始的所有指令、数据地址变换成主存物理地址。,静态重定位,：在将目标代码加载到主存时，将所有地址改为“原地址,+,目标代码所在主存起始地址”（链接时装配成绝对地址）。,动态重定位,：用硬件地址转换机构在执行访存指令时将“原地址,+,目标代码所在主存起始地址”后进行访问（指令执行时转换成绝对地址）。,上、下界寄存器,和,地址检查机制,（静态重定位）,基址寄存器,、,长度寄存器,和,动态地址转换机制,（动态重定位）,上界寄存器,下界寄存器,CPU,地址,A,T A,T A,主,存,程序性异常,F,F,硬件提供一对寄存器，分别存放运行程序的上、下界地址。当,CPU,分配给某道作业时，即将该作业的上、下界分别装入。,当程序被执行时，每访问一次主存，地址检查机制将,CPU,提供的访存地址与上、下界寄存器的值进行比较。,地址检查机制,长度寄存器,基地址寄存器,CPU,+,地址,A,T A,主,存,程序性异常,F,基地址寄存器,存放程序在主存的起始地址，,长度寄存器,存放程序总长度。,程序运行时，每访问一次主存，将访存地址（相对地址）与长度寄存器的值进行比较，若越界则终止该程序，否则与基地址寄存器中的值相加成为绝对物理地址。,动态地址转换机制,2.,作业存储调度,多道固定划分法下，作业调度分为多队列法和单队列法。,操作系统,4k,6k,12k,1k 2k,4k,5k 6k,11k 8k,8k,多队列作业,操作系统,4k,6k,12k,4k 5k,3k,7k,单队列作业,3.,存储碎片,存储碎片：未得到利用的空间称为碎片。,内部碎片：若存储长度为,n,，该块存储的作业长度为,m,，则剩下空间（,n-m,）称为内部碎片。,外部碎片：若存储块长度为,n,，作业长度超过该块，使该块长时间得不到使用，称该块为外部碎片。,5.1.3,多道连续可变划分法,1.,管理方法,系统设置一张表，用于登记主存空间用户区域中未占用的空闲块。例：,P113,存储区域的变化。,（,1,）分配存储空间,算法表示：,P114,分配策略：首次满足法、最佳满足法、最大满足法。,（,2,）回收空间,若收回的块与,F,中某些块相邻，则合并这些块。（什么时候空闲块个数减,1?),2.,可用空间的管理,多道可变连续划分法采用数组或链表管理可用空间。,数组：用一个数组登记可用空间的分配情况。当数组项为,0,时表示该项对应的存储分配单位为空闲，为,1,时表示占用。,链表：在每个可用块的低地址部分设两个域，分别是指针域和表示块长的长度域。,紧致：通过移动主存中作业位置，使可用空间连成一片。,总结,P115,表,5.2,5.2,不连续空间分配,连续存储易出现大量碎片，为充分利用存储空间引入不连续分配策略。,5.2.1,页式管理,避开作业连续分配的要求。,1.,空间安排,页式系统中，用户编程地址和主存中地址失去简单对应关系。需对两种空间加以区分。,逻辑空间,和,逻辑地址,：用户编程时所设想的空间和所用地址。,物理空间,和,物理地址,：主存空间和对应地址。,逻辑空间、物理空间及辅存空间均以相同长度为单位进行等分。逻辑空间划分出的区域称为,页,；物理空间划分出的区域称为,页帧,；辅存划分出的区域称为,块,。,2.,动态地址转换机制,程序运行时，须由硬件提供地址转换机构将逻辑地址转换成物理地址。,（,1,）页表,把逻辑地址对应的物理地址登记在一张称为页表的表中。逻辑空间有,N,页，页表就应有,N,项。,1,页,0,页,2,页,3,页,4,页,8,1,5,3,0,0,1,2,3,4,5,6,7,8,（,2,）地址结构,逻辑地址和物理地址均可分解成两部分。,逻辑地址：页号,P,，页内位移,d,。,物理地址：页帧号,f,，页帧内位移,d,。,求解公式：,P=,逻辑地址,/,页面大小,d=,逻辑地址,P,页面大小,例如：页面大小为,512,字节，地址,539,属于第,1,页，页内位移为,27,。,P=LA/,页面大小，,d=LA,P,页面大小,逻辑地址,LA,页表起,始地址,f,f,页面大小,物理地址,（,3,）有关页面大小的考虑,可将加减乘除运算改成位移。,例如：页面大小为,512,字节，即,2,的,9,次方。则逻辑地址,539,的转换过程如下：,（,539,）,10,=,（,1000011011,）,2,1,0,0,0,1,1,0,1,0,1,0,8,P,d,P,d,0,k,页表,起始地址,+,f,页表,f,d,说明：页面不可过大也不可过小。太大失去分页意义，太小一方面造成页表过大，一方面空间管理开销太大。,页面取,512,，,1024,，,2048,，,4096,字节。,（,3,）联想存储器,用户访问一次存储单元实际需要访问两次主存，使得运行速度下降一半。将经常使用的页表项置于快速存储器（联想存储器）可加快速度。,联想存储器,：一种高速存储体。每一项由两部分组成：关键字和值。,P,d,K1,f1,K,f,Kn,fn,P,P,P,f,d,LA,PA,页表起始地址,+,页表,f,P,d,f,d,P1,P2,P,Pk,Pn,f2,f,fk,fn,f1,联想存储器,假设访问主存的时间为,750ns,，搜索联想存储器的时间为,50ns,，命中率为,80%,，求出平均访存指令执行时间为：,80%,（,50+750,）,+20%,（,50+750+750,）,=950 ns,与非页系统相比，访问速度降低,26.6%,。,3.,可用空间管理,页式系统把所有可用页帧组成一个链表或数组。当作业进入主存时，检查现有可用页帧是否满足，若不满足则不能分配。,工作过程如下：,P119,例,1,：某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为,32M,，页的大小是,4K,。假定某进程的大小为,32,页，请回答如下问题：,(1),写出逻辑地址的格式。,(2),该进程的页表有多少项？,例,2,：操作系统采用分页式存储管理方法，要求,(),。,A,、每个进程拥有一张页表，且进程的页表驻留在内存中。,B,、每个进程拥有一张页表，但只要执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中。,C,、所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中。,D,、所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中，以最大限度地节约有限的内存空间。,例,3,：假定在某采用分页式存储管理的系统中，主存容量为,M,，被分成,1024,块，块号为,0,，,1,，,2,，,，,1023,。某作业的地址空间占,4,页，其页号为,0,、,1,、,2,、,3,，被分配到主存的第,28,、,46,、,12,、,57,块中。回答：,(1),主存地址应该用,(),位来表示。,(2),作业每一页的长度为,(),；逻辑地址中的页内地址 应占用,(),位来表示。,(3),把作业中每一页在分到的主存块中的起始地址填入下表。,页号,起始地址,页号,起始地址,0,2,1,3,例,4,：假定某操作系统存储器采用页式存储管理，页的大小为,64,字节，假定一进程的代码段的长度为,702,个字节，页表如左表所示。该进程在联想存储器中的页表如右表所示。,现进程有如下的访问序列：其逻辑地址为,八进制,的,105,、,217,、,567,、,1120,、,2500,。试问给定的这些地址能否进行转换？,页号 页帧号,0 F0,1 F1,2 F2,3 F3,4 F4,5 F5,6 F6,7 F7,8 F8,9 F9,10 F10,页号 页帧号,0 F0,1 F1,2 F2,3 F3,4 F4,例,5,：在页式存储系统中选择页的大小，需要考虑下列哪些因素,?,（,1,）页面大的好处是页表较小。,（,2,）页面小的好处是可以减少由内部碎片引起的内存浪费。,（,3,）通常，影响磁盘访问时间的主要因素不在于页面的大小，所以使用时可优先考虑较大的页面。,例,6,：,（,1,）,在采用请求分页式存储管理的系统中，地址变换过程可能会因为（）、（）和（）等原因而产生中断（,2,）在可变分区存储管理中，分区的保护通常采用（）和（）两种方式。,例,7,：在页式系统中：,(1),如果一次存储访问需,1.2s,，那么访问一次页面要多少时间,?(2),如果增加,8,个单元联想存储器，且查询联想存储器的命中率为,75%,，那么等效存储访问时间为多少,(,假定在联想存储器中查找一个页表项所需时间为零,)?,4.,共享与保护,有些代码应可以共享。在连续分配模式下，共享是不可能的。,在页式系统中的共享：,edit1,edit2,edit3,data1,J1,edit1,edit2,edit3,data2,J2,edit1,edit2,edit3,data3,J3,3 4 6 1,J1,3 4 6 2,J2,3 4 6 5,J3,0,1,2,3,4,5,6,7,edit1,edit2,edit3,data1,data2,data3,页式管理的越界保护：设置页表长度寄存器，查页表之前，首先检查页号是否越界。（需要查页内位移越界吗？）,新的问题：可共享后对共享页要进行特殊保护，称为操作访问保护。在页表项增设一个存储保护域，项目有读、写、执行。,P120,表,5.3,总结：页式管理空间利用好、管理方法简单，但将空间按页划分不符合用户需求。用户看待程序是以自然段为单位，保护与共享也以自然段划分。例：图,5.19,、图,5.20,5.2.2,段式管理,1.,空间安排,按照用户作业的自然段划分逻辑空间。例如：,主程序,子程序,1,子程序,2,数据,OS,子程序,2,主程序,子程序,1,数据,段的划分,作业在主存中以段为连续存放单位,逻辑地址：段号,S,，段内位移,d,。,注：页式系统中，逻辑地址的页号和页内位移对用户透明；段式系统中段号和段内位移由用户提供。,段式系统对物理空间的管理与多道连续可变划分法一样，但不要求作业在主存中以整个作业为连续单位，而以段为连续单位。,2.,动态地址转换,与页式系统基本相同。,段表：段表项内容（页表中为什么没有页内位移越界？）,保护码,保护码,段长（越界）,本段在主存的起始地址,段式管理地址装换过程,P122,图,5.24,例：某段式存储存器中采用如下段表，计算,0,432,、,1,10,、,2,500,、,3,400,的内存地址。,段号,段的长度,主存起始地址,0,660,2219,1,140,3300,2,100,90,3,580,1237,4,960,1959,3.,共享,与页式管理基本相同。,主程序,SIN,数据,主程序,SIN,子程序,1,子程序,2,SIN,J1,J2,共享时必须注意的问题：,若被共享的段引用自身的某个地址，则各程序必须用同一段号来共享这一段。例如：程序被两个进程共享,SQRT(X,Y),If(X,0)then,goto,L,Y=“X,开方的结果,”,RETURN,L:“,报告出错,”,RETURN,作业,J1,和,J2,分别将共享段,SQRT,安排在逻辑空间的第,1,段和第,0,段，出现问题：,SQRT,段调入主存时应该将语句（,1,）的符号地址转换成逻辑地址，即把,L,换成（段号，,L,），应该把段号置成,1,还是,0,？,A,段,SQRT,B,段,SQRT,J1,J2,J1,J2,A,段,SQRT,B,段,5.2.3,段页式管理,将段式和页式结合起来。,1.,空间安排,主程序,子程序,数据,0,1,0,1,0,1,2,3,逻辑地址组成：,段号、页号、页内位移,段表,页表,用户程序,2.,动态地址转换,保护码 长度 页表始地址,段表,页表,主存,地址转换,P124,图,5.29,增加联存,3.,保护与共享,与段式系统相同。,第,0,段,第,1,段,第,2,段,SIN,第,0,段,第,1,段,第,2,段,SIN,段表,段表,页表,SIN,主存,SIN,SIN,总结：,P125,5.3,虚存管理,