操作系统:存储管理算法(python实现)

连续分配存储管理方式

该分配方式为用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配是物理地址的相邻。连续分配方式可分为四类：

• 单一连续分配
• 固定分区分配
• 动态分区分配
• 动态可重定向分配

本文仅重点介绍动态分区分配算法

动态分区分配

动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。

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

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

1. 空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲的情况。每个空闲分区占一个表目(行)，表目中包括分区号、分区大小和分区始址等数据项，如下图所示
   
2. 空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接空闲分区的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。如下图所示
   

本文主要针对空闲分区链编写python代码

分区分配操作

在动态分区存储管理方式中，主要的操作是分配内存和回收内存

• 分配内存：系统利用某种分配算法，从空闲分区链中找到所需大小的分区。设请求的分区大小为apply.size，表中每个空闲分区的大小表示为part.size。若part.size - apply.size <= min_size(min_size是事先规定的最小剩余)，说明多余的部分太小，可不分割，将整个分区分配个请求者。否则(即多余的部分超过min_size)，说明剩下了很多，便可从该分区中按请求的大小划分出一块内存空间出去，余下的部分仍留在空闲分区链(表)中。最后将分配区的 首址(address) 返回给调用者。流程如下：
  
• 回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
  1. 回收区与插入点前一个空闲分区$F_{1}$相邻接。此时应将回收区与$F_{1}$合并。不必创建新表项，只需修改其前一分区$F_{1}$的大小。
  2. 回收分区与插入点的后一空闲分区$F_{2}$相邻接。此时也将两分区合并。但回收区的首址作为新空闲区的首址。
  3. 回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用前一个分区的表项和首址，取消后一个分区的表项。
  4. 回收区既与前后两个分区都不邻接。此时为回收区单独建立一个新表项，首址和大小分别为回收区的首址和大小。
     内存回收的流程如下：
     

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

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

• 首次适应(first fit, FF)算法：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。
• 循环首次适应(next fit, NF)算法：NF算法不再是每次都从链首开始查找，而是从上一次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区。
• 最佳适应(best fit, BF)算法：BF算法要求每次为作业分配内存时，总是把能满足要求、又是最小的空间分区分配给作业。同时，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。
• 最坏适应(worst fit, WF)算法：WF算法与BF算法相反：它在扫描整个空闲分区链时，总是挑选出一个最大的空闲区，以至于存储器中缺乏大的空闲分区

首次适应算法实现

分析操作系统的内存管理流程后大致可把算法分为以下几个步骤：

• 初始化空闲分区链
• 发出内存请求
• 使用算法(FF)分配内存
• 回收内存

用python实现该算法代码如下：

import numpy as np


class PartitionNode:
    """
    a node of idle partition chain
    """
    def __init__(self, size, loc):
        """
        initialize the node
        :param size: the size of this partition
        """
        self.prior = None  # the prior of this partition
        self.part_size = size
        self.loc = loc     # the begin location of this partition
        self.status = 0    # the distribution status of this partition
        self.next = None   # the next of this partition


class PartitionChain:
    def __init__(self, num):
        """
        initialize a free partition chain
        :param num:
        """
        self.partition_chain = PartitionNode(np.random.randint(50, 151), 0)  # create the head node
        self.num = num  # the number of the partition
        self.size = self.partition_chain.part_size
        self.free = 0   # the free space of the partition
        self.__init_chain()  # initialize the partition chain
        self.min_remain = 25  # the minimum size of split

    def __init_chain(self):
        """
        initialize the partition charin
        :return:
        """
        tmp = self.partition_chain
        for time in range(1, self.num):
            tmp.next = PartitionNode(np.random.randint(50, 151), self.size)  # create the next node
            self.size += tmp.next.part_size
            tmp.next.prior = tmp  # point to the prior node
            tmp = tmp.next
        self.free = self.size

    def print_chain(self):
        """
        print the infomation of partition chain
        :return:
        """
        tmp = self.partition_chain
        self.free = 0
        while tmp:
            self.free += tmp.part_size
            tmp = tmp.next
        tmp = self.partition_chain
        print("空闲分区链(分区数-%d 大小-%d 空闲-%d):" % (self.num, self.size, self.free), end=" ")
        while tmp:
            if tmp.next:
                print("<AT-%d, S-%d>" % (tmp.loc, tmp.part_size), end='···')
            else:
                print("<AT-%d, S-%d>" % (tmp.loc, tmp.part_size))
            tmp = tmp.next

    def alloc_memory(self, method, m):
        """
        the algorithm of allocate memory
        :param method: first fit, next fit, best fit, worst fit
        :param m: the memory of application
        :return:
        """
        print('**需求**:', m)
        if method == 'first':
            tmp = self.partition_chain
            while tmp:
                if m <= tmp.part_size and tmp.status == 0:  # 按顺序找到第一个能满足要求的空闲分区
                    if tmp.part_size - m <= self.min_remain:  # 划分后剩余的大小过小，则分出整个分区，并调整分区链结构
                        self.num -= 1  # 长度减一
                        if tmp.prior is None:   # 如果是表头
                            self.partition_chain = tmp.next
                            self.partition_chain.prior = None
                        elif tmp.next is None:  # 如果是表尾
                            tmp.prior.next = None
                        else:
                            tmp.next.prior = tmp.prior
                            tmp.prior.next = tmp.next
                        print("**Info**: 分配成功^_^, 地址-%d 大小-%d" % (tmp.loc, tmp.part_size))
                        return {'Address': tmp.loc, 'Size': tmp.part_size}
                    else:
                        tmp.part_size -= m
                        print("**Info**: 分配成功^_^, 地址-%d 大小-%d" % (tmp.loc, m))
                        return {'Address': tmp.loc, 'Size': m}  # 返回分配区的首地址
                else:
                    tmp = tmp.next
            print('**Info**: 分配失败x_x')
        elif method == 'next':
            pass
        elif method == 'best':
            pass
        elif method == 'fit':
            pass

    def dealloc_memory(self, m_dict):
        """
        recycle the memeory
        :param m_dict: the dict of deallocated memory
        :return:
        """
        if m_dict is None:
            print("**Info**: 回收失败x_x")
            return
        loc = m_dict.get('Address')
        size = m_dict.get('Size')
        tmp = self.partition_chain
        while tmp:
            if tmp.prior is None:   # 表头分区
                if loc <= tmp.loc:
                    if loc == tmp.loc:  # 同一分区
                        tmp.part_size += size
                    else:  # 与表头分区不邻接，自己作为表头分区
                        new_part = PartitionNode(size, loc)
                        new_part.next = tmp
                        tmp.prior = new_part
                        self.partition_chain = new_part
                        self.num += 1
                    print("**Info**: 大小:%d 回收成功^_^" % size)
                    break
            elif (tmp.next is None) and (loc >= tmp.loc):  # 表尾分区, 且在表尾之后
                if tmp.loc == loc:  # 与表尾分区邻接，表尾分区在前
                    tmp.part_size += size
                else:  # 与表尾分区不邻接，自己作为表尾分区
                    new_part = PartitionNode(size, loc)
                    tmp.next = new_part
                    new_part.prior = tmp
                    self.num += 1
                print("**Info**: 大小:%d 回收成功^_^" % size)
                break
            else:  # 表中分区，前后皆有分区存在
                if loc <= tmp.loc:
                    if ((loc + size) == tmp.loc) | (loc == tmp.loc):
                        if loc == tmp.loc:  # 同一分区
                            tmp.part_size += size
                        elif (tmp.prior.loc + tmp.prior.part_size) == loc:  # 1.同时与前面和后面的分区邻接
                            next_part = tmp.next
                            if next_part:  # 如果是不是表尾分区
                                next_part.prior = tmp.prior
                            tmp.prior.part_size += size + tmp.part_size
                            tmp.prior.next = next_part
                        else:  # 2.只与后面的分区邻接
                            tmp.part_size += size
                        print("**Info**: 大小:%d 回收成功^_^" % size)
                        break
                    else:
                        if loc == tmp.prior.loc:
                            tmp.prior.part_size += size
                        elif (tmp.prior.loc + tmp.prior.part_size) == loc:  # 3.只与前面的分区邻接
                            tmp.prior.part_size += size
                        else:  # 4.与前面和后面的都不邻接
                            new_part = PartitionNode(size, loc)
                            new_part.next = tmp
                            new_part.prior = tmp.prior
                            tmp.prior.next = new_part
                            tmp.prior = new_part
                            self.num += 1
                        print("**Info**: 大小:%d 回收成功^_^" % size)
                        break
            tmp = tmp.next


if __name__ == "__main__":
    my_chain = PartitionChain(5)
    my_chain.print_chain()
    my_apply = []
    for i in range(3):
        # 请求内存
        rnd = np.random.randint(80, 130)
        my_apply.append(my_chain.alloc_memory('first', rnd))
    my_chain.print_chain()
    print('已经请求的分区:', my_apply)
    for applys in my_apply:
        my_chain.dealloc_memory(applys)
    my_chain.print_chain()

运行示例如下：

空闲分区链(分区数-5 大小-484 空闲-484): <AT-0, S-126>···<AT-126, S-132>···<AT-258, S-50>···<AT-308, S-68>···<AT-376, S-108>
**需求**: 118
**Info**: 分配成功^_^, 地址-0 大小-126
**需求**: 86
**Info**: 分配成功^_^, 地址-126 大小-86
**需求**: 82
**Info**: 分配成功^_^, 地址-376 大小-82
空闲分区链(分区数-4 大小-484 空闲-190): <AT-126, S-46>···<AT-258, S-50>···<AT-308, S-68>···<AT-376, S-26>
已经请求的分区: [{'Address': 0, 'Size': 126}, {'Address': 126, 'Size': 86}, {'Address': 376, 'Size': 82}]
**Info**: 大小:126 回收成功^_^
**Info**: 大小:86 回收成功^_^
**Info**: 大小:82 回收成功^_^
空闲分区链(分区数-5 大小-484 空闲-484): <AT-0, S-126>···<AT-126, S-132>···<AT-258, S-50>···<AT-308, S-68>···<AT-376, S-108>

如有不当指出，请多多指教。