操作系统实验报告4
实验四 内存分配器的实现
- 实习编号：操作系统实验_实验_4
- 实习名称：内存分配器的实现
- 巩固知识点
- 了解并熟悉Linux操作系统的常用命令操作；
- 了解基于Linux的功能开发。
- 实习对应培养点
- 学习使用Linux环境编写C程序；
- 学习内存管理的开发相关知识。
- 实验目的
- 熟悉掌握基于Linux的程序开发环境配置与使用；
- 熟悉掌握常用内存管理开发知识点以及系统指令。
- 实验内容和步骤
【任务1】 实现简单的内存分配器
C语言中内存在使用之前必须为其分配空间，使用结束后要释放，否则会发生内存泄漏。申请和释放内存空间使用malloc和free这两个函数。malloc申请的空间在程序的堆中。本实验就是要你实现你自己的mymalloc和myfree，利用标准库的malloc和链表去模拟实现简单的内存分配器，实现mymalc.c文件。
函数原型如下：
void *mymalloc(int size); //分配大小为size的一块内存
void myfree(void *ptr); //释放ptr指针指向的一块内存
实现提示：
1、为了简单起见，我们的程序在运行开始时预先申请了一块内存作为我们的堆：
#define MAXMEM 64000
2、我们的堆里的每一块内存均有一个结构mymalc描述，不管这个内存块是空闲的还是已被分配的，这个结构描述如下：
struct mymalc
{
int id;
int size;
int status; // 0：自由；1:已分配
char *p; // 指向返回给用户的指针
struct mymalc *nextchunk; // 指向下一个内存块
};
所有的mymalc构成了一个单链表，表头指针是一个全局变量：
struct mymalc *my_mem_head;
链表的每一个节点之后紧跟的是一块大小为size的内存块。
3、你的程序开始时，需要首先调用myinit（）：
void myinit() { //初始化你的内存分配系统
my_mem_head=(struct mymalc *)malloc(MAXMEM);
my_mem_head->id=1;
my_mem_head->status=0;
my_mem_head->nextchunk=NULL;
my_mem_head->p=(char *)my_mem_head+sizeof(struct mymalc); // p represents the block of data
my_mem_head->size=MAXMEM - sizeof(struct mymalc); // available size should exclude the size of the block of meta data
}
显然，你的程序刚开始运行时，这个链表只有一个节点，整个堆空间是一个大的自由空间。随着你的程序的逐步运行，这个堆空间会变得支离破碎，链表也有了多个节点。
4、实现以下3个函数完成内存分配管理的模拟功能：
（1） mymalloc函数所完成的功能是根据应用所需要申请的内存数量，在堆中分配指定的数量内存。大致过程：在链表中找到一块大于要求数量的空闲内存，将这块内存一分为二，一部分分配给应用，另一部分标识为空闲，修改内存链表。
（2）myfree释放指定的内存。释放掉的内存如果前面或后面也是空闲块，需要将相邻的空闲块合并。
（3）disp_mem_link便于调试使用。该函数的作用是打印出目前内存链表中各个节点的相关信息，比如数据块编号、size、是否空闲以及p的指针。
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#define MAXMEM 64000 //划定最大堆区内存
int id = 0;//初始化id
struct mymalc//内存块结构
{
int id;
int size;
int status;
char *p;
struct mymalc *nextchunk;
};
struct mymalc* head_mem = NULL;
void initialize_headmem()//初始化堆区首节点
{
head_mem =(struct mymalc*)malloc(MAXMEM);//申请MAXMEM大小的堆区内存给head_mem
head_mem->id = id++;
head_mem->size = MAXMEM-sizeof(struct mymalc);
head_mem->status = 0;
head_mem->nextchunk = NULL;
head_mem->p = (char*)head_mem+sizeof(struct mymalc);
printf("初始化成功！\n");
printf("目前总可用内存为size:%d\n",head_mem->size);
}
char* my_malloc(int need_size)//开辟新节点并分配内存
{
struct mymalc* cur = head_mem;
//struct mymalc* pre = NULL;
struct mymalc* id_max = head_mem;
//while(1)
{
}
while(cur!=NULL)
{
if(cur->status == 0&&cur->size>=need_size)//
{
if(cur->size>need_size+sizeof(struct mymalc))//创建新内存块
{
struct mymalc* new_mem = (struct mymalc*)(cur->p + need_size);
new_mem->size = cur->size - need_size - sizeof(struct mymalc);
new_mem->nextchunk = NULL;
new_mem->p = (char*)new_mem + sizeof(struct mymalc);
new_mem->id = id++;
new_mem->status = 0;
cur->size = need_size;
new_mem->nextchunk = cur->nextchunk;
cur->nextchunk = new_mem;
}
printf("内存开辟成功\n");
cur->status = 1;
return cur->p;
}
cur = cur->nextchunk;
}
printf("内存开辟失败\n");
return NULL;
}
void my_free(char *ptr)//释放当前指针内存
{
struct mymalc* cur = head_mem;
struct mymalc* pre = NULL;
while(cur!=NULL)
{
if(cur->p==ptr)
{
break;
}
pre = cur;
cur = cur->nextchunk;
}
if(cur==NULL||cur->status == 0)
{
if(cur == NULL)
printf("未找到对应地址\n");
else
printf("该地址已经释放\n");
return;
}
if(pre != NULL&&cur->nextchunk!=NULL)//该地址前后内存块status均为0，前后内存合并
{
if(pre->status == 0&&cur->nextchunk->status == 0)//该判断位于cur->nextvhunk!=NULL,避免内存非法访问
{
pre->size = pre->size + cur->size + cur->nextchunk->size + 2*sizeof(struct mymalc);
pre->nextchunk = cur->nextchunk->nextchunk;
return;
}
}
if(cur->nextchunk!=NULL)//该地址后的内存块也为0，后内存合并
{
if(cur->nextchunk->status == 0)
{
cur->size = cur->size + cur->nextchunk->size + sizeof(struct mymalc);
cur->nextchunk = cur->nextchunk->nextchunk;
cur->status = 0;
return;
}
}
if(pre != NULL)//该地址的前内存块也为0，前内存合并
{
if(pre->status == 0)
{
pre->size = pre->size + cur->size + sizeof(struct mymalc);
pre->nextchunk = cur->nextchunk;
return;
}
}
//前后均不为0
{
printf("!\n");
cur->status = 0;
}
}
void disp_memchunk()//逐个打印内存块信息
{
struct mymalc* cur = head_mem;
while(cur != NULL)
{
printf("id:%d\t",cur->id);
printf("size:%d\t",cur->size);
printf("status:%d\n",cur->status);
printf("p:%p\n",cur->p);
cur = cur->nextchunk;
}
}
int main()
{
head_mem = (struct mymalc*)malloc(sizeof(struct mymalc));
initialize_headmem();
char *p1, *p2, *p3;
char *p[10];
int a = 0, i;
printf("-------------Test stage 1 ------------------------\n");
p1 = my_malloc(99);
p2 = my_malloc(999);
disp_memchunk();
printf("p1=%p\n", (void *)p1);
my_free(p1);
disp_memchunk();
printf("\n");
p3 = my_malloc(51);
disp_memchunk();
printf("p3=%p\n", (void *)p3);
printf("\n");
my_free(p2);
disp_memchunk();
printf("\n");
my_free(p3);
disp_memchunk();
printf("\n");
printf("-------------Test stage 2 ------------------------\n");
a = 64;
for (i = 0; i < 10; i++) {
p[i] = my_malloc(a);
printf("p[%d]=%p \n", i, (void *)p[i]);
}
disp_memchunk();
printf("\n");
my_free(p[2]);
disp_memchunk();
printf("\n");
my_free(p[3]);
disp_memchunk();
printf("\n");
my_free(p[4]);
p1 = my_malloc(1500);
disp_memchunk();
return 0;
}