os操作系统Chapter061.ppt

第六章存储管理,存储管理功能内存资源管理存储管理方式外存空间管理虚拟存储系统,学习目标明确存储管理的职能是对主存储器中的用户区域进行管理；理解在不同的管理方式下如何实现存储保护、地址转换、以及主存空间的分配和回收；比较各种管理方式的特点；掌握虚拟存储器的实现原理和方法。学习要点本章理解以下概念:逻辑地址,物理地址,可重定位地址,重定位,静态重定位,动态重定位,碎片,虚拟存储器等;对于每种存储管理技术应理解它解决什么问题,实现的思想是什么。本章主要介绍操作系统中有关存储管理的基本概念,几种常用的存储管理技术,分别讲述各自的基本思想,实现算法,硬件支持,并比较它们的特点.,编辑编译链接装入运行,程序的装入和链接,多级存储器体系示意图,现代计算机系统多级存储器体系,第六章存储管理,主存被划分成两部分：系统区：用于存放操作系统的程序和数据用户区：用于装入并存放各个用户进程的程序和数据(各进程如何占用主存，由操作系统动态实现，存储器的管理主要是针对用户区的分配和管理)存储管理需要完成的功能：存储分配存储共享存储保护存储扩充地址映射,6.1存储管理功能,存储分配系统应具有如下功能：记住内存每个位置的状态，即哪些是已经分配的，哪些是为分配的。在系统程序或用户作业提出申请时，按照所需要的大小进行分配并确定分配区域实施分配，修改分配记录表回收系统或用户释放的存储区，并修改分配记录表。,6.1存储管理功能,存储共享目的：节省内存、相互通讯内容：代码、数据存储保护防止地址越界防止操作越权,6.1存储管理功能(Cont.),存储扩充借助虚拟存储技术或自动覆盖技术来“扩充”主存容量内存、外存结合，虚拟存储体系速度接近内存，容量相当外存地址映射逻辑地址=物理地址原因:当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换硬件支持基址寄存器(base)、限长寄存器(limit)、快表；使用上述寄存器完成地址映射过程；不能正常完成地址映射时产生中断。,作业的逻辑地址空间和装入后的物理空间,当一个作业装入与其地址空间不一致的存储空间中，就得要地址变换。也就是说将逻辑地址映射为内存地址，把这种作法叫做地址重定位。(1)静态地址重定位在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。,地址映射,静态重定位示例：MovAx,100XorAx,AxMov200,Ax如装入起始地址为10000H的内存块处，则经重定位后，程序段改为：MovAx,10100XorAx,AxMov10200,Ax,（2）动态地址重定位：动态地址重地位是在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。,（b）采用动态重定位时内存空间及地址重定位示意图,（a）采用静态重定位后的内存空间,静态地址重定位和动态地址重定位示意图,1、在作业的过程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在作业过程中动态完成的。故称为动态重定位。2、程序可随机的从主存的一个区域移动到另一个区域，程序移动后仍丝毫不影响它的执行，这种技术称为。3、动态重定位是在作业的_中进行的。A、编译过程B、装入过程C、修改过程D、执行过程,6.2内存资源管理,6.2.1内存分区分区时刻静态分区：系统初始化时分；动态分区：申请时分。分区大小等长分区：2i异长分区：依程序、程序单位、对象大小。通常作法静态+等长（页式、段页式）动态+异长（段式、界地址）,6.2.2内存分配,静态等长分区的分配字位映象图空闲页面表空闲页面链动态异长分区的分配最先适应(FirstFit)最佳适应(BestFit)最坏适应(WorstFit),字位映象图（bitmap）,第0页,第2页,第1页,第k页,第n页,.,.,分配：自头寻找第一个为0的位，改为1，返回页号；去配：页号对应的位(bit)置为0。,用一个bit代表一页状态，0表空闲，1表占用。（多单元）,空闲页面表,特点：可以分配连续页面。,占用,占用,120页,121页,122页,123页,.,.,空闲页面链,占用,占用,占用,Head:,优点：节省空间。（不适合管理外存）,动态异长分区的分配,数据结构：,Criteria:尽量使空闲区域连续。,初始时一个连续空闲区。长度=0为表尾。,（1）最先适应法：按照某种次序依次检查各个空闲区，把第一个找到能容纳申请要求的内存区分配给申请者。空闲区按地址顺序从小到大登记。（2）最佳适应算法：全部空闲区按其大小递增的顺序排序，按照某一从小到大次序依次检查所有的空闲区，把能容纳申请要求的一个最接近尺寸且大于或等于作业大小的分区给申请的作业。3）最坏适应算法全部空闲区按其大小递减的顺序组成空闲区可用表或自由链，当用户作业或进程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项所有空闲区长度小于申请，则失败，否则从空闲区可用表或自由链分配相应的空间给用户，然后修改和调整空闲区可用表或由由链,从该空闲区中截取所需大小，修改调整可用表,从空闲区表第一表目顺序查找,从可用表中移去该表目，调整可用表,取下一表项,无法分配,该空闲区长度SIZE？,该空闲区长度=SIZE？,表目查完？,返回分配起始地址,否,否,否,是,是,是,最先适应算法,最先适应算法（FirstFit）,空闲区：首址递增排列；申请：取第一个可满足区域；优点：尽量使用低地址空间，高区保持大空闲区域。缺点：可能分割大空闲区。Eg.申请32将分割第一个区域。,最佳适应算法（BestFit）,空闲区：大小递增排列；申请：取最小可满足区域；优点：尽量使用小空闲区，保持大空闲区。缺点：可能形成碎片(fragment)。Eg.申请30将留下长度为2的空闲区。,最坏适应算法（WorstFit）,空闲区：递减排列；申请：取最大可满足区域；优点：防止形成碎片。缺点：分割大空闲区域。,例1：在一个分区存储管理系统中，按地址从低到高排列的空闲分区的长度分别是10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对于下列顺序的段请求12KB、10KB、15KB、18KB，分别采用最先适应算法、最佳适应算法和最坏适应算法，试说明空间的使用情况。,分区号,分区长度,1,2,3,4,5,6,7,8,10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB,(2)最佳适应算法空闲分区图,分区号,2,5,6,1,7,8,4,3,分区长度,20KB,18KB,15KB,12KB,10KB,9KB,7KB,4KB,例2：用可变分区方式管理主存储器时，假定主存中按地址顺序依次有5个空闲区，空闲区的大小依次为32K、10K、5K、228K和100K，现有5个作业J1、J2、J3、J4、J5，它们各需主存1K、10K、108K、28K和15K，若采用最先适应分配算法能把这5个作业按J1J5的次序全部装入主存么？你认为按怎样的次序装入这5个作业可使主存储器空间利用率最高？,6.2.3碎片处理,紧凑：移动占用区域，使所有空闲区域连成一片（开销很大）。,OS,P1(248k),P2(250k),8k,6k,4k,256k:,512k:,768k:,264k:,518k:,256k:,504k:,754k:,18k,6.3存储管理方式,界地址管理方式（一维地址）页式管理方式（一维地址）段式管理方式（二维地址）段页式管理方式（二维地址）,6.3.1界地址管理方式,4.3.1.1基本原理1.内存空间划分：动态异长；2.进程空间划分：一个进程一个区域，逻辑地址0l-13.进程空间与内存空间对应关系（可以浮动）：,0:,l-1:,.,.,b:,l,b+l-1:,进程空间,内存空间,6.3.1界地址管理方式,4.所需表目：(1)内存分配表-在PCB中；(2)空闲区域表：arrayof(addr,size)。5.所需寄存器：(1)基址寄存器；(2)限长寄存器。6.地址映射：,6.3.1界地址管理方式,0:,l-1:,.,.,b:,l,b+l-1:,l,b,逻辑地址,CP,+,a,a+b,步骤：(1)由程序确定逻辑地址a；(2)a与l比较判断是否越界，不满足：0al-1，越界；(3)a与b相加得到物理地址。,进程空间,内存空间,6.3.1界地址管理方式,6.3.1.2双对界代码：一对界数据：一对界6.3.1.3交换技术(swapping)交换原则：外存有可运行进程内存(1)内存有空间，直接移入；(2)内存空间不够，移出SWAIT,SSTOP状态进程；(3)如果还不够，移出SSLEEP,SRUN状态进程，6.3.1.4覆盖技术(overlay),离散分配方式可分为三种：分页式存储管理分段式存储管理段页式存储管理,6.3.2页式存储管理,6.3.2.1基本思想（工作原理）,页面与页表,1.页面：把逻辑地址空间划分为一些相等的片，这些片称为页面。2.页框：物理地址空间被划分为同样大小的片，称为物理块或页框。,页号块号03152632,01234567,内存,分页式存储管理中的地址结构：,页号P,页内位移量W,若给定一个逻辑地址空间中的地址位A,页面大小为L,则页号P和页内地址d，可得：P=INTA/Ld=AMODL设页面大小为1KB,A=2170B,则可求得P=2170/1024=2,d=2170%1024=122,分页存储管理的基本思想是：以块为单位把内存分给作业或进程，并且一个进程的若干个页可分别装入物理上不相邻的内存块中。即作业在内存中存放时会出现页号连续、而块号不连续的情况。页面映象表逻辑页物理块（页表）,页表的作用：实现从页号到物理块号的地址映射。,分页存储管理示意图,分页系统中的地址映射,通常，页表都放在内存中。当进程要访问某个逻辑地址中的数据时，分页地址映象硬件自动按页面大小将CPU得到的有效地址（相对地址）分成两部分：页号和页内地址（p，d）。以页号为索引去检索页表。从页表中得到该页的物理块号，把它装入物理地址寄存器中。同时，将页内地址d直接送入物理地址寄存器的块内地址字段中。即物理地址寄存器中的内容是二者拼接成的实际访问内存的地址。,分页中的地址转换机构,CPU,p,逻辑地址,物理地址,f,d,物理地址寄存器,拼接,例题：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048个字节，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？,例题：在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页表如下：页号块号02142638试借助地址变换图求出有效地址4865所对应的物理地址。,联想寄存器,从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问二次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。应用联想寄存器和页表相结合的方式，可有效地提高系统动态地址转换的速度，是一种行之有效的方法。,逻辑地址(p,d)物理地址(f,d)(1)由程序确定逻辑地址(p,d)；(2)由p查快表得页架号f；如查不到：(a)由p与l比较，判别是否越界：不满足：0pl-1，越界；(b)由p和b查页表得f,(p,f)快表，如满淘汰一个；(c)转(2);(3)f与d合并得物理地址,地址映射:(p,d)(f,d),地址映射机制,采用快表和页表相结合的分页地址变换过程示意图,6.3.2.2多级页表,提出背景进程虚拟空间大幅度增加单级页表需要很大连续内存空间多线程设计导致进程虚拟空间不连续性页表所占内存空间浪费例如32位进程地址空间，页长4k（占12位），页号20位，页表需要220个入口！解决策略对页表所需的内存空间，采取离散分配方式，来解决难以找到一块连续的大内存空间的问题只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再将他们调入内存。,1.二级页表,针对难于找到大的连续内存空间以存放页表的问题，可利用将页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0#页、1#页n#页。可以离散的将各个页面分别放在不同的物理块中，同样要为离散分配的页表再建立一张页表，称为外页表(OutPageTable)。,1.Two-LevelPage-TableScheme,2.多级页表,对于64位机器，若采用二级页表结构，页面仍采取4KB即212B,假定仍按物理块的大小210位来划分页表，则将有余下的42位用于外层页号。此时在外层页表中有4096G个页表；若按220来划分页表，将有余下的32位用于外层页表，每个分页将达到1MB,外层页表仍有4G个页表项，要占用16GB的连续内存空间。必须采用多级页表。,Linux的三级页表结构,6.3.2.3反置页表(invertedpagetable),传统页表面向进程空间每个进程逻辑页面有一表项当进程空间很大时，页表很大反置页表面向内存空间为每个物理块设置一个页表项并将它们按物理块号排序，其中的内容则是页号及其隶属进程的标识符。大小固定,反置页表-工作原理,程序,物理内存,fd,pidpd,f,逻辑地址,物理地址,反置页表,分段式存储管理,.分段存储管理方式的引入（1）方便编程（2）信息共享（3）信息保护（4）动态链接（5）动态增长,主程序,子程序A,子程序B,子程序C,符号表,栈,数据,段的共享,段长段首址,.,bl,.,段号si.,P1段表：,段长段首址,.,bl,.,段号sj.,P2段表：,共享段,.,.,b:,l,内存空间,信息的保护,段长段首址,.,lb101,段号s.,访问权限RWE,.,段号段长段首址,.,slb101,访问权限RWE,.,分段系统的基本原理,段式管理就是根据作业本身的内在逻辑联系，将作业划分成若干段，如把作业地址空间划分为主程序段，子程序段，数据段，工作区段，每段是一个首地址为零的连续线性地址空间，并可根据需要动态增长，每段必须有一个唯一的段名，分段后，用户作业的地址空间是二维的。,分段存储管理的基本概念,1.分段：段是一组逻辑信息的集合，每个段都有自己的名字和长度。系统为段编号段号。每个段都从0开始编址并连续，段长由该段包含的逻辑信息长度决定，不等。,Main段,P段,D段,S段,0段,1段,2段,3段,分段的逻辑地址空间,main,x,y,d,对应关系,40k,60k,80k,20k,.,.,.,.,进程空间,内存空间,100k:,200k:,300k:,320k:,分段存储管理的地址变换,1程序的逻辑地址结构2段表3分段动态地址变换过程4分段与分页的区别,1程序的逻辑地址结构,分段存储管理的逻辑地址结构由段号s和段内位移量d组成，如下图所示。,2段表,类似于分页存储管理的页表，为了实现动态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为：,段表：每进程一个,段首址,段长度,100k,40k,80k,60k,段号,0:1:2:3:,20k,200k,320k,300k,所需寄存器,(1)段表首址寄存器：,b,l,(2)段表长度寄存器：,系统一个,系统一个,(3)快表：系统一组：,段号段首址段长度,.,.,.,.,l,s,.,b,.,地址映射:(s,d)(b+d)逻辑地址(s,d)物理地址(b+d)(1)由程序确定逻辑地址(s,d);(2)由s查快表得b和l如查不到：(a)由s与l比较判断是否越界不满足：0sl-1，越界；(b)由s和b查段表，得b和l(s,b,l)快表,如快表满淘汰一个；(c)转(2)(3)由d与l比较，判断是否越界不满足：0dl-1，越界；(4)由bd得物理地址。,段号,段长段首址,.,.,.,.,lb,s,l,b,b,l,.,.,PCB,段长段首址,段号,.,lb,.,s,.,b+d,+,cp,slb,物理地址,逻辑地址,.,cp,+,b:,4.分段与分页的区别,（1）页是信息的物理单位，分页是为实现离散分配方式，以削减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。而段是信息的逻辑单位，段的内容具有完整的逻辑意义，分段的目的是为了更好的满足用户的需要。（2）页的大小固定且由操作系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统中只能有一种大小的页面；段的长度不固定，决定于用户所写的程序，常由编译器在对原程序进行编译时，根据信息的性质来划分。（3）分页的作业地址空间是一维线性连续的；而分段的作业地址空间是二维的，既需给出段名，又需给出段内地址。（4）分页的活动对用户是透明的；而分段是用户可见的活动。,6.3.4段页式存储管理(segmentationwithpaging),段式优于页式便于共享和保护页式优于段式消除“碎片”问题段页式：结合二者优点每个进程包含若干段每个段包含若干页,段页式存储管理,基本思想：用分段方法来分配和管理虚存，分页方法来分配和管理实存，在段页式管理系统中，每一段不再占有连续的实存空间，而被划分成若干个页面。,基本原理1.内存空间划分：(同页式)静态等长，2i,称为一页。物理地址=(页架号,页内地址)=(f,d)2.进程空间划分：一个进程若干个段一个段若干个页逻辑地址=(段号,逻辑页号,页内地址)=(