实验四 动态分区分配算法

实验四动态分区分配算法

问题描述：

设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, …,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。

程序要求如下：

1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。

2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。

3）输入：空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。

4）输出：最终内存空闲分区的分配情况。

代码实现：

#include

#include

#include

using namespace std;

const int MaxNumber=100;

int FreePartition[MaxNumber];//空闲分区大小

int FirstPartition[MaxNumber];//1-首次适应算法

int CycleFirstPartition[MaxNumber];//2-循环首次适应算法

int BestPartition[MaxNumber];//3-最佳适应算法

int WorstPartition[MaxNumber];//4-最坏适应算法

int ProcessNeed[MaxNumber];//进程需要的分区大小

int PartitionNum,ProcessNum;

char ProcessName[MaxNumber];//进程名

char ProcessPartition[MaxNumber];//进程分配的序列

int Partition[MaxNumber];

char str[MaxNumber][MaxNumber];

void FirstFit(int n,int m);

void NextFit(int n,int m);

void BestFit(int n,int m);

void WorstFit(int n,int m);

void Print(int n, int m);

void Print2(int n, int m);

//======================================================== void FirstFit(int n, int m)

{

cout<<"选择了首次适应算法!"<

cout<

int i,j,k=0;

for(i=0; i

{

FirstPartition[i] = FreePartition[i];

}

for(j=0; j

{

for(i=0; i

{

if(ProcessNeed[j]<=FirstPartition[i])

{

ProcessPartition[j]=i;

//str[i][k] = ProcessName[j];

FirstPartition[i] = FirstPartition[i]-ProcessNeed[j];

break;

}

}

}

Print(n,m);

cout<<"空间序号:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"分区大小:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"剩余分区大小:";

for(i=0; i

{

cout<<"|"<

}

cout<

Print2(n,m);

}

void NextFit(int n, int m)

{

cout<<"选择了循环首次适应算法!"<

cout<

int i,j,flag=0;

for(i=0; i

{

CycleFirstPartition[i] = FreePartition[i];

}

for(j=0; j

{

for(i=flag; i

{

if(ProcessNeed[j]<=CycleFirstPartition[i])

{

ProcessPartition[j]=i;

CycleFirstPartition[i] = CycleFirstPartition[i]-ProcessNeed[j];

flag = i+1;

if(i==n-1)

{

flag=0;

}

break;

}

}

}

Print(n,m);

cout<<"空间序号:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"分区大小:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"剩余分区大小:";

for(i=0; i

{

cout<<"|"<

}

cout<

Print2(n,m);

}

void BestFit(int n, int m)

{

cout<<"选择了最佳适应算法!"<

cout<

int i,j,flag=0,temp,id=0,flag1=0;

for(i=0; i

{

BestPartition[i] = FreePartition[i];

}

while(flag1

{

flag = 0;

for(i=0; i

{

Partition[i]=0;

}

for(i=0; i

{

if(ProcessNeed[flag1]<=BestPartition[i])

{

Partition[flag]=i;

flag += 1;

}

}

temp = BestPartition[Partition[0]];

id = Partition[0];

for(i=1; i

{

if(temp > BestPartition[Partition[i]])

{

temp = BestPartition[Partition[i]];

id = Partition[i];

}

}

BestPartition[id]=BestPartition[id]-ProcessNeed[flag1];

ProcessPartition[flag1]=id;

flag1 += 1;

}

Print(n,m);

cout<<"空间序号:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"分区大小:"<<" ";

for(i=0; i

{

cout<<"|"<

cout<

cout<<"剩余分区大小:";

for(i=0; i

{

cout<<"|"<

cout<

Print2(n,m);

}

void WorstFit(int n, int m)

{

cout<<"选择了最坏适应算法!"<

cout<

int i,j,flag=0,temp,id=0,flag1=0;

for(i=0; i

{

WorstPartition[i] = FreePartition[i];

}

while(flag1

{

flag = 0;

for(i=0; i

{

Partition[i]=0;

}

for(i=0; i

{

if(ProcessNeed[flag1]<=WorstPartition[i])

{

Partition[flag]=i;

flag += 1;

}

}

temp = WorstPartition[Partition[0]];

id = Partition[0];

for(i=1; i

{

if(WorstPartition[Partition[i]] > temp)

{

temp = WorstPartition[Partition[i]];

id = Partition[i];

}

}

WorstPartition[id]=WorstPartition[id]-ProcessNeed[flag1];

ProcessPartition[flag1]=id;

flag1 += 1;

Print(n,m);

cout<<"空间序号:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"分区大小:"<<" ";

for(i=0; i

{

cout<<"|"<

}

cout<

cout<<"剩余分区大小:";

for(i=0; i

{

cout<<"|"<

}

cout<

Print2(n,m);

}

void choice(int n, int m)

{

int intput;

cout<<"\n请选择：1.首次适应算法2.循环首次适应算法3.最佳适应算法4.最坏适应算法:"<

cin>>intput;

cout<

switch(intput)

{

case 1:

FirstFit(n,m);

choice(n,m);

break;

case 2:

NextFit(n,m);

choice(n,m);

break;

case 3:

BestFit(n,m);

choice(n,m);

break;

case 4:

WorstFit(n,m);

choice(n,m);

break;

}

cout<

}

void Print(int n, int m)

{

int j;

cout<<"进程名: ";

for(j=0; j

{

cout<<"|"<

}

cout<

cout<<"进程分区大小:";

for(j=0; j

{

cout<<"|"<

}

cout<

cout<<"分配结果:"<

}

void Print2(int n, int m)

{

int i,j;

for(i=0; i

{

for(j=0; j

{

str[i][j] = 0;

}

}

cout<<"进程分配分区:";

for(i=0; i

{

int k=0;

for(j=0; j

{

if(ProcessPartition[j]==i)

{

str[i][k] = ProcessName[j];

k += 1;

}

}

}

for(i=0; i

{

cout<<"|";

for(j=0; j

{

cout<

}

}

cout<

}

//===============================================================

void main()

{

ifstream in("yin.txt");

int n,m;

int i,j;

in>>n;

for(i=0; i

{

in>>FreePartition[i];

}

in>>m;

for(j=0; j

{

in>>ProcessName[j];

}

for(j=0; j

{

in>>ProcessNeed[j];

}

choice(n,m);

}

运行结果：