[工学]06第六章-存储管理.ppt

1、第六章 存储管理,6.1 存储管理功能 6.2 内存资源管理 6.3 存储管理方式 6.4 外存空间管理 6.5 虚拟存储系统,6.1 存储管理功能,内存/外存的管理; 内/外存管理采用相同 或相似的管理技术； 功 能 存储分配 存储共享 存储保护 存储扩充 地址映射,6.1 存储管理功能(Cont.),存储分配/去配 记录内/外存资源的使用情况: 分配表、空闲表 ; 分配/去配对象 内存、外存(相同方法) ; 分配/去配时刻 进程创建、撤销、交换、长度变化(栈溢出, execl) 存储共享 多个进程共用内存的相同区域 ; (物理空间有相交的部分) 目的：节省内存、相互通讯 ; 内容：代码、数

2、据。,存储保护 防止地址越界 ; 防止操作越权。 存储扩充 内存、外存结合，虚拟存储体系 ; 速度接近内存，容量相当外存。 地址映射 逻辑地址=物理地址 硬件支持 基址寄存器(base)、限长寄存器(limit)、快表； 使用上述寄存器完成地址映射过程； 不能正常完成地址映射时产生中断。,6.1 存储管理功能(Cont.),6.2 内存资源管理,6.2.1 内存分区 分区时刻 静态分区: 系统初始化时分; 动态分区: 申请时分。 分区大小 等长分区 : 2 i 异长分区 : 依程序, 程序单位, 对象大小。 通常作法 静态+等长 (页式、段页式) ; 动态+异长 (段式、界地址) 。,6.2.

3、2 内存分配,静态等长分区的分配 分配策略: 分配几个等长区域 ; 分区表示: 字位映象图 ; 空闲页面表 ; 空闲页面链。 动态异长分区的分配 最先适应 (First Fit) ; 最佳适应 (Best Fit) ; 最坏适应 (Worst Fit) 。,6.2.2.1 静态等长分区的分配,字位映象图(bit map),用一个 bit 代表一页状态，0: 空闲，1: 占用。,分配: 按页号从小到大查字位图, 找到为0的位改为1，返回页号。,去配: 把页号对应的 bit 置为 0 。,空闲页面表:,内存,分配/去配: 需修改空闲页面表。 特点: 可以分配连续页面。 DMA 要求,6.2.2.1

4、 静态等长分区的分配(Cont.),空闲页面表结构,6.2.2.1 静态等长分区的分配(Cont.),空闲页面链 :,空闲页面链结构,分配/去配: 调整链表。 特点: 节省空间。 (不适合外存管理),6.2.2.2 动态异长分区的分配,常用于界地址存储管理和段式存储管理。,空闲区表,初始时一个连续空闲区; 空闲区首址由小到大; 长度 = 0 为表尾。 分配: 按分配策略调整表项; 去配: 把去配的空间插入表中, 可能需要合并空闲区。,6.2.2.2 动态异长分区的分配(Cont.),最先适应算法(First Fit) :,空闲区表,空闲区: 首址递增排列； 申请: 取第一个可满足区域 ; 优点

5、: 尽量使用低地址空间, 高区保持大空闲区域。 缺点: 可能分割大空闲区。 如申请32将分割第一个区域。,6.2.2.2 动态异长分区的分配(Cont.),最佳适应算法(Best Fit) :,空闲区表,空闲区: 空闲区长度递增排列 ; 申请: 取最小可满足区域 ; 优点: 尽量使用小空闲区, 保持大空闲区域。 缺点: 容易形成碎片fragment。 如申请30将留下长度为2的空闲区。,6.2.2.2 动态异长分区的分配(Cont.),最坏适应算法(Worst Fit) :,空闲区表,空闲区: 空闲区长度递减排列。 申请: 取最大可满足区域。 优点: 防止形成碎片。 缺点: 分割大空闲区。,例

6、: UNIX存储分配First Fit (见12章p286-12.4.2 ),最先适应算法，空闲区首址递增排列 define CMAPSIZ 100 define SMAPSIZ 100 struct map /存储资源表结构 char *m_size; char *m_addr; ; struct map coremapCMAPSIZ; /内存资源表 struct map swapmapSMAPSIZ; /外存资源表,int malloc (mp, size ) /存储分配函数 struct map *mp; register int a ; register struct map *bp

7、; for (bp = mp; bp - m_size ; bp +) if ( bp - m_size = size ) a= bp - m_addr ; bp - m_addr += size ; if ( bp - m_size -= size ) = 0) /当前块size do bp +; /do循环压缩size=0的存储表项 (bp-1) - m_addr = bp - m_addr ; while(bp-1)-m_size = bp - m_size); return(a); /分配成功，返回分配存储块的首地址 return(0); /分配不成功，返回0 ,mfree (mp,

8、size, aa) struct map *map; register struct map bp ; register int t , a ; a = aa ; for (bp = mp; bp - m_addrm_size !=0; bp +); if (bp mp , else /是存储表项的第一项或不与前项存储块相连 if (a+size = bp -m_addr ,存储释放算法(Cont.),6.2.3 碎片与紧凑,紧凑(Compaction): 移动占用区域，使所有空闲区域 连成一片(开销很大)。,紧凑前,紧凑后,6.3 存储管理方式,无虚拟功能的存储管理方式： 界地址管理方式(一

9、维地址) 页式管理方式(一维地址) 段式管理方式(二维地址) 段页式管理方式(二维地址),6.3.1 界地址管理方式,单对界存储管理方式: (首地址, 长度),基本原理 内存空间划分: 动态异长； 进程空间划分: 一个进程一个区域, 逻辑地址0L -1 ; 进程空间与内存空间对应关系(可以浮动) :,6.3.1 界地址管理方式(Cont.), 所需表目： 内存分配表: 在PCB中 ; 空闲区域表: array of ( addr , size )。 所需寄存器： 基址寄存器b: 保存运行进程起始地址; 限长寄存器l : 保存运行进程长度。,6.3.1 界地址管理方式(Cont.), 地址映射：

10、 : (a) (b+a) ,步骤 : 由程序确定逻辑地址 a ; a与 L 比较判断是否越界，不满足: 0aL-1，越界; a与 b 相加得到物理地址。,6.3.1 界地址管理方式(Cont.),双对界 代码区域: 首址寄存器、限长寄存器 ; 数据区域: 首址寄存器、限长寄存器 ; UNIX : 代码I空间、数据D空间。 交换与重定位 交换: 换入(swap-in)/换出(swap-out) ; 滚入(roll-in)/滚出(roll-out) ; 交换的基本单位为整个进程。 可重定位程序: 程序编址与内存存放位置无关 ; 浮动程序: 满足重定位要求的程序,如0起始编址。 重定位: 换入程序需

11、重定位。,6.3.1 界地址管理方式(Cont.),覆盖技术: 将较大程序装入较小进程空间的技术, 最大限度提高内存利用率。 只将全局代码和数据静态装入内存, 其它部分动态装入; 后装入的成分重复使用先装入成分所使用的 存储区, 即覆盖先装入的成分; 用户编写覆盖驱动程序, 无需操作系统支持。,6.3.1 界地址管理方式(Cont.),例覆盖技术：四遍扫描的编译程序,6.3.2 分页式存储管理,页式存储管理(paging): 一个进程占多个等长、连续内存空间; 无碎片。,6.3.2.1 基本原理 内存空间划分: 页架: 静态等长, 长度2 i ; 页架号: 所有页架由0开始依次编号 ; 页内地

12、址: 页架内单元由0开始依次编址。 例如: 内存容量为2 n , 则共有2 n-i个页架。 第 k 个页架的起始地址为 k2 i。,6.3.2 分页式存储管理(Cont.),内存空间划分,n 位一维地址码,6.3.2 分页式存储管理(Cont.), 进程空间划分: 静态等长，2 i, 称为一个页面。,进程空间划分,6.3.2 分页式存储管理(Cont.), 进程空间与内存空间对应关系: 页面连续, 页架可能不连续。,6.3.2 分页式存储管理(Cont.), 所需表目,页表: 每个进程一个。,总页表: 系统一个, 记录页架使用情况 两种结构：表、链。, 所需寄存器,页表首址寄存器: 系统一个。

13、,b,页表长度寄存器: 系统一个。,l,快表: 系统一组。,l =4,6.3.2 分页式存储管理(Cont.), 地址映射 : (p, d) (f, d) ,逻辑地址 (p, d) 物理地址 (f, d) : 由程序确定逻辑地址 (p, d) ; 由 p 查快表得页架号 f ; 如查不到： p 与 l 比较，判别是否越界: 不满足: 0 p l 1 , 越界中断; 由 p 和 b 查页表得 f, (p,f) 快表, 如满淘汰一个; 转 ; f 与 d 合并得物理地址 (f, d) 。,页表长度寄存器,页表首址寄存器,页 表,进程控制块PCB,快表TLB,页式存储管理地址映射,快表未查到 p,6

14、.3.2 分页式存储管理(Cont.),页表长度寄存器,页表首址寄存器,页 表,进程控制块PCB,快表TLB,页式存储管理地址映射,6.3.2 分页式存储管理(Cont.),有效访问时间Effective Access Time : EAT,6.3.2 分页式存储管理(Cont.),EAT = 快表命中率(快表访问时间+内存访问时间)+ 快表不中率(快表访问时间+2内存访问时间) ns 例：快表命中率98，快表访问时间20ns， 内存一次访问时间100ns，则 EAT = 98(20+100)+2(20+200) = 122 ns,6.3.2.2 多级页表,提出背景 内存空间成倍增长, 进程虚

15、拟空间成倍增加。 单级页表需要很大连续内存空间 例如: 232位进程地址空间(4G), 页长占212位(4K), 进程拥有的页面最多可达220, 即页表最多可达220个表项。 多线程设计导致进程虚拟空间不连续(空洞hole) 页表所占内存空间浪费。 解决策略: 减少页表所占内存空间。 二级或多级页表: 外页表, 内页表 栈的预留空间(没有页架相对应),6.3.2 分页式存储管理(Cont.),6.3.2 分页式存储管理(Cont.),0,1,1023,0,1023,0,1023,0,1023,Outer-page table,Page table,Memory,外页表对应hole的表项没有对应

16、的内页表，访问hole表项动态建立内页表,二级页表,6.3.2 分页式存储管理(Cont.),二级页表的地址映射:,Logical address structure :,10 bits,10 bits,12 bits,Page offset,Pi : outer page table index ; Pj : page table displacement .,Page number,address translation scheme :,Logical address,Outer-page table,p1,Page table,p2,memory,d,6.3.2 分页式存储管理(Con

17、t.),采用二级页表结构时, 逻辑地址由外层页号pi, 外层页内地址pj, 页内地址d三部分构成。若给定一个逻辑地址空间的地址为A, 系统页面大小为L, 页表项的长度为N, 则pi, pj和d的计算公式如下： pi = int int A/L / N pj = int A/L mod N d = A mod L 对前述二级页表结构, L=212, N=210,6.3.2 分页式存储管理(Cont.),4级页表有效访问时间,EAT=快表命中率(快表访问时间+内存访问时间)+ 快表不中率(快表访问时间+5内存访问时间) ns 例4级页表: 快表命中率98，快表访问时间20ns， 内存访问时间100

18、ns，则 EAT = 98%(20+100)+2% (20+500)ns =128ns,6.3.2.3 反置页表,传统页表面向进程空间 每个进程逻辑页面有一表项 ; 当进程空间很大时, 页表很大。 反置页表面向内存空间 系统只设置一个反置页表, 为所有进程所用。 反置页表大小固定; 每个内存页架一个表项, 表项序号即为页架号;,inverted page table,6.3.2.3 反置页表(Cont.),反置页表工作原理 :, ,逻辑地址,程序,0,f,物理地址,反置页表,d,f个页架,d,物理内存,速度问题,反置页表查找 由表头起始, 平均为表长度的一半 ; 速度慢。 解决方案 在反置页表

19、前增加一级杂凑表 ; 逻辑页号为关键字， 通过Hash函数确定进程反置页表首项位置。 查找杂凑表与反置页表至少需要两次访问内存 ; 为进一步提高速度，快表缓冲。,6.3.2.3 反置页表(Cont.),6.3.3 分段式存储管理 segmentation,6.3.2.1 基本原理 内存空间划分: 动态划分成异长区域，每个区域称作一个物理段; 物理段: 段首址, 段内地址(由0开始编址) ; 物理地址: 段首址+段内地址 (一维地址);, 进程空间划分: 静态划分成异长区域，每个区域称作一个逻辑段 ; 逻辑段: 程序单位, 如主程序, 子程序, 数据区, 模块 ; 段号: 每个进程有多个逻辑段，

20、从0开始依次编号 ; 逻辑段的段内地址从0开始编址 ; 逻辑地址: (二维地址),6.3.3 分段式存储管理(Cont.),140 KB,100 KB,130 KB,60 KB,20 KB,50 KB,0 KB,内存空间划分, 调用X段入口E . 访问DATA段A单元 调用Y段入口F ,主程序段: main 段号=0,0,50KB-1,. . . . . ., F: ,子程序段: Y 段号=2,0,30KB-1, E： ,子程序段: X 段号=3,0,40KB-1, A: ,子程序段: DATA 段号=1,0,30KB-1,进程空间,6.3.3 分段式存储管理(Cont.), 进程空间与内存空

21、间对应关系:,进程P 段main 段号=0,进程P 段data 段号=1,进程P 段Y 段号=2,进程P 段X 段号=3,0,50KB-1,0,0,0,30KB-1,40KB-1,30KB-1,120 KB,390 KB,480 KB,810 KB,50 KB,30 KB,30 KB,40 KB,120 KB,220 KB,60 KB,300 KB,6.3.3 分段式存储管理(Cont.), 所需表目:, 段表: 每个进程一个。, 空闲表: 系统一个 array of (addr,size),6.3.3 分段式存储管理(Cont.), 所需寄存器:, 段表首址寄存器一个 :, 段表长度寄存器一

22、个:, 快表: 系统一组,b,l,逻辑地址 (s, d) 物理地址 (b+ d) : 由程序确定逻辑地址 (s, d) ; 由 s 查快表得 b和 l ;如查不到： s 与 l 比较，判别是否越界: 不满足: 0 s l 1 , 越界中断; 由 s 和 b 查段表得 b和 l , (s,b,l)快表, 如快表满淘汰一个； 转 ; d 与 l 比较, 不满足: 0dl-1 , 越界 ; b+d 得物理地址。,6.3.3 分段式存储管理(Cont.), 地址映射: : (s, d) ( b + d ) ,6.3.3 分段式存储管理(Cont.),段 表,进程控制块PCB,快表TLB,段式存储管理地

23、址映射,若快表查不到s,6.3.3 分段式存储管理(Cont.),段 表,进程控制块PCB,快表TLB,段式存储管理地址映射,6.3.3 分段式存储管理(Cont.),6.3.2.2 段的共享与保护 段的共享: 不同进程的段号Spi和Spj对应同一个段的段首址 和段长即可实现不同进程对段的共享。,P1段表,si,段号,P2段表,sj,段号,b:,l,内存空间,6.3.3 分段式存储管理(Cont.),共享段表: 系统1个, 记录所有共享段。,P1,0,段号,P2,1,2,3,4,0,段号,1,2,3,段 表,共享段表,主 存,6.3.3 分段式存储管理(Cont.), 段的保护: 不同进程对共享段的访问权限不同， 需要在段表中加上访问权限。,段表的改进,s,段号,快表的改进,页式管理和段式管理的比较:,6.3.3 分段式存