內(nèi)存管理、分配與回收模擬實驗(共43頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上姓名學(xué)號實驗成績專心-專注-專業(yè)華中師范大學(xué)計算機科學(xué)系實 驗 報 告 書實驗題目：內(nèi)存管理、分配與回收 課程名稱： 操作系統(tǒng) 主講教師： 輔導(dǎo)教師： 課程編號： 班 級： 實驗時間： 一、實驗?zāi)康模海?）掌握內(nèi)存分區(qū)管理的基本思想，理解內(nèi)存分配表。（2）深入理解可變分區(qū)的內(nèi)存分配策略，掌握首先適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法。（3）掌握內(nèi)存碎片產(chǎn)生的途徑以及解決碎片的方法拼接技術(shù)。（4）實現(xiàn)分區(qū)的回收。針對內(nèi)存管理的相關(guān)活動，研究內(nèi)存空閑隊列的動態(tài)組織與管理問題，以及在此基礎(chǔ)上執(zhí)行的內(nèi)存分配與回收活動。二、實驗內(nèi)容：本實驗將利用伙伴系統(tǒng)來組織內(nèi)存空閑塊隊列和已使

2、用內(nèi)存塊隊列。從初始化快照、某一組作業(yè)申請內(nèi)存塊前的快照、分配成功后的快照等狀態(tài)出發(fā)，結(jié)合內(nèi)存分配原語（算法）和內(nèi)存回收原語（算法）的實現(xiàn)，結(jié)合實際內(nèi)存塊的動態(tài)分配與回收情況（某一快照），研究內(nèi)存空閑塊隊列的組織、變化及其隊列管理方面的問題。具體內(nèi)容如下：（1）實現(xiàn)內(nèi)存分配算法和內(nèi)存回收算法。（2）以伙伴系統(tǒng)的組織方式管理內(nèi)存空閑隊列和已使用內(nèi)存塊隊列，具體的組織策略應(yīng)分別考慮首次適應(yīng)策略、最佳適應(yīng)策略和最壞適應(yīng)策略。（3）考慮在某一內(nèi)存使用一段時間的快照，給出一組作業(yè)的內(nèi)存申請，判斷該申請是否可以被滿足。3、 實驗要求（1） 分配算法中切割空閑區(qū)是從低地址開始；（2） 需考慮門限值情況，門限

3、值是指切割空閑區(qū)后剩下的區(qū)域若小于一個用戶給定的值時，就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請者，這個值由用戶指定；（3）回收算法需要考慮上鄰、下鄰、上下鄰和不相鄰四種情況。四、實驗環(huán)境：實踐平臺：windows編寫環(huán)境：CodeBlocks編譯器：g+五、實驗設(shè)計原理（1）可變分區(qū)基本思想可變分區(qū)是指系統(tǒng)不預(yù)先劃分固定分區(qū)，而是在裝入程序時劃分，使程序分配的大小正好等于程序的需求量，且分區(qū)的個數(shù)是可變的，這樣有較大的靈活性，較之固定分區(qū)能獲得更好的內(nèi)存利用率。其狀態(tài)如圖所示： （2）內(nèi)存分配表內(nèi)存分配表由兩張表格組成：一張是已分配表，記錄已裝入的程序在內(nèi)存中占用分區(qū)的起始地址和長度，并表之位指出占用分

4、區(qū)的程序名；另一張是空閑區(qū)表，記錄內(nèi)存中可供分配的空閑區(qū)的起始地址和長度，用標(biāo)志位指出該分區(qū)是未分配的空閑區(qū)。其基本結(jié)構(gòu)如圖所示： （3）分配策略1 首次適應(yīng)算法（First Fit）：從空閑分區(qū)表的第一個表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法的目的在于減少查找時間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。2 最佳適應(yīng)算法（Best Fit)：從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表

5、（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。3 最差適應(yīng)算法（Worst Fit)：從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最大的空閑分區(qū)，從而使鏈表中的結(jié)點大小趨于均勻，適用于請求分配的內(nèi)存大小范圍較窄的系統(tǒng)。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)按大小從大到小進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留小的空閑區(qū)，盡量減少小的碎片產(chǎn)生。（4）碎片拼接采用可變分區(qū)存儲管理方案后，經(jīng)過一段時間的分配回收，內(nèi)存中會存在很多很小的空閑塊。需要在適當(dāng)時刻進行碎片整理，通過內(nèi)存

6、中移動程序，把所有空閑碎片合并成一個連續(xù)的大空閑區(qū)且放在內(nèi)存的一端，而把所有程序占用區(qū)放在內(nèi)存另一端。（5） 分區(qū)的回收當(dāng)用戶執(zhí)行結(jié)束后，系統(tǒng)要收回已經(jīng)使用完畢的分區(qū)，將其記錄在空閑區(qū)表中。一般情況下應(yīng)考慮四種情況：1. 回收分區(qū)的上鄰分區(qū)是空閑的，需要將這兩個相鄰的空閑分區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表。2. 回收分區(qū)的下鄰分區(qū)是空閑的，需要將這兩個相鄰的空閑分區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表。3. 回收分區(qū)上下鄰區(qū)都是空閑的，需要將三者合并成一個更大的空閑區(qū)，然后修改空閑表。4. 回收區(qū)的上鄰下鄰區(qū)都不是空閑的，則直接將空閑區(qū)記錄在空閑表中。五、實驗詳細實現(xiàn)過程與算法流

7、程（一）數(shù)據(jù)結(jié)構(gòu)1. 作業(yè)結(jié)構(gòu)本實驗的重點是對內(nèi)存的管理、分配與回收，所以作業(yè)的內(nèi)部結(jié)構(gòu)簡單，僅包含：進程名（name）、程序大小（size）和內(nèi)部指針（next），其結(jié)構(gòu)如圖：2. 分配表結(jié)構(gòu)本實驗的分配表結(jié)構(gòu)包含：進程名兼區(qū)名（name）、地址（address）、程序大?。╯ize）、狀態(tài)（state）和內(nèi)部指針（next），其結(jié)構(gòu)如圖：2. 隊列結(jié)構(gòu)作業(yè)隊列（joblist）、占用表隊列（occupiedlist）和空閑表隊列（blanklist）。其結(jié)構(gòu)如圖所示：（2） 程序結(jié)構(gòu)思維導(dǎo)圖6、 實驗測試與過程分析（1） 實驗數(shù)據(jù)內(nèi)存大小設(shè)置為1024k。進行CreateJob操作后，由計

8、算機隨機生成一個作業(yè)，每生成一個作業(yè)，作業(yè)名累次加1，作業(yè)大小隨機設(shè)置位200k500k大小，其結(jié)構(gòu)如圖所示：（2） 測試首先適應(yīng)算法（FF）1 創(chuàng)建5個作業(yè)，作業(yè)隊列、空閑表隊列、占用隊列如圖所示：2 分配內(nèi)存直至內(nèi)存不足：3 依次終止JOB2、 JOB1、JOB3對FF算法進行了多組測試，僅記錄了一組測試結(jié)果。通過多組測試的結(jié)果分析，每次劃分內(nèi)存空間，均是從低地址處開始劃分，在結(jié)束作業(yè)，收回內(nèi)存時，根據(jù)相鄰情況與否，進行合并后在按地址升序插入到空閑隊列中。（3） 最佳適應(yīng)算法（BF）1 創(chuàng)建5個作業(yè)，作業(yè)隊列、空閑表隊列、占用隊列如圖所示：2 分配內(nèi)存直至不足：3 終止作業(yè)JOB2、JOB

9、1：對BF算法進行了多組測試，僅記錄了一組測試結(jié)果。通過多組測試的結(jié)果分析，每次劃分內(nèi)存空間，均是從低地址處開始劃分，在結(jié)束作業(yè)，收回內(nèi)存時，根據(jù)相鄰情況與否，進行合并后按照空閑塊的大小升序插入空閑隊列中。（4） 最壞適應(yīng)算法（BF）1 創(chuàng)建5個作業(yè)，作業(yè)隊列、空閑表隊列、占用隊列如圖所示：2 分配內(nèi)存直至不足：3 終止作業(yè)JOB2、JOB1： 對WF算法進行了多組測試，僅記錄了一組測試結(jié)果。通過多組測試的結(jié)果分析，每次劃分內(nèi)存空間，均是從低地址處開始劃分，在結(jié)束作業(yè)，收回內(nèi)存時，根據(jù)相鄰情況與否，進行合并后按照空閑塊的大小降序插入空閑隊列中。六、實驗結(jié)果分析（問題的發(fā)現(xiàn)、分析、解決方案與創(chuàng)新

10、）1. 在設(shè)計分配表數(shù)據(jù)結(jié)構(gòu)的時候，起初考慮了順序表結(jié)構(gòu)，發(fā)現(xiàn)在執(zhí)行整個內(nèi)存的分配與回收的過程中，需要較多地進行刪除、插入操作，順序表并不合適，遂改為鏈表結(jié)構(gòu)，實現(xiàn)相關(guān)的鏈表操作。2. 因為設(shè)計了鏈表的數(shù)據(jù)結(jié)構(gòu)，對不同算法中占用表和空閑表中塊的排序極為困難，換一種思路，便是在回收合并的時候，如果有相鄰的空閑塊，把它們摘取下來，進行合并，把合并后的結(jié)果再插入到空閑表中，這樣的方式與之前想過的在空閑表原有的塊上合并相鄰空閑塊更為簡單，容易實現(xiàn)，十分地方便。3. 在考慮到瀏覽結(jié)果的方便性和直觀性，通過相應(yīng)的格式控制，以表格的形式展現(xiàn)各個隊列的狀態(tài)，各個作業(yè)在何種操作后進入何種隊列有了清晰的直觀的追蹤

11、，充分地展示內(nèi)存分配過程。7、 源程序（加注釋）見附頁8、 實驗體會與改進意見（1）實驗體會1.本次實驗主要是熟悉內(nèi)存管理的相關(guān)概念及內(nèi)存管理的各部分內(nèi)容，并明確內(nèi)存管理中所運用到的數(shù)據(jù)結(jié)構(gòu)、控制機制的基本原理，代碼實現(xiàn)了三種內(nèi)存分配策略，分區(qū)的回收，代碼實現(xiàn)了實驗所需要的各種隊列的部分基本操作，實現(xiàn)代碼復(fù)用。2.通過編程自行模擬了操作系統(tǒng)的內(nèi)存分配與回收，充分理解了分配表的重要作用，更深入了其中的邏輯過程，而且對自己的編程能力也有所提高。（2）改進意見1.由于一些其他原因，本實驗中對碎片整合問題沒有實現(xiàn)。現(xiàn)主要描述一下實現(xiàn)思路：可設(shè)置一個fragdisposal函數(shù)來處理碎片整合問題，設(shè)置一

12、個指針reoccupied，從占用隊列（blanklist）中依次取出空閑塊加入到reoccupied指針后，形成新的占用隊列。對于空閑隊列刪除原有隊列塊，新的空閑隊列只有一個空閑塊，其地址為占用隊列最后一個占用塊的address+size。2.本實驗中計算機生成的作業(yè)大小范圍為200k500k，內(nèi)存區(qū)大小為1024k，則會出現(xiàn)，則大部分可能出現(xiàn)內(nèi)存區(qū)只能存放2到3個的作業(yè)，可以適當(dāng)?shù)恼{(diào)小作業(yè)大小范圍或者調(diào)大內(nèi)存大小，從而觀察多個作業(yè)的內(nèi)存管理、分配和回收的情況，更細致地對內(nèi)存管理進行追蹤。附頁：實驗三.cpp#include<stdio.h>#include<stdlib.

13、h>#include<time.h>#define MAX_MEMARY 1024#define MIN 100#define FREE 0#define BUSY 1/作業(yè)結(jié)構(gòu)typedef struct JOB int name; /進程名 int size; /大小 struct JOB *next; /指針JOB;/分配結(jié)構(gòu)typedef struct M_JOB int name; /進程名 int address; /地址 int size; /大小 int state; /狀態(tài) struct M_JOB *next; /指針M_JOB;int n;/JOB隊列結(jié)

14、構(gòu)typedef struct Queue_JOB JOB *head; JOB *tail; int len;Queue;/作業(yè)隊列Queue_JOB joblist;/M_JOB隊列結(jié)構(gòu)typedef struct Queue_M_JOB M_JOB *head; M_JOB *tail; int len;Queue_M_JOB;/占用、空閑隊列Queue_M_JOB occupiedlist, blanklist;void MainMenu() system("cls"); printf("t _ n"); printf("t| |n&q

15、uot;); printf("t| MainMenu |n"); printf("t| |n"); printf("t| Use FF press1 |n"); printf("t| |n"); printf("t| Use BF press2 |n"); printf("t| |n"); printf("t| Use WF press3 |n"); printf("t| |n"); printf("t| Exit press

16、0 |n"); printf("t| |n"); printf("t|_|n");void SubMenu() system("cls"); printf("t _ n"); printf("t| |n"); printf("t| SubMenu |n"); printf("t| |n"); printf("t| Create Job press1 |n"); printf("t| |n"); printf

17、("t| Distribute Memory press2 |n"); printf("t| |n"); printf("t| End Job press3 |n"); printf("t| |n"); printf("t| Exit press0 |n"); printf("t| |n"); printf("t|_|n");/創(chuàng)建作業(yè)插入作業(yè)隊列尾void CreateJob() JOB *p; p = new JOB(); p->name = +

18、n; p->size = rand() % 300 + 200; p->next = NULL; if(joblist.head = NULL) joblist.head = p; joblist.tail = p; joblist.len+; else joblist.tail->next = p; joblist.tail = p; joblist.len+; /取出作業(yè)隊列隊首元素JOB *PopFromJobList() JOB *q; if(joblist.len = 0) printf("the job list is empty!n"); e

19、lse q = joblist.head; joblist.head = joblist.head->next; joblist.len-; return q;/打印作業(yè)隊列void PrintJobList() JOB *p; p = joblist.head; printf("nt#job list:n"); if(joblist.len = 0) printf("tjob list is empty!n"); else printf("t-n"); printf("t|namet|sizet|n");

20、printf("t-n"); while(p != NULL) printf("t|JOB%dt|%dkt|n", p->name, p->size); p = p->next; printf("t-n"); /打印空閑表void PrintBlankList() M_JOB *p; p = blanklist.head->next; printf("nt#blank list:n"); if(blanklist.len = 0) printf("tblank list is em

21、pty!n"); else printf("t-n"); printf("t|namet|address|sizet|n"); printf("t-n"); while(p != NULL) printf("t|JOB%dt|%dt|%dkt|n", p->name, p->address, p->size); p = p->next; printf("t-n"); /打印占用表void PrintOccupiedList() M_JOB *p; p = occ

22、upiedlist.head->next; printf("nt#occupied list:n"); if(occupiedlist.len = 0) printf("toccupied list is empty!n"); else printf("t-n"); printf("t|namet|address|sizet|n"); printf("t-n"); while(p != NULL) printf("t|JOB%dt|%dt|%dkt|n", p->

23、name, p->address, p->size); p = p->next; printf("t-n"); /初始化各隊列void InitList() /初始空閑塊 M_JOB *q = new M_JOB(); q->name = 0; q->address = 0; q->size = MAX_MEMARY; q->state = FREE; q->next = NULL; /初始空閑塊入空閑隊列 blanklist.head = new M_JOB(); blanklist.head->next = q; b

24、lanklist.tail = q; blanklist.len+; /初始化占用隊列 occupiedlist.head = new M_JOB(); occupiedlist.head->next = NULL; occupiedlist.tail = occupiedlist.head; occupiedlist.len = 0;/加入到占用隊列void AddToOccupiedList(M_JOB *point) M_JOB *q = occupiedlist.head->next, *s = occupiedlist.head; /如果空，加入到隊首 if(q = NU

25、LL) occupiedlist.head->next = point; occupiedlist.len+; return; /按地址升序排列占用隊列 while(q != NULL) if(point->address < q->address) point->next = q; s->next = point; occupiedlist.len+; break; s = q; q = q->next; /如果地址大于前面元素，則加入到隊列尾 if(q = NULL) s->next = point; occupiedlist.len+; v

26、oid InsertIntoBlankList(M_JOB *point, int i) M_JOB *q = blanklist.head->next, *s = blanklist.head; /如果空，加入到隊首 if(q = NULL) blanklist.head->next = point; blanklist.len+; return; while(q != NULL) /首先適應(yīng)算法插入空閑隊列中 if(point->address < q->address && i = 1) point->next = q; s->n

27、ext = point; blanklist.len+; return; /最佳適應(yīng)算法插入空閑隊列中 else if(point->size < q->size && i = 2) point->next = q; s->next = point; blanklist.len+; return; /最壞適應(yīng)算法插入空閑隊列中 else if(point->size > q->size && i = 3) point->next = q; s->next = point; blanklist.len+;

28、 return; else s = q; q = q->next; /插入隊尾 if(q = NULL) s->next = point; blanklist.len+; return; /按相應(yīng)算法分配內(nèi)存void Distribute(int i) M_JOB *q = blanklist.head->next, *s = blanklist.head; M_JOB *p = new M_JOB(); /空閑隊列空，內(nèi)存不足 if(q = NULL) printf("ntTip:not enough memory!n"); return; /從作業(yè)隊列

29、中取出作業(yè) JOB *pjob = PopFromJobList(); while(q != NULL) if(q->size >= pjob->size) /如果分配后剩余大小不足100k就全部分配給該作業(yè) if(q->size - pjob->size < 100) s->next = q->next; blanklist.len-; q->name = pjob->name; q->state = BUSY; q->next = NULL; AddToOccupiedList(q); break; /否則進行切割 e

30、lse p->name = pjob->name; p->address = q->address; p->size = pjob->size; p->state = BUSY; p->next = NULL; /占用的內(nèi)存進占用表 AddToOccupiedList(p); q->name = 0; q->address = q->address + pjob->size; q->size = q->size - pjob->size; q->state = FREE; s->next =

31、q->next; blanklist.len-; /剩下的空閑內(nèi)存重新按算法插入空閑表 InsertIntoBlankList(q, i); break; s = q; q = q->next; /沒有滿足大小的空閑塊則內(nèi)存不足， /將取出的作業(yè)重新加入到作業(yè)隊列隊首 if(q = NULL) printf("ntTip:not enough memory!n"); pjob->next = joblist.head; joblist.head = pjob; joblist.len+; /從占用隊列中取出占用塊M_JOB *PopFromOccupied

32、List(int id) M_JOB *q = occupiedlist.head->next, *s = occupiedlist.head; if(occupiedlist.len = 0) printf("ntTip:the occupied list is empty!n"); return NULL; while(q != NULL) if(q->name = id) s->next = q->next; q->name = 0; q->state = FREE; q->next = NULL; occupiedlist.

33、len-; return q; s = q; q = q->next; if(q = NULL) printf("ntTip:can not find the job!n"); return NULL;/空閑塊合并M_JOB *Merge(M_JOB *point) M_JOB *q = blanklist.head->next, *s = blanklist.head; M_JOB *x, *y; M_JOB *merged = new M_JOB(); /如果空閑表為空，無需合并直接返回point空閑快 if(q = NULL) return point;

34、while(q != NULL) /指向可以合并的單元 if(point->address + point->size = q->address | q->address + q->size = point->address) /指向可合并單元 /鄰下找鄰上 if(point->address + point->size = q->address) x = q; s->next = q->next; q = q->next; blanklist.len-; if(q = NULL) point->name = 0;

35、/point->address = point->address; point->size = x->size + point->size; point->state = FREE; point->next = NULL; return point; else while(q != NULL) /查找是否鄰上 if(q->address + q->size = point->address) y = q; s->next = q->next; blanklist.len-; point->name = 0; poin

36、t->address = y->address; point->size = x->size + y->size + point->size; point->state = FREE; point->next = NULL; delete x; delete y; return point; s = q; q = q->next; /沒有鄰上則合并兩個空閑塊 if(q = NULL) point->name = 0; /point->address = point->address; point->size = x-

37、>size + point->size; point->state = FREE; point->next = NULL; return point; /鄰上找鄰下 if(q->address + q->size = point->address) x = q; s->next = q->next; q = q->next; blanklist.len-; if(q = NULL) point->name = 0; point->address = x->address; point->size = x->

38、;size + point->size; point->state = FREE; point->next = NULL; return point; else while(q != NULL) /查找是否鄰下 if(point->address + point->size = q->address) y = q; s->next = q->next; blanklist.len-; merged->name = 0; merged->address = x->address; merged->size = x->s

39、ize + y->size + point->size; merged->state = FREE; merged->next = NULL; delete x; delete y; delete point; return merged; s = q; q = q->next; /沒有鄰下則合并兩個空閑塊 if(q = NULL) point->name = 0; point->address = x->address; point->size = x->size + point->size; point->state

40、= FREE; point->next = NULL; return point; else s = q; q = q->next; return point;void EndJob(int i) printf("ntinput the number:"); int id; M_JOB *pop, *merged; scanf("%d",&id); pop = PopFromOccupiedList(id); if(pop != NULL) merged = Merge(pop); InsertIntoBlankList(merged, i); /首先適應(yīng)算法void FF() int m; SubMenu(); printf("ntYour select:"); while(scanf("%d", &m) != EOF) printf("t_n"); if(m = 1) CreateJob(); else if(m = 2) Distribute(1); else if(m = 3) EndJob(1); else if(m = 0) break; else printf(&q