《计算机操作系统 第5章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统 第5章.ppt（186页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第5 5章章 存储管理存储管理5.1 5.1 存储管理的功能存储管理的功能5.2 5.2 分区存储管理分区存储管理5.3 5.3 覆盖与交换技术覆盖与交换技术5.4 5.4 页式管理页式管理5.5 5.5 段式与段页式管理段式与段页式管理5.6 5.6 局部性原理和抖动问题局部性原理和抖动问题习习 题题5.1 5.1 存储管理的功能存储管理的功能存储器是计算机系统的重要资源之一。因为任何程存储器是计算机系统的重要资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占用一序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储管理直接影响系统性能。定的存储空间，因此，存储管理
2、直接影响系统性能。存储器由内存和外存组成。内存由顺序编址的块组存储器由内存和外存组成。内存由顺序编址的块组成，每块包含相应的物理单元。成，每块包含相应的物理单元。CPU CPU 要通过启动相要通过启动相应的输入输出设备后才能使外存与内存交换信息。应的输入输出设备后才能使外存与内存交换信息。本章主要讨论内存管理问题。主要包括：几种常用本章主要讨论内存管理问题。主要包括：几种常用的内存管理方法、内存的分配和释放算法、虚拟存的内存管理方法、内存的分配和释放算法、虚拟存储器的概念、控制主存和外存之间的数据流动方法、储器的概念、控制主存和外存之间的数据流动方法、地址变换技术和内存数据保护与共享技术等。下
3、面地址变换技术和内存数据保护与共享技术等。下面先介绍存储管理的功能。先介绍存储管理的功能。5.1.1 5.1.1 虚拟存储器虚拟存储器虚拟存储器是存储管理的核心概念。现代计算虚拟存储器是存储管理的核心概念。现代计算机系统的物理存储器都分为内存和外存，内存机系统的物理存储器都分为内存和外存，内存价格比外存价格昂贵，不可能用大容量的内存价格比外存价格昂贵，不可能用大容量的内存存储所有被访问的或不被访问的程序与数据段。存储所有被访问的或不被访问的程序与数据段。而外存尽管访问速度较慢，但价格便宜，适合而外存尽管访问速度较慢，但价格便宜，适合于存放大量信息。这样，存储管理系统把进程于存放大量信息。这样，
4、存储管理系统把进程中那些不经常被访问的程序段和数据放入外存中那些不经常被访问的程序段和数据放入外存中，待需要访问它们时再将它们调入内存。那中，待需要访问它们时再将它们调入内存。那么，对于那些一部分数据和程序段在内存而另么，对于那些一部分数据和程序段在内存而另一部分则在外存的进程，怎样安排它们的地址一部分则在外存的进程，怎样安排它们的地址呢？呢？通常由用户编写的源程序，首先要由编译通常由用户编写的源程序，首先要由编译程序编译成程序编译成CPU CPU 可执行的目标代码。然可执行的目标代码。然后，链接程序把一个进程的不同程序段后，链接程序把一个进程的不同程序段链接起来以完成所要求的功能。链接起来以
5、完成所要求的功能。显然，对于不同的程序段，应具有不同的显然，对于不同的程序段，应具有不同的地址。有两种方法安排这些编译后的目地址。有两种方法安排这些编译后的目标代码的地址。标代码的地址。一种方法是按照物理存储器中的位置赋予实际一种方法是按照物理存储器中的位置赋予实际物理地址。这种方法的好处是物理地址。这种方法的好处是CPU CPU 执行目标代执行目标代码时的执行速度高。但是，由于物理存储器的码时的执行速度高。但是，由于物理存储器的容量限制，能装入内存并发执行的进程数将会容量限制，能装入内存并发执行的进程数将会大大减少，对于某些较大的进程来说，当其所大大减少，对于某些较大的进程来说，当其所要求的
6、总内存容量超过内存容量时将会无法执要求的总内存容量超过内存容量时将会无法执行。另外，由于编译程序必须知道内存的当前行。另外，由于编译程序必须知道内存的当前空闲部分及其地址，并且把一个进程的不同程空闲部分及其地址，并且把一个进程的不同程序段连续地存放起来，因此编译程序将非常复序段连续地存放起来，因此编译程序将非常复杂。杂。另一种方法是编译链接程序把用户源程序编译另一种方法是编译链接程序把用户源程序编译后链接到一个以后链接到一个以0 0地址为始地址的线性或多维地址为始地址的线性或多维虚拟地址空间。这里，链接既可以是在程序执虚拟地址空间。这里，链接既可以是在程序执行以前由链接程序完成的静态链接，也可
7、以是行以前由链接程序完成的静态链接，也可以是在程序执行过程中由于需要而进行的动态链接。在程序执行过程中由于需要而进行的动态链接。而且，每一个进程都拥有这样一个空间（这个而且，每一个进程都拥有这样一个空间（这个空间是一维的还是多维的由存储管理方式决定）空间是一维的还是多维的由存储管理方式决定）。每个指令或数据单元都在这个虚拟空间中拥。每个指令或数据单元都在这个虚拟空间中拥有确定的地址，把这个地址称为虚拟地址有确定的地址，把这个地址称为虚拟地址（virtual addressvirtual address）。显然，进程在该空间的地址排列可以是非连显然，进程在该空间的地址排列可以是非连续的，其实际物
8、理地址由虚拟地址到实际物续的，其实际物理地址由虚拟地址到实际物理地址的地址变换机构变换得到。由源程序理地址的地址变换机构变换得到。由源程序到实际存放该程序指令或数据的内存物理位到实际存放该程序指令或数据的内存物理位置的变换如图所示。置的变换如图所示。地址变换与物理存储器图地址变换与物理存储器图将进程中的目标代码。数据等的虚拟地址组成将进程中的目标代码。数据等的虚拟地址组成的虚拟空间称为虚拟存储器的虚拟空间称为虚拟存储器。虚拟存储器不考虚拟存储器不考虑物理存储器的大小和信息存放的实际位置，虑物理存储器的大小和信息存放的实际位置，只规定每个进程中互相关连的信息的相对位置。只规定每个进程中互相关连的
9、信息的相对位置。与实际物理存储器只有一个（单机系统中），与实际物理存储器只有一个（单机系统中），且被所有进程共享不一样，每个进程都拥有自且被所有进程共享不一样，每个进程都拥有自己的虚拟存储器，且虚拟存储器的容量是由计己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。例如，直算机的地址结构和寻址方式确定的。例如，直接寻址时，如果接寻址时，如果CPU CPU 的有效地址长度为的有效地址长度为1616位，位，则其寻址范围为则其寻址范围为 0 0到到64K64K。上图中的编译和链接主要是语言系统的上图中的编译和链接主要是语言系统的设计问题。不过，由虚拟存储器到物理设计问题。不过，
10、由虚拟存储器到物理存储器的变换是操作系统所必须解决的存储器的变换是操作系统所必须解决的问题。问题。要实现这个变换，必须要有相应的硬件要实现这个变换，必须要有相应的硬件支持，并使这些硬件能够完成统一管理支持，并使这些硬件能够完成统一管理内存和外存之间数据和程序段自动交换内存和外存之间数据和程序段自动交换的虚拟存储器功能。的虚拟存储器功能。即：由于每个进程都拥有自己的虚存，且每即：由于每个进程都拥有自己的虚存，且每个虚存的大小不受实际物理存储器的限制，个虚存的大小不受实际物理存储器的限制，因此，系统不可能提供足够大的内存来存放因此，系统不可能提供足够大的内存来存放所有进程的内容。内存中只能存放那些
11、经常所有进程的内容。内存中只能存放那些经常被访问的程序和数据段等。这就需要有相当被访问的程序和数据段等。这就需要有相当大的外部存储器，以存储那些不经常被访问大的外部存储器，以存储那些不经常被访问或在某一段时间内不会被访问的信息。待到或在某一段时间内不会被访问的信息。待到进程执行过程中需要这些信息时，再从外存进程执行过程中需要这些信息时，再从外存中自动调入主存。中自动调入主存。5.1.2 5.1.2 地址变换地址变换内存地址的集合称为内存空间或物理地址空间。内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的称为内存内存中，每一个存储单元都与相应的称为内存地址的编号相对应。
12、显然，内存空间是一维线地址的编号相对应。显然，内存空间是一维线性空间。性空间。怎样把几个虚存的一维线性空间或多维线性空怎样把几个虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性空间呢？间变换到内存的唯一的一维物理线性空间呢？这涉及到两个问题。一个是虚拟空间的划分这涉及到两个问题。一个是虚拟空间的划分问题。例如进程的正文段和数据段应该放置问题。例如进程的正文段和数据段应该放置在虚拟空间的什么地方。虚拟空间的划分使在虚拟空间的什么地方。虚拟空间的划分使得编译链接程序可以把不同的程序模块（它得编译链接程序可以把不同的程序模块（它们可能是用不同的高级语言编写的），链接们可能是用不同的高级
13、语言编写的），链接到一个统一的虚拟空间中去。到一个统一的虚拟空间中去。虚拟空间的划分与计算机系统结构有关。虚拟空间的划分与计算机系统结构有关。VAX-11VAX-11机的虚拟空间结构图、机的虚拟空间结构图、虚拟空间的划分虚拟空间的划分第二个问题是把虚拟空间中已链接和划分好第二个问题是把虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存的内容装入内存，并将虚拟地址映射为内存地址的问题。称之为地址重定位或地址映射。地址的问题。称之为地址重定位或地址映射。地址映射就是要建立虚拟地址与内存地址的地址映射就是要建立虚拟地址与内存地址的关系。实现地址重定位或地址映射的方法有关系。实现地址重定位
14、或地址映射的方法有两种：两种：静态地址重定位静态地址重定位动态地址重定位。动态地址重定位。1.1.静态地址重定位静态地址重定位静态地址重定位（静态地址重定位（static address static address relocationrelocation）是在虚拟空间程序执行之前由装配是在虚拟空间程序执行之前由装配程序完成地址映射工作。假定分配给程序的内存程序完成地址映射工作。假定分配给程序的内存首地址为首地址为BABA，且程序的虚拟空间地址为，且程序的虚拟空间地址为V V，程序程序的内存地址空间为的内存地址空间为M M，虚地址空间到物理内存地虚地址空间到物理内存地址空间的映射为址空间的映
15、射为f f；则则 f:(V)Mf:(V)M即：即：M=f(V)=BA+V M=f(V)=BA+V 从而完成程序中所有地址部从而完成程序中所有地址部分的修改，以保证分的修改，以保证CPUCPU的正确执行。静态重定位的正确执行。静态重定位的优点是不需要硬件支持。但是，使用静态重定的优点是不需要硬件支持。但是，使用静态重定位方法进行地址变换无法实现虚拟存储器。静态位方法进行地址变换无法实现虚拟存储器。静态重定位的另一个缺点是必须占用连续的内存空间，重定位的另一个缺点是必须占用连续的内存空间，这就难以做到程序和数据的共享。这就难以做到程序和数据的共享。2.2.动态地址重定位动态地址重定位动态地址重定位
16、（动态地址重定位（dynamic address relocationdynamic address relocation）是在程序执行过程中，在是在程序执行过程中，在CPUCPU访问内存之前，将要访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。位依靠硬件地址变换机构完成。地址重定位机构需要一个地址重定位机构需要一个(或多个或多个)基地址寄存器基地址寄存器BRBR和一个和一个(或多个或多个)程序虚拟地址寄存器程序虚拟地址寄存器VRVR。指令或数指令或数据的内存地址据的内存地址MAMA与虚拟地址的关系为与虚拟地
17、址的关系为:MA=(BR)+(VR)MA=(BR)+(VR)这里，这里，(BR)(BR)与与(VR)(VR)分别表示寄存器分别表示寄存器BRBR与与VRVR中的内容。中的内容。动态重定位过程如下图所示。动态重定位过程如下图所示。动态地址重定位图动态地址重定位图其具体过程是其具体过程是:(1)(1)设置基地址寄存器设置基地址寄存器BRBR，虚拟地址寄存器虚拟地址寄存器VRVR。(2)(2)将程序段装入内存，且将其占用的内存区将程序段装入内存，且将其占用的内存区首地址送首地址送BRBR中。本例中中。本例中 (BR)=1000(BR)=1000。(3)(3)在程序执行过程中，将所要访问的虚拟在程序执
18、行过程中，将所要访问的虚拟地址送入地址送入VRVR中，本例中执行中，本例中执行LOAD A 500LOAD A 500语句时语句时 ，将所要访问的虚拟地址，将所要访问的虚拟地址500500放入放入VRVR中。中。(4)(4)地址变换机构把地址变换机构把VRVR和和BRBR的内容相加，得的内容相加，得到实际访问的物理地址。到实际访问的物理地址。动态重定位的主要优点有动态重定位的主要优点有:(1)(1)可以对内存进行非连续分配（程序段、数可以对内存进行非连续分配（程序段、数据段）。据段）。动态重定位提供了实现虚拟存储器的基础。因动态重定位提供了实现虚拟存储器的基础。因为动态重定位不要求在作业执行前
19、为所有程序为动态重定位不要求在作业执行前为所有程序分配内存，也就是说，可以部分地、动态地分分配内存，也就是说，可以部分地、动态地分配内存。配内存。(3)(3)有利于程序段的共享。有利于程序段的共享。5.1.3 5.1.3 内外存数据传输的控制内外存数据传输的控制要实现内存扩充，在程序执行过程中，内存和要实现内存扩充，在程序执行过程中，内存和外存之间必须经常地交换数据。也就是说，把外存之间必须经常地交换数据。也就是说，把那些即将执行的程序和数据段调入内存，而把那些即将执行的程序和数据段调入内存，而把那些处于等待状态的程序和数据段调出内存。那些处于等待状态的程序和数据段调出内存。最基本的控制办法有
20、两种：最基本的控制办法有两种：一种是用户程序自己控制一种是用户程序自己控制另一种是操作系统控制另一种是操作系统控制用户程序自己控制内外存之间的数据交换的例用户程序自己控制内外存之间的数据交换的例子是覆盖。覆盖技术要求用户清楚地了解程序子是覆盖。覆盖技术要求用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序。的结构，并指定各程序段调入内存的先后次序。覆盖是一种早期的主存扩充技术。使用覆盖技覆盖是一种早期的主存扩充技术。使用覆盖技术，用户负担很大，且程序段的最大长度仍受术，用户负担很大，且程序段的最大长度仍受内存容量限制。因此，覆盖技术不能实现虚拟内存容量限制。因此，覆盖技术不能实现虚拟存
21、储器。存储器。操作系统控制方式又可进一步分为两种：操作系统控制方式又可进一步分为两种：一种是交换一种是交换(swapping)(swapping)方式；方式；另一种是请求调入另一种是请求调入(on demand)(on demand)方式和预调入方式和预调入(on(on prefetchprefetch)方式；方式；交换方式由操作系统把那些在内存中处于等待状交换方式由操作系统把那些在内存中处于等待状态的进程换出内存，而把那些等待事件已经发生、态的进程换出内存，而把那些等待事件已经发生、处于就绪态的进程换入内存。处于就绪态的进程换入内存。请求调入方式是在程序执行时，如果所要访问的请求调入方式是在
22、程序执行时，如果所要访问的程序段或数据段不在内存中，则操作系统自动地程序段或数据段不在内存中，则操作系统自动地从外存将有关的程序段和数据段调入内存的一种从外存将有关的程序段和数据段调入内存的一种操作系统控制方式。而预调入则是由操作系统预操作系统控制方式。而预调入则是由操作系统预测在不远的将来会访问到的那些程序段和数据段测在不远的将来会访问到的那些程序段和数据段部分，并在它们被访问之前系统选择适当的时机部分，并在它们被访问之前系统选择适当的时机将它们调入内存的一种数据流控制方式。将它们调入内存的一种数据流控制方式。由于交换方式一般不进行部分交换，即每次交由于交换方式一般不进行部分交换，即每次交换
23、都交换那些除去常驻内存部分后的整个进程，换都交换那些除去常驻内存部分后的整个进程，而且，即使能完成部分交换，也不是按照执行而且，即使能完成部分交换，也不是按照执行的需要而交换程序段，只是把受资源限制、暂的需要而交换程序段，只是把受资源限制、暂时不能执行的程序段换出内存。因此，虽然交时不能执行的程序段换出内存。因此，虽然交换方式也能完成内存扩充任务，但它仍未实现换方式也能完成内存扩充任务，但它仍未实现那种所谓自动覆盖、内存和外存统一管理、进那种所谓自动覆盖、内存和外存统一管理、进程大小不受内存容量限制的虚拟存储器。只有程大小不受内存容量限制的虚拟存储器。只有请求调入方式和预调入方式可以实现进程大
24、小请求调入方式和预调入方式可以实现进程大小不受内存容量限制的虚拟存储器。不受内存容量限制的虚拟存储器。5.1.4 5.1.4 内存的分配与回收内存的分配与回收内存的分配与回收是内存管理的主要功能之一。内存的分配与回收是内存管理的主要功能之一。无论采用哪一种管理和控制方式，能否把外存无论采用哪一种管理和控制方式，能否把外存中的数据和程序调入内存，取决于能否在内存中的数据和程序调入内存，取决于能否在内存中为它们安排合适的位置。因此，存储管理模中为它们安排合适的位置。因此，存储管理模块要为每一个并发执行的进程分配内存空间。块要为每一个并发执行的进程分配内存空间。另外，当进程执行结束之后，存储管理模块
25、又另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给要及时回收该进程所占用的内存资源，以便给其他进程分配空间。其他进程分配空间。为了有效合理地利用内存，设计内存的分配和为了有效合理地利用内存，设计内存的分配和回收方法时，必须考虑和确定以下几种策略和回收方法时，必须考虑和确定以下几种策略和数据结构数据结构:(1)(1)分配结构：登记内存使用情况，供分配程分配结构：登记内存使用情况，供分配程序使用的表格与链表。例如内存空闲区表、空序使用的表格与链表。例如内存空闲区表、空闲区队列等。闲区队列等。(2)(2)放置策略：确定调入内存的程序和数据放置策略：确定调入内存的程序和
26、数据在内存中的位置。这是一种选择内存空闲区的在内存中的位置。这是一种选择内存空闲区的策略。策略。(3)(3)交换策略：在需要将某个程序段和数据交换策略：在需要将某个程序段和数据调入内存时，如果内存中没有足够的空闲区，调入内存时，如果内存中没有足够的空闲区，由交换策略来确定把内存中的哪些程序段和数由交换策略来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。据段调出内存，以便腾出足够的空间。(4)(4)调入策略：外存中的程序段和数据段什调入策略：外存中的程序段和数据段什么时间按什么样的控制方式进入内存。调入策么时间按什么样的控制方式进入内存。调入策略与略与5.1.35.1.3节中所述
27、内外存数据流动控制方式节中所述内外存数据流动控制方式有关。有关。(5)(5)回收策略：回收策略包括二点，一是回回收策略：回收策略包括二点，一是回收的时机，二是对所回收的内存空闲区和已存收的时机，二是对所回收的内存空闲区和已存在的内存空闲区的调整。在的内存空闲区的调整。5.1.5 5.1.5 内存信息的共享与保护内存信息的共享与保护内存信息的共享与保护也是内存管理的重要功内存信息的共享与保护也是内存管理的重要功能之一。能之一。在多道程序设计环境下，内存中的许在多道程序设计环境下，内存中的许多用户或系统程序和数据段可供不同的用户进多用户或系统程序和数据段可供不同的用户进程共享。这种资源共享将会提高
28、内存的利用率。程共享。这种资源共享将会提高内存的利用率。但是，反过来说，除了被允许共享的部分之外，但是，反过来说，除了被允许共享的部分之外，又要限制各进程只在自己的存储区活动，各进又要限制各进程只在自己的存储区活动，各进程不能对别的进程的程序和数据段产生干扰和程不能对别的进程的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段采取保破坏，因此须对内存中的程序和数据段采取保护措施。护措施。常用的内存信息保护方法有硬件法、软件法和常用的内存信息保护方法有硬件法、软件法和软硬件结合三种。软硬件结合三种。上下界保护法是一种常用的硬件保护法。上下上下界保护法是一种常用的硬件保护法。上下界存储保护技
29、术要求为每个进程设置一对上下界存储保护技术要求为每个进程设置一对上下界寄存器。上下界寄存器中装有被保护程序和界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过数据段的起始地址和终止地址。在程序执行过程中程中,在对内存进行访问操作时首先进行访址在对内存进行访问操作时首先进行访址合法性检查合法性检查,即检查经过重定位后的内存地址即检查经过重定位后的内存地址是否在上、下界寄存器所规定的范围之内。若是否在上、下界寄存器所规定的范围之内。若在规定的范围之内，则访问是合法的；否则是在规定的范围之内，则访问是合法的；否则是非法的，并产生访址越界中断。上下界保护法非法的，并产生访
30、址越界中断。上下界保护法的保护原理如图所示。的保护原理如图所示。上、下界寄存器保护法图上、下界寄存器保护法图另外，保护键法也是一种常用的存储保护法。另外，保护键法也是一种常用的存储保护法。保护键法为每一个被保护存储块分配一个单独保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护的保护键。在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配。保护码和与被保护的存储块中的保护键匹配。保护键可设置成对读写同时保护的或只对读，写进键可设置成对读写同时保护的或只对读，写进行单项保护的
31、。例保护键保护法示例图中的保行单项保护的。例保护键保护法示例图中的保护键护键0 0，就是对，就是对2K2K到到4K4K的存储区进行读写同时保的存储区进行读写同时保护的，而保护键护的，而保护键2 2则只对则只对4K4K到到6K6K的存储区进行写的存储区进行写保护。如果开关字与保护键匹配或存储块未受保护。如果开关字与保护键匹配或存储块未受到保护，则访问该存储块是允许的，否则将产到保护，则访问该存储块是允许的，否则将产生访问出错中断。生访问出错中断。保护键保护法示例图保护键保护法示例图另外一种常用的内存保护方式是：界限寄存器另外一种常用的内存保护方式是：界限寄存器与与CPUCPU的用户态或核心态工作
32、方式相结合的保的用户态或核心态工作方式相结合的保护方式。在这种保护模式下，用户态进程只能护方式。在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空分，而核心态进程则可以访问整个内存地址空间。间。UNIXUNIX系统就是采用的这种内存保护方式。系统就是采用的这种内存保护方式。返回返回5.2 5.2 分区存储管理分区存储管理分区管理是把内存划分成若干个大小不分区管理是把内存划分成若干个大小不等的区域，除操作系统占用一个区域之等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共外，其
33、余由多道环境下的各并发进程共享。分区管理是满足多道程序设计的一享。分区管理是满足多道程序设计的一种最简单的存储管理方法。种最简单的存储管理方法。下面结合分区原理来讨论分区存储管理下面结合分区原理来讨论分区存储管理时的虚存实现、地址变换、内存的分配时的虚存实现、地址变换、内存的分配与释放以及内存信息的共享与保护等问与释放以及内存信息的共享与保护等问题。题。5.2.1 5.2.1 分区管理基本原理分区管理基本原理分区管理的基本原理是给每一个内存中的进程分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区划分一块适当大小的存储区,以连续存储各进以连续存储各进程的程序和数据，使各进程得以并
34、发执行。按程的程序和数据，使各进程得以并发执行。按分区的时机，分区管理可以分为两种方法：分区的时机，分区管理可以分为两种方法：固定分区固定分区动态分区动态分区1.1.固定分区法固定分区法把内存区固定地划分为若干个大小不等的区域。把内存区固定地划分为若干个大小不等的区域。划分的原则由系统操作员或操作系统决定。分划分的原则由系统操作员或操作系统决定。分区一旦划分结束，在整个执行过程中每个分区区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。的长度和内存的总分区个数将保持不变。系统对内存的管理和控制通过数据结构系统对内存的管理和控制通过数据结构分分区说明表进行，分区说明表说
35、明各分区号、分区说明表进行，分区说明表说明各分区号、分区大小、起始地址和是否是空闲区区大小、起始地址和是否是空闲区(分区状态分区状态)。内存的分配释放、存储保护以及地址变换等都内存的分配释放、存储保护以及地址变换等都通过分区说明表进行。通过分区说明表进行。固定分区法示意图固定分区法示意图例图给出了固定分区时分区说明表和对应内存状态。例图给出了固定分区时分区说明表和对应内存状态。图中，操作系统占用低地址部分的图中，操作系统占用低地址部分的20K20K，其余空间，其余空间被划分为被划分为4 4个分区，其中个分区，其中1,2,31,2,3号分区已分配，号分区已分配，4 4号号分区未分配。分区未分配。
36、2.2.动态分区法动态分区法动态分区法在作业执行前并不建立分区，分区的动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率的浪费现象，从而提高了内存的利用率采用动态分区法，在系统初启时，除了操作系统采用动态分区法，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。随后，中常驻内存部分之外，只有一个空闲分区。随
37、后，分配程序将该区依次划分给调度选中的作业或进分配程序将该区依次划分给调度选中的作业或进程。图示给出了程。图示给出了FIFOFIFO调度方式时的内存初始分配调度方式时的内存初始分配情况。情况。内存初始分配情况图内存初始分配情况图随着进程的执行，会出现一系列的分配和释放。随着进程的执行，会出现一系列的分配和释放。如在某一时刻，进程如在某一时刻，进程C C执行结束并释放内存之后，执行结束并释放内存之后，管理程序又要为另两个进程管理程序又要为另两个进程E E（设需内存设需内存50K50K）和和F F（设需内存设需内存16K16K）分配内存。如果分配的空分配内存。如果分配的空闲区比所要求的大，则管理程
38、序将该空闲区分闲区比所要求的大，则管理程序将该空闲区分成两个部分，其中一部分成为已分配区而另一成两个部分，其中一部分成为已分配区而另一部分成为一个新的小空闲区。下图给出了采用部分成为一个新的小空闲区。下图给出了采用最先适应算法最先适应算法(first fit)(first fit)分配内存时进程分配内存时进程E E和和进程进程F F得到内存以及进程得到内存以及进程B B和进程和进程D D释放内存的内释放内存的内存分配变化过程。如图所示，在管理程序回收存分配变化过程。如图所示，在管理程序回收内存时，如果被回收分区有和它邻接的空闲分内存时，如果被回收分区有和它邻接的空闲分区存在，则要进行合并。区存
39、在，则要进行合并。内存分配变化过程图内存分配变化过程图与固定分区法时相同，动态分区法也要使用分与固定分区法时相同，动态分区法也要使用分区说明表等数据结构对内存进行管理。除了分区说明表等数据结构对内存进行管理。除了分区说明表之外，动态分区法还把内存中的可用区说明表之外，动态分区法还把内存中的可用分区单独构成可用分区表或可用分区自由链，分区单独构成可用分区表或可用分区自由链，以描述系统内的内存资源。与此相对应以描述系统内的内存资源。与此相对应,请求内请求内存资源的作业或进程也构成一个内存资源请求存资源的作业或进程也构成一个内存资源请求表。示图给出了可用表，自由链和请求表的例表。示图给出了可用表，自
40、由链和请求表的例子。子。可用表的每个表目记录一个空闲区，主要参数可用表的每个表目记录一个空闲区，主要参数包括区号、长度和起始地址。采用表格结构，包括区号、长度和起始地址。采用表格结构，管理过程比较简单，但表的大小难以确定，可管理过程比较简单，但表的大小难以确定，可用表要占用一部分内存。用表要占用一部分内存。可用表、自由链及请求表图可用表、自由链及请求表图自由链则是利用每个内存空闲区的头几个单元自由链则是利用每个内存空闲区的头几个单元存放本空闲区的大小及下个空闲区的起始地址，存放本空闲区的大小及下个空闲区的起始地址，从而把所有的空闲区链接起来。然后，系统再从而把所有的空闲区链接起来。然后，系统再
41、设置一自由链首指针让其指向第一个空闲区，设置一自由链首指针让其指向第一个空闲区，这样，管理程序可通过链首指针查到所有的空这样，管理程序可通过链首指针查到所有的空闲区。采用自由链法管理空闲区，查找时要比闲区。采用自由链法管理空闲区，查找时要比可用表困难，但由于自由链指针是利用的空闲可用表困难，但由于自由链指针是利用的空闲区自身的单元，所以不必占用额外的内存区。区自身的单元，所以不必占用额外的内存区。请求表的每个表目描述请求内存资源的请求表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。作业或进程号以及所请求的内存大小。无论是采用可用表方式还是自由链方式，无论是采用可用表方式还是自由
42、链方式，可用表或自由链中的各个项都要按照一可用表或自由链中的各个项都要按照一定的规则排列以利查找和回收。下面讨定的规则排列以利查找和回收。下面讨论分区法的分区分配与回收问题。论分区法的分区分配与回收问题。5.2.2 5.2.2 分区的分配与回收分区的分配与回收1.1.固定分区时的分配与回收固定分区时的分配与回收固定分区法时的内存分配与回收较为简单，当固定分区法时的内存分配与回收较为简单，当用户程序要装入执行时，通过请求表提出内存用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一程序根据
43、请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。个满足要求的空闲分区，并将其分配给申请者。固定分区时的分配算法如下图。固定分区时的分配算法如下图。固定分区的回收更加简单。当进程执行完毕，固定分区的回收更加简单。当进程执行完毕，不再需要内存资源时，管理程序将对应的分区不再需要内存资源时，管理程序将对应的分区状态置为未使用即可。状态置为未使用即可。固定分区分配算法图固定分区分配算法图2.2.动态分区时的分配与回收动态分区时的分配与回收动态分区时的分配与回收主要解决三个问题动态分区时的分配与回收主要解决三个问题:(1)(1)对于请求表中的要求内存长度，从可用对于请求表中的要
44、求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。表或自由链中寻找出合适的空闲区分配程序。(2)(2)分配空闲区之后，更新可用表或自由链。分配空闲区之后，更新可用表或自由链。(3)(3)进程或作业释放内存资源时，和相邻的进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。空闲区进行链接合并，更新可用表或自由链。动态分区时的分配方法从可用表或自由链中动态分区时的分配方法从可用表或自由链中寻找空闲区的常用方法有三种。它们是：寻找空闲区的常用方法有三种。它们是：最先适应法最先适应法(first fit algorithm)(first fit algorithm)；最佳
45、适应法最佳适应法(best fit algorithm)(best fit algorithm)；最坏适应法最坏适应法(worst fit(worst fit algoriathmalgoriathm)。这三种方法要求可用表或自由链按不同的这三种方法要求可用表或自由链按不同的方式排列。方式排列。(1)(1)最先适应法最先适应法最先适应法要求可用表或自由链按起始地址递最先适应法要求可用表或自由链按起始地址递增的次序排列。该算法的最大特点是一旦找到增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存长度的分区，则结束探大于或等于所要求内存长度的分区，则结束探索。然后，该算法从所找到的分区中
46、划出所要索。然后，该算法从所找到的分区中划出所要求的内存长度分配给用户，并把余下的部分进求的内存长度分配给用户，并把余下的部分进行合并行合并(如果有相邻空闲区存在如果有相邻空闲区存在)后留在可用表后留在可用表中，但要修改其相应的表项。中，但要修改其相应的表项。(2)(2)最佳适应算法最佳适应算法最佳适应算法要求从小到大的次序组成空闲最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。当用户作业或进程申请区可用表或自由链。当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停找，当找到第一个满足要求的空闲区时，停
47、止查找。如果该空闲区大于请求表中的请求止查找。如果该空闲区大于请求表中的请求长度，则与最先适应法时相同，将减去请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中。长度后的剩余空闲区部分留在可用表中。(3)(3)最坏适应算法最坏适应算法最坏适应算法要求空闲区按其大小递减的顺序最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。当用户作业或进组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，先检查空闲区可用表或程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲可用区的大小是否大于或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度
48、，若可用表或自由链的等于所要求的内存长度，若可用表或自由链的第一个项长度小于所要求的，则分配失败，否第一个项长度小于所要求的，则分配失败，否则从空闲区可用表或自由链中分配相应的存储则从空闲区可用表或自由链中分配相应的存储空间给用户，然后修改和调整空闲区可用表或空间给用户，然后修改和调整空闲区可用表或自由链。自由链。3.3.动态分区时的回收与拼接动态分区时的回收与拼接当用户作业或进程执行结束时，存储管理程序当用户作业或进程执行结束时，存储管理程序要收回已使用完毕的空闲区，并将其插入空闲要收回已使用完毕的空闲区，并将其插入空闲区可用表或自由链。这里，在将回收的空闲区区可用表或自由链。这里，在将回收
49、的空闲区插入可用表或自由链时插入可用表或自由链时,和分配空闲区时一样，和分配空闲区时一样，也要碰到剩余空闲区拼接问题。也要碰到剩余空闲区拼接问题。解决这个问题解决这个问题的办法之一就是在空闲区回收时或在内存分配的办法之一就是在空闲区回收时或在内存分配时进行空闲区拼接，以把不连续的零散空闲区时进行空闲区拼接，以把不连续的零散空闲区集中起来。集中起来。空闲区的合并图空闲区的合并图在将一个新可用区插入可用表或队列时在将一个新可用区插入可用表或队列时,该空闲区该空闲区和上下相邻区的关系是下述和上下相邻区的关系是下述4 4种关系之一种关系之一:a):a)该空该空闲区的上下两相邻分区都是空闲区；闲区的上下
50、两相邻分区都是空闲区；b)b)该空闲区的该空闲区的上相邻区是空闲区；上相邻区是空闲区；c)c)该空闲区的下相邻区是空该空闲区的下相邻区是空闲区；闲区；d)d)两相邻区都不是空闲区。如下图所示。两相邻区都不是空闲区。如下图所示。对上述对上述4 4种情况，如果释放区与上下两空闲区相种情况，如果释放区与上下两空闲区相邻，则将三个空闲区合并为一个空闲区。新空邻，则将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起始地址，大小闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲区合并后，取消可用为三个空闲区之和。空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修表或自由