動态分區-首次适應&最佳适應

編寫并調試一個可變式分區配置設定的存儲管理方案。并模拟實作分區的配置設定和回收過程。

對分區的配置設定算法可以是下面三種算法之一：

• 首次适應算法
• 循環首次适應算法
• 最佳适應算法

1，在記憶體配置設定時，系統優先使用空閑區低端的空間

10240+102380=112640 從位址112460開始配置設定，由低端向高端增長。

例如：配置設定給作業1，作業長度20，==》起始位址：112620，長度20，标志1。

每次配置設定，從起始位址最大的結點開始查找是否有合适區域

2,首次适應算法

// Memory_V1.cpp : 定義控制台應用程式的入口點。

/*
*Name:Memory_V1.cpp
*Author:WangLin
*Created On:2015/11/04
*Function:首次适應算法 可變式分區配置設定，模拟實作分區的配置設定和回收過程。 
*/
#include "stdafx.h"
# include<iostream>
using namespace std;

struct  partition //分區結構體：起始位址+分區長度＋标志
{
    int addr;
    int length;
    int tag;
    partition* next;
};
partition *empty=new partition; //空閑分區
partition *busy=new partition;//已配置設定區


//初始化函數
void init()
{
    //空閑分區初始化,empty和busy始終指向首位址最大結點，即低端第一個結點
    empty->addr=;
    empty->length=;
    empty->tag=;//1表示可用
    empty->next=NULL;

    //已配置設定區初始化
    busy->addr=;
    busy->length=;
    busy->tag=;//0表示空閑
    busy->next=NULL;
}

/*
配置設定主存
*/
void distriMemory()
{
    int pname,plength;
    partition* temp=new partition;
    cout<<"輸入作業名(請輸入數字)：";
    cin>>pname;
    temp->tag=pname;
    cout<<endl;

    cout<<"輸入作業所需長度xk:";
    cin>>plength;
    temp->length=plength;

    //為新作業配置設定主存,在空閑區表中，尋找長度大于等于temp結點長度的結點
    partition* q=new partition;
    partition* p=new partition;
    bool isfind=false;//标志是否找到可配置設定的區域
    for(q=empty;;p=q,q=q->next)//p是q的前驅
    {
        if((q->tag==)&&(q->length>=temp->length))
        {
            isfind=true;
            temp->addr=(q->addr+q->length)-temp->length;//在已配置設定區表中建立配置設定結點，配置設定區域
            q->length-=temp->length;    //修改空閑區表長度
            if(q->length==)//長度為0，區域已經不可以再配置設定了，從空閑區表删除
            {
                if(q==empty)//删除首結點
                    empty=empty->next;
                else
                    p->next=q->next;
            }
            break;
        }
    }
    if(isfind)
    {
        //修改已配置設定區表，temp挂到busy隊列中
        for(q=busy;;p=q,q=q->next)//找到第1個addr<temp->addr的結點q,temp插在q前面
            if(q->addr<temp->addr)break;
        if(q==busy)
        {
            temp->next=busy;//先連
            busy=temp;//後斷
        }
        else
        {
            temp->next=q;//先連
            p->next=temp;//後斷
        }
        cout<<"記憶體已配置設定！"<<endl;
    }
    else
        cout<<"找不到合适大小的區域，記憶體配置設定失敗！"<<endl;
}

/*
回收主存：4種情況
*/
void colletMemory()
{
    int pname;
    cout<<"輸入要回收分區的作業名：";
    cin>>pname;

    //在已配置設定區表中，按作業名查找要回收的結點p，何時删除這個結點？
    partition* q=new partition;
    partition* bfp=new partition;//p的前驅
    partition* p=new partition;
    partition* m=new partition;
    for(p=busy;p!=NULL;bfp=p,p=p->next)
    {
        if((p->tag==pname)&&(p->addr!=)&&(p->length)!=)
        {

            if(p==busy)
                busy=busy->next;
            else
                bfp->next=p->next;
            p->next=NULL;//從已配置設定區表中取下p結點
            break;
        }
    }
    if(p!=NULL)
    {
        //==============4種情況修改空閑表========================================
        for(q=empty;;m=q,q=q->next)//尋找位址和p相鄰的結點,m->addr>p->addr>q->addr
            if((q->tag==)&&(q->addr<p->addr))
                break;
        //case1回收區與插入點的前一個空閑分區F1相鄰接，此時将兩個分區合并() p和m相鄰，修改m，删除p
        if(((p->addr+p->length)==m->addr)&&((q->addr+q->length)!=p->addr))
        {
            m->length+=p->length;
            m->addr-=p->length;
            m->tag=;
            delete(p);
        }

        //case2回收區與插入點的後一個空閑分區F2相鄰接，此時将兩個分區合并,p和q相鄰，修改p，删除q
        else if(((q!=empty)&&(p->addr+p->length)!=m->addr)&&((q->addr+q->length)==p->addr))
        {
            q->length+=p->length;
            q->tag=;
            delete(p);
        }
        //3)回收區與插入點的前，後兩個空閑分區相鄰接，此時将三個分區合并,m,p,q相鄰，修改m，删除p,q
        else if(((p->addr+p->length)==m->addr)&&((q->addr+q->length)==p->addr))
        {
            m->length+=(p->length+q->length);
            m->addr-=(p->length+q->length);
            m->next=q->next;
            m->tag=;
            delete(p);
            delete(q);
        }

        //4)回收區既不與F1相鄰接，又不與F2相鄰接，此時應為回收區單獨建立一個新表項,p挂到空閑表區中m和q之間
        else
        {
            p->tag=;
            if(q==empty)
            {
                if(((q->addr+q->length)==p->addr))
                    q->length+=p->length;
                else
                {
                    p->next=empty;
                    empty=p;
                }
            }
            else
            {
                p->next=q;//先連
                m->next=p;//後斷
            }
        }
        //================空閑表區修改完畢-===================
        cout<<"記憶體已回收！"<<endl;
    }
    else
        cout<<"作業不存在！"<<endl;
}

/*顯示主存
(1)顯示空閑分區表 empty
(2)顯示已配置設定表busy
*/
void dispMemory()
{
    partition *p=new partition;
    char ch;
    p=empty;//(1)顯示空閑分區表 empty
    cout<<endl<<"+++++++++++++"<<endl<<"【輸出空閑分區表】"<<endl;
    cout<<"起始位址"<<"     "<<"分區長度"<<"        "<<"标志"<<endl;
    while(p!=NULL)
    {
        cout<<p->addr<<"            ";
        cout<<p->length<<"         ";
        cout<<p->tag<<endl;
        p=p->next;
    }

    p=busy;//(2)輸出已配置設定區表 busy
    cout<<endl<<"+++++++++++++"<<endl<<"【輸出已配置設定區表】"<<endl;
    cout<<"起始位址"<<"     "<<"分區長度"<<"        "<<"标志"<<endl;
    while(p!=NULL)
    {
        cout<<p->addr<<"            ";
        cout<<p->length<<"         ";
        cout<<p->tag<<endl;
        p=p->next;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    init();
    bool stop_flag=true;//程式結束标志
    int ch;
    while(stop_flag)
    {
        cout<<endl<<"============================================================="<<endl;
        cout<<"選擇功能項<0-退出；1-配置設定主存；2-回收主存；3-顯示主存>"<<endl;
        cout<<"顯示功能項<0-3>:";
        cin>>ch;
        switch (ch)
        {
        case :cout<<"程式已結束,再見！"<<endl;stop_flag=false;
            break;
        case :distriMemory();
            break;
        case :colletMemory();
            break;
        case :dispMemory();
            break;
        default:cout<<"輸入有誤，請重新輸入"<<endl;
            break;
        }
    }
    return ;
}



           

【調試結果】：

3 .最佳适應算法

/*
配置設定主存
*/
void distriMemory()
{
    int pname,plength;
    partition* temp=new partition;
    cout<<"輸入作業名(請輸入數字)：";
    cin>>pname;
    temp->tag=pname;
    cout<<endl;

    cout<<"輸入作業所需長度xk:";
    cin>>plength;
    temp->length=plength;

    //為新作業配置設定主存,在空閑區表中，尋找長度大于等于temp結點長度的結點
    partition* q=new partition;
    partition* p=new partition;


    //從全部空閑區中找出能滿足作業需求的容量最小的空閑區配置設定之
    q->length=MAXLENGTH;
    partition* s=empty;
    partition* ps=new partition;
    while(s!=NULL)
    {
        if((s->tag==)&&(s->length>=temp->length))
        {
            if(s->length<q->length)
            {
                p=ps;//p是q的前驅
                q=s;
            }
        }
        ps=s;//ps是s的前驅
        s=s->next;
    }
    if(q->length!=MAXLENGTH)//如果找到可以配置設定的區域
    {
        temp->addr=(q->addr+q->length)-temp->length;//在已配置設定區表中建立配置設定結點，配置設定區域
        q->length-=temp->length;    //修改空閑區表長度
        if(q->length==)//長度為0，區域已經不可以再配置設定了，從空閑區表删除
        {
            if(q==empty)//删除首結點
                empty=empty->next;
            else
                p->next=q->next;
        }

        //修改已配置設定區表，temp挂到busy隊列中
        for(q=busy;;p=q,q=q->next)//找到第1個addr<temp->addr的結點q,temp插在q前面
            if(q->addr<temp->addr)break;
        if(q==busy)
        {
            temp->next=busy;//先連
            busy=temp;//後斷
        }
        else
        {
            temp->next=q;//先連
            p->next=temp;//後斷
        }
        cout<<"記憶體已配置設定！"<<endl;
    }
    else
        cout<<"找不到合适大小的區域，記憶體配置設定失敗！"<<endl;
}