（二）可變分區存儲管理方案中的內存分配 

可變分區調度算法有:最先適應分配算法,最優適應分配算法,最壞適應算法 
用戶提出內存空間的申請；系統根據申請者的要求，按照一定的分配策略分析內存空間的使用情況，找出能 
滿足請求的空閑區，分給申請者；當程序執行完畢或主動歸還內存資源時，系統要收回它所占用的內存空間 
或它歸還的部分內存空間。 

1．程序運行時首先接收輸入：空閑區數據文件，包括若干行，每行有兩個數據項：起始地址、長度（均為 
整數），各數據項以逗號隔開。 

2．建立空閑區表并在屏幕上顯示輸出空閑區表內容，空閑區表中記錄了內存中可供分配的空閑區的始址和 
長度，用標志位指出該分區是否是未分配的空閑區。 

3．從用戶界面根據用戶提示接收一個內存申請，格式為：作業名、申請空間的大小。 

4．按照最差（最壞）適配算法選擇一個空閑區，分割并分配，修改相應的數據結構（空閑區表），填寫內 
存已分配區表（起始地址、長度、標志位），其中標志位的一個作用是指出該區域分配給哪個作業。 

5．重復3、4，直到輸入為特殊字符（0）。 

6．在屏幕上顯示輸出新的空閑區表和已分配區表的內容。 

本程序包括:FIFO,最優適應分配算法,最壞適應算法 

VC++調試通過 

(C)copyright by Neo 

歡迎大家測試 請問題請Email:sony006@163.com 
*/ 

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

const int MAXJOB=100;//定義表最大記錄數 

typedef struct node{ 
int start; 
int length; 
char tag[20]; 
}job; 

job frees[MAXJOB];//定義空閑區表 
int free_quantity; 

job occupys[MAXJOB];//定義已分配區表 
int occupy_quantity; 

//初始化函數 
void initial() 
{ 
int i; 

for(i=0;i<MAXJOB;i++){ 
frees.start=-1; 
frees.length=0; 
strcpy(frees.tag,"free"); 

occupys.start=-1; 
occupys.length=0; 
strcpy(occupys.tag,""); 
} 
free_quantity=0; 
occupy_quantity=0; 
} 

//讀數據函數 
int readData() 
{ 
FILE *fp; 
char fname[20]; 

cout<<"請輸入初始空閑表文件名:"; 
cin>>fname; 

if((fp=fopen(fname,"r"))==NULL){ 
cout<<"錯誤,文件打不開,請檢查文件名"<<endl; 
} 
else{ 
while(!feof(fp)){ 
fscanf(fp,"%d,%d",&frees[free_quantity].start,&frees[free_quantity].length); 
free_quantity++; 
} 
return 1; 
} 
return 0; 
} 

//sort 
void sort() 
{ 
int i,j,p; 

for(i=0;i<free_quantity-1;i++){ 
p=i; 
for(j=i+1;j<free_quantity;j++){ 
if(frees[j].start<frees[p].start){ 
p=j; 
} 
} 
if(p!=i){ 
frees[free_quantity]=frees; 
frees=frees[p]; 
frees[p]=frees[free_quantity]; 
} 
} 
} 


//顯示函數 
void view() 
{ 
int i; 

cout<<endl<<"----------------------------------------------------------"<<endl; 
cout<<"當前空閑表:"<<endl; 
cout<<"起始地址 長度 狀態"<<endl; 
for(i=0;i<free_quantity;i++){ 
cout.setf(2); 
cout.width(12); 
cout<<frees.start; 
cout.width(10); 
cout<<frees.length; 
cout.width(8); 
cout<<frees.tag<<endl; 
} 

cout<<endl<<"----------------------------------------------------------"<<endl; 
cout<<"當前已分配表:"<<endl; 
cout<<"起始地址 長度 占用作業名"<<endl; 
for(i=0;i<occupy_quantity;i++){ 
cout.setf(2); 
cout.width(12); 
cout<<occupys.start; 
cout.width(10); 
cout<<occupys.length; 
cout.width(8); 
cout<<occupys.tag<<endl; 
} 
} 

//最先適應分配算法 
void earliest() 
{ 
char job_name[20]; 
int job_length; 
int i,j,flag,t; 

cout<<"請輸入新申請內存空間的作業名和空間大小:"; 
cin>>job_name; 
cin>>job_length; 

flag=0; 
for(i=0;i<free_quantity;i++){ 
if(frees.length>=job_length){ 
flag=1; 
} 
} 
if(flag==0){ 
cout<<endl<<"Sorry,當前沒有能滿足你申請長度的空閑內存,請稍候再試"<<endl; 
} 
else{ 
t=0; 
i=0; 
while(t==0){ 
if(frees.length>=job_length){ 
t=1; 
} 
i++; 
} 
i--; 
occupys[occupy_quantity].start=frees.start; 
strcpy(occupys[occupy_quantity].tag,job_name); 
occupys[occupy_quantity].length=job_length; 
occupy_quantity++; 

if(frees.length>job_length){ 
frees.start+=job_length; 
frees.length-=job_length; 
} 
else{ 
for(j=i;j<free_quantity-1;j++){ 
frees[j]=frees[j+1]; 
} 
free_quantity--; 
cout<<"內存空間成功"<<endl; 
} 
} 
} 
//最優適應分配算法 
void excellent() 
{ 
char job_name[20]; 
int job_length; 
int i,j,flag,t; 

cout<<"請輸入新申請內存空間的作業名和空間大小:"; 
cin>>job_name; 
cin>>job_length; 

flag=0; 
for(i=0;i<free_quantity;i++){ 
if(frees.length>=job_length){ 
flag=1; 
} 
} 
if(flag==0){ 
cout<<endl<<"Sorry,當前沒有能滿足你申請長度的空閑內存,請稍候再試"<<endl; 
} 
else{ 
t=0; 
i=0; 
while(t==0){ 
if(frees.length>=job_length){ 
t=1; 
} 
i++; 
} 
i--; 
for(j=0;j<free_quantity;j++){ 
if((frees[j].length>=job_length)&&(frees[j].length<frees.length)){ 
i=j; 
} 
} 

occupys[occupy_quantity].start=frees.start; 
strcpy(occupys[occupy_quantity].tag,job_name); 
occupys[occupy_quantity].length=job_length; 
occupy_quantity++; 

if(frees.length>job_length){ 
frees.start+=job_length; 
frees.length-=job_length; 
} 
else{ 
for(j=i;j<free_quantity-1;j++){ 
frees[j]=frees[j+1]; 
} 
free_quantity--; 
cout<<"內存空間成功"<<endl; 
} 
} 
} 

//最壞適應算法 
void worst() 
{ 
char job_name[20]; 
int job_length; 
int i,j,flag,t; 

cout<<"請輸入新申請內存空間的作業名和空間大小:"; 
cin>>job_name; 
cin>>job_length; 

flag=0; 
for(i=0;i<free_quantity;i++){ 
if(frees.length>=job_length){ 
flag=1; 
} 
} 
if(flag==0){ 
cout<<endl<<"Sorry,當前沒有能滿足你申請長度的空閑內存,請稍候再試"<<endl; 
} 
else{ 
t=0; 
i=0; 
while(t==0){ 
if(frees.length>=job_length){ 
t=1; 
} 
i++; 
} 
i--; 
for(j=0;j<free_quantity;j++){ 
if((frees[j].length>=job_length)&&(frees[j].length>frees.length)){ 
i=j; 
} 
} 

occupys[occupy_quantity].start=frees.start; 
strcpy(occupys[occupy_quantity].tag,job_name); 
occupys[occupy_quantity].length=job_length; 
occupy_quantity++; 

if(frees.length>job_length){ 
frees.start+=job_length; 
frees.length-=job_length; 
} 
else{ 
for(j=i;j<free_quantity-1;j++){ 
frees[j]=frees[j+1]; 
} 
free_quantity--; 
cout<<"內存空間成功"<<endl; 
} 
} 
} 

//撤消作業 
void finished() 
{ 
char job_name[20]; 
int i,j,flag,p=0; 
int start; 
int length; 

cout<<"請輸入要撤消的作業名:"; 
cin>>job_name; 

flag=-1; 
for(i=0;i<occupy_quantity;i++){ 
if(!strcmp(occupys.tag,job_name)){ 
flag=i; 
start=occupys.start; 
length=occupys.length; 
} 
} 
if(flag==-1){ 
cout<<"沒有這個作業名"<<endl; 
} 
else{ 
//加入空閑表 
for(i=0;i<free_quantity;i++){ 
if((frees.start+frees.length)==start){ 
if(((i+1)<free_quantity)&&(frees[i+1].start==start+length)){ 
frees.length=frees.length+frees[i+1].length+length; 
for(j=i+1;j<free_quantity;j++){ 
frees[j]=frees[j+1]; 
} 
free_quantity--; 
p=1; 
} 
else{ 
frees.length+=length; 
p=1; 
} 
} 
if(frees.start==(start+length)){ 
frees.start=start; 
frees.length+=length; 
p=1; 
} 
} 

if(p==0){ 
frees[free_quantity].start=start; 
frees[free_quantity].length=length; 
free_quantity++; 
} 



//刪除分配表中的該作業 

for(i=flag;i<occupy_quantity;i++){ 
occupys=occupys[i+1]; 
} 
occupy_quantity--; 
} 
} 


//顯示版權信息函數 
void version() 
{ 
cout<<endl<<endl; 

cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl; 
cout<<" ┃　　　 　可變分區存儲管理模擬系統　 　　　　 ┃"<<endl; 
cout<<" ┠───────────────────────┨"<<endl; 
cout<<" ┃　 　(c)All Right Reserved Neo　　　 　　　┃"<<endl; 
cout<<" ┃　　　　　　sony006@163.com　　 　　　　　　　┃"<<endl; 
cout<<" ┃　　　　　version 2004 build 1122　　　　　　┃"<<endl; 
cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; 
cout<<endl<<endl; 
} 


void main() 
{ 

int flag=0; 
int t=1; 
int chioce=0; 

version(); 
initial(); 

flag=readData(); 

while(flag==1){ 

sort(); 
cout<<endl<<endl<<"========================================================="<<endl; 
cout<<" 可變分區存儲管理模擬系統"<<endl; 
cout<<"========================================================="<<endl; 
cout<<" 1.申請空間 2.撤消作業 3.顯示空閑表和分配表 0.退出"<<endl; 
cout<<"請選擇:"; 
cin>>chioce; 

switch(chioce){ 
case 1: 
//換算法請換下一句調用 
earliest(); 
break; 
case 2: 
finished(); 
break; 
case 3: 
view(); 
break; 
case 0: 
flag=0; 
break; 
default: 
cout<<"選擇錯誤!"<<endl; 
} 
} 
}