動態(tài)分區(qū)分配存儲管理系統(tǒng)2

1、實(shí)用標(biāo)準(zhǔn)文案動態(tài)分區(qū)分配存儲管理系統(tǒng)學(xué)院計算機(jī)科學(xué)與技術(shù)專業(yè)計算機(jī)科學(xué)與技術(shù)學(xué) 號學(xué)生姓名指導(dǎo)教師姓名精彩文檔目錄一、 課程設(shè)計目的11、背景12、目的1二、課題任務(wù)描述1三、課題研發(fā)相關(guān)知識 11、 最佳適應(yīng)算法(best fit ) 12、 最壞適應(yīng)算法(worst fit ) 13、 回收內(nèi)存14、庫函數(shù)的介紹2四、課題設(shè)計21、 總體結(jié)構(gòu)22、 數(shù)據(jù)結(jié)構(gòu)43、 主要功能的流程圖 54、 、程 序 的 技 術(shù)線7五、 帶有詳細(xì)注解的源程序 7-18六、運(yùn)行與測試18-19七、收獲及改進(jìn)意見 20一、課程設(shè)計目的1、背景主存是CPIM直接訪問的信息空間，合理而有效的使用貯存將在很大程度上

2、影響整個計算機(jī)系統(tǒng)的性能。本課題要求模擬實(shí)現(xiàn)分區(qū)式主存管理機(jī)制。模擬實(shí)現(xiàn)各種分區(qū)管理方法以及 相應(yīng)的主存分配以及回收算法。2、目的進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識。培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計的方法和能力。提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計的能力。提高學(xué)生分析問題、解決問題以及綜合利用C語言進(jìn)行程序設(shè)計的 能力。課題任務(wù)描述用高級語言編寫和調(diào)試一個動態(tài)分區(qū)內(nèi)存分配程序，演示實(shí)現(xiàn)下列兩種動態(tài) 分區(qū)分配算法1 .最佳適應(yīng)算法2 .最壞適應(yīng)算法三、課題研發(fā)相關(guān)知識(包含所用庫函數(shù)的介紹)1、最佳適應(yīng)算法(best fit )所謂“最佳”是指每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的 空

3、閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的 空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空閑區(qū)，必然是最佳的。 這樣，在存儲器中會留下許多難以利用的小 空閑區(qū)。2、最壞適應(yīng)算法(worst fit )要掃描整個空閑分區(qū)表或鏈表，總是挑選一個最大的空閑區(qū)分割給作業(yè)使 用，具優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對中小作業(yè)有力，查找效率很高。但是它會使存儲器中缺乏大的空閑分區(qū)。3、回收內(nèi)存當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)會收取的首址，從空閑區(qū)鏈中找到相 應(yīng)的插入點(diǎn)，并考慮回收區(qū)前后是否有空閑分區(qū)，如果有， 則把兩個分區(qū)

4、合并成 一個大的空閑分區(qū)。4、庫函數(shù)的介紹1) stdio 就是指 “standard buffered input&output"意思就是說帶緩沖的標(biāo)準(zhǔn)輸入輸出！ 所以了，用到標(biāo)準(zhǔn)輸入輸出函數(shù)時，就要調(diào)用這個 頭文件！2) Stdlib.h 即standard library 標(biāo)準(zhǔn)庫文件。Stdlib 頭文件里包含了 C,C+i§言的最常用白系統(tǒng)函數(shù)。Stdlib.h 里面定義了五中類型，一些宏和通用 工具函數(shù)。 類型例如：size_t ,wchar_t, div_t, ldiv_t,lldiv_t;宏例如：EXIT_FALIRE,EXIT_SUCCESS,RAN

5、D_MIAXIB_CUR_MAX以下是一些常用的函數(shù)：dec置基數(shù)為10相當(dāng)于"d" hex置基數(shù)為16相 當(dāng)于"X"； oct置基數(shù)為8相當(dāng)于"o" setw(n)設(shè)域?qū)挒閚個字符四、課題設(shè)計：總體結(jié)構(gòu)、所使用的數(shù)據(jù)結(jié)構(gòu)、主要功能的流程圖、程序的技術(shù)路線1、總體結(jié)構(gòu)本系統(tǒng)采用了最佳適應(yīng)算法和最壞適應(yīng)算法模擬存儲器動態(tài)分區(qū)。系統(tǒng)利用 其中某種分配算法，從空閑分區(qū)鏈中找到滿足請求內(nèi)存大小的分區(qū)并分配內(nèi)存給 作業(yè)。假設(shè)總的內(nèi)存大小為size ,作業(yè)請求的內(nèi)存大小為request,內(nèi)存碎片最 小為f。當(dāng)request>size 時，內(nèi)

6、存溢出，出現(xiàn)系統(tǒng)錯誤；當(dāng) request<=size 時, 在內(nèi)存中根據(jù)上述算法尋找最佳的內(nèi)存分區(qū)分配給作業(yè)。尋找到合適的內(nèi)存分區(qū)之后，如果size-request<=f, 將此分區(qū)上的內(nèi)存全部分配給作業(yè)；如果 size-request>f ,就在此分區(qū)上分割request大小的內(nèi)存給作業(yè)，剩余內(nèi)存繼續(xù) 留在當(dāng)前的分區(qū)中。當(dāng)進(jìn)程運(yùn)行完畢，系統(tǒng)找到該進(jìn)程并釋放其內(nèi)存，根據(jù)所釋放內(nèi)存的位置對內(nèi)存進(jìn)行合并。系統(tǒng)流程圖：如圖1系統(tǒng)框架圖：如圖2存儲器動態(tài)分區(qū)分配模擬系統(tǒng)檢測函數(shù)最佳適應(yīng)算法最壞適應(yīng)算法退 出 系 統(tǒng)分配內(nèi)存回收內(nèi)存返 回 上一級 菜 單圖22、數(shù)據(jù)結(jié)構(gòu)(1) 定義的全

7、局變量：#define SIZE 100/內(nèi)存初始大小#define MINSIZE 0/碎片最小值enum STATE Free, Busy /枚舉類型，記錄分區(qū)是否空閑的狀態(tài)量(2)定義的結(jié)構(gòu)體：struct subAreaNode 。記錄分區(qū)的主要數(shù)據(jù)。(3)函數(shù)1) void intSubArea():分配初始分區(qū)內(nèi)存。2) int bestFit(int taskId, int size):最佳適應(yīng)算法實(shí)現(xiàn)函數(shù)，taskId為作業(yè)名，size為作業(yè)申請的內(nèi)存大小。3) int worstFit(int taskId, int size):最壞適應(yīng)算法實(shí)現(xiàn)函數(shù)，taskId為作業(yè)名，s

8、ize為作業(yè)申請的內(nèi)存大小。4) int freeSubArea(int taskId) :內(nèi)存回收函數(shù)，該函數(shù)主要用于實(shí)現(xiàn)內(nèi) 存的回收，根據(jù)回收內(nèi)存的位置對分區(qū)進(jìn)行合并操作。其中 taskId為所 需回收內(nèi)存的作業(yè)號。5) void showSubArea():顯示空閑分區(qū)鏈情況。包括起始地址，空間大小。 工作狀態(tài)。作業(yè)號。6) int main():主函數(shù)，主要用于顯示操作界面，調(diào)用各個子函數(shù)等功能。3、主要功能的流程圖(1)最佳適應(yīng)算法 Best_fit(int,int);流程圖（圖3）(3)最壞適應(yīng)算法 Worst_fit(int,int); 流程圖(圖4)內(nèi)存初始大小碎片最小值起始地

9、址分區(qū)大小作業(yè)號分區(qū)狀態(tài)分區(qū)前向指針分區(qū)后向指針4.程序的技術(shù)路線本程序采用C語言編寫，在windows下的Visual C+中編譯，模擬可變分 區(qū)存儲管理方式的內(nèi)存分配與回收。假定系統(tǒng)的最大內(nèi)存空間為100M判斷是否劃分空閑區(qū)的最小限值為 MINSIZE=0初始化用戶可占用內(nèi)存區(qū)的首地址為 0, 大小為0M定義一個結(jié)構(gòu)體及其對象 subHead實(shí)現(xiàn)內(nèi)存的分配回收及分配表和 空閑表的登記。用最佳分配算法實(shí)現(xiàn)動態(tài)分配時，調(diào)用int bestFit(int taskId, int size)內(nèi)存分配函數(shù)，設(shè)定循環(huán)條件查找最佳空閑分區(qū)，根據(jù)找到的空閑區(qū) 大小和作業(yè)大小判斷是整個分配給作業(yè)還是切割空閑

10、區(qū)后再分配給作業(yè)，并在 “內(nèi)存分配表”和“空閑分區(qū)表”中作登記。調(diào)用int freeSubArea(int taskId) 函數(shù)實(shí)現(xiàn)內(nèi)存的回收。順序循環(huán)“內(nèi)存分配表”找到要回收的作業(yè)，設(shè)置標(biāo)志位 flag ,當(dāng)flag=1時表示回收成功?；厥諆?nèi)存時需考慮內(nèi)存的4種合并方式，即合并上下分區(qū)、合并上分區(qū)、合并下分區(qū)、上下分區(qū)都不合并。五、帶有詳細(xì)注解的源程序#include<stdio.h>#include<time.h>#include<stdlib.h>#define SIZE 100/#define MINSIZE 0/enum STATE Free, B

11、usy ; static int ss=0,ee=0;struct subAreaNode int addr;/int size;/int taskId; /STATE state; /subAreaNode *pre;/subAreaNode *nxt;/subHead;/初始化空閑分區(qū)鏈void intSubArea()/分配初始分區(qū)內(nèi)存subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode);/給首個分區(qū)賦值fir->addr = 0;fir->size = SIZE;fir->state = Free;f

12、ir->taskId = -1;fir->pre = &subHead;fir->nxt = NULL;/ 初始化分區(qū)頭部信息subHead.pre = NULL;subHead.nxt = fir;/最佳適應(yīng)算法int bestFit(int taskId, int size)subAreaNode *tar = NULL;int tarSize = SIZE + 1;subAreaNode *p = subHead.nxt;while(p != NULL) /尋找最佳空閑區(qū)問if(p->state = Free && p->size &

13、gt;= size && p->size < tarSize) tar = p;tarSize = p->size;p = p->nxt;if(tar != NULL) /找到要分配的空閑分區(qū)if(tar->size - size <= MINSIZE) /整塊分配tar->state = Busy;tar->taskId = taskId; else /分配大小為size的區(qū)間subAreaNode *node = (subAreaNode *)malloc(sizeof(subA reaNode);node->addr

14、= tar->addr + size;node->size = tar->size - size;node->state = Free;node->taskId = -1;/修改分區(qū)鏈節(jié)點(diǎn)指針node->pre = tar;node->nxt = tar->nxt;if(tar->nxt != NULL) tar->nxt->pre = node;tar->nxt = node;/分配空閑區(qū)間tar->size = size;tar->state = Busy;tar->taskId = taskId;p

15、rintf("內(nèi)存分配成功！ n");return 1; else /找不到合適的空閑分區(qū)printf("找不到合適的內(nèi)存分區(qū)，分配失敗 n");return 0;int worstFit(int taskId, int size)subAreaNode *tar = NULL;int tarSize;int mm=1;subAreaNode *p = subHead.nxt;while(p != NULL&&mm=1) /尋找最佳空閑區(qū)問if(p->state = Free && p->size >=

16、size) tar = p;tarSize = p->size;mm=0;elsep = p->nxt;p=subHead.nxt;while(p != NULL)/尋找最大空閑區(qū)問if(p->state = Free && p->size >= tarSize && p->size>=size) tar = p;tarSize = p->size;/遍歷找到最大空閑區(qū)問p=p->nxt;elsep = p->nxt;if(tar != NULL) /找到要分配的空閑分區(qū)if(tar->size-

17、size<= MINSIZE) /整塊分配tar->state = Busy;tar->taskId = taskId; else /分配大小為size的區(qū)間subAreaNode*node=(subAreaNode*)malloc(sizeof(subAreaNod e);node->addr = tar->addr + size;node->size = tar->size - size;node->state = Free;node->taskId = -1;/修改分區(qū)鏈節(jié)點(diǎn)指針node->pre = tar;node->

18、nxt = tar->nxt;if(tar->nxt != NULL) tar->nxt->pre = node;tar->nxt = node;/分配空閑區(qū)間tar->size = size;tar->state = Busy;tar->taskId = taskId;printf("內(nèi)存分配成功！ n");return 1; else /找不到合適的空閑分區(qū)printf("找不到合適的內(nèi)存分區(qū)，分配失敗 n");return 0;/回收內(nèi)存int freeSubArea(int taskId)int f

19、lag = 0;subAreaNode *p = subHead.nxt, *pp;while(p != NULL)if(p->state = Busy && p->taskId = taskId) flag = 1;if(p->pre != &subHead && p->pre->state = Free)&& (p->nxt != NULL && p->nxt->state = Free) /情況1:合并上下兩個分區(qū)/先合并上區(qū)間pp = p;p = p->pre;

20、p->size += pp->size;p->nxt = pp->nxt;pp->nxt->pre = p;free(pp);/后合并下區(qū)間pp = p->nxt;p->size += pp->size;p->nxt = pp->nxt;if(pp->nxt != NULL) pp->nxt->pre = p;)free(pp); else if(p->pre = &subHead | p->pre->state = Busy)&& (p->nxt != NULL

21、 && p->nxt->state = Free) /情況2:只合并下面的分區(qū)pp = p->nxt;p->size += pp->size;p->state = Free;p->taskId = -1;p->nxt = pp->nxt;if(pp->nxt != NULL) pp->nxt->pre = p;free(pp); else if(p->pre != &subHead && p->pre->state = Free)&& (p->

22、nxt = NULL | p->nxt->state = Busy) /情況3:只合并上面的分區(qū)pp = p;p = p->pre;p->size += pp->size;p->nxt = pp->nxt;if(pp->nxt != NULL) pp->nxt->pre = p;free(pp); else /情況4：上下分區(qū)均不用合并p->state = Free;p->taskId = -1;p = p->nxt;if(flag = 1) / 回收成功printf(" 內(nèi)存分區(qū)回收成功 n")

23、;return 1; else n");/ 找不到目標(biāo)作業(yè)，回收失敗printf(" 找不到目標(biāo)作業(yè)，內(nèi)存分區(qū)回收失敗return 0;/顯示空閑分區(qū)鏈情況 void showSubArea()printf("I*n");printf("*當(dāng)前的內(nèi)存分配情況如下:printf("I*n");printf("*起始地址|空間大小|工作狀態(tài)|*n");作業(yè)號*n");subAreaNode *p = subHead.nxt;while(p != NULL)printf("*n")

24、;printf("*");printf("%5d M |", p->addr);printf("%5d M |", p->size);printf(" %5s |", p->state = Free ? "Free" : "Busy");if(p->taskId > 0) printf("%5d ", p->taskId); else printf(" ");printf("*n"

25、);p = p->nxt;printf("*n");bool checks(int task) /檢測是否作業(yè)已存在，存在返回假，不存在返回真subAreaNode *p = subHead.nxt;while(p != NULL)if(p->state=Busy && task=p->taskId)return false;elsep=p->nxt;return true;int main()int option, ope, taskId, size;/初始化空閑分區(qū)鏈intSubArea();/選擇分配算法l1: while(1)

26、printf("I*n");printf("請選擇要模擬的分配算法：n1表示最佳適應(yīng)算法n2表示最壞適應(yīng)算法n3退出n");printf("*n");scanf("%d”, &option);system("cls");if(option = 1) printf("你選擇了最佳適應(yīng)算法，下面進(jìn)行算法的模擬 n");break; else if(option = 2) printf("你選擇了最壞適應(yīng)算法，下面進(jìn)行算法的模擬 n");break;else if

27、(option = 3)exit(0);else printf("錯誤:請輸入 0/1nn");/模擬動態(tài)分區(qū)分配算法while(1)printf("n");printf("I*n");printf(" 1:分配內(nèi)存n 2: 回收內(nèi)存n 3:單n0: 退出 nn");返回上一級菜printf("I*n");scanf("%d”, &ope);system("cls");if(ope = 0) break;if(ope = 1) / 模擬分配內(nèi)存printf(

28、"請輸入作業(yè)號：");scanf("%d”, &taskId);printf("請輸入需要分配的內(nèi)存大小(M):");scanf("%d”, &size);if(size <= 0) printf("錯誤：分配內(nèi)存大小必須為正值n");continue;/ 調(diào)用分配算法if(option=1)bestFit(taskId, size);elseworstFit(taskId, size);/ 顯示空閑分區(qū)鏈情況showSubArea(); else if(ope = 2) / 模擬回收內(nèi)存printf("請輸入要回收的作業(yè)號：");scanf("%d”, &taskId);freeSubArea(taskId);/ 顯示空閑分區(qū)鏈情況showSubArea(); else if(ope=3)goto l1;else printf（"錯誤:請輸入 0/1/2n"）;p