#操作系统#使用动态分区分配方式的模拟

实验内容
（1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
•作业1申请130KB。
•作业2申请60KB。
•作业3申请100KB。
•作业2释放60KB。
•作业4申请200KB。
•作业3释放100KB。
•作业1释放130KB。
•作业5申请140KB。
•作业6申请60KB。
•作业7申请50KB。
•作业6释放60KB。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。

代码

#include<iostream>
#include <vector>
using namespace std;

struct p_cb
{
    int id;
    int pcb_size;
};
struct memory
{
    int number;  //序号
    int front_number;  //前一个的***
    int id;  //占用程序的id 0为未占用
    bool flag;//0为未被占用
    int M_size; //大小
};

p_cb pc1={1,130};
p_cb pc2={2,60};
p_cb pc3={3,100};
p_cb pc4={4,200};
p_cb pc5={5,140};
p_cb pc6={6,60};
p_cb pc7={7,50};
struct memory M[2]={
    {0,0,0,1,0},
    {640,0,0,0,640}
};
vector<memory> M_queue;
memory temp;
vector<memory> best_queue;
int chose;
void M_merge(int mer_id)  //合并
{
    if((mer_id<M_queue.size()-1)&&(M_queue[mer_id+1].flag==0))
    {
        M_queue[mer_id+1].M_size+=M_queue[mer_id].M_size;
        M_queue[mer_id+1].front_number=M_queue[mer_id].front_number;
        M_queue.erase(M_queue.begin()+mer_id);
    }
    else{}
    if(M_queue[mer_id-1].flag==0)
    {
        M_queue[mer_id].M_size+=M_queue[mer_id-1].M_size;
        M_queue[mer_id].front_number=M_queue[mer_id-1].front_number;
        M_queue.erase(M_queue.begin()+mer_id-1);
    }
    else {}
}
void M_print()
{   cout<<"-----------------------------------"<<endl;
    cout<<"前序号\t序号\t程序ID\t内存大小\t标志"<<endl;
    for(int i=1;i<M_queue.size();i++)
    {
        cout<<M_queue[i].front_number<<"\t"<<M_queue[i].number<<"\t"<<M_queue[i].id<<"\t"<<M_queue[i].M_size<<"\t\t"<<M_queue[i].flag<<endl;
    }
    cout<<"-----------------------------------"<<endl;
    cout<<endl<<endl;
}
void alloc(p_cb p1)
{
    if(chose==1)   //首次适应算法
    {
        for(int i=0;i<M_queue.size();i++)
        {
            if((M_queue[i].flag==0)&&p1.pcb_size<M_queue[i].M_size)
            {
                temp.flag=1;
                temp.id=p1.id;
                temp.front_number=M_queue[i].front_number;
                temp.M_size=p1.pcb_size;
                temp.number=M_queue[i].front_number+p1.pcb_size;
                M_queue[i].front_number=temp.number;
                M_queue[i].M_size-=p1.pcb_size;
                M_queue.insert(M_queue.begin()+i,temp);
                break;

            }
        }

    }
    else if(chose==2)   //最佳适应算法
    {
        int best_num=640;
        int best_i;
        for(int i=0;i<M_queue.size();i++)
        {
            if((M_queue[i].flag==0)&&(M_queue[i].M_size>=p1.pcb_size)&&(M_queue[i].M_size<=best_num))
            {
                best_num=M_queue[i].M_size;
                best_i=i;
            }
        }
        temp.flag=1;
        temp.id=p1.id;
        temp.front_number=M_queue[best_i].front_number;
        temp.M_size=p1.pcb_size;
        temp.number=M_queue[best_i].front_number+p1.pcb_size;
        M_queue[best_i].front_number=temp.number;
        M_queue[best_i].M_size-=p1.pcb_size;
        M_queue.insert(M_queue.begin()+best_i,temp);


    }
    else{

    }

    M_print();
}
void free(p_cb p2)
{   int id;
    for(int i=0;i<M_queue.size();i++)
    {

        if(p2.id==M_queue[i].id)
        {
            M_queue[i].flag=0;
            M_queue[i].id=0;
            id=i;
            break;
        }
    }
    M_merge(id);
    M_print();

}

int main()
{

    M_queue.push_back(M[0]);
    M_queue.push_back(M[1]);
    best_queue.assign(M_queue.begin(),M_queue.begin()+M_queue.size());
    cout<<"1、首次适应算法\n2、最佳适应算法\n请输入:";
    cin>>chose;

    if(chose!=1&&chose!=2)
    {
        cout<<"error"<<endl;
    }

    cout<<"alloc(process[1])"<<endl;
    alloc(pc1);

    cout<<"alloc(process[2])"<<endl;
    alloc(pc2);

    cout<<"alloc(process[3])"<<endl;
    alloc(pc3);

    cout<<"free(process[2])"<<endl;
    free(pc2);

    cout<<"alloc(process[4])"<<endl;
    alloc(pc4);

    cout<<"free(process[3])"<<endl;
    free(pc3);

    cout<<"free(process[1])"<<endl;
    free(pc1);

    cout<<"alloc(process[5])"<<endl;
    alloc(pc5);

    cout<<"alloc(process[6])"<<endl;
    alloc(pc6);

    cout<<"alloc(process[7])"<<endl;
    alloc(pc7);

    cout<<"free(process[6])"<<endl;
    free(pc6);

    return 0;
}

• 运行结果截图：

使用首次适应算法：
最佳适应算法：