最適適応アルゴリズムC言語実装

広東工業大学オペレーティングシステム実験
最適な適応アルゴリズムを用いた動的パーティション割り当てプロセスと回収プロセスをC言語で実現した.
ここで、空きパーティションは、空きパーティションチェーン(テーブル)によって管理される.メモリ割り当てを行う場合、システムは空き領域のローエンドの空間を優先的に使用し、割り当てと回収のたびに空きメモリパーティションチェーンを表示する必要があります.

#include 
#include 
#include 

#define FREE 0
#define BUSY 1
#define Max_length 640

typedef struct freearea//       
{
     
    int ID;//   
    int size;//    
    int address;//    
    bool isUsed;//    ，0    ，1    
} freearea;

typedef struct DuNode//            
{
     
    freearea data;//   
    struct DuNode *prior;//   
    struct DuNode *next;
} DuNode, *DuLinkList;

DuLinkList m_rid;
DuLinkList m_last;

void init()//        
{
     
    m_rid = (DuLinkList)malloc(sizeof(DuNode));
    m_last = (DuLinkList)malloc(sizeof(DuNode));

    m_rid->prior = NULL;
    m_rid->next = m_last;

    m_last->prior = m_rid;
    m_last->next = NULL;

    m_rid->data.size = 0;
    m_rid->data.isUsed = BUSY; //        ，               

    m_last->data.address = 0;
    m_last->data.size = Max_length;
    m_last->data.ID = 0;
    m_last->data.isUsed = 0;
}

int best_fit(int ID,int size)//      
{
     
    int surplus;//              
    DuLinkList temp = (DuLinkList)malloc(sizeof(DuNode));
    DuNode *p = m_rid->next;
    DuNode *q = NULL;//      

    temp->data.ID = ID;
    temp->data.size = size;
    temp->data.isUsed = BUSY;

    while(p)//    ，              q
    {
     
        if (p->data.isUsed==FREE && p->data.size >= size)
        {
     
            q = p;
            surplus = p->data.size - size;
            break;
        }

        p=p->next;
    }

    while(p)//    ，       
    {
     
        if (p->data.isUsed == FREE && p->data.size == size) //              
        {
     
            p->data.isUsed = BUSY;
            p->data.ID = ID;

            return 1;
        }

        if (p->data.isUsed == FREE && p->data.size > size) //              
        {
     
            if (surplus > p->data.size - size)
            {
     
                surplus = p->data.size-size;
                q = p;
            }
        }

        p=p->next;
    }

    if (q == NULL)//      
        return 0;
    else//      
    {
     
        // temp     q  
        temp->next = q;
        temp->prior = q->prior;
        temp->data.address = q->data.address;

        q->prior->next = temp;
        q->prior = temp;

        q->data.size = surplus;
        q->data.address += size;

        return 1;
    }
}

void alloc()//    
{
     
    int ID,size1;

    printf("      ：");
    scanf("%d", &ID);
    printf("         ：");
    scanf("%d", &size1);

    if (ID<=0 || size1<=0)
        printf("  ！                 ");

    if(best_fit(ID,size1))
        printf("      ！
");
    else
        printf("      ！
");
}

void freeNode()//    
{
     
    int ID;
    DuNode *p = m_rid->next;

    printf("            ：");
    scanf("%d", &ID);

    while (p)
    {
     
        if (p->data.ID == ID)
        {
     
            p->data.ID = 0;
            p->data.isUsed = FREE;

            if (!p->prior->data.isUsed && p->next->data.isUsed)//         ，   
            {
     
                p->prior->data.size += p->data.size;
                p->prior->next = p->next;
                p->next->prior = p->prior;
            }

            if (!p->next->data.isUsed && p->prior->data.isUsed) //         ，   
            {
     
                p->data.size += p->next->data.size;

                if(p->next->next)
                {
     
                    p->next->next->prior=p;
                    p->next = p->next->next;
                }
                else
                    p->next = p->next->next;
            }

            if(!p->prior->data.isUsed && !p->next->data.isUsed) //         
            {
     
                p->prior->data.size += p->data.size + p->next->data.size;
                if(p->next->next)
                {
     
                    p->next->next->prior = p->prior;
                    p->prior->next = p->next->next;
                }
                else
                    p->prior->next = p->next->next;
            }

            printf("      ！
");
            break;
        }

        p = p->next;

        if(!p)
            printf("               ！");
    }
}

void show()
{
     
    printf("------------------");
    printf("      ");
    printf("------------------
");

    DuNode *p = m_rid->next;

    while(p)
    {
     
        printf("   ：");
        if (p->data.ID==FREE)
            printf("FREE
");
        else
            printf("%d 
", p->data.ID);

        printf("    ：%d
", p->data.address);
        printf("    ：%d
", p->data.size);
        printf("    ：");

        if (p->data.isUsed==FREE)
            printf("  
");
        else
            printf("   
");

        printf("------------------
");

        p=p->next;
    }
}

int main()
{
     
    printf("------------------");
    printf("      ");
    printf("------------------
");

    init();

    int tag = 1;

    while(tag < 3 && tag > 0)
    {
     
        printf("        ");
        printf("（1-    ，2-    ，  -    ）：");
        scanf("%d", &tag);

        switch(tag)
        {
     
        case 1:
            alloc();
            show();
            break;
        case 2:
            freeNode();
            show();
            break;
        default:
            printf("     ！");
        }
    }
}