unix_disk_allocate.cpp

操作系统中UNIX成组链接法的实现！ 对理解成组链接法的原理很有帮助。

#include<stdio.h>
#include<stdlib.h>
#define BLOCK 8             //总的空闲块数
#define GROUP 3             //每组的空闲块数
#define N 10                //每块的记录个数（相对于第一块）

void allocate(int);     //原型说明
void reclaim(int);

int disk[BLOCK][N];
int ma[N];

typedef struct Node     //防止回收时用户输入空闲块号 或其他错误的块号。 
{
    int allocate;
    struct Node *next;
}No;
No *h=NULL,*r=NULL;


int main()
{
	int i,j,k,count,last;
	int ca,temp;
	int num,id;
	count=BLOCK/GROUP;
	last=BLOCK%GROUP;
	disk[0][0]=GROUP;
	for(j=1;j<=GROUP;j++)      //初始化专用块
		disk[0][j]=j;

	for(i=0;i<=GROUP;i++)      //把专用块复制到主存中
		ma[i]=disk[0][i];
	i=1;
	k=0;

	for(;k<count-1;k++)          //初始化中间每组的第一块
	{
		disk[i][0]=GROUP;
		for(j=1;j<=GROUP;j++)
			disk[i][j]=j+(k+1)*GROUP;
		i+=GROUP;
	}

	if(last!=0)
	{                            //最后一组不足GROUP个空闲块的处理
		disk[i][0]=last+1;
		disk[i][1]=0;            //标记
		for(k=2;k<last+2;k++)
			disk[i][k]=BLOCK-last+k-1;
	}
	h=(No *)malloc(sizeof(No));    //链表初始化。 
    h->next=NULL;
    r=h;    

	printf("Select the function:1---allocate disk space\
		                                            2---reclaim  disk space\
				                            3---print the free group\
				                            0---exit\n");
	scanf("%d",&ca);
	while(1)
	{
		switch(ca){
		case 0:return 0;
		case 1:printf("Please input the number of blocks you required\n");
			   scanf("%d",&num);
			   allocate(num);
			   printf("Please input the function number(0~3):");
			   break;
		case 2:printf("Please input the block ID you want to reclaim\n");
			   scanf("%d",&id);
			   reclaim(id);
			   printf("Please input the function number(0~3):");
			   break;
		case 3:temp=0;
		       for(i=0;i<=ma[0];i++)
		           disk[0][i]=ma[i];
               if(ma[0]==1&&ma[1]==0||ma[0]==0)     //处理最后一组的情况及其他。 
                   printf("no free block to print\n");
               else 
                   while(1)
                   { 
                       printf("%d(",temp);
                       for(i=0;i<disk[temp][0];i++)
                           printf("%d,",disk[temp][i]);
                       printf("%d)\n",disk[temp][i]);
                       if(disk[temp][1]==0)             //对应last不等于0. 
                           break;
                       else 
                       {
                           temp=disk[temp][1];         
                           if(disk[temp][0]==0)         //对应last等于0. 
                           break;
                       }    
                   }
               printf("Please input the function number(0~3):");
               break;                            
		}
	   scanf("%d",&ca);
	}
}

void allocate(int num)
{
	int i,s;
	int nu;
	No *p;
	nu=num;
	while(nu>0)
	{
		if(ma[0]<=1)
			if(ma[0]==0)                         //该组已分完
			{
				for(i=0;i<=disk[0][0];i++)       //专用块的内容复制到主存
					ma[i]=disk[0][i];
				nu--;                           //确保正确返回。 
				continue;
			}
			else if(ma[1]==0)
				 {
				    printf("The system has no free block\n");
					return;
			      }
			     else       //只剩下最后一块可分配
				 {
					 s=ma[1];
					 for(i=0;i<=disk[s][0];i++)
						 disk[0][i]=disk[s][i];
					 disk[s][0]=0;           //清0(为功能3准备) 
					 ma[0]--;
					 nu++;                   //确保专用块内容复制到内存中 
					 printf("The block ID allocated is %d\n",s);
				 }
		else
		{
			i=ma[0];
			s=ma[i];
			ma[0]--;
			printf("The block ID allocated is %d\n",s);
		}
		nu--;
		p=(No *)malloc(sizeof(No));        //尾插法建单链表。 
		p->allocate=s;
		p->next=NULL; 
		r->next=p;
		r=p;
      }		
}

void reclaim(int id)
{
	int i,j;
	j=id;
	No *t,*q;	
	t=h->next;
	while(t!=NULL&&t->allocate!=j)
	{
	    q=t;
	    t=t->next;
	}    
   if(t==NULL)
   {
       printf("@Error:confirm your block ID(have not allocated or error id)\n\n");
       return;
   }
   q->next=t->next;
   if(t==r)
       r=q;                  //恰好是尾节点时，要修改全局变量r,否则下面free(t)将会释放掉r.   
   free(t);    
    
	if(ma[0]==GROUP)         //默认输入的磁盘号是已分配的。 
	{                       //当前组已满了
		for(i=0;i<=ma[0];i++)
			disk[j][i]=ma[i];
		ma[0]=1;
		ma[1]=j;
	}
	else
	{
		ma[0]++;
		i=ma[0];
		ma[i]=j;
	}
}