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

操作系统(存储管理设备管理文件系统)知识点介绍高速缓存(cache)主存辅存CPU几百k~nM几百M~nGnG~nTcache—主存主存—辅存存储层次结构：2研究三方面的问题：

取（fetch）放（placement）替换（replacement）请调、预调连续、不连续35.1连续空间分配特点：易理解，访问率高，空间利用率低。5.1.1单道连续分配特点：任一时刻内存只有一道作业，该作业连续存放于内存中。一、管理方法0内存空间安排操作系统用户程序aa+1n界地址寄存器4界地址寄存器主存A＞acputruefalse地址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(&runin，PSWP)调用xswap函数换出指定进程runin++进程睡眠sleep(&runout，PSWP)NYN函数Sched流程图10交换要花费较长的时间：如：辅存采用磁鼓，平均延迟时间为8ms，传输速度为250000B/s，用户空间为20KB，则一次交换活动需要时间至少为：2×(8+103×20KB/250000)=179ms交换时机：在进行I/O活动时不能进行交换，但如果开辟了I/O缓冲区就例外11

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

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

系统设置一个张表，用于登记用户区域中未占用的空闲块。作业到达后，即可在空闲块中分配空间。20举例：假设任一时间段内，内存中每一作业获得CPU时间相等。作业到来次序所需存储量运行时间160KB10s2100KB5s330KB20s470KB8s550KB15sOS040256J1J2J3J4J521（1）分配存储空间假设F是空闲块集合;size(k)为块k的大小;size(v)为用户所需空间，则分配算法可表示为：1.如果所有属于F的k，均有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（2）分配策略

1、首次满足(FirstFit)法：最好且最快的算法；2、最佳满足(BestFit)法；3、最大满足(WorstFit)法；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）回收合并有四种方式。284K内存表作业空间合并6K内存表4K2K内存表4K2K6K内存表分配资源释放资源29紧致：通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。Bitmap数组{1,1,1,0,0,1,0,0,0,0,1,0,0}321412空闲队列头二、可用空间管理（1）数组，数组项=用户空间总量/基本分配单位。缺点：没有内部碎片，但有外部碎片（2）链表303种方法的比较：31一、空间安排

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

(一)页表

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

逻辑地址=(p(页号),d(页内位移))物理地址=(f(页帧号),d(页内位移))p=INT[线性逻辑地址A/页面大小L]d=线性逻辑地址A–p×页面大小L43210页号36例1、设虚地址为8305，每页为1KB，求页号和页内地址。解：设线性逻辑地址(虚地址）为AA＝8305L＝1024页号P=INT[A/L]=[8305/1024]=8页内地址d=A-P*L=8305-8*1024=11337例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(三)页面大小的考虑P=LA/页面大小，d=LA-P*页面大小页表始地f逻辑地址LAf*页面大小++物理地址PA一般方法：39页面大小的选择：将页面大小取成2的k次幂(k是正整数),获取p和d的除法或乘法只要通过位移实现。页面大小为2的k次幂的地址转换原理如下：一般情况，页面大小为512，1024，2048，4096Pd页表始地fn

k-1 0fdn

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

k-1 0fdn

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

k-1 0fdn

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