《操作系统存储管理设备管理文件系统知识点介绍培训资料》由会员分享，可在线阅读，更多相关《操作系统存储管理设备管理文件系统知识点介绍培训资料（53页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 存储管理,主要内容：连续空间分配，覆盖与交换技术，页式管理，段式管理，段页式存储管理，虚存管理。 重点：多道固定划分法，页式管理，请求页式存储管理。 难点：覆盖与交换技术，页面替换策略,2,存储层次结构：,3,研究三方面的问题： 取（fetch） 放（placement） 替换（replacement）,5,界地址寄存器,主存,Aa,cpu,true,false,地址A,终止程序运行,越界检查机构：用户程序每访问一次主存，越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止其执行。,6,二、覆盖（overlay）,操作系统,固定区(4k),覆盖区0(6k),覆盖区1(1
2、0k),A(4k),E(10k),D(6k),C(4k),B(6k),F(8k),引入原因：因内存小于作业的程序空间。 基本思想：将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用函数，由用户编程时考虑调用。,7,B,C,E,D,F,(0,0) (0,1),(1,0) (1,1) (1,2),E(10k),C(4k),A(4k),操作系统,4k 6k 10k,D E,覆盖段编号用(i, j)表征 i指覆盖段号 j覆盖段中的覆盖号,E覆盖D,8,注意：,(i) 每次仅放入作业的一个部分,(ii) 覆盖结构需由程序员事先确定,(ii
3、i)可与其内存分配方法结合使用,缺点：,对用户不透明，增加了用户负担。,9,引入原因：采用时间片轮转法或可剥夺调度 基本思想：将处于等待状态(等I/O)或就绪(等CPU)状态的进程从主存换出到辅存，把将要执行的进程移入主存。 两个概念：换出，换入。,三、交换(Swapping),10,函数Sched流程图,11,交换要花费较长的时间： 如： 辅存采用磁鼓，平均延迟时间为8ms， 传输速度为250000B/s，用户空间为20KB， 则一次交换活动需要时间至少为： 2(8+10320KB/250000)=179ms 交换时机： 在进行I/O活动时不能进行交换，但如果开辟了I/O缓冲区就例外,12,
4、覆盖与交换的区别:,覆盖由用户解决空间不足，要求用户给出程序段之间的逻辑覆盖结构。,交换由系统解决空间不足。,交换发生在进程或作业之间，而覆盖发生在同一进程或作业内，且只能覆盖那些与覆盖段无关的程序段。,13,特点：任一时刻内存可有多道作业，每道作业连续存放于内存。,操作系统,U1,.,Un,5.1.2 多道固定划分区法,一、管理方法,将用户内存空间分成长度固定的若干块。 地址重定位：静态重定位，动态重定位,用户空间,14,CPU,主存,下界寄存器,上界寄存器,T,T,地址A,程序性异常,1.上下界寄存器和地址检查机构。 当作业被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次内存访问
5、时，地址检查机构作越界检查。作业程序须是绝对地址或静态可浮动的。,地址访问保护有两种方式：,F,F,15,操作系统,长度,基址,位移量或偏移量,两个概念：,基址寄存器 长度寄存器,2.基址寄存器、长度寄存器和动态地址转换机构。,16,2.基址寄存器、长度寄存器和动态地址转换机构。,CPU,主存,基地址寄存器,长度寄存器,+,T,地址A,F,程序性中断,17,二、作业调度,OS,4k,6k,12k,OS,4k,6k,12k,.,7k,3k,4k,5k,.,3k,4k,1k,2k,.,5k,6k,.,7k,10k,11k,8k,多队列法,单队列法,18,三、存储碎片 存储碎片：未得到利用的空间，有
6、两种类型： 1)内部碎片：内存某存储区间大于其存放作 业空间的部分 2)外部碎片：内存某存储区间容不下要运行 的作业时。,OS,12KB,4KB,3KB,内部碎片,OS,4KB,6KB,12KB,作业长度：5KB，8KB，12KB,外部碎片,19,4. 特点,每道程序占一个分区,可放多道程序,存在零头（即存在内部碎片和外部碎片）,缺点：由于存在碎片，降低了主存利用率，并且存在一个大作业找不到合适的存储区的情况。,20,一、管理方法,5.1.3 多道连续可变分区法,特点：多道、连续、但不固定划分内存。,系统设置一个张表，用于登记用户区域中未占用的空闲块。作业到达后，即可在空闲块中分配空间。,21
7、,举例：假设任一时间段内，内存中每一作业获得CPU时间相等。,作业到来次序 所需存储量 运行时间,1 60KB 10s,2 100KB 5s,3 30KB 20s,4 70KB 8s,5 50KB 15s,OS,0 40 256,J1,J2,J3,J4,J5,22,（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)=siz
8、e(v)，F = F + k2,23,（2）分配策略 1、首次满足(First Fit)法：最好且最快的算法； 2、最佳满足(Best Fit)法； 3、最大满足(Worst Fit)法；,24,例子：设系统空闲链表为,用户先后申请7.5k，4k，最小剩余空间size=0.3，试用3种算法，求出分配块。,25,首次满足法: c,a,3k,3k,2.5k,8k,20k,5k,a,b,c,d,e,f,先后申请7.5k，4k,26,d,f,最佳:,b,f,a,d,c,e,先后申请7.5k，4k,27,先后申请7.5k，4k,28,仅下相邻区都为空闲区,仅上相邻区都为空闲区,查找链表，找到相应记录进程
9、使用内存的节点,分四种情况回收空间,合并上下相邻区和回收区，即修改相应参数，删除相应表项和指针。,回收区与上相邻区合并，即修改相应参数。,回收区与下相邻区合并，即修改相应参数，,回收该节点，即修改有关参数,回收结束,上下相邻区都为空闲区,直接插入该回收区,两相邻区都不为空闲区,（3）回收 合并有四种方式。,29,4K,内存表,作业空间,合并,内存表,2K,内存表,分配资源,释放资源,30,紧致：通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。,Bitmap数组 1,1,1,0,0,1,0,0,0,0,1,0,0,3,2,1,4,1 2,空闲队列头,二、可用空间管理 （1）数组
10、，数组项=用户空间总量/基本分配单位。,缺点：没有内部碎片，但有外部碎片,（2）链表,31,3种方法的比较：,32,一、空间安排 用户进程空间(地址)叫逻辑空间(地址); 内存空间(地址)叫物理空间(地址); 用相同长度为单位对逻辑空间等分出的每个区 域叫页， 对物理空间等分出的区域叫页帧， 辅存所划出的每个区域叫块。,5.2 不连续空间分配 5.2.1 页式管理,特点：作业(进程)分成页面，内存也划分成页面，将作业(进程)页面不连续地分布到内存页面。,33,分配：初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。,页帧,进程页,回收：,34,二、动态
11、地址转换机构 因页式方法中逻辑地址与物理地址之间失去自然联系，故要通过页表，并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存。,35,1,8,5,3,0,4,9,8,7,6,5,4,3,2,1,0,3,2,1,0,逻辑空间,物理空间,页表,(一)页表,页号,页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。PCB表中有指针指向页表。,36,(二)地址结构 逻辑地址 = (p(页号),d(页内位移) 物理地址 = (f(页帧号),d(页内位移) p = INT 线性逻辑地址A / 页面大小L d = 线性逻辑地址A p页面大小L,4,3,2,1,0,页号,37,例1、设虚地址
12、为8305，每页为1KB，求页号和页内地址。,解：设线性逻辑地址(虚地址）为A A 8305 L1024,页号P = INTA/L=8305/1024=8 页内地址d = A-P*L=8305-8*1024=113,38,例2：设虚地址为(357101)8 ，每页为128，求页号和页内地址。,解： 12827 (逻辑地址的低7位为页内位移),1 6 74101,偏移为(101)8, 页号为(1674)8,(357101)8(011, 101, 111, 00 1, 000, 001)2,转成十进制：偏移为：(65)10, 页号为：183682784,39,(三)页面大小的考虑,一般方法：,40
13、,页面大小的选择： 将页面大小取成2的k次幂(k是正整数),获取p和d的除法或乘法只要通过位移实现。 页面大小为2的k次幂的地址转换原理如下：,一般情况，页面大小为512，1024，2048，4096,41,2,452,页,页帧,0,1,2,2,3,8,页表长,页表始址,8,452,实地址,虚地址(页),d (偏移),P(页),9k,8644,设内存页帧大小为1024字节，即1K。则物理地址810244528644,地址转换实例:,页表,42,(四)快表（联想存储器，高速存储体） 页面大小为2k的缺点： 要查表，两次访问主存，使程序速度下降一半。 解决办法：快表(快速存储器) 快表：一种高速存
14、储体，每一项由两步分组成：关键字和值；还有一个比较装置。 具体方法：当信息到达后，与关键字进行比较，匹配成功则输出该项值，否则输出一个特殊符号表示匹配不成功。,43,转换原理: 将页表存入快表的地址，页号设为关键字，页帧号为值，其转换原理如下：,44,优点：访问时间短，接近一次访问主存的时间 缺点：昂贵；,快表匹配,成功吗,形成物理地址,到主存页表中查找形成物理地址,yes,no,解决办法：只放一部分页表项； 转换过程为：,45,地址转换的一般过程： (联想存储器可以看成是页表的cache),P d,n k-10,f d,n k-10,P2,f2,P1,f1,.,.,P,f,.,.,Pm,fm
15、,f,页表始地,+,页表,快表,46,快表（联想存储器）的地址变换过程,47,实现方法：在进程被调度占用CPU时，将进程页表始址装入页表始地址寄存器，同时用新的页表内容替换快表中的原内容。,命中率：选用812项组成的快表，并采用适当的替换策略，在快表中匹配成功的可能性可达80%90%。,等效访问时间：设访存时间为750ns，搜索快表的时间为50ns，命中率为80%，则： 80%(750+50)+20%(750+50+750） 950ns,48,49,三、可用空间管理 可用数组或空闲页帧链来管理可用页帧，工作如下： 若可用页帧总数小于作业总页数，则拒绝分配 取作业的下一页P，分配一可用页帧f，并将p的内容抄到f中去； 将f抄到页P的页表中； 若所有页表已处理完，则结束，否则转到2)。 四、共享与保护 通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。,50,举例：,EDIT1,EDIT2,EDIT3,DATA1,EDIT1,EDIT2,EDIT3,DATA2,EDIT1,EDIT2,EDIT3,DATA3,3,4,6,1,3,4,6,7,3,4,6,10,OS,D
