操作系统(第2版)孟庆昌-牛欣源-编著--课件--第五章-存-储-管-理

《操作系统(第2版)孟庆昌-牛欣源-编著--课件--第五章-存-储-管-理》由会员分享，可在线阅读，更多相关《操作系统(第2版)孟庆昌-牛欣源-编著--课件--第五章-存-储-管-理（134页珍藏版）》请在金锄头文库上搜索。

1、第5章 存 储 管 理,图5-1 内存在计算机系统中的地位,5.1 引 言 5.2 分 区 法 5.5 分 页 技 术 5.6 分 段 技 术 5.7 段页式技术 5.8 虚拟存储器 5.9 请求分页技术 5.10 页面置换算法,本章内容提要,5.1 引 言,内存（Main Memory或Primary Memory或Real Memory）也称主存。 指CPU能直接存取指令和数据的存储器，统一编址。,5.1.1 用户程序的执行,图5-2 用户程序的机内处理过程,5.1.1 用户程序的主要处理阶段,1编辑阶段：编辑源代码。 2编译阶段：源代码转换为二进制指令构成的目标代码模块。 3链接阶段：将

2、目标模块及所需的库函数链接形成一个可执行程序。 4装入阶段：将可执行程序装入内存某地址空间。 5运行阶段：从第一条指令开始运行程序。,内存的使用,每个目标模块指令代码都以0为基地址顺序编址，称为相对地址或逻辑地址。 内存中物理存储单元统一由基地址0开始顺序编址，称为绝对地址或物理地址。 可执行程序各条指令需要进行地址转换方能正确执行。,主存管理功能,逻辑地址到物理地址的地址转换 内存分配和回收 存储保护 内存扩充(虚拟存储技术),5.1.2 重定位,程序逻辑地址的范围为逻辑地址空间。 可执行程序存放的内存存储单元的范围为物理地址空间。 用户程序和数据装入内存时，需对目标程序中的逻辑地址进行修改

3、，把逻辑地址转变为物理地址的过程称做地址重定位 。,地址映射,Load A 1200 3456 。 。,1200,物理地址空间,Load A data1 data1 3456,源程序,Load A 200 3456,0,100,200,编译连接,逻辑地址空间,BA=1000,1000,1静态重定位,目标程序装入内存时，由装入程序对目标程序中的指令地址、数据地址进行修改，完成逻辑地址到物理地址的转换。,图5-4 静态重定位示意图,静态重定位技术分析,优点 不需要硬件的支持 缺点 程序必须占用连续的内存空间 程序装入后不能移动位置 不支持虚拟存储及其交换技术 进程难以共享程序代码,2动态重定位,在

4、每条指令执行时，对所访问的内存进行地址重定位。 硬件地址转换机构实现动态重定位。,图5-5 动态重定位示意图,动态地址重定位优点： 程序的内存空间动态可变，当程序移到另一个空间时，修改寄存器BR的值 一个程序不必占用连续内存空间 可以部分装入程序运行 便于多个进程共享同一个程序代码 动态地址重定位的代价： 需要硬件的支持。 实现存储管理的软件算法较为复杂。,5.2 分 区 法,支持多道程序运行的一种存储管理方式。 把整个内存划分为若干大小不等的区域，操作系统占用一个区域，其它区域供用户进程共享，每个进程占用一个分区，这种方法称为分区存储管理。 分区的划分： 固定分区 动态分区,5.2.1 固定

5、分区法,内存中分区个数、分区大小固定，每个分区装入一个进程。 1分区的大小 划分分区大小有两种方式： 分区大小相同 分区大小不同,2内存分配 分区等分方式，进程装入内存很简单。 分区差分方式，有多个输入队列法和单一输入队列法,图5-6 固定分区内存分配,5.2.2 动态分区法,1分区的分配 进程进入内存建立分区，大小适应进程的需要。这种技术称为动态分区法。 2数据结构 （1）空闲分区表存放 （2）空闲分区链存放,图5-7 MVT的内存分配和进程调度情况,3动态分区分配算法,（1）最先适应算法 空闲表按内存地址顺序排列 （2）最佳（坏）适应算法 空闲表按空闲块大小的增量形式排列 （3）循环适应算

6、法 最先适应算法的变种。从上次找到的可用分区的下一个空闲分区开始查找，顺序选择满足要求的第一个空闲分区。,5.3 可重定位分区分配,5.3.1 碎片问题 内存中尺寸太小、无法利用的小分区称做“碎片”。 固定分区法会产生内部碎片。动态分区会产生外部碎片.,图5-9 分配16 KB内存块之前和之后的内存配置,5.3.1 碎片问题,紧缩的时机 进程结束、释放所占用的分区时（空闲区有可能相邻） 在分配进程的分区时（空闲区有可能不够）,5.3.2 紧缩,移动某些已分配区，使所有进程的分区紧邻的技术。,图5-10 可重定位分区的紧缩,5.3.3 动态重定位的实现,动态重定位经常用硬件实现 硬件支持 基址寄

7、存器 限长寄存器,图5-11 动态重定位的实现过程,5.3.4 可重定位分区法优缺点,优点 可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。 缺点 紧缩技术花费CPU时间 当进程大于整个空闲区无法装入时，仍要浪费一定的内存 进程的存储区内可能放有从未使用的信息 进程之间无法对信息共享,5.4 对 换 技 术,图5-12 对换两个进程,当内存不足时，将暂时不运行的进程换到外存， 将需要马上运行的进程调入内存。,图5-13 多道程序对换技术示例,5.5 分 页 技 术,5.5.1 分页存储管理的基本概念 把用户程序按逻辑页划分成大小相等的部分，称为页（page） 。从0开始

8、编制页号，页内地址从0开始编址。 （1）逻辑地址空间分页 （2）内存地址空间分块 页（或块）大小由硬件（系统）确定,（3）逻辑地址表示,图5-14 分页技术的地址结构,逻辑地址为A，页面大小为L， 页号p和页内地址d可按下式求得： p = INTA/L ，d = A MOD L,以块为单位分配内存 进程每个页面对应一个内存块 一个进程页面可以装入物理上不连续的内存块 页表记录分配结果,（4）内存分配原则,（5）页表从页号到物理块号的地址映射,图5-15 分页存储管理系统,内存块表记录内存使用情况 每个内存块在内存块表中占一项，记录该块的状态：空闲/分配。,（6）内存块表,5.5.2 分页系统中

9、的地址映射,图5-16 分页系统的地址转换机构,每个进程平均有半个页面的内部碎片,设进程平均大小为s字节，每个页表项占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的讨论,如果s = 1 MB，e = 8 B，则最佳页面尺寸p是4 KB,5.5.4 硬件支持,将页表保存在内存中，由一个页表基址寄存器PTBR指向该页表。整个系

10、统只有一个PTBR。 内存存取速度下降50%！,把页表放在一组快速存储器中（Cache），加快访问内存的速度。快速存储器组成的页表称为快表，内存中的页表称为慢表。 快表又称相联存储器（associative memory） 或 TLB（Translation lookaside buffers）转换检测缓冲区。,快表（或Translation Lookaside Buffer，TLB）,快表每项包括键号和值两部分 键号是当前进程正在使用的某个页面号 值是该页面所对应的物理块号,快表性能分析示例,如果访问联想存储器的时间为20ns，访问内存的时间是100ns，假定访问联想存储器的命中率分别为0%

11、，50%，80%，90%，98%，下表列出需要的访问时间：,图5-17 利用快表实现地址转换,5.5.5 保护方式,（1）利用页表本身进行保护：保护页表基址和页表长度 （2）设置存取控制位：一个页表项，权限包括：（R/W/RW），出错发中断。 （3）设置合法标志,5.5.6 页表的构造,1多级页表 大逻辑地址空间，页表项太多。假定： 逻辑地址空间：232 264 一个进程的逻辑空间占32位，页面大小为4kb 最大进程可有220 （1M）个逻辑页 页表表项达220个。 方案：利用两级页表给页表分页。,图5-18 两级页表地址结构,图5-19 两级页表结构,1023,图5-20 两级页表结构的地址

12、转换,图5-21 三级页表地址结构,三级页表结构及其地址映射过程,2散列页表,Hashed Page Table 以页号作为参数形成散列值 散列表中每一项具有相同散列值，是一个链表。 每个链表元素由页号、对应的内存块号、指向链表中下个元素的指针组成。,图5-22 散列页表,3倒置页表,进程页表以逻辑地址的顺序排序，虚地址空间较大。 倒置页表按内存块号排序，每个内存块占有一个表项。每个表项包括存放在该内存块中页号和拥有该页面的进程标识符。系统只有一个页表。,图5-23 倒置页表,5.5.7 页面共享,图5-24 页面共享,可再入代码（或纯码，在其执行过程中本身不做任何修改的代码，通常由指令和常数

13、组成）。,分页式管理可实现页面共享,条件： 共享部分是纯码程序 共享部分与非共享部分，分页单独存放 共享部分的逻辑页号、物理页号完全相同,分页技术总结,优点：解决了碎片问题，便于管理 缺点： 实现共享有条件 不便于动态连接 未考虑程序逻辑构成,设页长为1K，程序地址字长为16位，用户程序空间和页表如图：,执行指令MOV r1，2500，地址转换步骤说明,取出程序地址字2500送虚地址寄存器VR 由硬件分离页号P和页内地址W：页长为1K，所以页内地址占10位（09位），页号占6位（1015位） 硬件取出VR寄存器中的高6位即页号，低10位即页内地址，得到页号P=2，页内位移W=452 根据页号P

14、=2，硬件自动查该进程页表，找到第2页对应块号为7，将块号送到内存地址寄存器MR的高10位中，将VR中W值452复制到MR低10位中，形成内存地址。 系统就以MR中的地址访问内存,计算分页地址时要注意： 给出地址字的进制 地址的空间长度 页长 逻辑空间允许的最大页数,5.6 分 段 技 术,5.6.1 分段存储管理的基本概念,分页存储管理存在问题导致程序在用户角度的内存空间和实际内存空间不同。,用户角度的内存,段（segmentation）用户角度的内存管理模式,逻辑地址空间是段的集合 当用户程序被编译时，编译程序自动构建程序的分段，比如：pascal编译器,局部变量,1分段,按程序自身的逻辑

15、关系划分为若干个程序段 段名 段长 段号：段号从0开始排 段内地址：从0开始编址，段内地址连续,图5-25 分段地址空间,2分段程序的逻辑地址,逻辑地址：段号s + 段内地址d。 分段存储，进程逻辑地址空间是二维的。,图5-26 分段技术地址结构,3内存分配,内存以段为单位分配，每段占用一块连续的内存分区。各分区的大小由对应段的大小决定。 最大段长（分区大小） 最多段数 （一个进程拥有最多分区数）,4段地址映射,段表 系统为每个进程建一个段表。每个段是段表的一项，段表项中包含段号、段长和段起始地址。 段表基址寄存器 系统建立一个段表地址寄存器（段表首址+段表长度）。,逻辑地址：第2段，第7个字

16、节,图5-27 分段地址转换,5.6.2 地址转换,5.6.3 段的共享和保护,1段的共享 在段一级实现，共享信息可以设成一段。 可以只共享部分程序。,图5-28 分段系统中段的共享,2段的保护,段的保护措施包括以下三种： 存取控制（R/W/RW） 段表本身可起保护作用。 表项中设置该段的长度限制 段长限制，段表地址寄存器中有段表长度的信息。 保护环（进程优先权由所在环决定）,5分页和分段的主要区别, 页是信息的物理单位。段是信息的逻辑单位。 页大小由系统确定，段长因段而异。 分页地址空间是一维的。分段的地址空间是二维的。 分页系统很难实现过程和数据的分离。分段系统可以。 各段长度不一，难以统一管理。 引入段页式管理,5.7 段页式技术,5.7.1 段页式存储管理的基本原理,图5-29 段页式存储逻辑地址结构,5.7.2段页式地址转换过程,段号加段表寄存器中的段表首址该段页表首址+页表长度 页表长度比较越界发中断， 取页号加页表基址对应页号项，读出页