操作系统 实验3【动态分区存储管理】
目錄
一、實(shí)驗(yàn)?zāi)康?#xff08;目的與任務(wù)）
二、實(shí)驗(yàn)內(nèi)容（內(nèi)容、要求與安排方式）
三、實(shí)驗(yàn)代碼
①創(chuàng)建表示分區(qū)的類，類包含：分區(qū)ID、起始地址、結(jié)束地址、分區(qū)長度、分區(qū)狀態(tài)
②導(dǎo)入python模塊，方便拷貝分區(qū)對象
③編寫表示分區(qū)狀態(tài)的函數(shù)
④編寫冒泡排序函數(shù)
⑤編寫首次適應(yīng)算法（First Fit）函數(shù)
⑥編寫最佳適應(yīng)算法（Best Fit）函數(shù)
⑦回收內(nèi)存（作業(yè)）函數(shù)
⑧編寫主函數(shù)
完整實(shí)驗(yàn)代碼
四、實(shí)驗(yàn)結(jié)果
五、實(shí)驗(yàn)總結(jié)
一、實(shí)驗(yàn)?zāi)康?#xff08;目的與任務(wù)）
熟悉并掌握動態(tài)分區(qū)分配的各種算法。
熟悉并掌握動態(tài)分區(qū)中分區(qū)回收的各種情況，并能夠?qū)崿F(xiàn)分區(qū)合并。
二、實(shí)驗(yàn)內(nèi)容（內(nèi)容、要求與安排方式）
用高級語言模擬實(shí)現(xiàn)動態(tài)分區(qū)存儲管理，要求：
? ? ? （2）作業(yè)不能同名，但是刪除后可以再用這個名字；
? ? ? （3）作業(yè)空間回收是輸入作業(yè)名，回收相應(yīng)的空間，如果這個作業(yè)名不存在，也要有相應(yīng)的提示。
三、實(shí)驗(yàn)代碼
①創(chuàng)建表示分區(qū)的類，類包含：分區(qū)ID、起始地址、結(jié)束地址、分區(qū)長度、分區(qū)狀態(tài)
class?Memory(object):
????def?__init__(self,?start,?end,?length,?state=1,?ID=0):
????????self.Id?=?ID??##ID為0是未分配，其余為任務(wù)編號
????????self.start?=?start
????????self.end?=?end
????????self.length?=?length
????????self.state?=?state??#?state為1：內(nèi)存未分配
②導(dǎo)入python模塊，方便拷貝分區(qū)對象
import?copy?#?導(dǎo)入python模塊，copy僅拷貝對象本身
③編寫表示分區(qū)狀態(tài)的函數(shù)
def?show_memory(list):
????print("分配狀態(tài)????分區(qū)號????起始地址???終止地址??分區(qū)大小")
????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))
④編寫冒泡排序函數(shù)
##冒泡排序
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
⑤編寫首次適應(yīng)算法（First Fit）函數(shù)
#?首次適應(yīng)算法（First?Fit）
def?FF(work_id,?work_length,?list):
????for?i?in?list:
????????if?i.Id?==?work_id:
????????????print('作業(yè)已存在！')
????????????return
????for?i?in?range(0,?len(list)):
????????p?=?list[i]
????????if?p.state?==?1?and?p.length?>?work_length:??#?p是當(dāng)前未分配內(nèi)存的大小
????????????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("內(nèi)存空間不足！")
⑥編寫最佳適應(yīng)算法（Best Fit）函數(shù)
##最佳適應(yīng)算法（Best?Fit）
def?BF(work_id,?work_length,?li):
????for?i?in?li:
????????if?i.Id?==?work_id:
????????????print('作業(yè)已存在！')
????????????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("內(nèi)存空間不足！")
????????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
?
⑦回收內(nèi)存（作業(yè)）函數(shù)
##回收內(nèi)存（作業(yè)）函數(shù)
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)
⑧編寫主函數(shù)
if?__name__?==?'__main__':
????print("輸入內(nèi)存大小：")
????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('請輸入想要執(zhí)行的功能：')
????????if?select?==?'5':
????????????break
????????elif?select?==?'1':
????????????print("輸入內(nèi)存大小：")
????????????size?=?int(input())
????????????a?=?Memory(0,?size?-?1,?size,?state=1,?ID=0)
????????????b?=?[]
????????????b.append(a)
????????elif?select?==?'2':
????????????print("1.首次適應(yīng)算法：FF")
????????????print("2.最佳適應(yīng)算法：BF")
????????????x?=?input("請輸入分配執(zhí)行的算法：")
????????????x?=?float(x)
????????????repit?=?'Y'
????????????while?(repit?==?'Y'):
????????????????if?x?==?1:
????????????????????work_size?=?input('請輸入作業(yè)id和大小：').split()
????????????????????FF(work_size[0],?int(work_size[1]),?b)
????????????????????repit?=?input('是否繼續(xù)（Y/N）：')
????????????????elif?x?==?2:
????????????????????work_size?=?input('請輸入作業(yè)id和大小：').split()
????????????????????BF(work_size[0],?int(work_size[1]),?b)
????????????????????repit?=?input('是否繼續(xù)（Y/N）：')
????????elif?select?==?'3':
????????????id_delete?=?input('請輸入刪除作業(yè)id：')
????????????free1(id_delete,?b)
????????else:
????????????show_memory(b)
完整實(shí)驗(yàn)代碼
import copy # 導(dǎo)入python模塊，copy僅拷貝對象本身# 創(chuàng)建表示分區(qū)的類，類包含：分區(qū)ID、起始地址、結(jié)束地址、分區(qū)長度、分區(qū)狀態(tài) class Memory(object):def __init__(self, start, end, length, state=1, ID=0): # __init__()方法是一種特殊的方法，被稱為類的初始化方法，當(dāng)創(chuàng)建這個類的實(shí)例時就會調(diào)用該方法# self代表類的實(shí)例，self在定義類的方法時是必須有的，雖然在調(diào)用時不必傳入相應(yīng)的參數(shù)self.Id = ID ##ID為0是未分配，其余為任務(wù)編號self.start = startself.end = endself.length = lengthself.state = state # state為1：內(nèi)存未分配# 編寫表示分區(qū)狀態(tài)的函數(shù) def show_memory(list):print("分配狀態(tài) 分區(qū)號 起始地址 終止地址 分區(qū)大小")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))# 首次適應(yīng)算法（First Fit） def FF(work_id, work_length, list):for i in list:if i.Id == work_id:print('作業(yè)已存在！')returnfor i in range(0, len(list)):p = list[i]if p.state == 1 and p.length > work_length: # p是當(dāng)前未分配內(nèi)存的大小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)returnif p.state == 1 and p.length == work_length:p.state = 0show_memory(list)returnprint("內(nèi)存空間不足！")# 回收內(nèi)存（作業(yè)）函數(shù) def free1(work_id, li):for i in range(0, len(li)):p = li[i]if p.Id == work_id:p.state = 1target = ip.Id = 0break# 向前合并空閑塊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# 最佳適應(yīng)算法（Best Fit） def BF(work_id, work_length, li):for i in li:if i.Id == work_id:print('作業(yè)已存在！')returnq = copy.copy(li)q = bubble_sort(q) # 從小到大排序,給所有已分配和未分配的排序s = -1ss12 = -1for 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.startif s == -1 and ss12 == -1:print("內(nèi)存空間不足！")returnfor 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)returnelif p.start == ss12:p.state = 0show_memory(li)return# 主函數(shù) if __name__ == '__main__':print("輸入內(nèi)存大小：")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('請輸入想要執(zhí)行的功能：')if select == '5':breakelif select == '1':print("輸入內(nèi)存大小：")size = int(input())a = Memory(0, size - 1, size, state=1, ID=0)b = []b.append(a)elif select == '2':print("1.首次適應(yīng)算法：FF")print("2.最佳適應(yīng)算法：BF")x = input("請輸入分配執(zhí)行的算法：")x = float(x)repit = 'Y'while (repit == 'Y'):if x == 1:work_size = input('請輸入作業(yè)id和大小：').split()FF(work_size[0], int(work_size[1]), b)repit = input('是否繼續(xù)（Y/N）：')elif x == 2:work_size = input('請輸入作業(yè)id和大小：').split()BF(work_size[0], int(work_size[1]), b)repit = input('是否繼續(xù)（Y/N）：')elif select == '3':id_delete = input('請輸入刪除作業(yè)id：')free1(id_delete, b)else:show_memory(b)四、實(shí)驗(yàn)結(jié)果
BF算法有一點(diǎn)小毛病兒：兩個相同的分區(qū)，比如2個20，這個BF是從末尾地址開始分配的；不能這樣寫，應(yīng)該從低地址開始分配。
? ?
五、實(shí)驗(yàn)總結(jié)
動態(tài)分區(qū)分配算法包括如下4種算法：首次適應(yīng)算法（First Fit）、最佳適應(yīng)算法（Best Fit）、最壞適應(yīng)算法（Worst Fit）、臨近適應(yīng)算法（Next Fit）。
動態(tài)分區(qū)管理方式，在初始時不將主存劃分區(qū)域，而是把占用區(qū)域外的空間看作一個大的空閑區(qū)。當(dāng)作業(yè)要求裝入主存時，根據(jù)作業(yè)的大小查詢主存內(nèi)各空閑區(qū)的狀態(tài)，按照特定的算法選擇一個合適的空閑區(qū)，按作業(yè)大小劃分出一個分區(qū)并裝入該作業(yè)，剩下的區(qū)域作為新的空閑區(qū)。
當(dāng)作業(yè)執(zhí)行完畢后，所占用的主存空間將被回收，成為一個空閑區(qū)；如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個空閑區(qū)。
?? 通過本次實(shí)驗(yàn)，我對動態(tài)分區(qū)分配算法有了更深的理解，將4種算法的特點(diǎn)整理如下：
| 算法 | 算法思想 | 分區(qū)排列順序 | 優(yōu)點(diǎn) | 缺點(diǎn) |
| 首次適應(yīng)算法 | 從頭到尾尋找合適的分區(qū) | 空閑分區(qū)以地址遞增次序排列 | 綜合看，首次適應(yīng)算法性能最好。算法開銷小，回收分區(qū)后，一般不需要對空閑分區(qū)隊(duì)列重新排序 | 略！ |
| 最佳適應(yīng)算法 | 優(yōu)先使用更小的分區(qū)，以保留更多的大分區(qū) | 空閑分區(qū)以容量遞增次序排列 | 會有更多的大分區(qū)被保留下來，更能滿足大進(jìn)程需求 | 會產(chǎn)生很多太小的、難以利用的碎片：算法開銷大，回收分區(qū)后可能需要對空閑分區(qū)隊(duì)列重新排序 |
| 最壞適應(yīng)算法 | 優(yōu)先使用更大的分區(qū)，以防止產(chǎn)生太小的不可用碎片 | 空閑分區(qū)以容量遞減次序排列 | 可以減少難以利用的小碎片 | 大分區(qū)容易被用完，不利于大進(jìn)程：算法開銷大（原因同上） |
| 臨近適應(yīng)算法 | 由首次適應(yīng)算法演變而來，每次從上次查找結(jié)束的位置開始查找 | 空閑分區(qū)以地址遞增次序排列（可排列成循環(huán)鏈表） | 不用每次都從低地址的小分區(qū)開始檢索。算法開銷小（原因同首次適應(yīng)算法） | 會使高地址的大分區(qū)也被用完 |
總結(jié)
以上是生活随笔為你收集整理的操作系统 实验3【动态分区存储管理】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python常见的数据类型【数字、布尔、
- 下一篇： 考研经验交流会【高分前辈】【350分+】