西安邮电大学操作系统内存管理实验报告含源码

1、 西 安 邮 电 大 学 （计算机学院）课内实验报告实验名称： 内存管理 专业名称： 软件工程班 级： 1201班 学生姓名： 学号（8位）： 指导教师： 实验日期： 2014年11月25日1. 实验目的及实验环境(一)、实验环境1. 硬件(1) 主机：Pentium III 以上；(2) 内存：128MB 以上；(3) 显示器：VGA 或更高；(4) 硬盘空间：至少100MB 以上剩余空间。2. 软件Ubuntu下gcc编译器、gdb调试工具。(二)、实验目的(1)、掌握内存分配FF，BF，WF策略及实现的思路； (2)、掌握内存回收过程及实现思路； (3)、参考本程序思

2、路，实现内存的申请、释放的管理程序，调试运行，总    结程序设计中出现的问题并找出原因。二、实验内容（1)补充完整FF，BF，WF等算法的代码； （2)掌握内存回收过程及实现思路；（3)实现内存的申请和释放。三方案设计（一）、实现功能1 - Set memory size (default=1024) 2 - Select memory allocation algorithm3 - New proces

3、s4 - Terminate a process5 - Display memory usage 0 - Exit (二)、关键算法思想设计与分析 首次适应算法（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

4、0;     最佳适应算法（Best Fit）：它从全部空闲区中找出能满足作业要求的、 且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分 区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到 第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的 空闲区。        最差适应算法（Worst Fit）：它从全部空闲区中找出能满足作业要求的、 且大小最大的空闲分

5、区，从而使链表中的结点大小趋于均匀，适用于请求分 配的内存大小范围较窄的系统。为适应此算法，空闲分区表（空闲区链）中 的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求 的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。四测试数据及运行结果设置内存大小选择算法创建进程选择杀死进程查看内存以及进程五总结这次实验刚开始的时候不知道整个实验的思路，还好老师在课堂上大概讲解了一下，并且给出了大部分代码，剩下的工作就是填写部分代码，这样实验就简单多了。通过本次的内存实验我了解到了内存的管理模型的知识，在内存紧缩合并回收部分还遇到了一些问题，最终通过

6、查资料解决了问题，虽然对内存的管理掌握得不是很熟练，但这激励了我下来后看书，努力学习不懂的知识，通过让我对其有了更加深入的了解，让我认识到了，操作系统是一项真正实用，而且很有意义的学科，增加了我对操作系统的兴趣，也为以后的学习打下理论基础。六、源代码#include<stdio.h>#include<malloc.h>#include<unistd.h>#include<stdlib.h>#define PROCESS_NAME_LEN 32 /进程名长度#define MIN_SLICE 10 /最小碎片的大小#define DEFAULT_M

7、EM_SIZE 1024/内存大小#define DEFAULT_MEM_START 0 /起始位置/*内存分配算法*/#define MA_FF 1#define MA_BF 2#define MA_WF 3/*描述每一个空闲块的数据结构*/struct free_block_typeint size;/空闲块大小int start_addr;/空闲块起始地址struct free_block_type *next;/指向下一个空闲块;/*指向内存中空闲块链表的首指针*/struct free_block_type *free_block = NULL;/*每个进程分配到的内存块的描述*/s

8、truct allocated_blockint pid;/进程标识符int size;/进程大小int start_addr;/进程分配到的内存块的起始地址char process_namePROCESS_NAME_LEN;/进程名struct allocated_block *next;/指向下一个进程控制块;/*进程分配内存块链表的首指针*/struct allocated_block *allocated_block_head = NULL;int free_block_count = 0;/空闲块个数int mem_size = DEFAULT_MEM_SIZE; /内存大小int

9、current_free_mem_size = 0;/当前空闲内存大小int ma_algorithm = MA_FF; /当前分配算法static int pid = 0; /初始PIDint flag = 0;/设置内存大小标志,表示内存大小是否设置/*函数声明*/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();in

10、t rearrange_BF();int rearrange_FF();int new_process();int allocate_mem(struct allocated_block *ab);void kill_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 allocat

11、e_FF(struct allocated_block *ab);int allocate_BF(struct allocated_block *ab);int allocate_WF(struct allocated_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);/ 通过内存紧缩技术给新进程分配内存空

12、间int mem_retrench(struct allocated_block *ab)struct allocated_block *allocated_work, *allocated_pre = allocated_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;whi

13、le(allocated_work != NULL)allocated_work->start_addr = allocated_pre->start_addr + allocated_pre->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

14、_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->next;allocate(NULL, free_block, ab);return 1;/ 给新进程分配内存空间 int allocate(struct free_block_type *pre, struct free_block_type *allocate_free

15、_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->size < MIN_SLICE)ab->size = allocate_free_block->size;if(pre != NULL)pre->next = allocate_free_block;elsefre

16、e_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 = p->next;p->next = ab;current_free_mem_size -= ab->size;if

17、(current_free_mem_size = 0)free_block = NULL;return 0;/按照最坏适应算法给新进程分配内存空间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(current_free_mem_size >= ab->size)ret = mem

18、_retrench(ab);elseret = -2;rearrange_WF();return ret;/ 按照最佳适应算法给新进程分配内存空间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);break;pre = bf;pre = pr

19、e->next;if(bf = NULL && current_free_mem_size > ab->size)ret = mem_retrench(ab);elseret = -2;rearrange_BF();return ret;/ 按照首次适应算法给新进程分配内存空间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)

20、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;/分配内存模块int allocate_mem(struct allocated_block *ab)int ret ;struct free_block_typ

21、e *fbt, *pre;int request_size = ab->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;/ 创建一个新的进程。int new_process()struct allocated_block *ab;int size;int

22、 ret;ab = (struct allocated_block *)malloc(sizeof(struct allocated_block);if(!ab)exit(-5);ab->next = NULL;pid+;sprintf(ab->process_name, "PROCESS-%02d", pid);/sprintf()函数将格式化的数据写入某字符串中ab->pid = pid; printf("Memory for %s:", ab->process_name);for(; ; )scanf("%d&qu

23、ot;, &size);getchar();if(size > 0)ab->size = size;break;elseprintf("The size have to greater than zero! Please input again!");ret = allocate_mem(ab); /从空闲区分配内存，ret=1表示分配okif(ret = 1) && (allocated_block_head = NULL)/如果此时allocated_block_head尚未赋值，则赋值 /进程分配链表为空allocated_bloc

24、k_head = ab;return 1;else if(ret = 1) /分配成功，将该已分配块的描述插入已分配链表ab->next = allocated_block_head;/头插法allocated_block_head = ab;return 2;else if(ret = -1) /分配不成功printf("Allocation failn");free(ab);return -1; return 3;/退出程序并释放内存空间。int do_exit()struct allocated_block *allocated_ab, *allocated_p

25、re;struct free_block_type *free_ab, *free_pre;free_pre = free_block;allocated_pre = allocated_block_head;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;w

26、hile(allocated_ab != NULL)free(allocated_pre);allocated_pre = allocated_ab;allocated_ab = allocated_ab->next;allocated_ab = allocated_ab->next;return 0;/在进程分配链表中寻找指定进程。struct allocated_block *find_process(int pid)struct allocated_block *ab = allocated_block_head;if(ab = NULL)printf("Here?

27、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;/显示当前内存的使用情况，包括空闲区的情况和已经分配的情况。int display_mem_usage()struct free_block_type *fbt = free_blo

28、ck;struct allocated_block *ab = allocated_block_head;printf("-n");/显示空闲区printf("Free Memory:n");printf("%20s %20sn", " start_addr", " size");while(fbt != NULL)printf("%20d %20dn", fbt->start_addr, fbt->size);fbt = fbt->next;/显示已分配区

29、printf("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

30、;printf("-n");return 1;/ 释放ab数据结构节点。int dispose(struct allocated_block *free_ab)struct allocated_block *pre, *ab;if(free_block = NULL)return -1;if(free_ab = allocated_block_head)/如果要释放第一个节点allocated_block_head = allocated_block_head->next;free(free_ab); elsepre = allocated_block_head; a

31、b = allocated_block_head->next;/找到free_abwhile(ab != free_ab)pre = ab;ab = ab->next;pre->next = ab->next;free(ab);return 1;/*将ab所表示的已分配区归还，并进行可能的合并*/int free_mem(struct allocated_block *ab)int algorithm = ma_algorithm;struct free_block_type *fbt, *pre, *work;fbt = (struct free_block_type

32、*)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(pre != NULL)while(pre->next != NULL)pre = pre->next;pre->next = fbt;elsefree_block = fbt;rearrange_FF();pre = free_block;work =

33、 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_size += ab->size;return 1;/ 删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点。void kill_process()struct alloca

34、ted_block *ab;int pid;printf("Kill Process, pid=");scanf("%d", &pid);getchar();ab = find_process(pid);if(ab != NULL)free_mem(ab); /*释放ab所表示的分配区*/dispose(ab); /*释放ab数据结构节点*/按FF算法重新整理内存空闲块链表,按空闲块首地址排序。int rearrange_FF()struct free_block_type *head = free_block;struct free_block

35、_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 && forehand->start_addr >= pre->start_addr)/比较空闲链表中第一个空闲块与第二个空闲块的开始地址的大

36、小head->next = pre->next;pre->next = head;head = pre;forehand = head->next;pre = forehand->next;rear = pre->next;else if(pre->start_addr >= rear->start_addr)/比较链表中其他相邻两节点的开始地址的大小pre->next = rear->next;forehand->next = rear;rear->next = pre;forehand = rear;rear =

37、 pre->next;elseforehand = pre;pre = rear;rear = rear->next;return 0;/ 按BF算法重新整理内存空闲块链表,按空闲块大小从小到大排序。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 =

38、head;pre = forehand->next;rear = pre->next;while(pre->next != NULL)if(forehand = head && forehand->size <= pre->size)/比较空闲链表中第一个空闲块与第二个空闲块的空间的大小head->next = pre->next;pre->next = head;head = pre;forehand = head->next;pre = forehand->next;rear = pre->next;e

39、lse if(pre->size <= rear->size)/比较链表中其他相邻两节点的空间的大小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算法重新整理内存空闲块链表,按空闲块大小从大到小排序。int rearrange_WF()struct free_block_type

40、 *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 && forehand->size >= pre->size)/比较

41、空闲链表中第一个空闲块与第二个空闲块空间的大小head->next = pre->next;pre->next = head;head = pre;forehand = head->next;pre = forehand->next;rear = pre->next;else if(pre->size >= rear->size)/比较链表中其他相邻两节点的空间的大小pre->next = rear->next;forehand->next = rear;rear->next = pre;forehand = rea

42、r;rear = pre->next;elseforehand = pre;pre = rear;rear = rear->next;return 0;/按指定的算法整理内存空闲块链表。void rearrange(int algorithm)switch(algorithm)case MA_FF:rearrange_FF();break;case MA_BF:rearrange_BF();break;case MA_WF:rearrange_WF();break;/设置当前的分配算法void set_algorithm()int algorithm;/system("c

43、lear");printf("t1 - First Fitn");/首次适应算法printf("t2 - Best Fit n");/最佳适应算法printf("t3 - Worst Fit n");/最坏适应算法printf("nPlease choose(13):");for(; ; )scanf("%d", &algorithm);getchar();if(algorithm >= 1 && algorithm <= 3) ma_algorit

44、hm = algorithm;break;elseprintf("nCannot input %d, Please input 13 : ", algorithm);/按指定算法重新排列空闲区链表 rearrange(ma_algorithm); /设置内存的大小int set_mem_size()int size;if(flag != 0)/防止重复设置 printf("Cannot set memory size againn"); return 0; printf("Total memory size = ");for(; ; )scanf("%d", &size);getchar();if(size >