操作系统实验三：存储器管理

问题描述

一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验帮助学生理解在采用循环首次适应算法管理方式下应怎样实现主存空间的分配和回收。

问题要求

在可变分区管理方式下采用循环首次适应算法实现主存分配和实现主存回收。

1. 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

0
10k	作业1
14k	作业3
26k	空闲区
32k	作业2
128k	空闲区

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

	起止	长度	状态
第一栏	14k	12k	未分配
第二栏	32k	96k	未分配
第三栏			空表目
第四栏			空表目
……			……

其中，

• 起址——指出一个空闲区的主存起始地址；
• 长度——指出从起始地址开始的一个连续空闲的长度；
• 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。

2. 上述的这张说明表的登记情况是按提示：

   下面一张表是所装入的三个作业占用的主存区域后填写的。

   当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

3. 采用循环首次适应算法分配主存空间。

   该算法是首次适应算法的变种。在分配内存空间时，不是每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。首次适应算法如图2。

4. 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图3。

源代码

ram = []
ram_list = []

for i in range(128):
    ram.append(0)

# 写入主存(起始地址，大小，序号)
def addTask(start, size, id): 
    global ram
    for i in range(size):
        ram[i + start] = id

# 展示信息
def show(): 
    global ram
    global ram_list
    ram_list = []
    it = 0
    ram_list.append([ram[0], 1, 0])
    for i in range(1, len(ram)):
        if ram[i] == ram[i - 1]:
            ram_list[it][1] += 1
        else:
            it += 1
            ram_list.append([ram[i], 1, i])
    for i in range(len(ram_list)):
        print('起始地址：' + str(ram_list[i][2]) + ' 长度：' + str(ram_list[i][1]) + ' ID：' + str(ram_list[i][0]))

# 申请主存
def apply(size, id): 
    global ram_list
    for i in range(len(ram_list)):
        if ram_list[i][0]==0 and ram_list[i][1] >= size:
            print('[写入了长度为 ' + str(size) +'K id为' + str(id) + '的作业]')
            addTask(ram_list[i][2], size, id)
            break

# 结束进程
def remove(id): 
    global ram
    for i in range(len(ram)):
        if ram[i] == id:
            ram[i] = 0
    print('[结束了作业' + str(id) + ']')

addTask(0, 10, 1)
addTask(10, 4, 3)
addTask(26, 6, 2)
show()
apply(6, 4)
show()
remove(3)
show()
remove(2)
show()