操作系统实验四
题目 : 动态分区分配算法
班级 : 姓名 : 学号 : 完成日期 :
一、 需求分析
１、问题描述：设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,Pn，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,Sm，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。
２、基本要求：一个完整的系统应具有以下功能：
1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。
2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。
3）输入：空闲分区个数n，空闲分区大小P1, … ,Pn，进程个数m，进程需要的分区大小S1, … ,Sm，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。
4）输出：最终内存空闲分区的分配情况。
３、测试数据：见上机指导书测试数据。
４、实现提示：
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. 变量描述
int m,n; char ResName[MaxNumber]; char ProName[MaxNumber];
操作系统实验四
2. int Available[MaxNumber]; int Max[MaxNumber][MaxNumber]; int Allocation[MaxNumber][MaxNumber]; int Need[MaxNumber][MaxNumber]; 主程序的流程以及各程序模块之间的调用关系：
(1). 资源分配表初始化（Initialization）
(2). 读取资源分配表（Resource）
(3). 安全性算法（Safety）
(4). 银行家算法（Order）
(5). 申请需求后的银行家算法（Request）
(6). 结束程序
三.详细设计
#include"suanfa.h"
//-------------------------- 主函数 ------------------------------
int main()
{
cout<<"--------关闭窗口则退出.-----------"<<endl; int FreePartition[MaxNumber]; int FirstPartition[MaxNumber]; char Name[MaxNumber]; int CycleFirstPartition[MaxNumber]; int BestPartition[MaxNumber]; int WorstPartition[MaxNumber]; int ProcessNeed[MaxNumber]; int PartitionNum,ProcessNum; int k=1; while(k) { char chioce; cout<<"请键入一个选择功能符（I：Initialization，F：First，N：Next，"<<endl; cout<<"B：Best，W：Worst，Q：Quit）："<<endl; cin>>chioce; switch(chioce) { case'I':Initialization(Name,FreePartition,ProcessNeed,ProcessNum,PartitionNum);break; //初始化
操作系统实验四
case'F':First(Name,FreePartition,ProcessNeed,FirstPartition,ProcessNum,PartitionNum);break; //首次适应算法
case'N':Next(Name,FreePartition,ProcessNeed,CycleFirstPartition,ProcessNum,PartitionNum);break; //循环首次适应算法
case'B':Best(Name,FreePartition,ProcessNeed,BestPartition,ProcessNum,PartitionNum);break; //最佳适应算法
} case'W':Worst(Name,FreePartition,ProcessNeed,WorstPartition,ProcessNum,Part } case'Q':k=0; //退出运行 } itionNum);break; //最坏适应算法 return 0;
//----------------------------------------------------------------
//==================================================================== #include<iostream>
#include<fstream>
using namespace std;
#define MaxNumber 100
//==================================================================== void Initialization(char Name[],int FreePartition[],int ProcessNeed[],int &m,int &n)
{ //将数据写入文件partition.txt中
int i; ofstream fout("partition.txt"); cout<<"请输入进程个数：m = "; // cin>>m; fout<<m<<endl; cout<<"请输入空闲分区个数：n = "; // cin>>n; fout<<n<<endl; char *name=new char[m]; int *free=new int[n]; int *need=new int[m]; cout<<"请输入"<<m<<"个进程名称："; for (i=1;i<=m;i++) { cin>>name[i]; } for (i=1;i<=m;i++) {
操作系统实验四
Name[i]=name[i]; fout<<Name[i]<<" "; } fout<<endl; cout<<"请输入"<<m<<"个进程需求大小："; // for (i=1;i<=m;i++) { } for (i=1;i<=m;i++) { ProcessNeed[i]=need[i]; fout<<ProcessNeed[i]<<" "; cin>>need[i]; } fout<<endl; cout<<"请输入"<<n<<"个空闲分区大小："; // for (i=1;i<=n;i++) { cin>>free[i]; } for (i=1;i<=n;i++) { FreePartition[i]=free[i]; } fout<<FreePartition[i]<<" "; fout<<endl; cout<<"空间分区和进程大小已写入文件partition.txt中。"<<endl;
}
//--------------------------------------------------------------------
void Partition(char Name[],int FreePartition[],int ProcessNeed[],int &m,int &n)
{ //从partition.txt文件中读取数据
int i; ifstream fin("partition.txt"); fin>>m; fin>>n; char *name=new char[m]; int *free=new int[n]; int *need=new int[m]; for (i=1;i<=m;i++) { fin>>name[i];
操作系统实验四
} Name[i]=name[i]; for (i=1;i<=m;i++) { } for (i=1;i<=n;i++) { } fin>>free[i]; FreePartition[i]=free[i]; fin>>need[i]; ProcessNeed[i]=need[i];
}
//-------------------------------------------------------------------- /*void Select(int FreePartition[],int &n)
{ //泡沫排序
int t; for (int j=1;j<=n;j++) { for (int i=1;i<=n-j+1;i++) { if (FreePartition[i-1]>FreePartition[i]) { } } t=FreePartition[i-1]; FreePartition[i-1]=FreePartition[i]; FreePartition[i]=t;
}
}*/
//-------------------------------------------------------------------- int Min(int FreePartition[],int &n,int &t)
{ //求最小数
t=FreePartition[1]; for (int i=1;i<=n;i++) { if (FreePartition[i]<t) { t=FreePartition[i]; } } return t;
操作系统实验四
}
//--------------------------------------------------------------------
int Max(int FreePartition[],int &n,int &t)
{ //求最小数
} t=FreePartition[1]; for (int i=1;i<=n;i++) { } if (FreePartition[i]>t) { } t=FreePartition[i]; return t;
//--------------------------------------------------------------------
void First(char Name[],int FreePartition[],int ProcessNeed[],int FirstPartition[],int &m,int &n) { //首次适应算法
Partition(Name,FreePartition,ProcessNeed,m,n); int i,j; for (i=1;i<=m;i++) { FirstPartition[i]=0; } for (i=1;i<=m;i++) { for (j=1;j<=n;j++) { if (ProcessNeed[i]<=FreePartition[j]&&FirstPartition[i]==0) { FirstPartition[i]=j; } FreePartition[j]=FreePartition[j]-ProcessNeed[i]; } } cout<<"首次适应算法: "<<endl; for (i=1;i<=n;i++) { cout<<FreePartition[i]<<" "; for (j=1;j<=m;j++) { if (FirstPartition[j]==i) { } cout<<Name[j]<<" ";
操作系统实验四
}
}
cout<<endl;
}
//--------------------------------------------------------------------
void Next(char Name[],int FreePartition[],int ProcessNeed[],int CycleFirstPartition[],int &m,int &n)
{ //循环首次适应算法
Partition(Name,FreePartition,ProcessNeed,m,n);
int i,j; for (i=1;i<=m;i++) { } CycleFirstPartition[i]=0; for (i=1;i<=m;i++) { if (i==1) { for (j=1;j<=n;j++) { } } else { for (j=CycleFirstPartition[i-1];j<=n;j++) { } if (ProcessNeed[i]<=FreePartition[j]&&CycleFirstPartition[i]==0) { } CycleFirstPartition[i]=j; FreePartition[j]=FreePartition[j]-ProcessNeed[i]; if (ProcessNeed[i]<=FreePartition[j]&&CycleFirstPartition[i]==0) { } CycleFirstPartition[i]=j; FreePartition[j]=FreePartition[j]-ProcessNeed[i]; } } cout<<"循环首次适应算法: "<<endl; for (i=1;i<=n;i++) { cout<<FreePartition[i]<<" "; for (j=1;j<=m;j++)
操作系统实验四
} } { } if (CycleFirstPartition[j]==i) { cout<<Name[j]<<" "; } cout<<endl;
//--------------------------------------------------------------------
void Best(char Name[],int FreePartition[],int ProcessNeed[],int BestPartition[],int &m,int &n) { //最佳适应算法
Partition(Name,FreePartition,ProcessNeed,m,n); int i,j,t; int *Order=new int[n]; for (i=1;i<=m;i++) { } { Order[i]=FreePartition[i]; } for (i=1;i<=m;i++) { for (t=1;t<=n;t++) { Order[t]=100; } for (j=1;j<=n;j++) { } { } if (FreePartition[j]-ProcessNeed[i]>=0) { } Order[j]=FreePartition[j]-ProcessNeed[i]; BestPartition[i]=0; for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (BestPartition[i]==0&&Order[j]==Min(Order,n,t)) { } BestPartition[i]=j; FreePartition[j]=FreePartition[j]-ProcessNeed[i];
操作系统实验四
} cout<<"最佳适应算法: "<<endl; for (i=1;i<=n;i++) { cout<<FreePartition[i]<<" "; for (j=1;j<=m;j++) { } if (BestPartition[j]==i) { } cout<<Name[j]<<" "; } cout<<endl;
}
//--------------------------------------------------------------------
void Worst(char Name[],int FreePartition[],int ProcessNeed[],int WorstPartition[],int &m,int &n) { //最差适应算法
Partition(Name,FreePartition,ProcessNeed,m,n); int i,j,t; int *Order=new int[n]; for (i=1;i<=m;i++) { WorstPartition[i]=0; } for (i=1;i<=n;i++) { Order[i]=FreePartition[i]; } for (i=1;i<=m;i++) { for (t=1;t<=n;t++) { Order[t]=0; } for (j=1;j<=n;j++) { if (FreePartition[j]-ProcessNeed[i]>=0) { } Order[j]=FreePartition[j]-ProcessNeed[i]; } for (j=1;j<=n;j++) {
操作系统实验四
} } if (WorstPartition[i]==0&&Order[j]==Max(Order,n,t)) { } WorstPartition[i]=j; FreePartition[j]=FreePartition[j]-ProcessNeed[i]; } cout<<"最差适应算法: "<<endl; for (i=1;i<=n;i++) { } cout<<FreePartition[i]<<" "; for (j=1;j<=m;j++) { } if (WorstPartition[j]==i) { } cout<<Name[j]<<" "; cout<<endl;
//--------------------------------------------------------------------
三、 调试分析
本题中有两种主要算法：Safety和Order的时间复杂度均为O（n*n），本题的空间复杂度亦为O(n*n)。
四、 用户手册
1． 本程序的运行环境为Microsoft Visual C++ 6.0。
2． 按提示键入输入选择算法
3． 由文件输入测试数据。
4． 接受其他命令后即执行相应运算和显示相应结果。
5． 关闭窗口则退出程序。
五、 测试结果
操作系统实验四
六、 附录
suanfa.h //算法程序 Main.cpp //主程序
