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

第5章存放管理主要内容：连续空间分配，覆盖与交换技术，页式管理，段式管理，段页式存放管理，虚存管理。重点：多道固定划分法，页式管理，请求页式存放管理。难点：覆盖与交换技术，页面替换策略1第1页高速缓存(cache)主存辅存CPU几百k~nM几百M~nGnG~nTcache—主存主存—辅存存放层次结构：2第2页研究三方面问题：

取（fetch）放（placement）替换（replacement）请调、预调连续、不连续3第3页5.1连续空间分配特点：易了解，访问率高，空间利用率低。5.1.1单道连续分配特点：任一时刻内存只有一道作业，该作业连续存放于内存中。一、管理方法0内存空间安排操作系统用户程序aa+1n界地址存放器4第4页界地址存放器主存A＞acputruefalse地址A终止程序运行越界检验机构：用户程序每访问一次主存，越界检验机构将访问地址与界地址存放器中值比较。若越界，则终止其执行。5第5页二、覆盖（overlay）

操作系统固定区(4k)覆盖区0(6k)覆盖区1(10k)A(4k)E(10k)D(6k)C(4k)B(6k)F(8k)引入原因：因内存小于作业程序空间。基本思想：将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用子程序则放在同一个覆盖区。操作系统提供覆盖系统调用函数，由用户编程时考虑调用。6第6页BCEDF

(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第7页注意：(i)每次仅放入作业一个部分(ii)覆盖结构需由程序员事先确定(iii)可与其内存分配方法结合使用缺点：对用户不透明，增加了用户负担。8第8页引入原因：采取时间片轮转法或可剥夺调度基本思想：将处于等候状态(等I/O)或就绪(等CPU)状态进程从主存换出到辅存，把将要执行进程移入主存。两个概念：换出，换入。三、交换(Swapping)9第9页YN按换入算法在外存查找换入进程查到吗？Y调用swapin(p)函数换入进程换入成功？按换出算法寻找可换出进程找到吗？设置runout进程睡眠sleep(&runin，PSWP)调用xswap函数换出指定进程runin++进程睡眠sleep(&runout，PSWP)NYN函数Sched流程图10第10页交换要花费较长时间：如：辅存采取磁鼓，平均延迟时间为8ms，传输速度为250000B/s，用户空间为20KB，则一次交换活动需要时间最少为：2×(8+103×20KB/250000)=179ms交换时机：在进行I/O活动时不能进行交换，但假如开辟了I/O缓冲区就例外11第11页

覆盖与交换区分:覆盖由用户处理空间不足，要求用户给出程序段之间逻辑覆盖结构。交换由系统处理空间不足。交换发生在进程或作业之间，而覆盖发生在同一进程或作业内，且只能覆盖那些与覆盖段无关程序段。12第12页特点：任一时刻内存可有多道作业，每道作业连续存放于内存。操作系统U1...Un5.1.2多道固定划分区法一、管理方法将用户内存空间分成长度固定若干块。地址重定位：静态重定位，动态重定位用户空间13第13页CPU主存下界存放器上界存放器><TT地址A程序性异常1.上下界存放器和地址检验机构。看成业被调度运行时，作业在内存中上下界地址送上下界存放器，每次内存访问时，地址检验机构作越界检验。作业程序须是绝对地址或静态可浮动。地址访问保护有两种方式：FF14第14页操作系统长度基址位移量或偏移量两个概念：基址存放器长度存放器2.基址存放器、长度存放器和动态地址转换机构。15第15页2.基址存放器、长度存放器和动态地址转换机构。CPU主存基地址存放器长度存放器<+T地址AF 程序性中止16第16页二、作业调度OS4k6k12kOS4k6k12k...7k3k4k5k...3k4k1k2k...5k6k...7k10k11k8k多队列法单队列法17第17页三、存放碎片

存放碎片：未得到利用空间，有两种类型：1)内部碎片：内存某存放区间大于其存放作业空间部分2)外部碎片：内存某存放区间容不下要运行作业时。OS12KB4KB3KB内部碎片OS4KB6KB12KB作业长度：5KB，8KB，12KB外部碎片18第18页4.特点每道程序占一个分区可放多道程序存在零头（即存在内部碎片和外部碎片）缺点：因为存在碎片，降低了主存利用率，而且存在一个大作业找不到适当存放区情况。19第19页一、管理方法5.1.3多道连续可变分区法特点：多道、连续、但不固定划分内存。

系统设置一个张表，用于登记用户区域中未占用空闲块。作业抵达后，即可在空闲块中分配空间。20第20页举例：假设任一时间段内，内存中每一作业取得CPU时间相等。作业到来次序所需存放量运行时间160KB10s2100KB5s330KB20s470KB8s550KB15sOS040256J1J2J3J4J521第21页（1）分配存放空间假设F是空闲块集合;size(k)为块k大小;size(v)为用户所需空间，则分配算法可表示为：1.假如全部属于Fk，都有size(k)<size(v),则失败。2.不然按某一策略选出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+{k2}22第22页（2）分配策略

1、首次满足(FirstFit)法：最好且最快算法；2、最正确满足(BestFit)法；3、最大满足(WorstFit)法；23第23页例子：设系统空闲链表为指针7k3k10k8k20k5kabcdef用户先后申请7.5k，4k，最小剩下空间size=0.3，试用3种算法，求出分配块。24第24页首次满足法:c,a3k3k2.5k8k20k5kabcdef指针7k3k10k8k20k5kabcdef先后申请7.5k，4k25第25页指针7k3k10k8k20k5kabcdefd,f最正确:3k5k7k8k10k20kbfadce0.5k3k5k7k10k20kdbface0.5k1k3k7k10k20kdbface先后申请7.5k，4k26第26页12.5k10k8k7k5k3kecdafb最大:e,e20k10k8k7k5k3kecdafb指针7k3k10k8k20k5kabcdef先后申请7.5k，4k8.5k10k8k7k5k3kecdafb27第27页仅下相邻区都为空闲区仅上相邻区都为空闲区查找链表，找到对应统计进程使用内存节点分四种情况回收空间合并上下相邻区和回收区，即修改对应参数，删除对应表项和指针。回收区与上相邻区合并，即修改对应参数。回收区与下相邻区合并，即修改对应参数，回收该节点，即修改相关参数回收结束上下相邻区都为空闲区直接插入该回收区两相邻区都不为空闲区（3）回收合并有四种方式。28第28页4K内存表作业空间合并6K内存表4K2K内存表4K2K6K内存表分配资源释放资源29第29页紧致：经过移动作业位置能够将零碎空闲块连接成大块。要求作业动态可浮动。Bitmap数组{1,1,1,0,0,1,0,0,0,0,1,0,0}321412空闲队列头二、可用空间管理（1）数组，数组项=用户空间总量/基本分配单位。缺点：没有内部碎片，但有外部碎片（2）链表30第30页3种方法比较：31第31页一、空间安排

用户进程空间(地址)叫逻辑空间(地址);内存空间(地址)叫物理空间(地址);用相同长度为单位对逻辑空间等分出每个区域叫页，对物理空间等分出区域叫页帧，辅存所划出每个区域叫块。5.2不连续空间分配5.2.1页式管理特点：作业(进程)分成页面，内存也划分成页面，将作业(进程)页面不连续地分布到内存页面。32第32页分配：初始时，全部页帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列取得对应量页帧。页帧进程页页帧进程页释放分配回收：33第33页二、动态地址转换机构因页式方法中逻辑地址与物理地址之间失去自然联络，故要经过页表，并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存。34第34页18530498765432103210逻辑空间物理空间页表

(一)页表

页号页表放在系统空间页表区，存放逻辑页与物理页帧对应关系。PCB表中有指针指向页表。35第35页(二)地址结构

逻辑地址=(p(页号),d(页内位移))物理地址=(f(页帧号),d(页内位移))p=INT[线性逻辑地址A/页面大小L]d=线性逻辑地址A–p×页面大小L43210页号36第36页例1、设虚地址为8305，每页为1KB，求页号和页内地址。解：设线性逻辑地址(虚地址）为AA＝8305L＝1024页号P=INT[A/L]=[8305/1024]=8页内地址d=A-P*L=8305-8*1024=11337第37页例2：设虚地址为(357101)8，每页为128，求页号和页内地址。解：128＝27(逻辑地址低7位为页内位移)1 6 7 4 1 0 1偏移为(101)8,页号为(1674)8(357101)8＝(011,101,111,001,000,001)2转成十进制：偏移为：(65)10,页号为：1×83＋6×82＋7×8＋438第38页(三)页面大小考虑P=LA/页面大小，d=LA-P*页面大小页表始地f逻辑地址LAf*页面大小++物理地址PA普通方法：39第39页页面大小选择：将页面大小取成2k次幂(k是正整数),获取p和d除法或乘法只要经过位移实现。页面大小为2k次幂地址转换原理以下：普通情况，页面大小为512，1024，2048，4096Pd页表始地fn

k-1 0fdn

k-1 0+页表40第40页2452页页帧012238

页表长页表始址8452实地址虚地址(页)d(偏移)P(页)9k8644…设内存页帧大小为1024字节，即1K。则物理地址＝8×1024＋452＝8644地址转换实例:页表41第41页(四)快表（联想存放器，高速存放体）页面大小为2k缺点：要查表，两次访问主存，使程序速度下降二分之一。处理方法：快表(快速存放器)快表：一个高速存放体，每一项由两步分组成：关键字和值；还有一个比较装置。详细方法：当信息抵达后，与关键字进行比较，匹配成功则输出该项值，不然输出一个特殊符号表示匹配不成功。42第42页转换原理:将页表存入快表地址，页号设为关键字，页帧号为值，其转换原理以下：Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfm关键字值43第43页优点：访问时间短，靠近一次访问主存时间缺点：昂贵；快表匹配成功吗形成物理地址到主存页表中查找形成物理地址yesno处理方法：只放一部分页表项；转换过程为：44第44页地址转换普通过程：(联想存放器能够看成是页表cache)Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfmf页表始地+页表快表45第45页快表（联想存放器）地址变换过程页表始址B页表长度L3>L?+页表存放器越界中止逻辑地址V＝（3，d）页框号页面号物理地址页表2648…0123…是否（8，d）A0A2A1A30页框号123456789…偏移d查快表否是读快表页号联想存放器46第46页实现方法：在进程被调度占用CPU时，将进程页表始址装入页表始地址存放器，同时用新页表内容替换快表中原内容。命中率：选取8～12项组成快表，并采取适当替换策略，在快表中匹配成功可能性可达80%～90%。等效访问时间：设访存时间为750ns，搜索快表时间为50ns，命中率为80%，则：80%×(750+50)+20%×(750+50+750）＝950ns47第47页48第48页三、可用空间管理可用数组或空闲页帧链来管理可用页帧，工作以下：若可用