操作系统(存储管理,设备管理,文件系统)知识点介绍

第第5 5章章 存储管理存储管理主要内容：连续空间分配，覆盖与交换技术，页式管理，段式管理，段页式存储管理，虚存管理。重点：多道固定划分法，页式管理，请求页式存储管理。难点：覆盖与交换技术，页面替换策略1高速缓存 (cache)主存辅存CPU几百k nM几百M nGnGnTcache主存主存辅存存储层次结构：2研究三方面的问题： 取（fetch） 放（placement） 替换（replacement ）请调、预调连续、不连续35.1 连续空间分配 特点：易理解，访问率高，空间利用率低。5.1.1 单道连续分配 特点：任一时刻内存只有一道作业，该作业连 续存放于内存中。一、管理方法 0内存空间安排操作系统用户程序a a+1n界地址寄存器4界地址寄存器主存Aacputruefalse地址A终止程序运行越界检查机构：用户程序每访问一次主存 ，越界检查机构将访问的地址与界地址寄 存器中的值比较。若越界，则终止其执行 。5二、覆盖（overlay）操作系统固定区(4k)覆盖区0(6k)覆盖区1(10k)A(4k)E(10k)D(6k)C(4k)B(6k)F(8k)引入原因：因内存小于作业的程序空间。 基本思想：将用户空间划分成一个固定区和多个 覆盖区。主程序放固定区，依次调用的子程序则 放在同一个覆盖区。操作系统提供覆盖系统调用 函数，由用户编程时考虑调用。6BCEDF(0,0) (0,1)(1,0) (1,1) (1,2)D(6k )C(4k )A(4k )操作系统4k6k10kE(10k)C(4k )A(4k )操作系统4k6k10kDE覆盖段编号用(i, j)表征i指覆盖段号j覆盖段中的覆盖号E覆盖D7注意：(i) 每次仅放入作业的一个部分(ii) 覆盖结构需由程序员事先确定(iii)可与其内存分配方法结合使用缺点：对用户不透明，增加了用户负担。8引入原因：采用时间片轮转法或可剥夺调 度基本思想：将处于等待状态(等I/O)或就 绪(等CPU)状态的进程从主存换出到辅存 ，把将要执行的进程移入主存。两个概念：换出，换入。三、交换(Swapping)9YN按换入算法在外存查找换入 进程查到吗？ Y调用swapin(p) 函数换入进程换入成功？按换出算法 寻找可换出 进程找到吗？设置runout进程睡眠sleep (4. 如果size(k)-size(v)，则 将k分给用户。5. 否则将k分成k1,k2，其中 size(k1)=size(v)，F = F + k222（2 2）分配策略）分配策略1 1、首次满足、首次满足(First Fit)(First Fit)法：最好且最快法：最好且最快 的算法；的算法； 2 2、最佳满足、最佳满足(Best Fit)(Best Fit)法；法；3 3、最大满足最大满足(Worst Fit)(Worst Fit)法；法；23例子例子：设系统空闲链表为指针7k3k10k8k20k5kabcdef用户先后申请7.5k，4k，最小剩余空间size=0.3，试用3种算法， 求出分配块。24首次满足法: c,a3k3k2.5k8k20k5kabcdef指针7k3k10k8k20k5kabcdef先后申请7.5k，4k25指针7k3k10k8k20k5kabcdefd,f最佳:3k5k7k8k10k20kbfadce0.5k3k5k7k10k20kdbface0.5k1k3k7k10k20kdbface先后申请7.5k，4k2612.5k10k8k7k5k3kecdafb最大: e,e20k10k8k7k5k3kecdafb指针7k3k10k8k20k5kabcdef先后申请7.5k，4k8.5k10k8k7k5k3kecdafb27仅下相邻区 都为空闲区仅上相邻区 都为空闲区查找链表，找到相应 记录进程使用内存的 节点分四种情况回收空间合并上下相邻区 和回收区，即修 改相应参数，删 除相应表项和指 针。回收区与上相邻 区合并，即修改 相应参数。回收区与下相邻 区合并，即修改 相应参数，回收该节点，即修改 有关参数回收结束上下相邻区 都为空闲区直接插入 该回收区两相邻区都 不为空闲区（3 3）回收）回收合并有四种方式。284K内存表作业空间合并6K内存表4K 2K内存表4K 2K6K内存表分配资源释放资源29紧致：通过移动作业位置可以将零散的空闲块连 接成大块。要求作业动态可浮动。Bitmap数组1,1,1,0,0,1,0,0,0,0,1,0,032 1 4 1 2空闲队列头二、可用空间管理 （1）数组，数组项=用户空间总量/基本 分配单位。缺点：没有内部碎片，但有外部碎片（2）链表303种方法的比较：31一、空间安排 用户进程空间(地址)叫逻辑空间(地址); 内存空间(地址)叫物理空间(地址); 用相同长度为单位对逻辑空间等分出的每个区 域叫页， 对物理空间等分出的区域叫页帧， 辅存所划出的每个区域叫块。5.2 不连续空间分配 5.2.1 页式管理 特点：作业(进程)分成页面，内存也划分成页 面，将作业(进程)页面不连续地分布到内存页 面。32分配：初始时，所有页帧都在空闲队列中，当 用户进程被创建时，系统按需要量从空闲队列 获得相应量的页帧。页帧进程页页帧进程页释放分配回收：33二、动态地址转换机构因页式方法中逻辑地址与物理地址之间失去自 然联系，故要通过页表，并由硬件动态地址转 换机构将逻辑地址映射成物理地址才能正确访 存。341 8 5 3 0498765432103210逻辑空间物理空间 页表(一)页表页号页表放在系统空间的页表区，存放逻辑页与物理 页帧的对应关系。PCB表中有指针指向页表。35(二)地址结构逻辑地址 = (p(页号),d(页内位移)物理地址 = (f(页帧号),d(页内位移)p = INT 线性逻辑地址A / 页面大小Ld = 线性逻辑地址A p×页面大小L43210页号36例1、设虚地址为8305，每页为1KB，求页号和 页内地址。解：设线性逻辑地址(虚地址）为AA 8305 L1024页号P = INTA/L=8305/1024=8 页内地址d = A-P*L=8305-8*1024=11337例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, 页号为：1×836×827×8438(三)页面大小的考虑P=LA/页面大小，d=LA-P*页面大小页表始地f逻辑地址 LAf *页面大小+物理 地址 PAØ 一般方法：39Ø 页面大小的选择：将页面大小取成2的k次幂(k是正整数),获取p和d 的除法或乘法只要通过位移实现。页面大小为2的k次幂的地址转换原理如下：一般情况，页面大小为512，1024，2048，4096P d页表始地fn k-10f dn k-10+页表402452页页帧0 122 38页表长 页表始址8452实地址虚地址(页)d (偏移)P(页)9k8644设内存页帧大小为1024字节，即1K。 则物理地址8×10244528644地址转换实例:页表41(四)快表（联想存储器，高速存储体）页面大小为2k的缺点：要查表，两次访问主存，使程序速度下降一半 。 解决办法：快表(快速存储器)快表：一种高速存储体，每一项由两步分组成： 关键字和值；还有一个比较装置。具体方法：当信息到达后，与关键字进行比较， 匹配成功则输出该项值，否则输出一个特殊符号 表示匹配不成功。42转换原理: 将页表存入快表的地址，页号设为关键字， 页帧号为值，其转换原理如下：P dn k-10f dn k-10P2f2P1f1. Pf.Pmfm关键字 值43优点：访问时间短，接近一次访问主存的时间缺点：昂贵；快表匹配成功吗形成物理地址到主存页表中查找形成物理地址yesno解决办法：只放一部分页表项；转换过程为：44地址转换的一般过程： (联想存储器可以看成是页表的cache)P dn k-10f dn k-10P2f2P1f1. Pf . Pmfmf页表始地+页表快表45快表（联想存储器）的地址变换过程页表始址B 页表长度L3>L?+页表寄存器越界中断逻辑地址 V（3，d）页框号页面号物理地址页表26480123是否（8，d）A0A2A1A30页框号1 2 3 4 5 6 7 8 9 偏移d查快表否是读快表 页号联想存储器46实现方法：在进程被调度占用CPU时，将 进程页表始址装入页表始地址寄存器，同 时用新的页表内容替换快表中的原内容。命中率：选用812项组成的快表，并采 用适当的替换策略，在快表中匹配成功的 可能性可达80%90%。等效访问时间：设访存时间为750ns，搜索 快表的时间为50ns，命中率为80%，则：80%×(750+50)+20%×(750+50+750） 950ns4748三、可用空间管理可用数组或空闲页帧链来管理可用页帧，工作如 下：1) 若可用页帧总数小于作业总页数，则拒绝分配2) 取作业的下一页P，分配一可用页帧f，并将p 的内容抄到f中去；3) 将f抄到页P的页表中；4) 若所有页表已处理完，则结束，否则转到2)。四、共享与保护通过页表可以使几个逻辑空间指向同一个物理空 间，实现程序共享。 49举例：EDIT1 EDIT2 EDIT3 DATA1EDIT1 EDIT2 EDIT3 DATA2EDIT1 EDIT2 EDIT3 DATA33 4 6 13 4 6 73 4 6 10OSDATA1EDIT10 1 2 3 4 5 6 7 8 9 10 11EDIT2EDIT3 DATA2DATA3J1 J2J3页表0 1 2 30 1 2 350存储保护： 越界保护：设置页表长度寄存器，查页 表前，先检查页号是否越界。 操作访问保护：在每个页表项中增设 一存储保护域(R,W,E)，用于说明对该页 的访问权限，每一个对该页存储的访问 都首先比照是否满足该页访问权限的说 明，满足则访问，否则报错。51举例：设为每一页表项增加三位，R位表 示读权限，W位表示写权限，E位表示执行 权限。 RWE 000 不可进行任何操作 001 可以执行,不可以读写 010 只可以写 011 100 101 110 11152页式管理优点：内部碎片很少，空间管理简单 ；页式管理缺点：硬件开销大，与用户对空间划 分观点不统一，不利于共享，也不利于保护。53