西安郵電大學(xué)操作系統(tǒng)內(nèi)存管理實(shí)驗(yàn)報(bào)告含源碼

1、 西 安 郵 電 大 學(xué) （計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 內(nèi)存管理 專業(yè)名稱： 軟件工程班 級(jí)： 1201班 學(xué)生姓名： 學(xué)號(hào)（8位）： 指導(dǎo)教師： 實(shí)驗(yàn)日期： 2014年11月25日1. 實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境(一)、實(shí)驗(yàn)環(huán)境1. 硬件(1) 主機(jī)：Pentium III 以上；(2) 內(nèi)存：128MB 以上；(3) 顯示器：VGA 或更高；(4) 硬盤空間：至少100MB 以上剩余空間。2. 軟件Ubuntu下gcc編譯器、gdb調(diào)試工具。(二)、實(shí)驗(yàn)?zāi)康?1)、掌握內(nèi)存分配FF，BF，WF策略及實(shí)現(xiàn)的思路；(2)、掌握內(nèi)存回收過(guò)程及實(shí)現(xiàn)思路；(3)、參考本程序思路，實(shí)現(xiàn)內(nèi)存的申請(qǐng)、釋放

2、的管理程序，調(diào)試運(yùn)行，總結(jié)程序設(shè)計(jì)中出現(xiàn)的問(wèn)題并找出原因。二、實(shí)驗(yàn)內(nèi)容（1)補(bǔ)充完整FF，BF，WF等算法的代碼；（2)掌握內(nèi)存回收過(guò)程及實(shí)現(xiàn)思路；（3)實(shí)現(xiàn)內(nèi)存的申請(qǐng)和釋放。三方案設(shè)計(jì)（一）、實(shí)現(xiàn)功能1-Setmemorysize(default=1024)2-Selectmemoryallocationalgorithm3-Newprocess4-Terminateaprocess5-Displaymemoryusage0-Exit(二)、關(guān)鍵算法思想設(shè)計(jì)與分析首次適應(yīng)算法（FirstFit）：從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查

3、找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。最佳適應(yīng)算法（BestFit）：它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開(kāi)始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。 最差適應(yīng)算法（WorstFit）：它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最大的空閑分區(qū)，從而使鏈表中的結(jié)點(diǎn)大小趨于均勻，適用于請(qǐng)求分配的內(nèi)存大小

4、范圍較窄的系統(tǒng)。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按大小從大到小進(jìn)行排序，自表頭開(kāi)始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法保留小的空閑區(qū)，盡量減少小的碎片產(chǎn)生。四測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果設(shè)置內(nèi)存大小選擇算法創(chuàng)建進(jìn)程選擇殺死進(jìn)程查看內(nèi)存以及進(jìn)程五總結(jié)這次實(shí)驗(yàn)剛開(kāi)始的時(shí)候不知道整個(gè)實(shí)驗(yàn)的思路，還好老師在課堂上大概講解了一下，并且給出了大部分代碼，剩下的工作就是填寫部分代碼，這樣實(shí)驗(yàn)就簡(jiǎn)單多了。通過(guò)本次的內(nèi)存實(shí)驗(yàn)我了解到了內(nèi)存的管理模型的知識(shí)，在內(nèi)存緊縮合并回收部分還遇到了一些問(wèn)題，最終通過(guò)查資料解決了問(wèn)題，雖然對(duì)內(nèi)存的管理掌握得不是很熟練，但這激勵(lì)了我下來(lái)后看書(shū)，努力學(xué)習(xí)不懂的知識(shí)，

5、通過(guò)讓我對(duì)其有了更加深入的了解，讓我認(rèn)識(shí)到了，操作系統(tǒng)是一項(xiàng)真正實(shí)用，而且很有意義的學(xué)科，增加了我對(duì)操作系統(tǒng)的興趣，也為以后的學(xué)習(xí)打下理論基礎(chǔ)。六、源代碼#include#include#include#include#define PROCESS_NAME_LEN 32 /進(jìn)程名長(zhǎng)度#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/*描述每一

6、個(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)識(shí)符int size;/進(jìn)程大小int start_addr;/進(jìn)程分配到的內(nèi)存塊的起始地址char process_namePROCESS_NAME_LE

7、N;/進(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 = 0;/設(shè)置內(nèi)

8、存大小標(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 kill_pr

9、ocess();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 allocated_b

10、lock *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);/ 通過(guò)內(nèi)存緊縮技術(shù)給新進(jìn)程分配內(nèi)存空間int mem_retrench(struct allocated_block *ab)struct allocated_block *allocated_work, *allocated_pre = allocated

11、_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-size;allocated_pre = allocat

12、ed_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 = free_work;if(free_pre != NULL)free_work = free_work-

13、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 = allocate_free_block-start_addr;if(allocate_free_block-size - ab

14、-size 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 += ab-size;allocate_free_block-size -= ab-size;if(p = NULL)allocated_block_head = ab;elsewhile(p-next != NULL)p =

15、 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_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(curren

16、t_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_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);

17、break;pre = bf;pre = pre-next;if(bf = NULL & current_free_mem_size ab-size)ret = mem_retrench(ab);elseret = -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

18、)if(ff-size = ab-size)ret = allocate(pre, ff,ab);break;pre = ff;pre = pre-next;if(ff = NULL & 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 = a

19、b-size;fbt = pre = free_block;switch(ma_algorithm)case MA_FF :ret = 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 *)m

20、alloc(sizeof(struct allocated_block);if(!ab)exit(-5);ab-next = NULL;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 greater

21、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;/頭插法allocated_block_head = ab;re

22、turn 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;if(free_pre != NULL)free_ab = free

23、_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-next;allocated_ab = allocated_ab-next;return 0;/

24、在進(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(ab-next = NULL & ab-pid != pid)printf(Here?2222222n);return NULL;return ab;/顯示當(dāng)前內(nèi)存的使用情況

25、，包括空閑區(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 Memory:n);printf(%20s %20sn, start_addr, size);while(fbt != NULL)printf(%20d %20dn, fbt-start_addr, fbt-size);fbt = fbt-next;/顯示已分配區(qū)printf(

26、nUsed Memory:n);printf(%10s %20s %10s %10sn, PID, ProcessName, 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 allocated_block *pre, *ab;i

27、f(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 = ab-next;free(ab);return 1;/*將ab所表示的

28、已分配區(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-start_addr;fbt-size = ab-size;fbt-next = NULL;if(

29、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 += work-size;free(work);work = pre-next;elsepre = work;work = work-next;current_free_mem_si

30、ze += ab-size;return 1;/ 刪除進(jìn)程，歸還分配的存儲(chǔ)空間，并刪除描述該進(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 = 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(

31、)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 next;rear = pre-next;while(pre-next != NULL)if(forehand = head & forehand-start_addr = pre-start_addr)/比較空閑鏈表中第一個(gè)空閑塊與第二個(gè)空閑塊的開(kāi)始地址的大小head-next = pre-next;pre-next =

32、 head;head = pre;forehand = head-next;pre = forehand-next;rear = pre-next;else if(pre-start_addr = rear-start_addr)/比較鏈表中其他相鄰兩節(jié)點(diǎn)的開(kāi)始地址的大小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)存空閑塊鏈表

33、,按空閑塊大小從小到大排序。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 next;rear = pre-next;while(pre-next != NULL)if(forehand = head & forehand-size size)/比較空閑鏈表中第一個(gè)空閑塊與第二個(gè)空閑塊的空間的大小head-next = pre-next

34、;pre-next = head;head = pre;forehand = head-next;pre = forehand-next;rear = pre-next;else if(pre-size 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;/按WF算法重新整理內(nèi)存空閑塊鏈表,按空閑塊大小從大到小

35、排序。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(i = 0; i next;rear = pre-next;while(pre-next != NULL)if(forehand = head & forehand-size = pre-size)/比較空閑鏈表中第一個(gè)空閑塊與第二個(gè)空閑塊空間的大小head-next = pre-next;pre-n

36、ext = 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 = rear;rear-next = pre;forehand = rear;rear = pre-next;elseforehand = pre;pre = rear;rear = rear-next;return 0;/按指定的算法整理內(nèi)存空閑塊鏈表。void rearr

37、ange(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(t3 - Worst Fit n);/最壞適應(yīng)算法printf(nPlease choose(13):);for(; ; )scanf(%d, &algorithm);getchar();if(algorithm = 1 & algorithm 0)current_free_mem_size = siz