動態分區分配是根據進程的實際需要，動態地址為之分配內存空間，在分配時按照一定的分配算法，從空閑分區表或空閑分區鏈中選出一分區分配給該作業

• 1.首次適應算法(FF):將所有空閑分區按照地址遞增的次序鏈接，在申請內存分配時，從鏈首開始查找，將滿足需求的第一個空閑分區分配給作業。

• 2.循環首次適應算法（NF）：將所有空閑分區按照地址遞增的次序鏈接，在申請內存分配時，總是從上次找到的空閑分區的下一個空閑分區開始查找，將滿足需求的第一個空閑分區分配給作業

• 3.最壞適應算法(WF)：將所有的空閑分區按照從大到小的順序形成空閑分區鏈，在申請內存分配時，總是把滿足需求的、最大的空閑分區分配給作業。

• 4.最佳適應算法(BF): 將所有空閑分區按照從小到大的順序形成空閑分區鏈，在申請內存分配時，總是把滿足需求的、最小的空閑分區分配給作業。

源碼

#include <iostream> #include <fstream> #include <iomanip> using namespace std;#define MAXNUMBER 100 static int PartitionNum; //內存中空閑分區的個數 static int ProcessNum; //需要分配的進程個數 static int FreePartition[MAXNUMBER]; //空閑分區對應的內存 static int ProcessNeed[MAXNUMBER]; //需要分配的進程大小static int LeftFreePartition[MAXNUMBER]; static int LeftProcessNeed[MAXNUMBER];static char ProcessName[MAXNUMBER]; static char NameProcessToPartition[MAXNUMBER][MAXNUMBER];typedef struct {int partitionSize;int id; }sortNeed;void readDataFunction(); void input(); void display(); void FirstFit(); void NextFit(); void BestFit(); void WorstFit(); void selectAlgorithm(int chooceAlgorithm); void display();void readDataFunction() {cout<<"請輸入空閑分區數"<<endl;cin >> PartitionNum;cout << "請輸入空閑分區大小" << endl;for (int i = 0; i<PartitionNum; i++){cin >> FreePartition[i];}cout<<"請輸入進程個數"<<endl;cin >> ProcessNum;cout<<"請輸入進程名稱"<<endl;for (int i = 0; i<ProcessNum; i++){cin >> ProcessName[i];}cout<<"請輸入進程需要分配大小"<<endl;for (int i = 0; i<ProcessNum; i++){cin >> ProcessNeed[i];} }void input() {int chooseAlgorithm = 5;do{//readDataFunction();cout << "請選擇實現的算法：" << endl;cout << "***** 1 - 首次適應算法 *****" << endl;cout << "***** 2 - 循環首次適應算法 *****" << endl;cout << "***** 3 - 最佳適應算法 *****" << endl;cout << "***** 4 - 最壞適應算法 *****" << endl;cout << "***** 0 - 結束 *****" << endl;cout << "chooseAlgorithm = ";cin >> chooseAlgorithm;selectAlgorithm(chooseAlgorithm);//display();} while (chooseAlgorithm); }void initial() {readDataFunction(); //讀取原始數據for (int i = 0; i<PartitionNum; i++){LeftFreePartition[i] = FreePartition[i];for (int j = 0; j<ProcessNum; j++){NameProcessToPartition[i][j] = NULL;}}for (int i = 0; i<ProcessNum; i++){LeftProcessNeed[i] = ProcessNeed[i];} }void FirstFit() {cout << "***********首次適應算法***********" << endl;initial();int i, j;for (i = 0; i<ProcessNum; i++) //逐個遍歷每個進程{for (j = 0; j<PartitionNum; j++){if (LeftProcessNeed[i] <= LeftFreePartition[j] && LeftFreePartition != 0) //當系統內存分區足夠大的時候，即分配給進程資源{LeftFreePartition[j] -= LeftProcessNeed[i]; //扣除分配給進程的資源LeftProcessNeed[i] = 0; //當且僅當系統內存分區足夠時才執行，即當前進程大小置0NameProcessToPartition[i][j] = ProcessName[i]; //存儲各個進程所在的分區位置break; //!!!很重要，一個進程分區完后，應該立即break，進行下一個進程的判斷}}}display();}void NextFit() {cout << "***********循環首次適應算法***********" << endl;initial();int i, nextPoint = 0;bool isWhile;for (i = 0; i<ProcessNum; i++){isWhile = true;while (isWhile){if (LeftFreePartition[nextPoint] >= LeftProcessNeed[i]){LeftFreePartition[nextPoint] -= LeftProcessNeed[i];LeftProcessNeed[i] = 0;NameProcessToPartition[i][nextPoint] = ProcessName[i];nextPoint++;if (nextPoint > PartitionNum - 1){nextPoint = 0; //當j遍歷到分區末尾的時候，返回首位置}isWhile = false;}elsenextPoint++;}}display(); }void BestFit() {//思想：利用冒泡排序對分區大小進行排序，但不改變原分區的位置//創建一個結構體，包括分區大小和所對應的id，排序過程中，每改變順序一次，id隨著改變//關鍵：每次分配完一個進程的內存大小后，都要重新排序cout << "***********最佳適應算法***********" << endl;initial();int i, j, temp, tempID;sortNeed best[MAXNUMBER];for (i = 0; i<PartitionNum; i++){//初始化結構體best[i].partitionSize = FreePartition[i];best[i].id = i;}for (i = 0; i<ProcessNum; i++){for (int s = PartitionNum - 1; s > 0; s--) //冒泡排序(每次分配完一個進程后，都需要重新排序){for (int t = 0; t < s; t++){if (best[s].partitionSize < best[t].partitionSize){temp = best[s].partitionSize;best[s].partitionSize = best[t].partitionSize;best[t].partitionSize = temp;tempID = best[s].id;best[s].id = best[t].id;best[t].id = tempID;}}}for (j = 0; j<PartitionNum; j++){if (LeftProcessNeed[i] <= best[j].partitionSize){best[j].partitionSize -= LeftProcessNeed[i];LeftProcessNeed[i] = 0;NameProcessToPartition[i][best[j].id] = ProcessName[i];break;}}LeftFreePartition[best[j].id] = best[j].partitionSize;}display(); }void WorstFit() {cout << "***********最壞適應算法***********" << endl;initial();int i, j, s, t, tempSize, tempID;sortNeed Worst[MAXNUMBER];for (i = 0; i<PartitionNum; i++){Worst[i].partitionSize = FreePartition[i];Worst[i].id = i;}for (i = 0; i<ProcessNum; i++){for (s = PartitionNum - 1; s>0; s--){for (t = 0; t<s; t++){if (Worst[s].partitionSize > Worst[t].partitionSize){tempSize = Worst[s].partitionSize;Worst[s].partitionSize = Worst[t].partitionSize;Worst[t].partitionSize = tempSize;tempID = Worst[s].id;Worst[s].id = Worst[t].id;Worst[t].id = tempID;}}}for (j = 0; j<PartitionNum; j++){if (LeftProcessNeed[i] <= Worst[j].partitionSize){Worst[j].partitionSize -= LeftProcessNeed[i];LeftProcessNeed[j] = 0;NameProcessToPartition[i][Worst[j].id] = ProcessName[i];break;}}LeftFreePartition[Worst[j].id] = Worst[j].partitionSize;}display();}void selectAlgorithm(int chooseAlgorithm) {switch (chooseAlgorithm){case 0:break;case 1:FirstFit(); break;case 2:NextFit(); break;case 3:BestFit(); break;case 4:WorstFit(); break;default:cout << "請輸入正確的序號：" << endl;} }void display() {int i;cout << "需要分配內存的進程名：" << setw(10);for (i = 0; i<ProcessNum; i++){cout << ProcessName[i] << setw(6);}cout << endl;cout << "需要分配內存的進程分區大小：" << setw(4);for (i = 0; i<ProcessNum; i++){cout << ProcessNeed[i] << setw(6);}cout << endl;cout << "分配結果：" << endl;cout << "分區序號:";for (i = 0; i<PartitionNum; i++){cout << "分區" << i + 1 << " ";}cout << endl << "分區大小:";for (i = 0; i<PartitionNum; i++){cout << FreePartition[i] << " ";}cout << endl << "剩余大小: ";for (i = 0; i<PartitionNum; i++){cout << LeftFreePartition[i] << " ";}cout << endl << "分配進程情況:" << endl;for (i = 0; i<PartitionNum; i++){for (int j = 0; j<ProcessNum; j++){if (NameProcessToPartition[j][i] != NULL){cout << NameProcessToPartition[j][i] << ": (分區" << i + 1 << ")" << endl;}}//cout<<" ";}cout << endl << "********結束**********" << endl; }int main() {input();return 0; }

總結

以上是生活随笔為你收集整理的动态内存分配算法：首次适应算法，循环首次适应算法，最坏适应算法，最佳适应算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。