操作系统第5章存储管理.ppt

《操作系统第5章存储管理.ppt》由会员分享，可在线阅读，更多相关《操作系统第5章存储管理.ppt（88页珍藏版）》请在金锄头文库上搜索。

1、第5章 存储管理,5.1 存储管理的功能 5.2 分区存储管理 5.3 覆盖与交换技术 5.4 页式管理 5.5 段式与段页式管理 5.6 本章小结,5.1 存储管理的功能 存储管理的功能如下: 1.主存空间的分配与回收 2.地址转换 3.主存空间的共享和保护 4.主存空间的扩充,5.1.2 重定位 一.绝对地址和逻辑地址 内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的称为内存地址的编号相对应。显然，内存空间是一维线性空间。 二.虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性空间 1.虚拟空间的划分问题 2.把虚拟空间中已链接 和划分好的内容装入 内

2、存，并将虚拟地址 映射为内存地址的问题。,1. 静态地址重定位 在虚空间程序执行之前由装配程序完成地址映射工作. 静态重定位的优点是不需要硬件支持。 缺点: 不能移动 在程序执行之前将有关部分全部装入 必须占用连续的内存空间，这就难以做到程序和数据的共享。,2. 动态地址重定位 动态地址重定位（dynamic address relocation）是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。 地址重定位机构需要一个(或多个)基地址寄存器BR和一个(或多个)程序虚拟地址寄存器VR。指令或数据的内存地址MA与虚拟地址的关系为

3、: MA=(BR)+ (VR) 这里，(BR)与(VR)分别表示寄存器BR与VR中的内容。,图5.3 动态地址重定位,动态重定位的主要优点有: (1) 可以对内存进行非连续分配。 (2) 动态重定位提供了实现虚拟存储器的基础。 (3) 有利于程序段的共享。,5.1.3 内外存数据传输的控制 1.是用户程序自己控制:覆盖技术 2.是操作系统控制: 交换(swapping)方式 请求调入(on demand)方式和预调入(on prefetch)方式。,5.1.4 内存的分配与回收 几种策略和数据结构: 分配结构 (2) 放置策略 (3) 交换策略 (4) 调入策略。 (5) 回收策略,5.1.5

4、 内存信息的共享与保护 常用的内存信息保护方法有硬件法、软件法和软硬件结合三种。 1.上下界保护法是一种常用的硬件保护法,2.保护键法。,图5.5 保护键保护法,3.界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。 在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用的这种内存保护方式。,5.2 分区存储管理 5.2.1 分区管理基本原理 分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区,以连续存储各进程的程序和数据，使各进程得以并发执行。 按分区的时机，分区管理可以分为固定分区和动

5、态分区两种方法。,1. 固定分区法 把内存区固定地划分为若干个大小不等的区域。划分的原则由系统操作员或操作系统决定。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。 系统对内存的管理和控制通过数据结构分区说明表进行，,图5.6 固定分区法,2. 动态分区法 动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率,图5.7 内存初始分配情况,图5.8 内存分配变化过程,内存管理用数据结构: 可用分区表:每个表目记录一个空

6、闲区 可用分区自由链:查找比可用表困难，但不必占用额外的内存区。 请求表:请求表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。,图5.9 可用表、自由链及请求表,图5.10 固定分区分配算法,5.2.2 分区的分配与回收 1. 固定分区时的分配与回收,2. 动态分区时的分配与回收 动态分区时的分配与回收主要解决三个问题: (1) 对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。 (2) 分配空闲区之后，更新可用表或自由链。 (3) 进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。,动态分区时的分配方法： 最先适应法(first

7、 fit algorithm) 最佳适应法(best fit algorithm) 最坏适应法(worst fit algoriathm) (1) 最先适应法 按起始地址递增的次序排列 (2) 最佳适应算法 最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。 (3) 最坏适应算法 最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。,图5.11 最先适应算法,4. 几种分配算法的比较 思考：三种分配算法的各自特点 从查找速度、释放速度及空闲区的利用等三个方面对上述三种算法进行比较。,内存回收4种情况： 如果释放区与上下两空闲区相邻 如果释放区只与上空闲区相邻 如果释放区与下

8、空闲区相邻 如果释放区不与任何空闲区相邻,图5.12 空闲区的合并,5.2.3 有关分区管理其他问题的讨论 1. 关于虚存的实现 2. 关于内存扩充 3. 关于地址变换和内存保护 设CPU指令所要访问的虚拟地址为D 静态重定位:在上下限寄存器中值之间 动态重定位 若DVR (VR是限长寄存器中的限长值)，则说明地址越界 若D=VR，则该地址是合法的，由硬件完成对该虚拟地址的动态重定位。 保护键法也可用来对内存各分区提供保护。,4. 分区存储管理的主要优缺点 分区存储管理的主要优点如下: (1) 实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。 (2) 该方法要

9、求的硬件支持少，管理算法简单，因而实现容易。 主要缺点有: (1) 内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未用过的信息。而且，还存在着严重的碎小空闲区(碎片)不能利用的问题。 (2) 作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。 (3) 难以实现各分区间的信息共享。,5.3.1 覆盖技术 把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。 覆盖技术要求程序员提供一个清楚的覆盖结构，程序员负担较重。,5.3 覆盖与交换技术,图5.13 覆盖示例,5.3.2 交换技术 交换是指先将内存某部分的程序或数据写

10、入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。 交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或进程内进行。 交换进程由换出和换入两个过程组成。其中换出(swap out)过程把内存中的数据和程序换到外存交换区，而换入(swap in)过程把外存交换区中的数据和程序换到内存分区中。,1.各进程的虚拟空间被划分成若干个长度相等的页(page)。进程的虚地址变为页号p与页内地址的d所组成。 2.把内存空间也按页的大小划分为片或页面(page frame)。 3.用户进程在内存空间内除了在每个页面内地址连续之外，每个页面之间不再连续。 19 1

11、0 9 0 图5.14 页的划分,5.4 页 式 管 理 5.4.1 页式管理的基本原理,优点： 第一是实现了内存中碎片的减少，因为任一碎片都会小于一个页面。 第二是实现了由连续存储到非连续存储这个飞跃，为在内存中局部地、动态地存储那些反复执行或即将执行的程序和数据段打下了基础。,5.4.2 静态页面管理 静态页面管理方法在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的各个页面中，并通过页表(page mapping table)和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。,(1) 页表 最简单的页表由页号与页面号组成。页式管理时每个进程至少拥有一个页表。 图5

12、.15 基本页表示例,1. 内存页面分配与回收,(2) 请求表 请求表用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。请求表整个系统一张，如图5.16所示。 图5.16 请求表示例,(3) 存储页面表存储页面表也是整个系统一张，存储页面表指出内存各页面是否已被分配出去, 以及未分配页面的总数。 位示图 空闲页面链 图5.17 位示图,图5.18 页面分配算法流图,2. 分配算法,图5.19 页号与页面号 设每个页面长度为1K，指令LOAD 1，2500的虚地址为100，怎样通过图5.19所示页表来找到该指令所对应的物理地址呢?,3. 地址变换,图5.20 地址变换,取一个数据或指令至

13、少要访问内存两次以上 办法1：就是把页表放在寄存器中而不是内存中，但由于寄存器价格太贵，这样做是不可取的 办法2：是在地址变换机构中加入一个高速联想存储器，构成一张快表。在快表中，存入那些当前执行进程中最常用的页号与所对应的页面号，从而以提高查找速度。,静态页式管理 优点：解决了分区管理时的碎片问题。 缺点：在执行前全部装入内存 作业或进程的大小仍受内存可用页面数的限制,5.4.3 动态页式管理 分为请求页式管理和预调入页式管理。 共同点：请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。

14、其他部分则在执行过程中动态装入。 主要区别：在调入方式上 请求页式管理：当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其他的数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。 预调入方式：系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。,问题1：虚页不在内存中的-扩充页表的方法解决。增设该页是否在内存的中断位以及该页在外存中的副本起始地址。扩充后的页表如图5.21。 图5.21 加入中断处理后的页表,问题2：虚页不在内存时的处理。 第一，采用何种方式把所缺的页调入内

15、存。 -产生缺页中断信号，由中断处理程序做出相应的处理 第二，如果内存中没有空闲页面时，把调进来的页放在什么地方。 -置换算法 在页表中还应增加一项以记录该页是否曾被改变。增加改变位后的页表项如图5.22所示。,图5.22 加入改变位后的页表,图5.23 动态页式管理流图,置换算法 抖动(thrashing)现象：如果置换算法选择不当，有可能产生刚被调出内存的页又要马上被调回内存，调回内存不久又马上被调出内存，如此反复的局面。这使得整个系统的页面调度非常频繁，以致大部分时间都花费在主存和辅存之间的来回调入调出上。这种现象被称为抖动(thrashing)现象。,5.4.4 请求页式管理中的置换算

16、法 (1) 随机淘汰算法。 (2) 轮转法和先进先出算法。 由实验和测试发现FIFO算法和RR算法的内存利用率不高。 先进先出算法的另一个缺点是它有一种陷阱现象在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。,图5.24 FIFO算法的Belady现象,下面的例子可以用来说明FIFO算法的正常换页情况和Belady现象。例: 设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序(访问串)为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。 图5.25 Belady现象示例(1) 缺页率为12/17=70.5%,图5.26 Belady现象示例(2) 如果给进程P分配4个页面，共发生9次缺页，其缺页率为9/17=52.9%,设进程P可分为5页，访问串为1，2，3，4，1，2，5，1，2，3，4，5。当进程P分得3个页面时，执行过程中内存页面变化如