周峰.cpp

操作系统先适应法、最优适应法、最差适应法

#include<stdio.h>  
#include<iostream> 
using namespace std;                                                                                                                                         
#include"stdlib.h"
typedef struct area{
    int start;
    int length;
    int state;
    struct area *next;
}Area,*pArea;

const int Max=255;

void PrintMemoryState(Area *);
void FirstFit(Area *);
void BestFit(Area *);
void WorstFit(Area *);
void MaxLength(Area *);
int main()
{
    Area *work;
    Area *p;
	Area *p1;
	Area *p2;
	Area *p3;Area *p4;Area *p5;
    int Choice;
    //int start;
    pArea head=(Area *)malloc(sizeof(Area));//分配头指针
	//extern void *malloc(unsigned int num_bytes)功能：分配长度为num_bytes字节的内存块
    work=(Area *)malloc(sizeof(Area));
    head->start=0;
    head->length=0;
    head->state=1;
    head->next=NULL;
    //装入系统
    printf(".............正在载入系统中..............\n");
    work->start=0;
	work->length=1;
	work->next=NULL;
	work->state=1;
    head->next=work;
    p=(Area *)malloc(sizeof(Area));
    p->start=1;
	p->length=32;
//	p->next=NULL;
	p->state=-1;
    work->next=p;
	p1=(Area *)malloc(sizeof(Area));
    p1->start=33;
	p1->length=16;
//	p1->next=NULL;
	p1->state=-1;
    p->next=p1;
	p2=(Area *)malloc(sizeof(Area));
    p2->start=49;
	p2->length=8;
//	p2->next=NULL;
	p2->state=-1;
    p1->next=p2;
	p3=(Area *)malloc(sizeof(Area));
    p3->start=57;
	p3->length=4;
	//p3->next=NULL;
	p3->state=-1;
    p2->next=p3;
    p4=(Area *)malloc(sizeof(Area));
    p4->start=61;
	p4->length=64;
//	p4->next=NULL;
	p4->state=-1;
    p3->next=p4;
    p5=(Area *)malloc(sizeof(Area));
    p5->start=125;
	p5->length=Max-125;
	p5->next=NULL;
	p5->state=-1;
    p4->next=p5;
    PrintMemoryState(head);//输出当前的内存使用状况
    //开始循环
    while(1)
    {
        printf(" 1.最先适应法;2.最优适应法;3.最差适应法;0.退出程序\n");
        printf("<CHOICE> #");
        scanf("%d",&Choice);//输入你所要的选项。为choice 的值
        switch(Choice)
        {
            case 0:
                printf("The System Is Shutdown... \n");
                goto A;
            case 1:
                FirstFit(head);
                PrintMemoryState(head);//最先适应法
                continue;
			case 2:
                BestFit(head);
                PrintMemoryState(head);//最优适应法
                continue;
            case 3:
                WorstFit(head);
				PrintMemoryState(head);//最差适应法
                continue;              
            default:
                printf("Please input a right number!\n");
                break;
        }
    }
A:    return 0;
}
void PrintMemoryState(Area *head)
{
    int state=-1;
    Area *temp=(Area *)malloc(sizeof(Area));
    temp=head->next;
    printf("\t起始地址\t内存长度\t内存状态\n");
	do
    {
        printf("\t%8d\t%8d\t%8d\n",temp->start,temp->length,temp->state);
        temp=temp->next;
    }while(temp/*->length+temp->start)*/!=NULL);
    printf("\t%8d\t%8d\t%8d\n",Max,0,state);
    return ;
}
void FirstFit(Area *head)//装入作业,最先适应法
{
    int flag=0;//int sum=0;
    int lengthtemp;
	int a[3];
    Area *last=(Area *)malloc(sizeof(Area));
    Area *Task=NULL;
    Area *newFree=NULL;
	cout<<"请分别输入需要分配内存的3个作业内存长度:"<<endl;
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
	}
	for(i=0;i<3;)
	{
		int sum;int n=0;int b[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
		Task=head->next;
		while(Task!=NULL)
		{
			if(Task->state==1)
			{
				Task=Task->next;
			}
			else
			{
				b[n]=Task->length;
				Task=Task->next;
				n++;				
			}
		}
		delete Task;//把各个length装入数组B
		sum=b[0];
		for(int j=0;j<n;j++)
		{

			if(sum<b[j+1])
				sum=b[j+1];
		}//sum取B[n]中的最大值
			
		if(a[i]>sum)
		{
			cout<<"a["<<i<<"]   作业过长，无法装入 "<<endl;
			goto B;
			//exit(-1);
		}
		last=head->next;
		while(last!=NULL)
		{
			if(last->state==1)
			{
				last=last->next;

				continue;

			}//首先判断占用情况，如果被占用则查看下一个内存块

			else
			{
				if(last->length==a[i])
				{
					last->state=1;flag=1;
					goto B;
				}//等于的话直接装入
				if(last->length>a[i])
				{
					lengthtemp=last->length;
					last->length=a[i];
					last->state=1;
					newFree=(Area *)malloc(sizeof(Area));
					newFree->next=last->next;
					newFree->start=last->start+last->length;
					newFree->length=lengthtemp-last->length;
					newFree->state=-1;
					last->next=newFree;//成功插入newFree节点

					flag=1;
					goto B;
				}
				if(last->length<a[i])//如果内存长度小于所给作业要占用的内存长度，则查看下一个内存块
				{
					last=last->next;
					continue;
				}

			}//else结束
		} //while 结束
B:		i++;
	}
    if(flag==0)
    {
        printf("Cann't Load the Task! System will shutdown!\n");
        exit(-1);
    }
}
void WorstFit(Area *head)//装入作业,最差适应法
{
    int lengthtemp;
	int a[3];
    Area *last=NULL;
    Area *newFree=NULL;
	cout<<"请分别输入需要分配内存的3个作业内存长度:"<<endl;
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
	}
	for(i=0;i<3;)
	{
	    Area *Task=NULL;
		last=head->next;
		Task=last->next;
		while(Task!=NULL)
		{
			if(Task->state==1)
				Task=Task->next;
			else
			{
				if(last->length<Task->length)
				{
					last=Task;
					Task=Task->next;
				}
				else Task=Task->next;
			}//last指向length最大的那块
		}
//		int l=last->length;
//		cout<<l<<" 周    ";
		delete Task;
		if(a[i]>last->length)
		{
			cout<<"a["<<i<<"]   作业过长，无法装入 "<<endl;
			goto C;
		}
		if(last->length==a[i])
		{
			last->state=1;
			goto C;
		}//等于的话直接装入
		if(last->length>a[i])
		{
			lengthtemp=last->length;
			last->length=a[i];
			last->state=1;
			newFree=(Area *)malloc(sizeof(Area));
			newFree->next=last->next;
			newFree->start=last->start+last->length;
			newFree->length=lengthtemp-last->length;
			newFree->state=-1;
			last->next=newFree;//成功插入newFree节点
			goto C;
		}
C:	    i++;
	}
}
void BestFit(Area *head)//装入作业,最优适应法
{
    int flag=0;
    int lengthtemp;
	int a[3];
    Area *last=(Area *)malloc(sizeof(Area));
    Area *newFree=NULL;
	Area *H=NULL;
	cout<<"请分别输入需要分配内存的3个作业内存长度:"<<endl;
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
	}

	for(i=0;i<3;)

	{
		int sum;int n=0;int b[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
		int d=0;
	    Area *Task=NULL;
		Area *p=NULL;
		last=head->next;
		Task=last;
		p=head->next;
		H=head->next;
		while(H!=NULL)
		{
			if(H->state==1)
			{
				H=H->next;
			}
			else
			{
				b[n]=H->length;
				H=H->next;
				n++;				
			}
		}
		delete H;//把各个length装入数组B
		sum=b[0];
		for(int j=0;j<n;j++)
		{

			if(sum<b[j+1])
				sum=b[j+1];
		}//sum取B[n]中的最大值
			
		if(a[i]>sum)
		{
			cout<<"a["<<i<<"]   作业过长，无法装入 "<<endl;
			goto C;
			//exit(-1);
		}

		while(last!=NULL)
		{

			if(last->state==1)
				last=last->next;
			else
			{
				if(a[i]>last->length)
					last=last->next;
				else if(a[i]==last->length)
				{
					last->state=1;
					goto C;
				}
				else if(a[i]<last->length)
				{
					Task=last;
					if(d==0)
					{
						p=Task;
						d++;
					}
					if(p->length>Task->length)
						p=Task;
					last=last->next;
				}

			}
		}
		lengthtemp=p->length;
		p->length=a[i];
		p->state=1;
		newFree=(Area *)malloc(sizeof(Area));
		newFree->next=p->next;
		newFree->start=p->start+p->length;
		newFree->length=lengthtemp-p->length;
		newFree->state=-1;
		p->next=newFree;//成功插入newFree节点
C:	    i++;
	}

}