firstfit.cpp

操作系统实验 主存储器的空间分配和空闲回收

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream.h>
#define n 10 //假定系统允许的最大作业为n=10
#define m 10//假定系统允许的空闲区表为m=10
#define minisize 100

struct{
float address;  //已分配分区起始地址
float length;   // 已分配分区长度，单位为字节
int flag;       //已分配区表登记栏标志，用0表示空栏目
}used_table[n]; //已分配区表

struct{
float address;  //空闲区起始地址
float length;   // 空闲区长度，单位为字节
int flag;       //空闲区表登记栏标志，用0表示空栏目，用1表示未分配
}free_table[m]; //空闲分区表

void allocate(char J,float xk)//采用最有分配算法分配xk大小的空间
{
	int i,k;
	float ad;
	k=-1;
	for(i=0;i<m;i++) ///寻找空间大于xk的最小空闲空间区登记项k
		if(free_table[i].length>=xk&&free_table[i].flag==1)
			if(k==-1||free_table[i].length<free_table[k].length)
				k=i;
			if(k==-1) //未找到可用空闲区，返回
			{
				printf("无可用空闲区\n");
				return;
			}
			/*找到可用空闲区,开始分配: */
			//	若空闲区大小与要求分配的空间差小于minisize,则空闲区全部分配
			if(free_table[k].length-xk<=minisize)
			{
				free_table[k].flag=0;
				ad=free_table[k].address;
				xk=free_table[k].length;
			}
			// 若空闲区大小与要求分配的空间差大于minisize,则空闲区划出一部分分配
			else
			{
				free_table[k].length=free_table[k].length-xk;
				ad=free_table[k].address+free_table[k].length;
			}
			/*修改分配区表*/
			i=0;
			while(used_table[i].flag!=0&&i<n)
				i++;
			if(i>=n)  //无表目填写已分分区
			{
				cout<<"无表目填写已分分区,错误!"<<endl;
				if(free_table[k].flag==0)
					free_table[k].flag=1;
				else   //前面找到的某个空闲分区的一部分
				{
					free_table[k].length=free_table[k].length+xk;
					return;
				}
			}
			else //修改已分配区表
			{
				used_table[i].address=ad;
				used_table[i].length=xk;
				used_table[i].flag=J;
			}
			return;
}  //主存分配函数结束

void reclaim(char J) //回收作业名为J的作业所占主存空间
{
	int i,k,j,s,t;
	float S,L;
	/*寻找已分配表中对应登记项*/
	s=0;
	while((used_table[s].flag!=J||used_table[s].flag==0)&&s<n)
		s++;
	if(s>=n) //在分配表中找不到名字为J的作业
	{
		cout<<"找不到该作业!"<<endl;
		return;
	}
	used_table[s].flag=0;	//修改已分配表
	S=used_table[s].address; //取得归还分区的起始地址S
	L=used_table[s].length; //取得归还分区的长度L
	j=-1;
	k=-1;
	i=0;
	/*寻找回收分区的空闲上邻表目k,下邻表目j*/
	while(i<m&&(j==-1||k==-1))
	{
		if(free_table[i].flag==1)
		{
			if(free_table[i].address+free_table[i].length==S)
				k=i;
			if(free_table[i].address==S+L)
				j=i;
		}
		i++;
	}
	if(k!=-1)
		if(j!=-1)  //上邻空闲区,下邻空闲区,3项合并
		{
			free_table[k].length=free_table[j].length+free_table[k].length+L;
			free_table[j].flag=0;
		}
		else   //上邻空闲区,下邻非空闲区,与上邻合并
			free_table[k].length=free_table[k].length+L;

	else
		if(j!=-1) //上邻非空闲区,下邻空闲区,与下邻合并
		{
			free_table[j].address=S;
			free_table[j].length=free_table[j].length+L;
		}
		else  //上下邻非空闲区,回收区域直接填入,不合并
		{
			t=0;
			while(free_table[t].flag==1&&t<m)
				t++;
			if(t>=m)
			{
				cout<<"主存空闲表没有空间,回收空间失败!"<<endl;
				used_table[s].flag=J;
				return;
			}
			free_table[t].address=S;
			free_table[t].length=L;
			free_table[t].flag=1;
		}
		return;
} //主存回收函数结束

void main()
{
	int i,a;
	float xk;
	char J;

	free_table[0].address=10240;
	free_table[0].length=102400;
	free_table[0].flag=1;
	for(i=1;i<m;i++)
		free_table[i].flag=0;
	for(i=0;i<n;i++)
		used_table[i].flag=0;
	while(1)
	{
		cout<<"选择功能项: 0-退出,1-分配主存,2-回收主存,3-显示主存"<<endl;
		cin>>a;
		switch(a)
		{
		case 0:exit(0);
		case 1:
			cout<<"输入作业名J和作业所需长度xk:";
			cin>>J;
			cin>>xk;
			allocate(J,xk);
			break;
		case 2:
			cout<<"输入要回收分区的作业名";
			cin>>J;
			reclaim(J);
			break;
		case 3:
			cout<<"空闲区表:\n 起始地址  分区长度 标志 "<<endl;
			for(i=0;i<m;i++)
				cout<<free_table[i].address<<"   "<<free_table[i].length<<"   "<<free_table[i].flag<<endl;
			cout<<"已分配区表:\n 起始地址  分区长度 标志 "<<endl;
			for(i=0;i<n;i++)
			{					
				if(used_table[i].flag!=0)
				cout<<used_table[i].address<<"   "<<used_table[i].length<<"   "<<used_table[i].flag<<endl;
				else
				cout<<used_table[i].address<<"   "<<used_table[i].length<<"   "<<used_table[i].flag<<endl;
			}
			break;
		default: cout<<"没有该选项"<<endl;
		}
	}
}