第五章-存储管理-选修

1、第第5章章 存存 储储 管管 理理图图5-1 内存在计算机系统中的地位内存在计算机系统中的地位n 引引 言言n 分分 区区 法法n 分分 页页 技技 术术n 虚拟存储器及请求分页技术虚拟存储器及请求分页技术n 页面置换算法页面置换算法本章内容提要本章内容提要1 引引 言言n内存（内存（Main Memory或或Primary Memory或或Real Memory）也称主存。）也称主存。n指指CPU能直接存取指令和数据的存储器，能直接存取指令和数据的存储器，统一编址。统一编址。5.1.1 用户程用户程序的执行序的执行图图5-2 用户程序用户程序的机内处理过程的机内处理过程5.1.1 用户程序的

2、主要处理阶段用户程序的主要处理阶段1编辑阶段：编辑源代码。编辑阶段：编辑源代码。2编译阶段：源代码转换为二进制指令构成的编译阶段：源代码转换为二进制指令构成的目标代码模块。目标代码模块。3链接阶段：将目标模块及所需的库函数链接链接阶段：将目标模块及所需的库函数链接形成一个可执行程序。形成一个可执行程序。4装入阶段：将可执行程序装入内存某地址空装入阶段：将可执行程序装入内存某地址空间。间。5运行阶段：从第一条指令开始运行程序。运行阶段：从第一条指令开始运行程序。 内存的使用内存的使用u每个目标模块指令代码都以每个目标模块指令代码都以0为基地址顺序为基地址顺序编址，称为相对地址或逻辑地址。编址，称

3、为相对地址或逻辑地址。u内存中物理存储单元统一由基地址内存中物理存储单元统一由基地址0开始顺开始顺序编址，称为绝对地址或物理地址。序编址，称为绝对地址或物理地址。u可执行程序各条指令需要进行地址转换方可执行程序各条指令需要进行地址转换方能正确执行。能正确执行。5.1.2 重定位重定位n程序逻辑地址的范围为逻辑地址空间。程序逻辑地址的范围为逻辑地址空间。n可执行程序存放的内存存储单元的范围可执行程序存放的内存存储单元的范围为物理地址空间。为物理地址空间。n用户程序和数据装入内存时，需对目标用户程序和数据装入内存时，需对目标程序中的地址进行修改。把逻辑地址转程序中的地址进行修改。把逻辑地址转变为物

4、理地址的过程称做地址重定位变为物理地址的过程称做地址重定位 。地址映射地址映射Load A 1200 3456 。 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=100010001静态重定位静态重定位n目标程序装入内存时，由装入程序对目标目标程序装入内存时，由装入程序对目标程序中的指令地址、数据地址进行修改，程序中的指令地址、数据地址进行修改，完成逻辑地址到物理地址的转换。完成逻辑地址到物理地址的转换。图图5-4 静态重定位示意图静态重定位示意图静态重定位技术分

5、析静态重定位技术分析n优点：不需要硬件的支持。优点：不需要硬件的支持。 n缺点：缺点：n程序必须占用连续的内存空间程序必须占用连续的内存空间n程序装入后不能移动位置程序装入后不能移动位置n不支持虚拟存储及其交换技术不支持虚拟存储及其交换技术 2动态重定位动态重定位n在每条指令执行时，对所访问的内存进行在每条指令执行时，对所访问的内存进行地址重定位。地址重定位。n硬件地址转换机构实现动态重定位。硬件地址转换机构实现动态重定位。图图5-5 动态重定位示意图动态重定位示意图动态地址重定位优点：动态地址重定位优点：n程序的内存空间动态可变，当程序移程序的内存空间动态可变，当程序移到另一个空间时，修改寄

6、存器到另一个空间时，修改寄存器BRBR的值的值n一个程序不必占用连续内存空间一个程序不必占用连续内存空间n可以部分装入程序运行可以部分装入程序运行动态地址重定位的代价：动态地址重定位的代价：n需要硬件的支持。需要硬件的支持。n实现存储管理的软件算法较为复杂。实现存储管理的软件算法较为复杂。5.2 分分 区区 法法n支持多道程序运行的一种存储管理方式。支持多道程序运行的一种存储管理方式。n把整个内存划分为若干大小不等的区域，把整个内存划分为若干大小不等的区域，操作系统占用一个区域，其它区域供用操作系统占用一个区域，其它区域供用户进程共享，每个进程占用一个分区，户进程共享，每个进程占用一个分区，这

7、种方法称为分区存储管理。这种方法称为分区存储管理。n分区的划分：分区的划分：n固定分区固定分区n动态分区动态分区 5.2.1 固定分区法固定分区法n内存中分区个数、分区大小固定内存中分区个数、分区大小固定n每个分区装入一个进程每个分区装入一个进程5.2.2 动态分区法动态分区法1分区的分配分区的分配n进程进入内存建立分区，大小适应进程进程进入内存建立分区，大小适应进程的需要。这种技术称为动态分区法。的需要。这种技术称为动态分区法。图图5-7 MVT的内存分配和进程调度情况的内存分配和进程调度情况3动态分区分配算法动态分区分配算法（1）最先适应算法）最先适应算法n空闲表按内存地址顺序排列空闲表按

8、内存地址顺序排列（2）最佳（坏）适应算法）最佳（坏）适应算法n空闲表按空闲块大小的增量形式排列空闲表按空闲块大小的增量形式排列（3）循环适应算法）循环适应算法n最先适应算法的变种。从上次找到的可用最先适应算法的变种。从上次找到的可用分区的下一个空闲分区开始查找，顺序选分区的下一个空闲分区开始查找，顺序选择满足要求的第一个空闲分区。择满足要求的第一个空闲分区。 5.3 可重定位分区分配可重定位分区分配5.3.1 碎片问题碎片问题n内存中尺寸太小、无法利用的小分区称内存中尺寸太小、无法利用的小分区称做做“碎片碎片”。n固定分区法会产生内部碎片。动态分区固定分区法会产生内部碎片。动态分区会产生外部碎

9、片会产生外部碎片.图图5-9 分配分配16 KB内存块之前和之后的内存配置内存块之前和之后的内存配置5.3.1 碎片问题碎片问题n紧缩的时机紧缩的时机n进程结束、释放所占用的分区时（空闲区有进程结束、释放所占用的分区时（空闲区有可能相邻）可能相邻）n在分配进程的分区时（空闲区有可能不够）在分配进程的分区时（空闲区有可能不够）5.3.2 紧缩紧缩n移动某些已分配区，使所有进程的分区紧邻的技术。移动某些已分配区，使所有进程的分区紧邻的技术。图图5-10 可重定位分区的紧缩可重定位分区的紧缩5.3.4 可重定位分区法优缺点可重定位分区法优缺点n优点优点n可以消除碎片，能够分配更多的分区，有助可以消除

10、碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。于多道程序设计，提高内存的利用率。n缺点缺点n紧缩技术花费紧缩技术花费CPU时间时间5.5 分分 页页 技技 术术5.5.1 分页存储管理的基本概念分页存储管理的基本概念把用户程序按逻辑页划分成大小相等的部把用户程序按逻辑页划分成大小相等的部分，称为页（分，称为页（pagepage） 。从。从0 0开始编制页号，开始编制页号，页内地址从页内地址从0 0开始编址。开始编址。（1）逻辑地址空间）逻辑地址空间分页分页（2）内存地址空间）内存地址空间分块分块n页（或块）大小由硬件（系统）确定页（或块）大小由硬件（系统）确定（3）逻辑地址表

11、示）逻辑地址表示图图5-14 分页技术的地址结构分页技术的地址结构逻辑地址为逻辑地址为A，页面大小为，页面大小为L，页号页号p和页内地址和页内地址d可按下式求得：可按下式求得：p = INTA/L ，d = A MOD Ln以块为单位分配内存以块为单位分配内存n进程每个页面对应一个内存块进程每个页面对应一个内存块n一个进程页面可以装入物理上不连续的一个进程页面可以装入物理上不连续的内存块内存块n页表记录分配结果页表记录分配结果（5）页表）页表图图5-15 分页存储管理系统分页存储管理系统n内存块表记录内存使用情况内存块表记录内存使用情况n每个内存块在内存块表中占一项，每个内存块在内存块表中占一

12、项，记录该块的状态：空闲记录该块的状态：空闲/分配。分配。5.5.2 分页系统中的地址映射分页系统中的地址映射图图5-16 分页系统的地址转换机构分页系统的地址转换机构每个进程平均每个进程平均有半个页面的有半个页面的内部碎片内部碎片5.5.4 硬件支持硬件支持n将页表保存在内存中，由一个页表基将页表保存在内存中，由一个页表基址寄存器址寄存器PTBR指向该页表。整个系指向该页表。整个系统只有一个统只有一个PTBR。n内存存取速度下降内存存取速度下降50%！n把页表放在一组快速存储器中（把页表放在一组快速存储器中（CacheCache），加），加快访问内存的速度。快访问内存的速度。n快速存储器组成

13、的页表称为快表快速存储器组成的页表称为快表n内存中的页表称为慢表内存中的页表称为慢表图图5-17 利用快表实现地址转利用快表实现地址转换换快表性能分析示例快表性能分析示例n如果访问联想存储器的时间为如果访问联想存储器的时间为20ns20ns，访，访问内存的时间是问内存的时间是100ns100ns，假定访问联想存，假定访问联想存储器的命中率分别为储器的命中率分别为0%0%，50%50%，80%80%，90%90%，98%98%，下表列出需要的访问时间：，下表列出需要的访问时间：命中率命中率%平均平均访问时间访问时间：T = h*120+（1-h）*2200T=22050T=17080T=1409

14、0T=13098T=1225.5.6 页表的构造页表的构造1多级页表多级页表大逻辑地址空间，页表项太多。假定：大逻辑地址空间，页表项太多。假定：逻辑地址空间：逻辑地址空间：232 264 一个进程的逻辑空间占一个进程的逻辑空间占32位，页面大小为位，页面大小为4kb最大进程可有最大进程可有220 （1M）个逻辑页）个逻辑页页表表项达页表表项达220个。个。方案：方案：利用两级页表利用两级页表给页表分页。给页表分页。 图图5-18 两级页表地址结构两级页表地址结构图图5-19 两级页表结构两级页表结构1023图图5-20 两级页表结构的地址转换两级页表结构的地址转换分页技术总结分页技术总结n优点

15、：解决了碎片问题，便优点：解决了碎片问题，便于管理于管理n缺点：缺点：n实现共享有条件实现共享有条件n不便于动态连接不便于动态连接n未考虑程序逻辑构成未考虑程序逻辑构成n设页长为设页长为1K1K，程序地址字长为，程序地址字长为1616位，用户程序空位，用户程序空间和页表如图：间和页表如图：5.6 分分 段段 技技 术术5.6.1 分段存储管理的基本概念分段存储管理的基本概念分页存储管理存在问题分页存储管理存在问题导致程序在用户角度导致程序在用户角度的内存空间和实际内存空间不同。的内存空间和实际内存空间不同。子程序子程序符号表符号表主函数主函数库函数库函数堆栈堆栈用户角度的内存用户角度的内存n段

16、（段（segmentationsegmentation）用户角度的内存管）用户角度的内存管理模式理模式, ,逻辑地址空间是段的集合逻辑地址空间是段的集合n当用户程序被编译时，编译程序自动构当用户程序被编译时，编译程序自动构建程序的分段，比如：建程序的分段，比如：pascalpascal编译器编译器全局量全局量过程堆栈过程堆栈可执行代码可执行代码局部变量局部变量1分段分段n按程序自身的逻辑关系划分为若干个程按程序自身的逻辑关系划分为若干个程序段序段n段名段名n段长段长n段号：段号从段号：段号从0 0开始排开始排n段内地址：从段内地址：从0 0开始编址，段内地址连续开始编址，段内地址连续图图5-2

17、5 分分段地址空间段地址空间段号段长08k15k26k35k2分段程序的逻辑地址分段程序的逻辑地址n逻辑地址：段号逻辑地址：段号s + 段内地址段内地址d。n分段存储，进程逻辑地址空间是二维的。分段存储，进程逻辑地址空间是二维的。图图5-26 分段技术地址结构分段技术地址结构3内存分配内存分配n内存以段为单位分配，每段占用一块连内存以段为单位分配，每段占用一块连续的内存分区。各分区的大小由对应段续的内存分区。各分区的大小由对应段的大小决定。的大小决定。n最大段长（分区大小）最大段长（分区大小）n最多段数最多段数 （一个进程拥有最多分区数）（一个进程拥有最多分区数）4段地址映射段地址映射n段表段

18、表n系统为每个进程建一个段表。每个段是段表系统为每个进程建一个段表。每个段是段表的一项，段表项中包含段号、段长和段起始的一项，段表项中包含段号、段长和段起始地址。地址。n段表基址寄存器段表基址寄存器n系统建立一个段表地址寄存器（段表首址系统建立一个段表地址寄存器（段表首址+段表长度）。段表长度）。.40S30N20L10P00K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存k 3200p 1500l 6000n 8000s 5000段长段长 段地址段地址01234操作系统操作系统段号（段号（8bit）段内地址（段内地址（16b

19、it）0000，00100000，0000，0000，0111该段基址：该段基址：6000=（ 1，0111，0111，0000 ）2基址加段内位移量基址加段内位移量0001，0111，0111，00000000，0000，0000，01110001，0111，0111，0111（ 得：物理地址）（得：物理地址）（6007）逻辑地址：第逻辑地址：第2段，第段，第7个字节个字节图图5-27 分段地址转换分段地址转换5.6.2 地址转换地址转换5.6.3 段的共享和保护段的共享和保护1段的共享段的共享n在段一级实现，共享信息可以设成一段。在段一级实现，共享信息可以设成一段。n可以只共享部分程序。可

20、以只共享部分程序。图图5-28 分段系统中段的共享分段系统中段的共享5分页和分段的主要区别分页和分段的主要区别 页是信息的物理单位。段是信息的逻辑单位。页是信息的物理单位。段是信息的逻辑单位。 页大小由系统确定，段长因段而异。页大小由系统确定，段长因段而异。 分页地址空间是一维的。分段的地址空间是二维的。分页地址空间是一维的。分段的地址空间是二维的。 分页系统很难实现过程和数据的分离。分段系统可以。分页系统很难实现过程和数据的分离。分段系统可以。各段长度不一，难以统一管理。各段长度不一，难以统一管理。引入段页式管理引入段页式管理5.7 段页式技术段页式技术5.7.1 段页式存储管理的基本原理段

21、页式存储管理的基本原理图图5-29 段页式存储逻辑地址结构段页式存储逻辑地址结构5.8 虚拟存储器虚拟存储器5.8.1 虚拟存储器的概念虚拟存储器的概念n进程部分装入内存的依据进程部分装入内存的依据程序含有不执行代码段程序含有不执行代码段程序某些选项和路径很少使用程序某些选项和路径很少使用程序执行呈现局部性原理程序执行呈现局部性原理n部分调入内存的好处部分调入内存的好处用户编制程序时不必考虑内存容量的限制用户编制程序时不必考虑内存容量的限制在容量有限的内存中，可同时装入更多的进程在容量有限的内存中，可同时装入更多的进程5.9 请求分页技术请求分页技术5.9.1 请求分页存储管理的基本思想请求分

22、页存储管理的基本思想n按照分页管理提供虚拟存储器。按照分页管理提供虚拟存储器。n一个进程的起始页面在内存就可执行；继续执行一个进程的起始页面在内存就可执行；继续执行的页面不在内存，则动态换入内存。的页面不在内存，则动态换入内存。n页表项增加一个字段页表项增加一个字段标志位，标示进程该页面标志位，标示进程该页面是否已在内存是否已在内存 。 XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-

23、32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页块号块号虚存页表虚存页表虚拟存储的地址映射虚拟存储的地址映射n查询页表项及中断驻留位查询页表项及中断驻留位n在内存，可访问，进行逻辑地址到物理在内存，可访问，进行逻辑地址到物理地址的转换地址的转换n不在内存，发缺页中断，调入所需页面，不在内存，发缺页中断，调入所需页面，进行逻辑地址到物理地址的转换进行逻辑地址到物理地址的转换n按物理地址访问该页内存。按物理地址访问该页内存。14 8 400000000000000001111000010110

24、000000000000111100100011101001101011513121110 9 7 6 5 3 2 1 00010000000000100110000000000100110在在/不在内存不在内存虚存虚存页表页表虚地址虚地址8196物理地址物理地址2458005.9.3 请求分页技术的性能请求分页技术的性能n令令p表示缺页中断的概率表示缺页中断的概率（0p1），简称缺页率，等于），简称缺页率，等于缺页次数与全部访问内存次数之比。缺页次数与全部访问内存次数之比。n虚存有效存取时间表示为：虚存有效存取时间表示为：(1-p)ma + p缺页处理时间缺页处理时间 处理缺页中断的时间处理

25、缺页中断的时间 从磁盘调入该页的时间从磁盘调入该页的时间 重新启动该进程的时间重新启动该进程的时间处理缺页中断花费的时间处理缺页中断花费的时间从磁盘调入该页的时间从磁盘调入该页的时间n包括包括n磁盘寻道时间（即磁头从当前磁道移磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间）至指定磁道所用的时间）n旋转延迟时间（即磁头从当前位置落旋转延迟时间（即磁头从当前位置落到指定扇区开头所用的时间）到指定扇区开头所用的时间）n数据传输时间数据传输时间有效存取时间有效存取时间Tn磁盘旋转延迟时间约为磁盘旋转延迟时间约为8 ms，寻道时间约，寻道时间约为为15 ms，传输时间是，传输时间是1 ms，全部换

26、页时，全部换页时间约间约25 ms。n平均缺页服务时间取平均缺页服务时间取25 ms，内存存取时间，内存存取时间取取100 ns，则，则T = (1- p)100 + p25 000 000 = 100 + 24 999 900p有效存取时间有效存取时间T=110ns时时则有：则有： 100 + 25 000 000p=110 25 000 000p=10 p=0.000 000 4（0.00004%） 表明：表明：缺页率缺页率=0.00004%有效内存读写时间为有效内存读写时间为110ns5.10 页面置换算法页面置换算法5.10.1 页面置换页面置换1页面置换过程页面置换过程用户程序的存储

27、访问的页号顺序构成用户程序的存储访问的页号顺序构成的序列称为页面走向。的序列称为页面走向。常用页面置换算法常用页面置换算法n请求内存管理技请求内存管理技术在实现缺页中术在实现缺页中断时需要决定将断时需要决定将内存中的那些页内存中的那些页面调出内存面调出内存称为页面淘汰算称为页面淘汰算法法统一采用下述页面走向：统一采用下述页面走向： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且假定用户程序只有三并且假定用户程序只有三个内存块可供使用。个内存块可供使用。考察在程序执行的整个过考察在程序执行的整个过程中，一共发生多少次程中，一共发生多少次缺页中断。缺页中断。5.

28、10.2 先进先出法（先进先出法（FIFO）n先进入内存的页，先被换出。先进入内存的页，先被换出。图图5-37 FIFO页面置换页面置换nFIFO页面置换算法优点：容易理解、页面置换算法优点：容易理解、方便程序设计。性能并不很好。方便程序设计。性能并不很好。nFIFO页面置换算法另一个缺点：存在页面置换算法另一个缺点：存在Belady异常现象，即缺页率随内存块异常现象，即缺页率随内存块增加而增加。增加而增加。图5-38 关于一个页面走向的FIFO淘汰算法的缺页曲线有一虚拟存储系统，采用先进先出的页面淘有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配汰算法。在内存中为每个进程

29、分配3 3块。进程执块。进程执行时使用页号的顺序为行时使用页号的顺序为: : 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 5(1)(1) 该进程运行时总共出现几次缺页。该进程运行时总共出现几次缺页。(2)(2) 若每个进程在内存有若每个进程在内存有4 4块，又将产生几次缺块，又将产生几次缺页页(3)(3) 如何解释所出现的现象。如何解释所出现的现象。 Belady异常现象异常现象示例示例FIFO 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 4 4 1 1 1 5 5 5 5 5 5页页2 3 3 3 4 4 4 4 4 2 2 2页

30、页3 2 2 2 3 3 3 3 3 1 1 x x x x x x x x x 共缺页中断共缺页中断9次次m=3m=3FIFO 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 4 4 4 4 4 5 5 5 5 1 1页页2 3 3 3 3 3 3 4 4 4 4 5页页3 2 2 2 2 2 2 3 3 3 3页页4 1 1 1 1 1 1 2 2 2 x x x x x x x x x x共缺页中断共缺页中断10次次m=4m=4m=3m=3时，缺页中断时，缺页中断9 9次次m=4m=4时，缺页中断时，缺页中断1010次次FIFOFIFO页面淘汰算法会产生异常现象（页面淘汰算法会

31、产生异常现象（BeladyBelady现象），即：当分配给进程的物理页面数现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加增加时，缺页次数反而增加5.10.3 最佳置换法（最佳置换法（OPT）n最佳置换算法（最佳置换算法（Optimal Replacement, OPT）所淘汰的页面应在最远的将来才被）所淘汰的页面应在最远的将来才被访问。访问。 图图5-39 最佳页面置换最佳页面置换OPT算法在实现上有困难算法在实现上有困难5.10.4 最近最少使用置换法（最近最少使用置换法（LRU）n置换在最近一段时间里最久没有使用置换在最近一段时间里最久没有使用过的页面过的页面图5-40 最近最少使用页面置换算法(1) (1) 分配给进程的物理块