工学存储管理学习教案

1、会计学1工学存储管理工学存储管理第一页，编辑于星期二：点 二十一分。6.1 存储管理功能存储管理功能n 内存/外存的管理;n 内/外存管理采用相同 或相似的管理技术；n 功 能 l 存储分配存储分配l 存储共享存储共享l 存储保护存储保护l 存储扩充存储扩充l 地址映射地址映射第1页/共62页第二页，编辑于星期二：点 二十一分。第2页/共62页第三页，编辑于星期二：点 二十一分。第3页/共62页第四页，编辑于星期二：点 二十一分。第4页/共62页第五页，编辑于星期二：点 二十一分。第5页/共62页第六页，编辑于星期二：点 二十一分。6.2.2.1 静态等长分区的分配静态等长分区的分配n 字位映

2、象图字位映象图(bit map)用一个 bit 代表一页状态，0: 空闲，1: 占用。1001.10第第0页页第第1页页第第2页页第第k页页第第n-1页页第第n页页分配: 按页号从小到大查字位图, 找到为0的位改为1，返回页号。去配: 把页号对应的 bit 置为 0 。第6页/共62页第七页，编辑于星期二：点 二十一分。n 空闲页面表空闲页面表:首页面号首页面号页面个数页面个数1204占用占用120页页121页页122页页123页页占用占用内存内存分配/去配: 需修改空闲页面表。特点: 可以分配连续页面。 DMA 要求6.2.2.1 静态等长分区的分配静态等长分区的分配(Cont.)空闲页面表

3、结构空闲页面表结构第7页/共62页第八页，编辑于星期二：点 二十一分。6.2.2.1 静态等长分区的分配静态等长分区的分配(Cont.)n 空闲页面链空闲页面链 :占 用占 用占 用head空闲页面链结构空闲页面链结构分配/去配: 调整链表。特点: 节省空间。 (不适合外存管理)第8页/共62页第九页，编辑于星期二：点 二十一分。6.2.2.2 动态异长分区的分配动态异长分区的分配常用于界地址存储管理和段式存储管理。常用于界地址存储管理和段式存储管理。空闲区首址空闲区首址空闲区长度空闲区长度.addresssize0空闲区表空闲区表n 初始时一个连续空闲区;n 空闲区首址由小到大;n 长度 =

4、 0 为表尾。分配: 按分配策略调整表项;去配: 把去配的空间插入表中, 可能需要合并空闲区。第9页/共62页第十页，编辑于星期二：点 二十一分。6.2.2.2 动态异长分区的分配动态异长分区的分配(Cont.)最先适应算法最先适应算法(First Fit) :空闲区首址空闲区首址空闲区长度空闲区长度128642563210242560空闲区表空闲区表空闲区: 首址递增排列；申请: 取第一个可满足区域 ;优点: 尽量使用低地址空间, 高区保持大空闲区域。缺点: 可能分割大空闲区。 如申请32将分割第一个区域。第10页/共62页第十一页，编辑于星期二：点 二十一分。6.2.2.2 动态异长分区的

5、分配动态异长分区的分配(Cont.)最佳适应算法最佳适应算法(Best Fit) :空闲区首址空闲区首址空闲区长度空闲区长度256321286410242560空闲区表空闲区表空闲区: 空闲区长度递增排列 ;申请: 取最小可满足区域 ;优点: 尽量使用小空闲区, 保持大空闲区域。缺点: 容易形成碎片fragment。 如申请30将留下长度为2的空闲区。第11页/共62页第十二页，编辑于星期二：点 二十一分。6.2.2.2 动态异长分区的分配动态异长分区的分配(Cont.)最坏适应算法最坏适应算法(Worst Fit) :空闲区首址空闲区首址空闲区长度空闲区长度10242561286425632

6、0空闲区表空闲区表空闲区: 空闲区长度递减排列。申请: 取最大可满足区域。优点: 防止形成碎片。缺点: 分割大空闲区。第12页/共62页第十三页，编辑于星期二：点 二十一分。最先适应算法，空闲区首址递增排列define CMAPSIZ 100define SMAPSIZ 100struct map /存储资源表结构 char *m_size; char *m_addr;struct map coremapCMAPSIZ; /内存资源表struct map swapmapSMAPSIZ; /外存资源表第13页/共62页第十四页，编辑于星期二：点 二十一分。int malloc (mp, size

7、 ) /存储分配函数struct map *mp; register int a ; register struct map *bp ; 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_siz

8、e); return(a); /分配成功，返回分配存储块的首地址 return(0); /分配不成功，返回0存储分配函数: mp=coremap 内存分配swapmap 外存分配第14页/共62页第十五页，编辑于星期二：点 二十一分。mfree (mp, 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 & (bp-1)-m_addr+(bp-1)-m_size = a

9、) (bp-1)-m_size =+ size; /与前项存储块合并 if (a+size = bp - m_addr) /判断与后项存储块是否相连 (bp-1)-m_size += bp -m_size; /再与后项存储块合并 while (bp-m_size) /删除后项存储块表项 bp+; (bp-1)- m_addr = bp - m_addr ; (bp-1)-m_size = bp - m_size ; 存储释放算法: mp=coremap 释放内存swapmap 释放外存第15页/共62页第十六页，编辑于星期二：点 二十一分。 else /是存储表项的第一项或不与前项存储块相连

10、if (a+size = bp -m_addr & bp -m_size) /与后项存储块相连? bp- m_addr -= size; /与后项存储块合并。 bp -m_size += size ; else if (size) /与前、后项存储块均不相连, 插入(size,a)表项 do t = bp - m_addr ; /do循环逐项后移 bp - m_addr = a; a = t; /a与 bp - m_addr 交换 t = bp - m_size; bp - m_size = size; / size 与bp - m_size 交换 bp+; while (size =

11、 t ); 存储释放算法(Cont.)第16页/共62页第十七页，编辑于星期二：点 二十一分。6.2.3 碎片与紧凑碎片与紧凑紧凑(Compaction): 移动占用区域，使所有空闲区域 连成一片(开销很大)。0 KB操作系统空间操作系统空间20KB20 KB空闲区域空闲区域10KB30 KB进程进程p1空间空间30KB60 KB空闲区域空闲区域10KB70 KB进程进程p1空间空间20KB90 KB空闲区域空闲区域10KB紧凑前0 KB操作系统空间操作系统空间20KB20 KB进程进程p1空间空间30KB50 KB进程进程p1空间空间20KB70 KB空闲区域空闲区域30KB紧凑后第17页/

12、共62页第十八页，编辑于星期二：点 二十一分。址址)n 段页式管理方式段页式管理方式(二维二维地址地址)第18页/共62页第十九页，编辑于星期二：点 二十一分。6.3.1 界地址管理方式界地址管理方式单对界存储管理方式单对界存储管理方式: (首地址首地址, 长度长度)基本原理 内存空间划分: 动态异长； 进程空间划分: 一个进程一个区域, 逻辑地址0L -1 ; 进程空间与内存空间对应关系(可以浮动) :0 :L-1 :b :b+L-1 :L进程空间内存空间第19页/共62页第二十页，编辑于星期二：点 二十一分。6.3.1 界地址管理方式界地址管理方式(Cont.) 所需表目： 内存分配表:

13、在PCB中 ; 空闲区域表: array of ( addr , size )。 所需寄存器： 基址寄存器b: 保存运行进程起始地址; 限长寄存器l : 保存运行进程长度。第20页/共62页第二十一页，编辑于星期二：点 二十一分。6.3.1 界地址管理方式界地址管理方式(Cont.) 地址映射： : (a) (b+a) 0:L-1:b:b+L-1:L进程空间内存空间限长寄存器首址寄存器Lba越界中断CMP+b+a步骤 : 由程序确定逻辑地址 a ; a与 L 比较判断是否越界，不满足: 0aL-1，越界; a与 b 相加得到物理地址。第21页/共62页第二十二页，编辑于星期二：点 二十一分。6

14、.3.1 界地址管理方式界地址管理方式(Cont.)n 双对界l 代码区域代码区域: 首址寄存器、限长寄存器首址寄存器、限长寄存器 ;l 数据区域数据区域: 首址寄存器、限长寄存器首址寄存器、限长寄存器 ;l UNIX : 代码代码I空间、数据空间、数据D空间。空间。n 交换与重定位l 交换交换: 换入换入(swap-in)/换出换出(swap-out) ; 滚入(roll-in)/滚出(roll-out) ; 交换的基本单位为整个进程。l 可重定位程序可重定位程序: 程序编址与内存存放位置无关程序编址与内存存放位置无关 ;l 浮动程序浮动程序: 满足重定位要求的程序满足重定位要求的程序,如如

15、0起始编址。起始编址。l 重定位重定位: 换入程序需重定位。换入程序需重定位。第22页/共62页第二十三页，编辑于星期二：点 二十一分。6.3.1 界地址管理方式界地址管理方式(Cont.)n 覆盖技术覆盖技术: 将较大程序装入较小进程空间的技术将较大程序装入较小进程空间的技术, 最大限度提高内存利用率。最大限度提高内存利用率。l 只将全局代码和数据静态装入内存只将全局代码和数据静态装入内存, 其它部分动态装入其它部分动态装入;l 后装入的成分重复使用先装入成分所使用的后装入的成分重复使用先装入成分所使用的 存储区存储区, 即覆盖先装入的成分即覆盖先装入的成分;l 用户编写用户编写覆盖驱动程序

16、覆盖驱动程序, 无需操作系统支持。无需操作系统支持。第23页/共62页第二十四页，编辑于星期二：点 二十一分。6.3.1 界地址管理方式界地址管理方式(Cont.)例覆盖技术：四遍扫描的编译程序符符 号号 表表公公 共共 例例 程程覆盖驱动程序覆盖驱动程序覆覆 盖盖 区区50 KB内 存Pass130 KBPass250 KBPass425 KBPass340 KB第24页/共62页第二十五页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理页式存储管理(paging): 一个进程占多个等长、连续内存空间; 无碎片。6.3.2.1 基本原理 内存空间划分: 页架: 静态等长

17、, 长度2 i ; 页架号: 所有页架由0开始依次编号 ; 页内地址: 页架内单元由0开始依次编址。 例如: 内存容量为2 n , 则共有2 n-i个页架。 第 k 个页架的起始地址为 k2 i。第25页/共62页第二十六页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.)02i第第 0 页页2i12i第第 1 页页2ik2i第第 k 页页2i(2n-i-1)2i第第 2n-i1 页页2i内存空间划分n 位一维地址码=页架首址+页内地址=页架号2i+页内地址=页内地址页内地址页架号页架号i 位n-i 位物理地址第26页/共62页第二十七页，编辑于星期二：点 二

18、十一分。6.3.2 分页式存储管理分页式存储管理(Cont.) 进程空间划分: 静态等长，2 i, 称为一个页面。02i第第 0 页页2i12i第第 1 页页2ik2i第第 k 页页2i(l-1)2i第第 l1 页页2i进程空间划分=逻辑页首址+页内地址=逻辑页号2i+页内地址=页内地址页内地址逻辑页号逻辑页号i 位n-i 位逻辑地址第27页/共62页第二十八页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.) 进程空间与内存空间对应关系: 页面连续, 页架可能不连续。第第 3 页页第第 2 页页第第 1 页页第第 0 页页进程空间第第 79 页页第第 78

19、页页第第 47 页页第第 18 页页内存空间第28页/共62页第二十九页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.) 所需表目n 页表: 每个进程一个。页架号页架号18477978逻辑页号逻辑页号0123n 总页表: 系统一个, 记录页架使用情况 两种结构：表、链。 所需寄存器n 页表首址寄存器: 系统一个。bn 页表长度寄存器: 系统一个。ln 快表: 系统一组。逻辑页号逻辑页号页架号页架号pfl =4第29页/共62页第三十页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.) 地址映射 : (p, d) (f, d)

20、 逻辑地址 (p, d) 物理地址 (f, d) : 由程序确定逻辑地址 (p, d) ; 由 p 查快表得页架号 f ; 如查不到： p 与 l 比较，判别是否越界: 不满足: 0 p l 1 , 越界中断; 由 p 和 b 查页表得 f, (p,f) 快表, 如满淘汰一个; 转 ; f 与 d 合并得物理地址 (f, d) 。第30页/共62页第三十一页，编辑于星期二：点 二十一分。页表长度寄存器页表首址寄存器lb页架号页架号f逻辅逻辅页号页号0pl-1进程标识进程标识pid页表长度页表长度 l页表首址页表首址 b页 表进程控制块PCB逻辑页号逻辑页号页架号页架号pf 快表TLBdp页内地

21、址页内地址页号页号 逻辑地址df页内地址页内地址页架号页架号物理地址页式存储管理地址映射快表未查到 p6.3.2 分页式存储管理分页式存储管理(Cont.)第31页/共62页第三十二页，编辑于星期二：点 二十一分。页表长度寄存器页表首址寄存器lb页架号页架号f0逻辑逻辑页号页号l-1p页 表进程控制块PCB逻辑页号逻辑页号页架号页架号pf 快表TLBdp页内地址页内地址页号页号 逻辑地址df页内地址页内地址页架号页架号物理地址Cmp p:lb+p页式存储管理地址映射fp6.3.2 分页式存储管理分页式存储管理(Cont.)进程标识进程标识pid页表长度页表长度 l页表首址页表首址 b第32页/

22、共62页第三十三页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.)EAT = 快表命中率(快表访问时间+内存访问时间)+ 快表不中率快表不中率(快表访问时间快表访问时间+2内存访问时间内存访问时间) ns 例：快表命中率例：快表命中率98，快表访问时间，快表访问时间20ns， 内存一次访问时间内存一次访问时间100ns，则，则 EAT = 98 (20+100)+2 (20+200) = 122 ns第33页/共62页第三十四页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.)第34页/共62页第三十五页，编辑于星期二：点

23、二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.)01102320951023094985120102301023010232095102309498512Outer-pagetablePage tableMemory外页表对应hole的表项没有对应的内页表，访问hole表项动态建立内页表二级页表第35页/共62页第三十六页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.)二级页表的地址映射: pipjdn Logical address structure :10 bits10 bits12 bitsPage offsetPi : outer

24、page table index ;Pj : page table displacement .Page numbern address translation scheme :p1p2dLogical address.Outer-pagetablep1.fPage tablep2.Physicaladdressmemoryd第36页/共62页第三十七页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.) 采用二级页表结构时, 逻辑地址由外层页号pi, 外层页内地址pj, 页内地址d三部分构成。若给定一个逻辑地址空间的地址为A, 系统页面大小为L, 页表项的长度

25、为N, 则pi, pj和d的计算公式如下： pi = int int A/L / N pj = int A/L mod N d = A mod L 对前述二级页表结构, L=212, N=210第37页/共62页第三十八页，编辑于星期二：点 二十一分。6.3.2 分页式存储管理分页式存储管理(Cont.)4级页表有效访问时间级页表有效访问时间n EAT=快表命中率快表命中率 (快表访问时间快表访问时间+内存访问时间内存访问时间)+ 快表不中率快表不中率 (快表访问时间快表访问时间+5 内存访问时间内存访问时间) ns例例4级页表级页表: 快表命中率快表命中率98，快表访问时间，快表访问时间20

26、ns， 内存访问时间内存访问时间100ns，则，则 EAT = 98% (20+100)+2% (20+500)ns =128ns第38页/共62页第三十九页，编辑于星期二：点 二十一分。inverted page table第39页/共62页第四十页，编辑于星期二：点 二十一分。6.3.2.3 反置页表反置页表(Cont.)反置页表工作原理反置页表工作原理 : pidpd逻辑地址pidp程序0ffd物理地址反置页表d f个页架d物理内存第40页/共62页第四十一页，编辑于星期二：点 二十一分。6.3.2.3 反置页表反置页表(Cont.)第41页/共62页第四十二页，编辑于星期二：点 二十一

27、分。6.3.3 分段式存储管理分段式存储管理 segmentation6.3.2.1 基本原理 内存空间划分: n动态划分成异长区域，每个区域称作一个动态划分成异长区域，每个区域称作一个物理段物理段;n物理段物理段: 段首址段首址, 段内地址段内地址(由由0开始编址开始编址) ;n物理地址物理地址: 段首址段首址+段内地址段内地址 (一维地址一维地址);段号段号段内地址段内地址 进程空间划分:n静态划分成异长区域，每个区域称作一个静态划分成异长区域，每个区域称作一个逻辑段逻辑段 ;n逻辑段逻辑段: 程序单位程序单位, 如主程序如主程序, 子程序子程序, 数据区数据区, 模块模块 ;n段号段号:

28、 每个进程有多个逻辑段，从每个进程有多个逻辑段，从0开始依次编号开始依次编号 ;n逻辑段的段内地址从逻辑段的段内地址从0开始编址开始编址 ;n逻辑地址逻辑地址: (二维地址二维地址)第42页/共62页第四十三页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(Cont.)占用占用空闲空闲占用占用空闲空闲占用占用空闲空闲占用占用140 KB100 KB130 KB60 KB20 KB50 KB 0 KB内存空间划分调用X段入口E.访问DATA段A单元调用Y段入口F主程序段: main段号=0 050KB-1. F: 子程序段: Y段号=2 030KB-1 E： 子程序段:

29、X段号=3 040KB-1 A: 子程序段: DATA段号=1 030KB-1进程空间第43页/共62页第四十四页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(Cont.) 进程空间与内存空间对应关系: 进程P段main段号=0进程P段data段号=1进程P段Y段号=2进程P段X段号=3 050KB-1 0 0 030KB-140KB-130KB-1120 KB390 KB480 KB810 KB50 KB30 KB30 KB40 KB120 KB220 KB60 KB300 KB第44页/共62页第四十五页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段

30、式存储管理(Cont.) 所需表目: 段表: 每个进程一个。段号段号段首址段首址段长段长0120 KB50 KB1 390 KB30 KB2 480 KB30 KB3 810 KB40 KB 空闲表: 系统一个 array of (addr,size)首地址首地址长度长度 0 KB120 KB 170 KB220 KB 420 KB 60 KB 510 KB300 KB第45页/共62页第四十六页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(Cont.) 所需寄存器: 段表首址寄存器一个 : 段表长度寄存器一个: 快表: 系统一组bl段号段号段首址段首址段长度段长度s

31、bl第46页/共62页第四十七页，编辑于星期二：点 二十一分。逻辑地址 (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 ) 第47页/共62页第四十八页，编辑于星期二：点 二十一分。

32、6.3.3 分段式存储管理分段式存储管理(Cont.)段首址段首址段长段长bl段号段号0sl-1进程标识进程标识pid段表长度段表长度 l段表首址段表首址 b段 表进程控制块PCB段号段号段首址段首址段长段长sbl 快表TLB段式存储管理地址映射偏移偏移段号段号 逻辑地址dscmp物理地址b+d+段表长度reg段表首址regbl若快表查不到s第48页/共62页第四十九页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(Cont.)段首址段首址段长段长bl段号段号0sl-1进程标识进程标识pid段表长度段表长度 l段表首址段表首址 b段 表进程控制块PCB段号段号段首址段首

33、址段长段长sbl 快表TLB段式存储管理地址映射sbl偏移偏移段号段号 逻辑地址dscmp物理地址b+d+段表长度reg段表首址regbl+cmp第49页/共62页第五十页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(Cont.) 6.3.2.2 段的共享与保护 段的共享: 不同进程的段号Spi和Spj对应同一个段的段首址 和段长即可实现不同进程对段的共享。段首址段首址段长度段长度blP1段表si段号段首址段首址段长度段长度blP2段表sj段号共享段共享段b:l内存空间第50页/共62页第五十一页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(

34、Cont.)共享段表: 系统1个, 记录所有共享段。main1子程序子程序X子程序子程序Ydatamain2data子程序子程序Y子程序子程序X段长度段长度 首址首址P10段号P21234段长度段长度 首址首址0段号123段 表段名段名共享共享计数计数段长度段长度 段首址段首址其其它它X2Y2data2共享段表main1XDataYmain2主 存第51页/共62页第五十二页，编辑于星期二：点 二十一分。6.3.3 分段式存储管理分段式存储管理(Cont.) 段的保护: 不同进程对共享段的访问权限不同， 需要在段表中加上访问权限。段首址段首址段长度段长度访问权限访问权限RWEbl101段表的改

35、进s段号段号段号段首址段首址 段长度段长度访问权限访问权限RWEsbl101快表的改进第52页/共62页第五十三页，编辑于星期二：点 二十一分。页式管理页式管理段式管理段式管理一维地址空间一维地址空间二维地址空间二维地址空间页是物理单位页是物理单位段是逻辑单位段是逻辑单位页的大小固定页的大小固定段的大小可变段的大小可变对用户透明对用户透明对用户可见对用户可见无碎片无碎片有碎片有碎片通常不共享通常不共享便于共享、保护便于共享、保护页式管理和段式管理的比较:6.3.3 分段式存储管理分段式存储管理(Cont.)第53页/共62页第五十四页，编辑于星期二：点 二十一分。6.3.4 段页式存储管理段页

36、式存储管理segmentation with paging第54页/共62页第五十五页，编辑于星期二：点 二十一分。6.3.4 段页式存储管理段页式存储管理(Cont.)6.3.4.1 基本原理 内存空间划分: (同页式) 静态等长, 2i, 称为一页架 ; 物理地址 = = (f,d)。页内地址页内地址页架号页架号n-i 位i 位 进程空间划分: 一个进程若干个段; 一个段若干个页; 逻辑地址= =(s,p,d)。段号段号页内地址页内地址逻辑页号逻辑页号i 位j 位n-i-j 位第55页/共62页第五十六页，编辑于星期二：点 二十一分。 进程空间与内存空间对应关系: 6.3.4 段页式存储管理段页式存储管理(Cont.)第第 0 页页第第 1 页页第第 2 页页第第 0 页页第第 1 页页第第 2 页页第第 0 页页第第 1