主存空间的分配与回收.cpp

操作系统实验和实验报告

#include "stdio.h"
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include "iostream.h"
#define getjcb(type)  (type*)malloc(sizeof(type))
#define getsub(type)  (type*)malloc(sizeof(type))
#define NULL 0

int num,num2;  //要调度的作业数和要回收的区域数
int m=0;     //已分配作业数
int flag;     //分配成功标志
int isup,isdown;   //回收区域存在上邻和下邻的标志
int is=0;

struct jcb
{
	char name[10];
	char state;
	int ntime; //所需时间
	int size;  //所需空间大小
    int addr;  //所分配分区的首地址
	struct jcb *link;
} *ready =NULL, *p,*q,*as=NULL;
//作业队列ready,已分配作业队列as
typedef struct jcb JCB;

struct subarea{         //分区块
	char name[10];
	int addr;    //分区首地址
	int size;    //分区大小
	char state;
	struct subarea *link;
} *sub=NULL,*r,*s,*cur;
//空闲分区队列sub,当前分区指针cur
typedef struct subarea SUB;

//--------------------------------------------------------------------------
void sort_sub()     /*对空闲分区按从小到大排序*/
{   
	SUB *first,*second;
    int insert=0;
    if((sub==NULL)||((s->size)<(sub->size)))   /*插在队列之首*/
	{
		s->link=sub;
		sub=s;
	}
    else
	{
		first=sub;        /*寻找适当的位置插入*/
	    second=first->link;
		while(second!=NULL)
		{
			if((s->size)<(second->size))
			{
			   s->link=second;
			   first->link=s;
			   second=NULL;
			   insert=1;
			}
			else
			{
                first=first->link;
			    second=second->link;
			}
		 }
		 if(insert==0)first->link=s;   /*插在队尾*/
	}
} 

//--------------------------------------------------------------------------
void firstsort() /* 建立对作业按到达时间进行排列的函数,直接插在队列之尾 sort*/
{
	JCB *first;
	if(ready==NULL)  ready=p;
	else
	{
		first=ready;
		while(first->link!=NULL)
			first=first->link;
		first->link=p;
		p->link=NULL;
	}
}

//--------------------------------------------------------------------------
void lastsort()      /*建立对已分配作业队列的排列函数,直接插在队列之尾sort3*/
{
	JCB *fir;
	if(as==NULL) as=q;
	else
	{
		fir=as;
		while(fir->link!=NULL)
			fir=fir->link;
		fir->link=q;
		q->link=NULL;
	}
	m++;
}


//--------------------------------------------------------------------------   
void input() /* 建立作业控制块函数*/
{
	int i;
	printf("\n请输入要调度的总作业数:");
	scanf("%d",&num);
	for(i=0;i<num;i++)
	{
	   printf("\n作业号No.%d:\n",i);
	   p=getjcb(JCB);
	   printf("\n输入作业名:");
	   scanf("%s",&p->name);
	   printf("\n输入作业的大小:");
	   scanf("%d",&p->size);
	   printf("\n输入作业所需运行时间:");
	   scanf("%d",&p->ntime);
	   p->state='w';
	   p->link=NULL;
	   firstsort(); /* 调用sort函数*/
	}
	printf("\n 按任一键继续......\n");
	getch();
}

//--------------------------------------------------------------------------
void input2()     /*建立要回收区域的函数*/
{
	 JCB *k;
	 int has;
	 q=getjcb(JCB);
	 printf("\n输入区域名(作业名):");
	 scanf("%s",&q->name);
	 p=as;
	 while(p!=NULL)
	 {
		 if(strcmp(p->name,q->name)==0)  /*在已分配作业队列中寻找*/
		 {
				q->addr=p->addr;
				q->size=p->size;
				has=1;    /*输入作业名存在标志位*/
				if(p==as)  as=p->link;    /*在已分配作业队列中删除该作业*/
				else
				{
					k=as;
					while(k->link!=p)  k=k->link;
					k->link=k->link->link;      /*删除*/
				}
				printf("输出该作业首地址:%d\n",q->addr);
				printf("输出该作业大小:%d\n\n",q->size);
				q->link=NULL;
				break;
		}
		else
		   {p=p->link; has=0;}   /*输入作业名不存在标志*/
	}
	if(has==0)
	{
		printf("\n输入作业名错误!请重新输入!\n");
		input2();
	}  
}

//--------------------------------------------------------------------------
void init_sub()       /*初始化空闲分区表*/
{
	 r=getsub(SUB);
	 strcpy(r->name,"one"); r->addr=5; r->size=10; r->state='n';
	 sub=r;
	 s=getsub(SUB);
	 strcpy(s->name,"two"); s->addr=20; s->size=120; s->state='n';
	 sub->link=s;r=s;
	 s=getsub(SUB);
	 strcpy(s->name,"three"); s->addr=160; s->size=40; s->state='n'; 
	 r->link=s;r=s;
	 s=getsub(SUB);
	 strcpy(s->name,"four"); s->addr=220; s->size=10; s->state='n'; 
	 r->link=s;r=s;
	 s=getsub(SUB);
	 strcpy(s->name,"five"); s->addr=250; s->size=20; s->state='n'; 
	 r->link=s;
	 s->link=NULL;
}


//--------------------------------------------------------------------------
void disp()    /*空闲分区表的显示函数*/
{
	 printf("\t\t 分区          首地址           长度          状态 \n");
	 r=sub;
	 while(r!=NULL)
	 {
		printf("\t\t %s\t\t%d\t\t%d\t\t%c\n",r->name,r->addr,r->size,r->state);
		r=r->link;
	 }
	 printf("\n");
}

//--------------------------------------------------------------------------
void disp2()   /*显示已分配内存的作业表函数*/
{
	 printf("\t\t 作业名         首地址          长度          状态 \n");
	 p=as;
	 while(p!=NULL)
	 {
		printf("\t\t %s\t\t%d\t\t%d\t\t%c\n",p->name,p->addr,p->size,p->state);
		p=p->link;
	 }
	 printf("\n\n");
}

//--------------------------------------------------------------------------
void perfit(JCB *pr) /*最佳适应作业分区assign*/
{
	 SUB *k;
	 r=sub;
	 while(r!=NULL)
	 {
		if(((r->size)>(pr->size))&&(r->state=='n'))   /*有空闲分区大于作业大小的情况*/
		{
			pr->addr=r->addr;
			r->size-=pr->size;
			r->addr+=pr->size;
			if(r==sub) sub=r->link;     /*删除空闲分区*/ 
			else 
			{
				s=sub;
				while(s->link!=r)  s=s->link;
				s->link=s->link->link;      /*删除空闲分区*/ 
			}
			flag=1;       /*分配成功标志位置1*/
			q=pr;
			lastsort();    /*插入已分配作业队列*/
			//重新插入剩余空闲分区,插在合适位置
			if(r->size<sub->size)   /*插入队首*/
			{
				r->link=sub;
				sub=r;
			}
			else   /*插在适当的位置*/
			{
				s=sub;
				while((s->size)<=(r->size))   s=s->link;
				k=sub;
				if(k==s)  {r->link=sub->link; sub=r;}   /*插在队首的后一个位置*/
				else   /*第二个以后的位置*/
				{
					while(k->link!=s)  k=k->link;
					 r->link=s;    
					k->link=r;
				}	
			 }
			 printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);  
			 break;   	   
		} 
		else if(((r->size)==(pr->size))&&(r->state=='n'))    /*有空闲分区等于作业大小的情况*/
		{
		   pr->addr=r->addr;
		   flag=1;    /*分配成功标志位置1*/
		   q=pr;
		   lastsort();	     /*插入已分配作业队列*/
		   s=sub;        /*空闲分区已完成分配,应删除*/
		   while(s->link!=r)  s=s->link;
		   s->link=s->link->link;	 /*删除空闲分区*/  
		   printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr); 
		   break;
		}
		else 
		{r=r->link;  flag=0;}
	}
	if(flag==0)           /*作业过大的情况*/
	{
		printf("作业%s长度过大，内存不足，分区分配出错!\n",p->name);
		is=1;
	}
}

//--------------------------------------------------------------------------
void firstfit(JCB *pr) /*首次适应作业分区*/
{
	//SUB *k;
	r=sub;   /*从空闲表头开始寻找*/
	while(r!=NULL)
	{
		if(((r->size)>(pr->size))&&(r->state=='n'))   /*有空闲分区大于作业大小的情况*/
		{
			pr->addr=r->addr;
			r->size-=pr->size;
			r->addr+=pr->size;
		    flag=1;       /*分配成功标志位置1*/
		    q=pr;
		    q->state='r';
		    lastsort();     /*插入已分配作业队列*/
		    printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);
		    break;
		}
		else if(((r->size)==(pr->size))&&(r->state=='n'))    /*有空闲分区等于作业大小的情况*/
		{
		   pr->addr=r->addr;
		   flag=1;    /*分配成功标志位置1*/
		   q=pr;
		   lastsort();	    /*插入已分配作业队列*/
		   s=sub;       /*空闲分区已完成分配,应删除*/
		   while(s->link!=r)  s=s->link;
		   s->link=s->link->link;	 /*删除空闲分区*/
		   printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);
		   break;
		}
		else
        {r=r->link;  flag=0;}
	}
	if(flag==0)           /*作业过大的情况*/
	{
		printf("作业%s长度过大，内存不足，分区分配出错!\n",p->name);
		is=1;
	}
}

//--------------------------------------------------------------------------
void cyclefit(JCB *pr) /*循环首次适应作业分区*/
{
	SUB *k;
	r=cur;   /*从当前指针开始寻找*/
	while(r!=NULL)
	{
		if(((r->size)>(pr->size))&&(r->state=='n'))   /*有空闲分区大于作业大小的情况*/
		{
		   pr->addr=r->addr;
		   r->size-=pr->size;
		   r->addr+=pr->size;
		   flag=1;       /*分配成功标志位置1*/
		   cur=r;        /*更新当前指针*/
		   q=pr;
		   q->state='r';
		   lastsort();             /*插入已分配作业队列*/
		   printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);
		   break;
		}
		else if(((r->size)==(pr->size))&&(r->state=='n'))    /*有空闲分区等于作业大小的情况*/
		{
		   pr->addr=r->addr;
		   flag=1;    /*分配成功标志位置1*/
		   cur=r;
		   q=pr;
		   lastsort();	    /*插入已分配作业队列*/
		   s=sub;      /*空闲分区已完成分配,应删除*/
		   while(s->link!=r)  s=s->link;
		   s->link=s->link->link;	 /*删除空闲分区*/
		   printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);
		   break;
		}
		else
		{
			r=r->link;
			if(r==NULL)      /*当前指针为空时,重新由空闲区队列之首寻找*/
			{
			   k=cur;  /*作保存当前指针用*/
			   cur=sub;  
			   r=cur;
			}
			if(k==r)   /*又回到开始的指针时,确定为没有空间满足要求*/
			{
			   cur=k;  
			   break;
			}
			flag=0;  /*分配不成功标志*/
		}
	}
	if(flag==0)           /*作业过大的情况*/
	{
		printf("作业%s长度过大，内存不足，分区分配出错!\n",p->name);
		is=1;
	}
}


//--------------------------------------------------------------------------
void less_to_more()  /*把分区按大小从小到大排序*/
{
	r=sub;
	sub=NULL;
	while(r!=NULL)
	{
		s=r;
		r=s->link;
		s->link=NULL;
		sort_sub(); /*调用排序函数*/
	}
}

//--------------------------------------------------------------------------
void reclperfit(JCB *pr)       /*最佳适应回收区域,按分区大小排列*/
{ 
	SUB *k;
	r=sub;
	while(r!=NULL)
	{
		if(r->addr==((pr->addr)+(pr->size)))     /*回收区域有下邻*/
		{
			pr->size+=r->size;
			s=sub;
			isdown=1;     /*下邻标志位置1*/
			while(s!=NULL)
			{
				if(((s->addr)+(s->size))==(pr->addr))   /*有下邻又有上邻*/
				{
					s->size+=pr->size;
					k=sub;
					while(k->link!=r)  k=k->link;
					k->link=k->link->link;
					isup=1;      /*上邻标志位置1*/    
					break;
				}
				else 
				{s=s->link; isup=0;}    /*上邻标志位置0*/  
			}
 			if(isup==0)               /*有下邻无上邻*/
			{ 
				r->addr=pr->addr;
				r->size=pr->size;
			}
			break;	   
		}
		else 
		{r=r->link; isdown=0;}     /*下邻标志位置0*/  
	}  
	if(isdown==0)              /*区域无下邻*/
    { 
		s=sub; 
		while(s!=NULL) 
		{
			if(((s->addr)+(s->size))==(pr->addr))   /*无下邻但有上邻*/
			{ 
				s->size+=pr->size; 
				isup=1;        /*上邻标志位置1*/
				break;