初適応アルゴリズム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 first_fit(int ID,int size)//      
{
     
    DuLinkList temp = (DuLinkList)malloc(sizeof(DuNode));
    DuNode *p = m_rid->next;

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

    while(p)
    {
     
        if(p->data.ID == ID)//         
        {
     
            printf("               !");

            return 0;
        }

        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)//         ,             
        {
     
            temp->next=p;
            temp->prior=p->prior;
            temp->data.address=p->data.address;

            p->prior->next=temp;
            p->prior=temp;
            p->data.address=temp->data.address+temp->data.size;
            p->data.size-=size;

            return 1;
        }

        p=p->next;
    }

    return 0;
}

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

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

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

    if(first_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(" !"); } } }