操作系统存储管理设备管理文件系统知识点介绍.pptx

1第第5 5章章 存储管理存储管理主要内容：主要内容：连续空间分配，覆盖与交换技术，页连续空间分配，覆盖与交换技术，页式管理，段式管理，段页式存储管理，虚存管理。式管理，段式管理，段页式存储管理，虚存管理。重点：重点：多道固定划分法，页式管理，请求页式存多道固定划分法，页式管理，请求页式存储管理。储管理。难点：难点：覆盖与交换技术，页面替换策略覆盖与交换技术，页面替换策略2高速缓存高速缓存(cache)主存主存辅存辅存CPU几百几百k nM几百几百M nGnGnTcache主存主存主存主存辅存辅存存储层次结构：存储层次结构：3研究三方面的问题：研究三方面的问题：取（取（fetchfetch）放（放（placementplacement）替换（替换（replacementreplacement）请调、预调请调、预调连续、不连续连续、不连续45.1 5.1 连续空间分配连续空间分配特点：易理解，访问率高，空间利用率低。特点：易理解，访问率高，空间利用率低。5.1.1 5.1.1 单道连续分配单道连续分配特点：特点：任一时刻内存只有一道作业，该作业连任一时刻内存只有一道作业，该作业连续存放于内存中。续存放于内存中。一、管理方法0内存空间安排内存空间安排操作系统操作系统用户程序用户程序aa+1n界地址寄存器界地址寄存器5界地址寄存器界地址寄存器主存主存A Aa acpucputruetruefalsefalse地址地址A A终止程序运行终止程序运行越界检查机构：用户程序每访问一次主存，用户程序每访问一次主存，越界检查机构将访问的地址与界地址寄存越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止其执行。器中的值比较。若越界，则终止其执行。6二、覆盖（二、覆盖（overlayoverlay）操作系统操作系统固定区固定区(4k)(4k)覆盖区覆盖区0(6k)0(6k)覆盖区覆盖区1(10k)1(10k)A(4k)A(4k)E(10k)E(10k)D(6k)D(6k)C(4k)C(4k)B(6k)B(6k)F(8k)F(8k)引入原因：引入原因：因内存小于作业的程序空间。因内存小于作业的程序空间。基本思想：基本思想：将用户空间划分成一个固定区和多个将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用放在同一个覆盖区。操作系统提供覆盖系统调用函数，函数，由用户编程时考虑调用。由用户编程时考虑调用。7BCEDF (0,0)(0,1)(1,0)(1,1)(1,2)D(6k)C(4k)A(4k)操作系统操作系统4k4k6k6k10k10kE(10k)C(4k)A(4k)操作系统操作系统4k4k6k6k10k10kDE覆盖段编号用覆盖段编号用(i,j)表征表征i指覆盖段号指覆盖段号j覆盖段中的覆盖号覆盖段中的覆盖号E E覆盖覆盖D D8 注意：注意：(i)(i)每次仅放入作业的一个部分每次仅放入作业的一个部分(ii)(ii)覆盖结构需由程序员事先确定覆盖结构需由程序员事先确定(iii)(iii)可与其内存分配方法结合使用可与其内存分配方法结合使用 缺点：缺点：对用户不透明，增加了用户负担对用户不透明，增加了用户负担。9引入原因：采用时间片轮转法或可剥夺调采用时间片轮转法或可剥夺调度度基本思想：将处于等待状态将处于等待状态(等等I/O)I/O)或就或就绪绪(等等CPU)CPU)状态的进程从主存换出到辅存，状态的进程从主存换出到辅存，把将要执行的进程移入主存。把将要执行的进程移入主存。两个概念：换出，换入。换出，换入。三、交换(Swapping)10YN按换入算法在外存查找换入按换入算法在外存查找换入进程进程查到吗？查到吗？Y调用调用swapin(p)函数换入进程函数换入进程换入成功？换入成功？按换出算法按换出算法寻找可换出寻找可换出进程进程找到吗？找到吗？设置设置runout进程睡眠进程睡眠sleep(&runin，PSWP)调用调用xswap函函数换出指定进数换出指定进程程runin+进程睡眠进程睡眠sleep(&runout，PSWP)NYN函数函数Sched流流程图程图11交换要花费较长的时间：如：如：辅存采用磁鼓，平均延迟时间为辅存采用磁鼓，平均延迟时间为8ms，传输速度为传输速度为250000B/s，用户空间为，用户空间为20KB，则一次交换活动需要时间至少为：则一次交换活动需要时间至少为：2(8+10320KB/250000)=179ms交换时机：在进行在进行I/O活动时不能进行交换，但如果开辟了活动时不能进行交换，但如果开辟了I/O缓冲区就例外缓冲区就例外12 覆盖与交换的区别覆盖与交换的区别:覆盖由用户解决空间不足，要求用户给出覆盖由用户解决空间不足，要求用户给出程序段之间的逻辑覆盖结构。程序段之间的逻辑覆盖结构。交换由系统解决空间不足。交换由系统解决空间不足。交换发生在进程或作业之间，而覆盖发生在交换发生在进程或作业之间，而覆盖发生在同一进程或作业内，且只能覆盖那些与覆盖同一进程或作业内，且只能覆盖那些与覆盖段无关的程序段。段无关的程序段。13特点：特点：任一时刻内存可有多道作业，每道任一时刻内存可有多道作业，每道作业连续存放于内存。作业连续存放于内存。操作系统操作系统U1U1.U Un n5.1.2 5.1.2 多道固定划分区法多道固定划分区法一、管理方法n 将用户内存空间分将用户内存空间分成长度固定的若干块。成长度固定的若干块。n 地址重定位：静态地址重定位：静态重定位，动态重定位重定位，动态重定位用用户户空空间间14CPUCPU主存主存下界寄存器下界寄存器上界寄存器上界寄存器 T TT T地址地址A A程序性异常程序性异常1.1.上下界寄存器和地址检查机构。上下界寄存器和地址检查机构。当作业被调度运行时，作业在内存中的上下界地当作业被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次内存访问时，地址检查址送上下界寄存器，每次内存访问时，地址检查机构作越界检查。作业程序须是绝对地址或静态机构作越界检查。作业程序须是绝对地址或静态可浮动的。可浮动的。地址访问保护有两种方式：地址访问保护有两种方式：F FF F15操作系统操作系统长长度度基址基址位位移移量量或或偏偏移移量量两个概念：两个概念：n 基址寄存器基址寄存器n 长度寄存器长度寄存器2.基址寄存器、长度寄存器和动态地址转换机构。162.基址寄存器、长度寄存器和动态地址转换机构。CPUCPU主存主存基地址寄存器基地址寄存器长度寄存器长度寄存器+T T地址地址A AF F 程序性中断程序性中断17二、作业调度OS4k6k12kOS4k6k12k.7k3k4k5k.3k4k1k2k.5k6k.7k10k11k8k多多队队列列法法单单队队列列法法18三、存储碎片 存储碎片：存储碎片：未得到利用的空间，有两种类型：未得到利用的空间，有两种类型：1)1)内部碎片：内部碎片：内存某存储区间大于其存放作内存某存储区间大于其存放作 业空间的部分业空间的部分2)2)外部碎片：外部碎片：内存某存储区间容不下要运行内存某存储区间容不下要运行 的作业时。的作业时。OS12KB4KB3KB内部碎片内部碎片OS4KB6KB12KB作业长度：作业长度：5KB，8KB，12KB外部碎片外部碎片194.4.特点特点每道程序占一个分区每道程序占一个分区可放多道程序可放多道程序存在零头（即存在内部碎片和外部碎片）存在零头（即存在内部碎片和外部碎片）缺缺点点：由由于于存存在在碎碎片片，降降低低了了主主存存利利用用率率，并并且且存存在在一一个个大大作作业业找找不不到到合合适适的的存存储储区的情况。区的情况。20 一、管理方法5.1.3 5.1.3 多道连续可变分区法多道连续可变分区法特点：特点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。系统设置一个张表，用于登记用户区域中未占用的空闲块。作业到达后，即可在空闲块中分配空间。21举例：假设任一时间段内，内存中每一作业举例：假设任一时间段内，内存中每一作业获得获得CPUCPU时间相等。时间相等。作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间 1 60KB 10s 2 100KB 5s 3 30KB 20s 4 70KB 8s 5 50KB 15sOS0 40 256J1J2J3J4J522（1）分配存储空间）分配存储空间 假设假设F 是空闲块集合是空闲块集合;size(k)为块为块k的大小的大小;size(v)为用户所需空间，则分配算法可表示为：为用户所需空间，则分配算法可表示为：1.如果所有属于如果所有属于F 的的k，均有，均有size(k)size(v)3.F=F k;4.如果如果size(k)-size(v)，则，则将将k分给用户。分给用户。5.否则将否则将k分成分成k1,k2，其中，其中 size(k1)=size(v)，F=F+k223（2）分配策略）分配策略 1、首次满足、首次满足(First Fit)法：最好且最快法：最好且最快的算法；的算法；2、最佳满足、最佳满足(Best Fit)法；法；3、最大满足、最大满足(Worst Fit)法；法；24例子例子：设系统设系统空闲空闲链表为链表为指针指针7k3k10k8k20k5kabcdef用户先后申请用户先后申请7.5k，4k，最小剩余空间，最小剩余空间size=0.3，试用试用3种算法，种算法，求出分配块求出分配块。25首次首次满足法满足法:c,a3k3k2.5k8k20k5kabcdef指针指针7k3k10k8k20k5kabcdef先后申请先后申请7.5k，4k26指针指针7k3k10k8k20k5kabcdefd,f最佳最佳:3k5k7k8k10k20kbfadce0.5k3k5k7k10k20kdbface0.5k1k3k7k10k20kdbface先后申请先后申请7.5k，4k2712.5k10k8k7k5k3kecdafb最大最大:e,e20k10k8k7k5k3kecdafb指针指针7k3k10k8k20k5kabcdef先后申请先后申请7.5k，4k8.5k10k8k7k5k3kecdafb28仅仅下下相相邻邻区区都为空闲区都为空闲区仅仅上上相相邻邻区区都为空闲区都为空闲区查查找找链链表表，找找到到相相应应记记录录进进程程使使用用内内存存的的节点节点分四种情况回收空间分四种情况回收空间合合并并上上下下相相邻邻区区和和回回收收区区，即即修修改改相相应应参参数数，删删除除相相应应表表项项和和指指针。针。回回收收区区与与上上相相邻邻区区合合并并，即即修修改改相应参数。相应参数。回回收收区区与与下下相相邻邻区区合合并并，即即修修改改相应参数，相应参数，回回收收该该节节点点，即即修修改改有关参数有关参数回收结束回收结束上上下下相相邻邻区区都为空闲区都为空闲区直直接接插插入入该回收区该回收区两两相相邻邻区区都都不为空闲区不为空闲区（3）回收）回收 合并有四种方式。合并有四种方式。294K内存表内存表作业空间作业空间合并合并6K内存表内存表 4K 2K内存表内存表 4K 2K6K内存表内存表分配资源分配资源释放资源释放资源30紧致：通过移动作业位置可以将零散的空闲块连通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。接成大块。要求作业动态可浮动。Bitmap数组1,1,1,0,0,1,0,0,0,0,1,0,03 21412空闲队列头二、可用空间管理（1 1）数组，数组项）数组，数组项=用户空间总量用户空间总量/基本基本分配单位。分配单位。缺点：缺点：没有内部碎片，但有外部碎片没有内部碎片，但有外部碎片（2 2）链表）链表313种方法的比较：种方法的比较：32一、空间安排 用户进程空间用户进程空间(地址地址)叫叫逻辑空间逻辑空间(地址地址););内存空间内存空间(地址地址)叫叫物理空间物理空间(地址地址););用相同长度为单位对逻辑空间等分出的每个区用相同长度为单位对逻辑空间等分出的每个区 域叫域叫页页，对物理空间等分出的区域叫对物理空间等分出的区域叫页帧页帧，辅存所划出的每个区域叫辅存所划出的每个区域叫块块。5.2 5.2 不连续空间分配不连续空间分配5.2.1 5.2.1 页式管理页式管理特点：作业作业(进程进程)分成页面，内存也划分成页分成页面，内存也划分成页面，将作业面，将作业(进程进程)页面不连续地分布到内存页页面不连续地分布到内存页面。面。33分配：分配：初始时，所有页帧都在空闲队列中，当初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。获得相应量的页帧。页帧页帧进程页进程页页帧页帧进程页进程页释放释放分配分配回收：回收：34 二、动态地址转换机构因因页页式式方方法法中中逻逻辑辑地地址址与与物物理理地地址址之之间间失失去去自自然然联联系系，故故要要通通过过页页表表，并并由由硬硬件件动动态态地地址址转转换换机机构构将将逻逻辑辑地地址址映映射射成成物物理理地地址址才才能能正正确确访访存。存。3518530498765432103210逻辑空间逻辑空间物理空间物理空间页表页表 (一)页表 页页号号页表放在系统空间的页表区，存放逻辑页与物理页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。页帧的对应关系。PCBPCB表中有指针指向页表。表中有指针指向页表。36(二)地址结构 逻辑地址逻辑地址 =(p(=(p(页号页号),d(d(页内位移页内位移)物理地址物理地址 =(f(=(f(页帧号页帧号),d(d(页内位移页内位移)p=p=INT INT 线性逻辑地址线性逻辑地址A A/页面大小页面大小L L d=d=线性逻辑地址线性逻辑地址A A p p页面大小页面大小L L43210页页号号37例例1 1、设设虚虚地地址址为为83058305，每每页页为为1KB1KB，求求页页号号和和页内地址。页内地址。解：设解：设线性逻辑地址线性逻辑地址(虚地址）为虚地址）为AA A 83058305L L10241024页号页号P=INTA/L=8305/1024=8P=INTA/L=8305/1024=8页内地址页内地址d=A-P*L=8305-8*1024=113d=A-P*L=8305-8*1024=11338例例2 2：设虚地址为设虚地址为(357101)(357101)8 8 ，每页为，每页为128128，求页号，求页号和页内地址。和页内地址。解：解：1281282 27 7 (逻辑地址的低逻辑地址的低7 7位为页内位移位为页内位移)1 6 74101偏移为偏移为(101)(101)8 8,页号为页号为(1674)(1674)8 8(357101)8(011,101,111,00 1,000,001)2 转成十进制：偏移为：转成十进制：偏移为：(65)(65)1010,页号为：页号为：18183 368682 278784 439 (三)页面大小的考虑P=LA/页面大小，页面大小，d=LA-P*页面大小页面大小页表始地f逻辑地址逻辑地址 LALAf*页面大小页面大小+物理物理地址地址PA 一般方法：一般方法：40 页面大小的选择：页面大小的选择：将页面大小取成将页面大小取成2的的k次幂次幂(k是正整数是正整数),获取获取p和和d的除法或乘法只要通过位移实现。的除法或乘法只要通过位移实现。页面大小为页面大小为2的的k次幂的地址转换原理如下：次幂的地址转换原理如下：一般情况，页面大小为一般情况，页面大小为512，1024，2048，4096P d页表始地fn k-10f dn k-10+页表412 2452452页页页帧页帧0 01 12 22 23 38 8 页表长页表长 页表始址页表始址8 8452452实地址实地址虚地址虚地址(页页)d(d(偏移偏移)P(P(页页)9k9k86448644设内存页帧大小为设内存页帧大小为10241024字节，即字节，即1K1K。则物理地址则物理地址810248102445245286448644地址转换实例地址转换实例:页表页表42 (四)快表（联想存储器，高速存储体）页面大小为页面大小为2k2k的缺点：的缺点：要查表，两次访问主存，使程序速度下降一半。要查表，两次访问主存，使程序速度下降一半。解决办法：解决办法：快表快表(快速存储器快速存储器)快表：快表：一种高速存储体，每一项由两步分组成：一种高速存储体，每一项由两步分组成：关键字和值；还有一个比较装置。关键字和值；还有一个比较装置。具体方法：具体方法：当信息到达后，与关键字进行比较，当信息到达后，与关键字进行比较，匹配成功则输出该项值，否则输出一个特殊符号匹配成功则输出该项值，否则输出一个特殊符号表示匹配不成功。表示匹配不成功。43转换原理转换原理:将页表存入快表的地址，将页表存入快表的地址，页号页号设为关键字，设为关键字，页帧号页帧号为值，其转换原理如下：为值，其转换原理如下：P dn k-10f dn k-10P2f2P1f1.Pf.Pmfm关键字关键字 值值44优点：优点：访问时间短，接近一次访问主存的时间访问时间短，接近一次访问主存的时间缺点：缺点：昂贵；昂贵；快表匹配快表匹配成功吗成功吗形成物理地址形成物理地址到主存页表中查找形成物理地址到主存页表中查找形成物理地址yesno解决办法：解决办法：只放一部分页表项；只放一部分页表项；转换过程为：转换过程为：45地址转换的一般过程：地址转换的一般过程：(联想存储器可以看成是页表的联想存储器可以看成是页表的cache)cache)P dn k-10f dn k-10P2f2P1f1.Pf.Pmfmf页表始地+页表快表46快表（联想存储器）的地址变换过程快表（联想存储器）的地址变换过程页表始址页表始址B 页表长度页表长度L3L?3L?+页表寄存器页表寄存器越界中断越界中断逻辑地址逻辑地址V（3，d）页框号页框号页面号页面号物理地址物理地址页表页表26480123是是否否（8，d）A0A2A1A30页框号页框号123456789偏移偏移d查快表查快表否否是是读快表读快表页号页号联想存储器联想存储器47实现方法：实现方法：在进程被调度占用在进程被调度占用CPUCPU时，将时，将进程页表始址装入页表始地址寄存器，同进程页表始址装入页表始地址寄存器，同时用新的页表内容替换快表中的原内容。时用新的页表内容替换快表中的原内容。命中率：命中率：选用选用8 81212项组成的快表，并采项组成的快表，并采用适当的替换策略，在快表中匹配成功的用适当的替换策略，在快表中匹配成功的可能性可达可能性可达80%80%90%90%。等效访问时间：等效访问时间：设访存时间为设访存时间为750ns750ns，搜索，搜索快表的时间为快表的时间为50ns50ns，命中率为，命中率为80%80%，则：，则：80%(750+50)+20%(750+50+75080%(750+50)+20%(750+50+750）950ns950ns4849三、可用空间管理可用数组或空闲页帧链来管理可用页帧，工作如可用数组或空闲页帧链来管理可用页帧，工作如下：下：1)1)若可用页帧总数小于作业总页数，则拒绝分配若可用页帧总数小于作业总页数，则拒绝分配2)2)取作业的下一页取作业的下一页P P，分配一可用页帧，分配一可用页帧f f，并将，并将p p的内容抄到的内容抄到f f中去；中去；3)3)将将f f抄到页抄到页P P的页表中；的页表中；4)4)若所有若所有页表已处理完，则结束，否则转到页表已处理完，则结束，否则转到2)。四、共享与保护通过页表可以使几个逻辑空间指向同一个物理空通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。间，实现程序共享。50 举例举例：EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA33461346734610OSDATA1EDIT10 1 2 3 4 5 6 7 8 9 10 11EDIT2EDIT3 DATA2DATA3J1 J2J3页表0123012351存储保护：越界保护：越界保护：设置页表长度寄存器，查页设置页表长度寄存器，查页表前，先检查页号是否越界。表前，先检查页号是否越界。操作访问保护：操作访问保护：在每个页表项中增设在每个页表项中增设一存储保护域一存储保护域(R,W,E)(R,W,E)，用于说明对该页，用于说明对该页的访问权限，每一个对该页存储的访问的访问权限，每一个对该页存储的访问都首先比照是否满足该页访问权限的说都首先比照是否满足该页访问权限的说明，满足则访问，否则报错。明，满足则访问，否则报错。52举例：设为每一页表项增加三位，设为每一页表项增加三位，R R位表位表示读权限，示读权限，W W位表示写权限，位表示写权限，E E位表示执行位表示执行权限。权限。R RW WE E0 00 00 0 不可进行任何操作不可进行任何操作0 00 01 1 可以执行可以执行,不可以读写不可以读写0 01 10 0 只可以写只可以写0 01 11 11 10 00 01 10 01 11 11 10 01 11 11 153页式管理优点：页式管理优点：内部碎片很少，空间管理简单；内部碎片很少，空间管理简单；页式管理缺点：页式管理缺点：硬件开销大，与用户对空间划硬件开销大，与用户对空间划分观点不统一，不利于共享，也不利于保护。分观点不统一，不利于共享，也不利于保护。