搜索
第三章存储管理◆存储管理是指主存管理(外存管理见文件系统)，包括给进程分配主存片段，收回进程释放的主存片段，为分配出去的主存片段提供保护与共享，以及为作业提供一个虚拟的存储空间第三章存储管理3.1物理主存◆物理主存简称主存，它是计算机系统中的存储装置◆个人计算机上通常都配有128MB的RAM，除了操作系统代码占用一部分外，余者皆为用户区域，由用户进程瓜分存储管理3.2存储概念和虚存管理◆链接工作的实质是按照各个程序段之间的调用关系把各段的地址统一成从0开始的一维线性地址。链接既可在作业运行之前，也可在作业的程序段执行过程中依调用关系动态地进行。前者称为静态链接，由link程序完成；后者称为动态链接第三章存储管理3.2存储概念和虚存管理◆从0开始的指令地址和数据段地址组成作业的地址空间，它是逻辑上的，与主存地址毫不相干，因此称为虚拟空间或虚拟存储器。虚存的容量与主存大小无关，它是由计算机系统的地址结构和寻址方式确定的进程区共享区私用区系统区系统VxD及Windows系统DLL共享对象非系统DLL私用地址空间未用不可寻址4GB3GB4GB2GB4MB16KBFFFFFFFF512MB0000000000第三章存储管理3.2存储概念和虚存管理◆WindowsAPI控制进程的虚拟地址空间◆(1)私用堆用户使用HeapCreate()来产生私用堆空间HANDLEHeapCreate(flOptions,dwInitialSize,dwMaximumSize)DWORDflOptions;//堆的分配标记DWORDdwInitialSize;//堆的初始长度DWORDdwMaximumSize;//堆的最大长度第三章存储管理3.2存储概念和虚存管理◆(2)保留虚空间LPVOIDVirtualAlloc(lpvAddress,cbSize,fdwAllocationType,fdwProtect)LPVOIDlpvAddress;//该区虚地址DWORDcbSize;//该区域的长度DWORDfdwAllocationType;//该区域被指定的类型DWORDfdwProtect;//该区域的访问保护即访问权限第三章存储管理3.2存储概念和虚存管理◆(3)存储映射文件.最主要的虚存管理特性是通过存储映射支持共享虚存区域LPVOIDMapViewOfFile(hmapObect,fdwAccess,OffsetHigh,dwOffsetlow,cbMap)HANDLEhmapObject;//存储映射对象的句柄DWORDfdwAccess;//访问模式DWORDdwOffsetHigh;//32位地址的高位部分DWORDdwOffsetLow;//32位地址的低位部分DWORDcbMap;//映射的字节数第三章存储管理3.3地址变换◆物理主存空间地址是一维线性排列的，不妨记作M={0,1,2,…,2m-1},表示主存容量为2m。例如，当m=23时，主存的容量为8MB。虚存的一维线性空间和二维线性空间分别记为：V1={0,1,2,…,2v-1}V2={0段{0,1,2,…,n0},1段{0,1,2,…,n1},…，s段{0,1,2,…,ns}}第三章存储管理3.3地址变换◆所谓地址变换(又称地址映射)就是把多个V空间映射到M空间上去，或者说是把虚存地址变换成物理主存地址第三章存储管理3.4进程空间不大于主存空间的管理图3-2图3-2固定分区原理图第三章存储管理3.4.1固定分区◆由于进程空间(PS)的虚地址是从0开始递增编址的，因此装入模块在把它装入到分区时，必须把所有虚地址变换成从分区始址为起点的物理地址，其变换公式是：物理地址=虚地址+分区的始址第三章存储管理3.4.1固定分区◆静态重定位(staticaddressrelocation)◆动态重定位(dynamicaddressrelocation)如图3-3图3-3动态重定位过程示意图BR(基址寄存器)VR(有效地址寄存器)+物址1500物址1000虚址虚址500Load1,500┇┇┇┇┇虚址100虚址012345进程空间5001000第三章存储管理3.4.1固定分区◆固定分区的保护是指各进程空间在主存内运行时保证其每个物理地址都不超越自己的上下界限◆2种保护法（见图3-4）◆对上下界保护法满足：(UR)≤物理地址(LR)◆对基址/限长保护法满足：(BR)≤物理地址(BR)+(LR)基址寄存器BR1000限长寄存器LR1000上界寄存器UR被保护的区域被保护的区域主存下界寄存器LR10002000PSi基址/限长保护法(左)上下界保护法(右)第三章存储管理3.4.2可变分区◆根据进程空间的实际大小按需分配主存空间◆这种管理方法下，主存分区的个数，各区域的大小，在主存内活动的进程个数等都是随时间而变化的。所以，可变分区又称为动态分区图3-5图3-6PS5PS4PS3PS2PS10K主存需求量：50K70K30K100K60KOS估计运行时间：15820510FCFS40K256K图3-5可变分区管理初始状态示例40K100K200K230K256K(a)(b)(c)(d)(e)PS160K170KPS2100KPS2释放PS1PS330KPS330KPS330KPS330KPS330K分配PS4PS1PS470KPS1释放PS470K分配PS5PS470KPS550K第三章存储管理3.4.2.1数据结构◆有2种数据结构，即自由区表FBT(FreeBlockTable)和自由区链FBC(FreeBlockChain)供可变分区管理选用（图3-7）◆FBC的设计技巧在于，它利用自由区本身的空间记录自由区的大小及前后自由区的位置主存现状01260K40K30K170K26K230K大小始址已分60K170K60KFREE已分30K230K30K40K已分26KFREE26K170K已分始端指针当前指针尾端指针40K170K230KFREE结点(a)FBT(b)FBC第三章存储管理3.4.2.2分区分配算法◆首次适应法(FirstFit)找到第1个能满足长度要求的自由区，从中截取所需空间◆最佳适应法(BestFit)从自由区链中挑选能满足申请长度的最小自由区◆最坏适应法(WorstFit)总是挑选最大的自由区分割给申请者第三章存储管理3.4.2.3分配/回收程序与优先级考虑以首次适应算法和FBC结构为例，请求大小为x的自由存储区分配程序如下：PROCEDUREget_block(x,p);BEGINi:=1;WHILE(FBC[i].size0)AND(FBC[i].sizex)DOi:=i+1;IFFBC[i].size=0THENp:=0ELSEBEGIN存储管理3.4.2.3分配/回收程序与优先级考虑p:=FBC[i].adder;y:=FBC[i].size-x;IFy=THENBEGINFBC[i].size:=y;FBC[i].adder:=FBC[i].adder+x:ENDENDEND第三章第三章存储管理3.4.2.3分配/回收程序与优先级考虑◆回收过程(free_block)◆回收时要考虑回收的自由区是否与原自由区邻接图3-8回收区已分配已分配已分配回收区已分配已分配已分配回收区已分配已分配回收区第三章存储管理3.4.2.3分配/回收程序与优先级考虑◆get_block算法越快，系统的性能越好◆要研制快速get_block算法并且给予它以高的优先级以便尽快得到CPU响应第三章存储管理3.4.2.4地址变换与保护图3-9地址变换与保护虚地址CPU有效地址寄存器比较电路分区长度限长寄存器越界信号基址基址寄存器主存12345第三章存储管理3.4.2.5分区共享◆只要2个进程空间包含相同的虚地址(如Windows95)，物理主存分区即被2进程所共享。同理，允许多进程共享分区第三章存储管理3.4.3页式管理◆把进程空间划分成较小的片段(称为页面)，把主存也划分成较小的片段(称为块)，使页长等于块长，恰好1页能占用主存的1块（图3-10）3.4.3.1数据结构◆图3-11◆图3-12图3-10页式管理示意图进程空间分页页012块01234567主存分块图3-11虚空间表与各页表的关系图3-12主存空闲块表的数据结构N-1N-20^┅head(a)空闲块链00110(b)位示图图3-12主存空闲块表的数据结构状态┇┇┇进程号┇┇┇页号┇┇┇n=当前空闲块数块号01┇┇┇N-1(c)主存分块表第三章存储管理3.4.3.2主存的分配与回收PROCEDUREcmalloc(x,p);BEGINK:=x/Block_size;IFN=KTHENBEGINp:=getaPT;//申请一个页表区FORi=1TOKDOPT[i]:=getafreeblockEND//申请一个空闲块，把块号添入页表ELSEp:=0//分配失败，返回零END.其中x为进程所申请的主存空间大小，p为指向页表的指针。回收算法留给读者第三章存储管理3.4.3.3地址变换和保护措施◆图3-13◆图3-14图3-13页式地址变换控制寄存器有效地址寄存器页表长度页表始址pw┇B┇12345块号块Bw主存页表密码权限密钥现行PSW┄2┄正确访问：(密钥=密码）LOAD1块：不违反写保护STORE1块：不违反读保护非法访问STORE2块：违反写保护LOAD1块：密钥=密码块块块101112图3-14存储键保护法第三章存储管理3.4.3.4性能研究◆通常在CPU和主存之间增设高速小型的联想寄存器组，称之为“快表”，用它存放现行进程页表中最近常用的部分表目◆图3-15图3-15快表的使用页号┇块号┇pwBw页号块号第三章存储管理3.4.3.4性能研究◆设置快表后访问主存的流程如下：(1)CPU给出虚地址(2)按p值联查快表，若找到块号B则转④否则转③(3)按p值找页表得号B，把p指向的页表表目读入快表，置换“旧表目”(4)由B、w形成物理地址(5)访问主存(6)结束本次访问第三章存储管理3.4.3.5页面共享图3-16共享例程的页面附接的共享页进程乙的原有页进程甲的原有页附接的共享页主存主存块号块号页号块5（共享例程第0页）块7（共享例程第1页）块9（共享例程第2页）页表第三章存储管理3.4.4段式管理◆所谓“段(segment)”是指在逻辑上有完整意义的一组连续编址的代码◆段由程序员定义、能用段名·段内符号地址引用段内的信息◆经编译后，段名·段内符号地址转换成段号·段内位移第三章存储管理3.4.4段式管理◆每个分段必须分配在主存的一片地址连续的区域内，但各段之间不强求连续主存◆同一作业内的各段组成二维地址空间V2图3-17图3-17二维进程空间主段子段其他段01┋K-1001┋K-1i01┋K-1m-i┉S0SiSm-i第三章存储管理3.4.4.1段式管理的实现◆段式管理的存储分配的描述性程序如下：PROCEDUREcmalloc(k;s1,s2,…,Sk;p)；BEGINp=getaST;//获得一个存放段表的空间FORi:=1TokDOBEGINST[i]:=getaregion;IFnosuccessTHENp:=0ENDEND图3-18段式地址变换段表长度段表始址段号s段内位移w控制寄存器有效地址寄存器S段主存段长权限主存始址段号01sw段表ST物理地址第三章存储管理3.5进程空间大于主存空间◆有2种主要的方法能“扩充”主存，第1种是覆盖，第2种是虚拟存储器◆请求页式和请求段页式管理是实现虚存的2个具体方案3.5.1请求页式管理3.5.1.1请求页式的实现取下一个指令执行当前指令形成一维虚地址p,w访问主存，完成该指令以p查找页表、快表形成物理地址B,w该页在主存吗？不进入缺页中断处理(软件实现)保护现场淘汰主存中的一页主存中有空闲块吗？该页修改过吗？有从MBT取空闲块释放该页改从对换区调入所需页写回对换区调整页表，恢复现场无在未硬件实现图3-20请求