操作系统讲稿第四章内存管理

《操作系统讲稿第四章内存管理》由会员分享，可在线阅读，更多相关《操作系统讲稿第四章内存管理（100页珍藏版）》请在装配图网上搜索。

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

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

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

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

5、长期未使用的页面换出到辅助存域时，操作系统将内存中长期未使用的页面换出到辅助存储器上早已安排的页面（储器上早已安排的页面（paging file）文件中，腾出空间）文件中，腾出空间后再将需要换进的页面调入。后再将需要换进的页面调入。Windows 支持虚拟存储器。支持虚拟存储器。 Windows xp的存储器的存储器 页页面面在在内内存存中中换换出出换换进进 Page Faults/sec 是每秒是每秒钟发生页面缺失的平均钟发生页面缺失的平均数量。页面缺失将直接数量。页面缺失将直接导致页面换进。导致页面换进。 Pages Input/sec 是从磁是从磁盘换进页面的速度。盘换进页面的速度。当一

6、个进程引用一个虚当一个进程引用一个虚拟内存的页面，而此页拟内存的页面，而此页面不存在于内存，就会面不存在于内存，就会发生页面缺失。发生页面缺失。 Pages Output/sec 是指是指为了释放物理内存空间为了释放物理内存空间而将页面写入磁盘的速而将页面写入磁盘的速度。度。当物理内存不足时，当物理内存不足时，Windows 会将页面写回会将页面写回到磁盘以便释放空间。到磁盘以便释放空间。 出页的峰值往往与进页出页的峰值往往与进页峰值接近。峰值接近。说明出页多是因为有进说明出页多是因为有进页需求，即只有当内存页需求，即只有当内存中没有可分配空间，同中没有可分配空间，同时又必须调入内存新的时又必

7、须调入内存新的页面时，才需要换出页页面时，才需要换出页面。面。 Windows xp的存储器的存储器 可可用用物物理理内内存存Available MBytes 是计是计算机上运行的进程的可算机上运行的进程的可用物理内存大小。它是用物理内存大小。它是将零的、空闲的和备用将零的、空闲的和备用内存列表的空间添加在内存列表的空间添加在一起来计算的。一起来计算的。 Linux存储管理存储管理 Linux系统也是将存储器空间划分成页面，系统也是将存储器空间划分成页面，根据进程运行时的需要来对页面进行换进、根据进程运行时的需要来对页面进行换进、换出的。换出的。 同样在磁盘上也安排了交换区来与内存同样在磁盘上

8、也安排了交换区来与内存协调工作，以达到扩大内存的目的。协调工作，以达到扩大内存的目的。 但是但是Linux系统的交换区多采用在硬盘上系统的交换区多采用在硬盘上划分出一个指定区域来作为交换区，因此，划分出一个指定区域来作为交换区，因此，交换区的大小不可变化。交换区的大小不可变化。4.1 内存管理功能内存管理功能 n用户实体与存储空间用户实体与存储空间n分配、释放及分配原则分配、释放及分配原则n地址映射地址映射n虚拟存储器虚拟存储器n存储保护与共享存储保护与共享n存储区整理存储区整理 用户实体与存储器的关系用户实体与存储器的关系任务任务在被激活之前在被激活之前存放在辅助存储器存放在辅助存储器上。上

9、。当任务被激活时，它成为当任务被激活时，它成为进程进入主存储器进程进入主存储器。进程的描述进程的描述部分部分及主程序及主程序部分始终存放于部分始终存放于主存储器主存储器，其他其他程序和数据部分视需要由操作系统程序和数据部分视需要由操作系统在内存与外存之在内存与外存之间交换间交换。当用户向计算机当用户向计算机提交提交自己的自己的任务任务时，存储管理是以一时，存储管理是以一种种逻辑形式逻辑形式来进行描述。来进行描述。而当操作系统而当操作系统处理处理用户的用户的任务任务时，是对具体的时，是对具体的存储器存储器地址进行操作。地址进行操作。存储管理存储管理的工作就是圆满地处理发生在的工作就是圆满地处理发

10、生在衔接逻辑和物衔接逻辑和物理存储理存储时所产生的各种问题。时所产生的各种问题。存储空间与存储地址存储空间与存储地址概念：概念：逻辑地址逻辑地址逻辑地址空间逻辑地址空间物理地址物理地址物理地址空间物理地址空间用户的每一条程序指令要访问的数据都用户的每一条程序指令要访问的数据都有一个对应的地址，这个地址被称为有一个对应的地址，这个地址被称为逻逻辑地址辑地址。由于它是相对于由于它是相对于0的地址，因此又被称的地址，因此又被称为为相对地址相对地址。当用户程序被编译为当用户程序被编译为目标代码目标代码时也使用时也使用的是相对地址。的是相对地址。原则上讲，因此用户可以无限制地加长原则上讲，因此用户可以无

11、限制地加长自己的程序。自己的程序。在具体应用中在具体应用中相对地址的大小受相对地相对地址的大小受相对地址寄存器位数的限制址寄存器位数的限制，如在，如在Windows 中中相对地址寄存器为相对地址寄存器为32位，表示相对地址位，表示相对地址最大可达最大可达4GB。逻辑地址空间可以逻辑地址空间可以定义定义为：实体（用户、为：实体（用户、作业、任务、进程或程序）所用的所有作业、任务、进程或程序）所用的所有逻辑地址的集合逻辑地址的集合。不同的操作系统赋予逻辑地址空间不同不同的操作系统赋予逻辑地址空间不同的表现形式，它的大小也是可以确定的。的表现形式，它的大小也是可以确定的。用户可以直接对逻辑地址和逻辑

12、地址空用户可以直接对逻辑地址和逻辑地址空间进行访问和操作间进行访问和操作。逻辑地址空间又称为逻辑地址空间又称为相对地址空间相对地址空间，有，有时候也被简称为用户空间或者作业空间。时候也被简称为用户空间或者作业空间。逻辑地址空间的大小被限制在逻辑地址空间的大小被限制在0到相对到相对地址最大值之间。地址最大值之间。内存中的实际地址被称为物理地址。内存中的实际地址被称为物理地址。由于它并不和任何相对地址相关，因由于它并不和任何相对地址相关，因此，物理地址又称为绝对地址。此，物理地址又称为绝对地址。物理地址的最小值为物理地址的最小值为0，最大值取决，最大值取决于内存的大小和内存地址寄存器的所于内存的大

13、小和内存地址寄存器的所能表现的最大值，二者中较小的那一能表现的最大值，二者中较小的那一个值为物理地址的最大值。个值为物理地址的最大值。 物理地址空间可以定义为：当逻辑地物理地址空间可以定义为：当逻辑地址空间址空间被映射到内存被映射到内存时所对应的物理时所对应的物理地址的集合。地址的集合。物理地址空间又称为物理地址空间又称为绝对地址空间绝对地址空间。物理地址空间并不是指物理内存，只物理地址空间并不是指物理内存，只有当逻辑地址空间存在时，才会有物有当逻辑地址空间存在时，才会有物理地址空间。理地址空间。物理地址空间受存储器大小的限制，物理地址空间受存储器大小的限制，也就是说物理地址空间最大只能达到也

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.地址映射地址映射对于指令要访问的地址进行相对对于指令要访问的地址进行相对地址到绝对地址的变换，就是地地址到绝对地址的变换，就是地址映射。址映射。地址映射就是将逻辑地址空间中地址映射就是将逻辑地址空间中的地址映射到物理地址空间中去。的地址映射到物理地址空间中去。采用的办法为重定位。采用的办法为重定位。 1.装入程装入程序序 在装入过程完成后，根据装入的起始位在装入过程完成后，根据装入的起始位置来修改程序中指令要访问的地址，将置来修改程序

16、中指令要访问的地址，将相对地址改为绝对地址就是重定位。相对地址改为绝对地址就是重定位。绝对地址绝对地址 （BR）相对地址）相对地址 根据不同的根据不同的地址修改时间地址修改时间可可将重定位划分为将重定位划分为静态静态重定位重定位和和动态动态重定位。重定位。2.重定位：重定位：静态重定位静态重定位动态重定位动态重定位 mov AL, nn mov AL, nn+m 逻辑空间 0 内存 m nn L nn+m L+m 静态重定位是在装入过程完成后在静态重定位是在装入过程完成后在程序运行程序运行前前，一次一次将所有的指令要访问的地址全部修改将所有的指令要访问的地址全部修改为绝对地址，在程序运行过程中

17、不再修改。为绝对地址，在程序运行过程中不再修改。静态重定位要求程序一旦装入其静态重定位要求程序一旦装入其绝对地址空间绝对地址空间就就不能发生变化不能发生变化了。了。 mov AL, nn m nn+m nn + mov AL, nn m L+m 0 L nn 逻辑空间 L 基址寄存器 L 地址寄存器 内存 L 动态重定位是在程序的动态重定位是在程序的运行过程运行过程中，当指令需中，当指令需要执行时对将要访问的要执行时对将要访问的地址地址进行进行修改修改。 动态重定位动态重定位允许允许在在程序运行过程程序运行过程中，其中，其绝对地绝对地址址空间发生变化或被分割为不同的区域，空间发生变化或被分割为

18、不同的区域，变化变化后后只需要将基地址寄存器中的内容作对应修改。只需要将基地址寄存器中的内容作对应修改。 采用静态重定位方式的采用静态重定位方式的主要优点主要优点是：是：（1）可以在一般机器上全部用）可以在一般机器上全部用。（2）装入程序可以实现）装入程序可以实现。静态重定位方式静态重定位方式主要缺点主要缺点是：是：（1）执行期间程序）执行期间程序在主存储器中在主存储器中，所以对提高主存储器的利用率不利。所以对提高主存储器的利用率不利。（2）若程序空间大于被分配的物理空间，）若程序空间大于被分配的物理空间，由程序员自行采取某种手段来由程序员自行采取某种手段来问题，问题，如采用覆盖结构。如采用覆

19、盖结构。（3）用户）用户已经存放在主存中的同已经存放在主存中的同一个程序，如果几个用户要使用同一个程序，一个程序，如果几个用户要使用同一个程序，则每个用户必须在各自的主存空间中存放一则每个用户必须在各自的主存空间中存放一个程序副本。个程序副本。 采用动态重定位方式的采用动态重定位方式的主要优点主要优点有：有：（1）在程序开始执行之前，）在程序开始执行之前，不不一定要一定要把整把整个程序个程序都都调入调入到主存中。一个程序可以被分到主存中。一个程序可以被分配在多个配在多个不连续不连续的主存物理空间内，以提高的主存物理空间内，以提高主存储器的利用率。主存储器的利用率。（2）几个程序）几个程序可以共

20、享可以共享存放在主存中的同存放在主存中的同一个程序段。一个程序段。（3）支持）支持虚拟虚拟存储器。存储器。动态重定位方式的动态重定位方式的主要缺点主要缺点有：有：（1）需要有）需要有硬件支持硬件支持。（2）实现存储管理的软件算法）实现存储管理的软件算法比较复杂比较复杂。二、二、 内存内存分配与回收分配与回收 1.存储分配存储分配 2.存储释放存储释放 3.分配原则分配原则 在设计分配程序时需要考虑诸多因素:(1)内存空间的划分(2)数据结构的确定 (3)作业空间的划分(4)淘汰算法 (5)分配算法 存储分配实际上是将作存储分配实际上是将作业的逻辑地址空间映射成业的逻辑地址空间映射成为内存中的物

21、理地址空间。为内存中的物理地址空间。 内存中有许多尚未使用内存中有许多尚未使用的区域即自由区都可以被的区域即自由区都可以被分配，但到底选择哪一自分配，但到底选择哪一自由区必须依据分配算法来由区必须依据分配算法来确定。确定。 存储释放实际上是解除存储释放实际上是解除逻辑地址空间与物理地址逻辑地址空间与物理地址空间的联系，并释放物理空间的联系，并释放物理空间。空间。 存储释放程序将回收的存储释放程序将回收的内存区域重新设定为自由内存区域重新设定为自由区，并将其安排进入自由区，并将其安排进入自由区队列。进入自由区队列区队列。进入自由区队列的具体位置也必须依据分的具体位置也必须依据分配算法。配算法。

22、三、三、 存储保护与共享存储保护与共享 存储保护就是要保护进程的数据不被非法访存储保护就是要保护进程的数据不被非法访问者破坏。问者破坏。 （1）界地址寄存器保护法）界地址寄存器保护法（2）访问授权保护）访问授权保护n （1）界地址寄存器保护法）界地址寄存器保护法 采用硬件：采用硬件：基地址寄存器基地址寄存器BR长度寄存器长度寄存器LR 采用软件：采用软件： 地址寄存器指令中逻辑地址 出错 （地址寄存器）（基址寄存器）？ 否 是 （地址寄存器）（基址寄存器）+（长度寄存器）？ 运行指令 当进程之间需要共享当进程之间需要共享某些数据时，使用界地址某些数据时，使用界地址寄存器就表现得无能为力。寄存器

23、就表现得无能为力。 n （2）访问授权保护）访问授权保护分区号 访问权 1 2 2 0 3 1 1 0 P1 P2 进程访问权 当进程访问某个区域时，若进程的当进程访问某个区域时，若进程的访问权限大于等访问权限大于等于被访问区域的权限值于被访问区域的权限值，访问可以进行，否则视为，访问可以进行，否则视为非法。非法。系统为每一个系统为每一个存储区域存储区域都给都给定一个定一个访问权限值。访问权限值。同时也为每一个同时也为每一个进程进程赋予一赋予一个个访问权限值访问权限值。 一个进程可以对不同存储区域有一个进程可以对不同存储区域有不同的访问权限；不同的访问权限； 一个存储区域也可以被多个具有一个存

24、储区域也可以被多个具有不同访问权限的进程按权限级别进不同访问权限的进程按权限级别进行访问。行访问。 访问授权保护还有一个好处是它访问授权保护还有一个好处是它允许存储区域的共享。允许存储区域的共享。 四、四、 虚拟存储器虚拟存储器 (1)实际内存空间实际内存空间 (2)辅助存储器上的内存交换区辅助存储器上的内存交换区 (3)虚拟地址虚拟地址 (4)换进、换出机制换进、换出机制 n虚拟存储器是将内存进行虚拟，使用户能使用虚拟存储器是将内存进行虚拟，使用户能使用比实际内存大得多的虚拟空间。比实际内存大得多的虚拟空间。n要实现虚拟内存必须具备如下条件：要实现虚拟内存必须具备如下条件： 目前的操作系统几

25、乎目前的操作系统几乎全部全部具具备虚拟存储器功能，虽然不同的备虚拟存储器功能，虽然不同的系统其实现虚拟存储器的系统其实现虚拟存储器的基本条基本条件都相似件都相似，但在数据的换进、换，但在数据的换进、换出出策略上是可以不同策略上是可以不同的。的。 存储区整理存储区整理 n当系统运行一段时间后，可能出现如下当系统运行一段时间后，可能出现如下问题问题：产生许多产生许多碎片碎片；进程过分进程过分分散存储分散存储；换进、换出的次数过多，导致系换进、换出的次数过多，导致系统统运行缓慢运行缓慢；不断不断“内存空间不够内存空间不够”。存储区存储区需要整理需要整理。n存储器的存储器的整理方法整理方法：（1）定期

26、将内存中的）定期将内存中的碎片合并；碎片合并；（2）将某些）将某些进程进程的分散存储区域的分散存储区域移动移动到一起。到一起。n经过经过整理后整理后 系统中有更大的自由分区，系统中有更大的自由分区，提高提高存储管理的存储管理的效效率率；在整理时中断所有进程，并且需要在整理时中断所有进程，并且需要消耗较多的消耗较多的CPU时间时间。4.2 分区管理分区管理 n单一分区分配方式单一分区分配方式n多重固定分区分配方式多重固定分区分配方式n多重动态分区分配方式多重动态分区分配方式n伙伴系统伙伴系统 一、一、单一连续分配方式单一连续分配方式 1.原理原理 连续的用户逻连续的用户逻辑地址空间，辑地址空间，

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

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

29、分配方式 区号 大小 起始地址 状态 0 20K 40K 未分配 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 区 内存 将内存空间由小到大将内存空间由小到大划分为若干个划分为若干个位置固定大位置固定大小不等小不等的区域，每个区域的区域，每个区域可以存放一个作业，存放可以存放一个作业，存放于不同区域的于不同区域的

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

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

32、K 10K 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 自由分区链 根据作业对内存空间根据作业对内存空间的申请来划分主存区的申请来划分主存区域，区域的域，区域的大小可变大小可变、位置可变位置可变、数量也数量也可变可变 描述已被分配的区域描述已被分配的区域 描述内存中的自由区域描述内存中的自由区域 为每一个为每一个自由分区自由分区设置一设置一个个链接链接指针来指向下一个

33、指针来指向下一个自由分区，使所有的自由自由分区，使所有的自由分区形成一个链表分区形成一个链表 多重分区分配与释放多重分区分配与释放 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）最坏适应算法 将作业分配到内存中将作业分配到内存中第一第一个碰到个碰到的大于或等于作业的大于或等于作业申请空间的未分配区。申请空间的未分配区。将作业申请大小

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

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

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

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

38、PUCPU时间，并时间，并且在移动过程中稍有且在移动过程中稍有不慎不慎就有可能就有可能破坏破坏全部数据。全部数据。7.7.多重动态分区的优缺点多重动态分区的优缺点（1 1）多道程度得以提高。）多道程度得以提高。（2 2）提高了内存的利用率。）提高了内存的利用率。（3 3）作业大小依然受内存容量的限制。）作业大小依然受内存容量的限制。（4 4）对碎片问题的解决需要以增加系统开销为代价。）对碎片问题的解决需要以增加系统开销为代价。（5 5）不便共享。）不便共享。举例：举例： 作业作业A要求要求18KB；作业；作业B要求要求25KB；作业；作业C要求要求30KB。用首次适应算法、最佳适应算法来处理该

39、作业序列，看哪种用首次适应算法、最佳适应算法来处理该作业序列，看哪种算法合适。算法合适。 os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1 (1) 首次适应算法中的自由主存队列首次适应算法中的自由主存队列 (a) 首次适应算法中的自由主存队首次适应算法中的自由主存队列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1 (2) 最

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

41、 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 作业作业A要求要求18KB作业作业B要求要求25KB作业作业C要求要求30KB4.3 4.3 分页存储管理方式分页存储管理方式 页式系统应解决的问题页式系统应解决的问题 分区存储管理的主要问题是碎片问题。分区存储管理的主要问题是碎片问题。 在采用分区存储管理的系统中，会形成在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪不能被系统中的任何用户（程序）利用而浪费。费。 造成这样问题的主要原因是用户程序装造成这样问

42、题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。提出了分页存储管理技术。页式存储管理要解决如下问题页式存储管理要解决如下问题n页式存储管理系统的地址映射；页式存储管理系统的地址映射；n调入策略；调入策略；n淘汰策略；淘汰策略；n放置策略放置策略 一、一、 页式系统的基页式系统的基本概念本概念 （1 1） 页面页面 程序的地址空间被等程序的地址空间被等分成大小相等的片，称为分成大小相等的片，称为页面，又称为虚页。页面，又称为虚页。 （2 2） 主存块主存块 主存被等分成大小相主存被等分成大小相等的片，称为主存块，又等的片

43、，称为主存块，又称为实页。称为实页。（3 3） 页表页表 为了实现从地址空间到物理主存的映象，为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。地址变换的机构称为页面映像表，简称页表。 01KB01KB2KB3KB 1主存主存作业作业2地址空间地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB 101KB2KB 1作业作业1地址空间地址空间01KB 1作业作业3地址空间地址空间0516页号页号块号块号02140827作业作业1页表页表作业作业2页表页表作业作业3页表页表osos

44、分页映像存储的例分页映像存储的例 （4 4）虚地址结构）虚地址结构( (程序字程序字) ) 虚地址是用户程序中的逻辑地址，它包括页号和虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。页内地址（页内位移）。 区分页号和页内地址的依椐是页的大小，页内地区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。址占虚地址的低位部分，页号占虚地址的高位部分。 假定页面大小假定页面大小1024字节，虚地址共占用字节，虚地址共占用2个字节个字节(16位位) 页号页号 页内地址（位移量）页内地址（位移量） P W 15 10 9 0（5） 页式地址变换页式地址变

45、换 页式地址变换举例页式地址变换举例 作业作业2 2地址空间中，设地址空间中，设100100号单元处有如下指令：号单元处有如下指令： mov mov r1,2500r1,2500。当这条指令执行时，如何进行正确的地址变换。当这条指令执行时，如何进行正确的地址变换。mov r1 ,250012301KB1KB3KB 1作业作业2地址空间地址空间 2500 2 2* *1024 + 452 1024 + 452 p=2 w=452 p=2 w=4520000100111000100 000010 0111000100 页式地址变换过程页式地址变换过程 000111 011100010015 10

46、9 0页号页号P页内位移页内位移W页表始址寄存器页表始址寄存器mov r1 ,250012301KB2KB3KB 1作业作业2地址空间地址空间+021427页表页表 000010 011100010015 10 9 0页号页号P页内位移页内位移W250001KB主存主存2KB3KB4KB5KB6KB7KB8KB9KB10KB 1ososmov r1 , 2500123第第1页页7*1024+452=7620 页式地址变换的步骤页式地址变换的步骤 CPU给出操作数地址给出操作数地址(为为2500) ； 由分页机构自动地把逻辑地址分为两部分，由分页机构自动地把逻辑地址分为两部分，得到页号得到页号p

47、和页内相对位移和页内相对位移w (p =2， w =452)； 根据页表始址寄存器指示的页表始地址，以根据页表始址寄存器指示的页表始地址，以页号为索引，找到第页号为索引，找到第2页所对应的块号页所对应的块号(为为7) ； 最后，将块号最后，将块号b和页内位移量和页内位移量w拼接在一起，拼接在一起，就形成了访问主存的物理地址就形成了访问主存的物理地址 (7*1024+452=7620)。二、静态分页管理二、静态分页管理 1、分配与回收、分配与回收l在静态分页管理时，作业的一页可分配在静态分页管理时，作业的一页可分配到存储空间的任何一个可用的物理块中到存储空间的任何一个可用的物理块中 作业完成后，

48、系统回收分配给该作业的作业完成后，系统回收分配给该作业的内存块内存块 l作业完成后，系统回收分配给该作业的作业完成后，系统回收分配给该作业的内存块内存块 2、优缺点、优缺点（1）管理）管理简单简单（2）每访问一次内存数据需要经过）每访问一次内存数据需要经过二次寻址二次寻址。（3）解决了）解决了碎片问题碎片问题。无无须内存碎片整理。须内存碎片整理。（4）无无法实现法实现共享共享。（5）作业大小受内存可用页面数的）作业大小受内存可用页面数的限制限制。 如果想在内存中运行较大的作业，则如果想在内存中运行较大的作业，则必须必须利用内存以外的存储空间利用内存以外的存储空间。 例：有一系统采用页式存储管理

49、，有一作业大小例：有一系统采用页式存储管理，有一作业大小是是8KB8KB，页大小为，页大小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9 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三、

50、三、 请求分页管理请求分页管理 1.原理原理 内存 0 1 2 3 4 5 6 7 ： 作业空间 0 1 2 3 页表寄存器 页表 0 0 1 1 2 1 3 1 缺页状态 外存地址 内存块号 外存 与静态分页管理与静态分页管理不同不同 ：按需分配。将按需分配。将需要需要运行运行的页面的页面存放于内存存放于内存，暂时，暂时不不需要需要运行的页面存放于辅存，运行的页面存放于辅存，当需要运行当需要运行存放于辅存存放于辅存上的上的页面时，再将对应的页面调页面时，再将对应的页面调入内存。入内存。 注意页表变化注意页表变化2.分配与分配与淘汰算法淘汰算法动态分动态分配配 启动待执行指令 地址映射 缺页状

51、态=0？ 是 否 页面装入 淘汰一个页面 获取相对地址 P、d 执行指令 指令地址+1 有空闲块？ 否 该页修改过？ 是 写回外存 否 页面装入 缺页中断处理 分配与淘汰算法分配与淘汰算法淘汰算法淘汰算法衡量淘汰算法依据：衡量淘汰算法依据：所有页面访问次数淘汰页面数淘汰率 所有页面访问次数缺页次数缺页率 好的淘汰算法应该有好的淘汰算法应该有较低的缺页率和淘汰率。较低的缺页率和淘汰率。 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 * * * * * * * * * *

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

53、长时间未被使用选择最近一段时间内最长时间未被使用的页面淘汰的页面淘汰 该算法的该算法的假定假定：长时间未使用的页面不会马上被使用。：长时间未使用的页面不会马上被使用。这正好符合内存这正好符合内存局部性原理局部性原理（内存中某个位置现在被（内存中某个位置现在被访问，很快将再次被访问；某个位置现在被访问，其访问，很快将再次被访问；某个位置现在被访问，其邻近位置也将被访问。）邻近位置也将被访问。） 问题：问题：需要确定一个需要确定一个比较时间段比较时间段来反映哪一个页面长期未被来反映哪一个页面长期未被使用，时间段使用，时间段过长过长时该算法将变为时该算法将变为先进先出先进先出算法，时算法，时间段间段

54、过短过短又会使系统频繁地记录访问次数并进行比较，又会使系统频繁地记录访问次数并进行比较，从而增加系统从而增加系统开销开销。（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？ 是 否 页面回写外存 选择页面选择指针遇到的选择页面选择指针遇到的最近未被访问的页面淘汰。最近未被访问的页面淘汰。简化的方法是：简化的方法是：页面选择指针下移，只要遇到刚才页面选择指针下

55、移，只要遇到刚才未使用的页面就可以淘汰。未使用的页面就可以淘汰。 例例: : 某作业有某作业有a,b,c,da,b,c,d四个页面四个页面, ,作业在运行过程中的访作业在运行过程中的访问次序为问次序为:a,b,c,a,d,a,:a,b,c,a,d,a,试计算采用试计算采用FIFOFIFO和和LRULRU淘汰算法淘汰算法, ,各会产生几次缺页中断各会产生几次缺页中断?(?(注：系统为该作业分配个内注：系统为该作业分配个内存块存块) ) 缺页中断次数淘汰的页面进入主存的页面1-a2-B3-C4ad5ba缺页中断次数淘汰的页面进入主存的页面1-a2-b3-c4bd LRU LRUFIFOFIFO举例

56、举例FIFO算法的异常现象算法的异常现象(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个页面时个页面时,会出现什么会出现什么情况情况?虚拟存储器虚拟存储器 动态分页技术实现了虚拟

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

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

59、意义划分成段，作业地址空间按逻辑意义划分成段，每段都有其对应的段号和段长，对分每段都有其对应的段号和段长，对分段数量和分段的长度没有限制。段数量和分段的长度没有限制。 内存空间采用多重动态内存空间采用多重动态分区的形式，分区的长分区的形式，分区的长度和位置没有限制。度和位置没有限制。 段表将作业中的段对应于内段表将作业中的段对应于内存中的分区。有缺段机制。存中的分区。有缺段机制。1.分段分段2.逻辑地址逻辑地址 S d 段号段号S S 段内位移段内位移d d 每个段的段内位移的范围每个段的段内位移的范围是是不同不同的。的。 分页管理分页管理中，逻辑地址是中，逻辑地址是线性地址线性地址。分段管理

60、分段管理中，段号中，段号S和段内位移和段内位移d不能形成一不能形成一个线性地址，因为它实际上是代表着段长和段内位个线性地址，因为它实际上是代表着段长和段内位移移两个变量两个变量。由于这两个变量没有特定的限制范围而无法由于这两个变量没有特定的限制范围而无法用一个变量来替代，因此分段管理的用一个变量来替代，因此分段管理的逻辑地址是二逻辑地址是二维地址维地址，分段管理的逻辑地址空间是，分段管理的逻辑地址空间是二维空间二维空间。 3.数据结构数据结构 段表段表段表寄存器段表寄存器内存分块表内存分块表OrOr已使用分区表已使用分区表自由分区表自由分区表自由分区块链自由分区块链作业表作业表4.地址映射地址

61、映射 内存 段表寄存器 表目长度 地址寄存器中的逻辑地址 d S d 段表 段表长度 S 段表中段号为段表中段号为S S的表目地址（段的表目地址（段表寄存器）表目长度表寄存器）表目长度 S S 段表起始地址（段表寄存器）段表起始地址（段表寄存器） 对应的内存分区地址对应的内存分区地址S S 绝对地址绝对地址SSd d 二、简单分段二、简单分段 系统为每一个段分配一个连续的存储系统为每一个段分配一个连续的存储空间，而段和段之间可以不连续，离散空间，而段和段之间可以不连续，离散地分配到内存的不同区域。地分配到内存的不同区域。 系统为每个进程建立一张段表系统为每个进程建立一张段表 三、请求分段三、请

62、求分段1、分配与释放、分配与释放 首先为作业首先为作业分配分配段表段表空间；空间； 分配分配主程序段：主程序段：按一定的按一定的分配算法分配算法（内存空间采用动态分区（内存空间采用动态分区形式，因此分配算法可采用最先适应算法、最佳适形式，因此分配算法可采用最先适应算法、最佳适应算法或者最坏适应算法。）应算法或者最坏适应算法。） 填写段表填写段表：填入对应段表表目中该段的内存地址，其他填入对应段表表目中该段的内存地址，其他暂时暂时不在内存不在内存的段，的段，缺段状态缺段状态置为置为1 1，在需要运行时，在需要运行时再调入。再调入。 入口（段名） 调缺段中断处理 要连接的段 在内存吗？ 否 是 指

63、令中逻辑地址重定位 将该段地址填入段表， 缺段中断位=0 查共享表 返回 Sub Call Sub 的起始地址 ： Call Sub; ： 段名 Main Sub （a） 段之间的关系 （b） 段的动态连接 当作业空间逻辑分段当作业空间逻辑分段后，后，用户用户是靠是靠调用调用来来实现段与段之间的关实现段与段之间的关系，而存储管理将其系，而存储管理将其实现称为实现称为连接连接 连接也可以分为连接也可以分为静态连接静态连接与与动态连接动态连接。2、连接、连接静态连接静态连接发生在作业刚装发生在作业刚装入内存还入内存还没有被执行前没有被执行前，一次完成所有连接。一次完成所有连接。动态连接动态连接发生

64、在发生在执行过程执行过程中中，每当作业段与段之间，每当作业段与段之间产生调用要求时才进行连产生调用要求时才进行连接。接。问题问题：作业段必须一次全：作业段必须一次全部调入内存，限制了作业部调入内存，限制了作业的大小，对内存的容量要的大小，对内存的容量要求高。求高。作业中的各段没有必要一次作业中的各段没有必要一次全部调入，这极大的提高了全部调入，这极大的提高了内存的利用率。内存的利用率。分段管理采用的是动态连接方式。分段管理采用的是动态连接方式。3 3、共享、共享 共享区 内存 作业 A 段表 0 1 2 3 作业 B 段表 0 1 作业 C 段表 0 1 2 4 4、存储保护、存储保护n 在段

65、表中既有段的起始位置也有在段表中既有段的起始位置也有段的长度，段的长度， 实现作业区域的实现作业区域的界限管理界限管理。n 在段表中增加一个访问权限项，在段表中增加一个访问权限项， 实现实现访问授权控制访问授权控制。5、虚拟存储器虚拟存储器 缺段中断机制缺段中断机制+ +换进、换出，换进、换出， 实现了实现了虚拟存储器虚拟存储器。6 6、分段管理的特点分段管理的特点（1 1）易于实现）易于实现共享共享。（2 2）实现了）实现了动态连接动态连接。（3 3）实现了）实现了虚拟存储器虚拟存储器。（4 4）段长段长受内存容量的受内存容量的限制限制。（5 5）内存）内存管理复杂管理复杂。有没有同时有没有

66、同时利用利用分页管理和分段管理分页管理和分段管理的的优点优点，克服克服它们的它们的弱点弱点管理方法？管理方法？4.5 段页式管理段页式管理 将程序分为多个逻辑段，在每个段将程序分为多个逻辑段，在每个段里面又进行分页。里面又进行分页。 分段和分页的组合。分段和分页的组合。1、基本原理、基本原理内存 外存 段表寄存器 段表 4 0 2 1 3 0 1 1 缺段状态 外存地址 页表地址 段长 作业空间 0 1 1 0 0 0 1 缺页状态 外存地址 内存块号 页表 作业地址空间作业地址空间分段分段再再分页分页内存内存分块（页框）分块（页框）对应对应页表页表是否在内存是否在内存对应对应页面页面是否在内存是否在内存2.逻辑地址逻辑地址 S P d 段号段号页号页号页内位移页内位移一维地址一维地址二维地址二维地址3.数据结构数据结构段表段表页表页表段表寄存器段表寄存器存储分块表存储分块表作业表作业表4.地址映射地址映射 段表寄存器 表目长度 地址寄存器中的逻辑地址 S P d 段表 段表长度 S 表目长度 P 页表 页框长度 内存 d 5.分配与释放分配与释放 内存 外存 段表寄存器 段表 4 0