python实现操作系统大作业动态分区分配

路饼c

发布日期: 2020-05-30 13:44:09 浏览量: 136
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1. 使用说明

1.1 项目简介

  • 一个模拟动态分区分配方式的桌面程序

  • 开发环境 windows\python\pyQt5

1.2 项目目的

  • 设计相关数据结构、学习分配算法

  • 加深对动态分区存储管理方式及其实现过程的理解

1.3 项目功能要求

1.3.1 基本任务

  • 假设初始态下,可用内存空间为640K,并有下列请求序列,请分别用首次适应算法和最佳适应算法进行内存块的分配和回收,并显示出每次分配和回收后的空闲分区链的情况来。

2. 设计与实现

2.1 设计

2.1.1开发环境及语言

  • 开发环境:pycharm

  • 开发语言:python

本项目采用PyQt5实现图形化用户界面,达到可视化的目的。

2.1.2 算法设计

首次适应算法(First Fit)

该算法从空闲分区链首开始查找,直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链中。

  • 特点: 该算法倾向于使用内存中低地址部分的空闲区,在高地址部分的空闲区很少被利用,从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件

  • 缺点:低地址部分不断被划分,留下许多难以利用、很小的空闲区,而每次查找又都从低地址部分开始,会增加查找的开销

最佳适应算法(Best Fit)

该算法总是把既能满足要求,又是最小的空闲分区分配给作业。为了加速查找,该算法要求将所有的空闲区按其大小排序后,以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区,必然是最优的。孤立地看,该算法似乎是最优的,但事实上并不一定。因为每次分配后剩余的空间一定是最小的,在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序,这也带来了一定的开销。

  • 特点:每次分配给文件的都是最合适该文件大小的分区

  • 缺点:内存中留下许多难以利用的小的空闲区

2.1.3 数据结构设计

采用采用链表结构模拟空闲分区链。

2.1.4 类结构设计

UI主窗口类

  1. class mainWindow(object):
  1. # 属性
  2. self.centralwidget = QtWidgets.QWidget(main_window)# 中心控件
  3. self.rb_ff = QRadioButton("FirstFit", main_window)#首次适应单选按钮
  4. self.rb_bf = QRadioButton("BestFit", main_window)#最佳适应单选按钮
  5. self.big_btn = QtWidgets.QPushButton(main_window)#整块内存
  6. self.line_edit = QtWidgets.QLineEdit(main_window)#进程号输入框
  7. self.line_edit_2 = QtWidgets.QLineEdit(main_window)#进程大小输入框
  8. self.push_btn = QtWidgets.QPushButton("确定", main_window)#进程确认按钮
  9. self.line_edit_3 = QtWidgets.QLineEdit(main_window)#删除的进程号输入框
  10. self.del_btn= QtWidgets.QPushButton("del", main_window)#删除按钮
  11. self.clear_btn = QtWidgets.QPushButton('Reset', main_window)#清除所有进程按钮
  12. self.free_title=QLabel("空闲分区链", main_window)#空闲分区链文本
  13. self.free_label=QLabel("(0,640)", main_window)#空闲分区链展示
  14. # 方法
  15. def setup_ui(self, main_window):#初始化UI

UI主窗口逻辑实现类

  1. class Window(QtWidgets.QMainWindow):
  1. # 属性
  2. self.ui = mainWindow()#基本ui
  3. self.isbestFit=False#选择两种分配模式之一
  4. self.free_link=DList()#用链表实现的空闲分区链
  5. self.dict = {}#记录各进程信息的python字典
  1. #方法
  2. def first_fit_select(self): # 选中首次适应算法
  3. def best_fit_select(self): # 选中最佳适应算法
  4. def add_node(self,p_num,p_size): # 添加空闲分区链的节点
  5. def del_node(self,p_num): # 删除空闲分区链的节点
  6. def clear(self): # 清空进程
  7. def find_first_node(self,size): # 寻找 first fit
  8. def find_best_node(self,size): # 寻找 best fit
  9. def word_get(self): # 获取进程号和进程大小
  10. def del_get(self): # 获取要删除的进程号
  11. def display_free(self): # 展示空闲分区链

2.2 实现

2.2.1算法实现

首次适应算法

  1. def find_first_node(self,size): # 寻找 first fit
  2. p=self.free_link.head
  3. while p: # 遍历空闲分区链直到找到第一个符合要求的空闲区域
  4. if p.size>size: # 如果满足要求 且略大
  5. p.address+=size # 缩小空闲区域让给新进程使用
  6. # print(p.address)
  7. p.size-=size
  8. # print(p.address)
  9. self.display_free() # 展示新的空闲分区链
  10. return p.address-size
  11. elif p.size==size: # 如果大小相等 则全部分配出去 删除空闲分区链中该节点
  12. if p.prev: # 如果不是空闲分区链中第一个节点
  13. p.prev.next=p.next
  14. p.next.prev=p.prev
  15. else: self.free_link.head=p.next # 如果是第一个节点 则需修改链头
  16. # print(p.address)
  17. self.display_free() # 展示新的空闲分区链
  18. return p.address
  19. p=p.next
  20. return -1

最佳适应算法

  1. def find_best_node(self,size): # 寻找 best fit
  2. p = self.free_link.head # 令p为链头
  3. best=None # best最佳适应的空闲区
  4. min=cap+1 # 初始化所需内存大小空闲分区的最小差距
  5. while p: # 遍历空闲分区链
  6. if p.size>size: # 如果放得下
  7. if min>p.size-size: # 如果与大小相差更小
  8. min=p.size-size # 更新大小差距
  9. best=p # 更新最佳空闲区
  10. elif p.size==size: # 如果大小完全相等 即为最佳分配
  11. if p.prev: # 对空闲分区链进行更新
  12. p.prev.next = p.next
  13. p.next.prev = p.prev
  14. else:
  15. self.free_link.head = p.next
  16. self.display_free()
  17. return p.address # 返回进程应当存放在的首地址
  18. p=p.next
  19. if best: # 如果存在满足要求的空闲分区
  20. best.address+=size # 对空闲分区链进行更新
  21. best.size-=size
  22. self.display_free()
  23. return best.address-size # 返回进程应当存放在的首地址
  24. else: return -1

最佳适应算法

  1. def find_best_node(self,size): # 寻找 best fit
  2. p = self.free_link.head # 令p为链头
  3. best=None # best最佳适应的空闲区
  4. min=cap+1 # 初始化所需内存大小空闲分区的最小差距
  5. while p: # 遍历空闲分区链
  6. if p.size>size: # 如果放得下
  7. if min>p.size-size: # 如果与大小相差更小
  8. min=p.size-size # 更新大小差距
  9. best=p # 更新最佳空闲区
  10. elif p.size==size: # 如果大小完全相等 即为最佳分配
  11. if p.prev: # 对空闲分区链进行更新
  12. p.prev.next = p.next
  13. p.next.prev = p.prev
  14. else:
  15. self.free_link.head = p.next
  16. self.display_free()
  17. return p.address # 返回进程应当存放在的首地址
  18. p=p.next
  19. if best: # 如果存在满足要求的空闲分区
  20. best.address+=size # 对空闲分区链进行更新
  21. best.size-=size
  22. self.display_free()
  23. return best.address-size # 返回进程应当存放在的首地址
  24. else: return -1

最佳适应算法

  1. def find_best_node(self,size): # 寻找 best fit
  2. p = self.free_link.head # 令p为链头
  3. best=None # best最佳适应的空闲区
  4. min=cap+1 # 初始化所需内存大小空闲分区的最小差距
  5. while p: # 遍历空闲分区链
  6. if p.size>size: # 如果放得下
  7. if min>p.size-size: # 如果与大小相差更小
  8. min=p.size-size # 更新大小差距
  9. best=p # 更新最佳空闲区
  10. elif p.size==size: # 如果大小完全相等 即为最佳分配
  11. if p.prev: # 对空闲分区链进行更新
  12. p.prev.next = p.next
  13. p.next.prev = p.prev
  14. else:
  15. self.free_link.head = p.next
  16. self.display_free()
  17. return p.address # 返回进程应当存放在的首地址
  18. p=p.next
  19. if best: # 如果存在满足要求的空闲分区
  20. best.address+=size # 对空闲分区链进行更新
  21. best.size-=size
  22. self.display_free()
  23. return best.address-size # 返回进程应当存放在的首地址
  24. else: return -1

最佳适应算法

  1. def find_best_node(self,size): # 寻找 best fit
  2. p = self.free_link.head # 令p为链头
  3. best=None # best最佳适应的空闲区
  4. min=cap+1 # 初始化所需内存大小空闲分区的最小差距
  5. while p: # 遍历空闲分区链
  6. if p.size>size: # 如果放得下
  7. if min>p.size-size: # 如果与大小相差更小
  8. min=p.size-size # 更新大小差距
  9. best=p # 更新最佳空闲区
  10. elif p.size==size: # 如果大小完全相等 即为最佳分配
  11. if p.prev: # 对空闲分区链进行更新
  12. p.prev.next = p.next
  13. p.next.prev = p.prev
  14. else:
  15. self.free_link.head = p.next
  16. self.display_free()
  17. return p.address # 返回进程应当存放在的首地址
  18. p=p.next
  19. if best: # 如果存在满足要求的空闲分区
  20. best.address+=size # 对空闲分区链进行更新
  21. best.size-=size
  22. self.display_free()
  23. return best.address-size # 返回进程应当存放在的首地址
  24. else: return -1

空闲分区块合并算法

  1. def del_node(self,p_num): # 删除空闲分区链的节点
  2. node=self.dict[p_num]
  3. node["btn"].setVisible(False)
  4. if node["address"]<self.free_link.head.address:
  5. if self.free_link.head.address==(node["address"] + node["size"]):
  6. self.free_link.head.address=node["address"]
  7. self.free_link.head.size+=node["size"]
  8. else:
  9. p=Node(node["address"],node["size"])
  10. self.free_link.head.prev=p
  11. p.next=self.free_link.head
  12. self.free_link.head=p
  13. else:
  14. q = self.free_link.head
  15. while q:
  16. if q.address < node["address"] and q.next and q.next.address > node["address"]:
  17. if q.address+q.size==node["address"]:
  18. q.size+=node["size"]
  19. if q.next:
  20. if (q.address+q.size)==q.next.address:
  21. q.size+=q.next.size
  22. q.next=q.next.next
  23. if q.next:
  24. q.next.prev=q
  25. self.display_free()
  26. return 0
  27. elif q.next and node["address"]+node["size"]==q.next.address:
  28. q.next.address-=node["size"]
  29. q.next.size+=node["size"]
  30. self.display_free()
  31. return 0
  32. else:
  33. n=Node(node["address"],node["size"])
  34. n.prev=q
  35. n.next=q.next
  36. q.next.prev=n
  37. q.next=n
  38. q=q.next
  39. del self.dict[p_num]
  40. self.display_free()

分别判断该位置前后的内存块是否是未被分配的空闲块,如果是则与刚被释放的空闲块合并。

2.3 运行截图

上传的附件 cloud_download 操作系统大作业动态分区分配.zip ( 8.08kb, 6次下载 )

发送私信

5
文章数
2
评论数
最近文章
eject