基于顺序搜索的分区分配算法

为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。基于顺序搜索的分配方式是依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区，主要有如下四种算法。

首次适应算法

首次适应(first fit，FF)算法要求空闲分区链以地址递增的次序链接，在分配内存时从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败。

该算法倾向于优先利用内存中低址部分的空闲分区，保留了高址部分的大空闲区。缺点是低址部分不断被划分，会留下许多难以利用的外部碎片。而每次查找又都是从低址部分开始的，会导致搜索的时间开销较大。

循环首次适应算法

为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，可以使用循环首次适应算法。循环首次适应(next fit，NF)算法在为进程分配内存空间时，是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区。实现该算法一般会使用循环链表，如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区。

算法能使内存中的空闲分区分布得更均匀，减少了查找空闲分区时的开销。但这样会导致高地址的大分区可能被划分为小分区来使用，使缺乏大的空闲分区给较大的进程。

最佳适应算法

最佳适应(best fit，BF)算法在每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链，这样第一次找到的能满足要求的空闲区必然是最佳的。

由于每次分配后所切割下来的剩余部分总是最小的，所以在存储器中会留下许多难以利用的碎片。

最坏适应算法

最坏适应(worst fit，WF)算法在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用。该算法要求将所有的空闲分区，按其容量以从大到小的顺序形成空闲分区链。

这个算法会使存储器中缺乏大的空闲分区，它的优点是可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。同时最坏适应分配算法查找效率很高，查找时只要看第一个分区能否满足作业要求即可。

实验说明

实验目的

理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。

实验内容

按内容要求编写最佳适应和最坏适应存储分配算法。编写测试程序，对存储分配表进行初始化，然后对用户输入的请求和释放，按算法动态更新存储分配表，并将每次更新之后的存储分配表在屏幕上显示出来。

代码编写

ResourceTable 类

ResourceTable 类为系统资源表，有如下 3 个属性。

ResourceTable 类有如下 5 个方法。

class ResourceTable(object):
    def __init__(self, size):
        '''
        构造一个 ResourceTable 对象，为系统资源表。
        param size: int，空间的总大小
        '''
        self.FreeSpace = []         #空闲空间表
        self.AllocatedSpace = []    #已分配空间表
        self.method = 'bf'          #分配方式，bf为最佳适应，wf为最坏适应
        #初始化一个大小为size的空闲空间
        self.FreeSpace.append(Space(0,size))
    def distributeSpace(self, size):
        '''
        分配空间，从空闲空间表划分一个空闲空间，加入到已分配空间表。
        param size: int，划分出的空间大小
        '''
        idx = -1
        for i in range(len(self.FreeSpace)):
            #由于空闲空间表按照分配算法的特点进行排序，
            #所以找到的第一个可分配空间即可结束搜索
            if self.FreeSpace[i].size >= size:
                idx = i
                break
        if idx == -1:
            #没有符合要求的空闲空间
            print("Error !")
        else:
            #划分一个新的空间
            space = Space(self.FreeSpace[i].address, size)
            self.AllocatedSpace.append(space)
            if self.FreeSpace[i].size - size == 0:
                #刚好划分整个空间
                self.FreeSpace.pop(i)
            else:
                #划分一部分需要的空间
                self.FreeSpace[i].address += size
                self.FreeSpace[i].size -= size
        if self.method == 'bf':
            #最佳适应算法，按空闲空间由小到大的顺序排序
            self.FreeSpace.sort(key = Space.getSize)
        else:
            #最坏适应算法，按空闲空间由大到小的顺序排序
            self.FreeSpace.sort(key = Space.getSize, reverse=True)
        #已分配空间表按地址顺序排序
        self.AllocatedSpace.sort(key = Space.getAddress)
    def releaseSpace(self, address):
        '''
        释放空间，从已分配空间表释放一个空间，返回到空闲空间表，相邻的空间进行合并。
        param address: int，释放的空间地址
        '''
        idx = -1
        for i in range(len(self.AllocatedSpace)):
            #搜索是否有该地址的已分配空间
            if self.AllocatedSpace[i].address == address:
                idx = i
                break
        if idx == -1:
            #没有找到要释放的地址
            print("Error !")
        else:
            #释放空间，返回空闲空间表
            newSpace = self.AllocatedSpace.pop(idx)
            self.FreeSpace.append(newSpace)
            self.FreeSpace.sort(key = Space.getAddress)
            #相邻的空间进行合并
            flag = 1
            while flag:
                #由于在遍历时破坏被迭代的结构是危险的，所以采用多次合并的方法
                flag = 0
                for i in range(len(self.FreeSpace) - 1):
                    if self.FreeSpace[i].address + self.FreeSpace[i].size == self.FreeSpace[i + 1].address:
                        #如果表中2个空间可以合并，合并大小并设置被合并的空间为标志-1
                        self.FreeSpace[i].size += self.FreeSpace[i + 1].size
                        self.FreeSpace[i + 1].address = -1
                        #由于被迭代对象结构的改变，所以需要再次合并
                        flag = 1
                for space in self.FreeSpace:
                    if space.address == -1:
                        #删除被标记为-1的空间
                        self.FreeSpace.remove(space)
            #已分配空间表只是取出了一个元素，所以其他元素还是有序的不需要排序
            if self.method == 'bf':
                #最佳适应算法，按空闲空间由小到大的顺序排序
                self.FreeSpace.sort(key = Space.getSize)
            else:
                #最坏适应算法，按空闲空间由大到小的顺序排序
                self.FreeSpace.sort(key = Space.getSize, reverse=True)
    def printFree(self):
        '''
        打印空闲空间表的信息
        '''
        print("FreeSpace:")
        for space in self.FreeSpace:
            print(space)
    def printAllocated(self):
        '''
        打印已分配空间表的信息
        '''
        print("AllocatedSpace:")
        for space in self.AllocatedSpace:
            print(space)

Space 类

Space 类用于刻画单个空间，有如下 2 个属性。

Space 类有如下 4 个方法。

class Space(object):
    def __init__(self, address, size):
        '''
        构造一个 Space 对象，表示单个空间。
        param address: int，空间的起始地址
        param size: int，空间的总大小
        '''
        self.address = address    #起始地址
        self.size = size          #空间大小
    def __str__(self):
        '''
        魔术方法，格式化输出Space对象。
        '''
        return ("address: {}; size: {}".format(self.address, self.size))
    def getSize(self):
        '''
        获取address属性的get方法，排序用。
        '''
        return self.size
    def getAddress(self):
        '''
        获取size属性的get方法，排序用。
        '''
        return self.address

测试代码

#测试代码
size = int(input("请输入空闲空间的总大小："))
table = ResourceTable(size)
method = input("请输入分配方式：")
if method == 'wf': 
    table.method = 'wf'
while 1:
    action = int(input("请输入你的动作，1为申请，2为释放："))
    if action == 1:
        size = int(input("请输入申请空间的大小："))
        table.distributeSpace(size)
    elif action == 2:
        address = int(input("请输入释放的地址："))
        table.releaseSpace(address)
    else:
        break
    table.printFree()
    table.printAllocated()

运行效果

最佳适应算法

最坏适应算法