操作系統(tǒng)實(shí)驗(yàn)內(nèi)存分配

1、 西 安 郵 電 大 學(xué) （計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 內(nèi)存管理 專業(yè)名稱： 軟件工程班 級： 學(xué)生姓名： 學(xué)號（8位）：指導(dǎo)教師： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)五：進(jìn)程1.實(shí)驗(yàn)?zāi)康?通過深入理解區(qū)管理的三種算法，定義相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，編寫具體代碼。 充分模擬三種算法的實(shí)現(xiàn)過程，并通過對比，分析三種算法的優(yōu)劣。（1）掌握內(nèi)存分配FF，BF，WF策略及實(shí)現(xiàn)的思路；（2）掌握內(nèi)存回收過程及實(shí)現(xiàn)思路；（3）參考給出的代碼思路，實(shí)現(xiàn)內(nèi)存的申請、釋放的管理程序，調(diào)試運(yùn)行，總結(jié)程序設(shè)計(jì)中出現(xiàn)的問題并找出原因，寫出實(shí)驗(yàn)報(bào)告。2.實(shí)驗(yàn)要求：1） 掌握內(nèi)存分配FF，BF，WF策略及實(shí)現(xiàn)的思路；2） 掌握內(nèi)存回收過程及

2、實(shí)現(xiàn)思路；3） 參考本程序思路，實(shí)現(xiàn)內(nèi)存的申請、釋放的管理程序，調(diào)試運(yùn)行，總結(jié)程序設(shè)計(jì)中出現(xiàn)的問題并找出原因，寫出實(shí)驗(yàn)報(bào)告。3. 實(shí)驗(yàn)過程：創(chuàng)建進(jìn)程：刪除其中幾個(gè)進(jìn)程：(默認(rèn)以ff首次適應(yīng)算法方式排列)Bf 最佳適應(yīng)算法排列方式：wf最差匹配算法排列方式：4. 實(shí)驗(yàn)心得： 這次實(shí)驗(yàn)實(shí)驗(yàn)時(shí)間比較長，而且實(shí)驗(yàn)指導(dǎo)書中對內(nèi)存的管理講的很詳細(xì)，老師上課的時(shí)候也有講的很詳細(xì)，但是代碼比較長，剛開始的時(shí)候也是不太懂，但是后面經(jīng)過和同學(xué)一起商討，明白幾種算法的含義： 首次適應(yīng)算法。在采用空閑分區(qū)鏈作為數(shù)據(jù)結(jié)構(gòu)時(shí)，該算法要求空閑分區(qū)鏈表以地址遞增的次序鏈接。在進(jìn)行內(nèi)存分配時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)能

3、滿足進(jìn)程大小要求的空閑分區(qū)為止。然后，再按照進(jìn)程請求內(nèi)存的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求進(jìn)程，余下的空閑分區(qū)仍留在空閑鏈中。 循環(huán)首次適應(yīng)算法。該算法是由首次適應(yīng)算法演變而形成的，在為進(jìn)程分配內(nèi)存空間時(shí)，從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊與請求的大小相等的內(nèi)存空間分配給進(jìn)程。 最佳適應(yīng)算法將空閑分區(qū)鏈表按分區(qū)大小由小到大排序，在鏈表中查找第一個(gè)滿足要求的分區(qū)。 最差匹配算法將空閑分區(qū)鏈表按分區(qū)大小由大到小排序，在鏈表中找到第一個(gè)滿足要求的空閑分區(qū)。實(shí)驗(yàn)中沒有用到循環(huán)首次適應(yīng)算法，但是對其他三種的描述還是很詳細(xì)，總的來說，

4、從實(shí)驗(yàn)中還是學(xué)到了很多。5.程序源代碼：#include<stdio.h>#include<malloc.h>#include<unistd.h>#include<stdlib.h>#define PROCESS_NAME_LEN 32 /進(jìn)程名長度#define MIN_SLICE 10 /最小碎片的大小#define DEFAULT_MEM_SIZE 1024/內(nèi)存大小#define DEFAULT_MEM_START 0 /起始位置/*內(nèi)存分配算法*/#define MA_FF 1#define MA_BF 2#define MA_WF 3

5、/*描述每一個(gè)空閑塊的數(shù)據(jù)結(jié)構(gòu)*/struct free_block_typeint size;/空閑塊大小int start_addr;/空閑塊起始地址struct free_block_type *next;/指向下一個(gè)空閑塊;/*指向內(nèi)存中空閑塊鏈表的首指針*/struct free_block_type *free_block = NULL;/*每個(gè)進(jìn)程分配到的內(nèi)存塊的描述*/struct allocated_blockint pid;/進(jìn)程標(biāo)識符int size;/進(jìn)程大小int start_addr;/進(jìn)程分配到的內(nèi)存塊的起始地址char process_namePROCESS_N

6、AME_LEN;/進(jìn)程名struct allocated_block *next;/指向下一個(gè)進(jìn)程控制塊;/*進(jìn)程分配內(nèi)存塊鏈表的首指針*/struct allocated_block *allocated_block_head = NULL;int free_block_count = 0;/空閑塊個(gè)數(shù)int mem_size = DEFAULT_MEM_SIZE; /內(nèi)存大小int current_free_mem_size = 0;/當(dāng)前空閑內(nèi)存大小int ma_algorithm = MA_FF; /當(dāng)前分配算法static int pid = 0; /初始PIDint flag =

7、0;/設(shè)置內(nèi)存大小標(biāo)志,表示內(nèi)存大小是否設(shè)置/*函數(shù)聲明*/struct free_block_type* init_free_block(int mem_size);void display_menu();int set_mem_size();void set_algorithm();void rearrange(int algorithm);int rearrange_WF();int rearrange_BF();int rearrange_FF();int new_process();int allocate_mem(struct allocated_block *ab);void k

8、ill_process();int free_mem(struct allocated_block *ab);int dispose(struct allocated_block *free_ab);int display_mem_usage();struct allocated_block *find_process(int pid);int do_exit();int allocate_FF(struct allocated_block *ab);int allocate_BF(struct allocated_block *ab);int allocate_WF(struct alloc

9、ated_block *ab);int allocate(struct free_block_type *pre, struct free_block_type *allocate_free_nlock, struct allocated_block *ab);int mem_retrench(struct allocated_block *ab);/ 通過內(nèi)存緊縮技術(shù)給新進(jìn)程分配內(nèi)存空間int mem_retrench(struct allocated_block *ab)struct allocated_block *allocated_work, *allocated_pre = all

10、ocated_block_head;struct free_block_type *free_work, *free_pre = free_block->next;if(allocated_pre = NULL)return -1;allocated_pre->start_addr = 0;allocated_work = allocated_pre->next;while(allocated_work != NULL)allocated_work->start_addr = allocated_pre->start_addr + allocated_pre-&g

11、t;size;allocated_pre = allocated_work;allocated_work = allocated_work->next;free_block->start_addr = allocated_pre->start_addr + allocated_pre->size;free_block->size = current_free_mem_size;free_block->next = NULL;free_work = free_pre;while(free_pre != NULL)free(free_pre);free_pre

12、= free_work;if(free_pre != NULL)free_work = free_work->next;allocate(NULL, free_block, ab);return 1;/ 給新進(jìn)程分配內(nèi)存空間 int allocate(struct free_block_type *pre, struct free_block_type *allocate_free_block, struct allocated_block *ab)struct allocated_block *p = allocated_block_head;ab->start_addr = a

13、llocate_free_block->start_addr;if(allocate_free_block->size - ab->size < MIN_SLICE)ab->size = allocate_free_block->size;if(pre != NULL)pre->next = allocate_free_block;elsefree_block = allocate_free_block->next;free(allocate_free_block);elseallocate_free_block->start_addr +

14、= ab->size;allocate_free_block->size -= ab->size;if(p = NULL)allocated_block_head = ab;elsewhile(p->next != NULL)p = p->next;p->next = ab;current_free_mem_size -= ab->size;if(current_free_mem_size = 0)free_block = NULL;return 0;/按照最壞適應(yīng)算法給新進(jìn)程分配內(nèi)存空間int allocate_WF(struct allocated

15、_block *ab)int ret;struct free_block_type *wf = free_block;if(wf = NULL)return -1;if(wf->size >= ab->size)allocate(NULL, wf, ab);else if(current_free_mem_size >= ab->size)ret = mem_retrench(ab);elseret = -2;rearrange_WF();return ret;/ 按照最佳適應(yīng)算法給新進(jìn)程分配內(nèi)存空間int allocate_BF(struct allocated

16、_block *ab)int ret;struct free_block_type *pre = NULL, *bf = free_block;if(bf = NULL)return -1;while(bf != NULL)if(bf->size >= ab->size)ret = allocate(pre, bf,ab);break;pre = bf;pre = pre->next;if(bf = NULL && current_free_mem_size > ab->size)ret = mem_retrench(ab);elseret

17、= -2;rearrange_BF();return ret;/ 按照首次適應(yīng)算法給新進(jìn)程分配內(nèi)存空間int allocate_FF(struct allocated_block *ab)int ret;struct free_block_type *pre = NULL, *ff = free_block;if(ff = NULL)return -1;while(ff != NULL)if(ff->size >= ab->size)ret = allocate(pre, ff,ab);break;pre = ff;pre = pre->next;if(ff = NUL

18、L && current_free_mem_size > ab->size)ret = mem_retrench(ab);elseret = -2;rearrange_FF();return ret;/分配內(nèi)存模塊int allocate_mem(struct allocated_block *ab)int ret ;struct free_block_type *fbt, *pre;int request_size = ab->size;fbt = pre = free_block;switch(ma_algorithm)case MA_FF :ret =

19、allocate_FF(ab);break;case MA_BF :ret = allocate_BF(ab);break;case MA_WF :ret = allocate_WF(ab);break;default :break;return ret;/ 創(chuàng)建一個(gè)新的進(jìn)程。int new_process()struct allocated_block *ab;int size;int ret;ab = (struct allocated_block *)malloc(sizeof(struct allocated_block);if(!ab)exit(-5);ab->next = N

20、ULL;pid+;sprintf(ab->process_name, "PROCESS-%02d", pid);/sprintf()函數(shù)將格式化的數(shù)據(jù)寫入某字符串中ab->pid = pid; printf("Memory for %s:", ab->process_name);for(; ; )scanf("%d", &size);getchar();if(size > 0)ab->size = size;break;elseprintf("The size have to great

21、er than zero! Please input again!");ret = allocate_mem(ab); /從空閑區(qū)分配內(nèi)存，ret=1表示分配okif(ret = 1) && (allocated_block_head = NULL)/如果此時(shí)allocated_block_head尚未賦值，則賦值 /進(jìn)程分配鏈表為空allocated_block_head = ab;return 1;else if(ret = 1) /分配成功，將該已分配塊的描述插入已分配鏈表ab->next = allocated_block_head;/頭插法alloca

22、ted_block_head = ab;return 2;else if(ret = -1) /分配不成功printf("Allocation failn");free(ab);return -1; return 3;/退出程序并釋放內(nèi)存空間。int do_exit()struct allocated_block *allocated_ab, *allocated_pre;struct free_block_type *free_ab, *free_pre;free_pre = free_block;allocated_pre = allocated_block_head;

23、if(free_pre != NULL)free_ab = free_pre->next;while(free_ab != NULL)free(free_pre);free_pre = free_ab;free_ab = free_ab->next;if(allocated_pre != NULL)allocated_ab = allocated_pre->next;while(allocated_ab != NULL)free(allocated_pre);allocated_pre = allocated_ab;allocated_ab = allocated_ab-&g

24、t;next;allocated_ab = allocated_ab->next;return 0;/在進(jìn)程分配鏈表中尋找指定進(jìn)程。struct allocated_block *find_process(int pid)struct allocated_block *ab = allocated_block_head;if(ab = NULL)printf("Here?111111111n");return NULL;while(ab->pid != pid && ab->next != NULL)ab = ab->next;if(

25、ab->next = NULL && ab->pid != pid)printf("Here?2222222n");return NULL;return ab;/顯示當(dāng)前內(nèi)存的使用情況，包括空閑區(qū)的情況和已經(jīng)分配的情況。int display_mem_usage()struct free_block_type *fbt = free_block;struct allocated_block *ab = allocated_block_head;printf("-n");/顯示空閑區(qū)printf("Free Memor

26、y:n");printf("%20s %20sn", " start_addr", " size");while(fbt != NULL)printf("%20d %20dn", fbt->start_addr, fbt->size);fbt = fbt->next;/顯示已分配區(qū)printf("nUsed Memory:n");printf("%10s %20s %10s %10sn", "PID", "Proces

27、sName", "start_addr", " size");while(ab != NULL)printf("%10d %20s %10d %10dn", ab->pid, ab->process_name, ab->start_addr, ab->size);ab = ab->next;printf("-n");return 1;/ 釋放ab數(shù)據(jù)結(jié)構(gòu)節(jié)點(diǎn)。int dispose(struct allocated_block *free_ab)struct allocate

28、d_block *pre, *ab;if(free_block = NULL)return -1;if(free_ab = allocated_block_head)/如果要釋放第一個(gè)節(jié)點(diǎn)allocated_block_head = allocated_block_head->next;free(free_ab); elsepre = allocated_block_head; ab = allocated_block_head->next;/找到free_abwhile(ab != free_ab)pre = ab;ab = ab->next;pre->next =

29、ab->next;free(ab);return 1;/*將ab所表示的已分配區(qū)歸還，并進(jìn)行可能的合并*/int free_mem(struct allocated_block *ab)int algorithm = ma_algorithm;struct free_block_type *fbt, *pre, *work;fbt = (struct free_block_type*)malloc(sizeof(struct free_block_type);if(!fbt)return -1;pre = free_block;fbt->start_addr = ab->st

30、art_addr;fbt->size = ab->size;fbt->next = NULL;if(pre != NULL)while(pre->next != NULL)pre = pre->next;pre->next = fbt;elsefree_block = fbt;rearrange_FF();pre = free_block;work = pre->next;while(work != NULL)if(pre->start_addr + pre->size = work->start_addr)pre->size

31、+= work->size;free(work);work = pre->next;elsepre = work;work = work->next;current_free_mem_size += ab->size;return 1;/ 刪除進(jìn)程，歸還分配的存儲空間，并刪除描述該進(jìn)程內(nèi)存分配的節(jié)點(diǎn)。void kill_process()struct allocated_block *ab;int pid;printf("Kill Process, pid=");scanf("%d", &pid);getchar();ab

32、 = find_process(pid);if(ab != NULL)free_mem(ab); /*釋放ab所表示的分配區(qū)*/dispose(ab); /*釋放ab數(shù)據(jù)結(jié)構(gòu)節(jié)點(diǎn)*/按FF算法重新整理內(nèi)存空閑塊鏈表,按空閑塊首地址排序。int rearrange_FF()struct free_block_type *head = free_block;struct free_block_type *forehand, *pre, *rear;int i;if(head = NULL)return -1;/冒泡排序for(i = 0; i < free_block_count-1; i+

33、)forehand = head;pre = forehand->next;rear = pre->next;while(pre->next != NULL)if(forehand = head && forehand->start_addr >= pre->start_addr)/比較空閑鏈表中第一個(gè)空閑塊與第二個(gè)空閑塊的開始地址的大小head->next = pre->next;pre->next = head;head = pre;forehand = head->next;pre = forehand->

34、next;rear = pre->next;else if(pre->start_addr >= rear->start_addr)/比較鏈表中其他相鄰兩節(jié)點(diǎn)的開始地址的大小pre->next = rear->next;forehand->next = rear;rear->next = pre;forehand = rear;rear = pre->next;elseforehand = pre;pre = rear;rear = rear->next;return 0;/ 按BF算法重新整理內(nèi)存空閑塊鏈表,按空閑塊大小從小到大排序

35、。int rearrange_BF()struct free_block_type *head = free_block;struct free_block_type *forehand, *pre, *rear;int i;if(head = NULL)return -1;/冒泡排序for(i = 0; i < free_block_count-1; i+)forehand = head;pre = forehand->next;rear = pre->next;while(pre->next != NULL)if(forehand = head &&

36、 forehand->size <= pre->size)/比較空閑鏈表中第一個(gè)空閑塊與第二個(gè)空閑塊的空間的大小head->next = pre->next;pre->next = head;head = pre;forehand = head->next;pre = forehand->next;rear = pre->next;else if(pre->size <= rear->size)/比較鏈表中其他相鄰兩節(jié)點(diǎn)的空間的大小pre->next = rear->next;forehand->next

37、 = rear;rear->next = pre;forehand = rear;rear = pre->next;elseforehand = pre;pre = rear;rear = rear->next;return 0;/按WF算法重新整理內(nèi)存空閑塊鏈表,按空閑塊大小從大到小排序。int rearrange_WF()struct free_block_type *head = free_block;struct free_block_type *forehand, *pre, *rear;int i;if(head = NULL)return -1;/冒泡排序for

38、(i = 0; i < free_block_count-1; i+)forehand = head;pre = forehand->next;rear = pre->next;while(pre->next != NULL)if(forehand = head && forehand->size >= pre->size)/比較空閑鏈表中第一個(gè)空閑塊與第二個(gè)空閑塊空間的大小head->next = pre->next;pre->next = head;head = pre;forehand = head->ne

39、xt;pre = forehand->next;rear = pre->next;else if(pre->size >= rear->size)/比較鏈表中其他相鄰兩節(jié)點(diǎn)的空間的大小pre->next = rear->next;forehand->next = rear;rear->next = pre;forehand = rear;rear = pre->next;elseforehand = pre;pre = rear;rear = rear->next;return 0;/按指定的算法整理內(nèi)存空閑塊鏈表。void r

40、earrange(int algorithm)switch(algorithm)case MA_FF:rearrange_FF();break;case MA_BF:rearrange_BF();break;case MA_WF:rearrange_WF();break;/設(shè)置當(dāng)前的分配算法void set_algorithm()int algorithm;/system("clear");printf("t1 - First Fitn");/首次適應(yīng)算法printf("t2 - Best Fit n");/最佳適應(yīng)算法printf(

41、"t3 - Worst Fit n");/最壞適應(yīng)算法printf("nPlease choose(13):");for(; ; )scanf("%d", &algorithm);getchar();if(algorithm >= 1 && algorithm <= 3) ma_algorithm = algorithm;break;elseprintf("nCannot input %d, Please input 13 : ", algorithm);/按指定算法重新排列空閑

42、區(qū)鏈表 rearrange(ma_algorithm); /設(shè)置內(nèi)存的大小int set_mem_size()int size;if(flag != 0)/防止重復(fù)設(shè)置 printf("Cannot set memory size againn"); return 0; printf("Total memory size = ");for(; ; )scanf("%d", &size);getchar();if(size > 0)current_free_mem_size = size;mem_size = size;/設(shè)置內(nèi)存大小為sizefree_bloc