操作系統(tǒng)課程設(shè)計(jì)-內(nèi)存管理

1、仲愷農(nóng)業(yè)工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱：操作系統(tǒng)實(shí)驗(yàn)題目：內(nèi)存管理院 系：信息科學(xué)與技術(shù)學(xué)院班 級： 姓 名： 學(xué) 號： 二十五年十二月三十日目錄1 系統(tǒng)分析31.1目的和意義31.2目標(biāo)分析32總體設(shè)計(jì)42.1程序設(shè)計(jì)組成框圖4系統(tǒng)分為4個子模塊：初始化模塊，4初始化模塊：42.2流程圖53詳細(xì)設(shè)計(jì)63.1設(shè)計(jì)思路63.1.1.動態(tài)分區(qū)分配63.1.2.動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)63.1.3.動態(tài)分區(qū)分配算法63.1.4.回收內(nèi)存73.2參數(shù)定義73.3數(shù)據(jù)結(jié)構(gòu)73.4函數(shù)定義73.5算法分析84核心代碼實(shí)現(xiàn)84.1首次適應(yīng)算法84.2最佳適應(yīng)算法94.3最差適應(yīng)算法115 程序調(diào)試133.3分

2、配內(nèi)存143.4回收內(nèi)存及合并分區(qū)156 總結(jié)177參考文件178源代碼181 系統(tǒng)分析1.1 目的和意義操作系統(tǒng)課程主要講述的內(nèi)容是多道操作系統(tǒng)的原理與技術(shù)，與其它計(jì)算機(jī)原理、編譯原理、匯編語言、計(jì)算機(jī)網(wǎng)絡(luò)、程序設(shè)計(jì)等專業(yè)課程關(guān)系十分密切。本課程設(shè)計(jì)的目的綜合應(yīng)用學(xué)生所學(xué)知識，建立系統(tǒng)和完整的計(jì)算機(jī)系統(tǒng)概念，理解和鞏固操作系統(tǒng)基本理論、原理和方法，掌握操作系統(tǒng)開發(fā)的基本技能。1.2 目標(biāo)分析11.111.11.1.111.11.1.1.1.2.1 采用可變分區(qū)方式完成對存儲空間的管理（即存儲空間的分配與回收工作）。1.2.2 設(shè)計(jì)用來記錄主存使用情況的數(shù)據(jù)結(jié)構(gòu)：已分區(qū)表和空閑分區(qū)表或鏈表。1

3、.2.3 在設(shè)計(jì)好的數(shù)據(jù)結(jié)構(gòu)上設(shè)計(jì)一個主存分配算法。1.2.4 在設(shè)計(jì)好的數(shù)據(jù)結(jié)構(gòu)上設(shè)計(jì)一個主存回收算法。其中，若回收的分區(qū)有上鄰空閑分區(qū)和（或）下鄰空閑分區(qū)，要求合并為一個空閑分區(qū)登記在空閑分區(qū)表的一個表項(xiàng)里。2總體設(shè)計(jì)122.1 程序設(shè)計(jì)組成框圖系統(tǒng)分為4個子模塊：初始化模塊，首次適應(yīng)算法模塊、最佳適應(yīng)算法模塊、最差適應(yīng)算法模塊的四個算法模塊。 初始化模塊：allocation( )初始化函數(shù)，給每個相關(guān)的算法分配內(nèi)存賦值。首次適應(yīng)算法模塊，利用首次適應(yīng)算法實(shí)現(xiàn)主存空間的分配并可以查看主存空間的分配情況和內(nèi)存的回收。最佳適應(yīng)算法模塊，利用首次適應(yīng)算法實(shí)現(xiàn)主存空間的分配并可以查看主存空間的分

4、配情況和內(nèi)存的回收。最差適應(yīng)算法模塊，利用首次適應(yīng)算法實(shí)現(xiàn)主存空間的分配并可以查看主存空間的分配情況和內(nèi)存的回收。Main（）allocation( )初始化最差適應(yīng)算法最佳適應(yīng)算法首次適應(yīng)算法回收內(nèi)存分配內(nèi)存回收內(nèi)存分配內(nèi)存回收內(nèi)存分配內(nèi)存2.2 流程圖分配成功表頭移動錯誤退出查找下一個可用內(nèi)存是否足夠設(shè)定內(nèi)存分配可用內(nèi)存回收內(nèi)存表頭不變，區(qū)間合并表頭移動至上領(lǐng)區(qū)間并合并是否含有上領(lǐng)或下領(lǐng)區(qū)間3詳細(xì)設(shè)計(jì)1233.1 設(shè)計(jì)思路1.2.3.3.1.3.1.1. 動態(tài)分區(qū)分配動態(tài)分區(qū)分配又稱為可變分區(qū)分配，它是根據(jù)進(jìn)程的實(shí)際需要，動態(tài)的為之分配內(nèi)存空間。在實(shí)現(xiàn)動態(tài)分區(qū)分配時，將涉及到分區(qū)分配中所用

5、的數(shù)據(jù)結(jié)構(gòu)，分區(qū)分配算法和分區(qū)的分配與回收操作這樣三方面的問題。3.1.2. 動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)動態(tài)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用以描述空閑分區(qū)和已分配分區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式:（1）空閑分區(qū)表，在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目中包括分區(qū)號，分區(qū)大小和分區(qū)始址等數(shù)據(jù)項(xiàng)。（2）空閑分區(qū)鏈，為實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的其實(shí)部分設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針，在分區(qū)尾部則設(shè)置一后向指針。通過前后相鏈接指針，可將所有的空閑分區(qū)鏈接成一個雙向鏈。3

6、.1.3. 動態(tài)分區(qū)分配算法首次適應(yīng)算法（FF算法）：FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€能滿足要求的分區(qū)，則表示系統(tǒng)中已沒有足夠大的內(nèi)存分配給該進(jìn)程，內(nèi)存分配失敗，返回。最佳適應(yīng)（BF算法）：BF算法是指，每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈。這樣，第一次找

7、到的能滿足要求的空閑區(qū)必然是最佳的。最壞適應(yīng)算法（WF算法)：與最佳適應(yīng)算法正好相反，在掃描整個空閑分區(qū)表或鏈表時，總是挑選一個最大的空閑區(qū)，從中分割一小部分存儲空間給作業(yè)使用，以至于存儲器中缺失大的空閑分區(qū)。該算法要求，將所有的空閑分區(qū)，按其容量以從大到小的順序形成一空閑分區(qū)鏈，查找時，只要看第一個分區(qū)是否滿足作業(yè)要求即可。3.1.4. 回收內(nèi)存（1）回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接。此時也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用（2）回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。（3）回收區(qū)同時與插入點(diǎn)的前、后兩個分區(qū)鄰接，此時將三個分區(qū)合并，使用F1的表項(xiàng)和F1的首址，取消F2的

8、表項(xiàng)，大小為三者之和。（4）回收區(qū)既不與F1鄰接，也不與F2鄰接。這時應(yīng)為回收區(qū)單獨(dú)建立一個新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈表中的適當(dāng)位置。3.2 參數(shù)定義#define OK 1 /完成 #define ERROR 0 /出錯typedef int Status;LinkList first;/頭結(jié)點(diǎn)LinkList end;/尾結(jié)點(diǎn)int flag;/記錄要刪除的分區(qū)序號3.3 數(shù)據(jù)結(jié)構(gòu)typedef struct free_table/定義一個空閑區(qū)說明表結(jié)構(gòu)int num; /分區(qū)序號long address; /起始地址long length;/分區(qū)大小 in

9、t state; /分區(qū)狀態(tài) ElemType;typedef struct Node/線性表的雙向鏈表存儲結(jié)構(gòu)ElemType data;struct Node*prior;/前趨指針struct Node *next;/后繼指針Node,*LinkList;3.4 函數(shù)定義Status Initblock()/初始化函數(shù)Status First_fit(int request) /首次適應(yīng)算法Status Best_fit(int request)/最佳適應(yīng)算法Status Worst_fit(int request) /最差適應(yīng)算法3.5 算法分析首次適應(yīng)算法（First Fit）： 從

10、空閑分區(qū)表的第一個表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。最佳適應(yīng)算法（Best Fit）：它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。最差適應(yīng)算法（Worst Fit）也稱最差適配算法：它從

11、全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最大的空閑分區(qū)，從而使鏈表中的結(jié)點(diǎn)大小趨于均勻，適用于請求分配的內(nèi)存大小范圍較窄的系統(tǒng)。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按大小從大到小進(jìn)行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留小的空閑區(qū)，盡量減少小的碎片產(chǎn)生。4 核心代碼實(shí)現(xiàn)4.1 首次適應(yīng)算法Status First_fit(int request) /首次適應(yīng)算法Node *p=first->next;/為申請作業(yè)開辟新空間且初始化 LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.le

12、ngth=request;temp->data.state=1;p->data.num=1;while(p)if(p->data.state=0)&&(p->data.length=request)/有大小恰好合適的空閑塊p->data.state=1;return OK;break;else if(p->data.state=0) && (p->data.length>request)/有空閑塊能滿足需求且有剩余temp->prior=p->prior;temp->next=p;temp->

13、;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;4.2 最佳適應(yīng)算法Status Best_fit(int request)/最佳適

14、應(yīng)算法int ch;/記錄最小剩余空間Node *p=first;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) && (p->data.length>=request) ) if(q=NULL) q=p;ch=p->data.length-request;

15、 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;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.nu

16、m=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;4.3 最差適應(yīng)算法Status Worst_fit(int request) /最差適應(yīng)算法int ch;/記錄最大剩余空間Node *p=first->next; Node *q=NULL;/記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node)

17、;temp->data.length=request;temp->data.state=1;p->data.num=1; while(p)/初始化最大空間和最佳位置if(p->data.state=0 && (p->data.length>=request) )if(q=NULL)q=p;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=NU

18、LL) return ERROR;/沒有找到空閑塊else if(q->data.length=request)q->data.length=1;return OK;elsetemp->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=c

19、h;q->data.num+=1;return OK; return OK; 5 程序調(diào)試 以最佳適應(yīng)算法為例進(jìn)行程序調(diào)試，調(diào)試結(jié)果如下4.1開始界面 4.2選擇最佳適應(yīng)算法3.3分配內(nèi)存 3.4回收內(nèi)存及合并分區(qū)6 總結(jié) 本次課程設(shè)計(jì)使我加深了請求頁式存儲管理中置換算法的理解，在這次設(shè)計(jì)中，我學(xué)到了許多知識，由于之前的C語言、數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)打的不好，分析算法程序時感到很吃力，在剛開始編程時很茫然，無從下手，所以先看了老師之前的程序，也到網(wǎng)上看了別人寫的相似程序，這才對存儲管理的各個算法的設(shè)計(jì)有一點(diǎn)眉目。 在這次課程設(shè)計(jì)中，我不僅學(xué)會了一些C+知識，還知道了一個道理：有些程序編寫看起來很

20、難，毫無頭緒，一旦你嘗試去寫，最終你終能得到你想要的結(jié)果，不怕你不會，就怕你不做。 通過各個置換算法的設(shè)計(jì)編程，使我在思維、看待問題的全面性等方面也有了很大的提高。讓我對實(shí)驗(yàn)原理有更深的理解，通過把該算法的內(nèi)容，算法的執(zhí)行順序在計(jì)算機(jī)上實(shí)現(xiàn)，知道和理解了該理論在計(jì)算機(jī)中是怎樣執(zhí)行的，對該理論在實(shí)踐中的應(yīng)用有深刻的理解。并且這次課程設(shè)計(jì)把各個學(xué)科之間的知識融合起來，把各門課程的知識聯(lián)系起來，對計(jì)算機(jī)整體的認(rèn)識更加深刻。我希望今后能在動手方面加強(qiáng)，多上機(jī)。雖然現(xiàn)在的我還不能獨(dú)立的完成這樣一個復(fù)雜的設(shè)計(jì)，但我相信經(jīng)過這樣一次又一次的設(shè)計(jì)，最終我能做得更好。7參考文件1. 陸松華.操作系統(tǒng).

21、電子工業(yè)出版社2. 李春葆.數(shù)據(jù)結(jié)構(gòu)（第4版）.清華大學(xué)出版社3. 石玉強(qiáng).C語言程序設(shè)計(jì). 電子工業(yè)出版社8源代碼#include<stdio.h>#include<stdlib.h>#define OK 1 /完成 #define ERROR 0 /出錯typedef int Status;typedef struct free_table/定義一個空閑區(qū)說明表結(jié)構(gòu)int num; /分區(qū)序號long address; /起始地址long length;/分區(qū)大小 int state; /分區(qū)狀態(tài) ElemType;typedef struct Node/線性表的雙

22、向鏈表存儲結(jié)構(gòu)ElemType data;struct Node*prior;/前趨指針struct Node *next;/后繼指針Node,*LinkList;LinkList first;/頭結(jié)點(diǎn)LinkList end;/尾結(jié)點(diǎn)int flag;/記錄要刪除的分區(qū)序號Status Initblock()/開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表first=(LinkList)malloc(sizeof(Node);end=(LinkList)malloc(sizeof(Node);first->prior=NULL;first->next=end;end->prior=first;

23、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(

24、)/顯示主存分配情況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("ntt主存空間分配情況n"); printf("*nn");printf("分區(qū)序號t起始地址t分區(qū)大小t分區(qū)狀態(tài)nn");while(p)printf("%dtt%dtt%d",p->data.num,p->data.addre

25、ss,p->data.length);if(p->data.state=0)printf("tt空閑nn");else printf("tt已分配nn");p=p->next; printf("*nn"); Status First_fit(int request) /首次適應(yīng)算法Node *p=first->next;/為申請作業(yè)開辟新空間且初始化 LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->

26、;data.state=1;p->data.num=1;while(p)if(p->data.state=0)&&(p->data.length=request)/有大小恰好合適的空閑塊p->data.state=1;return OK;break;else if(p->data.state=0) && (p->data.length>request)/有空閑塊能滿足需求且有剩余temp->prior=p->prior;temp->next=p;temp->data.address=p->d

27、ata.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)/最佳適應(yīng)算法int ch;/記錄最小剩余空間Node *p=firs

28、t;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) && (p->data.length>=request) )if(q=NULL)q=p;ch=p->data.length-request; else if(q->data.length > p

29、->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;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.num=q->data.num;q->prior->n

30、ext=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK;return OK;Status Worst_fit(int request) /最差適應(yīng)算法int ch;/記錄最大剩余空間Node *p=first->next; Node *q=NULL;/記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.

31、state=1;p->data.num=1; while(p)/初始化最大空間和最佳位置if(p->data.state=0 && (p->data.length>=request) )if(q=NULL)q=p;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.

32、length=request)q->data.length=1;return OK;elsetemp->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; /分

33、配主存Status allocation(int a)int request;/申請內(nèi)存大小printf("請輸入申請分配的主存大小(單位:KB):");scanf("%d",&request);if(request<0 |request=0)printf("分配大小不合適，請重試！");return ERROR;switch(a)case 1:/默認(rèn)首次適應(yīng)算法 if(First_fit(request)=OK) printf("t*分配成功！*"); else printf("t*內(nèi)存不

34、足，分配失??！*"); return OK; break;case 2:/選擇最佳適應(yīng)算法if(Best_fit(request)=OK)printf("t*分配成功！*");else printf("t*內(nèi)存不足，分配失??！*");return OK;break;case 3:/選擇最差適應(yīng)算法if(Worst_fit(request)=OK)printf("t*分配成功！*");else printf("t*內(nèi)存不足，分配失??！*");return OK; break; Status deal1(No

35、de *p)/處理回收空間Node *q=first;for(;q!=NULL;q=q->next)if(q=p)if(q->prior->data.state=0&&q->next->data.state!=0)q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(

36、q->prior->data.state!=0&&q->next->data.state=0)q->data.length+=q->next->data.length;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->next->data.state=0)q->prior->

37、;data.length+=q->data.length;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->data.state!=0)q->data.state=0;return OK;Status deal2(Node *p)/處理回收空間Node *q=first;for(;q

38、!=NULL;q=q->next)if(q=p)if(q->prior->data.state=0&&q->next->data.state!=0)q->prior->data.length+=q->data.length;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&

39、;&q->next->data.state=0)q->data.state=0;if(q->prior->data.state=0&&q->next->data.state=0)q->prior->data.length+=q->data.length;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->data.state!=0)q->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)/當(dāng)前P指向的下一個不是最后一個時if(p->next->