操作系统实验报告实验四-动态分区分配算法有运行图

实验目的

通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。 【实验内容】 问题描述：

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

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

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

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

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

用C++语言实现提示：

1）程序中变量定义参考（根据需要可添加）如下：

const int MaxNumber=100; int FreePartition[MaxNumber]; int FirstPartition[MaxNumber]; int CycleFirstPartition[MaxNumber]; int BestPartition[MaxNumber]; int WorstPartition[MaxNumber]; int ProcessNeed[MaxNumber]; int PartitionNum,ProcessNum;

2）页面置换的实现过程如下：  变量初始化；

 空闲分区个数n，空闲分区大小P1, … ,Pn，进程个数m，进程需要的分区大小S1, … ,Sm，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法；

 根据用户选择的算法进行动态分区分配；



输出所有进程分配后的空闲分区分配情况。

实验要求：

1) 上机前认真复习动态分区分配算法，熟悉首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的计算过程； 2) 上机时独立编程、调试程序；

3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源

程序、实例运行结果截图）。 【源程序】

头文件First.h

#include #include #include #include

#define Proprintf printf(\"|-----+-----+-----+-----+-----+-----+-----+-----+-----|\\n\") #define Myprintf printf(\"|++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++|\\n\") #define MaxNum 100

typedef struct ProcessPartition_struct{ int FreePartition[MaxNum]; //空闲分区大小 char ProcessName[MaxNum]; //作业名称 int ProcessNeed[MaxNum]; //作业需求空间大小 int state[MaxNum]; //作业分配标志 int PartitionNum,ProcessNum; //空闲分区个数，作业个数 }Process;

Process p;

int i,j,k,d,temp;

char order[MaxNum][MaxNum]; char ch[MaxNum]; int m; //作业个数 int n; //空闲分区个数 int First();

int CycleFirst(); int Best(); int Worst();

int Option(); //选择算法 int Pinput(); //参数输入 int Poutput(); //结果输出

int Pinput() //参数输入 { printf(\"请输入空闲分区个数:\\n\"); scanf(\"%d\ printf(\"请依次输入空闲分区大小(KB):\\n\"); for(i=0;iscanf(\"%d\ } printf(\"请输入作业个数:\\n\"); scanf(\"%d\ printf(\"请依次输入作业名称:\\n\"); for(i=0;iint First() //首次适应算法 { for(i=0;i{ for(k=0;k<3;k++) //记录作业分配 { if(order[j][k]==NULL) { order[j][k]=p.ProcessName[i]; break; } else continue; } p.FreePartition[j]=p.FreePartition[j]-p.ProcessNeed[i]; p.state[i]=1; } } } return 0; }

头文件CycleFirst.h #include #include #include #include

int CycleFirst() //循环首次适应算法 { i=0; j=0; while((ii++; } else j++; } return 0; }

头文件Best.h

#include #include #include #include

int Best() //最佳适应算法 { for(i=0;i temp) { k++; temp=p.FreePartition[k]; } for(j=0;j p.FreePartition[j]) && (!p.state[i])) { temp=p.FreePartition[j]; k=j; } else continue; } for(d=0;d<3;d++) //记录作业分配 { if(order[k][d]==NULL) { order[k][d]=p.ProcessName[i]; break; }

else continue; } p.FreePartition[k]=p.FreePartition[k]-p.ProcessNeed[i]; p.state[i]=1; } return 0; }

头文件Worst.h

#include #include #include #include

int Worst() //最坏适应算法 { for(i=0;i} return 0; }

主程序Main.cpp #include #include #include #include #include

#include #include #include

int Option() //选择算法 { int option; printf(\"请选择算法:\\n\"); printf(\"0-退出\\n\"); printf(\"1-首次适应算法\\n\"); printf(\"2-循环首次适应算法\\n\"); printf(\"3-最佳适应算法\\n\"); printf(\"4-最坏适应算法\\n\"); printf(\"请输入你选择的算法的序号:\\n\"); scanf(\"%d\ switch(option) { case 0: printf(\"程序运行结束\\n\"); break; case 1: printf(\"对作业用首次适应算法进行空间分配:\\n\"); First(); Poutput(); break; case 2: printf(\"对作业用循环首次适应算法进行空间分配:\\n\"); CycleFirst(); Poutput(); break; case 3: printf(\"对作业用最佳适应算法进行空间分配:\\n\"); Best();

Poutput(); break; case 4: printf(\"对作业用最坏适应算法进行空间分配:\\n\"); Worst(); Poutput(); break; default: printf(\"********error!*****\"); } return 0; }

int Poutput() //结果输出 { Myprintf; for(i=0;ivoid main() //主函数 { Pinput(); Option(); }

【实例运行结果截图】 实例

下面依次是测试数据、First、CycleFirst、Best和Worst算法执行的截图：