メモリ管理における最適なアルゴリズムのためのC++プログラム

ブロックサイズとプロセスサイズを含む2つの配列があるとします。タスクは、メモリ管理のベストフィットアルゴリズムに従って結果を印刷することです。

最適なアルゴリズムとは何ですか？

Best Fitは、メモリ管理アルゴリズムです。要求プロセスの要件を満たす最小の空きパーティションの割り当てを処理します。このアルゴリズムでは、メモリブロック全体を探し、プロセスに最も小さく最も適切なブロックをチェックしてから、適切なプロセスを実行するために使用できるすぐ近くのブロックを探します。

したがって、ブロックサイズとプロセスサイズを取得し、プロセスの出力と、プロセスに割り当てられるブロックを返します。

例

Input: bsize[] = {100, 500, 200, 300, 400}
   psize[] = {112, 518, 110, 526}
Output:
Process No. Process Size Block no.
1            112          3
2            518          Not Allocated
3            110          4
4            526         Not Allocated

アプローチは上記の問題を解決するために使用されます-

• プロセス広告のブロックサイズを入力します。
• 最初にすべてのメモリブロックを空きとして設定します。
• 各プロセスを実行して、ブロックに割り当てることができる最小ブロックサイズを見つけます。これは、プロセスサイズよりも大きいブロック全体の最小値を意味します。
• 見つかった場合は現在のプロセスに割り当て、そうでない場合はそのプロセスを終了して次のプロセスを確認します。

アルゴリズム

Start
Step 1-> In function void bestfit(int bsize[], int m, int psize[], int n)
   Declare int alloc[n]
   Call function memset(alloc, -1, sizeof(alloc))
   Loop For i=0 and i<n and i++
      Declare and Initialize bestIdx = -1
      Loop For j=0 and j<m and j++
         If bsize[j] >= psize[i] then,
            If bestIdx == -1 then,
               Set bestIdx = j
            Else If bsize[bestIdx] > bsize[j] then,
               Set bestIdx = j
            If bestIdx != -1 then,
               Set alloc[i] = bestIdx
               Set bsize[bestIdx] -= psize[i]
      Loop For i = 0 and i < n and i++
         Print i+1, psize[i]
         If alloc[i] != -1
            Print alloc[i] + 1
         Else
            Print "Not Allocated"
            Print newline
Step 2->In function int main()
   Declare and initialize bsize[] = {100, 500, 200, 300, 400}
   Declare and initialize psize[] = {112, 518, 110, 526}
   Set m = sizeof(bsize)/sizeof(bsize[0])
   Set n = sizeof(psize)/sizeof(psize[0])
   Call function bestfit(bsize, m, psize, n)
Stop

例

#include <iostream>
#include <memory>
using namespace std;
// To allocate the memory to blocks as per Best fit
// algorithm
void bestfit(int bsize[], int m, int psize[], int n) {
   // To store block id of the block allocated to a
   // process
   int alloc[n];
   // Initially no block is assigned to any process
    memset(alloc, -1, sizeof(alloc));
   // pick each process and find suitable blocks
   // according to its size ad assign to it
   for (int i=0; i<n; i++) {
      // Find the best fit block for current process
      int bestIdx = -1;
      for (int j=0; j<m; j++) {
         if (bsize[j] >= psize[i]) {
            if (bestIdx == -1)
               bestIdx = j;
            else if (bsize[bestIdx] > bsize[j])
               bestIdx = j;
         }
      }
      // If we could find a block for current process
      if (bestIdx != -1) {
         // allocate block j to p[i] process
         alloc[i] = bestIdx;
         // Reduce available memory in this block.
         bsize[bestIdx] -= psize[i];
      }
   }
   cout << "\nProcess No.\tProcess Size\tBlock no.\n";
   for (int i = 0; i < n; i++) {
      cout << " " << i+1 << "\t\t\t\t" << psize[i] << "\t\t\t\t";
      if (alloc[i] != -1)
         cout << alloc[i] + 1;
      else
         cout << "Not Allocated";
         cout << endl;
   }
}
// Driver code
int main() {
   int bsize[] = {100, 500, 200, 300, 400};
   int psize[] = {112, 518, 110, 526};
   int m = sizeof(bsize)/sizeof(bsize[0]);
   int n = sizeof(psize)/sizeof(psize[0]);
   bestfit(bsize, m, psize, n);
   return 0 ;
}

出力

Process No. Process Size    Block no.
 1              112             3
 2              518          Not Allocated
 3              110             4
 4              526          Not Allocated