北京分校

考试资讯

      计算机专业课的备考，不仅要掌握一定的理论知识外，也要结合一定的题来查漏补缺。接下来，小编为广大2022计算机考研学子们给出了-2022计算机考研408知识点:动态分区分配和算法，希望对大家在专业知识理论的回顾上面有所帮助!

2022计算机考研408知识点:动态分区分配和算法

一、动态分区分配

根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这三方面的问题。

动态分区分配中数据结构：

为了实现动态分区分配，系统中必须配置相应的数据结构，用来描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式：

表1 空闲分区表

分区号	大小/KB	起址/KB
1	12	20
2	32	32
3	64	64
4	128	128

(1)空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项。

(2)空闲分区链：为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。

二、分区分配算法

1.首次适应算法

该算法将空闲分区表中登记的空闲分区按照其起始地址由低到高的次序排列，每次分配时从低地址开始查找，取第一个满足要求的空闲分区分配给进程。

优点：尽量使用低地址空间，因而在高地址的空间可能会保留较大的空闲分区。所以，大进程申请的存储空间大都能在高地址端得到满足。

缺点：低地址部分不断被划分，会留下许多难以利用的，很小的空闲分区，称为碎片。每次查找都是从低地址部分开始的，这无疑会增加查找可用空闲分区时的开销。

2.循环首次适应算法

该算法是首次适应算法的变种。在分配内存空间时，不再每次从低地址部分开始查找，而是从上次找到空闲区的下一个空闲分区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。

优点：减少查找空闲分区开销，空闲分区分布更均匀。

缺点：该算法常常会导致内存中缺乏大分区，因为它会均衡地利用空闲分区，包括分割较大的空闲分区。从而使得大进程无法装入内存运行。

3.较佳适应算法

该算法要求将所有的空闲分区按其容量从小到大的顺序形成一空闲分区链。在为进程分配存储空间时，从较小的空闲分区开始查找，满足进程申请存储空间大小的分区就是较适合的分区。总是选择满足申请要求且长度较小的空闲分区。

优点：不缺乏大的空闲区。

缺点：会在存储器中滞留许多难以利用的小分区--“零头(碎片)”;查找效率低。

4.较差适应算法

该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链。在为进程分配存储空间时，从较大的空闲分区开始查找，选择满足申请要求且长度较大的空闲分区，使分割出来的剩余空闲分区较大。

优点：剩余的空间较大化，不会出现太小的“零头”。

缺点：该算法总是分割大的空闲分区，那么当遇到大进程申请大空间时，无法找到一个足够大的空闲分区。

首次适应算法被认为较好、较快的算法，其次是循环首次适应算法，较佳算法，较差算法。

      以上是“2022计算机考研408知识点:动态分区分配和算法”，考生们一定要在理解的基础上来记忆。祝考研学子们，在备考中快速进步，加油!

推荐阅读：

2022计算机考研408知识点汇总