0
0

动态分区分配算法（操作系统实验 C＋＋）

动态分区分配算法

1.实验目的

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

2.实验内容

问题描述：
设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为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-最坏适应算法；
根据用户选择的算法进行动态分区分配；
输出所有进程分配后的空闲分区分配情况。

3.程序主要构成部分及其算法说明

1.首次适应算法FF
算法思想：将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中。

voidFirstFit(){
    cout<<"首次适应算法"<<endl;initial();int i,j;for(i=0;i<SNum;i++){//遍历进程for(j=0;j<PNum;j++){//每次从分区的首地址开始查找//当系统内存分区足够大的时候，即分配给进程资源if(LeftSNeed[i]<= LeftFreeP[j]&& LeftFreeP!=0){
                LeftFreeP[j]-= LeftSNeed[i];//扣除分配给进程的资源
                LeftSNeed[i]=0;//当内存分区足够才执行，当前进程大小置0
                SWhere[i][j]= SName[i];//存储各个进程所在的分区位置break;//一个进程分区完后，立即进行下一个进程的判断}}}display();}
  1. 循环首次适应算法NF 算法思想：分配内存时不是从链首进行查找可以分配 内存的空闲分区，而是从上一次分配内存的空闲分区的下一个分区开始查找，直到找到可以为该进程分配内存的空闲分区。
voidNextFit(){
    cout<<"循环首次适应算法"<<endl;initial();int i,j,nextPoint =0;bool isWhile;for(i=0;i<SNum;i++){
        isWhile =true;while(isWhile){//每次都从当前分区的下一个分区开始查找if(LeftFreeP[nextPoint]>= LeftSNeed[i]){
                LeftFreeP[nextPoint]-= LeftSNeed[i];
                LeftSNeed[i]=0;
                SWhere[i][nextPoint]= SName[i];
                nextPoint++;if(nextPoint > PNum -1){
                    nextPoint =0;//当j遍历到分区末尾的时候，返回首位置}
                isWhile =false;}else{
                nextPoint++;if(nextPoint > PNum -1){
                    nextPoint =0;//当j遍历到分区末尾的时候，返回首位置}
                j++;if(j>=PNum){//避免死循环
                    isWhile=false;
                    j=0;}}}}display();}
  1. 最佳适应算法BF 算法思想：将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”.
voidBestFit(){//对分区大小进行排序,每次分配完一个进程的内存大小后，重新排序
    cout<<"最佳适应算法"<<endl;initial();int i,j,s,t;
    sortNeed best[MAXNUMBER];
    sortNeed temp;for(i=0;i<PNum;i++){
        best[i].pSize = FreeP[i];
        best[i].id = i;}for(i=0;i<SNum;i++){//冒泡排序(每次分配完一个进程后，都需要重新排序)for(s=0;s < PNum -1;s++){for(t = s;t < PNum -1;t++){if(best[s].pSize > best[t].pSize){
                    temp = best[s];
                    best[s]= best[t];
                    best[t]= temp;}}}for(j=0;j<PNum;j++){if(LeftSNeed[i]<= best[j].pSize){
                best[j].pSize -= LeftSNeed[i];
                LeftSNeed[i]=0;
                SWhere[i][best[j].id]= SName[i];break;}}
        LeftFreeP[best[j].id]= best[j].pSize;}display();}

4.最坏适应算法WF
算法思想：与最佳适应算法刚好相反，将空闲分区链的分区按照从大到小的顺序排序形成空闲分区链，每次查找时只要看第一个空闲分区是否满足即可。

voidWorstFit(){ 
    cout<<"最坏适应算法"<<endl;initial();int i,j,s,t;
    sortNeed temp;
    sortNeed Worst[MAXNUMBER];for(i =0;i<PNum;i++){Worst[i].pSize = FreeP[i];
        Worst[i].id = i;}for(i =0;i<SNum;i++){for(s=PNum-1;s>0;s--){for( t=0; t<s;t++){if(Worst[s].pSize > Worst[t].pSize){    temp = Worst[s];
                    Worst[s]= Worst[t];
                    Worst[t]= temp;}}}for(j=0;j<PNum;j++){if(LeftSNeed[i]<=Worst[j].pSize){
            Worst[j].pSize -= LeftSNeed[i];
            LeftSNeed[j]=0;
            SWhere[i][Worst[j].id]= SName[i];break;}}
        LeftFreeP[Worst[j].id]= Worst[j].pSize;}display();}

4.运行结果

在这里插入图片描述

在这里插入图片描述

5.程序源码

#include<iostream>#include<fstream>#include<iomanip>#include<stdlib.h>usingnamespace std;#define MAXNUMBER 100staticint PNum;//内存中空闲分区的个数staticint FreeP[MAXNUMBER];//空闲分区对应的内存staticint choose;//算法选择staticint SNum;//进程个数staticchar SName[MAXNUMBER];//进程名字staticint SNeed[MAXNUMBER];//进程大小staticchar SWhere[MAXNUMBER][MAXNUMBER];//各个进程的分区位置staticint LeftFreeP[MAXNUMBER];//分区的剩余大小 staticint LeftSNeed[MAXNUMBER];//进程剩余的大小 typedefstruct{int pSize;int id;}sortNeed;voidinput();//输入分区数和大小、资源数和大小voidinitial();//初始化供4个算法使用voiddisplay();//显示分区结果voidFirstFit();//首次适应算法FFvoidNextFit();//循环首次适应算法NFvoidBestFit();//最佳适应算法BFvoidWorstFit();//最坏适应算法WFvoidchoose_Algorithm();intmain(){input();choose_Algorithm();return0;}//输入分区数和大小、资源数和大小voidinput(){int i;
    ifstream inData;
    inData.open("datainput.txt");//读取数据
    inData>>PNum;//分区个数for(i=0;i<PNum;i++){//对应的内存
        inData>>FreeP[i];}
   inData>>SNum;//进程个数for(i=0;i<SNum;i++){//初始化名称
        SName[i]=i+65;}for(i=0;i<SNum;i++){
        inData>>SNeed[i];//进程大小}
    cout<<"进程名称: "<<"\t\t";for(i=0;i<SNum;i++){
        cout<<SName[i]<<"\t";}
    cout<<endl;
    cout<<"进程大小： "<<"\t\t";for(i=0;i<SNum;i++){
        cout<<SNeed[i]<<"\t";}
    cout<<endl;
 
    cout<<"分区名称: "<<"\t\t";for(i=0;i<PNum;i++){
        cout<<"P"<<i+1<<"\t";}
    cout<<endl<<"内存大小: "<<"\t\t";for(i=0;i<PNum;i++){
        cout<<FreeP[i]<<"\t";}}//初始化供4个算法使用voidinitial(){int i,j;for(i=0;i<SNum;i++){for(j=0;j<PNum;j++){
            SWhere[i][j]=NULL;
            LeftFreeP[j]= FreeP[j];}}for(i=0;i<SNum;i++){
        LeftSNeed[i]= SNeed[i];//代替ProcessNeed进行操作}}//显示分区结果voiddisplay(){int i;
    cout<<"进程名称: "<<"\t\t";for(i=0;i<SNum;i++){
        cout<<SName[i]<<"\t";}
    cout<<endl;
    cout<<"进程大小： "<<"\t\t";for(i=0;i<SNum;i++){
        cout<<SNeed[i]<<"\t";}
    cout<<endl;
 
    cout<<"分区名称: "<<"\t\t";for(i=0;i<PNum;i++){
        cout<<"P"<<i+1<<"\t";}
    cout<<endl<<"内存大小: "<<"\t\t";for(i=0;i<PNum;i++){
        cout<<FreeP[i]<<"\t";}
    cout<<endl<<"分区剩余内存大小: "<<"\t";for(i=0;i<PNum;i++){
        cout<<LeftFreeP[i]<<"\t";}
    cout<<endl<<"分区结果:"<<endl;for(i=0;i<PNum;i++){for(int j =0;j<SNum;j++){if(SWhere[j][i]!=NULL){
                cout<<SWhere[j][i]<<": P"<<i+1<<endl;}}}}//首次适应算法FFvoidFirstFit(){
    cout<<"首次适应算法"<<endl;initial();int i,j;for(i=0;i<SNum;i++){//遍历进程for(j=0;j<PNum;j++){//每次从分区的首地址开始查找//当系统内存分区足够大的时候，即分配给进程资源if(LeftSNeed[i]<= LeftFreeP[j]&& LeftFreeP!=0){
                LeftFreeP[j]-= LeftSNeed[i];//扣除分配给进程的资源
                LeftSNeed[i]=0;//当内存分区足够才执行，当前进程大小置0
                SWhere[i][j]= SName[i];//存储各个进程所在的分区位置break;//一个进程分区完后，立即进行下一个进程的判断}}}display();}//循环首次适应算法NFvoidNextFit(){
    cout<<"循环首次适应算法"<<endl;initial();int i,j,nextPoint =0;bool isWhile;for(i=0;i<SNum;i++){
        isWhile =true;while(isWhile){//每次都从当前分区的下一个分区开始查找if(LeftFreeP[nextPoint]>= LeftSNeed[i]){
                LeftFreeP[nextPoint]-= LeftSNeed[i];
                LeftSNeed[i]=0;
                SWhere[i][nextPoint]= SName[i];
                nextPoint++;if(nextPoint > PNum -1){
                    nextPoint =0;//当j遍历到分区末尾的时候，返回首位置}
                isWhile =false;}else{
                nextPoint++;if(nextPoint > PNum -1){
                    nextPoint =0;//当j遍历到分区末尾的时候，返回首位置}
                j++;if(j>=PNum){//避免死循环
                    isWhile=false;
                    j=0;}}}}display();}//最佳适应算法BFvoidBestFit(){//对分区大小进行排序,每次分配完一个进程的内存大小后，重新排序
    cout<<"最佳适应算法"<<endl;initial();int i,j,s,t;
    sortNeed best[MAXNUMBER];
    sortNeed temp;for(i=0;i<PNum;i++){
        best[i].pSize = FreeP[i];
        best[i].id = i;}for(i=0;i<SNum;i++){//冒泡排序(每次分配完一个进程后，都需要重新排序)for(s=0;s < PNum -1;s++){for(t = s;t < PNum -1;t++){if(best[s].pSize > best[t].pSize){
                    temp = best[s];
                    best[s]= best[t];
                    best[t]= temp;}}}for(j=0;j<PNum;j++){if(LeftSNeed[i]<= best[j].pSize){
                best[j].pSize -= LeftSNeed[i];
                LeftSNeed[i]=0;
                SWhere[i][best[j].id]= SName[i];break;}}
        LeftFreeP[best[j].id]= best[j].pSize;}display();}voidWorstFit(){//对分区大小进行排序,每次分配完一个进程的内存大小后，重新排序
    cout<<"最坏适应算法"<<endl;initial();int i,j,s,t;
    sortNeed temp;
    sortNeed Worst[MAXNUMBER];for(i =0;i<PNum;i++){Worst[i].pSize = FreeP[i];
        Worst[i].id = i;}for(i =0;i<SNum;i++)//冒泡排序(每次分配完一个进程后，都需要重新排序){for(s=PNum-1;s>0;s--){for( t=0; t<s;t++){if(Worst[s].pSize > Worst[t].pSize){    temp = Worst[s];
                    Worst[s]= Worst[t];
                    Worst[t]= temp;}}}for(j=0;j<PNum;j++){if(LeftSNeed[i]<=Worst[j].pSize){
            Worst[j].pSize -= LeftSNeed[i];
            LeftSNeed[j]=0;
            SWhere[i][Worst[j].id]= SName[i];break;}}
        LeftFreeP[Worst[j].id]= Worst[j].pSize;}display();}voidchoose_Algorithm(){
    cout<<"请选择算法“1-首次适应算法FF，2-循环首次适应算法NF，3-最佳适应算法BF，4-最坏适应算法WF”"<<endl;
 
    cin>>choose;
    cout<<endl;if(choose==1){FirstFit();choose_Algorithm();}elseif(choose==2){NextFit();choose_Algorithm();}elseif(choose==3){BestFit();choose_Algorithm();}elseif(choose==4){WorstFit();choose_Algorithm();}else{
        cout<<"请输入正确的选择“1-首次适应算法FF，2-循环首次适应算法NF，3-最佳适应算法BF，4-最坏适应算法WF”"<<endl;choose_Algorithm();//递归}}

输入格式

51005002003006004212417112426
标签： 算法 数据结构 windows
本文转载自: https://blog.csdn.net/weixin_51080803/article/details/129911799
版权归原作者 落灬枫 所有， 如有侵权，请联系我们删除。
登录后发布评论

“动态分区分配算法（操作系统实验 C＋＋）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航