memoryassign.cpp

操作系统实验模拟

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

#define  BLOCK_SIZE		500				//初始空闲分区大小
#define  NULL			0

typedef struct Node{
	int				start_address;		//空闲区首地址
	int				block_size;			//空闲区大小
	struct Node*	prior;				//前向指针
	struct Node*	next;				//后向指针
	int				state;				//空闲区状态
}Node,*LinkList;

LinkList	L;							//指向用户存储区的首地址
LinkList	Free;						//空闲分区链表头指针
LinkList	Assigned;					//已分配区链表头指针

//--------------------------------------------------------------
void InitBlock(void) //初始化
{
	L = (LinkList)malloc(sizeof(Node));
	
	L->start_address = 0;
	L->block_size = BLOCK_SIZE;
	L->prior = NULL;
	L->next = NULL;
	L->state = 0;
	
	Free = (LinkList)malloc(sizeof(Node));		//建立空闲区链表(含头指针)
	Assigned = (LinkList)malloc(sizeof(Node));	//建立分配区链表(含头指针)

	Assigned->block_size = Free->block_size = 0;
	Assigned->start_address = Free->start_address = 0;
	Assigned->prior = Free->prior = NULL;
	Assigned->next = Free->next = NULL;
	Assigned->state = Free->state = 0;


	//printf("\n初始化空闲块成功\n");
}
//--------------------------------------------------------------
void Display(void)		//显示存储区分配情况
{
	LinkList p;

	printf("****存储区情况****:\n");
	printf("已经分配区有:\n");
	for(p = L;p != NULL;p = p->next)
	{
		if(p->block_size == 0)	continue;
		if(p->state == 1)
		{		
			printf("(%3d,%3d)\n",p->start_address ,p->block_size);
		}
	}

	printf("空闲区有:\n");
	for(p = L;p != NULL;p = p->next)
	{
		if(p->block_size == 0)	continue;
		if(p->state == 0)
		{		
			printf("(%3d,%3d)\n",p->start_address ,p->block_size);
		}
	}
}
//--------------------------------------------------------------
void Tighten(void)//紧凑算法
{
	int flag;
	LinkList p,q;

	flag = 0;
	p = L;   
	
	for(;p != NULL;p = p->next)
	{
		if(p->state == 0 && flag == 0)
		{
			q = p;
			if(p->prior != NULL)
			{
				p->prior->next = p->next ;
				p->state = 1;
			}
			flag = 1;					//标记 已找到要移动的空闲区
			p = p->next ;
		}

		if(flag == 1)				
		{
			for(;p->state == 1 && p != NULL;p = p->next)
			{
				p->start_address = p->start_address - q->block_size;	//移动空闲区后的已分配区
			}
		}

		if(p->state == 0 && flag == 1)	//找到后面的空闲区,合并
		{
			p->start_address = p->start_address - q->block_size ;
			p->block_size = p->block_size + q->block_size ;
		}
	}

	printf("紧凑后:\n");
	Display();
}

//--------------------------------------------------------------
void FirstAdapt(void)//首次适应算法
{
	int progress_size;
	int success;							//是否分配成功
	int sum;								//空闲区总大小
	char y_n;
	LinkList  p,q;
	Display();
				
	printf("\n请输入进程需要的存储空间:\n");
	scanf("%d",&progress_size);
	
	if(progress_size <= 0)		printf("A wrong number!\n");
	else 
	{
		for(p = L;p != NULL;p = p->next)
		{
			if(progress_size <= p->block_size && p->state == 0)		//找到可用的空闲区
			{
				q = (LinkList)malloc(sizeof(Node));					// q 分配后剩余的存储块（空闲区）

				q->start_address = p->start_address + progress_size;	
				q->block_size = p->block_size - progress_size;
				q->prior = p;
				q->next  = p->next;
				q->state = 0;

				if(q->block_size != 0)
				{
					p->next = q;
				}
				p->block_size = progress_size;				// p 指向已分配的块单元
				p->state = 1;
		
				success = 1;
				break;
			}
			else continue;
		}

		if(success == 1)		//成功分配
		{
			Display();
		}
		else					//暂时未能成功分配
		{
			sum = 0;
			for(p = L;p != NULL;p = p->next )
			{
				if(p->state == 0)
					sum = sum + p->block_size ;			//计算总的空闲区大小
			}
			if(sum >= progress_size)
			{
				printf("\n存储区大小不足，是否紧凑?(Y/N)\n");
				getchar();
				scanf("%c",&y_n);
				if(y_n == 'Y' || y_n == 'y')
					Tighten();	//执行紧凑
			}
			else 
				printf("\n存储区大小不足，分配失败\n");
		}
	}
}//FirstAdapt
//--------------------------------------------------------------
void swap(LinkList p,LinkList q)//交换节点
{
	p->block_size = q->block_size ;
	p->start_address = q->start_address ;
	p->state = q->state ;
}


//--------------------------------------------------------------
void SortFree(LinkList Free)		//空闲区排序(从小到大)
{
	LinkList p,q,t;

	t = (LinkList)malloc(sizeof(Node));

	for(p = Free->next;p != NULL;p = p->next )
	{
		q = p;
		for(;q != NULL;q = q->next )
			if(q->block_size < p->block_size )
			{
				swap(t,q);
				swap(q,p);
				swap(p,t);
			}
	}
}
//--------------------------------------------------------------
void EvaluateLink(void)
{
	LinkList p,q,r,s;
	
	q = Free;
	s = Assigned;
	
	for(p = L;p != NULL;p = p->next)
	{
		if(p->state == 0)						//查找 L 中空闲分区
		{
			r = (LinkList)malloc(sizeof(Node));

			r->start_address = p->start_address;
			r->block_size = p->block_size ;
			r->state = p->state ;
			r->next = NULL;

			q->next = r;
			q->next->prior = q;
			q = q->next ;
		}

		else if(p->state == 1)					//查找 L 中已分配分区
		{
			r = (LinkList)malloc(sizeof(Node));
			
			r->start_address = p->start_address ;
			r->block_size = p->block_size ;
			r->state = p->start_address ;
			r->next = p->next;

			s->next = r;
			s->next->prior = s;
			s = s->next;
		}
	}
}
//--------------------------------------------------------------
void BestAdapt(void)	//最佳适应算法
{
	int progress_size;	//新增进程所需空间大小
	int success;		//是否分配成功
	int sum;			//空闲区总大小
	char y_n;
	LinkList p,q,r;
	LinkList A,F;

	Display();

	EvaluateLink();

	SortFree(Free);		//空闲区链表排序

	printf("\n请输入进程需要的存储空间:\n");
	scanf("%d",&progress_size);

	A = Assigned;
	F = Free;

	if(progress_size <= 0) printf("A wrong number\n");
	else
	{
		for(p = Free->next;p != NULL;p = p->next)
		{
			if(progress_size <= p->block_size)
			{
				q = (LinkList)malloc(sizeof(Node));			// q 分配后剩余的空闲块
	
				q->start_address = p->start_address + progress_size;	
				q->block_size = p->block_size - progress_size;
				q->prior = p;
				q->next  = p->next;
				q->state = 0;
	
				p->next = q;
				p->block_size = progress_size;				// p 指向已分配的块单元
				p->state = 1;
	
				p->next = Assigned->next ;
				A->next = p;
	
				q->next = Free->next;
				F->next = q;

				success = 1;

				for(r = L;r != NULL;r = r->next )
				{
					if(r->start_address == p->start_address )
					{
						r->start_address = p->start_address ;
						r->block_size = p->block_size ;
						r->state = 1;

						q->next = r->next ;
						r->next = q;
					}
				}
				break;
			}
			else continue;
		}

		if(success == 1)
		{
			Display();
		}
		else
		{
			sum = 0;
			for(p = L;p != NULL;p = p->next )
			{
				if(p->state == 0)
					sum = sum + p->block_size ;			//计算总的空闲区大小
			}
			if(sum >= progress_size)
			{
				printf("\n存储区大小不足，是否紧凑?(Y/N)\n");
				getchar();
				scanf("%c",&y_n);
				if(y_n == 'Y' || y_n == 'y')
					Tighten();	//执行紧凑
			}
			else 
				printf("\n存储区大小不足，分配失败\n");
		}
	}
}//BestAdapt

//--------------------------------------------------------------
void Callback(void)						//存储区回收函数
{
	int i;
	int x;
	LinkList p;

	printf("已经分配区有:\n");
	for(i = 0,p = L;p != NULL;p = p->next)		//显示已分配区
	{
		if(p->state == 1)
		{		
			printf("%d.\t(%3d,%3d)\n",i+1,p->start_address ,p->block_size);
			i++;
		}
	}

	printf("请输入需要撤消的进程编号:\n");
	scanf("%d",&x);

	for(i = 0,p = L;p != NULL;p = p->next)
	{
		if(p->state == 1) i++;
		if(i == x)
		{
			p->state = 0;						//回收后状态位置
			break;
		}
	}

	for(p = L;p->next != NULL;)		
	{
		if(p->state == 0 && p->next->state == 0)
		{
			p->block_size = p->block_size + p->next->block_size ;		//改变空闲块大小
			p->next = p->next->next ;
			if(p->next != NULL)
			{
				p->next->prior = p;
			}
		}
		else	p = p->next ;
	}

	Display();
}//回收算法

//--------------------------------------------------------------
void main(void)
{
	int i;
	int choice;

	printf("存储器动态分区分配演示系统\n");
	
	InitBlock();			//初始化空闲块

	for(i = 0;;i++)
	{
		printf("\n请选择操作:\n");
		printf("--------------------------------------\n");
		printf("\t1.\t首次适应算法分配内存\n");
		printf("\t2.\t最佳适应算法分配内存\n");
		printf("\t3.\t回收存储区\n");
		printf("\t0.\t退出\n");
		printf("--------------------------------------\n");
			
		scanf("%d",&choice);
		if(choice == 1)	 FirstAdapt();
		else if(choice == 2)  BestAdapt();
		else if(choice == 3)	 Callback();
		else if(choice == 0)	 {printf("谢谢使用\n");break;}
		else {printf("A wrong choice!\n");getchar();}
	}
}