操作系统原理——可变分区存储管理

原理

进行一个实验报告的抄~

可变分区方式是按作业需要的主存空间大小来分区。
当装入一个作业时，首先要查看是否有足够的空闲空间来分配，若有则按指定的分配方式进行分配；否则作业不能装入。

可变分区的三种分配算法就是为作业分配主存空间的方法。

• 最先适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入第一个满足条件的空间中去。
• 最佳适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最小的一个空间中去。
• 最坏适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最大的一个空间中去。

从三种算法的说明可以看出，分配空间的过程主要可以分两步：

1. 查询所有满足作业需求的空间块。
2. 按照指定的算法将作业装入空间块中。

可变分区的回收算法：

• 回收区有下邻空闲区
• 回收区有上邻空闲区
• 归还区既有上邻空闲区又有下邻空闲区
• 归还区既无上邻空闲区又有下邻空闲区

实现

空闲表和已分配表

这里其实根据我的作业要求只能用一个内存分区表（就是一个列表）来实现的，但是明显是用两个表来表示会更方便，这样就不需要标志属性了！（偷懒）
所以我定义了两个全局变量，一个存空闲分区，一个存已分配分区。

free_list = []  # 空闲列表
allocated_list = []  # 已分配列表

空闲空间和已分配空间

这边用了两个类来表示：

class Free:
    """空闲表类"""

    def __init__(self, start, length):
        self.start = start  # 起址
        self.length = length    # 长度


class Allocated:
    """已分配表类"""

    def __init__(self, name, start, length):
        self.name = name    # 作业名
        self.start = start  # 起址
        self.length = length    # 长度

读取用户输入

我先不急着实现功能，而是先做了“具有交互功能”（确信）的函数，能够让用户操作数据和读取数据！

def input_data():
    """读取用户输入以及操作"""
    global free_list, allocated_list
    while True:
        op = input("请选择要进行的操作：A 分配主存； B 回收主存； C 显示主存； Q 退出；")
        if op == 'A':
            job_name = input("请输入作业名：")
            length = int(input("请输入作业长度"))
            algorithm = input("请输入分配算法：A 最先适应； B 最优适应； C 最坏适应；")
            if algorithm == 'A':
                allocate(job_name, length, algorithm)
            elif algorithm == 'B':
                allocate(job_name, length, algorithm)
            elif algorithm == 'C':
                allocate(job_name, length, algorithm)
            else:
                print("输入错误，请重新输入。")
        elif op == 'B':
            recycle_name = input("请输入要回收的作业名：")
            recycle(recycle_name)
        elif op == 'C':
            display()
        elif op == 'Q':
            print("程序退出。")
            break;
        else:
            print("输入错误，请重新输入。")

显示主存空间

为了检查前面写的代码没什么问题，比如功能选择、空闲和已分配列表，我决定先实现这个函数。

def display():
    """打印两张表"""
    global free_list, allocated_list
    free_list_sort('A')
    print("\n")
    print("空闲表".center(32, '-'))
    print("起址".center(10) + "|" + "长度".center(10) + "|" + "终址".center(10))
    for free in free_list:
        print(f"{free.start}".center(11) + "|" + f"{free.length}".center(
            11) + "|" + f"{free.start + free.length - 1}".center(11))
    print("".center(34, '-'))
    print("已分配表".center(32, '-'))
    print("名字".center(10) + "|" + "起址".center(10) + "|" + "长度".center(10))
    for job in allocated_list:
        print(f"{job.name}".center(11) + "|" + f"{job.start}".center(
            11) + "|" + f"{job.length}".center(11))
    print("".center(34, '-'))

(请无视这粗暴的代码分行，这是我用IDEA快捷格式化出来的。。。)
如果不明白其中的center方法的话，可以看我之后的随笔（写完后会在这里放跳转链接）。
在这个函数第二行我调用了一个free_list_sort函数，作用如其名，用来对空闲分区列表中的空闲分区排序。

对空闲分区列表进行排序

虽然看上去是写了一个函数，但其实用的还是python自带的sorted函数进行的排序因为真的太好用啦
为什么要特地写这个函数？因为分配主存空间有三种算法，最先、最优和最坏适应，这里我就写了三个排序方式：按照起址、长度升序、长度逆序。

def free_list_sort(method):
    """为空闲表选择排序方式"""
    global free_list
    if method == 'A':
        free_list = sorted(free_list, key=lambda free: free.start)  # 按照起址排序
    elif method == 'B':
        free_list = sorted(free_list, key=lambda free: free.length)  # 按照长度排序
    elif method == 'C':
        free_list = sorted(free_list, key=lambda free: free.length, reverse=True)  # 按照长度排逆序

这里的用到的sorted函数和sort方法类似，都接受两个作用一样的可选参数key和reverse，这两个参数有什么用可以看这篇文章：点我跳转
而lambda表达式就是一个单表达式函数，也可以当成匿名函数。在对可迭代对象进行排序的时候，我们都可以用lambda表达式定义简短的key函数。关于lambda表达式可能之后会写在随笔或者学习笔记里。

分配主存

虽然有三种算法，但是由于我的空闲分区和已分配分区是分开的，所以不同的地方只有排序上，剩下的找空闲分区并安排的操作是一样的。

def allocate(name, length, method):
    """分配主存空间"""
    global free_list, allocated_list
    free_list_sort(method)
    for i in range(len(free_list)):
        # 找到可进行分配的空间
        if free_list[i].length >= length:
            allocated_list.append(Allocated(name, free_list[i].start, length))
            allocated_list = sorted(allocated_list, key=lambda job: job.start)
            if free_list[i].length == length:
                del free_list[i]
            else:
                free_list[i].start = free_list[i].start + length
                free_list[i].length = free_list[i].length - length
            print("分配成功！")
            return
    print("分配失败！")

在找空闲分区前，我们先按照给定的算法对空闲分区列表进行排序，然后再去遍历这个列表，尝试找到合适的分区并对作业进行分配。
这里有两种情况，一种是作业长度刚好等于找到的空闲分区长度，这时候直接删除掉对应的空闲分区即可；若作业长度小于空闲分区的长度，这个空闲分区就应该重新计算起址和长度。

回收主存

这部分其实涉及到两个东西，一个是回收，一个是合并。
先来看回收：

def recycle(name):
    """回收空间"""
    global free_list, allocated_list
    for i in range(len(allocated_list)):
        # 检查已分配表中是否有该作业
        if allocated_list[i].name == name:
            free_list.append(Free(allocated_list[i].start, allocated_list[i].length))
            free_list_sort('A')
            for index in range(len(free_list)):
                # 找出新加入的空闲表的索引并调用merge函数进行合并
                if free_list[index].start == allocated_list[i].start:
                    merge(index)
                    break
            del allocated_list[i]
            print("回收成功！")
            return
    print("回收失败！")

可以看出遍历一遍已分配列表就好啦，找到对应名字的作业后，先在空闲分区列表中加入一个新的空闲分区，然后对这个新的空闲分区调用merge函数进行合并，最后使用del函数删除掉这个作业即可~
那么我们再来看看合并函数：

def merge(index):
    """合并空间"""
    global free_list
    if index == 0:
        # 第一个元素，只需向下合并
        if free_list[index].start + free_list[index].length == free_list[index + 1].start:
            # 当前起址加上长度等于下个起址，可以合并
            free_list[index].length = free_list[index].length + free_list[index + 1].length
            del free_list[index + 1]
        return
    elif index == len(free_list) - 1:
        # 最后一个元素，只需向上合并
        if free_list[index - 1].start + free_list[index - 1].length == free_list[index].start:
            # 上个起址加上长度等于当前起址，可以合并
            free_list[index - 1].length = free_list[index - 1].length + free_list[index].length
            del free_list[index]
        return
    else:
        # 向上向下均要检查
        if free_list[index].start + free_list[index].length == free_list[index + 1].start:
            # 当前起址加上长度等于下个起址，可以合并
            free_list[index].length = free_list[index].length + free_list[index + 1].length
            del free_list[index + 1]
        if free_list[index - 1].start + free_list[index - 1].length == free_list[index].start:
            # 上个起址加上长度等于当前起址，可以合并
            free_list[index - 1].length = free_list[index - 1].length + free_list[index].length
            del free_list[index]
        return

由于我们在回收的时候重新“整理”（排序）了空闲分区列表，列表中的空闲分区现在是连续（有序）的，所以可以直接用下标进行数据处理。
不过在上下均要回收的时候，不要搞错了数组下标以及合并先后顺序、合并的应该是哪个空闲分区。

测试代码

为了方便提前提供了一点数据：

if __name__ == '__main__':
    # 预输入数据
    free_1 = Free(10, 16)
    free_2 = Free(36, 14)
    free_3 = Free(55, 10)
    free_4 = Free(70, 30)
    free_list.append(free_1)
    free_list.append(free_2)
    free_list.append(free_3)
    free_list.append(free_4)
    job_1 = Allocated('A', 26, 10)
    job_2 = Allocated('B', 50, 5)
    job_3 = Allocated('C', 65, 5)
    allocated_list.append(job_1)
    allocated_list.append(job_2)
    allocated_list.append(job_3)
    input_data()

那么代码部分到这就堂堂完结啦

运行结果

这部分还请大家自行验证（因为不想放图…）

尾声

尾声就是没有尾声。

希望本文章能够帮到您~