1、第三章第三章存储管理存储管理存储管理是指主存管理存储管理是指主存管理(外存管理见文件系统外存管理见文件系统)，包括给进程分配主存片段，收回进程释放的主包括给进程分配主存片段，收回进程释放的主 存片段，为分配出去的主存片段提供保护与共存片段，为分配出去的主存片段提供保护与共 享，以及为作业提供一个虚拟的存储空间享，以及为作业提供一个虚拟的存储空间 第三章第三章存储管理存储管理3.1 物理主存物理主存 物理主存简称主存，它是计算机系统中的存储装置物理主存简称主存，它是计算机系统中的存储装置 个人计算机上通常都配有个人计算机上通常都配有12128MB的的RAM，除了操作系，除了操作系 统代码占用一部
2、分外，余者皆为用户区域，由用户进统代码占用一部分外，余者皆为用户区域，由用户进 程瓜分程瓜分 存储管理存储管理3.2 存储概念和虚存管理存储概念和虚存管理 链接工作的实质是按照各个程序段之间的链接工作的实质是按照各个程序段之间的调用关系把各段的地址统一成从调用关系把各段的地址统一成从0开始的一维开始的一维线性地址。链接既可在作业运行之前，也可线性地址。链接既可在作业运行之前，也可在作业的程序段执行过程中依调用关系动态在作业的程序段执行过程中依调用关系动态地进行。前者称为静态链接，由地进行。前者称为静态链接，由link程序完程序完成；后者称为动态链接成；后者称为动态链接 第三章第三章存储管理存储
3、管理3.2 存储概念和虚存管理存储概念和虚存管理 从从0开始的指令地址和数据段地址组成作业开始的指令地址和数据段地址组成作业 的地址空间，它是逻辑上的，与主存地址的地址空间，它是逻辑上的，与主存地址 毫不相干，因此称为虚拟空间或虚拟存储毫不相干，因此称为虚拟空间或虚拟存储 器。虚存的容量与主存大小无关，它是由器。虚存的容量与主存大小无关，它是由 计算机系统的地址结构和寻址方式确定的计算机系统的地址结构和寻址方式确定的 进程区共 享 区私 用 区系 统 区系 统V xD及W indow s系 统D LL共 享 对 象非 系 统D LL私 用 地 址空 间未 用不 可 寻 址4GB3GB4GB2G
4、B4M B16K BFFFFFFFF512M B0000000000第三章第三章存储管理存储管理3.2 存储概念和虚存管理存储概念和虚存管理 Windows API控制进程的虚拟地址空间控制进程的虚拟地址空间 (1)私用堆私用堆 用户使用用户使用HeapCreate()来产生私用堆空间来产生私用堆空间 HANDLE HeapCreate(flOptions,dwInitialSize,dwMaximumSize)DWORD flOptions;/堆的分配标记堆的分配标记 DWORD dwInitialSize;/堆的初始长度堆的初始长度 DWORD dwMaximumSize;/堆的最大长度堆
5、的最大长度 第三章第三章存储管理存储管理3.2 存储概念和虚存管理存储概念和虚存管理 (2)保留虚空间保留虚空间 LPVOID VirtualAlloc(lpvAddress,cbSize,fdwAllocationType,fdwProtect)LPVOID lpvAddress;/该区虚地址 DWORD cbSize;/该区域的长度 DWORD fdwAllocationType;/该区域被指定的类型 DWORD fdwProtect;/该区域的访问保护即访问权限 第三章第三章存储管理存储管理3.2 存储概念和虚存管理存储概念和虚存管理 (3)存储映射文件存储映射文件.最主要的虚存管理特性
6、是最主要的虚存管理特性是 通过存储映射支持共享虚存区域通过存储映射支持共享虚存区域 LPVOID MapViewOfFile(hmapObect,fdwAccess,OffsetHigh,dwOffsetlow,cbMap)HANDLE hmapObject;/存储映射对象的句柄 DWORD fdwAccess;/访问模式 DWORD dwOffsetHigh;/32位地址的高位部分 DWORD dwOffsetLow;/32位地址的低位部分 DWORD cbMap;/映射的字节数 第三章第三章存储管理存储管理3.3 地址变换地址变换 物理主存空间地址是一维线性排列的，不妨记作物理主存空间地址
7、是一维线性排列的，不妨记作 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空间上去，或者说是把虚存地址变换成物理主空间上去，或者说是把虚存地址变换成物理主存地址存地址 第三
8、章第三章存储管理存储管理3.4 进程空间不大于主存空间的管理进程空间不大于主存空间的管理 图图3-2图图3-2 固定分区原理图固定分区原理图第三章第三章存储管理存储管理3.4.1 固定分区固定分区 由于进程空间由于进程空间(PS)的虚地址是从的虚地址是从0开始递增编址的，开始递增编址的，因此装入模块在把它装入到分区时，必须把所有因此装入模块在把它装入到分区时，必须把所有 虚地址变换成从分区始址为起点的物理地址，其虚地址变换成从分区始址为起点的物理地址，其 变换公式是变换公式是：物理地址物理地址=虚地址虚地址+分区的始址分区的始址 第三章第三章存储管理存储管理3.4.1 固定分区固定分区 静态重
9、定位静态重定位(static address relocation)动态重定位动态重定位(dynamic address relocation)如如图图3-3 图图3-3 动态重定位过程示意图动态重定位过程示意图BR(基址寄存器)VR(有效地址寄存器)+物址 1500物址 1000虚址虚址500Load 1,500虚址100虚址012345进程空间5001000第三章第三章存储管理存储管理3.4.1 固定分区固定分区 固定分区的保护是指各进程空间在主存内运行固定分区的保护是指各进程空间在主存内运行时保证其每个物理地址都不超越自己的上下界限时保证其每个物理地址都不超越自己的上下界限 2 2种保护
10、法（见种保护法（见图图3-43-4）对上下界保护法满足：对上下界保护法满足：(UR)(UR)物理地址物理地址(LR)LR)对基址对基址/限长保护法满足：限长保护法满足：(BR)(BR)物理地址物理地址(BR)+(LR)BR)+(LR)基址寄存器BR1000限长寄存器LR1000上界寄存器UR被保护的区域被保护的区域主存下界寄存器LR10002000PSi基址/限长保护法(左)上下界保护法(右)第三章第三章存储管理存储管理3.4.2 可变可变分区分区 根据进程空间的实际大小按需分配主存空间根据进程空间的实际大小按需分配主存空间 这种管理方法下，主存分区的个数，各区域的这种管理方法下，主存分区的个
11、数，各区域的大小，在主存内活动的进程个数等都是随时间而大小，在主存内活动的进程个数等都是随时间而变化的。所以，可变分区又称为动态分区变化的。所以，可变分区又称为动态分区 图图3-53-5 图图3-63-6PS5PS4PS3PS2PS10K主 存 需 求 量：50K70K30K 100K 60KOS估 计 运 行 时 间：15820510FCFS40K256K图图3-5 可变分区管理初始状态示例可变分区管理初始状态示例 40K100K200K230K256K(a)(b)(c)(d)(e)PS160K170KPS2100KPS2释放PS1PS330KPS330KPS330KPS330KPS330K
12、分配PS4PS1PS470KPS1释放PS470K分配PS5PS470KPS550K第三章第三章存储管理存储管理3.4.2.1 数据结构数据结构 有有2种数据结构，即自由区表种数据结构，即自由区表FBT(Free Block Table)和自由区链和自由区链FBC(Free Block Chain)供可变分供可变分区管理选用区管理选用（图图3-7）FBC的设计技巧在于，它利用自由区本身的空的设计技巧在于，它利用自由区本身的空间记录自由区的大小及前后自由区的位置间记录自由区的大小及前后自由区的位置 主存现状01260K40K30K 170K26K 230K大小 始址已分60K 170K60K F
13、REE已分30K 230K30K 40K已分26K FREE26K 170K已分始端指针当前指针尾端指针40K170K230KFREE 结点(a)FBT(b)FBC第三章第三章存储管理存储管理3.4.2.2 分区分配算法分区分配算法 首次适应法首次适应法(First Fit)找到第找到第1个能满足长度要求的自由区，从中截取所需空间个能满足长度要求的自由区，从中截取所需空间 最佳适应法最佳适应法(Best Fit)从自由区链中挑选能满足申请长度的最小自由区从自由区链中挑选能满足申请长度的最小自由区 最坏适应法最坏适应法(Worst Fit)总是挑选最大的自由区分割给申请者总是挑选最大的自由区分割
14、给申请者 第三章第三章存储管理存储管理3.4.2.3分配分配/回收程序与优先级考虑回收程序与优先级考虑 以首次适应算法和FBC结构为例，请求大小为x的自由存储区分配程序如下：PROCEDURE get_block(x,p);BEGIN i:=1;WHILE (FBCi.size0)AND (FBCi.size=THEN BEGIN FBCi.size:=y;FBCi.adder:=FBCi.adder+x:END END END 第三章第三章第三章第三章存储管理存储管理3.4.2.3分配分配/回收程序与优先级考虑回收程序与优先级考虑 回收过程回收过程(free_block)回收时要考虑回收的自
15、由区是否与原自由区邻接回收时要考虑回收的自由区是否与原自由区邻接 图图3-8回收区已分配已分配已分配回收区已分配已分配已分配回收区已分配已分配回收区第三章第三章存储管理存储管理3.4.2.3分配分配/回收程序与优先级考虑回收程序与优先级考虑 get_block算法越快，系统的性能越好算法越快，系统的性能越好 要研制快速要研制快速get_block算法并且给予它以算法并且给予它以高的优先级以便尽快得到高的优先级以便尽快得到CPU响应响应 第三章第三章存储管理存储管理3.4.2.4 地址变换与保护地址变换与保护图图3-9 地址变换与保护地址变换与保护虚地址CPU 有效地址寄存器比较电路分区长度限长
16、寄存器越界信号基 址基址寄存器主 存12345第三章第三章存储管理存储管理3.4.2.5 分区共享分区共享 只要只要2个进程空间包含相同的虚地址个进程空间包含相同的虚地址 (如如Windows 95)，物理主存分区即被，物理主存分区即被2 进程所共享。同理，允许多进程共享进程所共享。同理，允许多进程共享 分区分区 第三章第三章存储管理存储管理3.4.3 页式管理页式管理把进程空间划分成较小的片段把进程空间划分成较小的片段(称为页面称为页面)，把主存，把主存 也划分成较小的片段也划分成较小的片段(称为块称为块)，使页长等于块长，使页长等于块长，恰好恰好1页能占用主存的页能占用主存的1块块（图图3
17、-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=当前空闲块数当前空闲块数块号块号01N-1(c)主存分块表主存分块表第三章第三章存储管理存储管理3.4.3.2 主存的分配与回收主存的分配与回收PROCE
18、DURE cmalloc(x,p);BEGIN K:=x/Block_size;IF N=K THEN BEGIN p:=get a PT;/申请一个页表区申请一个页表区 FOR i=1 TO K DO PTi:=get a free block END/申请一个空闲块，把块号添入页表申请一个空闲块，把块号添入页表 ELSE p:=0/分配失败，返回零分配失败，返回零 END.其中其中x为进程所申请的主存空间大小，为进程所申请的主存空间大小，p为指向页表的指针。回收算法留给读者为指向页表的指针。回收算法留给读者 第三章第三章存储管理存储管理3.4.3.3 地址变换和保护措施地址变换和保护措施图
19、图3-13图图3-14图图3-13 页式地址变换页式地址变换控制寄存器控制寄存器有效地址寄存器有效地址寄存器页表长度页表长度 页表始址页表始址pwB12345块号块号块块Bw主存主存页表页表密码权限密码权限密钥密钥现行现行PSW2 正确访问：正确访问：(密钥密钥=密码）密码）LOAD1块：不违反写保护块：不违反写保护STORE1块：不违反读保护块：不违反读保护非法访问非法访问STORE2块：违反写保护块：违反写保护LOAD1块：密钥块：密钥=密码密码块块块块块块101112图图3-14 存储键保护法存储键保护法 第三章第三章存储管理存储管理3.4.3.4 性能研究性能研究通常在通常在CPU和主
20、存之间增设高速小型的联想寄和主存之间增设高速小型的联想寄 存器组，称之为存器组，称之为“快表快表”，用它存放现行进程页，用它存放现行进程页表表 中最近常用的部分表目中最近常用的部分表目 图图3-153-15图图3-15 快表的使用快表的使用 页号页号块号块号pwBw页号页号块号块号第三章第三章存储管理存储管理3.4.3.4 性能研究性能研究设置快表后访问主存的流程如下设置快表后访问主存的流程如下：(1)CPU(1)CPU给出虚地址给出虚地址 (2)(2)按按p p值联查快表，若找到块号值联查快表，若找到块号B B则转则转否则转否则转 (3)(3)按按p p值找页表得号值找页表得号B B，把，把
21、p p指向的页表表目读入快表，指向的页表表目读入快表，置换置换“旧表目旧表目”(4)(4)由由B、w形成物理地址形成物理地址 (5)(5)访问主存访问主存 (6)(6)结束本次访问结束本次访问 第三章第三章存储管理存储管理3.4.3.5 页面共享页面共享图图3-16 共享例程的页面共享例程的页面 附接的共享页附接的共享页进程乙的原有页进程乙的原有页进程甲的原有页进程甲的原有页附接的共享页附接的共享页主存主存主存主存块号块号块号块号页号页号块块5（共享例程第（共享例程第0页）页）块块7（共享例程第（共享例程第1页）页）块块9（共享例程第（共享例程第2页）页）页表页表第三章第三章存储管理存储管理3
22、.4.4 段式管理段式管理 所谓所谓“段段(segment)”是指在逻辑上有完整意义的一组是指在逻辑上有完整意义的一组 连续编址的代码连续编址的代码段由程序员定义、能用段由程序员定义、能用引用段引用段 内的信息内的信息经编译后，经编译后，转换成转换成第三章第三章存储管理存储管理3.4.4 段式管理段式管理每个分段必须分配在主存的一片地址连每个分段必须分配在主存的一片地址连 续的续的 区域内，但各段之间不强求连续主存区域内，但各段之间不强求连续主存 同一作业内的各段组成二维地址空间同一作业内的各段组成二维地址空间V2图图3-17图图3-17 二维进程空间二维进程空间 主主 段段子子 段段其他段其
23、他段01K-1001K-1i01K -1m-iS 0 S i S m-i 第三章第三章存储管理存储管理3.4.4.1 段式管理的实现段式管理的实现段式管理的存储分配的描述性程序如下：PROCEDURE cmalloc(k;s1,s2,Sk;p)；BEGIN p=get a ST;/获得一个存放段表的空间 FOR i:=1 To k DO BEGIN STi:=get a region;IF no success THEN p:=0 END END 图图3-18 段式地址变换段式地址变换段表长度段表始址段号s 段内位移w控制寄存器有效地址寄存器S 段主存段长权限 主存始址段号01sw段表ST物理
24、地址第三章第三章存储管理存储管理3.5 进程空间大于主存空间进程空间大于主存空间有有2种主要的方法能种主要的方法能“扩充扩充”主存，第主存，第1种种 是覆盖，第是覆盖，第2种是虚拟存储器种是虚拟存储器 请求页式和请求段页式管理是实现虚存请求页式和请求段页式管理是实现虚存 的的2个具体方案个具体方案 3.5.1 请求页式管理请求页式管理3.5.1.1 请求页式的实现请求页式的实现取下一个指令执行当前指令形成一维虚地址访问主存，完成该指令以p查找页表、快表形成物理地址该页在主存吗？不进入缺页中断处理(软件实现)保护现场淘汰主存中的一页主存中有空闲块吗？该页修改过吗？有从MBT取空闲块释放该页改从对
25、换区调入所需页写回对换区调整页表，恢复现场无在未硬件实现图图3-20 请求页式下指令执行过程请求页式下指令执行过程 012345678910111231P R/W U/SAD 1231 位为主存块号P标记位，该页在主存置标记位，该页在主存置1，否则置，否则置0 D修改标记位，对该页内容修改时置修改标记位，对该页内容修改时置1，否则置，否则置0 A引用标记位，任何一次对该页的引用，包括读、写、引用标记位，任何一次对该页的引用，包括读、写、执行，都置执行，都置1 U/S“用户用户/管理员管理员”标记位标记位 R/W权限标记位权限标记位 第三章第三章存储管理存储管理3.5.1.1 请求页面实现请求页
26、面实现根据根据MBT可以回答可以回答“主存有空闲块吗主存有空闲块吗”一条指令的执行有可能产生多次缺页中断一条指令的执行有可能产生多次缺页中断 对换区管理问题对换区管理问题 第三章第三章存储管理存储管理3.5.1.2 页面置换算法页面置换算法 FIFO(First In First Out)即先进先出算法即先进先出算法 页面访问序列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 页面失效()：图3-22 当M=3时，FIFO算法示例 但但FIFO有异常现象有异常现象(Beladys anomaly)，即，即M增加时增加时 不能下降反而增加不能下降反而增加 第三章
27、第三章存储管理存储管理3.5.1.2 页面置换算法页面置换算法 OPT(Optimal)即最优置换算法即最优置换算法 NUR(Not Used Recently)算法算法 LRU(Least Recently Used)算法算法 记时法记时法 寄存器法寄存器法 第三章第三章存储管理存储管理3.5.1.3 性能研究性能研究 M与与 的关系的关系 页面尺寸与页面尺寸与 的关系的关系 与主存有效存取时间的关系与主存有效存取时间的关系 EAT页面传输时间页面传输时间ta 第三章第三章存储管理存储管理3.5.1.3 性能研究性能研究仅在本进程空间发生的颠簸称局部颠簸仅在本进程空间发生的颠簸称局部颠簸当系
28、统内进程总数超过一定数额时，当系统内进程总数超过一定数额时，CPU的利的利用率反而急剧下降用率反而急剧下降系统进入颠簸系统进入颠簸 程序的局部性程序的局部性 第三章第三章存储管理存储管理3.5.1.3 性能研究性能研究工作集工作集WS(working set)是指在进程运行中距时刻是指在进程运行中距时刻ti最最近的近的次访问主存所涉及到的那些页面的集合次访问主存所涉及到的那些页面的集合 2 6 1 5 7 7 7 7 5 1 6 2 3 6 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2=10=10t1t2W S1=1,2,5,6,7=10W S2=3,4=10图图3-23 工作集
29、工作集第三章第三章存储管理存储管理3.5.1.4 对换区管理对换区管理磁盘页表磁盘页表对换文件对换文件 第三章第三章存储管理存储管理3.5.1.5 页面共享页面共享图图3-24 请求页市式下的页面共享请求页市式下的页面共享12100其它其它共享计数共享计数 块号块号12100其它其它共享计数共享计数 块号块号进程甲的页表进程甲的页表进程乙的页表进程乙的页表共享页共享页主页主页块号块号100第三章第三章存储管理存储管理3.5.1.6 实例实例-UNIX系统系统V的存储管理的存储管理 图图3-25 图图3-26 图图3-25 虚存布局、地址结构与页表项格式虚存布局、地址结构与页表项格式0p0区1G
30、230p1区1G2230系统空间1G虚存页表区3230未用空间1G4230进程 pi的 p0区进程 pi的 p1区OS 本身的代码与数据进程pi的p0区页表进程pi的p1区页表其它未用319 80页号 p页内位移 w地址结构3126200V P R O T M 主存块始址 B页表表项格式其中V=0该页不在主存V=1该页在主存PROT 为访问权限M=0该页未修改M=1该页已修改过第 2125 位为专用对换区第 020 为主存块号始址，但当V=0 时用于查找该页在外存的位置(不一定是外存地址)注意，页表格式与 Windows 95 不同图图3-26 主存布局主存布局系统数据系统数据系统页表系统页表
31、进程进程i的的P0区页表区页表进程进程i的的P1区页表区页表主存位示图主存位示图进程进程0的页表的页表进程进程0的栈区的栈区进程空间进程空间主存空闲快主存空闲快I/O专用专用第三章第三章存储管理存储管理3.5.2 请求段页式管理请求段页式管理3.5.2.1 实现原理实现原理虚拟地址是二维的：图图3-27 请求段页式管理的地址变换请求段页式管理的地址变换 进程登记表当前进程段 表段号 其它 页表始址 页表长度 扩充 状态 共享段入口进程号 父进程号 段表始址 段表长度主存块号 外存地址 修改 状态块长块始址物理地址w虚地址段号S页号p页内位移w页 表p第三章第三章存储管理存储管理3.5.2.1
32、实现原理实现原理越界中断处理越界中断处理 越权中断处理越权中断处理 缺页中断处理缺页中断处理 链接中断处理链接中断处理 链接中断处理链接中断处理 第三章第三章存储管理存储管理3.5.2.2 分段动态链接分段动态链接 MULTICS方法方法（图）（图）图图3-28 MULTICS的动态链接的动态链接 load 1 3 100L 3 104load 1 3 1000 5 120M段段 内部段号内部段号3(编译后链接前编译后链接前)内部段号内部段号3（链接后）（链接后）间接字间接字链接链接Y:1 2 3 4 50Y:1 2 3 4 51201485装入装入X段（未入主存）段（未入主存）内部段号内部段
33、号5（已入主存）（已入主存）3 5段号段号段表段表第三章第三章存储管理存储管理3.5.2.2 分段动态链接分段动态链接动态链接库动态链接库(DLL)机制机制 动态链接程序分成链接和装入两个步骤动态链接程序分成链接和装入两个步骤 链接步骤中扫描链接步骤中扫描DLLDLL的输入库，并把一个目标模块名的输入库，并把一个目标模块名和一个数字入口点嵌入到用户的可执行文件中和一个数字入口点嵌入到用户的可执行文件中 在装入步骤中，操作系统负责用那些在函数调用中在装入步骤中，操作系统负责用那些在函数调用中能有效地使用的地址替换这些引用能有效地使用的地址替换这些引用 第三章第三章存储管理存储管理3.5.2.3 分段共享分段共享图图3-29 甲进程的甲进程的5号段、乙进程的号段、乙进程的3号段共享号段共享X段段 05M段：段：进程甲的段表进程甲的段表X段的页表段的页表03N段：段：进程乙的段表进程乙的段表
