操作系统——分区存储管理

操作系统——分区存储管理

分区存储管理是把主存储器中的⽤户区作为⼀个连续区或分成若⼲个连续区进⾏管理，每个连续区中可装⼊⼀个作业。

多道程序系统⼀般都采⽤多个分区的存储管理，具体可分为固定分区和可变分区两种⽅式。

⼀、固定分区存储管理

把主存中可分配的⽤户区域预先划分成若⼲个连续的分区，每个连续区的⼤⼩可以相同，也可以不同。但是，⼀旦划分好分区之后，主存中

分区的个数就固定了，且每个分区的⼤⼩也固定不变。这是⼀种静态分区法。

在固定分区⽅式管理下，每个分区⽤来装⼊⼀个作业。由于主存中有多个分区，就可同时在每个分区中装⼊⼀个作业。所以，这种存储管理

⽅式适⽤于多道程序系统。

1、主存空间的分配与释放

为了管理主存空间的使⽤，必须设置⼀张“主存分配表”（分区说明表），以说明各分区的分配情况。主存分配表中应指出各分区的起始地址

和长度，并为每个分区设⼀个标志位。当标志位为“0”时，表⽰对应的分区是空闲分区，当标志位为⾮“0”时，表⽰对应的分区已被某作业占

⽤。空闲分区可以⽤来装作业。

当作业队列中有作业要装⼊主存时，存储管理可采⽤“顺序分配算法”进⾏主存空间的分配。

顺序查看主存分配表，找到⼀个标志为“0”的并且长度⼤于或等于欲装⼊作业的地址空间长度的分区，则把此分区分配给该作业，相应表⽬的

标志位改成作业名的标识；若找不到⼀个这样的空闲分区，则该作业暂时不能装⼊主存。

主存空间的释放很简单。某作业执⾏结束后必须归还所占的分区，这时存储管理根据作业名查看主存分配表，找到相应的表⽬后，把其中的

标志位重新置成“0”即可。

2、地址转换

固定分区管理⽅式下作业的地址转换常采⽤静态重定位技术。

3、存储保护

固定分区管理⽅式下只考虑判断其物理地址即可。常采⽤“界限寄存器对”法。If 下限地址<=物理地址<=上限地址

Then 继续

Else 产⽣“越界中断” ，转越界中断的处理⼦程序

4．内存扩充

采⽤覆盖技术

5．固定分区的优缺点

优点：实现简单，⽆外部碎⽚

缺点：

a.当⽤户程序太⼤时，可能所有的分区都不能满⾜需求，此时不得不采⽤覆盖技术解决，但这⼜会降低性能

b.会产⽣内部碎⽚，碎⽚⼤，存在⼩分区占⽤⼤作业的情况，内存利⽤率低。

解决办法：采⽤可变分区存储管理

⼆、可变分区存储管理

内存管理的可变分区模式，⼜称变长分区模式、动态分区分配模式。这种分配⽅式不会预先划分内存分区，⽽是在进程装⼊内存时，根据进

程的⼤⼩动态地建⽴分区，并使分区的⼤⼩正好适合进程的需要。因此系统分区的⼤⼩和数⽬是可变的。

与固定分区的区别就是：动态的划分分区。

克服固定分区管理的“内碎⽚”问题。

1.可变分区模式下，刚开始，OS就绪，但任何⽤户程序未进⼊内存前整个⽤户内存区是⼀⼤空间。已占⽤区和空闲分区并不是绝对的。

2.必须有表来记录分区的情况。

3.程序进⼊内存时的例⾏⼯作就是分配空闲区和装⼊程序，并修改相应的空闲表和已分配区表。4.⼀旦⼀个内存分区被分配给⼀个进程，该进程可以被装⼊该块中执⾏，装⼊时需重定位。

可变分区分配的数据结构

系统要使⽤什么样的数据结构来记录内存的使⽤情况？

可变分区分配算法

把⼀个新作业装⼊内存时，需要按照⼀定的可变分区分配算法，从空闲分区表（或空闲分区链）中选出⼀个分区分配给该作业。

在可变分区分配⽅式中，当有很多空闲分区都满⾜需求时，应该使⽤哪个分区进⾏分配?

这⾥介绍三种可变分区分配算法

最先适应分配算法

算法思想：每次都从低地址开始查找，找到第⼀个能满⾜⼤⼩的空闲分区。

实现步骤：

空闲区地址由低到⾼排序=>1.顺序查找各个空闲区，把第⼀个找到能容纳申请要求的内存区分配给申请者.（若空闲区⽐作业长度⼤，则分割该空闲区。⼀部分分配给

作业⼀部分空闲。）=>2.调整相应的空闲分区表和已分配分区表。

评价：性能⼀般但实现⽐较简单直接，易于释放时合并相邻空间分区。⽐较容易的满⾜⼤作业的需要。完成⼀次分配平均需要的搜索次数较

⼤，影响了⼯作效率。

尽可能地利⽤存储器中低地址的空闲区，⽽尽量保存⾼地址的空闲区。

最佳适应算法

算法思想：由于可变分区分配是⼀种连续分配⽅式，为各进程分配的空间必须是连续的⼀整⽚区域。因此为了保证当“⼤进程”到来时能有连

续的⼤⽚空间，优先使⽤更⼩的空闲区。

实现步骤：

空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区表，找到⼤⼩能够满⾜要求的第⼀个空闲分区。

评价：尽可能地保留了较⼤的空间。 产⽣⼤量的不能被使⽤的很⼩的空闲区。因此这种⽅法会产⽣很多的外部碎⽚。所以该算法分配效果不

⼀定是最佳的。

尽可能地利⽤存储器中⼩的空闲区，⽽尽量保存⼤的空闲区。

最坏适应算法

算法思想：为了解决最佳适应算法的问题——即留下太多难以利⽤的⼩碎⽚，可以在每次分配时，优先使⽤最⼤的连续空闲区，这样分配后

的空闲区就不会太⼩，更⽅便使⽤。

实现步骤：

空闲分区按照容量递减次序链接。每次分配内存时顺序查找空闲分区表，找到⼤⼩能满⾜要求的第⼀个空闲分区。

评价：分割后产⽣的空闲区⼀般仍可以供以后分配使⽤。⼯作⼀段时间后，不能满⾜⼤作业对空闲区的请求。

尽可能地利⽤存储器中⼤的空闲区。

三种算法的⽐较：

可变分区内存回收

只⽐固定分区管理增加了合并相邻空闲区的操作。

主要是为了及时减少“外碎⽚”，利于今后⼤作业的到来。

实现回收内存空间，关键是修改空闲分区表和已分配分区表。

回收内存分区时可能会遇到的四种情况：

(a)若释放区R既有上邻空闲区，⼜有下邻空闲区。将三个空闲区合并成⼀个⼤空闲区。

先将R与F2合并记为F2,

再将F2与F1合并记为F1,并将F2从链中删除。

IF (B+H1=C) AND (C+L2=D)

THEN 修改空闲表，分配表。

(b)若释放区R只有上邻空闲区F1。

则只修改空闲区F1⼤⼩即可。

IF (D+H2=E)

THEN 修改空闲表，分配表。

(c)只有下邻空闲区

修改空闲区F2的⾸地址。F2的⼤⼩＝F2的⼤⼩＋R的⼤⼩

(d)既⽆上邻⼜⽆下邻空闲区

Else 修改释放区的⾸地址为空闲区的起始地址

地址转换

动态重定位

分区的存储保护

If 下限地址<=物理地址<=上限地址

Then 继续

Else 产⽣“越界中断” ，转越界中断的处理⼦程序

内存扩充

消除了固定分区管理造成的“内碎⽚”，但是不可避免的在内存空间造成“外碎⽚”。

采⽤移动（紧缩）技术。定时的或在内存紧张时，将内存中所有作业移到内存的⼀端，使其相邻。

经过紧缩后的进程在内存中的位置发⽣了变化，若不对程序和数据的地址进⾏修改，在进程就⽆法运⾏。

要使其运⾏，必须进⾏“动态重定位”

注意：

＝》紧缩的时机： （1）⼀旦有归还的分区便进⾏紧缩，系统开销⼤。

（2）分配算法发现各空闲区不够⽤，但其和够⽤时。此法紧缩开销⼩，更实⽤。因此，实际的可变分区分配算法⽐固定分区分配算法主

要增加了“紧缩”操作

三、 伙伴系统（buddy system）

伙伴系统可看作固定分区分配和可变分区分配的⼀种折中⽅案。 采⽤伙伴系统时，内存是以2的幂次个字节⼤⼩的空闲块为分配单位的。系统初启时，只有1个最⼤的2的幂次的空闲块，它就是整个可⽤

的内存空间。当1个进程申请内存时，系统就分给它1个⼤于或等于进程所申请尺⼨的最⼩的2的幂次的空闲块。 例如，某进程提出的50KB的内存请求，将⾸先被系统向上取整，转化为对1个64KB的空闲块的请求。如果此时不存在如此⼤⼩的空闲

块，则此时可获得的1个最⼩的⽐该空闲块⼤的空闲块将被对分成2个“伙伴”单位。对其中1个伙伴单位的对分过程可能还要继续下去，直到

获得1个64KB的空闲块为⽌。伙伴系统的内存释放算法考虑将两个伙伴单位合并成1个⼤1倍的空闲单位。且这个合并过程会递归下去，直到不能继续合并为⽌。

注意观察下图，合并后的空闲区块也必须是2的幂次个字节

为了实现伙伴系统，系统要为每⼀种可能的空闲块维护1个空闲块链表。设系统管理的可⽤内存空间共为2N个字节，则1个伙伴系统最多需

要维护N个空闲块链表。由于每种尺⼨的空闲块都有⼀个空闲块队列，因此内存的分配与释放可以有效地进⾏。 伙伴系统的最⼤缺陷是不能有效地利⽤内存，特别是内碎⽚严重。例如，1个257KB的进程需要占⽤1个512KB的分配单位，其中将产⽣

255KB的内碎⽚。另外，每次释放内存时都尽可能地合并伙伴单位的做法也会降低系统性能，因为刚合并好的块可能马上⼜要对分。⼀种改

进的做法是延迟合并的时机。如今Linux⽤它。