首次適應(yīng)算法
首次適應(yīng)算法找到一個(gè)可以分配的內(nèi)存塊就進(jìn)行分配，下一次分配時(shí)還是從空閑分區(qū)鏈頭開始找，該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)，這為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。
但是低址部分不斷被劃分，會(huì)留下許多難以利用的，很小的空閑分區(qū)(碎片)。而每次查找又都是從低址部分開始的，會(huì)增加查找可用空閑分區(qū)時(shí)的開銷;
定義內(nèi)存塊，作業(yè)，分區(qū)鏈結(jié)構(gòu)體?？臻e分區(qū)用循環(huán)鏈表串起,正在運(yùn)行的作業(yè)用數(shù)組記錄，分配失敗的作業(yè)用另一個(gè)數(shù)組記錄。設(shè)置開始分配時(shí)起始指針(上一次分配的內(nèi)存塊的后一塊)，查找時(shí)使用的遍歷指針，分區(qū)起始地址最小的鏈頭指針，一個(gè)空閑分區(qū)的最小大小。
查找過程如果找到符合的分區(qū)，就分配給作業(yè)，將作業(yè)放入運(yùn)行中數(shù)組；否則放入分配失敗數(shù)組
回收過程查找運(yùn)行作業(yè)數(shù)組,從鏈頭開始對比分區(qū)起始地址加上大小后 與作業(yè)分配的起始地址的大?。?/p>
若小于則往后找分區(qū)；
若大于則判斷作業(yè)起始地址加上分配的大小 與分區(qū)起始地址的關(guān)系，關(guān)系為等于則修改分區(qū)內(nèi)容，否則將分配給作業(yè)的內(nèi)存空間構(gòu)造新分區(qū)插入空閑分區(qū)鏈合適位置；
若等于則判斷作業(yè)起始地址加上分配的大小 與下一空閑分區(qū)起始地址的關(guān)系，若相等則修改當(dāng)前分區(qū)并刪除下一分區(qū)，不等則只修改分區(qū)
代碼如下
#include<iostream>
#include <conio.h>
using namespace std;
struct block
{
int address; //內(nèi)存塊起始地址
int size; //內(nèi)存塊大小
}BLOCK; //內(nèi)存塊
struct job
{
char id[10]; //作業(yè)id
int address; //作業(yè)分配的內(nèi)存起始地址
int size; //作業(yè)需要的大小
int alloc_size; //作業(yè)分配的大小
}; //作業(yè)
struct free_blocks_linklist
{
block free_block; //空閑內(nèi)存塊
free_blocks_linklist* next; //指向下一內(nèi)存塊的指針
}Free_Blocks_linklist; //空閑分區(qū)鏈
job running_job[10]; //運(yùn)行中的作業(yè)數(shù)組
int running_job_num = 0;
job waiting_job[10]; //分配失敗后等待的作業(yè)數(shù)組
int waiting_jon_num = 0;
job finish_job[10]; //完成的作業(yè)數(shù)組
int finish_job_num = 0;
free_blocks_linklist * header = nullptr; //內(nèi)存分區(qū)鏈頭指針
void Init()
{
header = new free_blocks_linklist;
cout << "請輸入內(nèi)存大小(kB) : ";
cin >> header->free_block.size;
cout << "請輸入內(nèi)存起始地址 : ";
cin >> header->free_block.address;
header->next = header;
/*cin >> hex >> a;
cout << a << endl;
cout << hex <<a;*/
}
bool alloc_memory(job &j)
{
free_blocks_linklist* temp = header;
if (temp == nullptr)
{
cout << "\n\n內(nèi)存不足分配失敗" << endl;
return false;
}
while (1)
{
if (temp->free_block.size < j.size && temp->next != header)
temp = temp->next; //分區(qū)內(nèi)存不夠且后面還有分區(qū)
else if (temp->free_block.size == j.size) //分區(qū)內(nèi)存正好
{
if (temp->next == temp) //只剩一個(gè)分區(qū)
{
j.address = temp->free_block.address;
j.alloc_size = j.size;
delete temp;
header = nullptr;
cout << "\n\n分配內(nèi)存成功" << endl;
return true;
}
else //有多個(gè)分區(qū)
{
j.address = temp->free_block.address;
j.alloc_size = j.size;
temp = temp->next;
delete temp;
cout << "\n\n分配內(nèi)存成功" << endl;
return true;
}
}
else if (temp->free_block.size > j.size) //內(nèi)存塊分配后還有空間
{
j.address = temp->free_block.address;
j.alloc_size = j.size;
temp->free_block.size -= j.size;
temp->free_block.address += j.size;
cout << "\n\n分配內(nèi)存成功" << endl;
cout << "\n\n請按任意鍵繼續(xù)" << endl;
_getch();
return true;
}
else
{
cout << "\n\n沒有合適內(nèi)存塊分配" << endl;
return false;
}
}
}
void run_job(job j)
{
if (true == alloc_memory(j)) //分配成功
running_job[running_job_num++] = j;
else
waiting_job[waiting_jon_num++] = j;
}
void show_message()
{
system("cls");
free_blocks_linklist* temp = header;
int i = 1;
cout << "\n\n當(dāng)前運(yùn)行的作業(yè)數(shù)量為：" << running_job_num <<endl;
cout << "正在等待分配內(nèi)存的作業(yè)數(shù)量(分配內(nèi)存失敗)為：" << waiting_jon_num << endl;
cout << "已完成作業(yè)數(shù)量為： " << finish_job_num << endl;
cout << "\n當(dāng)前內(nèi)存空間信息如下 : " << endl;
if (header != nullptr)
{
do
{
cout << "\n內(nèi)存塊" << i << "起始地址為: " << temp->free_block.address << endl;
cout << "內(nèi)存塊" << i << "大小為: " << temp->free_block.size << endl;
temp = temp->next;
i++;
} while (temp != header);
}
else cout << "\n內(nèi)存空間已經(jīng)用完" << endl;
cout << "\n\n請按任意鍵繼續(xù)" << endl;
_getch();
}
void input_job()
{
job temp;
cout << "請輸入作業(yè)名: " << endl;
cin >> temp.id;
cout << "請輸入作業(yè)大小: " << endl;
cin >> temp.size;
run_job(temp);
show_message();
return;
}
void release_memory(int count) //count為要釋放作業(yè)的序號
{
if (header == nullptr)
{
header = new free_blocks_linklist;
header->free_block.address = running_job[count].address;
header->free_block.size = running_job[count].alloc_size;
header->next = header;
}
else
{
free_blocks_linklist* temp = header;
while (temp->next != header)
{
temp = temp->next;
} //找到鏈尾
if (running_job[count].address == temp->free_block.address + temp->free_block.size)
{ //作業(yè)分配的內(nèi)存地址最大且可合并
temp->free_block.size += running_job[count].alloc_size;
}
else if (running_job[count].address > temp->free_block.address + temp->free_block.size)
{ //作業(yè)分配的內(nèi)存地址最大且不可合并
free_blocks_linklist* temp1 = new free_blocks_linklist;
temp1->free_block.address = running_job[count].address;
temp1->free_block.size = running_job[count].alloc_size;
temp1->next = header;
temp->next = temp1;
}
else if (header->free_block.address == running_job[count].address + //作業(yè)分配的地址最小且可合并
running_job[count].alloc_size)
{
header->free_block.address = running_job[count].address;
header->free_block.size += running_job[count].alloc_size;
}
else if (header->free_block.address > running_job[count].address + //作業(yè)分配的地址最小且不可合并
running_job[count].alloc_size)
{
temp = new free_blocks_linklist;
temp->free_block.address = running_job[count].address;
temp->free_block.size = running_job[count].alloc_size;
temp->next = header;
free_blocks_linklist* temp1 = header;
while (temp1->next != header)
temp1 = temp1->next;
temp1->next = temp;
header = temp;
}
else //作業(yè)回收的地址在分區(qū)鏈中間
{
temp = header;
while (temp->next->free_block.address + temp->next->free_block.size < running_job[count].address)
temp = temp->next; //找到要插入的前一分區(qū)位置temp
if (temp->free_block.address + temp->free_block.size == running_job[count].address)
{ //前分區(qū)可以合并
if (running_job[count].address + running_job[count].alloc_size == temp->next->free_block.address)
{ //回收時(shí)可以和前后分區(qū)合并
temp->free_block.size += running_job[count].alloc_size + temp->next->free_block.size;
free_blocks_linklist* temp1 = temp->next;
temp->next = temp1->next;
delete temp1;
}
else //只能與前分區(qū)合并
{
temp->free_block.size += running_job[count].alloc_size;
}
}
else //前分區(qū)不可合并
{
if (temp->next->free_block.address == running_job[count].address + running_job[count].alloc_size)
{//后分區(qū)可以合并
temp->next->free_block.address -= running_job[count].alloc_size;
temp->next->free_block.size += running_job[count].alloc_size;
}
else
{//后分區(qū)不可以合并
free_blocks_linklist* temp1 = new free_blocks_linklist;
temp1->free_block.address = running_job[count].address;
temp1->free_block.size = running_job[count].alloc_size;
temp1->next = temp->next;
temp->next = temp1;
}
}
}
}
finish_job[finish_job_num++] = running_job[count];
running_job[count] = running_job[--running_job_num];
cout << "釋放內(nèi)存成功" << endl;
cout << "\n\n請按任意鍵繼續(xù)" << endl;
_getch();
}
void show_running_job()
{
system("cls");
int i = 0;
cout << "當(dāng)前正在運(yùn)行的作業(yè)信息如下:\n" << endl;
while (i < running_job_num)
{
cout << "序號: " << i
<< "\t作業(yè)名: " << running_job[i].id
<< "\t大小: " << running_job[i].size << endl;
i++;
}
cout << "請輸入要釋放的作業(yè)序號 : ";
cin >> i;
if (i >= running_job_num || i < 0)
{
cout << "\n\n輸入序號有誤,請按任意鍵重新輸入" << endl;
show_running_job();
}
else
{
release_memory(i);
show_message();
}
}
void release_job()
{
show_running_job();
}
void menu()
{
char choice;
while (1)
{
system("cls");
cout << " 1: 輸入作業(yè)" << endl;
cout << " 2: 釋放作業(yè)" << endl;
cout << " 3: 離開" << endl;
cout << "\n\n\n請輸入選擇: " << endl;
choice = _getch();
if (choice == '1')
input_job();
else if (choice == '2')
release_job();
else if (choice == '3')
exit(0);
else
{
cout << "輸入有誤,請按任意鍵繼續(xù)" << endl;
_getch();
}
}
}
int main()
{
Init();
menu();
return 0;
}輸入內(nèi)存大小640kb,起始地址0
?作業(yè)1申請130KB后
?作業(yè)2申請60KB后
?
作業(yè)3申請100KB后
作業(yè)2釋放60KB后
?
作業(yè)4申請200KB后
作業(yè)3釋放100KB后
作業(yè)1釋放130KB后
作業(yè)5申請140KB后
作業(yè)6申請60KB后
作業(yè)7申請50KB后
作業(yè)8申請60KB后
?最佳適應(yīng)算法
最佳適應(yīng)算法在分區(qū)鏈中尋找可以分配且分配后剩余空間最小的分區(qū)，這樣可以使分區(qū)碎片最小化，留下一些大分區(qū)，但是每次都要遍歷分區(qū)鏈表，效率較低。(或者事先進(jìn)行排序，維護(hù)空閑分區(qū)大小升序，但開銷還是會(huì)比較大，而且合并時(shí)也需要查一次分區(qū)鏈)
最佳適應(yīng)算法與首次適應(yīng)算法只在分配時(shí)策略不同。最佳適應(yīng)算法分配時(shí)從分區(qū)鏈頭開始找，直到有一個(gè)分區(qū)大小 不小于作業(yè)大小。如果找不到說明沒有分區(qū)塊可以分配。如果找到，將這個(gè)分區(qū)塊標(biāo)記下，然后往后尋找大小滿足作業(yè)要求，又盡可能小的分區(qū)，找到就將標(biāo)記替換。
得到最佳塊后，分情況討論；
若分區(qū)塊大小等于作業(yè)大小且內(nèi)存只剩這個(gè)塊，分配后header置null，分區(qū)鏈內(nèi)存釋放
若分區(qū)塊大小等于作業(yè)大小且內(nèi)存還有多塊，將此分配分區(qū) 后一個(gè)分區(qū)的內(nèi)容賦值給該分區(qū)，修改指針后釋放后一分區(qū)
若分區(qū)塊大小大于作業(yè)大小，只修改分區(qū)信息
代碼如下
#include<iostream>
#include <conio.h>
using namespace std;
struct block
{
int address; //內(nèi)存塊起始地址
int size; //內(nèi)存塊大小
}BLOCK; //內(nèi)存塊
struct job
{
char id[10]; //作業(yè)id
int address; //作業(yè)分配的內(nèi)存起始地址
int size; //作業(yè)需要的大小
int alloc_size; //作業(yè)分配的大小
}; //作業(yè)
struct free_blocks_linklist
{
block free_block; //空閑內(nèi)存塊
free_blocks_linklist* next; //指向下一內(nèi)存塊的指針
}Free_Blocks_linklist; //空閑分區(qū)鏈
job running_job[10]; //運(yùn)行中的作業(yè)數(shù)組
int running_job_num = 0;
job waiting_job[10]; //分配失敗后等待的作業(yè)數(shù)組
int waiting_jon_num = 0;
job finish_job[10]; //完成的作業(yè)數(shù)組
int finish_job_num = 0;
free_blocks_linklist * header = nullptr; //內(nèi)存分區(qū)鏈頭指針
void Init() //初始化內(nèi)存
{
header = new free_blocks_linklist;
cout << "請輸入內(nèi)存大小(KB) : ";
cin >> header->free_block.size;
cout << "請輸入內(nèi)存起始地址 : ";
cin >> header->free_block.address;
header->next = header;
/*cin >> hex >> a;
cout << a << endl;
cout << hex <<a;*/
}
bool alloc_memory(job &j) //給作業(yè)分配內(nèi)存
{
free_blocks_linklist* temp = header;
free_blocks_linklist* temp1 = nullptr; //最佳塊指針
if (temp == nullptr)
{
cout << "\n\n內(nèi)存不足分配失敗" << endl;
return false;
}
do
{
if (temp->free_block.size >= j.size) //可以分配
{
temp1 = temp;
temp = temp->next;
break;
}
temp = temp->next;
}while (temp != header); //是否有能分配的塊
if(temp1 == nullptr)
{
cout << "\n\n沒有合適內(nèi)存塊分配" << endl;
return false;
}
do
{
if (temp->free_block.size >= j.size && temp->free_block.size < temp1->free_block.size)
temp1 = temp; //找到更合適的分區(qū)
temp = temp->next;
} while (temp!= header);
if (temp1->free_block.size == j.size) //分區(qū)內(nèi)存正好
{
if (temp1->next == temp1) //只剩一個(gè)分區(qū)
{
j.address = temp1->free_block.address;
j.alloc_size = j.size;
delete temp1;
header = nullptr;
cout << "\n\n分配內(nèi)存成功" << endl;
return true;
}
else //有多個(gè)分區(qū)
{
j.address = temp1->free_block.address;
j.alloc_size = j.size;
temp = temp1->next;
temp1->free_block = temp->free_block;
temp1->next = temp->next;
if (temp == header)
header = header->next;
delete temp;
cout << "\n\n分配內(nèi)存成功" << endl;
return true;
}
}
else if (temp1->free_block.size > j.size) //內(nèi)存塊分配后還有空間
{
j.address = temp1->free_block.address;
j.alloc_size = j.size;
temp1->free_block.size -= j.size;
temp1->free_block.address += j.size;
cout << "\n\n分配內(nèi)存成功" << endl;
cout << "\n\n請按任意鍵繼續(xù)" << endl;
_getch();
return true;
}
}
void run_job(job j) //調(diào)度運(yùn)行作業(yè)
{
if (true == alloc_memory(j)) //分配成功
running_job[running_job_num++] = j;
else
waiting_job[waiting_jon_num++] = j;
}
void show_message() //顯示系統(tǒng)信息
{
system("cls");
free_blocks_linklist* temp = header;
int i = 1;
cout << "\n\n當(dāng)前運(yùn)行的作業(yè)數(shù)量為：" << running_job_num <<endl;
cout << "正在等待分配內(nèi)存的作業(yè)數(shù)量(分配內(nèi)存失敗)為：" << waiting_jon_num << endl;
cout << "已完成作業(yè)數(shù)量為： " << finish_job_num << endl;
cout << "\n當(dāng)前內(nèi)存空間信息如下 : " << endl;
if (header != nullptr)
{
do
{
cout << "\n內(nèi)存塊" << i << "起始地址為: " << temp->free_block.address << endl;
cout << "內(nèi)存塊" << i << "大小為: " << temp->free_block.size << endl;
temp = temp->next;
i++;
} while (temp != header);
}
else cout << "\n內(nèi)存空間已經(jīng)用完" << endl;
cout << "\n\n請按任意鍵繼續(xù)" << endl;
_getch();
}
void input_job() //輸入作業(yè)
{
job temp;
cout << "請輸入作業(yè)名: " << endl;
cin >> temp.id;
cout << "請輸入作業(yè)大小: " << endl;
cin >> temp.size;
run_job(temp);
show_message();
return;
}
void release_memory(int count) //釋放作業(yè)內(nèi)存， count為要釋放作業(yè)的序號
{
if (header == nullptr)
{
header = new free_blocks_linklist;
header->free_block.address = running_job[count].address;
header->free_block.size = running_job[count].alloc_size;
header->next = header;
}
else
{
free_blocks_linklist* temp = header;
while (temp->next != header)
{
temp = temp->next;
} //找到鏈尾
if (running_job[count].address == temp->free_block.address + temp->free_block.size)
{ //作業(yè)分配的內(nèi)存地址最大且可合并
temp->free_block.size += running_job[count].alloc_size;
}
else if (running_job[count].address > temp->free_block.address + temp->free_block.size)
{ //作業(yè)分配的內(nèi)存地址最大且不可合并
free_blocks_linklist* temp1 = new free_blocks_linklist;
temp1->free_block.address = running_job[count].address;
temp1->free_block.size = running_job[count].alloc_size;
temp1->next = header;
temp->next = temp1;
}
else if (header->free_block.address == running_job[count].address + //作業(yè)分配的地址最小且可合并
running_job[count].alloc_size)
{
header->free_block.address = running_job[count].address;
header->free_block.size += running_job[count].alloc_size;
}
else if (header->free_block.address > running_job[count].address + //作業(yè)分配的地址最小且不可合并
running_job[count].alloc_size)
{
temp = new free_blocks_linklist;
temp->free_block.address = running_job[count].address;
temp->free_block.size = running_job[count].alloc_size;
temp->next = header;
free_blocks_linklist* temp1 = header;
while (temp1->next != header)
temp1 = temp1->next;
temp1->next = temp;
header = temp;
}
else //作業(yè)回收的地址在分區(qū)鏈中間
{
temp = header;
while (temp->next->free_block.address + temp->next->free_block.size < running_job[count].address)
temp = temp->next; //找到要插入的前一分區(qū)位置temp
if (temp->free_block.address + temp->free_block.size == running_job[count].address)
{ //前分區(qū)可以合并
if (running_job[count].address + running_job[count].alloc_size == temp->next->free_block.address)
{ //回收時(shí)可以和前后分區(qū)合并
temp->free_block.size += running_job[count].alloc_size + temp->next->free_block.size;
free_blocks_linklist* temp1 = temp->next;
temp->next = temp1->next;
delete temp1;
}
else //只能與前分區(qū)合并
{
temp->free_block.size += running_job[count].alloc_size;
}
}
else //前分區(qū)不可合并
{
if (temp->next->free_block.address == running_job[count].address + running_job[count].alloc_size)
{//后分區(qū)可以合并
temp->next->free_block.address -= running_job[count].alloc_size;
temp->next->free_block.size += running_job[count].alloc_size;
}
else
{//后分區(qū)不可以合并
free_blocks_linklist* temp1 = new free_blocks_linklist;
temp1->free_block.address = running_job[count].address;
temp1->free_block.size = running_job[count].alloc_size;
temp1->next = temp->next;
temp->next = temp1;
}
}
}
}
finish_job[finish_job_num++] = running_job[count];
running_job[count] = running_job[--running_job_num];
cout << "\n釋放內(nèi)存成功" << endl;
cout << "\n\n請按任意鍵繼續(xù)" << endl;
_getch();
}
void show_running_job() //顯示正在運(yùn)行的作業(yè)
{
system("cls");
int i = 0;
cout << "當(dāng)前正在運(yùn)行的作業(yè)信息如下:\n" << endl;
while (i < running_job_num)
{
cout << "序號: " << i
<< "\t作業(yè)名: " << running_job[i].id
<< "\t大小: " << running_job[i].size << endl;
i++;
}
cout << "請輸入要釋放的作業(yè)序號 : ";
cin >> i;
if (i >= running_job_num || i < 0)
{
cout << "\n\n輸入序號有誤,請按任意鍵重新輸入" << endl;
show_running_job();
}
else
{
release_memory(i);
show_message();
}
}
void release_job() //釋放作業(yè)
{
show_running_job();
}
void menu() //選項(xiàng)菜單
{
char choice;
while (1)
{
system("cls");
cout << " 1: 輸入作業(yè)" << endl;
cout << " 2: 釋放作業(yè)" << endl;
cout << " 3: 離開" << endl;
cout << "\n\n\n請輸入選擇: " << endl;
choice = _getch();
if (choice == '1')
input_job();
else if (choice == '2')
release_job();
else if (choice == '3')
exit(0);
else
{
cout << "輸入有誤,請按任意鍵繼續(xù)" << endl;
_getch();
}
}
}
int main()
{
Init();
menu();
return 0;
}輸入內(nèi)存大小640KB,起始地址0
作業(yè)1申請130KB后
?
作業(yè)2申請60KB后
作業(yè)3申請100KB后
?作業(yè)2釋放60KB后
?作業(yè)4申請200KB后
?作業(yè)3釋放100KB后
?作業(yè)1釋放130KB后
?作業(yè)5申請140KB后
?作業(yè)6申請60KB后
?作業(yè)7申請50KB后
?作業(yè)8申請60KB后
?文章來源地址http://www.zghlxwxcb.cn/news/detail-759770.html文章來源：http://www.zghlxwxcb.cn/news/detail-759770.html
?
到了這里，關(guān)于操作系統(tǒng)簡單動(dòng)態(tài)分區(qū)分配算法(c++)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
