#include"stdio.h"
#include<iostream.h>
#include<string.h>
#include <stdlib.h>
#include <time.h>
#define n 10 //模擬實驗中允許的最大進程數為n
#define m 10 //模擬實驗中允許的最大分區個數為m
#define M_SIZE 10000 

struct 
{	
float address; //分配給進程的起始地址
float length; //分配給進程的空閑區長度，單位為字節
int flag;    //分配區表標志，用"0"已分配，用"1"表示未分配
}Used_Table[m]; //分配分區表


struct 
{ 
float address; //空閑區起始地址
float length; //空閑區長度，單位為字節 
int flag;    //空閑區表登記欄標志，用"0"表示已分配，用"1"表示未分配
}Free_table[m]; //空閑分區表

float stand_length(int k)//隨機產生一個分區大小的函數
{
float  st_length[20];
srand((unsigned)time(NULL));//srand()函數產生一個當前時間開始的隨機種子
for (int i=0;i<20;i++)
st_length[i]=float (rand()%1000);
return st_length[k];
}


float process_length(int k)//隨機產生一個進程大小的函數
{
float  pt_length[20];
srand((unsigned)time(NULL));//srand()函數產生一個當前時間開始的隨機種子
for (int i=0;i<20;i++)
pt_length[i]= float (rand()%500);
return pt_length[k];
}



int process_num()//隨機產生一個進程個數的函數
{
int num;
int A[10]={1,2,3,4,5,6,7,8,9,10};
srand((unsigned)time(NULL));
num=rand()%10;
return A[num];
}

char srand_name(int k)//隨機產生一個進程的名字
{

char A[26]={'A','B','C','D','E','F','G','H','I',
  'J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
  return A[k];

}

void allocate(char PRS_NAME,float X_K) //采用最優分配算法為進程PRS_NAME分配X_K大小的空間
{ 
int i,k; 
float ad; 
k=-1; 
for(i=0;i<m;i++) //尋找空間大于X_K的最小空閑區登記項k
if(Free_table[i].length>=X_K&&Free_table[i].flag==1) 
if(k==-1||Free_table[i].length<Free_table[k].length) 
k=i; 
if(k==-1)//未找到可用空閑分區，返回
{ 
printf("無可用空閑區\n"); 
return; 
} 
//找到可用空閑區，開始分配：
//若空閑區大小與要求分配的空間差小于M_SIZE大小，則空閑區全部分配；
//若空閑區大小與要求分配的空間差大于M_SIZE大小，則從空閑區劃出一部分分配
if(Free_table[k].length-X_K<=M_SIZE) 
{ 
Free_table[k].flag=0; 
ad=Free_table[k].address; 
X_K=Free_table[k].length; 
} 
else 
{ 
Free_table[k].length=Free_table[k].length-X_K; 
ad=Free_table[k].address+Free_table[k].length; 
} 
//修改已分配區表
i=0; 
while(Used_Table[i].flag!=0&&i<n) //尋找空表目
i++; 
if(i>=n) //無表目填寫已分分區
{ 
printf("無表目填寫已分分區，錯誤\n"); 
//修正空閑區表 
if(Free_table[k].flag==0) 
//前面找到的是整個空閑分區  
Free_table[k].flag=1; 
else 
{//前面找到的是某個空閑分區的一部分  
Free_table[k].length=Free_table[k].length+X_K; 
return; 
} 
} 
else 
{//修改已分配表 
Used_Table[i].address=ad; 
Used_Table[i].length=X_K; 
Used_Table[i].flag=PRS_NAME; 
} 
return; 
}//內存分配函數結束 

void reclaim(char PRS_NAME) //回收進程名為PRS_NAME的進程所占內存空間 
{ 
int i,k,j,s,t; 
float S,L; 
//尋找已分配表中對應登記項 
s=0; 
while((Used_Table[s].flag!=PRS_NAME||Used_Table[s].flag==0)&&s<n) 
s++; 
if(s>=n)//在已分配表中找不到名字為PRS_NAME的進程
{ 
printf("找不到該進程\n"); 
return; 
} 
//修改已分配表
Used_Table[s].flag=0; //取得歸還分區的起始地址S和長度L
S=Used_Table[s].address; 
L=Used_Table[s].length; 
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) 
// 上鄰空閑區，下鄰空閑區，三項合并
{ 
Free_table[k].length=Free_table[j].length+Free_table[k].length+L; 
Free_table[j].flag=1; 
} 
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 p_length; 
char p_name; 
//空閑分區表初始化：
int t_P;
Free_table[0].address=10000;
for(t_P=0; t_P<m; t_P++)
{
Free_table[t_P].length=stand_length(t_P); 
Free_table[t_P].flag=1; 
}

for(t_P=1;t_P<m;t_P++)
{
Free_table[t_P].address=Free_table[t_P-1].address+Free_table[t_P-1].length;
}//空閑分區表初始化結束
//已分配表初始化：
for(i=0;i<n;i++) 
Used_Table[i].flag=0; 
cout<<"--------------模擬固定分區存儲管理的分配與回收------------"<<endl<<endl;
cout<<"*********************功能選項*****************************"<<endl;
cout<<"*     0——退出               1——隨機產生進程并分配內存*"<<endl;
cout<<"*     2——回收進程和內存     3——顯示內存分配記錄      *"<<endl;
cout<<"**********************************************************"<<endl;
while(1) 
{ 

cout<<"輸入選擇的功能項(0--3) :"<<endl;
cin>>a;
switch(a) 
{ 
case 0: return;///a=0選擇退出程序結束 
case 1: //選擇a=1，開始隨機的產生進程并分配空間
	{
int p_num=process_num();
cout<<"隨機產生"<<p_num<<"個進程"<<endl;
int p_p;
cout<<"進程名    進程大小"<<endl;
for(p_p=0;p_p<p_num;p_p++)
{
p_name=srand_name(p_p);
p_length= process_length(p_p);
cout<<p_name<<"           "<<p_length<<endl;
allocate(p_name,p_length);//分配內存空間 
}
cout<<"要查看內存分配請在提示命令出現后輸入'3'回車"<<endl;
	}
break; 
case 2: //a=2回收內存空間 
cout<<"輸入要回收分區的進程名"; 
cin>>p_name; 
reclaim(p_name);//回收內存空間 
break; 
case 3: //a=3顯示內存情況
//輸出空閑分區表和已分配分區表的內容
cout<<"輸出空閑區表："<<endl;
cout<<"------------------------------------------------------"<<endl;
cout<<"起始地址 分區大小 標志(0—已分配，1—未分配)"<<endl; 
for(i=0;i<m;i++) 
printf("%6.0f%9.0f%6d\n",Free_table[i].address,Free_table[i].length, Free_table[i].flag); 
cout<<"已分配分區表："<<endl;
cout<<"------------------------------------------------------"<<endl;
cout<<"起始地址 分區大小 進程名"<<endl;
for(i=0;i<n;i++) 
if(Used_Table[i].flag!=0) 
printf("%6.0f%9.0f%6c\n",Used_Table[i].address,Used_Table[i].length, Used_Table[i].flag); 
break; 
default:
cout<<"沒有該選項，請輸入正確的選項！"<<endl; 
}
}
}