パーティション割当てアルゴリズム
49706 ワード
パーティション割当てアルゴリズム
1.アルゴリズムFF(First Fit)の基本思想に初めて適応する:空きパーティションをアドレスの増加順に並べることを要求する.メモリ割り当てを行うと、空き領域の先頭から、サイズの要件を満たす最初の空き領域が見つかるまで順番に検索されます.リクエスト者に1つに分けて、残りの部分は空き領域に残っています.
2.最適適応アルゴリズムBF(Best Fit)の基本思想:BFの空きパーティションテーブル(または空きパーティションチェーン)は、空き領域サイズの昇順方法で組織される.割り当て時に、空きパーティションテーブル(または空きパーティションチェーン)の前後順に、最初から検索し、要求に合致する最初のパーティションを見つけます.それが最適(すなわち最適)であることを示します.大きな空き領域を残すことができます.
最悪適応アルゴリズムWF(Worst Fit)の基本思想:空きパーティションの大きさに応じて大きいから小さいまでソートするため、毎回常に最大の空きパーティションから検索を開始し、最初の空きパーティションが満たされなければ検索を終了する.
1.アルゴリズムFF(First Fit)の基本思想に初めて適応する:空きパーティションをアドレスの増加順に並べることを要求する.メモリ割り当てを行うと、空き領域の先頭から、サイズの要件を満たす最初の空き領域が見つかるまで順番に検索されます.リクエスト者に1つに分けて、残りの部分は空き領域に残っています.
2.最適適応アルゴリズムBF(Best Fit)の基本思想:BFの空きパーティションテーブル(または空きパーティションチェーン)は、空き領域サイズの昇順方法で組織される.割り当て時に、空きパーティションテーブル(または空きパーティションチェーン)の前後順に、最初から検索し、要求に合致する最初のパーティションを見つけます.それが最適(すなわち最適)であることを示します.大きな空き領域を残すことができます.
最悪適応アルゴリズムWF(Worst Fit)の基本思想:空きパーティションの大きさに応じて大きいから小さいまでソートするため、毎回常に最大の空きパーティションから検索を開始し、最初の空きパーティションが満たされなければ検索を終了する.
#include
");
printf("* 1. FF(First Fit) *
");
printf("* 2. BF(Best Fit) *
");
printf("* 3. WF(Worst Fit) *
");
printf("* 4. *
");
printf("* 0. *
");
printf("-------------------------------------------------
");
}
void print(Part p[])//
{
int i,j;
for (i = 0; i < PN; i++)
{
if (p[i].SZ == 0)//
{
printf(" %d
", i + 1);
for (j = i; j < PN - 1; j++)
p[j] = p[j + 1];
PN--;
}
}
printf("
");
for (i = 0; i < PN; i++)
printf("%4d%6d%5d
", p[i].ID, p[i].SA, p[i].SZ);
}
void Copy(Part p[], Part s[])
{
int i;
for (i = 0; i < PN; i++)
{
s[i].ID = p[i].ID;
s[i].SA = p[i].SA;
s[i].SZ = p[i].SZ;
}
}
void Sort(Part p[])//WF、BF ，
{
int i, n = PN;
bool flag = true;
while (n > 1 && flag)
{
flag = false;
for (i = 0; i < n - 1; i++)
if (p[i].ID>p[i + 1].ID)
{
Partition temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
flag = true;
}
n--;
}
}
void Judge(Part p[])//
{
int i, j;
bool flag, free[max];
for (i = 0; i < PN; i++)
free[i] = true;
for (i = 0; i < WN; i++)
{
flag = true;
for (j = 0; j < PN&&flag; j++)
if (work[i] <= p[j].SZ&&free[j])// j i
{
p[j].SA += work[i];
p[j].SZ -= work[i];
flag = false;
free[j] = false;
}
if (flag)
{
printf(" ! %d .
", i + 1); break;
}
}
}
bool Check(Part p[])//
{
int i,j;
bool flag = true;
for (i = 1; flag&&i < PN; i++)
if (p[i].SA <( p[i - 1].SA + p[i-1].SZ))
flag = false;
else if (p[i].SA ==(p[i - 1].SA + p[i-1].SZ))
{
printf("
");
p[i - 1].SZ += p[i].SZ;
for (j = i; j < PN-1; j++)
p[j] = p[j + 1];
PN--;
print(p);
}
return flag;
}
void Free(Part p[])// ，
{
int i, choice, size;
bool flag;
printf(" ");
scanf("%d%d", &choice, &size);
Sort(p);
p[choice - 1].SZ += size;
flag=Check(p);
if (flag) {
printf(" !
"); print(p);
}
else
{
printf(" ， !");
p[choice - 1].SZ -= size;
}
}
void FF()//
{
printf("----------------------FF -------------------------
");
int i, j, n = PN;
bool flag = true;
Part p[max];
Copy(PT, p);
while (n > 1 && flag)
{
flag = false;
for (i = 0; i < n - 1; i++)
if (p[i].SA>p[i + 1].SA)
{
Partition temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
flag = true;
}
n--;
}
printf(" :
");
print(p);
Judge(p);
Sort(p); Copy(p, PT);
print(PT);
}
void BF()//
{
printf("----------------------BF -------------------------
");
int n = PN, i, j;
bool flag = true;
Part p[max];
Copy(PT, p);
while (n > 1 && flag)
{
flag = false;
for (i = 0; i < n - 1; i++)
if (p[i].SZ>p[i + 1].SZ)
{
Partition temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
flag = true;
}
n--;
}
printf(" :
");
print(p);
Judge(p);
Sort(p); Copy(p, PT);
print(PT);
}
void init()
{
int i;
bool flag;
printf(" : : ");
scanf("%d", &PN);
printf(" 、 、
");
for (i = 0; i < PN; i++)
{
printf(" ", i + 1);
scanf("%d%d%d", &(PT[i].ID), &(PT[i].SA), &(PT[i].SZ));
}
flag = Check(PT);
if(!flag)
{
printf(" ! !
");
init();
}
}
void Apply()//
{
int i;
int choice;
printf(" : "); scanf("%d", &WN);
printf(" :
");
for (i = 0; i < WN; i++)
{
printf("%3d ", i + 1);
scanf("%d", &work[i]);
}
printf(" :(1)FF (2)BF ");
scanf("%d", &choice);
if (choice == 1)FF();
if (choice == 2)BF();
}
void WF()
{
printf("----------------------WF -------------------------
");
int n = PN, i, j;
bool flag = true;
Part p[max];
Copy(PT, p);
while (n > 1 && flag)
{
flag = false;
for (i = 0; i < n - 1; i++)
if (p[i].SZ<p[i + 1].SZ)
{
Partition temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
flag = true;
}
n--;
}
printf(" :
");
print(p);
Judge(p);
Sort(p); Copy(p, PT);
print(p);
}
int main()
{
bool flag = true;
int choice;
Menu();
init();
print(PT);
CHOICE: printf(" (1) (2) ");
scanf("%d", &choice);
if(choice==1) Apply();
if(choice== 2)Free(PT);
int n;
printf(" ? 1 0 :");
scanf("%d", &n);
if (n == 1) goto CHOICE;
else return 0;
}