1、第第5章章 存存 储储 管管 理理图图5-1 内存在计算机系统中的地位内存在计算机系统中的地位5.1 引引 言言5.2 分分 区区 法法5.5 分分 页页 技技 术术5.6 分分 段段 技技 术术5.7 段页式技术段页式技术5.8 虚拟存储器虚拟存储器5.9 请求分页技术请求分页技术5.10 页面置换算法页面置换算法本章内容提要本章内容提要5.1 引引 言言n内存内存（Main Memory或或Primary Memory或或Real Memory）也称主存。）也称主存。n指指CPU能直接存取指令和数据的存储器，能直接存取指令和数据的存储器，统一编址。统一编址。5.1.1 用户程用户程序的执行
2、序的执行图图5-2 用户程序用户程序的机内处理过程的机内处理过程5.1.1 用户程序的主要处理阶段用户程序的主要处理阶段1编辑阶段：编辑源代码。编辑阶段：编辑源代码。2编译阶段：源代码转换为二进制指令构成的编译阶段：源代码转换为二进制指令构成的目标代码模块。目标代码模块。3链接阶段：将链接阶段：将目标模块及所需的库函数链接目标模块及所需的库函数链接形成一个可执行程序。形成一个可执行程序。4装入阶段：将可执行程序装入内存某地址空装入阶段：将可执行程序装入内存某地址空间。间。5运行阶段：从第一条指令开始运行程序。运行阶段：从第一条指令开始运行程序。 内存的使用内存的使用u每个目标模块指令代码都以每
3、个目标模块指令代码都以0为基地址顺序为基地址顺序编址，称为相对地址或逻辑地址。编址，称为相对地址或逻辑地址。u内存中物理存储单元统一由基地址内存中物理存储单元统一由基地址0开始顺开始顺序编址，称为绝对地址或物理地址。序编址，称为绝对地址或物理地址。u可执行程序各条指令需要进行地址转换方可执行程序各条指令需要进行地址转换方能正确执行。能正确执行。主存管理功能主存管理功能n逻辑地址到物理地址的地址转换逻辑地址到物理地址的地址转换n内存分配和回收内存分配和回收n存储保护存储保护n内存扩充内存扩充( (虚拟存储技术虚拟存储技术) )5.1.2 重定位重定位n程序逻辑地址的范围为逻辑地址空间。程序逻辑地
4、址的范围为逻辑地址空间。n可执行程序存放的内存存储单元的范围为物可执行程序存放的内存存储单元的范围为物理地址空间。理地址空间。n用户程序和数据装入内存时，需对目标程序用户程序和数据装入内存时，需对目标程序中的逻辑地址进行修改，把逻辑地址转变为中的逻辑地址进行修改，把逻辑地址转变为物理地址的过程称做地址重定位物理地址的过程称做地址重定位 。地址映射地址映射Load A 1200 3456 。 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=100010001静态重定
5、位静态重定位n目标程序装入内存时，由装入程序对目标目标程序装入内存时，由装入程序对目标程序中的指令地址、数据地址进行修改，程序中的指令地址、数据地址进行修改，完成逻辑地址到物理地址的转换。完成逻辑地址到物理地址的转换。图图5-4 静态重定位示意图静态重定位示意图静态重定位技术分析静态重定位技术分析n优点优点n不需要硬件的支持不需要硬件的支持 n缺点缺点n程序必须占用连续的内存空间程序必须占用连续的内存空间n程序装入后不能移动位置程序装入后不能移动位置n不支持虚拟存储及其交换技术不支持虚拟存储及其交换技术 n进程难以共享程序代码进程难以共享程序代码2动态重定位动态重定位n在每条指令执行时，对所访
6、问的内存进行在每条指令执行时，对所访问的内存进行地址重定位。地址重定位。n硬件地址转换机构实现动态重定位。硬件地址转换机构实现动态重定位。图图5-5 动态重定位示意图动态重定位示意图动态地址重定位优点：动态地址重定位优点：n程序的内存空间动态可变，当程序移程序的内存空间动态可变，当程序移到另一个空间时，修改寄存器到另一个空间时，修改寄存器BRBR的值的值n一个程序不必占用连续内存空间一个程序不必占用连续内存空间n可以部分装入程序运行可以部分装入程序运行n便于多个进程共享同一个程序代码便于多个进程共享同一个程序代码动态地址重定位的代价：动态地址重定位的代价：n需要硬件的支持。需要硬件的支持。n实
7、现存储管理的软件算法较为复杂。实现存储管理的软件算法较为复杂。5.2 分分 区区 法法n支持多道程序运行的一种存储管理方式。支持多道程序运行的一种存储管理方式。n把整个内存划分为若干大小不等的区域，把整个内存划分为若干大小不等的区域，操作系统占用一个区域，其它区域供用操作系统占用一个区域，其它区域供用户进程共享，每个进程占用一个分区，户进程共享，每个进程占用一个分区，这种方法称为分区存储管理。这种方法称为分区存储管理。n分区的划分：分区的划分：n固定分区固定分区n动态分区动态分区 5.2.1 固定分区法固定分区法n内存中分区个数、分区大小固定，每个内存中分区个数、分区大小固定，每个分区装入一个
8、进程。分区装入一个进程。1分区的大小分区的大小n划分分区大小有两种方式：划分分区大小有两种方式：n分区大小相同分区大小相同n分区大小不同分区大小不同2内存分配内存分配n分区等分方式，进程装入内存很简单。分区等分方式，进程装入内存很简单。n分区差分方式，有多个输入队列法和单一输入队列法分区差分方式，有多个输入队列法和单一输入队列法图图5-6 固定分区内存分配固定分区内存分配5.2.2 动态分区法动态分区法1分区的分配分区的分配n进程进入内存建立分区，大小适应进程进程进入内存建立分区，大小适应进程的需要。这种技术称为动态分区法。的需要。这种技术称为动态分区法。2数据结构数据结构（1）空闲分区表存放
9、）空闲分区表存放（2）空闲分区链存放）空闲分区链存放图图5-7 MVT的内存分配和进程调度情况的内存分配和进程调度情况3动态分区分配算法动态分区分配算法（1）最先适应算法）最先适应算法n空闲表按内存地址顺序排列空闲表按内存地址顺序排列（2）最佳（坏）适应算法）最佳（坏）适应算法n空闲表按空闲块大小的增量形式排列空闲表按空闲块大小的增量形式排列（3）循环适应算法）循环适应算法n最先适应算法的变种。从上次找到的可用最先适应算法的变种。从上次找到的可用分区的下一个空闲分区开始查找，顺序选分区的下一个空闲分区开始查找，顺序选择满足要求的第一个空闲分区。择满足要求的第一个空闲分区。 5.3 可重定位分区
10、分配可重定位分区分配5.3.1 碎片问题碎片问题n内存中尺寸太小、无法利用的小分区称内存中尺寸太小、无法利用的小分区称做做“碎片碎片”。n固定分区法会产生内部碎片。动态分区固定分区法会产生内部碎片。动态分区会产生外部碎片会产生外部碎片.图图5-9 分配分配16 KB内存块之前和之后的内存配置内存块之前和之后的内存配置5.3.1 碎片问题碎片问题n紧缩的时机紧缩的时机n进程结束、释放所占用的分区时（空闲区有进程结束、释放所占用的分区时（空闲区有可能相邻）可能相邻）n在分配进程的分区时（空闲区有可能不够）在分配进程的分区时（空闲区有可能不够）5.3.2 紧缩紧缩n移动某些已分配区，使所有进程的分区
11、紧邻的技术。移动某些已分配区，使所有进程的分区紧邻的技术。图图5-10 可重定位分区的紧缩可重定位分区的紧缩5.3.3 动态重定位的实现动态重定位的实现n动态重定位经常用硬件实现动态重定位经常用硬件实现n硬件支持硬件支持n基址寄存器基址寄存器n限长寄存器限长寄存器图图5-11 动态重定位的实现过程动态重定位的实现过程5.3.4 可重定位分区法优缺点可重定位分区法优缺点n优点优点n可以消除碎片，能够分配更多的分区，有助于多道可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。程序设计，提高内存的利用率。n缺点缺点n紧缩技术花费紧缩技术花费CPU时间时间n当进程大于整个空闲区无
12、法装入时，仍要浪费一定当进程大于整个空闲区无法装入时，仍要浪费一定的内存的内存n进程的存储区内可能放有从未使用的信息进程的存储区内可能放有从未使用的信息n进程之间无法对信息共享进程之间无法对信息共享5.4 对对 换换 技技 术术图图5-12 对换两个进程对换两个进程当内存不足时，将暂时不运行的进程换到外存，当内存不足时，将暂时不运行的进程换到外存，将需要马上运行的进程调入内存。将需要马上运行的进程调入内存。图图5-13 多道程序对换技术示例多道程序对换技术示例5.5 分分 页页 技技 术术5.5.1 分页存储管理的基本概念分页存储管理的基本概念把用户程序按逻辑页划分成大小相等的部把用户程序按逻
13、辑页划分成大小相等的部分，称为页（分，称为页（pagepage） 。从。从0 0开始编制页号，开始编制页号，页内地址从页内地址从0 0开始编址。开始编址。（1）逻辑地址空间）逻辑地址空间分页分页（2）内存地址空间）内存地址空间分块分块n页（或块）大小由硬件（系统）确定页（或块）大小由硬件（系统）确定（3）逻辑地址表示）逻辑地址表示图图5-14 分页技术的地址结构分页技术的地址结构逻辑地址为逻辑地址为A，页面大小为，页面大小为L，页号页号p和页内地址和页内地址d可按下式求得：可按下式求得：p = INTA/L ，d = A MOD Ln以块为单位分配内存以块为单位分配内存n进程每个页面对应一个内
14、存块进程每个页面对应一个内存块n一个进程页面可以装入物理上不连续的一个进程页面可以装入物理上不连续的内存块内存块n页表记录分配结果页表记录分配结果（5）页表）页表图图5-15 分页存储管理系统分页存储管理系统n内存块表记录内存使用情况内存块表记录内存使用情况n每个内存块在内存块表中占一项，每个内存块在内存块表中占一项，记录该块的状态：空闲记录该块的状态：空闲/分配。分配。5.5.2 分页系统中的地址映射分页系统中的地址映射图图5-16 分页系统的地址转换机构分页系统的地址转换机构每个进程平均每个进程平均有半个页面的有半个页面的内部碎片内部碎片设进程平均大小为设进程平均大小为s字节，每个页表项占
15、字节，每个页表项占e字节。字节。每个进程需要的页数为每个进程需要的页数为s/p每个进程的页表空间：每个进程的页表空间： e*s /p 字节字节每个进程内部碎片平均为每个进程内部碎片平均为p/2页表和内部碎片带来的总开销是：页表和内部碎片带来的总开销是： e*s /p +p/2令该表达式的值最小，对令该表达式的值最小，对p求导，令其等于求导，令其等于0，得到方程：，得到方程：-e* s /p2 + 1/2=0得出最佳页面尺寸公式，仅考虑上述两个因素：得出最佳页面尺寸公式，仅考虑上述两个因素：5.5.3 页面尺寸页面尺寸p的讨论的讨论esp2如果如果s = 1 MB，e = 8 B，则最佳页面尺寸
16、，则最佳页面尺寸p是是4 KB5.5.4 硬件支持硬件支持n将页表保存在内存中，由一个页表基将页表保存在内存中，由一个页表基址寄存器址寄存器PTBR指向该页表。整个系指向该页表。整个系统只有一个统只有一个PTBR。n内存存取速度下降内存存取速度下降50%！n把页表放在一组快速存储器中（把页表放在一组快速存储器中（CacheCache），加），加快访问内存的速度。快速存储器组成的页表快访问内存的速度。快速存储器组成的页表称为快表，内存中的页表称为慢表。称为快表，内存中的页表称为慢表。n快表又称相联存储器（快表又称相联存储器（associative memory）或或 TLB（Translatio
17、n lookaside buffers）转换检测缓冲区。转换检测缓冲区。快表（或快表（或Translation Lookaside Buffer，TLB）n快表每项包括键号和值两部分快表每项包括键号和值两部分n键号是当前进程正在使用的某个页面号键号是当前进程正在使用的某个页面号n值是该页面所对应的物理块号值是该页面所对应的物理块号快表性能分析示例快表性能分析示例n如果访问联想存储器的时间为如果访问联想存储器的时间为20ns20ns，访，访问内存的时间是问内存的时间是100ns100ns，假定访问联想存，假定访问联想存储器的命中率分别为储器的命中率分别为0%0%，50%50%，80%80%，90
18、%90%，98%98%，下表列出需要的访问时间：，下表列出需要的访问时间：命中率命中率%平均平均访问时间访问时间：T = h*120+（1-h）*2200T=22050T=17080T=14090T=13098T=122图图5-17 利用快表实现地址转利用快表实现地址转换换5.5.5 保护方式保护方式（1）利用页表本身进行保护：保护页表基址）利用页表本身进行保护：保护页表基址和页表长度和页表长度（2）设置存取控制位：一个页表项，权限包）设置存取控制位：一个页表项，权限包括：（括：（R/W/RW），出错发中断。），出错发中断。（3）设置合法标志）设置合法标志5.5.6 页表的构造页表的构造1多级
19、页表多级页表大逻辑地址空间，页表项太多。假定：大逻辑地址空间，页表项太多。假定：逻辑地址空间：逻辑地址空间：232 264 一个进程的逻辑空间占一个进程的逻辑空间占32位，页面大小为位，页面大小为4kb最大进程可有最大进程可有220 （1M）个逻辑页）个逻辑页页表表项达页表表项达220个个。方案：方案：利用两级利用两级页表页表给页表分页。给页表分页。 图图5-18 两级页表地址结构两级页表地址结构图图5-19 两级页表结构两级页表结构1023图图5-20 两级页表结构的地址转换两级页表结构的地址转换图图5-21 三级页表地址结构三级页表地址结构三级页表结构及其地址映射过程三级页表结构及其地址映
20、射过程2散列页表散列页表nHashed Page Tablen以页号作为参数形成散列值以页号作为参数形成散列值n散列表中每一项具有相同散列值，是一个散列表中每一项具有相同散列值，是一个链表。链表。n每个链表元素由页号、对应的内存块号、每个链表元素由页号、对应的内存块号、指向链表中下个元素的指针组成。指向链表中下个元素的指针组成。图图5-22 散列页表散列页表3倒置页表倒置页表n进程页表以逻辑地址的顺序排序，虚地址空间进程页表以逻辑地址的顺序排序，虚地址空间较大。较大。n倒置页表按内存块号排序，每个内存块占有一倒置页表按内存块号排序，每个内存块占有一个表项。每个表项包括存放在该内存块中页号个表项
21、。每个表项包括存放在该内存块中页号和拥有该页面的进程标识符。系统只有一个页和拥有该页面的进程标识符。系统只有一个页表。表。图图5-23 倒置页表倒置页表5.5.7 页面共享页面共享图图5-24 页面共享页面共享可 再 入 代 码可 再 入 代 码（或纯码，在（或纯码，在其执行过程中其执行过程中本身不做任何本身不做任何修改的代码，修改的代码，通常由指令和通常由指令和常数组成）。常数组成）。分页式管理可实现页面共享分页式管理可实现页面共享n条件：条件：n共享部分是纯码程序共享部分是纯码程序n共享部分与非共享部分，分页单独存放共享部分与非共享部分，分页单独存放n共享部分的逻辑页号、物理页号完全相同共
22、享部分的逻辑页号、物理页号完全相同分页技术总结分页技术总结n优点：解决了碎片问题，便优点：解决了碎片问题，便于管理于管理n缺点：缺点：n实现共享有条件实现共享有条件n不便于动态连接不便于动态连接n未考虑程序逻辑构成未考虑程序逻辑构成n设页长为设页长为1K1K，程序地址字长为，程序地址字长为1616位，用户程序空位，用户程序空间和页表间和页表如图如图：执行指令执行指令MOV r1，2500，地址转换步骤，地址转换步骤说明说明1)1)取出程序地址字取出程序地址字25002500送虚地址寄存器送虚地址寄存器VRVR2)2)由硬件分离页号由硬件分离页号P P和页内地址和页内地址W W：页长为：页长为1
23、K1K，所以页，所以页内地址占内地址占1010位（位（0909位），页号占位），页号占6 6位（位（10151015位）位）3)3)硬件取出硬件取出VRVR寄存器中的高寄存器中的高6 6位即页号，低位即页号，低1010位即页内位即页内地址，得到页号地址，得到页号P=2P=2，页内位移，页内位移W=452W=4524)4)根据页号根据页号P=2P=2，硬件自动查该进程页表，找到第，硬件自动查该进程页表，找到第2 2页页对应块号为对应块号为7 7，将块号送到内存地址寄存器，将块号送到内存地址寄存器MRMR的高的高1010位中，将位中，将VRVR中中W W值值452452复制到复制到MRMR低低10
24、10位中，形成内存位中，形成内存地址。地址。5)5)系统就以系统就以MRMR中的地址访问内存中的地址访问内存计算分页地址时要注意：计算分页地址时要注意：u给出地址字的进制给出地址字的进制u地址的空间长度地址的空间长度u页长页长u逻辑空间允许的最大页数逻辑空间允许的最大页数5.6 分分 段段 技技 术术5.6.1 分段存储管理的基本概念分段存储管理的基本概念分页存储管理存在问题分页存储管理存在问题导致程序在用户角度导致程序在用户角度的内存空间和实际内存空间不同。的内存空间和实际内存空间不同。子程序子程序符号表符号表主函数主函数库函数库函数堆栈堆栈用户角度的内存用户角度的内存n段（段（segmen
25、tationsegmentation）用户角度的内存管）用户角度的内存管理模式理模式, ,逻辑地址空间是段的集合逻辑地址空间是段的集合n当用户程序被编译时，编译程序自动构当用户程序被编译时，编译程序自动构建程序的分段，比如：建程序的分段，比如：pascalpascal编译器编译器全局量全局量过程堆栈过程堆栈可执行代码可执行代码局部变量局部变量1分段分段n按程序自身的逻辑关系划分为若干按程序自身的逻辑关系划分为若干个程序段个程序段n段名段名n段长段长n段号：段号从段号：段号从0 0开始排开始排n段内地址：从段内地址：从0 0开始编址，段内地址连开始编址，段内地址连续续图图5-25 分分段地址空间
26、段地址空间段号段长08k15k26k35k2分段程序的逻辑地址分段程序的逻辑地址n逻辑地址：段号逻辑地址：段号s + 段内地址段内地址d。n分段存储，进程逻辑地址空间是分段存储，进程逻辑地址空间是二维的二维的。图图5-26 分段技术地址结构分段技术地址结构段号（段号（8bit）段内地址（段内地址（16bit）0000，00000000，,00000000，00001111，,11110000，00010000，,00000000，00011111，,1111，1111，11110000，,00001111，11111111，,11113内存分配内存分配n内存以段为单位分配，每段占用一块连内存以
27、段为单位分配，每段占用一块连续的内存分区。各分区的大小由对应段续的内存分区。各分区的大小由对应段的大小决定。的大小决定。n最大段长（分区大小）最大段长（分区大小）n最多段数最多段数 （一个进程拥有最多分区数）（一个进程拥有最多分区数）4段地址映射段地址映射n段表段表n系统为每个进程建一个段表。每个段是段表系统为每个进程建一个段表。每个段是段表的一项，段表项中包含段号、段长和段起始的一项，段表项中包含段号、段长和段起始地址。地址。n段表基址寄存器段表基址寄存器n系统建立一个段表地址寄存器（段表首址系统建立一个段表地址寄存器（段表首址+段表长度）。段表长度）。.40S30N20L10P00K逻辑段
28、号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存k 3200p 1500l 6000n 8000s 5000段长段长 段地址段地址01234操作系统操作系统段号（段号（8bit）段内地址（段内地址（16bit）0000，00100000，0000，0000，0111该段基址：该段基址：6000=（ 1，0111，0111，0000 ）2基址加段内位移量基址加段内位移量0001，0111，0111，00000000，0000，0000，01110001，0111，0111，0111（ 得：得：物理地址）（物理地址）（6007）逻辑地址：
29、第逻辑地址：第2段，第段，第7个字节个字节图图5-27 分段地址转换分段地址转换5.6.2 地址转换地址转换5.6.3 段的共享和保护段的共享和保护1段的共享段的共享n在段一级实现，共享信息可以设成一段。在段一级实现，共享信息可以设成一段。n可以只共享部分程序。可以只共享部分程序。图图5-28 分段系统中段的共享分段系统中段的共享2段的保护段的保护n段的保护措施包括以下三种：段的保护措施包括以下三种： 存取控制（存取控制（R/W/RW） 段表本身可起保护作用。段表本身可起保护作用。n表项中设置该段的长度限制表项中设置该段的长度限制n段长限制，段表地址寄存器中有段表段长限制，段表地址寄存器中有段
30、表长度的信息。长度的信息。 保护环（进程优先权由所在环决定）保护环（进程优先权由所在环决定） 5分页和分段的主要区别分页和分段的主要区别 页是信息的物理单位。段是信息的逻辑单位。页是信息的物理单位。段是信息的逻辑单位。 页大小由系统确定，段长因段而异。页大小由系统确定，段长因段而异。 分页地址空间是一维的。分段的地址空间是二维的。分页地址空间是一维的。分段的地址空间是二维的。 分页系统很难实现过程和数据的分离。分段系统可以。分页系统很难实现过程和数据的分离。分段系统可以。各段长度不一，难以统一管理。各段长度不一，难以统一管理。引入段页式管理引入段页式管理5.7 段页式技术段页式技术5.7.1
31、段页式存储管理的基本原理段页式存储管理的基本原理图图5-29 段页式存储逻辑地址结构段页式存储逻辑地址结构5.7.2段页式地址转换过程段页式地址转换过程n段号加段表寄存器中的段表首址段号加段表寄存器中的段表首址该段页表首址该段页表首址+页表页表长度长度n页表长度比较页表长度比较越界发中断，越界发中断，n取页号加页表基址取页号加页表基址对应页号项，对应页号项，读出页表中的物理块读出页表中的物理块号号n物理块号与页内地址合成物理块号与页内地址合成物理地址物理地址n(如不在内存发缺页中断，重新更新页表如不在内存发缺页中断，重新更新页表)n进行读写。进行读写。5.8 虚拟存储器虚拟存储器5.8.1 虚
32、拟存储器的概念虚拟存储器的概念n进程部分装入内存的依据进程部分装入内存的依据程序含有不执行代码段程序含有不执行代码段程序某些选项和路径很少使用程序某些选项和路径很少使用程序执行呈现局部性原理程序执行呈现局部性原理n部分调入内存的好处部分调入内存的好处用户编制程序时不必考虑内存容量的限制用户编制程序时不必考虑内存容量的限制在容量有限的内存中，可同时装入更多的进程在容量有限的内存中，可同时装入更多的进程虚存下的编程地址空间虚存下的编程地址空间n指令操作数中地址的二进制位数指令操作数中地址的二进制位数n磁盘中对换区的大小磁盘中对换区的大小5.8.2 虚拟存储器的特征虚拟存储器的特征l虚拟扩充虚拟扩充
33、l部分装入部分装入l内存分配不连续内存分配不连续l进程执行中多次对换进程执行中多次对换 5.9 请求分页技术请求分页技术5.9.1 请求分页存储管理的基本思想请求分页存储管理的基本思想n按照分页管理提供虚拟存储器。按照分页管理提供虚拟存储器。n一个进程的起始页面在内存就可执行；继续执行一个进程的起始页面在内存就可执行；继续执行的页面不在内存，则动态换入内存。的页面不在内存，则动态换入内存。n页表项增加一个字段页表项增加一个字段标志位，标示进程该页面标志位，标示进程该页面是否已在内存是否已在内存 。 5.9.2 硬件支持及缺页处理硬件支持及缺页处理1页表机制页表机制n页表项通常页表项通常包含下列
34、包含下列5种信息：种信息： 内存块号内存块号 标志位标志位该位是该位是1，表示该表项有效，该页在内存，表示该表项有效，该页在内存，可以使用。可以使用。该位是该位是0，表示该表项对应的页面不在内存，表示该表项对应的页面不在内存，访问该页置缺页中断访问该页置缺页中断 保护位（读写权限）保护位（读写权限） 修改位修改位/引用位。记录该页的状态。引用位。记录该页的状态。 禁止缓存位。该位用于禁止该页被缓存。禁止缓存位。该位用于禁止该页被缓存。XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24
35、K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页块号块号虚存页表虚存页表虚拟存储的地址映射虚拟存储的地址映射n查询页表项及中断驻留位查询页表项及中断驻留位n在内存，可访问，进行逻辑地址到物理在内存，可访问，进行逻辑地址到物理地址的转换地址的转换n不在内存，发缺页中断，调入所需页面，不在内存，发缺页中断，调入所需页面，进行逻辑地址到物理地址的转换进行逻辑地址到物理地址的转换n按物理地址访问该页内
36、存。按物理地址访问该页内存。14 8 400000000000000001111000010110000000000000111100100011101001101011513121110 9 7 6 5 3 2 1 00010000000000100110000000000100110在在/不在内存不在内存虚存虚存页表页表虚地址虚地址8196物理地址物理地址2458005.9.3 请求分页技术的性能请求分页技术的性能n令令p表示缺页中断的概率表示缺页中断的概率（0p1），简称缺页率，等于），简称缺页率，等于缺页次数与全部访问内存次数之比。缺页次数与全部访问内存次数之比。n虚存有效存取时间表示
37、为：虚存有效存取时间表示为：(1-p)ma + p缺页处理时间缺页处理时间2缺页中断机构缺页中断机构图图5-34 指令执行步骤与缺页指令执行步骤与缺页中断处理过程中断处理过程 进程进程A缺页处理过程缺页处理过程1.进程进程A遇到缺页指令，捕俘进入操作系统。遇到缺页指令，捕俘进入操作系统。2.保存进程保存进程A的各个寄存器和进程状态信息。的各个寄存器和进程状态信息。3.检查该页的访问合法性，并确定该页在磁盘上的地检查该页的访问合法性，并确定该页在磁盘上的地址，把该页从盘上读到空闲内存块中。址，把该页从盘上读到空闲内存块中。4.在等待盘在等待盘I/O完成时，把完成时，把CPU分给其他进程分给其他进
38、程5.盘盘I/O完成，发出盘中断。完成，发出盘中断。6.保存进程保存进程B的用户寄存器和进程状态。的用户寄存器和进程状态。7.确定该中断来自磁盘。确定该中断来自磁盘。8.调整页表，标明所需页已放入内存。调整页表，标明所需页已放入内存。9.进程进程A就绪，等待分配就绪，等待分配CPU。10.调度进程调度进程A，则恢复它的各寄存器、进程状态和新，则恢复它的各寄存器、进程状态和新的页表，然后重新执行前面被中断的指令。的页表，然后重新执行前面被中断的指令。 处理缺页中断的时间处理缺页中断的时间 从磁盘调入该页的时间从磁盘调入该页的时间 重新启动该进程的时间重新启动该进程的时间处理缺页中断花费的时间处理
39、缺页中断花费的时间从磁盘调入该页的时间从磁盘调入该页的时间n包括包括n磁盘寻道时间（即磁头从当前磁道移磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间）至指定磁道所用的时间）n旋转延迟时间（即磁头从当前位置落旋转延迟时间（即磁头从当前位置落到指定扇区开头所用的时间）到指定扇区开头所用的时间）n数据传输时间数据传输时间有效存取时间有效存取时间Tn磁盘旋转延迟时间约为磁盘旋转延迟时间约为8 ms，寻道时间约，寻道时间约为为15 ms，传输时间是，传输时间是1 ms，全部换页时全部换页时间约间约25 ms。n平均缺页服务时间取平均缺页服务时间取25 ms，内存存取时间，内存存取时间取取100 n
40、s，则，则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页面置换过程页面置换过程2页面走向页面走向n用户程序的存储访问的页号顺序构成的序用户程序的存储访问的页号顺序构成的序列称为页面走向。列称为页面走向。页面走向示例页面
41、走向示例对于给定的页面大小，仅考虑其页号，不关心完整对于给定的页面大小，仅考虑其页号，不关心完整的地址。的地址。如果当前对页面如果当前对页面p进行了访问，那么，马上又对该进行了访问，那么，马上又对该页访问就不会缺页。例如程序访问的地址顺序如下：页访问就不会缺页。例如程序访问的地址顺序如下： 0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105n若每页若每页100个字节，则前两位就是页号。页面走向简化个字节，则前两位就是页号。页面走向简化为：
42、为： 1，4，1，6，1，6，1，6，1，6，1n一般来说，随着可用块数的增加，缺页数一般来说，随着可用块数的增加，缺页数将减少。将减少。图图5-36 缺页量与内存块数关系图缺页量与内存块数关系图常用页面置换算法常用页面置换算法n请求内存管理技请求内存管理技术在实现缺页中术在实现缺页中断时需要决定将断时需要决定将内存中的那些页内存中的那些页面调出内存面调出内存称为页面淘汰算称为页面淘汰算法法( (中级调度中级调度) )统一采用下述页面走向：统一采用下述页面走向： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且假定用户程序只有三并且假定用户程序只有三个内存块可
43、供使用。个内存块可供使用。考察在程序执行的整个过考察在程序执行的整个过程中，一共发生多少次程中，一共发生多少次缺页中断。缺页中断。5.10.2 先进先出法（先进先出法（FIFO）n先进入内存的页，先被换出。先进入内存的页，先被换出。图图5-37 FIFO页面置换页面置换nFIFO页面置换算法优点：容易理解、页面置换算法优点：容易理解、方便程序设计。性能并不很好。方便程序设计。性能并不很好。nFIFO页面置换算法另一个缺点：存在页面置换算法另一个缺点：存在Belady异常现象，即缺页率随内存块异常现象，即缺页率随内存块增加而增加。增加而增加。图5-38 关于一个页面走向的FIFO淘汰算法的缺页曲
44、线有一虚拟存储系统，采用先进先出的页有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配面淘汰算法。在内存中为每个进程分配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
45、 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页页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=4 m=3 m=
46、3时，缺页中断时，缺页中断9 9次次 m=4m=4时，缺页中断时，缺页中断1010次次 FIFOFIFO页面淘汰算法会产生异常现象（页面淘汰算法会产生异常现象（BeladyBelady现现象），即：当分配给进程的物理页面数增加时，象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。缺页次数反而增加。5.10.3 最佳置换法（最佳置换法（OPT）n最佳置换算法（最佳置换算法（Optimal Replacement, OPT）所淘汰的页面应在最远的将来才被）所淘汰的页面应在最远的将来才被访问。访问。 图图5-39 最佳页面置换最佳页面置换OPT算法在实现上有困难算法在实现上有困难5.10.
47、4 最近最少使用置换法（最近最少使用置换法（LRU）n置换在最近一段时间里最久没有使用置换在最近一段时间里最久没有使用过的页面过的页面图5-40 最近最少使用页面置换算法LRULRU算法需要实际硬件的支持。确定最后访问算法需要实际硬件的支持。确定最后访问以来的时间顺序。有以下两种可行的办法：以来的时间顺序。有以下两种可行的办法： 计数器。计数器。 栈。栈。图图5-41 利用栈记录目前访问最多的页面利用栈记录目前访问最多的页面5.10.5 第二次机会置换法（第二次机会置换法（SCR）n第二次机会置换法（第二次机会置换法（Second Chance Page Replacement, SCR）是对
48、）是对FIFO算算法法的改进。的改进。n当选择某一页面置换时，就检查最老页面当选择某一页面置换时，就检查最老页面的引用位：如果是的引用位：如果是0，就立即淘汰该页；如，就立即淘汰该页；如果该引用位是果该引用位是1，就给它第二次机会，将引，就给它第二次机会，将引用位置用位置0，按当前时间排在队尾。，按当前时间排在队尾。图图5-42 第二次机会法示例第二次机会法示例5.10.7 最少使用置换法（最少使用置换法（LFU） 最不经常使用（最不经常使用（LFULFU）置换算法：）置换算法： 选择访问次数最少的页面淘汰。选择访问次数最少的页面淘汰。(1)(1)页淘汰算法页淘汰算法(2)(2)程序的编制方法
49、程序的编制方法(3)(3)分配给进程的物理块数分配给进程的物理块数(4)(4)页本身的大小页本身的大小影响缺页次数的因素影响缺页次数的因素程序编制方法示例程序编制方法示例程序编制方法程序编制方法1：for j=0 to 127 for i=0 to 127 aij=0;程序编制方法程序编制方法2：for i=0 to 127 for j=0 to 127 aij=0;内存分配内存分配1 1页，初始时矩阵数据均不在内存；页，初始时矩阵数据均不在内存；页面大小为页面大小为128128个整数；矩阵个整数；矩阵A A128X128128X128按行存放。按行存放。这两个程序执行时分别会产生多少次缺页中
50、断？这两个程序执行时分别会产生多少次缺页中断？int a128128;A00A01A02A0127A10A01A02A0127A1270A1271A1272A127127n程序An根据已知条件可知：外循环加内循环赋值访问逻辑页的顺序是0、1、2、3、4、5、。127页，正好与缺页中断调入内存的页面顺序一致。所以共产生128次缺页中断。n程序Bn根据已知条件可知：每次内循环赋值访问逻辑页的顺序是0、1、2、3、4、5、。127页，每一次外循环赋值访问逻辑页的顺序是0、1、2、3、4、5、。127页，因此，每次赋值都会产生一次缺页中断，将需要的页面调入调入内存。所以共产生128*128次缺页中断。
