操作系统实验：首次适应算法、最佳适应算法、最坏适应算法

1、首次适应算法

概念：首次适应算法从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。

实验要求：已知作业名、作业大小、作业提交时间、内存容量、碎片大小，要求使用分区大小不等的内存分区方法和首次适应分配算法给每次到来的作业分配内存。输出内存分区情况和分配情况。

#include 
using namespace std;
#define FREE 0
#define  BUSY 1
#define  MAX_length 300
const double debri = 20; //设置碎片大小
// FREE代表空闲  BUSY代表已分配 
typedef struct free_area //首先定义空闲区分表结构
{
int flag;
int size;
int number;
int begin_address;
 }Elemtype;
 
typedef struct Free_Node
{
	Elemtype date;
	struct Free_Node *prior;
	struct Free_Node *next;
}Free_Node,*pNod;
 
pNod headNode;
pNod initNode;
int m_allocation();//作业分配
int free(int number);//作业回收
bool ff(int number,int size);//首次适应算法
void show();//查看分配
void init();//初始化
int main()
{
	int tag=0;
	int number;
	init();
	while(tag!=4)
	{
		coutnext=NULL;
	initNode->date.begin_address=0;
	initNode->date.flag=FREE;
	initNode->date.number= 0;
	initNode->date.size=MAX_length;
}
 
//实现作业分配
int m_allocation()
{
	int number,size1;
	coutnumber;
	coutsize1;
	if(ff(number,size1))
	{		
		coutdate.number=number;
			return true;
		}
		if (p->date.flag==FREE && p->date.size>size)//说明还有其他的空闲区间
		{
			temp->next=p;
			temp->prior=p->prior;
			temp->date.begin_address=p->date.begin_address;
			p->prior->next=temp;
			p->prior=temp;
			p->date.begin_address=temp->date.begin_address+temp->date.size;//空闲分区开始地址+此次分配的空间
			p->date.size-=size;      //分配空闲作业
		    return true;
		}
		p=p->next;
	}
	return false;
}
int free(int number)//主存回收
{
	Free_Node *p=headNode->next;
	while(p)
	{
		if (p->date.number==number)//找到要回收的number区域
		{
			p->date.flag=FREE;
			p->date.number=FREE;
			//判断P与前后区域关系
			//1、回收分区r上临一个空闲分区，此时应该合并为一个连续的空闲区，其始址为r上相邻的分区的首地址，而大小为两者大小之和
			if (p->prior->date.flag==FREE&&p->next->date.flag!=FREE)   
			{
				p->prior->date.size+=p->date.size;
				p->prior->next=p->next;  //将要回收分区的前后两个分区链接起来
				p->next->prior=p->prior;
			}
			//2、回收分区r与下相邻空闲分区，合并后仍然为空闲区，该空闲区的始址为回收分区r的地址。大小为两者之和
			else if (p->prior->date.flag!=FREE&&p->next->date.flag==FREE)
			{
				p->date.size+=p->next->date.size;   //合并前后两个分区
				if(p->next->next)      //下一个分区不是最后一个分区
				{
					p->next->next->prior=p;
				    p->next = p->next->next;
				}
				else 
					p->next=p->next->next;
			}
			//3、回收部分r与上下空闲区相邻，此时将这三个区域合并，始址为r上相邻区域的地址，大小为三个分区大小之和
			else if(p->prior->date.flag==FREE&&p->next->date.flag==FREE)
			{
				p->prior->date.size+=p->date.size+p->next->date.size;
				if(p->next->next) //如果最后一个节点不是最后一个节点
				{
				p->next->next->prior=p->prior;
				p->prior->next=p->next->next;
				}
				else p->prior->next=p->next->next;
			}
			//4、当回收部分r上下区域都为非空闲区域，此时建立一个新的空闲分区，并且加入到空闲区队列中去
			else if(p->prior->date.flag!=FREE && p->next->date.flag!=FREE)
			{
				//只用把结点的number和flag改成free就行了
			}
			break;
		}
		p=p->next;
	}
	coutdate.ID==ID)//找到要回收的ID区域
		{
			p->date.flag=FREE;
			p->date.ID=FREE;
			//判断P与前后区域关系
			if (p->front->date.flag==FREE&&p->next->date.flag!=FREE)
			{
				p->front->date.size+=p->date.size;
				p->front->next=p->next;
				p->next->front=p->front;
			}
			if (p->front->date.flag!=FREE&&p->next->date.flag==FREE)
			{
				p->date.size+=p->next->date.size;
				if(p->next->next)
				{
					p->next->next->front=p;
				p->next = p->next->next;
				}
				else p->next=p->next->next;
			}
			if(p->front->date.flag==FREE&&p->next->date.flag==FREE)
			{
				p->front->date.size+=p->date.size+p->next->date.size;
				if(p->next->next)
				{
				p->next->next->front=p->front;
				p->front->next=p->next->next;
				}
				else p->front->next=p->next->next;
			}
			if(p->front->date.flag!=FREE&&p->next->date.flag!=FREE)
			{//
				
			}
			break;
		}
		p=p->next;
	}
	coutdate.flag==FREE)
			{
				p->date.size+=p->next->date.size;
				if(p->next->next)
				{
					p->next->next->front=p;
				p->next = p->next->next;
				}
				else p->next=p->next->next;
			}
			if(p->front->date.flag==FREE&&p->next->date.flag==FREE)
			{
				p->front->date.size+=p->date.size+p->next->date.size;
				if(p->next->next)
				{
				p->next->next->front=p->front;
				p->front->next=p->next->next;
				}
				else p->front->next=p->next->next;
			}
			if(p->front->date.flag!=FREE&&p->next->date.flag!=FREE)
			{//
				
			}
			break;
		}
		p=p->next;
	}
	cout