os3.cpp

动态分区存储管理方式的主存分配回收。存储管理中动态分区的管理方式

//os3.cpp－－使用
// distribute分配函数, recycle回收函数

#include <iostream.h>
#include <iomanip.h>

//已分配表的定义
#define  N  10	 //假定系统允许的最大作业数量为n
struct
{float address;  //已分分区起始地址
 float length;	 //已分分区长度，单位为字节
 int flag;		 //已分配区表登记栏标志，"0"表示空栏目，实验中只支持一个字符的作业名
}used_table[N];	 //已分配区表

//空闲区表的定义：
#define  M  10	//假定系统允许的空闲区表最大为m
struct
{float address;		//空闲区起始地址
 float length;		//空闲区长度，单位为字节
 int flag;      	//空闲区表登记栏标志，用"0"表示空栏目，用"1"表示未分配
}free_table[M];  	//空闲区表

//全局变量
float minSIZE=1000;

void initial(void);
int distribute(int, float);
int recycle(int);
void instructions(void);
void print_two_tables(void);

main()
{
	int choice;
	int job_name;
	float need_memory;
	
	initial();
	instructions();	//显示菜单
	cout<<"?";
	cin>>choice;
	
	while(choice!=4){
		switch(choice){
			case 1:
				cout<<"Enter the job name(a positive integer) to be distributed: ";
				cin>>job_name;
				cout<<"Enter how many memory the job need(<100*1024): ";
				cin>>need_memory;
				if(distribute(job_name, need_memory)){
					cout<<"Job "<<job_name<<" memory distributed successfull.\n";
					print_two_tables();
				}
				else
					cout<<"Job "<<job_name<<" memory distribute fail!\n";
				
				break;
			case 2:
				cout<<"Enter the job name to be recycle: ";
				cin>>job_name;
				if(recycle(job_name)){
					cout<<"Job "<<job_name<<" memory recycle successfull.\n";
					print_two_tables();
				}
				else
					cout<<" job "<<job_name<<" memory recycle fail!\n";

				break;
			case 3:
				print_two_tables();
				break;
			default:
				cout<<"Invalid choice.\n\n";
				instructions();
				break;
		}

		cout<<"?";
		cin>>choice;
	}
	
	cout<<"End to run.\n";
	system("PAUSE");
	return 0;	
}

//显示菜单
void instructions(void)
{
	cout<<"Enter your choice: \n"
		<<"1 to distribute mainmemmory for the job_area.\n"
		<<"2 to recycle job_area back to the mainmemory.\n"
		<<"3 to print the two tables.\n"
		<<"4 to end.\n";
}

//初始化两个表
void initial(void)
{
	int tmp;
	
	//已分配表
	for(tmp=0; tmp<=N-1; tmp++)
		used_table[tmp].flag=0;	//已分配表的表项全部置为空表项
	
	//空闲区表
		free_table[0].address=10*1024;
		free_table[0].length=100*1024;
		free_table[0].flag=1;	//空闲区表的表项全部为可用
}

//用最优分配算法实现的动态分区
int distribute(int job_name, float need_memory)
{
	int i, k=-1;	//k用于定位最优分配算法中选择空闲表中的未分配栏
	float ad, xk;
	int count=0;	//用于计数

	i=0;	//操作空闲区表
	while(i<=M-1){
		if(free_table[i].flag==1&&need_memory<=free_table[i].length){
			count++;
			if(count==1||free_table[i].length<free_table[k].length)
				k=i;
		}
		
		i=i+1;	//i下移一个位置
	}

	if(k!=-1){	//找到满足需求的分区k
		if((free_table[k].length-need_memory)<=minSIZE){	//整个分配
			free_table[k].flag=0;
			ad=free_table[k].address;
			xk=free_table[k].length;
		}
		else{	//切割空闲区
			ad=free_table[k].address;
			xk=need_memory;

			free_table[k].address+=need_memory;
			free_table[k].length-=need_memory;
		}
		
		i=0;	//操作已分配区表
		while(used_table[i].flag!=0)
			i=i+1;	
		
		if(i<=N-1){	//若是，则在已分配区表中登记一个表项
			used_table[i].address=ad;
			used_table[i].length=xk;
			used_table[i].flag=job_name;
		}
		else{	//i>=N，即i不是已分配区表中的一栏，已分配区表长度不足
			if(free_table[k].flag==0){	//撤销前面的"整个分配"
				free_table[k].flag=1;
				free_table[k].address=ad;
				free_table[k].length=xk;
			}
			else{	//撤销前面的"切割空闲区"
				free_table[k].address=ad;
				free_table[k].length+=xk;
			}
			
			cout<<"Error! used_table is full. Distribute fail.\n";
			return 0;
		}
	}
	else{
		cout<<"Erorr! Can not find enough memory for need_memory!\n";
		return 0;
	}

	return job_name;
}

int recycle(int job_name)
{
	//首先在已分配区表中找到要回收的作业
	int s=0;
	float recycle_address, recycle_length;
	int i, j, k;	//j栏是下邻空闲区，k栏是上栏空闲区
	int t;

	while(s<=N-1&&used_table[s].flag!=job_name)
		s=s+1;

	if(s<=N-1){	//找到
		recycle_address=used_table[s].address;
		recycle_length=used_table[s].length;
		used_table[s].flag=0;
	}
	else{//未找到作业，回收失败
		cout<<"Erorr! Can not find the job "<<job_name<<", ";
		return 0;
	}

	//然后操作空闲区表
	j=k=-1;
	i=0;
	while(!(i>=M||(k!=-1&&j!=-1))){
		if(free_table[i].flag==1){	//第i栏的状态未"未分配"，则查看是否是上邻接或下邻接
			if((free_table[i].address+recycle_length)==recycle_address)
				k=i;	//上邻接
			 if((recycle_address+recycle_length)==free_table[i].address)
				j=i;	//下邻接
		}
		
		i=i+1;		
	}

	//最后合并空闲区
	if(k!=-1){	//回收区有上邻接
		if(j!=-1){	//和上下领接三项合并
			free_table[k].length+=free_table[j].length+recycle_length;
			free_table[j].flag=0;	//将第j栏的登记项删除
		}
		else	//和上邻接合并
			free_table[k].length+=recycle_length;
	}
	else if(j!=-1){	//没有上邻，只有下邻，和下邻合并
		free_table[j].length+=recycle_length;
		free_table[j].address=recycle_address;
	}
	else {	//上下邻接都没有
		t=0;
		while(free_table[t].flag!=0)
			t=t+1;	//在空闲区表中查找一个状态为“空”的栏目，用于登记

		if(t<=M-1){	//归还分区，并在空闲分区表中登记一行
			free_table[t].address=recycle_address;
			free_table[t].length=recycle_length;
			free_table[t].flag=1;
		}
		else{	//空闲表已满，回收失败
			used_table[s].flag=job_name;
			cout<<"Erorr! The free_table is full. Recycle fail.\n";
			return 0;
		}
	}

	return job_name;
}

void print_two_tables(void)
{
	int i;

	//输出used_table的信息
	cout<<"Print the used_table.\n";
	cout<<setw(5)<<"No"<<setw(20)<<"start_address"<<setw(15)<<"length"<<setw(25)<<"state(job_name)"<<endl;
	for(i=0; i<=N-1; i++)
		cout<<setw(5)<<i<<setw(15)<<used_table[i].address<<setw(20)<<used_table[i].length
			<<setw(15)<<used_table[i].flag<<endl;
		
	//输出free_table的信息
	cout<<"Print the free_table.\n";
	cout<<setw(5)<<"No"<<setw(20)<<"start_address"<<setw(15)<<"length"<<setw(15)<<"state"<<endl;
	for(i=0; i<=M-1; i++)
		cout<<setw(5)<<i<<setw(15)<<free_table[i].address<<setw(20)<<free_table[i].length
		<<setw(15)<<free_table[i].flag<<endl;
}