os操作系统.pptx

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