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

[TOC]

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主窗口类

python class mainWindow(object):

```python

属性

self.centralwidget = QtWidgets.QWidget(main_window)# 中心控件 self.rb_ff = QRadioButton("FirstFit", main_window)#首次适应单选按钮 self.rb_bf = QRadioButton("BestFit", main_window)#最佳适应单选按钮 self.big_btn = QtWidgets.QPushButton(main_window)#整块内存 self.line_edit = QtWidgets.QLineEdit(main_window)#进程号输入框 self.line_edit_2 = QtWidgets.QLineEdit(main_window)#进程大小输入框 self.push_btn = QtWidgets.QPushButton("确定", main_window)#进程确认按钮 self.line_edit_3 = QtWidgets.QLineEdit(main_window)#删除的进程号输入框 self.del_btn= QtWidgets.QPushButton("del", main_window)#删除按钮 self.clear_btn = QtWidgets.QPushButton('Reset', main_window)#清除所有进程按钮 self.free_title=QLabel("空闲分区链", main_window)#空闲分区链文本 self.free_label=QLabel("(0,640)", main_window)#空闲分区链展示

方法

def setup_ui(self, main_window):#初始化UI ```

UI主窗口逻辑实现类

python class Window(QtWidgets.QMainWindow):

```python

属性

self.ui = mainWindow()#基本ui self.isbestFit=False#选择两种分配模式之一 self.free_link=DList()#用链表实现的空闲分区链 self.dict = {}#记录各进程信息的python字典 ```

```python

方法

def first_fit_select(self): # 选中首次适应算法 def best_fit_select(self): # 选中最佳适应算法 def add_node(self,p_num,p_size): # 添加空闲分区链的节点 def del_node(self,p_num): # 删除空闲分区链的节点 def clear(self): # 清空进程 def find_first_node(self,size): # 寻找 first fit def find_best_node(self,size): # 寻找 best fit def word_get(self): # 获取进程号和进程大小 def del_get(self): # 获取要删除的进程号 def display_free(self): # 展示空闲分区链 ```

2.2 实现

2.2.1算法实现

首次适应算法

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

最佳适应算法

python def find_best_node(self,size): # 寻找 best fit p = self.free_link.head # 令p为链头 best=None # best最佳适应的空闲区 min=cap+1 # 初始化所需内存大小空闲分区的最小差距 while p: # 遍历空闲分区链 if p.size>size: # 如果放得下 if min>p.size-size: # 如果与大小相差更小 min=p.size-size # 更新大小差距 best=p # 更新最佳空闲区 elif p.size==size: # 如果大小完全相等即为最佳分配 if p.prev: # 对空闲分区链进行更新 p.prev.next = p.next p.next.prev = p.prev else: self.free_link.head = p.next self.display_free() return p.address # 返回进程应当存放在的首地址 p=p.next if best: # 如果存在满足要求的空闲分区 best.address+=size # 对空闲分区链进行更新 best.size-=size self.display_free() return best.address-size # 返回进程应当存放在的首地址 else: return -1

最佳适应算法

空闲分区块合并算法

```python def del_node(self,p_num): # 删除空闲分区链的节点 node=self.dict[p_num] node["btn"].setVisible(False) if node["address"]<self.free_link.head.address: if self.free_link.head.address==(node["address"] + node["size"]): self.free_link.head.address=node["address"] self.free_link.head.size+=node["size"] else: p=Node(node["address"],node["size"]) self.free_link.head.prev=p p.next=self.free_link.head self.free_link.head=p else: q = self.free_link.head while q: if q.address < node["address"] and q.next and q.next.address > node["address"]: if q.address+q.size==node["address"]: q.size+=node["size"] if q.next: if (q.address+q.size)==q.next.address: q.size+=q.next.size q.next=q.next.next if q.next: q.next.prev=q

                self.display_free()
                return 0
            elif q.next and node["address"]+node["size"]==q.next.address:
                q.next.address-=node["size"]
                q.next.size+=node["size"]
                self.display_free()

                return 0
            else:
                n=Node(node["address"],node["size"])
                n.prev=q
                n.next=q.next
                q.next.prev=n
                q.next=n
        q=q.next
del self.dict[p_num]
self.display_free()

```

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