操作系统 动态分区存储管理（最坏分配算法）

• 前言
• 一、实验内容
• 二、实验环境
• 三、代码
• 四、结果
• 总结

通过这次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想

阅读教材《计算机操作系统》第四章，掌握存储器管理相关概念和原理。
编写程序模拟实现内存的动态分区法存储管理。内存空闲区使用空闲分区链管理，采用最坏适应算法从空闲分区链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。
假定系统的内存共640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。

Windows操作系统、vscode、C语言

#include 
#include 

struct freelink
{
	int len, address; 
	struct freelink *next;
};

struct busylink
{
	char name; 
	int len, address;
	struct busylink *next;
};

struct freelink *free_head = NULL; //空闲分区链队列（带头结点）队首指针
struct busylink *busy_head = NULL; //占用区队列队（带头结点）首指针
struct busylink *busy_tail = NULL; //占用区队列队尾指针

void start()
{
	free_head = (struct freelink *)malloc(sizeof(struct freelink));
	struct freelink *f = (struct freelink *)malloc(sizeof(struct freelink));
	free_head->next = f;
	f->address = 64;
	f->len = 640 - 64;
	f->next = NULL;
	struct busylink *b = (struct busylink *)malloc(sizeof(struct busylink));
	busy_head = b;
	busy_tail = b;
	b->len = 64;
	b->address = 0;
	b->name = 'S';
} 

void requireMemo(char name, int require)
{
	if (free_head->next->len >= require)
	{
		struct busylink *p = (struct busylink *)malloc(sizeof(struct busylink));
		p->name = name;
		p->address = free_head->next->address;
		p->len = require;
		p->next = NULL;
		busy_tail->next = p;
		busy_tail = p;
	}
	else
	{
		printf("Can not allocate");
		return;
	}

	struct freelink *w = (struct freelink *)malloc(sizeof(struct freelink));
	w = free_head->next;
	free_head->next = w->next;
	if (w->len == require)
	{
		free(w);
		return;
	}
	else
	{
		w->address = w->address + require;
		w->len = w->len - require;
		struct freelink *v = (struct freelink *)malloc(sizeof(struct freelink));
		struct freelink *u = (struct freelink *)malloc(sizeof(struct freelink));
		u = free_head;
		v = free_head->next;
		while ((v != NULL) && v->len > w->len)
		{
			u = v;
			v = v->next;
		}
		u->next = w;
		w->next = v;
	}
} 

void freeMemo(char name)
{
	struct busylink *q = (struct busylink *)malloc(sizeof(struct busylink));
	q = busy_head;
	struct busylink *p = (struct busylink *)malloc(sizeof(struct busylink));
	p = busy_head->next;
	while ((p != NULL) && (p->name != name))
	{
		q = p;
		p = p->next;
	}
	if (p == NULL)
	{
		printf("%c is not exist", name);
		return;
	}
	if (p == busy_tail)
		busy_tail = q;
	q->next = p->next;
	int len, address;
	len = p->len;
	address = p->address;
	free(p);
	struct freelink *w = (struct freelink *)malloc(sizeof(struct freelink));
	w->len = len;
	w->address = address;
	struct freelink *v = (struct freelink *)malloc(sizeof(struct freelink));
	struct freelink *u = (struct freelink *)malloc(sizeof(struct freelink));
	u = free_head;
	v = free_head->next;
	while ((v != NULL) && (v->len > len))
	{
		u = v;
		v = v->next;
	}
	u->next = w;
	w->next = v;
} 

void past(int time)
{
	printf("%ds时间后:n", time);
} 

void printfreelink()
{
	printf("内存空闲区：n");
	printf("空闲的长度t空闲区域的首地址n");
	struct freelink *f = (struct freelink *)malloc(sizeof(struct freelink));
	f = free_head->next;
	while (f != NULL)
	{
		printf("%dtt%dn", f->len, f->address);
		f = f->next;
	}
	printf("n");
}


void printbusylink()
{
	printf("内存占用区：n");
	printf("作业名称t占用的长度t首地址n");
	struct busylink *b = (struct busylink *)malloc(sizeof(struct busylink));
	b = busy_head;
	while (b)
	{
		printf("%ctt%dtt%dn", b->name, b->len,b->address);
		b = b->next;
	}
	printf("-----------------------------------n");
} 

void main()
{
	int t1 = 1, t2 = 2, t3 = 3, t4 = 4;
	start();
	past(t1);
	requireMemo('A', 8);
	requireMemo('B', 16);
	requireMemo('C', 64);
	requireMemo('D', 124);
	printfreelink();
	printbusylink();

	past(t2);
	freeMemo('C');
	printfreelink();
	printbusylink();

	past(t3);
	requireMemo('E', 50);
	printfreelink();
	printbusylink();

	past(t4);
	freeMemo('D');
	printfreelink();
	printbusylink();
}

经过这次实验，我对主存空间的分配和回收有了深一步的了解，同时也初步了解了内存空间的工作原理。在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。