操作系統(tǒng)實驗四報告-主存空間分配和回收(含源碼)

1 計算機 學院 計算機科學與技術 專業(yè) 班學號 姓名 教師評定 實驗題目 主存空間的分配和回收 一 實驗目的一 實驗目的 熟悉主存的分配與回收 理解在不同的存儲管理方式下 如何實現(xiàn)主存空間的分配與 回收 掌握動態(tài)分區(qū)分配方式中的數(shù)據(jù)結構和分配算法及動態(tài)分區(qū)存儲管理方式及其實現(xiàn) 過程 二 實驗內(nèi)容和要求二 實驗內(nèi)容和要求 主存的分配和回收的實現(xiàn)是與主存儲器的管理方式有關的 所謂分配 就是解決多道 作業(yè)或多進程如何共享主存空間的問題 所謂回收 就是當作業(yè)運行完成時將作業(yè)或進程 所占的主存空間歸還給系統(tǒng) 可變分區(qū)管理是指在處理作業(yè)過程中建立分區(qū) 使分區(qū)大小正好適合作業(yè)的需求 并 且分區(qū)個數(shù)是可以調(diào)整的 當要裝入一個作業(yè)時 根據(jù)作業(yè)需要的主存量查看是否有足夠 的空閑空間 若有 則按需要量分割一個分區(qū)分配給該作業(yè) 若無 則作業(yè)不能裝入 作 業(yè)等待 隨著作業(yè)的裝入 完成 主存空間被分成許多大大小小的分區(qū) 有的分區(qū)被作業(yè) 占用 而有的分區(qū)是空閑的 實驗要求使用可變分區(qū)存儲管理方式 分區(qū)分配中所用的數(shù)據(jù)結構采用空閑分區(qū)表和 空閑分區(qū)鏈來進行 分區(qū)分配中所用的算法采用首次適應算法 最佳適應算法 最差適應 算法三種算法來實現(xiàn)主存的分配與回收 同時 要求設計一個實用友好的用戶界面 并顯 示分配與回收的過程 同時要求設計一個實用友好的用戶界面 并顯示分配與回收的過程 三 實驗主要儀器設備和材料三 實驗主要儀器設備和材料 實驗環(huán)境 硬件環(huán)境 IBM PC 或兼容機 軟件環(huán)境 VC 6 0 四 實驗原理及設計分析四 實驗原理及設計分析 某系統(tǒng)采用可變分區(qū)存儲管理 在系統(tǒng)運行當然開始 假設初始狀態(tài)下 可用的內(nèi)存 空間為 640KB 存儲器區(qū)被分為操作系統(tǒng)分區(qū) 40KB 和可給用戶的空間區(qū) 600KB 作業(yè) 1 申請 130KB 作業(yè) 2 申請 60KB 作業(yè) 3 申請 100KB 作業(yè) 2 釋放 60KB 作業(yè) 4 申請 200KB 作業(yè) 3 釋放 100KB 作業(yè) 1 釋放 130KB 作業(yè) 5 申請 140KB 作業(yè) 6 申請 60KB 作業(yè) 7 申請 50KB 當作業(yè) 1 進入內(nèi)存后 分給作業(yè) 1 130KB 隨著作業(yè) 1 2 3 的進入 分別分配 60KB 100KB 經(jīng)過一段時間的運行后 作業(yè) 2 運行完畢 釋放所占內(nèi)存 此時 作業(yè) 4 進 入系統(tǒng) 要求分配 200KB 內(nèi)存 作業(yè) 3 1 運行完畢 釋放所占內(nèi)存 此時又有作業(yè) 5 申請 2 140KB 作業(yè) 6 申請 60KB 作業(yè) 7 申請 50KB 為它們進行主存分配和回收 1 采用可變分區(qū)存儲管理 使用空閑分區(qū)鏈實現(xiàn)主存分配和回收 空閑分區(qū)鏈 使用鏈指針把所有的空閑分區(qū)鏈成一條鏈 為了實現(xiàn)對空閑分區(qū)的分配和鏈 接 在每個分區(qū)的起始部分設置狀態(tài)位 分區(qū)的大小和鏈接各個分區(qū)的前向指針 由狀態(tài) 位指示該分區(qū)是否分配出去了 同時 在分區(qū)尾部還設置有一后向指針 用來鏈接后面的 分區(qū) 分區(qū)中間部分是用來存放作業(yè)的空閑內(nèi)存空間 當該分區(qū)分配出去后 狀態(tài)位就由 0 置為 1 設置一個內(nèi)存空閑分區(qū)鏈 內(nèi)存空間分區(qū)通過空閑分區(qū)鏈來管理 在進行內(nèi)存分配時 系統(tǒng)優(yōu)先使用空閑低端的空間 設計一個空閑分區(qū)說明鏈 設計一個某時刻主存空間占用情況表 作為主存當前使用 基礎 初始化空間區(qū)和已分配區(qū)說明鏈的值 設計作業(yè)申請隊列以及作業(yè)完成后釋放順序 實現(xiàn)主存的分配和回收 要求每次分配和回收后顯示出空閑內(nèi)存分區(qū)鏈的情況 把空閑區(qū) 說明鏈的變化情況以及各作業(yè)的申請 釋放情況顯示打印出來 2 采用可變分區(qū)存儲管理 分別采用首次適應算法 最佳適應算法和最壞適應算法實 現(xiàn)主存分配和回收 3 主存空間分配 1 首次適應算法 在該算法中 把主存中所有空閑區(qū)按其起始地址遞增的次序排列 在為作業(yè)分配 存儲空間時 從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找 直到找到第一個能 滿足要求的空閑區(qū) 從中劃出與請求的大小相等的存儲空間分配給作業(yè) 余下的空閑 區(qū)仍留在空閑區(qū)鏈中 2 最佳適應算法 在該算法中 把主存中所有空閑區(qū)按其起始地址遞增的次序排列 在為作業(yè)分配 存儲空間時 從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找 直到找到一個能滿 足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都小 從中劃出與請求的 大小相等的存儲空間分配給作業(yè) 余下的空閑區(qū)仍留在空閑區(qū)鏈中 3 最壞適應算法 在該算法中 把主存中所有空閑區(qū)按其起始地址遞增的次序排列 在為作業(yè)分配 存儲空間時 從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找 直到找到一個能滿 足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都大 從中劃出與請求的 大小相等的存儲空間分配給作業(yè) 余下的空閑區(qū)仍留在空閑區(qū)鏈中 4 主存空間回收 當一個作業(yè)執(zhí)行完成撤離時 作業(yè)所占的分區(qū)應該歸還給系統(tǒng) 歸還的分區(qū)如果與 其它空閑區(qū)相鄰 則應合成一個較大的空閑區(qū) 登記在空閑區(qū)說明鏈中 此時 相鄰空閑 區(qū)的合并問題 要求考慮四種情況 1 釋放區(qū)下鄰空閑區(qū) 低地址鄰接 2 釋放區(qū)上鄰空閑區(qū) 高地址鄰接 3 釋放區(qū)上下都與空閑區(qū)鄰接 4 釋放區(qū)上下鄰都與空閑區(qū)不鄰接 五 程序流程圖五 程序流程圖 main 函數(shù)里的流程圖 3 初始化 first 和 end 整理分區(qū)序號 顯示空閑分區(qū)鏈 選擇算法 a a 1 首次適應算法a 2 最佳適應算法a 3 最壞適應算法 選擇操作 i i 1 分配空間函數(shù) ai 0 退出程序i 2 回收空間函 數(shù) 結束 分配空間里的流程圖 4 p data length request 分配不成功 分配空間函數(shù) a 1a 2a 3 輸入申請內(nèi)存大 小 按順序找空閑塊 初始化 q 使它指向空 閑塊中長度小的一塊 輸入申請內(nèi)存 大小 初始化 q 使它指向空 閑塊中長度大的一塊 p data length request p 的狀態(tài)為已分配 剩下 p data length request 輸入申請內(nèi)存 大小 Y Y N N 返回到整理分區(qū)序號 回收空間里的流程圖 5 p 的狀態(tài) 改為空閑 回收 p p 的前一個為 first p 的后一 個是 end p 的后一 個狀態(tài)空 與后面空閑 塊相連 將 p 的 狀態(tài)改為 空閑 將 p 的狀態(tài)改 為空閑 回收空間函數(shù) p 的后一 個是 end Y N Y N YN p 的前一 個狀態(tài)空 p 的前一 個狀態(tài)空 p 的后一 個狀態(tài)空 p 的后一 個狀態(tài)空 p 的后一 個狀態(tài)空 p 的后一 個狀態(tài)空 Y Y Y N N N 與前面空 閑塊相連 p 的狀態(tài) 改為空閑 與前面空 閑塊相連 與后面空閑 塊相連 Y N 返回到整理分區(qū)序號 六 相關數(shù)據(jù)結構及關鍵函數(shù)說明六 相關數(shù)據(jù)結構及關鍵函數(shù)說明 本程序采用了一個 struct free table 數(shù)據(jù)結構 里面包含分區(qū)序號 num 起始地址 address 分區(qū)長度 length 和分區(qū)狀態(tài) state 還用了線性表的雙性鏈表存儲結構 struct Node 里面包含前區(qū)指針 prior 和后繼指針 next 一開始定義一條 含有 first 和 end 的鏈 用開始指針和尾指針開創(chuàng)空間鏈表 然后分別按三種算法進行分配和 6 回收 在該程序中關鍵函數(shù)有 sort allocation recovery 和 First fit Best fit Worst fit 其中 sort 函數(shù)是用來整理分區(qū)序號的 如在刪序號 3 時 她與前面序號 2 相連在一起了 然后序號 2 中的長度總滿足申請的內(nèi)存大小 就會在序號 2 中分配 然后序號在 2 的基礎上加 1 一直加 加到與原本序號 3 的下一個序號也就是 4 相等 這時 sort 就開始有明顯的工作了 allocation 是分配空間的 也是過渡到三 個算法中的 當三個算法中滿足或者不滿足分配請求 都會又返回值給 allocation recovery 是用來回收內(nèi)存的 里面包含了四種情況相連結果 即釋放區(qū)上與空閑區(qū)鄰接 釋放區(qū)下與空閑區(qū)鄰接 釋放區(qū)上下都與空閑區(qū)鄰接 釋放區(qū)上下都與空閑區(qū)不鄰接這四 種情況的結果 七 源代碼七 源代碼 include include define OK 1 完成 define ERROR 0 出錯 typedef int Status typedef struct free table 定義一個空閑區(qū)說明表結構 int num 分區(qū)序號 long address 起始地址 long length 分區(qū)大小 int state 分區(qū)狀態(tài) ElemType typedef struct Node 線性表的雙向鏈表存儲結構 ElemType data struct Node prior 前趨指針 struct Node next 后繼指針 Node LinkList LinkList first 頭結點 LinkList end 尾結點 int flag 記錄要刪除的分區(qū)序號 Status Initblock 開創(chuàng)帶頭結點的內(nèi)存空間鏈表 first LinkList malloc sizeof Node end LinkList malloc sizeof Node first prior NULL first next end 7 end prior first end next NULL end data num 1 end data address 40 end data length 600 end data state 0 return OK void sort 分區(qū)序號重新排序 Node p first next q q p next for p NULL p p next for q p next q q q next if p data num q data num q data num 1 顯示主存分配情況 void show int flag 0 用來記錄分區(qū)序號 Node p first p data num 0 p data address 0 p data length 40 p data state 1 sort printf n t t 主存空間分配情況 n printf n n printf 分區(qū)序號 t 起始地址 t 分區(qū)大小 t 分區(qū)狀態(tài) n n while p printf d t t d t t d p data num p data address p data length if p data state 0 printf t t 空閑 n n else printf t t 已分配 n n p p next 8 printf n n 首次適應算法 Status First fit int request 為申請作業(yè)開辟新空間且初始化 Node p first next LinkList temp LinkList malloc sizeof Node temp data length request temp data state 1 p data num 1 while p if p data state 0 return OK break else if p data state 0 temp next p temp data address p data address temp data num p data num p prior next temp p prior temp p data address temp data address temp data length p data length request p data num 1 return OK break p p next return ERROR 最佳適應算法 Status Best fit int request int ch 記錄最小剩余空間 Node p first 9 Node q NULL 記錄最佳插入位置 LinkList temp LinkList malloc sizeof Node temp data length request temp data state 1 p data num 1 while p 初始化最小空間和最佳位置 if p data state 0 ch p data length request else if q data length p data length q p ch p data length request p p next if q NULL return ERROR 沒有找到空閑塊 else if q data length request q data state 1 return OK else temp prior q prior temp next q temp data address q data address temp data num q data num q prior next temp q prior temp q data address request q data length ch q data num 1 return OK return OK 10 最差適應算法 Status Worst fit int request int ch 記錄最大剩余空間 Node p first next Node q NULL 記錄最佳插入位置 LinkList temp LinkList malloc sizeof Node temp data length request temp data state 1 p data num 1 while p 初始化最大空間和最佳位置 if p data state 0 ch p data length request else if q data length data length q p ch p data length request p p next if q NULL return ERROR 沒有找到空閑塊 else if q data length request q data length 1 return OK else temp prior q prior temp next q temp data address q data address temp data num q data num q prior next temp q prior temp q data address request q data length ch 11 q data num 1 return OK return OK 分配主存 Status allocation int a int request 申請內(nèi)存大小 printf 請輸入申請分配的主存大小 單位 KB scanf d if requestnext if q p 12 if q prior data state 0 q prior next q next q next prior q prior q q prior q data state 0 q data num flag 1 if q prior data state 0 q next q next next q next next prior q q data state 0 q data num flag if q prior data state 0 q prior next q next q next prior q prior q q prior q data state 0 q data num flag 1 if q prior data state 0 return OK Status deal2 Node p 處理回收空間 Node q first for q NULL q q next if q p if q prior data state 0 q prior next q next q next prior q prior q p prior q data state 0 q data num flag 1 if q prior data state 0 if q prior data state 0 q prior next q next q next prior q prior q q prior q data state 0 q data num flag 1 if q prior data state 0 return OK 主存回收 Status recovery int flag Node p first for p NULL p p next if p data num flag if p prior first if p next end 當前 P 指向的下一個不是最后一個時 if p next data state 0 與后面的空閑塊相連 p data length p next data length 14 p next next prior p p next p next next p data state 0 p data num flag else p data state 0 if p next end 當前 P 指向的下一個是最后一個時 p data state 0 結束 if p prior block first 的情況 else if p prior first if p next end deal1 p else deal2 p 結束 if p prior block first 的情況 結束 if p data num flag 的情況 printf t 回收成功 return OK 主函數(shù) void main int i 操作選擇標記 int a 算法選擇標記 printf n printf t t 用以下三種方法實現(xiàn)主存空間的分配 n printf t 1 首次適應算法 t 2 最佳適應算法 t 3 最差適應算法 n printf n printf n printf 請輸入所使用的內(nèi)存分配算法 scanf d while a3 printf 輸入錯誤 請重新輸入所使用的內(nèi)存分配算法 n 15 scanf d switch a case 1 printf n t 使用首次適應算法 n break case 2 printf n t 使用最佳適應算法 n break case 3 printf n t 使用最壞適應算法 n break Initblock 開創(chuàng)空間表 while 1 show printf t1 分配內(nèi)存 t2 回收內(nèi)存 t0 退出 n printf 請輸入您的操作 scanf d if i 1 allocation a 分配內(nèi)存 else if i 2 內(nèi)存回收 printf 請輸入您要釋放的分區(qū)號 scanf d recovery flag else if i 0 printf n 退出程序 n break 退出 else 輸入操作有誤 printf 輸入有誤 請重試 continue 八 執(zhí)行結果和結果分析八 執(zhí)行結果和結果分析 16 初始化首次適應算法 當作業(yè) 1 2 3 順利分配內(nèi)存空間后 回收序號 2 里面的內(nèi)存 17 分配作業(yè) 4 回收序號 3 里面的內(nèi)存 與上鄰序號 2 相連了 18 回收序號 1 里的內(nèi)存 與下鄰序號 2 相連了 繼續(xù)分配 會發(fā)現(xiàn)總是按順序查找滿足要求的第一個空閑塊 一旦發(fā)現(xiàn)就