初適応アルゴリズムC言語実装
32430 ワード
広東工業大学オペレーティングシステム実験
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(" !");
}
}
}