mainmemalloc.c

在可变分区管理方式下采用首次适应算法实现主存分配和回收。

/*
  程序功能:模拟主存空间的分配与回收
  其中空闲表为单链表，没有长度限制
*/
#include <stdio.h>
#include <malloc.h>
#include <process.h>
#include <string.h>

#define minisize 1

typedef struct freeTable
{
  char proID[6];
  int startAddr; /*空闲区起始地址*/
  int length; /*空闲区长度，单位为字节*/
  int flag; /*空闲区表登记栏标志，用"0"表示空表项，用"1"表示未分配*/
  struct freeTable *next; 
}freeTabNode; /*空闲区表结点*/

freeTabNode *freeTab;

void InitFreeTab()
{
	freeTabNode *f,*temp;
	f=(freeTabNode *)malloc(sizeof(freeTabNode));
    strcpy(f->proID,"OS");
    f->startAddr=0;
    f->length=5;f->flag=0;
    freeTab=f;
    f=(freeTabNode *)malloc(sizeof(freeTabNode));;
    strcpy(f->proID,"1");
    f->startAddr=5;
    f->length=5;f->flag=0;
    freeTab->next=f;
    temp=f;
	f=(freeTabNode *)malloc(sizeof(freeTabNode));
    strcpy(f->proID,"3");
    f->startAddr=10;
    f->length=4;temp->flag=0;
    temp->next=f;
	temp=temp->next;
	f=(freeTabNode *)malloc(sizeof(freeTabNode));
    f->startAddr=14;
	f->length=12;
	f->flag=1;
	temp->next=f;temp=temp->next;
	f=(freeTabNode *)malloc(sizeof(freeTabNode));
    strcpy(f->proID,"2");
    f->startAddr=26;
    f->length=6;f->flag=0;
    temp->next=f;temp=temp->next;
    f=(freeTabNode *)malloc(sizeof(freeTabNode));
	f->startAddr=32;
	f->length=96;
	f->flag=1;
	f->next=NULL;
	temp->next=f;
}

void allocate(char PName[],int PLength)
{
	freeTabNode *f,*temp;
	f=freeTab;
    while(f) /*寻找空间大于PLength的最小空闲区登记项k*/
	{ 
		if(f->length>=PLength&&f->flag==1) break;
                f=f->next;
	}
  if(!f)/*未找到可用空闲区，返回*/
  {
   printf("无可用空闲区\n");
   return;
  }
/*找到可用空闲区，开始分配*/
  if(f->length-PLength<=minisize)
  {    /*空闲区大小与要求分配的空间差小于minisize大小，空闲区全部分配*/
   strcpy(f->proID,PName);
   f->flag=0;  /*修改成空表目状态*/
  }
  else 
  { /*若空闲区大小与要求分配的空间差大于minisize大小，从中划出一部分分配*/
      f->length=f->length-PLength;
	  temp=(freeTabNode *)malloc(sizeof(freeTabNode));
   	  strcpy(temp->proID,PName);
	  temp->startAddr=f->startAddr+f->length;
      temp->length=PLength;
	  temp->flag=0;
	  temp->next=NULL;
	  temp->next=f->next;
	  f->next=temp;
   }
   return;
}/*主存分配函数结束*/

void reclaim(char PName[]){
/*回收作业名为PName的作业所占主存空间*/
freeTabNode *front,*rear,*temp;
temp=freeTab;  /*寻找空闲表中对应登记项*/
if(strcmp(PName,"OS")==0)
{ printf("ERROR!");
  return;
}
while((strcmp(temp->proID,PName)!=0||temp->flag==1)&&temp)
temp=temp->next;

if(!temp)/*在已分配表中找不到名字为PName的作业*/
{
printf("找不到该作业\n");
return;
}
/*寻找回收分区的空闲上下邻，上邻表目front，下邻表目rear*/
rear=temp->next;
front=freeTab;
while(front)
{ if(front->next==temp)  break;
    front=front->next;
	}/*找到回收分区的上邻表目*/
if(rear==NULL) 
{
	if(front->flag==1) {
		front->length+=temp->length;
		front->next=NULL;
		free(temp);
	}
	else temp->flag=1;
}
else 
{
    if(front->flag==1&&rear->flag==1)
          /* 上邻空闲区，下邻空闲区，三项合并*/
    {  
    front->length=front->length+rear->length+temp->length;
    front->next=rear->next;
	free(temp);
	free(rear);
    }
    else if(front->flag==1&&rear->flag==0){
     /*上邻空闲区，下邻非空闲区，与上邻合并*/
    front->length+=temp->length;
	front->next=rear;
	free(temp);
	}
	     else  if(front->flag==0&&rear->flag==1)
   /*上邻非空闲区，下邻为空闲区，与下邻合并*/
		 {
            temp->length+=rear->length;
            temp->next=rear->next;
		    free(rear);
			temp->flag=1;
		 }
               else
           /*上下邻均为非空闲区，回收区域直接作修改*/
		   temp->flag=1;
}
}

main( )
{
int a;
freeTabNode *freeNode;
char PName[6];
int PLength;
InitFreeTab();   /*空闲分区表初始化：*/
while(1)
{
printf("**选择功能项**\n");
printf("\t0--退出\n\t1--分配主存\n\t2--回收主存\n\t3--显示主存\n");
printf("选择项(0~3) :");
scanf("%d",&a);
switch(a)
{
case 0: exit(0); /*a=0程序结束*/
case 1: /*a=1分配主存空间*/
        printf("要分配的作业名PName:");
		scanf("%s",PName);
		printf("\n和作业所需内存大小PLength(>1K): ");
        scanf("%d",&PLength);
        allocate(PName,PLength);/*分配主存空间*/
        break;
case 2: /*a=2回收主存空间*/
        printf("输入要回收分区的作业名:");
        scanf("%s",PName);
        reclaim(PName);/*回收主存空间*/
        break;
case 3: /*a=3显示主存情况*/
        printf("--------------------------------------\n");
	    printf("内存分区表:\n");
		printf("\t\t进程标识  起始地址  分区长度\t状态\n");
        freeNode=freeTab;   /*打印空闲区表*/
		while(freeNode)
		{
		   if(freeNode->flag==1)
			   printf("\t\t空\t%5d\t%6d\t\t空闲\n",freeNode->startAddr,freeNode->length);
		   else 
			   printf("\t\t%s\t%5d\t%6d\t\t空表目\n",freeNode->proID,freeNode->startAddr,freeNode->length);
			
			freeNode=freeNode->next;
		}       
        getchar();
		break;
default:printf("没有该选项\n");
}/*case*/
}/*while*/
}/*main()*/