《操作系统课件第六章存储管理》由会员分享，可在线阅读，更多相关《操作系统课件第六章存储管理（48页珍藏版）》请在金锄头文库上搜索。
1、6.1 存储管理功能,存储分配和去配 分配去配对象 内存、外存(相同方法) 分配去配时刻 进程创建、撤销、交换、长度变化 记录内存资源和外存资源的使用情况 存储共享 目的：节省内存、相互通讯 内容：代码、数据 纯代码（(pure code), 以保证“可再入”, 即它在运行过程中不修改自身. 存储保护 防止地址越界 防止操作越权,6.1 存储管理功能(Cont.),存储扩充 内存、外存结合，虚拟存储体系 速度接近内存，容量相当外存 地址映射 逻辑地址=物理地址 硬件支持 基址寄存器(base)、限长寄存器(limit)、快表； 使用上述寄存器完成地址映射过程； 不能正常完成地址映射时产生中断；
2、 需软硬件相结合来完成。,6.2 内存资源管理,6.2.1 内存分区 分区时刻 静态分区：系统初始化时分； 动态分区：申请时分。 分区大小 等长分区：2i 异长分区：依程序、程序单位、对象大小。 通常作法 静态+等长（页式、段页式） 动态+异长（段式、界地址）,6.2.2 内存分配,静态等长分区的分配 字位映象图（bit map） 空闲页面表 空闲页面链,字位映象图（bit map）,第0 页,第2 页,第1 页,第 k 页,第 n 页,.,.,分配：自头寻找第一个为0的位，改为1，返回页号； 去配：页号对应的位(bit)置为0。,用一个bit代表一页状态，0表空闲，1表占用。（ 多单元）,空
3、闲页面表,特点：可以分配连续页面。,占用,占用,120页,121页,122页,123页,.,.,空闲页面链,占用,占用,占用,Head:,优点：节省空间。 （不适合管理外存）,动态异长分区的分配,数据结构：,Criteria: 尽量使空闲区域连续。,初始时一个连续空闲区。 长度=0为表尾。,最先适应算法（First Fit）,空闲区：首址递增排列； 申请：取第一个可满足区域； 优点：尽量使用低地址空间， 高区保持大空闲区域。 缺点：可能分割大空闲区。 Eg. 申请32将分割第 一个区域。,最佳适应算法（Best Fit）,空闲区：递增排列； 申请：取最小可满足区域； 优点：尽量使用小空闲区，
4、保持大空闲区。 缺点：可能形成碎片 (fragment)。 Eg. 申请30将留下长 度为2的空闲区。,最坏适应算法（Worst Fit）,空闲区：长度递减排列； 申请：取最大可满足区域； 优点：防止形成碎片。 缺点：分割大空闲区域。,空闲区首址,空闲区长度,128,64,1024,256,32,256,0,.,.,6.2.3 碎片处理,动态异长分区存储分配可能形成很小的空闲区域，称为碎片(fragment) 紧凑：移动占用区域，使所有空闲区域连成一片（开销很大）。,OS,P1(248k),P2(250k),8k,6k,4k,256k:,512k:,768k:,264k:,518k:,256k
5、:,504k:,754k:,18k,6.3 存储管理方式,界地址管理方式（一维地址） 页式管理方式（一维地址） 段式管理方式（二维地址） 段页式管理方式（二维地址）,6.3.1 界地址管理方式,4.3.1.1 基本原理 一个进程在内存空间的地址由两个参数确定：起始地址和长度，称作一个对界. 1. 内存空间划分：动态异长； 2. 进程空间划分：一个进程一个区域，逻辑地址0l-1 3. 进程空间与内存空间对应关系：可以浮动,0:,l-1:,.,.,b:,l,b+l-1:,进程空间,内存空间,6.3.1 界地址管理方式,4. 所需表目： (1)内存分配表-在PCB中； (2)空闲区域表：用于记录内存
6、中所有尚未分配的区域 。 5. 所需寄存器： (1)基址寄存器； (2)限长寄存器。 6. 地址映射：,6.3.1 界地址管理方式,6. 地址映射： 地址映射需要将程序所产生的逻辑地址变换为内存中的物理地址,即完成如下映射： ：（a）（b+a） 其中a为逻辑地址，b为进程起始地址. 当a所对应的物理地址不存在时(越界)，映射没有意义，结果为.,6.3.1 界地址管理方式,0:,l-1:,.,.,b:,l,b+l-1:,l,b,逻辑地址,CP,+,a,a+b,步骤：(1) 由程序确定逻辑地址a； (2) a与l比较判断是否越界， 不满足：0al-1，越界； (3) a与b相加得到物理地址。,进程
7、空间,内存空间,6.3.1 界地址管理方式,6.3.1.2 双对界 代码：一对界 数据：一对界,6.3.1 界地址管理方式,6.3.1.3 交换技术(swapping) 交换(swapping) ：是指进程在内存空间与外存空间之间的动态调度，它是缓解内存空间紧张矛盾的一种有效方法. 当外存中有可运行进程时，系统试图将其调入内存；当内存空间紧张时，系统将内存中某些进程， 尤其是暂时不可运行的进程(如处于WAIT状态的进程)移到外存. 采用交换技术，一个进程可在内外存之间交换，但由于交换的基本单位是整个进程，因而仍然不能运行比内存大的程序.,覆盖技术,覆盖(overlay)是将较大程序装入较小进程
8、空间一种的技术其思想是只将全局代码和数据静态地放在内存，其它部分则分阶段地动态装入。 例如，一个包括四遍扫描的编译程序 ：,6.3.2 分页式存储管理(paging),6.3.2.1 基本原理 1. 内存空间划分：静态等长，2i, 称为一个页架(page frame)。,.,.,第0页,第1页,第k页,第2n-i-1页,2i,02i:,12i:,k2i:,(2n-i-1)2i:,物理地址=页架首址+页内地址 =页架号 2i +页内地址 =,i位,n-i位,6.3.2 分页式存储管理,2. 进程空间划分：静态等长，2i, 称为一个页面。,.,.,第0页,第1页,第k页,第l-1页,2i,02i:
9、,12i:,k2i:,(l-1)2i:,逻辑地址=逻辑页首址+页内地址 =逻辑页号 2i +页内地址 =,i位,3. 进程空间与内存空间对应关系,.,第0页,第1页,第2页,第3页,第16页,第22页,第32页,第15页,.,.,.,进程空间,内存空间,4. 所需表目：,(1)页表，每个进程一个,物理页号,逻辑页号:,15,22,16,32,0,1,2,3,5. 所需寄存器,(2)总页表：系统一个,(1) 页表首址寄存器：,b,l,(2) 页表长度寄存器：,系统一个,系统一个,(3) 快表：系统一组,逻辑页号,页架号,.,.,.,.,f,p,逻辑地址(p,d)物理地址(f,d) (1) 由程序
10、确定逻辑地址(p,d)； (2) 由p查快表得页架号f； 如查不到： (a) 由p与l比较，判别是否越界： 不满足：0pl-1，越界； (b) 由p和b查页表得f, (p,f)快表，如满淘汰一个； /(c) 转(2) (3) f与d合并得物理地址,6. 地址映射 : (p,d)(f,d),表6-1快表长度与页命中率的关系,假定快表的命中率为98%，快表的访问时间为20(ns)，内存的 一次访问时间为100(ns)，则内存 有效访问时间(effective access time)为： EAT 98%(20+100)+2%(20+200) 122(ns),.,逻辑页号,页架号,.,.,.,.,f
11、,p,l,b,b,l,.,.,PCB,页架号,逻辑页号,.,f,.,p,.,f d,+,cp,p f,物理地址,逻辑地址,b:,.,6.3.2.2 多级页表,提出背景 进程虚拟空间大幅度增加 单级页表需要很大连续内存空间 多线程设计导致进程虚拟空间不连续性 页表所占内存空间浪费 例如 32位进程地址空间，页长4k（占12位），页号20位，页表需要220个入口！ 解决策略 二级或多级页表,例如对于四级页表，假定快表的命中率仍为98%，快表与 内存的访问时间仍分别为20(ns)和100(ns)，有效访问时间为： EAT 98%(20+100)+2%(20+500) 128(ns),二级页表,6.3
12、.2.3 反置页表(inverted page table),传统页表面向进程空间 每个进程逻辑页面有一表项 当进程空间很大时，页表很大 反置页表面向内存空间 每个内存页架一个表项 大小固定,反置页表-工作原理,程序,物理 内存,f d,pid p d,f,逻辑地址,物理地址,反置页表,速度问题,反置页表查找 由表头起始，平均为表长度的一半 速度慢 解决方案 在反置页表前增加一级杂凑表 查找杂凑表与反置页表需要两次访问内存 为进一步提高速度，快表缓冲,1. 内存空间划分：动态异长，每区一段。,段首址+段内地址,物理地址=,b：,l,b+d,6.3.3 分段式存储管理(segmentation)
13、,2. 进程空间划分：若干段，每段一个程序单位。,调用x段e,f: 访问d段a,e: 调用y段f,main(段号0),X(段号1),Y(段号2),D(段号3),a:,0 80k-1,0 . 40k-1,0 20k-1,0 60k-1,逻辑地址=,段号 段内地址,(二维地址),main,x,y,d,3. 对应关系,40k,60k,80k,20k,.,.,.,.,进程空间,内存空间,100k:,200k:,300k:,320k:,4. 所需表目,(1) 段表：每进程一个,段首址,段长度,100k,40k,80k,60k,段号,0: 1: 2: 3:,20k,200k,320k,300k,(2) 空
14、闲表：系统一个 array of (addr, size),5. 所需寄存器,(1) 段表首址寄存器：,b,l,(2) 段表长度寄存器：,系统一个,系统一个,(3) 快表：系统一组：,段号 段首址 段长度,.,.,.,.,l,s,.,b,.,6. 地址映射 : (s,d)(b+d) 逻辑地址(s,d)物理地址(b+d) (1) 由程序确定逻辑地址(s,d); (2) 由s查快表得b和l 如查不到： (a) 由s与l比较判断是否越界 不满足：0sl-1，越界； (b)由s和b查段表，得b和l (s,b,l)快表, 如快表满淘汰一个； /(c) 转(2) (3) 由d与l比较，判断是否越界 不满足：0dl-1，越界； (4) 由bd得物理地址。,段号,段长 段首址,., ., .,.,l b,s,l,b,b,l,.,.,PCB,段长 段首址,段号, .,l b,.,s,.,b+d,+,cp,s l b,物理地址,逻辑地址, .,cp,+,b:,6.3.3.2 段的共享,段长 段首址, .,b l,. .,段号 si .,P1段表：,段长 段首址, .,b l,. .,段号 sj .,P2段表：,共享段,.,.,b:,l,内存空间,段名 共享记数 段长 段首址 其它, .,vi 3 35k 125k ?,
