第五章 存储管理(1).ppt

第五章存储管理(1)第五章第五章 存储管理存储管理v5.1 存储管理的功能存储管理的功能v5.2 分区存储管理分区存储管理v5.3 覆盖和交换覆盖和交换v5.4 页式管理页式管理v5.5 段式与段页式管理段式与段页式管理v5.6 局部性原理与抖动问题局部性原理与抖动问题25.1.1 虚拟存储器虚拟存储器源程序源程序目标代码目标代码 地址安排？地址安排？v按照物理存储器中的位置赋予实际物理地址。按照物理存储器中的位置赋予实际物理地址。优点：优点：CPU 执行目标代码时的执行速度高。执行目标代码时的执行速度高。缺点：缺点：能装入内存并发执行的进程数大大减少，对于某能装入内存并发执行的进程数大大减少，对于某些较大的进程可能会无法执行；编译程序将非常复杂，些较大的进程可能会无法执行；编译程序将非常复杂，编译程序必须知道内存的当前空闲部分及其地址，并编译程序必须知道内存的当前空闲部分及其地址，并且把一个进程的不同程序段连续地存放起来且把一个进程的不同程序段连续地存放起来6 由编译链接程序编译后链接（静态、动态）到一由编译链接程序编译后链接（静态、动态）到一个以个以0地址为始地址的线性或多维地址为始地址的线性或多维虚拟地址空间虚拟地址空间（逻辑地址空间逻辑地址空间）。每个进程都拥有一个虚拟地址空间。每个指令或数据单每个进程都拥有一个虚拟地址空间。每个指令或数据单元都在这个虚拟空间中拥有确定的地址，把这个地址元都在这个虚拟空间中拥有确定的地址，把这个地址称为称为虚拟地址虚拟地址（virtual address）(逻辑地址逻辑地址)。地址转换地址转换Load A 200 3456 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译链接链接虚拟地址空间虚拟地址空间BA=100075.1.1 虚拟存储器虚拟存储器v虚拟存储器：虚拟存储器：进程中的目标代码、数据等的进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。虚拟地址组成的虚拟空间称为虚拟存储器。8实现虚拟内存的基本原理实现虚拟内存的基本原理v将将程程序序正正在在使使用用的的部部分分内内容容放放在在内内存存，而而暂暂时时不不用用的的部部分分放放在在外外存存，在在需需要要时时由由系系统统调调入入内内存存，并并将将不需要（或暂不需要）的部分调出内存。不需要（或暂不需要）的部分调出内存。v由由于于程程序序在在执执行行时时，在在一一段段时时间间内内一一般般仅仅使使用用它它的的程程序序的的一一部部分分（或或一一小小部部分分），所所以以程程序序仅仅有有部部分分装入内存完全能够正确执行。装入内存完全能够正确执行。v要由操作系统结合相关硬件来完成上述工件，这样要由操作系统结合相关硬件来完成上述工件，这样计算机好象为用户提供了一个容量远大于内存的存计算机好象为用户提供了一个容量远大于内存的存储器，这个存储器称为储器，这个存储器称为虚拟存储器虚拟存储器。95.1.1 虚拟存储器虚拟存储器v虚拟存储器虚拟存储器呈现在用户面前的是一个在呈现在用户面前的是一个在物理上只受物理上只受内存和外存总容量限制内存和外存总容量限制的存储系统，这要求存储管的存储系统，这要求存储管理系统只把进程执行时频繁使用和立即需要的指令理系统只把进程执行时频繁使用和立即需要的指令与数据等存放在内存中，而把那些暂时不需要的部与数据等存放在内存中，而把那些暂时不需要的部分存放在外存中，待需要时自动调入，以提高内存分存放在外存中，待需要时自动调入，以提高内存的利用率和并行执行的作业道数。的利用率和并行执行的作业道数。v虚拟存储器虚拟存储器不考虑不考虑物理存储器的大小和信息存放的物理存储器的大小和信息存放的实际位置实际位置，只规定只规定每个进程中互相关联的信息的每个进程中互相关联的信息的相相对位置对位置。v每个进程都拥有自己的虚拟存储器，且虚拟存储器每个进程都拥有自己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。的容量是由计算机的地址结构和寻址方式确定的。105.1.2 地址变换地址变换v地址重定位：地址重定位：从虚拟地址到内存地址的转换从虚拟地址到内存地址的转换称为称为地址重定位地址重定位，或称为，或称为地址映射地址映射。v地址映射的方式：地址映射的方式：1 1、静态地址重定位、静态地址重定位2 2、动态地址重定位、动态地址重定位111、静态地址重定位、静态地址重定位v在虚拟空间程序执行之前由装配程序完成在虚拟空间程序执行之前由装配程序完成地址映射的工作。地址映射的工作。不能实现虚拟存储器不能实现虚拟存储器v假定程序装入内存的首地址为假定程序装入内存的首地址为BA，程序地，程序地址为址为VA，内存地址为，内存地址为MA，则地址映射按下，则地址映射按下式进行：式进行：MA=(BA)+(VA)。12例例v程序装入内存的首地址为程序装入内存的首地址为1000，则，则装配程序就按装配程序就按MA=1000+VA对程序对程序中所有地址部分进行修改，修改后中所有地址部分进行修改，修改后指令指令Load A，200就变为就变为Load A，120013静态地址重定位的静态地址重定位的优缺点优缺点v优点：优点：不需要硬件的支持。不需要硬件的支持。v缺点：缺点：程序必须占用连续的内存空间，程序程序必须占用连续的内存空间，程序和数据不能共享；和数据不能共享；程序一旦装入内存之后就程序一旦装入内存之后就不能再移动，并且必须在程序执行之前将有不能再移动，并且必须在程序执行之前将有关部分全部装入。关部分全部装入。142、动态地址重定位、动态地址重定位v动态地址重定位是在程序执行的过程中，在动态地址重定位是在程序执行的过程中，在CPUCPU访问访问内存之前，将要访问的程序地址转换为内存地址。内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的一般来说这种转换是由专门的硬件机构硬件机构来完成的。来完成的。v在在地地址址重重定定位位机机构构中中，有有一一个个基基地地址址寄寄存存器器BR和和一一个个程序地址寄存器程序地址寄存器VR，一个，一个内存地址寄存器内存地址寄存器MR。MA=(BR)+(VR)152、动态地址重定位、动态地址重定位v动态地址重定位的具体过程：动态地址重定位的具体过程：程序装入内存后，它所占用的内存区的程序装入内存后，它所占用的内存区的首地址首地址由系统由系统送入送入基地址寄存器基地址寄存器BRBR中。中。在程序在程序执行的过程中执行的过程中，若要访问内存，将访问，若要访问内存，将访问的的逻辑地址送入逻辑地址送入程序地址寄存器程序地址寄存器VRVR中。中。地址转换机构地址转换机构把把VRVR和和BRBR中的内容相加中的内容相加，并将结，并将结果果送入送入MRMR中，作为实际访问的物理地址。中，作为实际访问的物理地址。16图图5.3 动态地址重定位动态地址重定位172、动态地址重定位、动态地址重定位v动态地址重定位的动态地址重定位的优点优点可可以以对对内内存存进进行行非非连连续续分分配配。程程序序占占用用的的内内存存空空间间是是动动态态可可变变的的，当当程程序序从从某某个个存存储储区区移移到到另另一一个个区区域域时时，只只需需要要修修改改相相应应的的寄寄存存器器BRBR的的内内容容即即可。可。提提供供了了实实现现虚虚拟拟存存储储器器的的基基础础。一一个个程程序序不不一一定定要要求求占占用用一一个个连连续续的的内内存存空空间间。可可以以部部分分地地装装入入程序运行。程序运行。便于多个进程共享同一个程序的代码。便于多个进程共享同一个程序的代码。182、动态地址重定位、动态地址重定位v动态地址重定位的代价：动态地址重定位的代价：需要硬件的支持。需要硬件的支持。实现存储管理的软件算法较为复杂。实现存储管理的软件算法较为复杂。195.1.3 内外存数据传输的控制内外存数据传输的控制v内外存数据传输的控制：内外存数据传输的控制：用户程序自己控制：用户程序自己控制：覆盖技术覆盖技术用户负担很用户负担很大，程序段的最大长度受内存容量限制，不能大，程序段的最大长度受内存容量限制，不能实现虚拟存储器。实现虚拟存储器。操作系统控制：操作系统控制：v交换交换(swapping)方式方式：不同的进程或作业之间：不同的进程或作业之间v请求调入请求调入(on demand)方式和方式和预调入预调入(on prefetch)方式方式205.1.4 内存的分配与回收内存的分配与回收v要要完完成成内内存存的的分分配配和和回回收收工工作作，要要求求设设计计者者选择和确定以下几种策略和结构：选择和确定以下几种策略和结构：分配结构分配结构调入策略调入策略放置策略放置策略交换策略交换策略回收策略回收策略215.1.4 内存的分配与回收内存的分配与回收v分配结构分配结构分配结构是用来登记内存使用情分配结构是用来登记内存使用情况的数据结构。如况的数据结构。如空闲区表、空闲区队列等。空闲区表、空闲区队列等。v调入策略调入策略用户程序在何时、怎样调入内存用户程序在何时、怎样调入内存的策略。的策略。v放置策略放置策略用户程序调入内存时，确定将其用户程序调入内存时，确定将其放置在何处的策略。放置在何处的策略。225.1.4 内存的分配与回收内存的分配与回收v交换策略交换策略当需要将某个用户程序调入内存当需要将某个用户程序调入内存而内存空间又不够时，就要确定哪个或哪些而内存空间又不够时，就要确定哪个或哪些程序可以从内存中移走。程序可以从内存中移走。v回收策略回收策略确定回收的时机和对所回收的内确定回收的时机和对所回收的内存空闲区和已存在的内存空闲区进行调整。存空闲区和已存在的内存空闲区进行调整。235.1.5 内存信息的共享与保护内存信息的共享与保护v保保证证在在内内存存中中的的多多道道程程序序只只能能在在给给定定的存储区域内活动并互不产生干扰。的存储区域内活动并互不产生干扰。v包括：包括：防止地址越界防止地址越界防止越权防止越权(对共享区有访问权对共享区有访问权)245.1.5 内存信息的共享与保护内存信息的共享与保护v内存保护的方法：内存保护的方法：硬件法、软件法硬件法、软件法和和软硬件法软硬件法。v上下界保护法上下界保护法：硬件法：硬件法 1 1、在、在CPUCPU中设置一对下限寄存器和上限寄存器存放中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址用户作业在主存中的下限和上限地址 2 2、每当、每当CPUCPU要访问主存，硬件自动将被访问的主存要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界地址与界限寄存器的内容进行比较，以判断是否越界 3 3、如果未越界，则按此地址访问主存，否则将产生、如果未越界，则按此地址访问主存，否则将产生程序中断程序中断越界中断越界中断（存储保护中断）（存储保护中断）25图图5.4 上、下界寄存器保护法上、下界寄存器保护法265.1.5 内存信息的共享与保护内存信息的共享与保护v保护键法：保护键法：软件法软件法 为每一个被保护的存储块分配一个单独为每一个被保护的存储块分配一个单独的保护键。在程序状态字中设置相应的保的保护键。在程序状态字中设置相应的保护键开关字段，访问过程中比较保护开关护键开关字段，访问过程中比较保护开关字段的内容和保护键是否匹配，匹配则允字段的内容和保护键是否匹配，匹配则允许访问，否则产生访问出错中断。许访问，否则产生访问出错中断。27图图5.5 保护键保护法保护键保护法285.1.5 内存信息的共享与保护内存信息的共享与保护v界限寄存器与界限寄存器与CPU的用户态或核心态工作方的用户态或核心态工作方式相结合的保护方式。式相结合的保护方式。软硬件法软硬件法 用户态进程只能访问那些在界限寄存器用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。可以访问整个内存地址空间。295.2 分区存储管理分区存储管理v把把整整个个内内存存划划分分为为若若干干大大小小不不等等的的区区域域，操操作作系系统统占占用用一一个个区区域域，其其它它区区域域供供系系统统中中的的多多个进程共享，这种方法称为个进程共享，这种方法称为分区存储管理分区存储管理。5.2.1 5.2.1 分区存储管理的基本原理分区存储管理的基本原理5.2.2 5.2.2 分区的分配与回收分区的分配与回收5.2.3 5.2.3 有关分区管理其他问题讨论有关分区管理其他问题讨论 305.2.1 5.2.1 分区存储管理的基本原理分区存储管理的基本原理v基基本本原原理理：给给每每一一个个内内存存中中的的进进程程划划分分一一块块适适当当大大小小的的存存储储区区,以以连连续续存存储储各各进进程程的的程程序序和数据，使各进程得以并发执行。和数据，使各进程得以并发执行。这是最简单的一种存储管理这是最简单的一种存储管理，按分区划分按分区划分的时机可分为：的时机可分为：1 1、固定分区、固定分区 2 2、动态分区、动态分区311 1、固定分区、固定分区v固固定定分分区区：把把内内存存固固定定地地划划分分为为若若干干个个大大小小不不等等的的区区域域。分分区区的的划划分分由由计计算算机机的的操操作作员员或或者者由由操操作作系系统统给给出出，并并给给出出分分区区说说明明表表。在在调调度度作作业业时时，由由存存储储管管理理根根据据所所需需量量在在分分区说明表中找出一个单元分配给它。区说明表中找出一个单元分配给它。321 1、固定分区、固定分区v分区说明表分区说明表分区号分区号大小大小(KB)始址始址状态状态1820已分配已分配23228已分配已分配36460已分配已分配4132124未分配未分配33图图5.6 固定分区法固定分区法341 1、固定分区、固定分区v在在作作业业大大小小和和出出现现频频率率均均已已知知的的情情况况下下，固固定定分分区区是是合合适适的的。在在这这种种情情况况下下分分区区的的大大小小选选择择与与作作业业大大小小相相当当，这这样样内内存存的的使使用用效效率率较高。较高。v但但是是若若作作业业的的大大小小和和出出现现的的频频率率不不知知道道时时，势势必必造造成成分分区区的的大大小小和和作作业业的的大大小小相相差差甚甚远远，这这样样就就会会造造成成存存储储空空间间的的浪浪费费，从从而而影影响响整整个系统的效率。个系统的效率。352 2、动态分区、动态分区v动动态态分分区区：在在系系统统运运行行的的过过程程中中建建立立分分区区，并使分区的大小刚好与作业的大小相等。并使分区的大小刚好与作业的大小相等。v这这种种存存储储管管理理的的方方法法解解决决了了固固定定分分区区严严重重浪浪费费内内存存的的问问题题。是是一一种种较较为为实实用用的的存存储储管管理理方法。方法。36图图5.7 动态分区内存初始分配情况动态分区内存初始分配情况372 2、动态分区、动态分区v 在实现动态分区分配的时候需要涉及到以下在实现动态分区分配的时候需要涉及到以下三个方面的问题：三个方面的问题：动态分配中所用到的数据结构动态分配中所用到的数据结构；分区的分配算法；分区的分配算法；分区的分配和回收操作。分区的分配和回收操作。382 2、动态分区、动态分区v实现动态分区的数据结构：实现动态分区的数据结构：在在动动态态分分区区存存储储管管理理中中，要要有有相相应应的的数数据据结结构构来来登登记记空空闲闲区区的的说说明明信信息息，它它包包括括空空闲闲区区的的大大小小和和位位置置。其其数数据据结结构构有有：分分区区说说明明表表、可可用用分分区表（或自由链）、请求表。区表（或自由链）、请求表。分区说明表分区说明表可用分区表：可用分区表：用于为内存中每个还没有分区设用于为内存中每个还没有分区设置一个表项，每个分区表项包含分区序号、分置一个表项，每个分区表项包含分区序号、分区起始地址以及分区大小。（占用内存）区起始地址以及分区大小。（占用内存）392 2、动态分区、动态分区v实现动态分区的数据结构：实现动态分区的数据结构：自由链：自由链：利用每个内存空闲区的头几个单元存放利用每个内存空闲区的头几个单元存放本空闲区的大小和下个空闲区的起始地址，将所本空闲区的大小和下个空闲区的起始地址，将所有空闲区组成一条链。（不占用内存）有空闲区组成一条链。（不占用内存）请求表：请求表：表的每个表目描述请求内存资源的作表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。业或进程号以及所请求的内存大小。40图图5.9 可用表、自由链及请求表可用表、自由链及请求表41图图5.8 内存分配变化过程内存分配变化过程425.2.2 分区的分配与回收分区的分配与回收v1、固定分区的分配与回收、固定分区的分配与回收v2、动态分区时的分配与回收、动态分区时的分配与回收v3、动态分区时的回收与拼接、动态分区时的回收与拼接v4、几种分配算法的比较、几种分配算法的比较431、固定分区的分配与回收、固定分区的分配与回收v分配：分配：当用户程序要装入执行时，通过请求当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大表提出内存分配要求和所要求的内存空间大小。存储管理程序小。存储管理程序根据请求表要求查询分区根据请求表要求查询分区说明表说明表，从中找出一个满足要求的空闲分区，从中找出一个满足要求的空闲分区，将其分配给申请者。将其分配给申请者。P117图图v回收：回收：回收时管理程序只需将对应的分区状回收时管理程序只需将对应的分区状态置为未使用即可。态置为未使用即可。442、动态分区时的分配与回收、动态分区时的分配与回收v主要解决的三个问题主要解决的三个问题:(1)对于请求表中的要求内存长度，从可用表或对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。自由链中寻找出合适的空闲区分配程序。(2)分配空闲区之后，更新可用表或自由链。分配空闲区之后，更新可用表或自由链。(3)进程或作业释放内存资源时，和相邻的空闲进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。区进行链接合并，更新可用表或自由链。452、动态分区时的分配与回收、动态分区时的分配与回收v从可用表或自由链中寻找空闲区的常用的三从可用表或自由链中寻找空闲区的常用的三种方法：种方法：最先适应法最先适应法(first fit algorithm)最佳适应法最佳适应法(best fit algorithm)最坏适应法最坏适应法(worst fit algoriathm)这三种方法要求可用表或自由链按不同的方式排列。这三种方法要求可用表或自由链按不同的方式排列。46最先适应法最先适应法v要求可用表或自由链要求可用表或自由链按起始地址递增的次序按起始地址递增的次序排列排列。v分配：分配：当进程申请大小为当进程申请大小为SIZESIZE的内存时，的内存时，存存储管理程序储管理程序从空闲区表的第一个表目开始查从空闲区表的第一个表目开始查询，直到首次找到等于或大于询，直到首次找到等于或大于SIZESIZE的空闲区。的空闲区。从该区中划出大小为从该区中划出大小为SIZESIZE的分区分配给进程，的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。中，但要修改其首址和大小。47最先适应法最先适应法v回收：回收：按释放区的首址，查询空闲区表，若按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址把释放区作为一个空闲区，将其大小和首址按照首地址大小递增按照首地址大小递增的顺序插入到空闲区表的顺序插入到空闲区表的适当位置。的适当位置。48最先适应法的最先适应法的优点优点v释放某一存储区时，若与空闲区相邻则合并释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。区在表中的位置，只要修改其大小或首址。v这种算法是尽可能地利用低地址空间，从而这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。保证高地址空间有较大的空闲区。49最佳适应法最佳适应法v要求按要求按空闲区大小从小到大空闲区大小从小到大的次序组成空闲的次序组成空闲区表（队列）。区表（队列）。v分配：分配：当当用户作业或用户作业或进程申请一个存储区时，进程申请一个存储区时，存储存储管理程序管理程序从表头开始查找，当找到第一个满足要求从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是的空闲区时，停止查找，并且这个空闲区是最佳的最佳的空闲区空闲区（选中的空闲区是满足要求的最小空闲区）选中的空闲区是满足要求的最小空闲区）。如果该空闲区大于请求表中的请求长度，则与最先如果该空闲区大于请求表中的请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中。分留在可用表中。50最佳适应法最佳适应法v回回收收：按按释释放放区区的的首首址址，查查询询空空闲闲区区表表（队队列列），若若有有与与释释放放区区相相邻邻的的空空闲闲区区，则则合合并并到到相相邻邻的的空空闲闲区区中中，并并修修改改该该区区的的大大小小和和首首址址，否否则则，把把释释放放区区作作为为一一个个空空闲闲区区插插入入空闲区表（队列）空闲区表（队列）。v分分配配和和回回收收后后要要对对空空闲闲区区表表（队队列列）重重新新排排序。序。51最佳适应算法的最佳适应算法的优点优点v在在系系统统中中若若存存在在一一个个与与申申请请分分区区大大小小相相等等的的空空闲闲区区，必必定定会会被被选选中中，而而最最先先适适应应法法则则不不一定。一定。v若若系系统统中中不不存存在在与与申申请请分分区区大大小小相相等等的的空空闲闲区区，则则选选中中的的空空闲闲区区是是满满足足要要求求的的最最小小空空闲闲区，而不致于毁掉较大的空闲区。区，而不致于毁掉较大的空闲区。52最佳适应算法的最佳适应算法的缺点缺点v 空闲区的大小一般与申请分区大小不相等，空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储系统中的小空闲区会越来越多，从而造成存储区的大量浪费。区的大量浪费。53最坏适应算法最坏适应算法v 要求空闲区按要求空闲区按由大至小递减由大至小递减的顺序组织空闲的顺序组织空闲区表（或队列）。区表（或队列）。v分配：分配：进程申请一个大小为进程申请一个大小为SIZE的存储区时，的存储区时，总是检查空闲区表的第一个空闲区的大小是否总是检查空闲区表的第一个空闲区的大小是否大于或等于大于或等于SIZE。若空闲区小于。若空闲区小于SIZE，则分，则分配失败；否则从空闲区中分配配失败；否则从空闲区中分配SIZE的存储区给的存储区给用户，然后修改和调整空闲区表。用户，然后修改和调整空闲区表。54最坏适应算法最坏适应算法v回回收收：按按释释放放区区的的首首址址，查查询询空空闲闲区区表表（队队列列），若若有有与与释释放放区区相相邻邻的的空空闲闲区区，则则合合并并到到相相邻邻的的空空闲闲区区中中，并并修修改改该该区区的的大大小小和和首首址址，否否则则，把把释释放放区区作作为为一一个个空空闲闲区区插插入入空空闲区表（队列）。闲区表（队列）。v分分配配和和回回收收后后要要对对空空闲闲区区表表（队队列列）重重新新排排序。序。55最坏适应算法的优点最坏适应算法的优点v当当程程序序装装入入内内存存中中最最大大的的空空闲闲区区后后，剩剩下下的的空闲区还可能相当大，还能装下较大的程序。空闲区还可能相当大，还能装下较大的程序。v每次仅作一次查询工作。每次仅作一次查询工作。563、动态分区时分区的回收、动态分区时分区的回收v当当某某个个进进程程释释放放某某存存储储区区时时，系系统统首首先先检检查查释释放放区区是是否否与与系系统统中中的的空空闲闲区区相相邻邻，若若相相邻邻则则把把释释放放区区合合并并到到相相邻邻的的空空闲闲区区中中去去，否否则则把把释释放放区区作作为为一一个个空空闲闲区区插插入入到到空空闲闲区区表表的的适适当当位位置。置。57图图5.12 空闲区的合并空闲区的合并58空闲区的合并空闲区的合并v释放区与上下两空闲区相邻：释放区与上下两空闲区相邻：将三个空闲区合并为将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起一个空闲区。新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲区合并后，始地址，大小为三个空闲区之和。空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。修改上空闲区的对应项。v释放区只与上空闲区相邻：释放区只与上空闲区相邻：将释放区与上空闲区合将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后，修改址，大小为上空闲区与释放区之和。合并后，修改上空闲区对应的可用表的表目项或自由链指针。上空闲区对应的可用表的表目项或自由链指针。59空闲区的合并空闲区的合并v释放区与下空闲区相邻：释放区与下空闲区相邻：将释放区与下空闲将释放区与下空闲区合并，并将释放区的起始地址作为合并区区合并，并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空的起始地址。合并区的长度为释放区与下空闲区之和。合并后修改可用表或自由链中相闲区之和。合并后修改可用表或自由链中相应的表目项或链指针。应的表目项或链指针。v释放区不与任何空闲区相邻：释放区不与任何空闲区相邻：释放区作为一释放区作为一个新可用区插入可用表或自由链。个新可用区插入可用表或自由链。604、三种分配算法的比较、三种分配算法的比较v三种算法的优缺点比较三种算法的优缺点比较搜索速度：搜索速度：最先适应算法最先适应算法具有具有最佳性能最佳性能，最佳适应算法，最佳适应算法和最坏适应算法都要求把不同大小的空闲区按大小进行和最坏适应算法都要求把不同大小的空闲区按大小进行排队；排队；回收过程回收过程：最先适应算法最先适应算法具有具有最佳性能，最佳性能，因为最佳适应因为最佳适应算法和最坏适应算法都必须重新调整空闲区的位置；算法和最坏适应算法都必须重新调整空闲区的位置；空闲区利用：空闲区利用：最佳适应法找到的空闲区是最佳的，最佳适应法找到的空闲区是最佳的，但是但是会造成内存碎片较多，影响内存利用率，而最坏适用法会造成内存碎片较多，影响内存利用率，而最坏适用法的内存碎片最少，但是对内存的请求较多的进程有可能的内存碎片最少，但是对内存的请求较多的进程有可能分配失败。分配失败。总之，三种算法各有所长，针对不同的请求队列，它们的总之，三种算法各有所长，针对不同的请求队列，它们的效率和功能是不一样的。效率和功能是不一样的。614、三种分配算法的比较、三种分配算法的比较v上上述述三三种种放放置置策策略略各各有有利利弊弊，到到底底哪哪种种最最好好不不能能一一概概而而论论，而而应应针针对对具具体体作作业业序序列列来分析。来分析。v对对于于某某一一作作业业序序列列来来说说，某某种种算算法法能能将将该该作作业业序序列列中中所所有有作作业业安安置置完完毕毕，那那么么我我们们说说该算法对这一作业序列是合适的。该算法对这一作业序列是合适的。v对于某一算法而言，如它不能立即满足某对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，一要求，而其它算法却可以满足此要求，则则这一算法对该作业序列是不合适的。这一算法对该作业序列是不合适的。62例题例题v例例1 1：有有作作业业序序列列：作作业业A A要要求求18K18K；作作业业B B要要求求25K25K，作作业业C C要要求求30K30K。系系统统中中空空闲闲区区按按三三种种算算法法组组成成的的空空闲闲区区队队列列，现现在在请请你你分分析析哪哪种种算算法法适合该作业序列？适合该作业序列？OS30作业作业作业作业2046作业作业5205010012016016016521025663 例题例题最先最先分配前内存分配前内存 分配前内存自由链分配前内存自由链作业作业 请求长度请求长度A18B25C30请求表请求表64例题例题v经经分分析析可可知知：最最佳佳适适应应法法对对这这个个作作业业序序列列是是合合适适的的，而而其其它它两两种种对对该该作作业业序序列列是是不不合合适适的。的。v因为最先适应算法和最坏适应算法对于作业因为最先适应算法和最坏适应算法对于作业C来说都不能为它分配所需要的内存空间。来说都不能为它分配所需要的内存空间。65练练 习习v如果现在作业序列变为以下情况，分析如果现在作业序列变为以下情况，分析哪种算法适合于这个作业序列？哪种算法适合于这个作业序列？作业作业A A要求要求21K21K，作业，作业B B要求要求30K30K，作业，作业C C要求要求25K25K。665.2.3 有关分区管理其他问题的讨论有关分区管理其他问题的讨论v1、关于虚存的实现、关于虚存的实现v2、关于内存扩充、关于内存扩充v3、关于地址变换和内存保护、关于地址变换和内存保护v4、分区存储管理的主要优缺点、分区存储管理的主要优缺点671、关于虚存的实现、关于虚存的实现v无法实现那种用户进程所需内存容量只受内无法实现那种用户进程所需内存容量只受内存和外存容量之和限制的虚拟存储器。存和外存容量之和限制的虚拟存储器。v如果不采用内存扩充技术，每个用户进程所如果不采用内存扩充技术，每个用户进程所需内存容量是受到分区大小限制的。需内存容量是受到分区大小限制的。682、关于内存扩充、关于内存扩充v可以使用覆盖或交换技术来扩充内存可以使用覆盖或交换技术来扩充内存693、关于地址变换和内存保护、关于地址变换和内存保护v静态地址重定位和动态地址重定位技术，都静态地址重定位和动态地址重定位技术，都可用来完成分区式内存管理的地址变换。可用来完成分区式内存管理的地址变换。v不能使用静态地址重定位的方法来完成动态不能使用静态地址重定位的方法来完成动态分区时的地址变换。分区时的地址变换。v动态地址重定位中的一对硬件寄存器除了完动态地址重定位中的一对硬件寄存器除了完成动态地址重定位的功能之外，还具有保护成动态地址重定位的功能之外，还具有保护内存中数据和程序的功能。内存中数据和程序的功能。v保护键法也可用来对内存各分区提供保护。保护键法也可用来对内存各分区提供保护。704、分区存储管理的主要优缺点、分区存储管理的主要优缺点v优点：优点：实现了多个作业或进程对内存的共享，提高了系实现了多个作业或进程对内存的共享，提高了系统的资源利用率。统的资源利用率。该方法要求的硬件支持少，管理算法简单，实现该方法要求的硬件支持少，管理算法简单，实现容易。容易。v缺点：缺点：内存利用率仍然不高，因为依然存在着碎小的空内存利用率仍然不高，因为依然存在着碎小的空闲区不能利用的问题。闲区不能利用的问题。作业或进程的大小受分区大小的影响。除非配合作业或进程的大小受分区大小的影响。除非配合覆盖和交换技术。覆盖和交换技术。难以实现各分区的信息共享。难以实现各分区的信息共享。715.3 覆盖与交换技术覆盖与交换技术 在多道环境下扩充内存的方法，用以解决在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛在较小的存储空间中运行较大程序时遇到的矛盾。盾。v覆盖技术主要用在早期的操作系统中；覆盖技术主要用在早期的操作系统中；v交换技术被广泛用于小型分时系统中，交换交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现。技术的发展导致了虚存技术的出现。72覆盖技术与交换技术异同点：覆盖技术与交换技术异同点：v共同点：共同点：进程的程序和数据主要放在外存，当进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存前需要执行的部分放在内存，内外存之间进行信息交换。之间进行信息交换。v不同点：不同点：如何控制交换？如何控制交换？73覆盖技术覆盖技术v把程序划分为若干个功能上相对独立的程序把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域。执行的程序段共享同一块内存区域。v程序段先保存在磁盘上，当有关程序段的前程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存覆盖前面的程序段（内存“扩大扩大”了）。了）。v一般要求作业各模块之间有明确的调用结构，一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作程序员要向系统指明覆盖结构，然后由操作系统完成自动覆盖。系统完成自动覆盖。74A8KB8KC10KD12KE4KF10K覆盖区覆盖区0（10K）覆盖区覆盖区1（12K）BC CE FD作业作业X X的常驻区的常驻区 A A（8K8K）75交换技术交换技术v为什么引入交换技术？为什么引入交换技术？当内存空间紧张时，系统将内存中某些进程暂当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。与外存之间的动态调度。多用于分时系统中多用于分时系统中76v交换进程包括两个过程：交换进程包括两个过程：换出换出把内存中的数据和程序换到外存把内存中的数据和程序换到外存交换区。交换区。换入换入把外存交换区的数据和程序换到把外存交换区的数据和程序换到内存分区中。内存分区中。何时需发生交换？何时需发生交换？只要不用就换出（或很少再用）只要不用就换出（或很少再用）只在内存空间不够或有不够的危险只在内存空间不够或有不够的危险时换出时换出77覆盖技术与交换技术的分析比较覆盖技术与交换技术的分析比较v与覆盖技术相比，交换技术不要求用户给出与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；程序段之间的逻辑覆盖结构；v交换发生在进程或作业之间，而覆盖发生在交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。同一进程或作业内。v覆盖只能覆盖那些与覆盖段无关的程序段。覆盖只能覆盖那些与覆盖段无关的程序段。78此此课件下件下载可自行可自行编辑修改，修改，仅供参考！供参考！感感谢您的支持，我您的支持，我们努力做得更好！努力做得更好！谢谢!