實(shí)驗(yàn)五-動(dòng)態(tài)分區(qū)存儲(chǔ)管理

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

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

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

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

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

6、oat length; / 空閑區(qū)長(zhǎng)度，單位為字 節(jié)int flag; / 空閑區(qū)表登記欄標(biāo)志，用 "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ū)長(zhǎng)度，單位為int flag;/ 已分配區(qū)表登記欄標(biāo)志， "0"表示空欄目used_tableN;/ 已分配區(qū)表對(duì)象名/ 空閑區(qū)表的定義：structfloat address; / 空閑區(qū)起始地址 float length; / 空閑區(qū)長(zhǎng)度，單位為字 節(jié)int flag; / 空閑區(qū)表登記欄標(biāo)志，用 &qu

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

9、ee_table0.flag=1; / 空 閑 區(qū) 表 的表項(xiàng)全部為未分配/ 最優(yōu)分配算法實(shí)現(xiàn)的動(dòng)態(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) / 整個(gè)分配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、分配表中標(biāo)志為空欄 目的項(xiàng)while(used_tablei.flag!=0)i=i+1;if(i<=N-1) / 找到，在已分配區(qū)表 中登記一個(gè)表項(xiàng)used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=process_name;count1+;else / 已分配區(qū)表長(zhǎng)度不足if(free_tablek.flag = 0) / 將已做的整個(gè)分配撤銷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 <<" 無(wú)法為該作業(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è)后，將該欄的 標(biāo)志置為 '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欄的標(biāo)記置為 '0'else和上鄰接合并/ 不存在下free_tablek.length+=recycle_length;else if(j!=-1) / 只 有 下鄰接，和下鄰接合并free_tablej.length+=recycle_len gth;free_tablej.address=recycle_address;else / 上下鄰 接都沒(méi)有x=0;while(free_tablex.flag!=0)x=x+1; / / 在空閑區(qū)表中查找一個(gè)狀 態(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ū)已滿， 回收失?。" return 0;return process_name;void show() / 程序執(zhí)行時(shí)輸出模擬 的內(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<<""<<" 長(zhǎng) 度 ： "<<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<<""<<" 長(zhǎng) 度 ："<<used_tablej.length<

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