操作系统实验3【动态分区存储管理】

今天药忘吃喽~ 2023-01-20 14:59 14阅读 0赞

> 1.  [操作系统 实验1【短作业优先调度算法（C++实现——FCFS\\SJF\\HRRN）】][_1_C_FCFS_SJF_HRRN]
> 2.  [操作系统 实验2【动态高优先权优先调度算法 C++实现】][_2_ C]
> 3.  [操作系统 实验3【动态分区存储管理 Python实现】][_3_ Python]
> 4.  [操作系统 实验4【基本分页存储管理 C++实现】][_4_ C]

**目录**

一、实验目的（目的与任务）

二、实验内容（内容、要求与安排方式）

三、实验代码

①创建表示分区的类，类包含：分区ID、起始地址、结束地址、分区长度、分区状态

②导入python模块，方便拷贝分区对象

③编写表示分区状态的函数

④编写冒泡排序函数

⑤编写首次适应算法（First Fit）函数

⑥编写最佳适应算法（Best Fit）函数

⑦回收内存（作业）函数

⑧编写主函数

完整实验代码

四、实验结果

五、实验总结

--------------------

# 一、实验目的（目的与任务） #

> 熟悉并掌握动态分区分配的各种算法。
> 
> 熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。

# 二、实验内容（内容、要求与安排方式） #

> 用高级语言模拟实现动态分区存储管理，要求：
> 
> 1.  分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。
> 2.  分区的初始化——可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小）
> 3.  分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。
> 4.  分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出来。（注意：不存在的作业号要给出错误提示！）
> 5.  分区的显示：任何时刻，可以查看当前内存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来）
> 6.  要求考虑：（1）内存空间不足的情况，要有相应的显示；
> 
>       （2）作业不能同名，但是删除后可以再用这个名字；
> 
>       （3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。

# 三、实验代码 #

### ①创建表示分区的类，类包含：分区ID、起始地址、结束地址、分区长度、分区状态 ###

> class Memory(object):
> 
>     def \_\_init\_\_(self, start, end, length, state=1, ID=0): 
> 
>         self.Id = ID  \#\#ID为0是未分配，其余为任务编号
> 
>         self.start = start
> 
>         self.end = end
> 
>         self.length = length
> 
>         self.state = state  \# state为1：内存未分配

### ②导入python模块，方便拷贝分区对象 ###

> import copy \# 导入python模块，copy仅拷贝对象本身

### ③编写表示分区状态的函数 ###

> def show\_memory(list):
> 
>     print("分配状态    分区号    起始地址   终止地址  分区大小")
> 
>     for i in range(0, len(list)):
> 
>         p = list\[i\]
> 
>         if p.state == 1:
> 
>             print("%s%s%s%11.d%11.d%10.d" % ('空闲', "          ", p.Id, p.start, p.end, p.length))
> 
>         else:
> 
>             print("%s%s%s%11.d%11.d%10.d" % ('已分配', "        ", p.Id, p.start, p.end, p.length))

### ④编写冒泡排序函数 ###

> \#\#冒泡排序
> 
> def bubble\_sort(list):
> 
>     count = len(list)
> 
>     for i in range(0, count):
> 
>         for j in range(i + 1, count):
> 
>             if list\[i\].length < list\[j\].length:
> 
>                 list\[i\], list\[j\] = list\[j\], list\[i\]
> 
>     return list

### ⑤编写首次适应算法（First Fit）函数 ###

> \# 首次适应算法（First Fit）
> 
> def FF(work\_id, work\_length, list):
> 
>     for i in list:
> 
>         if i.Id == work\_id:
> 
>             print('作业已存在！')
> 
>             return
> 
>     for i in range(0, len(list)):
> 
>         p = list\[i\]
> 
>         if p.state == 1 and p.length > work\_length:  \# p是当前未分配内存的大小
> 
>             node2 = Memory(p.start + work\_length, p.end, p.length - work\_length, 1, 0)  \# 剩下的未分配的
> 
>             a = Memory(p.start, p.start + work\_length - 1, work\_length, state=0, ID=work\_id)  \# a是已分配的
> 
>             del list\[i\]
> 
>             list.insert(i, node2)
> 
>             list.insert(i, a)
> 
>             show\_memory(list)
> 
>             return
> 
>         if p.state == 1 and p.length == work\_length:
> 
>             p.state = 0
> 
>             show\_memory(list)
> 
>             return
> 
>     print("内存空间不足！")

### ⑥编写最佳适应算法（Best Fit）函数 ###

> \#\#最佳适应算法（Best Fit）
> 
> def BF(work\_id, work\_length, li):
> 
>     for i in li:
> 
>         if i.Id == work\_id:
> 
>             print('作业已存在！')
> 
>             return
> 
>     q = copy.copy(li)
> 
>     q = bubble\_sort(q)  \# 从小到大排序,给所有已分配和未分配的排序
> 
>     s = -1
> 
>     ss12 = -1
> 
>     for i in range(0, len(q)):
> 
>         p = q\[i\]
> 
>         if p.state == 1 and p.length > work\_length:  \# p.state == 1 已分配的不参与分配
> 
>             s = p.start  \# s得到起始位置
> 
>         elif p.state == 1 and p.length == work\_length:
> 
>             ss12 = p.start
> 
>     if s == -1 and ss12 == -1:
> 
>         print("内存空间不足！")
> 
>         return
> 
>     for i in range(0, len(li)):
> 
>         p = li\[i\]
> 
>         if p.start == s:
> 
>             node2 = Memory(p.start + work\_length, p.end, p.length - work\_length, 1, 0)  \# 未分配
> 
>             a = Memory(p.start, p.start + work\_length - 1, work\_length, state=0, ID=work\_id)
> 
>             del li\[i\]
> 
>             li.insert(i, node2)
> 
>             li.insert(i, a)
> 
>             show\_memory(li)
> 
>             return
> 
>         elif p.start == ss12:
> 
>             p.state = 0
> 
>             show\_memory(li)
> 
>             return
> 
>

### ⑦回收内存（作业）函数 ###

> \#\#回收内存（作业）函数
> 
> def free1(work\_id, li):
> 
>     for i in range(0, len(li)):
> 
>         p = li\[i\]
> 
>         if p.Id == work\_id:
> 
>             p.state = 1
> 
>             target = i
> 
>             p.Id = 0
> 
>             break
> 
>     \# 向前合并空闲块
> 
>     if target - 1 > 0:
> 
>         if li\[target - 1\].state == 1:
> 
>             a = Memory(li\[target - 1\].start, li\[target\].end, li\[target - 1\].length + li\[target\].length, 1, 0)
> 
>             del li\[target - 1\]
> 
>             del li\[target - 1\]
> 
>             li.insert(target - 1, a)
> 
>             target = target - 1
> 
>     \# 向后合并空闲块
> 
>     if target + 1 < len(li):
> 
>         if li\[target + 1\].state == 1:
> 
>             a = Memory(li\[target\].start, li\[target + 1\].end, li\[target\].length + li\[target + 1\].length, 1, 0)
> 
>             del li\[target\]
> 
>             del li\[target\]
> 
>             li.insert(target, a)
> 
>     show\_memory(li)

### ⑧编写主函数 ###

> if \_\_name\_\_ == '\_\_main\_\_':
> 
>     print("输入内存大小：")
> 
>     size = int(input())
> 
>     a = Memory(0, size - 1, size, state=1, ID=0)
> 
>     b = \[\]
> 
>     b.append(a)
> 
>     print('\*\*\*\*\*\*\*1：初始化\*\*\*\*\*\*')
> 
>     print('\*\*\*\*\*\*\*2：分配空间\*\*\*\*')
> 
>     print('\*\*\*\*\*\*\*3：回收\*\*\*\*\*\*\*\*')
> 
>     print('\*\*\*\*\*\*\*4：查看\*\*\*\*\*\*\*\*')
> 
>     print('\*\*\*\*\*\*\*5：退出\*\*\*\*\*\*\*\*')
> 
>     while (True):
> 
>         select = input('请输入想要执行的功能：')
> 
>         if select == '5':
> 
>             break
> 
>         elif select == '1':
> 
>             print("输入内存大小：")
> 
>             size = int(input())
> 
>             a = Memory(0, size - 1, size, state=1, ID=0)
> 
>             b = \[\]
> 
>             b.append(a)
> 
>         elif select == '2':
> 
>             print("1.首次适应算法：FF")
> 
>             print("2.最佳适应算法：BF")
> 
>             x = input("请输入分配执行的算法：")
> 
>             x = float(x)
> 
>             repit = 'Y'
> 
>             while (repit == 'Y'):
> 
>                 if x == 1:
> 
>                     work\_size = input('请输入作业id和大小：').split()
> 
>                     FF(work\_size\[0\], int(work\_size\[1\]), b)
> 
>                     repit = input('是否继续（Y/N）：')
> 
>                 elif x == 2:
> 
>                     work\_size = input('请输入作业id和大小：').split()
> 
>                     BF(work\_size\[0\], int(work\_size\[1\]), b)
> 
>                     repit = input('是否继续（Y/N）：')
> 
>         elif select == '3':
> 
>             id\_delete = input('请输入删除作业id：')
> 
>             free1(id\_delete, b)
> 
>         else:
> 
>             show\_memory(b)

## 完整实验代码 ##

import copy # 导入python模块，copy仅拷贝对象本身
 
 
 # 创建表示分区的类，类包含：分区ID、起始地址、结束地址、分区长度、分区状态
 class Memory(object):
 def __init__(self, start, end, length, state=1, ID=0): # __init__()方法是一种特殊的方法，被称为类的初始化方法，当创建这个类的实例时就会调用该方法
 # self代表类的实例，self在定义类的方法时是必须有的，虽然在调用时不必传入相应的参数
 self.Id = ID ##ID为0是未分配，其余为任务编号
 self.start = start
 self.end = end
 self.length = length
 self.state = state # state为1：内存未分配
 
 
 # 编写表示分区状态的函数
 def show_memory(list):
 print("分配状态 分区号 起始地址 终止地址 分区大小")
 for i in range(0, len(list)):
 p = list[i]
 if p.state == 1:
 print("%s%s%s%11.d%11.d%10.d" % ('空闲', " ", p.Id, p.start, p.end, p.length))
 else:
 print("%s%s%s%11.d%11.d%10.d" % ('已分配', " ", p.Id, p.start, p.end, p.length))
 
 
 # 首次适应算法（First Fit）
 def FF(work_id, work_length, list):
 for i in list:
 if i.Id == work_id:
 print('作业已存在！')
 return
 for i in range(0, len(list)):
 p = list[i]
 if p.state == 1 and p.length > work_length: # p是当前未分配内存的大小
 node2 = Memory(p.start + work_length, p.end, p.length - work_length, 1, 0) # 剩下的未分配的
 a = Memory(p.start, p.start + work_length - 1, work_length, state=0, ID=work_id) # a是已分配的
 del list[i]
 list.insert(i, node2)
 list.insert(i, a)
 show_memory(list)
 return
 if p.state == 1 and p.length == work_length:
 p.state = 0
 show_memory(list)
 return
 print("内存空间不足！")
 
 
 # 回收内存（作业）函数
 def free1(work_id, li):
 for i in range(0, len(li)):
 p = li[i]
 if p.Id == work_id:
 p.state = 1
 target = i
 p.Id = 0
 break
 # 向前合并空闲块
 if target - 1 > 0:
 if li[target - 1].state == 1:
 a = Memory(li[target - 1].start, li[target].end, li[target - 1].length + li[target].length, 1, 0)
 del li[target - 1]
 del li[target - 1]
 li.insert(target - 1, a)
 target = target - 1
 # 向后合并空闲块
 if target + 1 < len(li):
 if li[target + 1].state == 1:
 a = Memory(li[target].start, li[target + 1].end, li[target].length + li[target + 1].length, 1, 0)
 del li[target]
 del li[target]
 li.insert(target, a)
 show_memory(li)
 
 
 # 冒泡排序
 def bubble_sort(list):
 count = len(list)
 for i in range(0, count):
 for j in range(i + 1, count):
 if list[i].length < list[j].length:
 list[i], list[j] = list[j], list[i]
 return list
 
 
 # 最佳适应算法（Best Fit）
 def BF(work_id, work_length, li):
 for i in li:
 if i.Id == work_id:
 print('作业已存在！')
 return
 q = copy.copy(li)
 q = bubble_sort(q) # 从小到大排序,给所有已分配和未分配的排序
 s = -1
 ss12 = -1
 for i in range(0, len(q)):
 p = q[i]
 if p.state == 1 and p.length > work_length: # p.state == 1，已分配的不参与分配
 s = p.start # s得到起始位置
 elif p.state == 1 and p.length == work_length:
 ss12 = p.start
 if s == -1 and ss12 == -1:
 print("内存空间不足！")
 return
 for i in range(0, len(li)):
 p = li[i]
 if p.start == s:
 node2 = Memory(p.start + work_length, p.end, p.length - work_length, 1, 0) # 未分配
 a = Memory(p.start, p.start + work_length - 1, work_length, state=0, ID=work_id)
 del li[i]
 li.insert(i, node2)
 li.insert(i, a)
 show_memory(li)
 return
 elif p.start == ss12:
 p.state = 0
 show_memory(li)
 return
 
 
 # 主函数
 if __name__ == '__main__':
 print("输入内存大小：")
 size = int(input())
 a = Memory(0, size - 1, size, state=1, ID=0)
 b = []
 b.append(a)
 print('*******1：初始化******')
 print('*******2：分配空间（FF\BF）****')
 print('*******3：回收********')
 print('*******4：查看********')
 print('*******5：退出********')
 while (True):
 select = input('请输入想要执行的功能：')
 if select == '5':
 break
 elif select == '1':
 print("输入内存大小：")
 size = int(input())
 a = Memory(0, size - 1, size, state=1, ID=0)
 b = []
 b.append(a)
 elif select == '2':
 print("1.首次适应算法：FF")
 print("2.最佳适应算法：BF")
 x = input("请输入分配执行的算法：")
 x = float(x)
 repit = 'Y'
 while (repit == 'Y'):
 if x == 1:
 work_size = input('请输入作业id和大小：').split()
 FF(work_size[0], int(work_size[1]), b)
 repit = input('是否继续（Y/N）：')
 elif x == 2:
 work_size = input('请输入作业id和大小：').split()
 BF(work_size[0], int(work_size[1]), b)
 repit = input('是否继续（Y/N）：')
 elif select == '3':
 id_delete = input('请输入删除作业id：')
 free1(id_delete, b)
 else:
 show_memory(b)

# 四、实验结果 #

> BF算法有一点小毛病儿：两个相同的分区，比如2个20，这个BF是从末尾地址开始分配的；不能这样写，应该从低地址开始分配。
> 
> ![20210613101911131.png][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][]  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1][]

# 五、实验总结 #

> 动态分区分配算法包括如下4种算法：首次适应算法（First Fit）、最佳适应算法（Best Fit）、最坏适应算法（Worst Fit）、临近适应算法（Next Fit）。
> 
> 动态分区管理方式，在初始时不将主存划分区域，而是把占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业的大小查询主存内各空闲区的状态，按照特定的算法选择一个合适的空闲区，按作业大小划分出一个分区并装入该作业，剩下的区域作为新的空闲区。
> 
> 当作业执行完毕后，所占用的主存空间将被回收，成为一个空闲区；如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。
> 
>    通过本次实验，我对动态分区分配算法有了更深的理解，将4种算法的特点整理如下：
> 
> <table> 
> <tbody> 
> <tr> 
> <td style="vertical-align:top;width:55.05pt;"> 算法 </td> 
> <td style="vertical-align:top;width:3cm;"> 算法思想 </td> 
> <td style="vertical-align:top;width:77.95pt;"> 分区排列顺序 </td> 
> <td style="vertical-align:top;width:4cm;"> 优点 </td> 
> <td style="vertical-align:top;width:94.65pt;"> 缺点 </td> 
> </tr> 
> <tr> 
> <td style="vertical-align:top;width:55.05pt;"> 首次适应算法 </td> 
> <td style="vertical-align:top;width:3cm;"> 从头到尾寻找合适的分区 </td> 
> <td style="vertical-align:top;width:77.95pt;"> 空闲分区以地址递增次序排列 </td> 
> <td style="vertical-align:top;width:4cm;"> 综合看，首次适应算法性能最好。算法开销小，回收分区后，一般不需要对空闲分区队列重新排序 </td> 
> <td style="vertical-align:top;width:94.65pt;"> 略！ </td> 
> </tr> 
> <tr> 
> <td style="vertical-align:top;width:55.05pt;"> 最佳适应算法 </td> 
> <td style="vertical-align:top;width:3cm;"> 优先使用更小的分区，以保留更多的大分区 </td> 
> <td style="vertical-align:top;width:77.95pt;"> 空闲分区以容量递增次序排列 </td> 
> <td style="vertical-align:top;width:4cm;"> 会有更多的大分区被保留下来，更能满足大进程需求 </td> 
> <td style="vertical-align:top;width:94.65pt;"> 会产生很多太小的、难以利用的碎片：算法开销大，回收分区后可能需要对空闲分区队列重新排序 </td> 
> </tr> 
> <tr> 
> <td style="vertical-align:top;width:55.05pt;"> 最坏适应算法 </td> 
> <td style="vertical-align:top;width:3cm;"> 优先使用更大的分区，以防止产生太小的不可用碎片 </td> 
> <td style="vertical-align:top;width:77.95pt;"> 空闲分区以容量递减次序排列 </td> 
> <td style="vertical-align:top;width:4cm;"> 可以减少难以利用的小碎片 </td> 
> <td style="vertical-align:top;width:94.65pt;"> 大分区容易被用完，不利于大进程：算法开销大（原因同上） </td> 
> </tr> 
> <tr> 
> <td style="vertical-align:top;width:55.05pt;"> 临近适应算法 </td> 
> <td style="vertical-align:top;width:3cm;"> 由首次适应算法演变而来，每次从上次查找结束的位置开始查找 </td> 
> <td style="vertical-align:top;width:77.95pt;"> 空闲分区以地址递增次序排列（可排列成循环链表） </td> 
> <td style="vertical-align:top;width:4cm;"> 不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法） </td> 
> <td style="vertical-align:top;width:94.65pt;"> 会使高地址的大分区也被用完 </td> 
> </tr> 
> </tbody> 
> </table>

[_1_C_FCFS_SJF_HRRN]: https://blog.csdn.net/weixin_44949135/article/details/116242551
[_2_ C]: https://blog.csdn.net/weixin_44949135/article/details/116539292
[_3_ Python]: https://blog.csdn.net/weixin_44949135/article/details/116755819
[_4_ C]: https://blog.csdn.net/weixin_44949135/article/details/116850356
[20210613101911131.png]: https://img-blog.csdnimg.cn/20210613101911131.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210613102131625.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1]: /images/20221021/cb46804184824ba68e9c48fb5334eefe.png