操作系统讲稿内存管理课件

1、第四章第四章 内存管理内存管理 主存储器是仅次于主存储器是仅次于CPU的宝贵资源。的宝贵资源。 众多进程共用一个存储器，必然涉及到存储器众多进程共用一个存储器，必然涉及到存储器 的分配、安全、利用率、共享以及扩展等诸多的分配、安全、利用率、共享以及扩展等诸多 问题。问题。 存储管理需要做的事情是：存储管理需要做的事情是： 将用户程序所用的地址空间转换为主存储器中的实将用户程序所用的地址空间转换为主存储器中的实 际地址空间，将用户程序的操作地址变换为存储器际地址空间，将用户程序的操作地址变换为存储器 上的具体位置。上的具体位置。 为存储空间提供安全和共享的手段。为存储空间提供安全和共享的手段。

2、为用户程序实现虚拟存储空间等。为用户程序实现虚拟存储空间等。 概述概述 DOS分区及分段分区及分段 Windows XP的存储器的存储器 Linux存储管理存储管理 实用系统中的存储管理方法实用系统中的存储管理方法 DOS分区及分段分区及分段 OS 用户区 扩展内存 0 640KB 1MB 主存储器被限制为主存储器被限制为 1MB的内存空间。的内存空间。 低端的低端的640KB的基的基 本内存。本内存。 高端的扩展内存。高端的扩展内存。 系统启动后将操作系系统启动后将操作系 统调入基本内存的低端统调入基本内存的低端 位置，大概占几十位置，大概占几十KB 的空间。的空间。 基本内存的剩余部分便基

3、本内存的剩余部分便 是用来存放用户程序的是用来存放用户程序的 用户区。用户区。 在在DOS发展的后期，已发展的后期，已 经可以利用扩展内存来经可以利用扩展内存来 存放系统的数据结构、存放系统的数据结构、 驱动程序以及某些库文驱动程序以及某些库文 件等内容，但用户不能件等内容，但用户不能 对扩展存储器中的内容对扩展存储器中的内容 进行修改。进行修改。 程序和数据不能突程序和数据不能突 破基本内存的限制，因破基本内存的限制，因 此，用户程序的大小必此，用户程序的大小必 须低于须低于640KB。 用户区内只能存放用户区内只能存放 一个用户程序，因此，一个用户程序，因此， DOS系统只支持单道程系统只

4、支持单道程 序。序。 Windows xp的存储器的存储器 Windows xp要求存储器最低为要求存储器最低为64MB。 内存被划分为大小为内存被划分为大小为4KB的页面。内存中可以存放多个用的页面。内存中可以存放多个用 户任务的页面，因此，户任务的页面，因此，Windows支持多任务同时运行。支持多任务同时运行。 用户在编制程序时，其大小最高可达用户在编制程序时，其大小最高可达4GB，但在程序运行，但在程序运行 时，并不是全部程序都装入内存，而是只装入程序的部分时，并不是全部程序都装入内存，而是只装入程序的部分 页面来运行。页面来运行。 当需要装入新的程序页面而内存中又没有足够的空闲区当需

5、要装入新的程序页面而内存中又没有足够的空闲区 域时，操作系统将内存中长期未使用的页面换出到辅助存域时，操作系统将内存中长期未使用的页面换出到辅助存 储器上早已安排的页面（储器上早已安排的页面（paging file）文件中，腾出空间）文件中，腾出空间 后再将需要换进的页面调入。后再将需要换进的页面调入。 Windows 支持虚拟存储器。支持虚拟存储器。 Windows xp的存储器的存储器 页页 面面 在在 内内 存存 中中 换换 出出 换换 进进 Page Faults/sec 是每秒是每秒 钟发生页面缺失的平均钟发生页面缺失的平均 数量。页面缺失将直接数量。页面缺失将直接 导致页面换进。导

6、致页面换进。 Pages Input/sec 是从磁是从磁 盘换进页面的速度。盘换进页面的速度。 当一个进程引用一个虚当一个进程引用一个虚 拟内存的页面，而此页拟内存的页面，而此页 面不存在于内存，就会面不存在于内存，就会 发生页面缺失。发生页面缺失。 Pages Output/sec 是指是指 为了释放物理内存空间为了释放物理内存空间 而将页面写入磁盘的速而将页面写入磁盘的速 度。度。 当物理内存不足时，当物理内存不足时， Windows 会将页面写回会将页面写回 到磁盘以便释放空间。到磁盘以便释放空间。 出页的峰值往往与进页出页的峰值往往与进页 峰值接近。峰值接近。 说明出页多是因为有进说

7、明出页多是因为有进 页需求，即只有当内存页需求，即只有当内存 中没有可分配空间，同中没有可分配空间，同 时又必须调入内存新的时又必须调入内存新的 页面时，才需要换出页页面时，才需要换出页 面。面。 Windows xp的存储器的存储器 可可 用用 物物 理理 内内 存存 Available MBytes 是计是计 算机上运行的进程的可算机上运行的进程的可 用物理内存大小。它是用物理内存大小。它是 将零的、空闲的和备用将零的、空闲的和备用 内存列表的空间添加在内存列表的空间添加在 一起来计算的。一起来计算的。 Linux存储管理存储管理 Linux系统也是将存储器空间划分成页面，系统也是将存储器

8、空间划分成页面， 根据进程运行时的需要来对页面进行换进、根据进程运行时的需要来对页面进行换进、 换出的。换出的。 同样在磁盘上也安排了交换区来与内存同样在磁盘上也安排了交换区来与内存 协调工作，以达到扩大内存的目的。协调工作，以达到扩大内存的目的。 但是但是Linux系统的交换区多采用在硬盘上系统的交换区多采用在硬盘上 划分出一个指定区域来作为交换区，因此，划分出一个指定区域来作为交换区，因此， 交换区的大小不可变化。交换区的大小不可变化。 4.1 内存管理功能内存管理功能 用户实体与存储空间用户实体与存储空间 分配、释放及分配原则分配、释放及分配原则 地址映射地址映射 虚拟存储器虚拟存储器

9、存储保护与共享存储保护与共享 存储区整理存储区整理 用户实体与存储器的关系用户实体与存储器的关系 n任务任务在被激活之前在被激活之前存放在辅助存储器存放在辅助存储器上。上。 n当任务被激活时，它成为当任务被激活时，它成为进程进入主存储器进程进入主存储器。 n进程的描述进程的描述部分部分及主程序及主程序部分始终存放于部分始终存放于主存储器主存储器， 其他其他程序和数据部分视需要由操作系统程序和数据部分视需要由操作系统在内存与外存之在内存与外存之 间交换间交换。 n当用户向计算机当用户向计算机提交提交自己的自己的任务任务时，存储管理是以一时，存储管理是以一 种种逻辑形式逻辑形式来进行描述。来进行描

10、述。 n而当操作系统而当操作系统处理处理用户的用户的任务任务时，是对具体的时，是对具体的存储器存储器 地址进行操作。地址进行操作。 n存储管理存储管理的工作就是圆满地处理发生在的工作就是圆满地处理发生在衔接逻辑和物衔接逻辑和物 理存储理存储时所产生的各种问题。时所产生的各种问题。 存储空间与存储地址存储空间与存储地址 概念：概念： 逻辑地址逻辑地址 逻辑地址空间逻辑地址空间 物理地址物理地址 物理地址空间物理地址空间 用户的每一条程序指令要访问的数据都用户的每一条程序指令要访问的数据都 有一个对应的地址，这个地址被称为有一个对应的地址，这个地址被称为逻逻 辑地址辑地址。 由于它是相对于由于它是

11、相对于0的地址，因此又被称的地址，因此又被称 为为相对地址相对地址。 当用户程序被编译为当用户程序被编译为目标代码目标代码时也使用时也使用 的是相对地址。的是相对地址。 原则上讲，因此用户可以无限制地加长原则上讲，因此用户可以无限制地加长 自己的程序。自己的程序。 在具体应用中在具体应用中相对地址的大小受相对地相对地址的大小受相对地 址寄存器位数的限制址寄存器位数的限制，如在，如在Windows 中中 相对地址寄存器为相对地址寄存器为32位，表示相对地址位，表示相对地址 最大可达最大可达4GB。 逻辑地址空间可以逻辑地址空间可以定义定义为：实体（用户、为：实体（用户、 作业、任务、进程或程序）

12、所用的所有作业、任务、进程或程序）所用的所有 逻辑地址的集合逻辑地址的集合。 不同的操作系统赋予逻辑地址空间不同不同的操作系统赋予逻辑地址空间不同 的表现形式，它的大小也是可以确定的。的表现形式，它的大小也是可以确定的。 用户可以直接对逻辑地址和逻辑地址空用户可以直接对逻辑地址和逻辑地址空 间进行访问和操作间进行访问和操作。 逻辑地址空间又称为逻辑地址空间又称为相对地址空间相对地址空间，有，有 时候也被简称为用户空间或者作业空间。时候也被简称为用户空间或者作业空间。 逻辑地址空间的大小被限制在逻辑地址空间的大小被限制在0到相对到相对 地址最大值之间。地址最大值之间。 内存中的实际地址被称为物理

13、地址。内存中的实际地址被称为物理地址。 由于它并不和任何相对地址相关，因由于它并不和任何相对地址相关，因 此，物理地址又称为绝对地址。此，物理地址又称为绝对地址。 物理地址的最小值为物理地址的最小值为0，最大值取决，最大值取决 于内存的大小和内存地址寄存器的所于内存的大小和内存地址寄存器的所 能表现的最大值，二者中较小的那一能表现的最大值，二者中较小的那一 个值为物理地址的最大值。个值为物理地址的最大值。 物理地址空间可以定义为：当逻辑地物理地址空间可以定义为：当逻辑地 址空间址空间被映射到内存被映射到内存时所对应的物理时所对应的物理 地址的集合。地址的集合。 物理地址空间又称为物理地址空间又

14、称为绝对地址空间绝对地址空间。 物理地址空间并不是指物理内存，只物理地址空间并不是指物理内存，只 有当逻辑地址空间存在时，才会有物有当逻辑地址空间存在时，才会有物 理地址空间。理地址空间。 物理地址空间受存储器大小的限制，物理地址空间受存储器大小的限制， 也就是说物理地址空间最大只能达到也就是说物理地址空间最大只能达到 内存的大小。内存的大小。 一、地址重定位一、地址重定位 mov AL, nn mov AL, nn 逻辑空间 0 内存 m nn L nn+m L+m 装入后的作业并不能立即运行，装入后的作业并不能立即运行， 因为作业中每一个指令要访问的因为作业中每一个指令要访问的 地址依然是

15、地址依然是相对地址相对地址，相对地址，相对地址 是逻辑地址空间中的地址，并不是逻辑地址空间中的地址，并不 是内存中的实际地址，因此不能是内存中的实际地址，因此不能 够访问。够访问。 装入是指将逻辑地址空间安装入是指将逻辑地址空间安 排到内存中具体的物理位置上。排到内存中具体的物理位置上。 装入针对的是整个逻辑地址空装入针对的是整个逻辑地址空 间。间。 1.装入装入 mov AL, nn mov AL, nn+m 逻辑空间 0 内存 m nn L nn+m L+m 2.地址映射地址映射 对于指令要访问的地址进行相对对于指令要访问的地址进行相对 地址到绝对地址的变换，就是地地址到绝对地址的变换，就

16、是地 址映射。址映射。 地址映射就是将逻辑地址空间中地址映射就是将逻辑地址空间中 的地址映射到物理地址空间中去。的地址映射到物理地址空间中去。 采用的办法为重定位。采用的办法为重定位。 1.装入程装入程 序序 在装入过程完成后，根据装入的起始位在装入过程完成后，根据装入的起始位 置来修改程序中指令要访问的地址，将置来修改程序中指令要访问的地址，将 相对地址改为绝对地址就是重定位。相对地址改为绝对地址就是重定位。 绝对地址绝对地址 （BR）相对地址）相对地址 根据不同的根据不同的地址修改时间地址修改时间可可 将重定位划分为将重定位划分为静态静态重定位重定位 和和动态动态重定位。重定位。 2.重定

17、位：重定位： 静态重定位静态重定位 动态重定位动态重定位 mov AL, nn mov AL, nn+m 逻辑空间 0 内存 m nn L nn+m L+m 静态重定位是在装入过程完成后在静态重定位是在装入过程完成后在程序运行程序运行 前前，一次一次将所有的指令要访问的地址全部修改将所有的指令要访问的地址全部修改 为绝对地址，在程序运行过程中不再修改。为绝对地址，在程序运行过程中不再修改。 静态重定位要求程序一旦装入其静态重定位要求程序一旦装入其绝对地址空间绝对地址空间 就就不能发生变化不能发生变化了。了。 mov AL, nn m nn+m nn + mov AL, nn m L+m 0 L

18、 nn 逻辑空间 L 基址寄存器 L 地址寄存器 内存 L 动态重定位是在程序的动态重定位是在程序的运行过程运行过程中，当指令需中，当指令需 要执行时对将要访问的要执行时对将要访问的地址地址进行进行修改修改。 动态重定位动态重定位允许允许在在程序运行过程程序运行过程中，其中，其绝对地绝对地 址址空间发生变化或被分割为不同的区域，空间发生变化或被分割为不同的区域，变化变化后后 只需要将基地址寄存器中的内容作对应修改。只需要将基地址寄存器中的内容作对应修改。 采用静态重定位方式的采用静态重定位方式的主要优点主要优点是：是： （1）可以在一般机器上全部用）可以在一般机器上全部用。 （2）装入程序可以

19、实现）装入程序可以实现。 静态重定位方式静态重定位方式主要缺点主要缺点是：是： （1）执行期间程序）执行期间程序在主存储器中在主存储器中， 所以对提高主存储器的利用率不利。所以对提高主存储器的利用率不利。 （2）若程序空间大于被分配的物理空间，）若程序空间大于被分配的物理空间， 由程序员自行采取某种手段来由程序员自行采取某种手段来问题，问题， 如采用覆盖结构。如采用覆盖结构。 （3）用户）用户已经存放在主存中的同已经存放在主存中的同 一个程序，如果几个用户要使用同一个程序，一个程序，如果几个用户要使用同一个程序， 则每个用户必须在各自的主存空间中存放一则每个用户必须在各自的主存空间中存放一 个

20、程序副本。个程序副本。 采用动态重定位方式的采用动态重定位方式的主要优点主要优点有：有： （1）在程序开始执行之前，）在程序开始执行之前，不不一定要一定要把整把整 个程序个程序都都调入调入到主存中。一个程序可以被分到主存中。一个程序可以被分 配在多个配在多个不连续不连续的主存物理空间内，以提高的主存物理空间内，以提高 主存储器的利用率。主存储器的利用率。 （2）几个程序）几个程序可以共享可以共享存放在主存中的同存放在主存中的同 一个程序段。一个程序段。 （3）支持）支持虚拟虚拟存储器。存储器。 动态重定位方式的动态重定位方式的主要缺点主要缺点有：有： （1）需要有）需要有硬件支持硬件支持。 （

21、2）实现存储管理的软件算法）实现存储管理的软件算法比较复杂比较复杂。 二、二、 内存分配与回收内存分配与回收 1.存储分配存储分配 2.存储释放存储释放 3.分配原则分配原则 在设计分配程序时需要考虑诸多因素: (1)内存空间的划分 (2)数据结构的确定 (3)作业空间的划分 (4)淘汰算法 (5)分配算法 存储分配实际上是将作存储分配实际上是将作 业的逻辑地址空间映射成业的逻辑地址空间映射成 为内存中的物理地址空间。为内存中的物理地址空间。 内存中有许多尚未使用内存中有许多尚未使用 的区域即自由区都可以被的区域即自由区都可以被 分配，但到底选择哪一自分配，但到底选择哪一自 由区必须依据分配算

22、法来由区必须依据分配算法来 确定。确定。 存储释放实际上是解除存储释放实际上是解除 逻辑地址空间与物理地址逻辑地址空间与物理地址 空间的联系，并释放物理空间的联系，并释放物理 空间。空间。 存储释放程序将回收的存储释放程序将回收的 内存区域重新设定为自由内存区域重新设定为自由 区，并将其安排进入自由区，并将其安排进入自由 区队列。进入自由区队列区队列。进入自由区队列 的具体位置也必须依据分的具体位置也必须依据分 配算法。配算法。 三、三、 存储保护与共享存储保护与共享 存储保护就是要保护进程的数据不被非法访存储保护就是要保护进程的数据不被非法访 问者破坏。问者破坏。 （1）界地址寄存器保护法）

23、界地址寄存器保护法 （2）访问授权保护）访问授权保护 （1）界地址寄存器保护法）界地址寄存器保护法 采用硬件：采用硬件： 基地址寄存器基地址寄存器BR 长度寄存器长度寄存器LR 采用软件：采用软件： 地址寄存器指令中逻辑地址 出错 （地址寄存器） （基址寄存器）？ 否 是 （地址寄存器） （基址寄存器）+ （长度寄存器）？ 运行指令 当进程之间需要共享当进程之间需要共享 某些数据时，使用界地址某些数据时，使用界地址 寄存器就表现得无能为力。寄存器就表现得无能为力。 （2）访问授权保护）访问授权保护 分区号 访问权 1 2 2 0 3 1 1 0 P1 P2 进程访问权 当进程访问某个区域时，若

24、进程的当进程访问某个区域时，若进程的访问权限大于等访问权限大于等 于被访问区域的权限值于被访问区域的权限值，访问可以进行，否则视为，访问可以进行，否则视为 非法。非法。 系统为每一个系统为每一个存储区域存储区域都给都给 定一个定一个访问权限值。访问权限值。 同时也为每一个同时也为每一个进程进程赋予一赋予一 个个访问权限值访问权限值。 一个进程可以对不同存储区域有一个进程可以对不同存储区域有 不同的访问权限；不同的访问权限； 一个存储区域也可以被多个具有一个存储区域也可以被多个具有 不同访问权限的进程按权限级别进不同访问权限的进程按权限级别进 行访问。行访问。 访问授权保护还有一个好处是它访问授

25、权保护还有一个好处是它 允许存储区域的共享。允许存储区域的共享。 四、四、 虚拟存储器虚拟存储器 (1)实际内存空间实际内存空间 (2)辅助存储器上的内存交换区辅助存储器上的内存交换区 (3)虚拟地址虚拟地址 (4)换进、换出机制换进、换出机制 虚拟存储器是将内存进行虚拟，使用户能使用虚拟存储器是将内存进行虚拟，使用户能使用 比实际内存大得多的虚拟空间。比实际内存大得多的虚拟空间。 要实现虚拟内存必须具备如下条件：要实现虚拟内存必须具备如下条件： 目前的操作系统几乎目前的操作系统几乎全部全部具具 备虚拟存储器功能，虽然不同的备虚拟存储器功能，虽然不同的 系统其实现虚拟存储器的系统其实现虚拟存储

26、器的基本条基本条 件都相似件都相似，但在数据的换进、换，但在数据的换进、换 出出策略上是可以不同策略上是可以不同的。的。 存储区整理存储区整理 当系统运行一段时间后，可能出现如下当系统运行一段时间后，可能出现如下问题问题： 产生许多产生许多碎片碎片； 进程过分进程过分分散存储分散存储； 换进、换出的次数过多，导致系换进、换出的次数过多，导致系 统统运行缓慢运行缓慢； 不断不断“内存空间不够内存空间不够”。 存储区存储区需要整理需要整理。 存储器的存储器的整理方法整理方法： （1）定期将内存中的）定期将内存中的碎片合并；碎片合并； （2）将某些）将某些进程进程的分散存储区域的分散存储区域移动移动

27、到一起。到一起。 经过经过整理后整理后 系统中有更大的自由分区，系统中有更大的自由分区，提高提高存储管理的存储管理的效效 率率； 在整理时中断所有进程，并且需要在整理时中断所有进程，并且需要消耗较多的消耗较多的 CPU时间时间。 4.2 分区管理分区管理 单一分区分配方式单一分区分配方式 多重固定分区分配方式多重固定分区分配方式 多重动态分区分配方式多重动态分区分配方式 伙伴系统伙伴系统 一、单一连续分配方式一、单一连续分配方式 1.原理原理 连续的用户逻连续的用户逻 辑地址空间，辑地址空间， 经过装入程序经过装入程序 直接装入分区直接装入分区 的低地址部分的低地址部分 的单一的连续的单一的连

28、续 的区域。的区域。 OS 作业空间 内存 用 户 区 2.分配与释放分配与释放 入口（作业逻辑空间） 出错： 内存不够 逻辑空间用户区？ 否 是 装入作业 3.地址映射地址映射 采用采用静态重定位静态重定位的方式在作业装入时的方式在作业装入时 一次性对所有指令将要访问的地址进行一次性对所有指令将要访问的地址进行 修改。修改。 由于作业的物理地址空间由于作业的物理地址空间不不会发生会发生变变 化化，因此，单一连续分区，因此，单一连续分区不适合不适合使用使用动动 态重定位态重定位。 4.存储保护存储保护 使用界地址寄存器保护法界地址寄存器保护法。其中，基 址寄存器的内容是操作系统常驻内存部 分以

29、后的首地址，长度寄存器的内容便 是用户可用区域的长度。 由于操作系统不会发生变化，甚至可甚至可 以不使用界地址寄存器以不使用界地址寄存器，而将基址和长 度用两个常量来代替 。 5.单一连续分区的优缺点单一连续分区的优缺点 （1）管理简单。管理简单。 （2）使用安全。）使用安全。 （3）不需要任何附加的硬件设备。）不需要任何附加的硬件设备。 （1）作业的大小受用户区大小的限制。作业的大小受用户区大小的限制。 （2）不支持多用户。）不支持多用户。 （3）容易造成系统资源的浪费。）容易造成系统资源的浪费。 二、多重固定二、多重固定分区分配方式分区分配方式 区号 大小 起始地址 状态 0 20K 40

30、K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作业号 大小 区号 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作业表 内存分区表 OS 作业 1 作业 0 ： ： 作业 2 ： ： ： 0 区 1 区 2 区 5 区 4 区 内存 将内存空间由小到大将内存空间由小到大 划分为若干个划分为若干个位置固定大位置固定大 小不等小不等的区域，每个区域的区域，每个区域 可以存放一个作业，存放可以存放一个作业，存放 于不同区域的于不同区域的作业可以并作业可以并 行行。 用户逻辑地址空间

31、依用户逻辑地址空间依 然是一个连续的整体，在然是一个连续的整体，在 作业申请进入内存时作业申请进入内存时一次一次 性装入性装入。 描述内存中每一个区描述内存中每一个区 域的情况域的情况 描述存放于区域中的描述存放于区域中的 作业作业 地址映射地址映射 由于作业被分配进入内存后位置不再发生变化，因此，由于作业被分配进入内存后位置不再发生变化，因此， 地址映射可以采用地址映射可以采用静态重定位静态重定位方法。不过我们要注意到方法。不过我们要注意到 每一个作业的物理地址空间的起始位置是不相同的，因每一个作业的物理地址空间的起始位置是不相同的，因 此，对每一个作业进行重定位时要修正基址寄存器的值。此，

32、对每一个作业进行重定位时要修正基址寄存器的值。 存储保护存储保护 存储保护可以采取存储保护可以采取界地址寄存器界地址寄存器的方法和的方法和访问授权访问授权 保护保护，由于作业在内存中的位置保持不变，可以用两个，由于作业在内存中的位置保持不变，可以用两个 常量替代界地址寄存常量替代界地址寄存。 优缺点：优缺点： （1）提高了）提高了CPU的的利用率利用率。 （2）作业大小受到最大分）作业大小受到最大分 区大小的区大小的限制限制。 （3）空间）空间浪费浪费。 （4）碎片碎片问题。问题。 三、三、 可变分区分配方式可变分区分配方式 自由分区表 起始地址 大小 作业号 40K 55K 0 95K 10

33、K 1 210K 150K 2 ： ： ： 已使用分区表 OS 作业 0 40K 作业 0 作业 2 80 内存 60K 40K 95K 105K 210K 150K 360K 起始地址 大小 105K 40K 150K 60K 360K 80K ： ： 40K 80 60K 自由分区链 根据作业对内存空间根据作业对内存空间 的申请来划分主存区的申请来划分主存区 域，区域的域，区域的大小可变大小可变 、位置可变位置可变、数量也数量也 可变可变 描述已被分配的区域描述已被分配的区域 描述内存中的自由区域描述内存中的自由区域 为每一个为每一个自由分区自由分区设置一设置一 个个链接链接指针来指向下一

34、个指针来指向下一个 自由分区，使所有的自由自由分区，使所有的自由 分区形成一个链表分区形成一个链表 多重分区分配与释放多重分区分配与释放 20K 80K 60K 40K 120K 20K 25K 60K 40K 120K 20K 80K 60K 40K 120K 20K 80K 5K 40K 120K 20K 80K 60K 40K 120K 20K 80K 60K 40K 65K 55K 作业空间 （a）最先适应算法 （b）最佳适应算法 （c）最坏适应算法 将作业分配到内存中将作业分配到内存中第一第一 个碰到个碰到的大于或等于作业的大于或等于作业 申请空间的未分配区。申请空间的未分配区。 将

35、作业申请大小与内存中将作业申请大小与内存中 所有未分配区的大小进行所有未分配区的大小进行 比较，直到找到比较，直到找到最小的最小的大大 于或等于作业空间的区分于或等于作业空间的区分 配给作业。配给作业。 将作业申请大小与内存中将作业申请大小与内存中 所有未分配区的大小进行所有未分配区的大小进行 比较，直到找到比较，直到找到最大的最大的大大 于或等于作业空间的区分于或等于作业空间的区分 配给作业。配给作业。 算法简单但分配比较盲目算法简单但分配比较盲目 ，可能造成较小的作业分，可能造成较小的作业分 割了较大的空间，使大作割了较大的空间，使大作 业无法被分配。业无法被分配。 优先使用小的自由空间，

36、优先使用小的自由空间， 但每次分配以后的剩余空但每次分配以后的剩余空 间可能变得过小而成为碎间可能变得过小而成为碎 片。片。 使用大的自由空间，在进使用大的自由空间，在进 行分割后剩余空间还可以行分割后剩余空间还可以 被使用，但也使大的自由被使用，但也使大的自由 空间无法保留给需要大空空间无法保留给需要大空 间的作业。间的作业。 另外可以有：另外可以有： 最佳适应算法也是最先适应最佳适应算法也是最先适应 算法算法 最坏适应算法也是最先适应最坏适应算法也是最先适应 算法算法 如何实现？如何实现？ 几种方法比较几种方法比较 4.4.地址映射地址映射 动态分区采用动态分区采用动态重定位动态重定位方式

37、来实现地址映射，方式来实现地址映射， 这样作业的基地址发生变化也不会影响执行。这样作业的基地址发生变化也不会影响执行。 当作业被选择当作业被选择运行时运行时，其物理空间，其物理空间起始地址起始地址被装入被装入 基地址寄存器中，基地址寄存器中，CPUCPU每执行一条指令之前每执行一条指令之前重定位硬件重定位硬件 对指令要访问的地址进行修改。对指令要访问的地址进行修改。 5.5.存储保护存储保护 存储保护可以采用存储保护可以采用界地址寄存器界地址寄存器的方法和访问授权保的方法和访问授权保 护，不过由于作业被分配于内存一个连续的区域中，护，不过由于作业被分配于内存一个连续的区域中，访访 问授权保护问

38、授权保护的的作用作用似乎似乎并不大并不大，因为作业并没有对其他，因为作业并没有对其他 作业空间的访问权力。作业空间的访问权力。 6.6.存储区整理存储区整理 经过不断地分配和释放后，内存中自由分区会变得经过不断地分配和释放后，内存中自由分区会变得 越来越多和越来越小，这就使很多小自由分区成为越来越多和越来越小，这就使很多小自由分区成为 碎片碎片。 可以用可以用紧缩紧缩的方法来解决碎片。的方法来解决碎片。紧缩是紧缩是将内存中已将内存中已 使用区域经过移动沉淀到低地址部分，从而使碎片使用区域经过移动沉淀到低地址部分，从而使碎片 浮动浮动到内存的高地址部分合并成较大的可使用空间。到内存的高地址部分合

39、并成较大的可使用空间。 用紧缩方法来消除碎片需要占用大量的用紧缩方法来消除碎片需要占用大量的CPUCPU时间，并时间，并 且在移动过程中稍有且在移动过程中稍有不慎不慎就有可能就有可能破坏破坏全部数据。全部数据。 7.7.多重动态分区的优缺点多重动态分区的优缺点 （1 1）多道程度得以提高。）多道程度得以提高。 （2 2）提高了内存的利用率。）提高了内存的利用率。 （3 3）作业大小依然受内存容量的限制。）作业大小依然受内存容量的限制。 （4 4）对碎片问题的解决需要以增加系统开销为代价。）对碎片问题的解决需要以增加系统开销为代价。 （5 5）不便共享。）不便共享。 举例：举例： 作业作业A要求

40、要求18KB；作业；作业B要求要求25KB；作业；作业C要求要求30KB。 用首次适应算法、最佳适应算法来处理该作业序列，看哪种用首次适应算法、最佳适应算法来处理该作业序列，看哪种 算法合适。算法合适。 os 在使用在使用 在使用在使用 在使用在使用 30KB 5KB 46KB 0KB 20KB 100KB 20KB 160KB 210KB 256KB- -1 (1) 首次适应算法中的自由主存队列首次适应算法中的自由主存队列 (a) 首次适应算法中的自由主存队首次适应算法中的自由主存队 列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB o

41、s 在使用在使用 在使用在使用 在使用在使用 30KB 5KB 46KB 0KB 20KB 100KB 20KB 160KB 210KB 256KB- -1 (2) 最佳适应算法中的自由主存队列最佳适应算法中的自由主存队列 (b) 最佳适应算法中的自由主存队列最佳适应算法中的自由主存队列 160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB os 在使用在使用 在使用在使用 在使用在使用 30KB 5KB 46KB 0KB 20KB 100KB 20KB 160KB 210KB 256KB- -1 (a) 首次适应算法中的自由主存队首次适应算法中的

42、自由主存队 列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB (b) 最佳适应算法中的自由主存队最佳适应算法中的自由主存队 列列 160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 作业作业A要求要求18KB 作业作业B要求要求25KB 作业作业C要求要求30KB 4.3 4.3 分页存储管理方式分页存储管理方式 页式系统应解决的问题页式系统应解决的问题 分区存储管理的主要问题是碎片问题。分区存储管理的主要问题是碎片问题。 在采用分区存储管理的系统中，会形成在采用分区存储管理的系统中，会形成

43、 一些非常小的分区，最终这些非常小的分区一些非常小的分区，最终这些非常小的分区 不能被系统中的任何用户（程序）利用而浪不能被系统中的任何用户（程序）利用而浪 费。费。 造成这样问题的主要原因是用户程序装造成这样问题的主要原因是用户程序装 入内存时是整体装入的，为解决这个问题，入内存时是整体装入的，为解决这个问题， 提出了分页存储管理技术。提出了分页存储管理技术。 页式存储管理要解决如下问题页式存储管理要解决如下问题 页式存储管理系统的地址映射；页式存储管理系统的地址映射； 调入策略；调入策略； 淘汰策略；淘汰策略； 放置策略放置策略 一、一、 页式系统的基页式系统的基 本概念本概念 （1 1）

44、 页面页面 程序的地址空间被等程序的地址空间被等 分成大小相等的片，称为分成大小相等的片，称为 页面，又称为虚页。页面，又称为虚页。 （2 2） 主存块主存块 主存被等分成大小相主存被等分成大小相 等的片，称为主存块，又等的片，称为主存块，又 称为实页。称为实页。 （3 3） 页表页表 为了实现从地址空间到物理主存的映象，为了实现从地址空间到物理主存的映象， 系统建立的记录页与内存块之间对应关系的系统建立的记录页与内存块之间对应关系的 地址变换的机构称为页面映像表，简称页表。地址变换的机构称为页面映像表，简称页表。 0 1KB 0 1KB 2KB 3KB 1 主存主存 作业作业2地址空间地址空

45、间 2KB 3KB 4KB 5KB 6KB 7KB 8KB 9KB 10KB 1 0 1KB 2KB 1 作业作业1地址空间地址空间 0 1KB 1 作业作业3地址空间地址空间 05 16 页号页号块号块号 02 14 08 27 作业作业1页表页表 作业作业2页表页表 作业作业3页表页表 os os 分页映像存储的例分页映像存储的例 （4 4）虚地址结构）虚地址结构( (程序字程序字) ) 虚地址是用户程序中的逻辑地址，它包括页号和虚地址是用户程序中的逻辑地址，它包括页号和 页内地址（页内位移）。页内地址（页内位移）。 区分页号和页内地址的依椐是页的大小，页内地区分页号和页内地址的依椐是页的

46、大小，页内地 址占虚地址的低位部分，页号占虚地址的高位部分。址占虚地址的低位部分，页号占虚地址的高位部分。 假定页面大小假定页面大小1024字节，虚地址共占用字节，虚地址共占用2个字节个字节 (16位位) 页号页号 页内地址（位移量）页内地址（位移量） P W 15 10 9 0 （5） 页式地址变换页式地址变换 l 页式地址变换举例页式地址变换举例 作业作业2 2地址空间中，设地址空间中，设100100号单元处有如下指令：号单元处有如下指令： mov mov r1,2500r1,2500。当这条指令执行时，如何进行正确的地址变换。当这条指令执行时，如何进行正确的地址变换。 mov r1 ,

47、2500 123 0 1KB 1KB 3KB 1 作业作业2地址空间地址空间 2500 2 2* *1024 + 452 1024 + 452 p=2 w=452 p=2 w=452 0000100111000100 000010 0111000100 l 页式地址变换过程页式地址变换过程 000111 0111000100 15 10 9 0 页号页号P页内位移页内位移W 页表始址寄存器页表始址寄存器 mov r1 , 2500 123 0 1KB 2KB 3KB 1 作业作业2地址空间地址空间 + 02 14 27 页表页表 000010 0111000100 15 10 9 0 页号页号

48、P页内位移页内位移W 2500 0 1KB 主存主存 2KB 3KB 4KB 5KB 6KB 7KB 8KB 9KB 10KB 1 os os mov r1 , 2500 123 第第1页页 7*1024+452 =7620 l 页式地址变换的步骤页式地址变换的步骤 CPU给出操作数地址给出操作数地址(为为2500) ； 由分页机构自动地把逻辑地址分为两部分，由分页机构自动地把逻辑地址分为两部分， 得到页号得到页号p和页内相对位移和页内相对位移w (p =2， w =452)； 根据页表始址寄存器指示的页表始地址，以根据页表始址寄存器指示的页表始地址，以 页号为索引，找到第页号为索引，找到第2

49、页所对应的块号页所对应的块号(为为7) ； 最后，将块号最后，将块号b和页内位移量和页内位移量w拼接在一起，拼接在一起， 就形成了访问主存的物理地址就形成了访问主存的物理地址 (7*1024+452=7620)。 二、静态分页管理二、静态分页管理 1、分配与回收、分配与回收 l在静态分页管理时，作业的一页可分配在静态分页管理时，作业的一页可分配 到存储空间的任何一个可用的物理块中到存储空间的任何一个可用的物理块中 作业完成后，系统回收分配给该作业的作业完成后，系统回收分配给该作业的 内存块内存块 l作业完成后，系统回收分配给该作业的作业完成后，系统回收分配给该作业的 内存块内存块 2、优缺点、

50、优缺点 （1）管理）管理简单简单 （2）每访问一次内存数据需要经过）每访问一次内存数据需要经过二次寻址二次寻址。 （3）解决了）解决了碎片问题碎片问题。无无须内存碎片整理。须内存碎片整理。 （4）无无法实现法实现共享共享。 （5）作业大小受内存可用页面数的）作业大小受内存可用页面数的限制限制。 如果想在内存中运行较大的作业，则如果想在内存中运行较大的作业，则 必须必须利用内存以外的存储空间利用内存以外的存储空间。 例：有一系统采用页式存储管理，有一作业大小例：有一系统采用页式存储管理，有一作业大小 是是8KB8KB，页大小为，页大小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9

51、9、1010、5 5 块，试将虚地址块，试将虚地址71457145，34123412转换成内存地址。转换成内存地址。 虚地址虚地址 34123412 P P3412 3412 2048 2048 1 1 W W 3412 mod 20483412 mod 2048 13641364 MR=9MR=9* *2048+1364=197962048+1364=19796 虚地址虚地址34123412的内存地址的内存地址 是：是：1979619796 三、三、 请求分页管理请求分页管理 1.原理原理 内存 0 1 2 3 4 5 6 7 ： 作业空间 0 1 2 3 页表寄存器 页表 0 0 1 1

52、2 1 3 1 缺页状态 外存地址 内存块号 外存 与静态分页管理与静态分页管理不同不同 ： 按需分配。将按需分配。将需要需要运行运行 的页面的页面存放于内存存放于内存，暂时，暂时不不 需要需要运行的页面存放于辅存，运行的页面存放于辅存， 当需要运行当需要运行存放于辅存存放于辅存上的上的 页面时，再将对应的页面调页面时，再将对应的页面调 入内存。入内存。 注意页表变化注意页表变化 2.分配与分配与 淘汰算法淘汰算法 动态分动态分 配配 启动待执行指令 地址映射 缺页状态=0？ 是 否 页面装入 淘汰一个页面 获取相对地址 P、d 执行指令 指令地址+1 有空闲块？ 否 该页修改过？ 是 写回外

53、存 否 页面装入 缺页中断处理 分配与淘汰算法分配与淘汰算法淘汰算法淘汰算法 衡量淘汰算法依据：衡量淘汰算法依据： 所有页面访问次数 淘汰页面数 淘汰率 所有页面访问次数 缺页次数 缺页率 好的淘汰算法应该有好的淘汰算法应该有较低的缺页率和淘汰率。较低的缺页率和淘汰率。 0 2 4 3 1 0 5 2 7 8 1 6 4 0 5 8 4 2 7 6 4 3 1 * * * * * * * 0 3 5 8 4 2 1 2 1 4 0 7 6 * * * * * * * * * * 页面访问次序 最佳淘汰算法 缺页中断 最先淘汰算法 缺页中断 内存 块号 0 1 2 0 1 2 t 选择在最远的将

54、来才被访问的页面淘汰。选择在最远的将来才被访问的页面淘汰。 谁是最远的、将来才被访问的页面？选择最早进入内存的页面淘汰 这种方法包含一个假定：这种方法包含一个假定： 最早进入内存的页面就是目前最不会被使最早进入内存的页面就是目前最不会被使 用的页面。用的页面。 假定不成立？假定不成立？系统抖动！系统抖动！ 1 2 1 5 4 1 3 4 2 4 0 2 2 4 5 3 * * * 页面访问次序 最近最少使用算 法淘汰算法 缺页中断 CPU t 内存 块号 0 1 2 选择最近一段时间内最长时间未被使用选择最近一段时间内最长时间未被使用 的页面淘汰的页面淘汰 该算法的该算法的假定假定：长时间未使

55、用的页面不会马上被使用。：长时间未使用的页面不会马上被使用。 这正好符合内存这正好符合内存局部性原理局部性原理（内存中某个位置现在被（内存中某个位置现在被 访问，很快将再次被访问；某个位置现在被访问，其访问，很快将再次被访问；某个位置现在被访问，其 邻近位置也将被访问。）邻近位置也将被访问。） 问题：问题： 需要确定一个需要确定一个比较时间段比较时间段来反映哪一个页面长期未被来反映哪一个页面长期未被 使用，时间段使用，时间段过长过长时该算法将变为时该算法将变为先进先出先进先出算法，时算法，时 间段间段过短过短又会使系统频繁地记录访问次数并进行比较，又会使系统频繁地记录访问次数并进行比较， 从而

56、增加系统从而增加系统开销开销。 （4）最近未使用算法（）最近未使用算法（NRU） 块号 页号 访问位 修改位 ： i-1 p1 0 0 i p2 10 0 i+1 p3 0淘汰 1回写 i+2 p4 1 1 ： 页面选择指针 入口 访问位=0 访问位=0？ 否 是 页面淘汰 申请页表 页面选择指针+1 返回 修改位=0？ 是 否 页面回写外存 选择页面选择指针遇到的选择页面选择指针遇到的 最近未被访问的页面淘汰。最近未被访问的页面淘汰。 简化的方法是：简化的方法是： 页面选择指针下移，只要遇到刚才页面选择指针下移，只要遇到刚才 未使用的页面就可以淘汰。未使用的页面就可以淘汰。 例例: : 某作

57、业有某作业有a,b,c,da,b,c,d四个页面四个页面, ,作业在运行过程中的访作业在运行过程中的访 问次序为问次序为:a,b,c,a,d,a,:a,b,c,a,d,a,试计算采用试计算采用FIFOFIFO和和LRULRU淘汰算法淘汰算法, , 各会产生几次缺页中断各会产生几次缺页中断?(?(注：系统为该作业分配个内注：系统为该作业分配个内 存块存块) ) 缺页中断 次数 淘汰的 页面 进入主存 的页面 1-a 2-B 3-C 4ad 5ba 缺页中断 次数 淘汰的 页面 进入主存 的页面 1-a 2-b 3-c 4bd LRU LRUFIFOFIFO 举例举例 FIFO算法的异常现象算法的

58、异常现象(Belady) 设进程共有设进程共有8页页,且已在内存中分配有且已在内存中分配有3个页个页 面面,程序访问内存的顺序为程序访问内存的顺序为 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1. 求缺页次数和缺页率求缺页次数和缺页率, 当分配当分配4个页面时个页面时,缺页次数和缺页率为多缺页次数和缺页率为多 少少? 又进程又进程P有有5页页,访问串为访问串为 1,2,3,4,1,2,5,1,2,3,4,5.P分得分得3 个页面个页面,情况如何情况如何? 当分配当分配4个页面时个页面时,会出现什么会出现什么 情况情况? 虚拟存储器虚拟存储器 动态分页技术实现了虚拟存储器。

59、动态分页技术实现了虚拟存储器。 虚拟要素？虚拟要素？ 3.3.加速寻址加速寻址 二次寻址？二次寻址？ 一次寻址？一次寻址？ 页表长度 页框长度 内存 页表寄存器 表目长度 地址寄存器 中的逻辑地址 d P d 页表 P P 页框长度 快 速 页 表 举例举例 有一页式系统，页表放在主存中有一页式系统，页表放在主存中 如对主存的一次存取需如对主存的一次存取需1.5us，试问实现一次页面，试问实现一次页面 访问的存取时间是多少？访问的存取时间是多少？ 如系统有快表，平均命中率为如系统有快表，平均命中率为85%，当页表在快，当页表在快 表中时，查找时间忽略为表中时，查找时间忽略为0。此时的存取时间为

60、多。此时的存取时间为多 少？少？ 解：（解：（1）1.5*2=3us （2）0.85*1.5+（1-0.85） *2*1.5=1.725us。 4.4.分页管理的优缺点分页管理的优缺点 （1 1）管理简单。）管理简单。 （2 2）支持虚拟存储器。）支持虚拟存储器。 （3 3）无法实现共享。）无法实现共享。 作业空间按逻辑意义分割！作业空间按逻辑意义分割！ 4.4 段式管理段式管理 简单分段管理简单分段管理 请求分段管理请求分段管理 一、一、 基本概念基本概念 内存 作业空间 s0 s1 s2 s3 段表寄存器 段表 0 0 1 1 2 0 3 1 缺段状态 外存地址 内存地址 外存 段长 作业