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

第第五五章章 存储管理存储管理n5.1 存储管理的功能存储管理的功能n5.2 实存管理实存管理（分区）（分区）n5.3 覆盖与交换覆盖与交换n5.4 虚拟存储器管理虚拟存储器管理（分页，段）（分页，段）n5.5 碎片与抖动问题碎片与抖动问题本章学习目标本章学习目标n存储管理的目的和四大基本功能。存储管理的目的和四大基本功能。n 实实存存管管理理中中讲讲述述了了固固定定分分区区存存储储管管理理、可可变变式式分分区区存存储储管管理理、纯纯分分页页存存储储管管理理三三种种存存储储管管理理方方案案的的实实现现原原理理，内内存存的的分分配配与与回收方法回收方法.n虚虚存存管管理理以以请请求求式式分分页页存存储储管管理理为为重重点点，讲述其实现原理和动态地址重定位过程讲述其实现原理和动态地址重定位过程.n总总结结各各种种存存储储管管理理方方案案中中存存在在的的碎碎片片和和抖抖动问题及解决方法动问题及解决方法 存储体系概述存储体系概述1.存储体系存储体系 操作系统协调各存储器的使用。操作系统协调各存储器的使用。重要性：重要性：直接存取要求内存速度尽量快到与直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行取指速度相匹配，大到能装下当前运行的程序与数据，否则的程序与数据，否则CPU执行速度就会受到执行速度就会受到内存速度和容量的影响而得不到充分发挥内存速度和容量的影响而得不到充分发挥多级存储多级存储图4.1 多级存储器体系示意图2.2.内存内存 由存储单元（字节或字）组成的一维连续的地由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。所指的、亦即程序计数器所指的存储器。分为：分为：系统区：用于存放操作系统系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据用户区：用于装入并存放用户程序和数据3.存储管理的目的存储管理的目的1 1、充分利用内存，为多道程序并发执行提供充分利用内存，为多道程序并发执行提供 存储基础。存储基础。2 2、尽可能方便用户使用。、尽可能方便用户使用。3 3、自动装入用户程序。、自动装入用户程序。4 4、用户程序中不必考虑硬件细节。、用户程序中不必考虑硬件细节。5 5、系统能够解决程序空间比实际内存空间大的、系统能够解决程序空间比实际内存空间大的问题。问题。6 6、程序在执行时可以动态伸缩、程序在执行时可以动态伸缩7 7、内存存取速度快、内存存取速度快8 8、存储保护与安全、存储保护与安全9 9、共享与通信、共享与通信1010、了解有关资源的使用状况、了解有关资源的使用状况5.1 存储管理的功能存储管理的功能n5.1.1 内存的分配与回收内存的分配与回收n5.1.2 地址重定位地址重定位 n5.1.3 存储保护存储保护n5.1.4 虚拟存储器虚拟存储器 返回首页5.1.1 内存的分配与回收内存的分配与回收n内内存存分分配配按按分分配配时时机机的的不不同同，可可分分为为两两种种方式。方式。（1）静态存储分配）静态存储分配（2）动态存储分配）动态存储分配 返回本节5.1.2 地址重定位地址重定位程序在成为进程前的准备工作程序在成为进程前的准备工作l编辑：形成源文件编辑：形成源文件(符号地址符号地址)l编译：形成目标模块编译：形成目标模块(模块内符号地址解析模块内符号地址解析)l链接：由多个目标模块或程序库生成可执链接：由多个目标模块或程序库生成可执行文件行文件(模块间符号地址解析模块间符号地址解析)l装入：构造装入：构造PCB，形成进程形成进程(使用物理地址使用物理地址)n重定位方法：重定位方法：l绝对装入绝对装入l可重定位装入可重定位装入l动态装入动态装入1.逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射n逻辑地址逻辑地址（相对地址，虚地址）：用户的（相对地址，虚地址）：用户的程序中相对于某个基准量（通常为程序中相对于某个基准量（通常为0）编址）编址所用的地址。所用的地址。l其首地址为其首地址为0，其余指令中的地址都相对，其余指令中的地址都相对于首地址来编址。于首地址来编址。l不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。n物理地址物理地址（绝对地址，实地址）：内存中（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。存储单元的地址。物理地址可直接寻址。地址空间：相对地址的集合（虚地址空地址空间：相对地址的集合（虚地址空 间）。间）。存储空间：绝对地址的集合（实地址空存储空间：绝对地址的集合（实地址空 间）。间）。n地址映射地址映射：将用户程序中的逻辑地址转换：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。为运行时由机器直接寻址的物理地址。l当程序装入内存时当程序装入内存时,操作系统要为该程序操作系统要为该程序分配一个合适的内存空间，由于分配一个合适的内存空间，由于程序的程序的逻辑地址与分配到内存物理地址不一致逻辑地址与分配到内存物理地址不一致,而而CPU执行指令时，是按物理地址进行的，执行指令时，是按物理地址进行的，所以要进行地址转换。所以要进行地址转换。图5.2 作业的名空间、逻辑地址空间和装入后的物理空间2.绝对装入绝对装入(absolute loading)在可执行文件中记录内存地址，装入时直接定位在上述(即文件中记录的地址)内存地址。n优点：装入过程简单。优点：装入过程简单。n缺点：过于依赖于硬件结构，不适于多道缺点：过于依赖于硬件结构，不适于多道程序系统。程序系统。3.可重定位装入可重定位装入(relocatable loading)程序在执行前集中一次性完成的地址程序在执行前集中一次性完成的地址变换方式，只完成一个首地址不同的变换方式，只完成一个首地址不同的连续地址转换。连续地址转换。优点：不需硬件支持，可装入有限多道程序缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。可执行文件在内存中的重定位说明：重定位表中列出所有修改的位置。如：重定位表的150表示相对地址150处的内容为相对地址(即100为从0起头的相对位置)。在装入时，要依据重定位后的起头位置(2000)修改相对地址。重定位修改：重定位表中的150-绝对地址2150(=2000+150)内容修改：内容100变成2100(=100+2000)。4.动态装入动态装入(dynamic run-time loading)程序在执行过程中，当程序在执行过程中，当CPU访问指令或数访问指令或数据时进行的地址变换方式，。据时进行的地址变换方式，。优点：优点：OS可以将一个程序分散存放于不连续的内存空可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。间，可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。变量（而不仅是生成可执行文件时的地址引用）。缺点：需要硬件支持（通常是缺点：需要硬件支持（通常是CPU），），OS实现较复杂。它是虚拟存储的基础。实现较复杂。它是虚拟存储的基础。图4.3 静态地址重定位和动态地址重定位示意图（b）采用动态重定位时内存空 间及地址重定位示意图（a）采用静态重定位后的内存空间返回本节5.1.3 存储保护存储保护（1）上、下界存储保护：上、下界保护是一）上、下界存储保护：上、下界保护是一种简单的存储保护技术。如图种简单的存储保护技术。如图4.4（a）所示所示（2）基址）基址限长存储保护：上、下界保护限长存储保护：上、下界保护的一个变种是采用基址的一个变种是采用基址限长存储保护。限长存储保护。如图如图4.4（b）所示。所示。（a）上、下界保 （b）基址限长保护图4.4 界限寄存器的两种存储保护方式返回本节5.1.4 虚拟存储器虚拟存储器n虚拟存储技术的基本思想是把有限的内存虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。一个远大于实际内存的、虚拟的存储器。即把两级存储器当作一级存储器来看待。即把两级存储器当作一级存储器来看待。n对用户而言，感觉到系统提供了一个大容对用户而言，感觉到系统提供了一个大容量的内存，供用户使用，但这样大容量的量的内存，供用户使用，但这样大容量的内存实际上并不存在，是一种虚拟的存储内存实际上并不存在，是一种虚拟的存储器，因此把具有这种功能的存储管理技术器，因此把具有这种功能的存储管理技术称为虚拟存储管理。称为虚拟存储管理。返回本节虚拟存储技术的核心虚拟存储技术的核心 其核心是把作业的地址空间和主存的存储空其核心是把作业的地址空间和主存的存储空间看做两个不同的概念。一个计算机为程间看做两个不同的概念。一个计算机为程序员提供了多大的地址空间，他就可以在序员提供了多大的地址空间，他就可以在这个地址空间内编制多大的程序，而完全这个地址空间内编制多大的程序，而完全不顾及实际内存的大小。不顾及实际内存的大小。所谓虚拟存储器就是一个地址空间，正如所谓虚拟存储器就是一个地址空间，正如主存对应于存储空间一样。主存对应于存储空间一样。虚存的形式虚存的形式1、单段式虚存：是一个连续的线性空、单段式虚存：是一个连续的线性空 间，其间，其 地址顺序为：地址顺序为：0，1，2，.n1，n。2、多段式虚存：把地址空间分成若干多段式虚存：把地址空间分成若干 个段，个段，而在每一个段内则是一个连而在每一个段内则是一个连续的线性空间。续的线性空间。*引入虚拟存储技术的好处引入虚拟存储技术的好处n大程序大程序：可在较小的可用内存中执行较：可在较小的可用内存中执行较大的用户程序；大的用户程序；n大的用户空间大的用户空间：提供给用户可用的虚拟：提供给用户可用的虚拟内存空间通常大于物理内存；内存空间通常大于物理内存；n并发并发：可在内存中容纳更多程序并发执：可在内存中容纳更多程序并发执行。行。虚拟存储技术的特征虚拟存储技术的特征n不连续性不连续性：物理内存分配的不连续，虚拟地址空间：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）享段和动态链接库占用的空间）n部分交换部分交换：与交换技术相比较，虚拟存储的调入和：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；调出是对部分虚拟地址空间进行的；n大空间大空间：通过物理内存和快速外存相结合，提供大：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间范围的虚拟地址空间l总容量不超过物理内存和外存交换区容量之和总容量不超过物理内存和外存交换区容量之和5.2 分区存储管理分区存储管理n5.2.1 固定分区存储管理固定分区存储管理n5.2.2 可变式分区存储管理可变式分区存储管理 n5.2.3 可重定位分区存储管理可重定位分区存储管理返回首页分区存储管理的基本原理分区存储管理的基本原理 分区存储管理是能满足多道程序设计的最分区存储管理是能满足多道程序设计的最简单的存储管理技术，它运行多个作业共享简单的存储管理技术，它运行多个作业共享内存。内存。在内存中为每个进程划分一个相应的存储在内存中为每个进程划分一个相应的存储区，以连续存储各进程的程序段和数据段，区，以连续存储各进程的程序段和数据段，使得各进程得以并发执行。使得各进程得以并发执行。5.2.1 固定分区存储管理固定分区存储管理 基基本本思思想想：在在作作业业未未进进入入内内存存之之前前，就就由由操操作作员员或或操操作作系系统统把把内内存存可可用用空空间间划划分分成成若若干干个个固固定定大大小小的的存存储储区区，除除操操作作系系统统占占用用一一个个区区域域外外，其其余余区区域域为为系系统统中中多多个个用用户户共共享享，因因为为在在系系统统运运行行期期间间，分分区区大大小小、数数目目都都不不变变，所所以以固固定定式式分分区区也也称称为为静静态态分区（分区（如图如图4.5所示）。所示）。图5.5 固定式分区内存分配示意图（a）和（b）固定式分区说明表返回本节固定分区内存分配方法固定分区内存分配方法1）操作系统占用内存低端分区；）操作系统占用内存低端分区；2）如油作业提出分配请求，则根据作业的大）如油作业提出分配请求，则根据作业的大小在分区说明表中查找一个大于作业要求小在分区说明表中查找一个大于作业要求的未分配区进行分配；的未分配区进行分配；3）用重定位装入程序装入作业；）用重定位装入程序装入作业；4）如分区说明表中无满足作业要求的分区，）如分区说明表中无满足作业要求的分区，则通知系统出错，并调度下一个作业。则通知系统出错，并调度下一个作业。特点：特点：作业进入内存后，每一个分区内只允作业进入内存后，每一个分区内只允 许有一个作业，其占用的分区直到作许有一个作业，其占用的分区直到作 业运行结束才收回。业运行结束才收回。缺点：缺点：内存浪费较严重，因为作业的大小不内存浪费较严重，因为作业的大小不 可能正好与某个分区相等。可能正好与某个分区相等。5.2.2 可变式分区存储管理可变式分区存储管理n1空闲分区的组织形式空闲分区的组织形式n2内存的分配与回收内存的分配与回收n3常用的分配算法常用的分配算法n4可变式分区的地址重定位可变式分区的地址重定位可变式分区的基本原理可变式分区的基本原理原理：原理：分区的划分是在有作业提出内存分区的划分是在有作业提出内存请求时进行的，且使得分区的大小与作请求时进行的，且使得分区的大小与作业的大小相一致。业的大小相一致。特点：特点：分区个数不固定，每个分区大分区个数不固定，每个分区大小也不固定。小也不固定。图5.6 可变式分区内存使用情况示意图 空闲分区的组织形式空闲分区的组织形式n分分区区说说明明表表：共共计计2张张表表，一一个个是是可可用用表表，另另外外一一个个是是请请求求表表。其其中中，可可用用表表中中记记录录内内存存中中所所有有空空白白块块的的信信息息，包包括括：块块号号、长长度度和和首首地地址址；而而请请求求表表记记录录各各个个作作业业的的内存需求。内存需求。使用分区说明表进行内存分配与回收使用分区说明表进行内存分配与回收n分配方法：分配方法：1）从请求表中按）从请求表中按FCFS原则选定一个作业；原则选定一个作业；2）从可用表中按各空白块的排列顺序找出一）从可用表中按各空白块的排列顺序找出一个可以容纳选中作业的空白块；个可以容纳选中作业的空白块；3）如果该空白块的大小比作业要求空间超出）如果该空白块的大小比作业要求空间超出1K，则把它分成两部分；则把它分成两部分；4）修改）修改2张表的相关信息。张表的相关信息。n分区回收：分区回收：1）检查回收的分区是否与可用表中的空白块）检查回收的分区是否与可用表中的空白块 相邻，如相邻则执行合并算法；相邻，如相邻则执行合并算法；2）修改可用表。）修改可用表。n合并算法：合并算法：1）回收区）回收区R与上面空白块与上面空白块F1邻接，合并后仍为邻接，合并后仍为空白块空白块F1，首地址不变，修改该块大小；首地址不变，修改该块大小；2）回收区）回收区R与下面空白块与下面空白块F2邻接，合并后仍为邻接，合并后仍为空白块空白块F2，修改该块首地址和大小；修改该块首地址和大小；3）回收区与上、下空白块邻接，则撤消下面）回收区与上、下空白块邻接，则撤消下面空白块空白块F2，保留保留F1，修改该块大小。修改该块大小。n空空闲闲分分区区链链表表：在在每每个个空空闲闲分分区区的的起起始始部部分分开开辟辟出出一一个个单单元元，存存放放一一个个链链表表指指针针和和该该分分区区的的大大小小，链链表表指指针针指指向向下下一一个个空空闲闲分区。分区。图5.7 空闲分区链表组织形式 内存的分配与回收内存的分配与回收n当当某某一一个个用用户户作作业业完完成成释释放放所所占占分分区区时时，系系统统应应进进行行回回收收。在在可可变变式式分分区区中中，应应该该检检查查回回收收区区与与内内存存中中前前后后空空闲闲区区是是否否相相邻邻，若若相相邻邻，则则应应进进行行合合并并，形形成成一一个个较较大大的的空空闲闲区区，并并对对相相应应的的链链表表指指针针进进行行修修改改；若若不不相相邻邻，应应将将空空闲闲区区插插入入到到空空闲闲区区链链表表的适当位置。的适当位置。常用的分配算法常用的分配算法1）首次适应算法）首次适应算法 2）最佳适应算法）最佳适应算法 3）最差适应算法）最差适应算法 n首次适应算法：首次适应算法：原理：原理：所有空白块按首地址由低到高的次序所有空白块按首地址由低到高的次序 排列。排列。优点：优点：尽可能利用内存低址部分的空白块，尽可能利用内存低址部分的空白块，尽量保存位于高地址部分的大空白块，这样尽量保存位于高地址部分的大空白块，这样当有较大作业提出内存请求时便可能满足其当有较大作业提出内存请求时便可能满足其要求。要求。n最佳适应算法：最佳适应算法：原理：原理：空白块按容量大小递增的次序链空白块按容量大小递增的次序链接，在为作业分配内存空间时总是从最接，在为作业分配内存空间时总是从最小的空白块开始，即第一次找到的满足小的空白块开始，即第一次找到的满足要求的空白块必是最合适的。要求的空白块必是最合适的。优点：总能保留较大的空白块在内存中。优点：总能保留较大的空白块在内存中。缺点：缺点：1）由于空白块一般不会和作业的要求）由于空白块一般不会和作业的要求相等，因而肯定会对空白块进行划分，会相等，因而肯定会对空白块进行划分，会使得剩下的空白块都较小（易产生碎片）使得剩下的空白块都较小（易产生碎片）2）寻找一个较大空白块时间过长；）寻找一个较大空白块时间过长；3）划分后剩下的空白块还需要在自由链中进）划分后剩下的空白块还需要在自由链中进行位置的调整。行位置的调整。n最坏适应算法：最坏适应算法：原理：原理：空白块按容量大小递减的次序链空白块按容量大小递减的次序链接，在为作业进行内存分配时总是从接，在为作业进行内存分配时总是从最大的空白块开始进行。最大的空白块开始进行。优点：易于判别系统内是否有符合要求的空优点：易于判别系统内是否有符合要求的空白块存在；白块存在；划分后剩下的空白块较大，不易产生划分后剩下的空白块较大，不易产生碎片。碎片。缺点：当有大作业要求进入内存时无法满足缺点：当有大作业要求进入内存时无法满足的概率较大；的概率较大；划分后剩下的空白块还需要在自由链划分后剩下的空白块还需要在自由链中进行位置的调整。中进行位置的调整。图5.8 最佳适应算法的空闲分区链表组织形式图5.9 最差适应算法的空闲分区链表组织形式图5.10 内存使用情况图5.11 用三种适应算法处理同一作业序列三种算法的对比三种算法的对比n对满足要求的空白块查找效率的对比对满足要求的空白块查找效率的对比n分配后自由链调整的复杂性对比分配后自由链调整的复杂性对比n回收复杂性的对比回收复杂性的对比n碎片产生概率的对比碎片产生概率的对比n分配综合性能的对比（能否满足各种不同分配综合性能的对比（能否满足各种不同作业的要求）作业的要求）可变式分区的地址重定位可变式分区的地址重定位n可变式分区的地址重定位可采用静态重定可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。位，也可采用动态重定位。采用动态重定采用动态重定位的可变式分区管理技术，在执行内存分位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图凑操作。其分配算法如图4.12所示。所示。n可可变变式式分分区区的的存存储储保保护护可可采采用用基基址址限限长存储保护方式。长存储保护方式。图5.12 采用动态重定位的可变式分区分配算法返回本节可重定位式分区存储管理可重定位式分区存储管理原理：原理：采用紧凑（拼接）技术将内存中各个采用紧凑（拼接）技术将内存中各个空白块合并成一个大的空白块。该方法与可空白块合并成一个大的空白块。该方法与可变式分区管理技术基本相同。变式分区管理技术基本相同。需解决的问题：需解决的问题：1）程序原先占用空间的调整（程序浮动）程序原先占用空间的调整（程序浮动）2）何时进行紧凑？）何时进行紧凑？思考题思考题1、已知内存容量为、已知内存容量为512K，其中操作系统代码，其中操作系统代码占用了低地址部分的占用了低地址部分的126K，有作业序列如，有作业序列如下：作业下：作业1：80K；作业；作业2：56K；作业；作业3：120K；作业；作业1：完成；作业：完成；作业3：完成；作业：完成；作业4：156K；作业；作业5：80K。试用试用3种分配算法处理上述作业序列完成下种分配算法处理上述作业序列完成下述要求：述要求：1）画出作业）画出作业1，3完成后内存分布完成后内存分布情况及自由链结构；情况及自由链结构；2）画出作业）画出作业4，5进入进入系统后的内存分布情况及自由链结构。系统后的内存分布情况及自由链结构。2、设内存空白块数为、设内存空白块数为3，申请内存分配作业，申请内存分配作业数为数为4，其大小依次为，其大小依次为30K，32K，29K，20K请构造一种在动态分区管理中满足请构造一种在动态分区管理中满足WF但不但不能满足能满足BF的空白块的最低容量大小并说明的空白块的最低容量大小并说明其理由。其理由。1、为了满足、为了满足WF，则最大的空白块必须是被作，则最大的空白块必须是被作业业1划分后还能被其它作业使用；划分后还能被其它作业使用；2、为了不满足、为了不满足BF，则必须使得有个空白块大，则必须使得有个空白块大于作业于作业1且划分后剩余空间不能被其他作业使且划分后剩余空间不能被其他作业使用。用。6.4.1 覆盖覆盖(overlay)引入：引入：其目标是在小的可用内存中其目标是在小的可用内存中运行较大的运行较大的程序程序。常用于多道程序系统，与分区存储管理。常用于多道程序系统，与分区存储管理配合使用。配合使用。原理：一个程序的几个代码段或数据段，按照原理：一个程序的几个代码段或数据段，按照时间时间先后来先后来占用公共的内存空间占用公共的内存空间。l将程序的将程序的必要部分必要部分（常用功能）的代码和（常用功能）的代码和数据常驻内存；数据常驻内存；l可选部分可选部分（不常用功能）在其他程序模块（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；在需要用到时才装入到内存；l不存在调用关系的模块不必同时装入到内不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。存，从而可以相互覆盖。(即即不同时用的模不同时用的模块可共用一个分区块可共用一个分区)注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；覆盖技术n缺点：缺点：l编程时必须划分程序模块和确定程序模块编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。之间的覆盖关系，增加编程复杂度。l从外存装入覆盖文件，以时间延长来换取从外存装入覆盖文件，以时间延长来换取空间节省。空间节省。l注意：覆盖技术的对象是一个作业或程序注意：覆盖技术的对象是一个作业或程序内部的各个模块。内部的各个模块。6.4.2 交换交换(swapping)n引入：多个程序并发执行，可以将引入：多个程序并发执行，可以将暂时不能暂时不能执行的程序执行的程序送到外存中，从而送到外存中，从而获得空闲内存获得空闲内存空间空间来装入新程序，或读入保存在外存中而来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。目前到达就绪状态的进程。交换单位为整个交换单位为整个进程的地址空间进程的地址空间。n程序暂时不能执行的可能原因程序暂时不能执行的可能原因：处于阻塞状：处于阻塞状态，低优先级（确保高优先级程序执行）；态，低优先级（确保高优先级程序执行）；返回原理：原理：暂停暂停执行内存中的进程，将整个进执行内存中的进程，将整个进程的地址空间程的地址空间保存到外存保存到外存的交换区中（换的交换区中（换出出swap out），），而将外存中由阻塞变为就而将外存中由阻塞变为就绪的进程的地址空间绪的进程的地址空间读入读入到内存中，并将到内存中，并将该进程送到就绪队列（换入该进程送到就绪队列（换入swap in）。）。n优点：增加并发运行的程序数目，并且给用优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响户提供适当的响应时间；编写程序时不影响程序结构程序结构n缺点：对换入和换出的控制增加处理机的开缺点：对换入和换出的控制增加处理机的开销；程序整个地址空间都进行传送，没有考销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。虑执行过程中地址访问的统计特性。覆盖：覆盖：一个作业的若干程序段共享某一一个作业的若干程序段共享某一段存储空间。段存储空间。交换：交换：把内存中的程序信息以文件的形把内存中的程序信息以文件的形式写到外存，将指定的另一个程序信息式写到外存，将指定的另一个程序信息从外存读入内存。从外存读入内存。5.4 页式存储管理页式存储管理n5.4.1 基本原理基本原理n5.4.2 静态页式管理静态页式管理n5.4.3 动态页式管理动态页式管理 n5.4.4 请求页式管理中的置换算法请求页式管理中的置换算法 返回首页5.4.1 页式存储管理的基本原理页式存储管理的基本原理n地地址址空空间间管管理理：把把各各进进程程的的地地址址空空间间划划分分成成若若干干个个大大小小相相等等的的页页，经经过过页页的的划划分分后后，进进程的虚地址由页号程的虚地址由页号P与页内相对地址与页内相对地址W组成。组成。页号页号P页内相对位移页内相对位移W存储空间管理：存储空间管理：把内存空间划分成与页大把内存空间划分成与页大小相同的页面以存放各进程的页。在页式小相同的页面以存放各进程的页。在页式管理中，用户进程在内存中除了在每个页管理中，用户进程在内存中除了在每个页面内保持地址连续外，在各个页面之间不面内保持地址连续外，在各个页面之间不再连续。再连续。1、内存利用率的提高；、内存利用率的提高；2、实现了非连续存储。、实现了非连续存储。5.4.2静态页式管理静态页式管理原理：原理：在作业提出内存空间申请时，将作业在作业提出内存空间申请时，将作业的程序段和数据全部装入内存空闲页面中。的程序段和数据全部装入内存空闲页面中。地址重定位：地址重定位：使用页表完成地址空间到存储使用页表完成地址空间到存储空间的地址映射。空间的地址映射。图5.14 纯分页存储管理示意图图5.15 纯分页存储管理地址重定位实现过程联想存储器联想存储器n为为了了提提高高查查表表的的速速度度，人人们们在在分分页页地地址址变变换换机机构构中中，加加入入一一组组高高速速缓缓冲冲存存储储器器，用用来来存存放放当当前前作作业业的的最最常常用用的的页页号号和和与与之之相相应应的的物物理理块块号号。一一般般称称这这样样的的寄寄存存器器组组为为快快表表或或联联想想存存储储器器。采采用用联联想想存存储储器器和和内内存存中中页页表表相相结合的分页地址变换过程如图结合的分页地址变换过程如图5.16所示。所示。n应应用用联联想想存存储储器器和和页页表表相相结结合合的的方方式式，可可有有效效地地提提高高系系统统动动态态地地址址转转换换的的速速度度，是是一一种种行之有效的方法。行之有效的方法。利用快表查找 利用页表查找 利用页表中查找到的页号、块号更新快表图5.16 采用快表和页表相结合的分页地址变换过程示意图静态页式存储的分配算法静态页式存储的分配算法n所用数据结构：所用数据结构：1）页表：每个作业一张。）页表：每个作业一张。用以确定各作业的地址空间的各页在内存用以确定各作业的地址空间的各页在内存中的实际位置（页面）。中的实际位置（页面）。2）请求表：整个系统一张。）请求表：整个系统一张。说明每个作业的页表存放位置及长度。说明每个作业的页表存放位置及长度。3）存储页面表：整个系统一张。）存储页面表：整个系统一张。反映系统中空白页面的位置。反映系统中空白页面的位置。n分配算法：分配算法：1）根据请求表中作业的页表长度在存储页面表中计）根据请求表中作业的页表长度在存储页面表中计算有无足够的空白页面；算有无足够的空白页面；2）如果有足够空白页面，则开始填写该作业页表中）如果有足够空白页面，则开始填写该作业页表中相关数据。相关数据。n回收算法：回收算法：当进程运行结束，系统将该进程页表中各当进程运行结束，系统将该进程页表中各个页面插入系统存储页面表，并删除该进个页面插入系统存储页面表，并删除该进程的页表。程的页表。优点：实现了非连续存储，一定程度上解优点：实现了非连续存储，一定程度上解决了内存碎片问题。决了内存碎片问题。缺点：由于要求将作业的全部页面一次性缺点：由于要求将作业的全部页面一次性都装入内存，所以无法实现虚拟存储。都装入内存，所以无法实现虚拟存储。5.4.3动态页式管理动态页式管理原理：动态页式管理并不在作业执行前将其原理：动态页式管理并不在作业执行前将其一次性完整地装入内存，而是一次性完整地装入内存，而是先装入当前运先装入当前运行必要的一部分行必要的一部分，其余部分待作业运行过程，其余部分待作业运行过程中根据需要装入，并且中根据需要装入，并且将内存中暂时不需要将内存中暂时不需要的部分页面换到外存上的部分页面换到外存上。根据页面置换方式的不同，可分为根据页面置换方式的不同，可分为请求页式请求页式管理和预调入页式管理管理和预调入页式管理。请求页式管理：请求页式管理：当需要的程序代码或数据不当需要的程序代码或数据不在内存中时，系统产生缺页中断，将放在外在内存中时，系统产生缺页中断，将放在外存的相应页调入内存。存的相应页调入内存。预调入页式管理：预调入页式管理：系统对存放在外存的页进系统对存放在外存的页进行调入顺序的估算，计算其应被执行或访问行调入顺序的估算，计算其应被执行或访问的顺序，并按此顺序安排页的调入和调出。的顺序，并按此顺序安排页的调入和调出。请求式分页存储管理请求式分页存储管理n先把内存空间划分成大小相等的块，将用先把内存空间划分成大小相等的块，将用户逻辑地址空间划分成与块相等的页，每户逻辑地址空间划分成与块相等的页，每页可装入到内存中任一块中，这都类似于页可装入到内存中任一块中，这都类似于纯分页式存储管理。在请求式分页存储管纯分页式存储管理。在请求式分页存储管理的地址重定位时，可能会出现所需页面理的地址重定位时，可能会出现所需页面不在主存的情况，不在主存的情况，如图如图5.18所示是请求式分所示是请求式分页存储管理的存储映像。页存储管理的存储映像。n请求式分页存储管理中的地址重定位和缺请求式分页存储管理中的地址重定位和缺页中断处理过程如图页中断处理过程如图5.19所示。所示。图4.18 请求式分页存储管理示意图图4.19 请求式分页存储管理缺页中断处理过程示意图请求页式管理需解决的问题请求页式管理需解决的问题n记录各个页是存放在内存还是外存；记录各个页是存放在内存还是外存；n需调入外存上的虚页而内存无足够空间时需调入外存上的虚页而内存无足够空间时的解决方法（页面置换）；的解决方法（页面置换）；n如何解决抖动现象。如何解决抖动现象。n抖动：抖动：系统在内存和外存之间频繁地进行系统在内存和外存之间频繁地进行页的换进换出。页的换进换出。页面置换算法页面置换算法n1最优算法（最优算法（OPT算法）算法）n2先进先出算法（先进先出算法（FIFO算法）算法）n3最久未使用页面置换算法（最久未使用页面置换算法（LRU算法）算法）n4LRU近似算法近似算法 置换算法在内存没有空闲页面时使用，其置换算法在内存没有空闲页面时使用，其目的是选出一个被淘汰的页面用于存放调入的目的是选出一个被淘汰的页面用于存放调入的页。页。1最优算法（最优算法（OPT算法）算法）n最最理理想想的的页页面面置置换换算算法法是是：从从内内存存中中移移出出以以后后不不再再使使用用的的页页面面；如如无无这这样样的的页页面面，则则选选择择以以后后最最长长时时间间内内不不需需要要访访问问的的页页。这就是最优算法的思想。这就是最优算法的思想。2先进先出算法（先进先出算法（FIFO算法）算法）n这种算法的基本思想是：总是先淘汰那些这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。这内存的页面不再被访问的可能性最大。这种算法实现起来比较简单。如图种算法实现起来比较简单。如图5.20所示所示 图4.20 先进先出算法存储分块表构造 先进先出算法中的先进先出算法中的Belady现象现象Belady现象：现象：在使用在使用FIFO算法时，当未给进程算法时，当未给进程或作业分配足它所要求的页面数时，有时会或作业分配足它所要求的页面数时，有时会出现分配的页面数目越多，缺页次数反而增出现分配的页面数目越多，缺页次数反而增加的现象。加的现象。原因：原因：FIFO算法的设计思想基于程序的结构是算法的设计思想基于程序的结构是顺序结构的，但是很多时候程序的执行是非顺序结构的，但是很多时候程序的执行是非线性的，例如循环。线性的，例如循环。n例：进程例：进程P共有共有8页，程序的执行顺序是页，程序的执行顺序是7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1，请给出该进程在执，请给出该进程在执行中产生缺页中断的次数：行中产生缺页中断的次数：n1）系统在内存中分配给它了）系统在内存中分配给它了3个页面；个页面；n2）系统在内存中分配给它了）系统在内存中分配给它了4个页面。个页面。3最久未使用页面置换算法（最久未使用页面置换算法（LRU算法）算法）n这这种种算算法法的的基基本本思思想想是是，如如果果某某一一页页被被访访问问了了，那那么么它它很很可可能能马马上上又又被被访访问问；反反之之，如如果果某某一一页页很很长长时时间间没没有有被被访访问问，那那么么最最近近也也不不太太可可能能会会被被访访问问。这这种种算算法法考考虑虑了了程程序序设设计计的的局局部部性性原原理理。其其实实质质是是，当当需需要要置置换换一一页页时时，选选择择在在最最近近一一段段时时间间最最久久未使用的页面予以淘汰。未使用的页面予以淘汰。4LRU近似算法近似算法n这种算法，只要在存储分块表（或页表）这种算法，只要在存储分块表（或页表）中设一个中设一个“引用位引用位”，当存储分块表中的，当存储分块表中的某一页被访问时，该位由硬件自动置某一页被访问时，该位由硬件自动置1，并，并由页面管理软件周期性把所有引用位置由页面管理软件周期性把所有引用位置0。这样，在一个时间周期这样，在一个时间周期T内，某些被访问过内，某些被访问过的页面其引用位为的页面其引用位为1，而未被访问过的页面，而未被访问过的页面其引用位为其引用位为0。n根据引用位的状态来判别各页面最近的使根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用情况。当需要置换一页面时，选择其引用位为用位为0的页，如图的页，如图5.215.22所示的算法。所示的算法。图5.21 LRU近似算法流程图5.22 LRU近似算法举例返回本节*动态页式动态页式存储管理性能分析存储管理性能分析n优点：优点：1）由于实现了程序虚页的非连续）由于实现了程序虚页的非连续存储，解决了内存碎片问题；存储，解决了内存碎片问题；2）由于采用了程序的部分装入技术，实）由于采用了程序的部分装入技术，实现了虚拟存储。现了虚拟存储。n 缺点：缺点：1）增加了系统开销和成本；）增加了系统开销和成本；2）可能产生抖动，影响系统的效率；）