工学存储管理学习教案

1、会计学1工学存储管理工学存储管理第一页，共63页。6.1 存储管理功能存储管理功能(gngnng)n 内存/外存的管理;n 内/外存管理采用(ciyng)相同n 或相似的管理技术；n 功 能 n 存储分配n 存储共享n 存储保护n 存储扩充n 地址映射第1页/共62页第二页，共63页。第2页/共62页第三页，共63页。第3页/共62页第四页，共63页。第4页/共62页第五页，共63页。第5页/共62页第六页，共63页。6.2.2.1 静态静态(jngti)等长分区等长分区的分配的分配n 字位映象字位映象(yn xin)图图(bit map)用一个(y ) bit 代表一页状态，0: 空闲，1:

2、 占用。1001.10第第0页页第第1页页第第2页页第第k页页第第n-1页页第第n页页分配: 按页号从小到大查字位图, 找到为0的位改为1，返回页号。去配: 把页号对应的 bit 置为 0 。第6页/共62页第七页，共63页。n 空闲空闲(kngxin)页面表页面表:首页面号首页面号页面个数页面个数1204占用占用120页页121页页122页页123页页占用占用内存内存(ni cn)分配/去配: 需修改空闲页面(y min)表。特点: 可以分配连续页面(y min)。 DMA 要求6.2.2.1 静态等长分区的分配静态等长分区的分配(Cont.)空闲页面表结构空闲页面表结构第7页/共62页第八

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

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

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

6、闲区首址空闲区首址空闲区长度空闲区长度102425612864256320空闲空闲(kngxin)区表区表空闲区: 空闲区长度递减排列。申请: 取最大可满足区域。优点: 防止形成碎片。缺点: 分割大空闲区。第12页/共62页第十三页，共63页。最先适应算法，空闲区首址递增排列(pili)define CMAPSIZ 100define SMAPSIZ 100struct map /存储资源表结构 char *m_size; char *m_addr;struct map coremapCMAPSIZ; /内存资源表struct map swapmapSMAPSIZ; /外存资源表第13页/共6

7、2页第十四页，共63页。int malloc (mp, size ) /存储(cn ch)分配函数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的存储(cn ch)表项 (bp-1) - m_addr =

8、 bp - m_addr ; while(bp-1)-m_size = bp - m_size); return(a); /分配成功，返回分配存储(cn ch)块的首地址 return(0); /分配不成功，返回0存储分配函数: mp=coremap 内存分配swapmap 外存分配第14页/共62页第十五页，共63页。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

9、(bp mp & (bp-1)-m_addr+(bp-1)-m_size = a) (bp-1)-m_size =+ size; /与前项存储块合并 if (a+size = bp - m_addr) /判断与后项存储块是否相连(xin lin) (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 释放外存第1

10、5页/共62页第十六页，共63页。 else /是存储(cn ch)表项的第一项或不与前项存储(cn ch)块相连 if (a+size = bp -m_addr & bp -m_size) /与后项存储(cn ch)块相连? bp- m_addr -= size; /与后项存储(cn ch)块合并。 bp -m_size += size ; else if (size) /与前、后项存储(cn ch)块均不相连, 插入(size,a)表项 do t = bp - m_addr ; /do循环逐项后移 bp - m_addr = a; a = t; /a与 bp - m_addr 交换

11、 t = bp - m_size; bp - m_size = size; / size 与bp - m_size 交换 bp+; while (size = t ); 存储(cn ch)释放算法(Cont.)第16页/共62页第十七页，共63页。6.2.3 碎片碎片(su pin)与紧凑与紧凑紧凑(jncu)(Compaction): 移动占用区域，使所有空闲区域 连成一片(开销很大)。0 KB操作系统空间操作系统空间20KB20 KB空闲区域空闲区域10KB30 KB进程进程p1空间空间30KB60 KB空闲区域空闲区域10KB70 KB进程进程p1空间空间20KB90 KB空闲区域空闲区

12、域10KB紧凑(jncu)前0 KB操作系统空间操作系统空间20KB20 KB进程进程p1空间空间30KB50 KB进程进程p1空间空间20KB70 KB空闲区域空闲区域30KB紧凑后第17页/共62页第十八页，共63页。(fngsh)(二维地址二维地址)段页式管理方式段页式管理方式(fngsh)(二维地址二维地址)第18页/共62页第十九页，共63页。6.3.1 界地址界地址(dzh)管理管理方式方式单对界存储管理方式单对界存储管理方式(fngsh): (首地址首地址, 长度长度)基本原理 内存空间划分: 动态异长； 进程空间划分: 一个进程一个区域, 逻辑地址0L -1 ; 进程空间与内存

13、空间对应(duyng)关系(可以浮动) :0 :L-1 :b :b+L-1 :L进程空间内存空间第19页/共62页第二十页，共63页。6.3.1 界地址界地址(dzh)管理方式管理方式(Cont.) 所需表目： 内存分配(fnpi)表: 在PCB中 ; 空闲区域表: array of ( addr , size )。 所需寄存器： 基址寄存器b: 保存运行进程起始地址; 限长寄存器l : 保存运行进程长度。第20页/共62页第二十一页，共63页。6.3.1 界地址管理界地址管理(gunl)方式方式(Cont.) 地址映射： : (a) (b+a) 0:L-1:b:b+L-1:L进程空间内存空间

14、限长寄存器首址寄存器Lba越界中断CMP+b+a步骤 : 由程序确定(qudng)逻辑地址 a ; a与 L 比较判断是否越界，不满足: 0aL-1，越界; a与 b 相加得到物理地址。第21页/共62页第二十二页，共63页。6.3.1 界地址界地址(dzh)管理方式管理方式(Cont.)n 双对界n 代码区域: 首址寄存器、限长寄存器 ;n 数据区域: 首址寄存器、限长寄存器 ;n UNIX : 代码I空间、数据D空间。n 交换与重定位n 交换: 换入(swap-in)/换出(swap-out) ;n 滚入(roll-in)/滚出(roll-out) ;n 交换的基本单位为整个进程。n 可重

15、定位程序: 程序编址与内存存放位置无关 ;n 浮动程序: 满足(mnz)重定位要求的程序,如0起始编址。n 重定位: 换入程序需重定位。第22页/共62页第二十三页，共63页。6.3.1 界地址界地址(dzh)管理方式管理方式(Cont.)n 覆盖技术覆盖技术: 将较大程序装入较小进程空间的技术将较大程序装入较小进程空间的技术,n 最大限度最大限度(xind)提高内存利用率。提高内存利用率。n 只将全局代码和数据静态装入内存只将全局代码和数据静态装入内存, n 其它部分动态装入其它部分动态装入;n 后装入的成分重复使用先装入成分所使用的后装入的成分重复使用先装入成分所使用的n 存储区存储区,

16、即覆盖先装入的成分即覆盖先装入的成分;n 用户编写覆盖驱动程序用户编写覆盖驱动程序, 无需操作系统支持。无需操作系统支持。第23页/共62页第二十四页，共63页。6.3.1 界地址管理界地址管理(gunl)方式方式(Cont.)例覆盖(fgi)技术：四遍扫描的编译程序符符 号号 表表公公 共共 例例 程程覆盖驱动程序覆盖驱动程序覆覆 盖盖 区区50 KB内 存Pass130 KBPass250 KBPass425 KBPass340 KB第24页/共62页第二十五页，共63页。6.3.2 分页式存储管理分页式存储管理页式存储管理(paging): 一个进程占多个(du )等长、连续内存空间;

17、无碎片。6.3.2.1 基本原理 内存空间划分: 页架: 静态等长, 长度2 i ; 页架号: 所有页架由0开始依次编号 ; 页内地址(dzh): 页架内单元由0开始依次编址。 例如: 内存容量为2 n , 则共有2 n-i个页架。 第 k 个页架的起始地址(dzh)为 k2 i。第25页/共62页第二十六页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.)02i第第 0 页页2i12i第第 1 页页2ik2i第第 k 页页2i(2n-i-1)2i第第 2n-i1 页页2i内存空间划分(hu fn)n 位一维地址码=页架首址+页内地址=页架号2i+页内地址=页内地址页内地址页架

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

19、第 3 页页第第 2 页页第第 1 页页第第 0 页页进程空间第第 79 页页第第 78 页页第第 47 页页第第 18 页页内存空间第28页/共62页第二十九页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.) 所需表目n 页表: 每个进程(jnchng)一个。页架号页架号18477978逻辑页号逻辑页号0123n 总页表: 系统一个,n 记录(jl)页架使用情况n 两种结构：表、链。 所需寄存器n 页表首址寄存器:n 系统(xtng)一个。bn 页表长度寄存器: 系统一个。ln 快表: 系统一组。逻辑页号逻辑页号页架号页架号pfl =4第29页/共62页第三十页，共63页。

20、6.3.2 分页式存储管理分页式存储管理(Cont.) 地址映射 : (p, d) (f, d) 逻辑地址(dzh) (p, d) 物理地址(dzh) (f, d) : 由程序确定逻辑地址(dzh) (p, d) ; 由 p 查快表得页架号 f ; 如查不到： p 与 l 比较，判别是否越界: 不满足: 0 p l 1 , 越界中断; 由 p 和 b 查页表得 f, (p,f) 快表, 如满淘汰一个; 转 ; f 与 d 合并得物理地址(dzh) (f, d) 。第30页/共62页第三十一页，共63页。页表长度(chngd)寄存器页表首址寄存器lb页架号页架号f逻辅逻辅页号页号0pl-1进程标

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

22、:lb+p页式存储管理地址映射fp6.3.2 分页式存储管理分页式存储管理(Cont.)进程标识进程标识pid页表长度页表长度 l页表首址页表首址 b第32页/共62页第三十三页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.)EAT = 快表命中率(快表访问(fngwn)时间+内存访问(fngwn)时间)+ 快表不中率(快表访问(fngwn)时间+2内存访问(fngwn)时间) ns 例：快表命中率98，快表访问(fngwn)时间20ns， 内存一次访问(fngwn)时间100ns，则 EAT = 98(20+100)+2(20+200) = 122 ns第33页/共62页第

23、三十四页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.)第34页/共62页第三十五页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.)01102320951023094985120102301023010232095102309498512Outer-pagetablePage tableMemory外页表对应hole的表项没有(mi yu)对应的内页表，访问hole表项动态建立内页表二级页表第35页/共62页第三十六页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.)二级页表的地址映射: pipjdn Logical address stru

24、cture :10 bits10 bits12 bitsPage offsetPi : outer page table index ;Pj : page table displacement .Page numbern address translation scheme :p1p2dLogical address.Outer-pagetablep1.fPage tablep2.Physicaladdressmemoryd第36页/共62页第三十七页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.) 采用二级页表结构时, 逻辑地址由外层页号pi, 外层页内地址pj, 页内地址

25、d三部分(b fen)构成。若给定一个逻辑地址空间的地址为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第37页/共62页第三十八页，共63页。6.3.2 分页式存储管理分页式存储管理(Cont.)4级页表有效访问级页表有效访问(fngwn)时间时间nEAT=快表命中率快表命中率(快表访问时间快表访问时间(shjin)+内存访问时间内存访问时间(shjin)+n 快表不中率快表不中率(快表访问时间快表访问时间(

26、shjin)+5内存访问时间内存访问时间(shjin) nsn例例4级页表级页表: 快表命中率快表命中率98，快表访问时间，快表访问时间(shjin)20ns，n 内存访问时间内存访问时间(shjin)100ns，则，则 n EAT = 98%(20+100)+2% (20+500)nsn =128ns第38页/共62页第三十九页，共63页。inverted page table第39页/共62页第四十页，共63页。6.3.2.3 反置页表反置页表(Cont.)反置页表工作反置页表工作(gngzu)原理原理 : pidpd逻辑(lu j)地址pidp程序0ffd物理地址反置页表d f个页架d物

27、理内存第40页/共62页第四十一页，共63页。6.3.2.3 反置页表反置页表(Cont.)第41页/共62页第四十二页，共63页。6.3.3 分段分段(fn dun)式式存储管理存储管理 segmentation6.3.2.1 基本原理 内存空间划分: 动态划分成异长区域(qy)，每个区域(qy)称作一个物理段;物理段: 段首址, 段内地址(由0开始编址) ;物理地址: 段首址+段内地址 (一维地址);段号段号段内地址段内地址 进程空间划分:静态划分成异长区域，每个区域称作一个逻辑段 ;逻辑段: 程序单位, 如主程序, 子程序, 数据区, 模块 ;段号: 每个进程有多个逻辑段，从0开始依次编

28、号(bin ho) ;逻辑段的段内地址从0开始编址 ;逻辑地址: (二维地址)第42页/共62页第四十三页，共63页。6.3.3 分段分段(fn dun)式存储式存储管理管理(Cont.)占用占用空闲空闲占用占用空闲空闲占用占用空闲空闲占用占用140 KB100 KB130 KB60 KB20 KB50 KB 0 KB内存空间划分(hu fn)调用X段入口E.访问(fngwn)DATA段A单元调用Y段入口F主程序段: main段号=0 050KB-1. F: 子程序段: Y段号=2 030KB-1 E： 子程序段: X段号=3 040KB-1 A: 子程序段: DATA段号=1 030KB-1

29、进程空间第43页/共62页第四十四页，共63页。6.3.3 分段分段(fn dun)式存储式存储管理管理(Cont.) 进程(jnchng)空间与内存空间对应关系: 进程(jnchng)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页第四十五页，共63页。6.3.3 分段分段(fn dun)式存储管理式存储管理(Cont.) 所需表目: 段表: 每个

30、进程(jnchng)一个。段号段号段首址段首址段长段长0120 KB50 KB1 390 KB30 KB2 480 KB30 KB3 810 KB40 KB 空闲表: 系统(xtng)一个 array of (addr,size)首地址首地址长度长度 0 KB120 KB 170 KB220 KB 420 KB 60 KB 510 KB300 KB第45页/共62页第四十六页，共63页。6.3.3 分段分段(fn dun)式存储管式存储管理理(Cont.) 所需寄存器: 段表首址寄存器一个(y ) : 段表长度(chngd)寄存器一个: 快表: 系统一组bl段号段号段首址段首址段长度段长度sb

31、l第46页/共62页第四十七页，共63页。逻辑地址 (s, d) 物理地址 (b+ d) : 由程序(chngx)确定逻辑地址 (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 分段分段(fn dun)式存储管式存储管理理(Cont.) 地址映射: : (s, d) ( b + d ) 第47页/共62页第四十八页，共63页。6.3.

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

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

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

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

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

37、共63页。 进程空间(kngjin)与内存空间(kngjin)对应关系: 6.3.4 段页式存储管理段页式存储管理(Cont.)第第 0 页页第第 1 页页第第 2 页页第第 0 页页第第 1 页页第第 2 页页第第 0 页页第第 1 页页第 0 段第 1 段第 2 段第第 11 页页第第 12 页页第第 28 页页第第 29 页页第第 84 页页第第 90 页页第第 96 页页第第 99 页页进程(jnchng)空间内存空间第56页/共62页第五十七页，共63页。 所需表目: 6.3.4 段页式存储管理段页式存储管理(Cont.) 段表: 每个进程(jnchng)一个。段号段号页表首址页表首址页表长度页表长度0 Sbll-1页表: 每个段一个(y )。页架号页架号f