7.2.1 概述
◆分区式存储管理是满足多道程序设计的最简单的存储管理方法；
◆在分区式存储管理方式下允许多个用户共享主存空间；
◆基本原理：给每一个内存中的进程划分一块适当大小的存储区，以连续存放各进程的程序和数据，使各进程得以并发执行；
◆适用环境：多道程序环境下的小型、微型机上的多道系统；
◆ 分区式存储管理可以划分为固定分区和动态分区两种方法。
一、固定分区法
存储器在作业处理之前已被划分为若干大小不等的分区，分区一旦划分结束，在整个执行过程中分区的长度及内存分区的总个数不变。
二、动态分区法
在作业的处理过程中，根据作业或进程对内存的需要而动态的建立分区。
下面以图7.5所示的例子说明动态分区的分配情况。设某系统拥有256主存，操作系统占用顶端20KB主存区。当有一个作业队列请求进入系统时，动态分区存储管理方案中的初始分区分配如图7.5所示。
作业队列：作业132KB；
作业214KB；
作业364KB；
作业4100KB；
作业550KB；作业550KB；
图7.5 动态分存储管理方案中的初始分区分配
但是，每种存储组织方案都包含一定程序的浪费。在动态分区方案中，主存中的作业在开始充入时，只有主存最后一部分可能小于任一作业的需要而空闲，但当系统运行一段时间后，作业陆续完成时，它们要释放主存区域，在主存中形成一些空闲区，如图7.6中的斜线部分所示。这些区可以被其他作业使用，但由于空闲区和容纳的作业的大小不一定正好相等，因而这样剩余的空闲区域变得更小。当系统运行相当长一段时间后，主存中会出现一些更小的空闲区。
为此，可从以下几个方面来讨论分区存储管理技术：
①在分区存储管理方案中，如何实现地址映射。
②动态分区的分配机构。
③分区的分配和回收。
④三种最基本的放置策略。
图7.6 动态分区方法中存储区的释放
7.2.2 用在址寄存器实现动态地址映射
分区式存储管理方式下的地址映射采用动态地址重定位；
动态重定位装置：基址寄存器；
原理：相应程序运行时，CPU每次产生的逻辑地址都要加上基址寄存器的内容作为访问实际内存的物理地址；
7.2.3 分区分配机构
（一）主存资源信息块
在动态分区方法中，描述主存资源的数据结构是主存资源信息m-rib，其结构如图7.7所示。
m-rib |
|
pd |
等待队列指针 |
|
分配标志 |
falg |
自由主存队列指针 |
|
大小 |
size |
主存分配程序入口地址 |
|
勾链字 |
next |
图7.7 主存资源信息块 图7.8 分区描述器
（二）分区描述器和自由主存队列
对于主存中的每一个分区都有相应的分区描述器说明分区的特征信息。分区描述器（pd）的结构如图7.8所示。
该结构图中各项内容与分区类型（在主存中有两类不同的分区，一类为已分配区，一类为自由分区）有关，其具体解释如下：
flag：对自帽分区而言为零，对已分配区而言为非零数值；
size：分区可用字数（设为n）与分区描述器所需字数（设为3）之和，即为n+3；
next：对自由分区而方，为自由主存队列中的勾链字，指向队列中下一个自由分区，对已分配区而言，此项为零。
配区而言，此项为零。
在主存分配中，主要讨论自由分描述器和自由主存队列。以下例说明这两个结构。设某系统在时刻t时的主存分布如图7.9(a)所示。图7.9(b)画出了自由分区描述器的内容和自由主存队列。
(a)主存分布 (b)自由主存队列
图7.9 动态分区的自由主存队列
7.2.4 分区的分配与回收
（1）分配一个主存块
操作过程：在自由主存队列中找出一个满足空间大小的可用空闲分区；
对可用空闲区进行划分：已分配区、新空闲区、门限值问题；
修改空闲分区描述器；
建立已分配区描述器；
其实现过程的算法描述见MODULE7.1。
MODULE7.1 分配一个主存块
算法getmb |
输入：请求主存大小size |
输出：分配块的首址baddr |
{ |
size加上分区描述器的大小得xize1； |
for（自由主存队列中的每一个空闲块） |
{ |
if（当前块大小≥size1） |
break; /*已找到*/ |
} |
if（自由队列已空） |
return(0); |
当前块大小减去size得剩余块大小； |
if（剩余块<门限值） |
{ |
当前块作为已分配区，并从自由主存队列中摘除； |
flag=1; /*建立已分配区描述器*/ |
Next=NULL; |
} |
else |
{ |
修改剩余块大小： /*该块仍留在自由主存队列上*/ |
当前块首址加剩余块大小得分配块首址； |
flag=1; /*建立已分配区描述器*/ |
size=aize1; |
next=NULL; |
} |
分配块首址加上描述器大小得baddr； |
return(baddr); |
} |
（二）回收一个主存块
将首地址为baddr的主存块还给主存资源信息块；
◆分区回收的四种情况：
回收分区r上邻一个空闲区；
回收分区r下邻一个空闲区；
回收分区r上、下均邻空闲区；
回收分区r上、下均不邻空闲区；
注意合并后的空闲区的起始地址及大小；
◆计算出自由块首地址，判断是否上下邻空闲区，若有则合并；
将自由块插入到自由主存队列。
如图7.10所示。第一种情况是回收分区r上邻一个空闲区，此时应合并成为一个连续的空闲区，其始址为r上邻的空闲区始址，而大小为二者之和；第二种情况是回收分区r与下面的空闲区邻，合并后仍为空闲区，但该空闲区始址为回收分区r的地址，其大小为二者之和；第三种情况为r与上、下空闲区邻接，这时应将这三个区域合并为一个连续的空闲区，其始址为r上邻的空闲区始地址，大小为三者之和，并且应把与r下邻的空闲区从自由主存队列中摘除；第四种情况为r不与任何空闲区相邻接，这时应建立一个新的空闲区，并加入到自由主存队列中去。
|
|
|
|
|
|
|
f1 |
|
作业2 |
|
f1 |
|
作业1 |
r |
|
r |
|
r |
|
r |
作业1 |
|
f2 |
|
f2 |
|
作业2 |
|
|
|
|
|
|
|
(a)回收分区r上邻空闲区 |
|
(b)回收分区r下邻空闲区 |
|
(c)回收分区r上、下邻空闲区 |
|
(c)回收分区r上、下邻已分配区 |
|
|
|
2．分区回收的实现
回收分区的实现过程的程序描述见MOEULE7.2。该程序的功能是先计算释放分区f的首址，然后判断这一释放块是否邻接空闲区；若有上邻或下邻空闲区，则应合并成一个新的自由区，并将它插入到处由主存队列合适的位置上。
MOEULE7.2
算法relmb |
输入：释放分区首址baddr |
输出：无 |
{ |
释放分区首址减3得自由块f首址； |
计算自由块f的末址：首址加大小； |
For（自由主存队列中每一块） |
{ |
If(f与当前块f1是上邻) |
{ |
合并为一个自由块f； |
f1撤消； |
break; |
} |
} |
For（自由队列中的每一块） |
{ |
if（f与当前块f2是下邻） |
{ |
合并为一个自由块f； |
f1撤消； |
break; |
} |
} |
f入自由主存队列； |
} |
7.2.5 几种基本的放置策略
自由主存队列的排序原则就体现了选择一个空闲区的策略。
这个队列可以是无序的，即按照主存块释放的先后次序排列，但也可以是按某种分类方法进行排序的。
下面是两种常用的分类方法：
（一）首次适应算法
按空闲区起始地址递增的次序组织自由主存队列；
用这种算法实施分配时，找到的第一个适应要求的空闲区，其大小不一定正好等于所要求的大小。这时，需要把该空闲区分为两个区，一为已分配区，其大小刚好等于所要求的大小；另一个仍为空闲区，并留在原严寒的连接位置上。
当系统回收一个分区是时，首先检查是否有邻接的空闲区。如有，则合并。合并后所得的空闲区仍保持在队列中原来的位置上。如回收的分区不和空闲区邻接，则应根据其起始地址大小，把它插到队列中相应的位置上。一般地，只要查找半个表就可找到解答。
优点：简单，速度快，尽量利用低地址部分的空闲块，以便在高地址部分形成大的空闲区。
（二）最佳适应算法
按空闲区大小由小到大组织自由主存队列；
优点：如果有一个作业申请空间的大小正好与某空闲块相等，则该空闲块必被选中，命中率最佳。
缺点：大量碎片出现；时间花销大，要先排序在组织队列。
（三）最坏适应算法
按空闲区大小由大到小组织自由主存队列；
优点：每次切开较大的分区，剩余部分还能再次被分配。
缺点：时间开销大，剩余部分仍需排序后插入到队列中。
首次适应、最佳适应、最坏适应算法的说明见图7.11。在图7.11(a)中，作业放入适合于它的第一个空闲区中，图(b)则将作业放入适合它的、尽可能最小的空闲区中，在图(c)中，作业被放置到适合于它的、尽可能最大的空闲区中。 
主存 主存 主存
(a)首次适应算法 (b)最佳适应算法 (c)最坏适应算法
图7.11 三种放置策略的说明
这三种算法到底哪一种好，不能一概而论，而应针对具体的作业序列来分析。对于某一作序列来说，若某种算法能将该作业序列中的所有作业安置完毕，那我们就说该算法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求（即在某个被分配的分区回收之前无法进行分配），而其他算法却可以满足此要求，则这一算法对该作业序列是不合适的。
设在图7.11所示的系统中（主存容量为256KB），有这样一个作业序列：作业A要求18KB；作业B要求25KB；作业C要求30KB。用首次适应算法、最佳适应算法、最坏适应算法来处理该作业序列，看哪种算法合适（为简单起见，假定作业要求的主存容量中包含了分区描述器所需占用的空间）。
为了讨论这一问题，画出了在这三种算法下的自由主存队列。如图7.12所示。根据动态分区分配算法可以分析出：最佳适应算法对该和业是合适的，其余两种算法对该和业是不合适的。读者可以验证上述结论是否正确。
 free (a)首次适应算法中的自由主存队列
 (b)最佳适应算法中的自由主存队列
(c)最坏适应算法中的自由主存队列
图7.12 不同放置策略下的自由主存队列
7.2.6 碎片问题及拼接技术
碎片：在已分配区之间存在着的一些没有被充分利用的空闲区。
。
拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区，如图7.13所示。
图7.13 分区分配中的存储区拼接
拼接时机：
①在某个分区回收时立即拼接；
②找不到足够大的空白分区时实施拼接
拼接技术的缺点是：
①消耗系统资源，为移动已分配区信息要花费大量的CPU时间。
②当系统进行拼接时，它必须停止所有其他的工作。对交互作用的用户，可能导致响应时间不规律；对实时系统的紧迫任务而言，由于不能及时响应，可能造成严重后果。
③拼接需要重新定义已存入主存的作业。由于拼接要消耗大量的系统资源，且有时为拼接所花费的系统开销要大于拼接技术的效益，因而这种方法的使用受到限制。
小结：分区式存储管理的主要优缺点
优点：①实现了多个作业或进程对内存的共享；
②硬件支持少，管理算法简单，容易实现；
缺点：①内存利用率不高；
②作业或进程大小受分区大小限制，未能实现真正意义上的虚存；
③难以实现各分区间的信息共享。
|
