實驗五-動態(tài)分區(qū)存儲管理

1、實驗五-動態(tài)分區(qū)存儲管理實驗五 動態(tài)分區(qū)存儲管理一、實驗?zāi)康?深入了解采用動態(tài)分區(qū)存儲管理方式的內(nèi) 存分配回收的實現(xiàn)。 通過編寫和調(diào)試存儲管理的 模擬程序以加深對存儲管理方案的理解， 熟悉動 態(tài)分區(qū)存儲管理的內(nèi)存分配和回收。二、實驗內(nèi)容 編寫程序完成動態(tài)分區(qū)存儲管理方式的內(nèi) 存分配回收。具體包括：確定內(nèi)存空間分配表； 采用最優(yōu)適應(yīng)算法完成內(nèi)存空 間的分配和回收；編寫主函數(shù)對所做工作進行測 試。三、設(shè)計思路整體思路： 動態(tài)分區(qū)管理方式將內(nèi)存除操作系統(tǒng)占用區(qū) 域外的空間看成一個大的空閑區(qū)。 當作業(yè)要求裝 入內(nèi)存時，根據(jù)作業(yè)需要內(nèi)存空間的大小 查詢 內(nèi)存中的各個空閑區(qū)， 當從內(nèi)存空間中找到一個 大于

2、或等于該作業(yè)大小的內(nèi)存空閑區(qū)時， 選擇其 中一個空閑區(qū)， 按作業(yè)需求量劃出一個分區(qū)裝人 該作業(yè)， 作業(yè)執(zhí)行完后， 其所占的內(nèi)存分區(qū)被收 回，成為一個空閑區(qū)。 如果該空閑區(qū)的相鄰分區(qū) 也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個空 閑區(qū)。設(shè)計所采用的算法：采用最優(yōu)適應(yīng)算法， 每次為作業(yè)分配內(nèi)存時， 總是把既能滿足要求、 又是最小的空閑分區(qū)分配 給作業(yè)。 但最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個 分區(qū)可能只比作業(yè)所需求的長度略大一點的情 行，這時，空閑區(qū)分割后剩下的空閑區(qū)就很小以 致很難再使用， 降低了內(nèi)存的使用率。 為解決此 問題，設(shè)定一個限值 minsize ，如果空閑區(qū)的大 小減去作業(yè)需求長度得到的值小

3、于等于 minsize，不再將空閑區(qū)分成己分分區(qū)和空閑區(qū) 兩部分，而是將整個空閑區(qū)都分配給作業(yè)。內(nèi)存分配與回收所使用的結(jié)構(gòu)體： 為便于對內(nèi)存的分配和回收，建立兩張表記 錄內(nèi)存的使用情況。 一張為記錄作業(yè)占用分區(qū)的 “內(nèi)存分配表”，內(nèi)容包括分區(qū)起始地址、 長度、 作業(yè)名 /標志（為 0 時作為標志位表示空欄目） ； 一張為記錄空閑區(qū)的“空閑分區(qū)表” ，內(nèi)容包括分區(qū)起始地址、長度、標志（ 0 表空欄目， 1 表 未分配）。兩張表都采用順序表形式。關(guān)于分配留下的內(nèi)存小碎片問題： 當要裝入一個作業(yè)時，從“空閑分區(qū)表”中 查找標志為“ 1”（未分配）且滿足作業(yè)所需內(nèi)存 大小的最小空閑區(qū)， 若空閑區(qū)的大小

4、與作業(yè)所需 大小的差值小于或等于 minsize ，把該分區(qū)全部 分配給作業(yè)，并把該空閑區(qū)的標志改為“ 0”（空 欄目）。同時，在已分配區(qū)表中找到一個標志為 “0”的欄目登記新裝人作業(yè)所占用分區(qū)的起始 地址，長度和作業(yè)名。 若空閑區(qū)的大小與作業(yè)所 需大小的差值大于 minsize 。則把空閑區(qū)分成兩 部分，一部分用來裝入作業(yè)， 另外一部分仍為空 閑區(qū)。這時只要修改原空閑區(qū)的長度， 且把新裝 人的作業(yè)登記到已分配區(qū)表中。內(nèi)存的回收：在動態(tài)分區(qū)方式下回收內(nèi)存空間時， 先檢查 是否有與歸還區(qū)相鄰的空閑區(qū) （上鄰空閑區(qū)， 下 鄰空閑區(qū)）。若有，則將它們合件成一個空閑區(qū)。 程序?qū)崿F(xiàn)時， 首先將要釋放的作

5、業(yè)在 “內(nèi)存分配 表”中的記錄項的標志改為“ 0”（空欄目），然 后檢查“空閑區(qū)表”中標志為 1'（未分配）的欄目，查找是否有相鄰的空閑區(qū)，若有，將之合 并，并修改空閑區(qū)的起始地址和長度。四、數(shù)據(jù)結(jié)構(gòu)定義（ 1 ）已分配表的定義：structfloat address; / 已分分區(qū)起始地址 float length; / 已分分區(qū)長度，單位為 字節(jié)int flag; / 已分配區(qū)表登記欄標志， "0 表示空欄目，實驗中只支持一個字符的作業(yè)名used_tablen; / 已分配區(qū)表 （ 2 ）空閑分區(qū)表的定義：structfloat address; / 空閑區(qū)起始地址 fl

6、oat length; / 空閑區(qū)長度，單位為字 節(jié)int flag; / 空閑區(qū)表登記欄標志，用 "0" 表示空欄目，用 "1" 表示未分配free_tablem; / 空閑區(qū)表(3) 全局變量 float minsize=5; #define n 10 / 假定系統(tǒng)允許的最大 作業(yè)數(shù)量為 n#define m 10 / 假定系統(tǒng)允許的空閑 區(qū)表最大為 m五、源程序代碼#include <iostream.h> #include <iomanip.h>/ 全局變量 float minsize=5; int count1=0; i

7、nt count2=0;#defineM 10 / 假定系統(tǒng)允許的空閑區(qū)表最大為 m#defineN 10 / 假定系統(tǒng)允許的最大作業(yè)數(shù)量為 n / 已分配表的定義 structfloat address; float length;字節(jié)/ 已分分區(qū)起始地址/ 已分分區(qū)長度，單位為int flag;/ 已分配區(qū)表登記欄標志， "0"表示空欄目used_tableN;/ 已分配區(qū)表對象名/ 空閑區(qū)表的定義：structfloat address; / 空閑區(qū)起始地址 float length; / 空閑區(qū)長度，單位為字 節(jié)int flag; / 空閑區(qū)表登記欄標志，用 &qu

8、ot;0" 表示空欄目，用 "1" 表示未分配 free_tableM; / 空閑區(qū)表對象名/ 函數(shù)聲明 void initialize(void); int distribute(int, float); int recycle(int); void show();/ 初始化兩個表void initialize(void)int a;for(a=0; a<=N-1; a+) used_tablea.flag=0; / 已 分 配 表 的表項全部置為空表項free_table0.address=1000; free_table0.length=1024;fr

9、ee_table0.flag=1; / 空 閑 區(qū) 表 的表項全部為未分配/ 最優(yōu)分配算法實現(xiàn)的動態(tài)分區(qū)int distribute(int process_name, float need_length)int i, k=-1; /k 用于定位在空閑表中選擇 的未分配欄float ads, len; int count=0;i=0;w hile(i<=M-1) / 循環(huán)找到最佳 的空閑分區(qū)if(free_tablei.flag=1 && need_length <=free_tablei.length)count+;if(count=1|free_tablei.l

10、ength< free_tablek.length)k=i;i=i+1;if(k!=-1)if(free_tablek.length-need_leng th)<=minsize) / 整個分配free_tablek.flag=0;ads=free_tablek.address; len=free_tablek.length;else / 切割空閑區(qū)ads=free_tablek.address; len=need_length;free_tablek.address+=need_length;free_tablek.length-=need_length;i=0;/ 循環(huán)尋找內(nèi)存

11、分配表中標志為空欄 目的項while(used_tablei.flag!=0)i=i+1;if(i<=N-1) / 找到，在已分配區(qū)表 中登記一個表項used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=process_name;count1+;else / 已分配區(qū)表長度不足if(free_tablek.flag = 0) / 將已做的整個分配撤銷free_tablek.flag=1; free_tablek.address=ads; free_tablek.length=len;else/ 將已做的切割分配撤銷

12、free_tablek.address=ads;free_tablek.length+=len;cout<<" 內(nèi)存分配區(qū)已滿，分配失?。"return 0;elsecout <<" 無法為該作業(yè)找到合適分區(qū)！n"return 0;return process_name;int recycle(int process_name)int y=0; floatrecycle_address,recycle_length;int i, j, k; /j 欄是下鄰空閑區(qū)， k 欄 是上欄空閑區(qū)int x;/ 在內(nèi)存分配表中找到要回收的作

13、業(yè)while(y<=N-1&&used_tabley.fla g!=process_name) y=y+1;if(y<=N-1) / 找到作業(yè)后，將該欄的 標志置為 '0'recycle_address=used_tabley.address;recycle_length=used_tabley.length;used_tabley.flag=0;count2+;else / 未能找到作業(yè)，回收失cout<<" 該作業(yè)不存在！ n" return 0;j=k=-1;i=0; while(!(i>=M|(k!=-1

14、&&j!=-1) / 修改空閑分區(qū)表 if(free_tablei.flag=1) if(free_tablei.address+free _tablei.length)=recycle_a ddress)k=i; / 判斷是否有上鄰接if(recycle_address+recycle_length) =free_tablei.address)j=i; / / 判斷是否有下鄰接i=i+1;/ 合并空閑區(qū)if(k!=-1) / 回收區(qū)有上鄰接 if(j!=-1) / 回收區(qū)也有下鄰接，和上 下鄰接合并free_tablek.length+=free_tablej.length+

15、recycle_length;free_tablej.flag=0; / 將 第 j欄的標記置為 '0'else和上鄰接合并/ 不存在下free_tablek.length+=recycle_length;else if(j!=-1) / 只 有 下鄰接，和下鄰接合并free_tablej.length+=recycle_len gth;free_tablej.address=recycle_address;else / 上下鄰 接都沒有x=0;while(free_tablex.flag!=0)x=x+1; / / 在空閑區(qū)表中查找一個狀 態(tài)為 '0' 的欄目

16、if(x<=M-1) / 找到后，在空閑分區(qū) 中登記回收的內(nèi)存free_tablex.address=recycle_address;free_tablex.length=recycle_length;free_tablex.flag=1;else / 空閑表已滿，執(zhí)行 回收失敗used_tabley.flag=process_namecout<<" 空閑區(qū)已滿， 回收失敗！n" return 0;return process_name;void show() / 程序執(zhí)行時輸出模擬 的內(nèi)存分配回收表cout<<"+ +ncout&l

17、t;<"+ 空 閑 區(qū) +n"cout<<"+ +n"for(int i=0;i<=count2;i+) if(free_tablei.flag!=0)cout<<" 初 始 地 址 ： "<<free_tablei.address<<""<<" 長 度 ： "<<free_tablei.length<<" "<<" 狀 態(tài)： "<<fr

18、ee_tablei.flag<<endl;cout<<"+ncout<<"+ 已 分 配 區(qū) +n"cout<<"+ +n"for(int j=0;j<count1;j+) if(used_tablej.flag!=0)cout<<" 初 始 地 址 ： "<<used_tablej.address<<""<<" 長 度 ："<<used_tablej.length<

19、<" "<<" 作業(yè)名："<<used_tablej.flag<<endl;void main() / 主函數(shù)調(diào)用各功能 函數(shù)對所有工作進行測試int choice; / 用來選擇將要進行的 操作int job_name;float need_memory;bool exitFlag=false;cout<<" 動態(tài)分區(qū)分配方式的模擬n"cout<< * n"cout<<" 請選擇操作類型： n"initialize(); / 開創(chuàng)空閑區(qū)和已分配區(qū) 兩個表while(!exitFlag)cout<<"*1: 分 配 內(nèi) 存3: 查 看 分 配cout<<"*2: 回收內(nèi)存*n"cout<<"*0: 退 出*n"cout<<n"c