工学06第六章-存储管理

第六章存储管理6.1存储管理功能6.2内存资源管理6.3存储管理方式6.4外存空间管理6.5虚拟存储系统6.1存储管理功能

内存/外存的管理;

内/外存管理采用相同或相似的管理技术；功能存储分配存储共享存储保护存储扩充地址映射6.1存储管理功能(Cont.)

存储分配/去配记录内/外存资源的使用情况:分配表、空闲表;分配/去配对象内存、外存(相同方法);分配/去配时刻进程创建、撤销、交换、长度变化(栈溢出,execl)

存储共享多个进程共用内存的相同区域;(物理空间有相交的部分)

目的：节省内存、相互通讯;

内容：代码、数据。存储保护防止地址越界;

防止操作越权。存储扩充内存、外存结合，虚拟存储体系;

速度接近内存，容量相当外存。地址映射逻辑地址=>物理地址硬件支持基址寄存器(base)、限长寄存器(limit)、快表；使用上述寄存器完成地址映射过程；不能正常完成地址映射时产生中断。6.1存储管理功能(Cont.)6.2内存资源管理

6.2.1内存分区分区时刻静态分区:系统初始化时分;动态分区:申请时分。分区大小等长分区:2i异长分区:依程序,程序单位,对象大小。通常作法静态+等长(页式、段页式);动态+异长(段式、界地址)。6.2.2内存分配

静态等长分区的分配分配策略:分配几个等长区域;

分区表示:

字位映象图;

空闲页面表;

空闲页面链。

动态异长分区的分配最先适应(FirstFit);

最佳适应(BestFit);

最坏适应(WorstFit)。6.2.2.1静态等长分区的分配

字位映象图(bitmap)用一个bit代表一页状态，0:空闲，1:占用。100………1……..10第0页第1页第2页………第k页第n-1页第n页分配:按页号从小到大查字位图,找到为0的位改为1，返回页号。去配:把页号对应的bit置为0。

空闲页面表:首页面号页面个数…………1204………………占用120页121页122页123页占用……内存分配/去配:需修改空闲页面表。特点:可以分配连续页面。

DMA要求6.2.2.1静态等长分区的分配(Cont.)空闲页面表结构6.2.2.1静态等长分区的分配(Cont.)

空闲页面链:占用占用占用head空闲页面链结构分配/去配:调整链表。特点:节省空间。

(不适合外存管理)6.2.2.2动态异长分区的分配常用于界地址存储管理和段式存储管理。空闲区首址空闲区长度……addresssize………………0空闲区表

初始时一个连续空闲区;

空闲区首址由小到大;

长度=0为表尾。分配:

按分配策略调整表项;去配:把去配的空间插入表中,

可能需要合并空闲区。6.2.2.2动态异长分区的分配(Cont.)最先适应算法(FirstFit):空闲区首址空闲区长度128642563210242560…………空闲区表空闲区:首址递增排列；申请:取第一个可满足区域;优点:尽量使用低地址空间,高区保持大空闲区域。缺点:可能分割大空闲区。

如申请32将分割第一个区域。6.2.2.2动态异长分区的分配(Cont.)最佳适应算法(BestFit):空闲区首址空闲区长度256321286410242560…………空闲区表空闲区:空闲区长度递增排列;申请:取最小可满足区域;优点:尽量使用小空闲区,保持大空闲区域。缺点:容易形成碎片fragment。

如申请30将留下长度为2的空闲区。6.2.2.2动态异长分区的分配(Cont.)最坏适应算法(WorstFit):空闲区首址空闲区长度102425612864256320…………空闲区表空闲区:空闲区长度递减排列。申请:取最大可满足区域。优点:防止形成碎片。缺点:分割大空闲区。例:UNIX存储分配－FirstFit

(见12章p286-12.4.2)最先适应算法，空闲区首址递增排列defineCMAPSIZ100defineSMAPSIZ100structmap//存储资源表结构{char*m_size;char*m_addr;};structmapcoremap[CMAPSIZ];//内存资源表structmapswapmap[SMAPSIZ];//外存资源表intmalloc(mp,size)

//存储分配函数structmap*mp;{registerinta;registerstructmap*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)//当前块＝sizedo{bp++;//do循环压缩size=0的存储表项

(bp-1)->m_addr=bp->m_addr;}while((bp-1)->m_size=bp->m_size);return(a);//分配成功，返回分配存储块的首地址

}return(0);//分配不成功，返回0}存储分配函数:mp=coremap内存分配swapmap外存分配mfree(mp,size,aa)structmap*map;{registerstructmapbp;registerintt,a;a=aa;for(bp=mp;bp->m_addr<=a&&bp->m_size!=0;bp++);if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_size==a)

{(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释放外存

}else//是存储表项的第一项或不与前项存储块相连

{if(a+size==bp->m_addr&&bp->m_size)//与后项存储块相连?{bp->m_addr-=size;//与后项存储块合并。

bp->m_size+=size;}elseif(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=t);}}存储释放算法(Cont.)6.2.3碎片与紧凑紧凑(Compaction):

移动占用区域，使所有空闲区域连成一片(开销很大)。0KB操作系统空间20KB20KB空闲区域10KB30KB进程p1空间30KB60KB空闲区域10KB70KB进程p1空间20KB90KB空闲区域10KB紧凑前0KB操作系统空间20KB20KB进程p1空间30KB50KB进程p1空间20KB70KB空闲区域30KB紧凑后6.3存储管理方式无虚拟功能的存储管理方式：界地址管理方式(一维地址)

页式管理方式(一维地址)

段式管理方式(二维地址)

段页式管理方式(二维地址)6.3.1界地址管理方式单对界存储管理方式:(首地址,长度)基本原理⒈内存空间划分:动态异长；⒉进程空间划分:一个进程一个区域,逻辑地址0～L-1;⒊进程空间与内存空间对应关系(可以浮动):0:L-1:b:b+L-1:L…………进程空间内存空间6.3.1界地址管理方式(Cont.)⒋所需表目：

⑴内存分配表:在PCB中;

⑵空闲区域表:arrayof(addr,size)。⒌所需寄存器：

⑴基址寄存器b:保存运行进程起始地址;

⑵限长寄存器l:保存运行进程长度。6.3.1界地址管理方式(Cont.)⒍地址映射：σ:(a)→(b+a)∪{Ω}0:L-1:b:b+L-1:L…………进程空间内存空间限长寄存器首址寄存器Lb…………<逻辑地址>……………………<物理地址>…………a越界中断CMP+b+a步骤:

⑴由程序确定逻辑地址a;

⑵a与L比较判断是否越界，不满足:0≤a≤L-1，越界;

⑶a与b相加得到物理地址。6.3.1界地址管理方式(Cont.)

双对界代码区域:首址寄存器、限长寄存器;

数据区域:首址寄存器、限长寄存器;UNIX:代码I空间、数据D空间。交换与重定位

交换:换入(swap-in)/换出(swap-out);

滚入(roll-in)/滚出(roll-out);

交换的基本单位为整个进程。

可重定位程序:程序编址与内存存放位置无关;

浮动程序:满足重定位要求的程序,如0起始编址。

重定位:换入程序需重定位。6.3.1界地址管理方式(Cont.)

覆盖技术:

将较大程序装入较小进程空间的技术,

最大限度提高内存利用率。只将全局代码和数据静态装入内存,

其它部分动态装入;

后装入的成分重复使用先装入成分所使用的存储区,即覆盖先装入的成分;

用户编写覆盖驱动程序,无需操作系统支持。6.3.1界地址管理方式(Cont.)例[覆盖技术]：四遍扫描的编译程序符号表公共例程覆盖驱动程序覆盖区50KB…………内存Pass130KBPass250KBPass425KBPass340KB6.3.2分页式存储管理页式存储管理(paging):一个进程占多个等长、连续内存空间;无碎片。6.3.2.1基本原理⒈内存空间划分:页架:静态等长,长度2i;

页架号:所有页架由0开始依次编号;

页内地址:页架内单元由0开始依次编址。例如:内存容量为2n,则共有2n-i个页架。第k个页架的起始地址为k×2i。6.3.2分页式存储管理(Cont.)0×2i第0页2i1×2i第1页2i…………k×2i第k页2i…………(2n-i-1)×2i第2n-i－1页2i内存空间划分n位一维地址码=页架首址+页内地址=页架号×2i+页内地址=页内地址页架号i位n-i位物理地址6.3.2分页式存储管理(Cont.)⒉进程空间划分:静态等长，2

i,称为一个页面。0×2i第0页2i1×2i第1页2i…………k×2i第k页2i…………(l-1)×2i第l－1页2i进程空间划分=逻辑页首址+页内地址=逻辑页号×2i+页内地址=页内地址逻辑页号i位n-i位逻辑地址6.3.2分页式存储管理(Cont.)⒊进程空间与内存空间对应关系:页面连续,页架可能不连续。第3页第2页第1页第0页进程空间……第79页第78页……第47页……第18页……内存空间6.3.2分页式存储管理(Cont.)⒋所需表目

页表:

每个进程一个。页架号18477978逻辑页号0123

总页表:

系统一个,

记录页架使用情况

两种结构：表、链。⒌所需寄存器

页表首址寄存器:

系统一个。b

页表长度寄存器:

系统一个。l

快表:

系统一组。逻辑页号页架号…………pf…………l=46.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)

。页表长度寄存器页表首址寄存器lb页架号……f……逻辅页号0…p…l-1进程标识pid……页表长度l页表首址b……页表进程控制块PCB逻辑页号页架号…………pf…………快表TLBdp页内地址页号

逻辑地址df页内地址页架号物理地址页式存储管理地址映射快表未查到p6.3.2分页式存储管理(Cont.)页表长度寄存器页表首址寄存器lb页架号……f……0逻辑页号l-1…p…页表进程控制块PCB逻辑页号页架号…………pf…………快表TLBdp页内地址页号

逻辑地址df页内地址页架号物理地址Cmpp:lb+p页式存储管理地址映射fp6.3.2分页式存储管理(Cont.)进程标识pid……页表长度l页表首址b……有效访问时间

EffectiveAccessTime:EAT6.3.2分页式存储管理(Cont.)EAT=快表命中率×(快表访问时间+内存访问时间)+快表不中率×(快表访问时间+2×内存访问时间)ns例：快表命中率98％，快表访问时间20ns，内存一次访问时间100ns，则EAT=98％(20+100)+2％(20+200)=122ns6.3.2.2多级页表提出背景内存空间成倍增长,进程虚拟空间成倍增加。单级页表需要很大连续内存空间

例如:

232位进程地址空间(4G),页长占212位(4K),

进程拥有的页面最多可达220,即页表最多可达220个表项。多线程设计导致进程虚拟空间不连续(空洞hole)

页表所占内存空间浪费。解决策略:

减少页表所占内存空间。二级或多级页表:外页表,内页表栈的预留空间(没有页架相对应)6.3.2分页式存储管理(Cont.)6.3.2分页式存储管理(Cont.)……01102320……95102……309498……512010230102301023…………20……95……102……309……498……512……OutertablePagetableMemory外页表对应hole的表项没有对应的内页表，访问hole表项动态建立内页表二级页表6.3.2分页式存储管理(Cont.)二级页表的地址映射:pipjd

Logicaladdressstructure:10bits10bits12bitsPageoffsetPi:outerpagetableindex;Pj:pagetabledisplacement.Pagenumber

addresstranslationscheme:p1p2dLogicaladdress……Outertablep1f……Pagetablep2Physicaladdress……memoryd6.3.2分页式存储管理(Cont.)

采用二级页表结构时,逻辑地址由外层页号pi,外层页内地址pj,页内地址d三部分构成。若给定一个逻辑地址空间的地址为A,系统页面大小为L,页表项的长度为N,则pi,pj和d的计算公式如下：pi=int[int[A/L]/N]

pj=int[A/L]modN

d=AmodL

对前述二级页表结构,L=212,N=2106.3.2分页式存储管理(Cont.)4级页表有效访问时间EAT=快表命中率

(快表访问时间+内存访问时间)+

快表不中率(快表访问时间+5内存访问时间)ns例[4级页表]:

快表命中率98％，快表访问时间20ns，内存访问时间100ns，则

EAT=98%(20+100)+2%(20+500)ns=128ns6.3.2.3反置页表

传统页表面向进程空间每个进程逻辑页面有一表项;

当进程空间很大时,页表很大。

反置页表面向内存空间系统只设置一个反置页表,为所有进程所用。反置页表大小固定;

每个内存页架一个表项,表项序号即为页架号;invertedpagetable6.3.2.3反置页表(Cont.)反置页表工作原理:

……<内存访问>……pidpd逻辑地址pidp程序0f…fd物理地址反置页表……………………d

f个页架d物理内存速度问题

反置页表查找由表头起始,平均为表长度的一半;

速度慢。解决方案在反置页表前增加一级杂凑表;

逻辑页号为关键字，通过Hash函数确定进程反置页表首项位置。

查找杂凑表与反置页表至少需要两次访问内存;

为进一步提高速度，快表缓冲。6.3.2.3反置页表(Cont.)6.3.3分段式存储管理

segmentation6.3.2.1基本原理⒈内存空间划分:动态划分成异长区域，每个区域称作一个物理段;物理段:段首址,段内地址(由0开始编址);物理地址:段首址+段内地址(一维地址);段号段内地址⒉进程空间划分:静态划分成异长区域，每个区域称作一个逻辑段;逻辑段:程序单位,如主程序,子程序,数据区,模块;段号:每个进程有多个逻辑段，从0开始依次编号;逻辑段的段内地址从0开始编址;逻辑地址:(二维地址)6.3.3分段式存储管理(Cont.)占用空闲占用空闲占用空闲占用140KB100KB130KB60KB20KB50KB

0KB内存空间划分……调用[X]段入口E访问[DATA]段A单元……调用[Y]段入口F……主程序段:[main]段号=0

050KB-1......

……F:…………子程序段:[Y]段号=2

030KB-1…

……E：…………子程序段:[X]段号=3

040KB-1…

……A:…………子程序段:[DATA]段号=1

030KB-1…进程空间6.3.3分段式存储管理(Cont.)⒊进程空间与内存空间对应关系:进程P段[main]段号=0进程P段[data]段号=1进程P段[Y]段号=2进程P段[X]段号=3

050KB-1

0

0

030KB-140KB-130KB-1……………………………………………………120KB390KB480KB810KB50KB30KB30KB40KB120KB220KB60KB300KB6.3.3分段式存储管理(Cont.)⒋所需表目:⑴段表:每个进程一个。段号段首址段长0120KB50KB1

390KB30KB2

480KB30KB3

810KB40KB⑵空闲表:系统一个arrayof(addr,size)首地址长度

0KB120KB

170KB220KB

420KB

60KB

510KB300KB6.3.3分段式存储管理(Cont.)⒌所需寄存器:⑴段表首址寄存器一个:⑵段表长度寄存器一个:⑶快表:系统一组bl段号段首址段长度………………sb’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’比较,不满足:0≤d≤l’-1,越界;⑷b’+d得物理地址。6.3.3分段式存储管理(Cont.)⒍地址映射::(s,d)(b’+d)∪{}6.3.3分段式存储管理(Cont.)段首址段长…………b’l’…………段号0…s…l-1进程标识pid……段表长度l段表首址b……段表进程控制块PCB段号段首址段长…………sb’l’…………

快表TLB段式存储管理地址映射偏移段号

逻辑地址dscmp物理地址b’+d+段表长度reg段表首址regbl若快表查不到s6.3.3分段式存储管理(Cont.)段首址段长…………b’l’…………段号0…s…l-1进程标识pid……段表长度l段表首址b……段表进程控制块PCB段号段首址段长…………sb’l’…………

快表TLB段式存储管理地址映射sb’l’偏移段号

逻辑地址dscmp物理地址b’+d+段表长度reg段表首址regbl+cmp6.3.3分段式存储管理(Cont.)

6.3.2.2段的共享与保护⒈段的共享:不同进程的段号Spi和Spj对应同一个段的段首址和段长即可实现不同进程对段的共享。段首址段长度…………b’l’…………P1段表……si段号段首址段长度…………b’l’…………P2段表……sj段号……共享段……b’:l’内存空间6.3.3分段式存储管理(Cont.)共享段表:系统1个,记录所有共享段。main1子程序X子程序Y……datamain2data子程序Y子程序X段长度首址P10段号P21234段长度首址0段号123段表段名共享计数段长度段首址其它X2Y2data2共享段表●●●main1XDataYmain2●●●主存6.3.3分段式存储管理(Cont.)⒉段的保护:不同进程对共享段的访问权限不同，需要在段表中加上访问权限。段首址段长度访问权限RWE…………………………b’l’101…………………………段表的改进……s段号段号段首址段长度访问权限RWE…………………………sb’l’101…………………………快表的改进页式管理段式管理一维地址空间二维地址空间页是物理单位段是逻辑单位页的大小固定段的大小可变对用户透明对用户可见无碎片有碎片通常不共享便于共享、保护页式管理和段式管理的比较:6.3.3分段式存储管理(Cont.)

段式优于页式便于共享和保护

页式优于段式消除“碎片”问题段页式：结合二者优点每个进程包含若干段；每个段包含若干页。6.3.4段页式存储管理segmentationwithpaging6.3.4段页式存储管理(Cont.)6.3.4.1基本原理

⒈内存空间划分:(同页式)静态等长,2i,称为一页架;

物理地址

==(f,d)。页内地址页架号n-i位i位⒉进程空间划分:

一个进程若干个段;

一个段若干个页;

逻辑地址==(s,p,d)。段号页内地址逻辑页号i位j位n-i-j位⒊