メモリ管理におけるFirstFitアルゴリズムのC++プログラム

---

n個のプロセスとm個のメモリブロックのサイズが与えられた場合、タスクは、最初の適合メモリ管理アルゴリズムを使用して、対応するプロセスに最適なメモリブロックを見つけることです。

First Fitメモリ管理アルゴリズムとは何ですか？

オペレーティングシステムがメモリブロックを-

のようなプロセスに割り当てるために使用する、利用可能な複数のメモリ分割アルゴリズムがあります。

• ファーストフィットアルゴリズム
• 次の適合アルゴリズム
• 最適なアルゴリズム
• ワーストフィットアルゴリズム
• クイックフィットアルゴリズム

First Fit Algorithmは、すべてのプロセスの中でメモリブロックをプロセスに割り当てる最も簡単な手法です。このアルゴリズムでは、ポインタはメモリ内のすべての空きブロックを追跡し、次のプロセスにメモリブロックを割り当てる要求を受け入れます。その後、ポインタはプロセスの最大の最初の空きブロックの検索を開始し、そのメモリブロックを次のプロセスに割り当てます。ここでは、2つのパーティションが作成されます。1つは穴用で、もう1つはプロセスを格納します。

利点 First Fit Algorithmを使用すると、最大のFirst Fitアルゴリズムが新しいプロセスに割り当てられるため、今後のプロセスへのメモリ割り当てが最速になります。

短所 First Fit Algorithmを使用することは、他のプロセスのメモリ不足につながるメモリの浪費です。

例

Input-: block_size[] = {300, 50, 200, 350, 70}
process_size[] = {200, 47, 212, 426, 10}
Output-:
Process No. Process Size Block no.
1             200       1
2             47       1
3             212       4
4             426       Not Allocated
5             10       1

次のプログラムで使用されるアプローチは次のとおりです −

• ブロックとプロセスを配列に入力します
• すべてのメモリブロックを解放するように設定します
• （プロセスのサイズ）<=（メモリブロックのサイズ）かどうかを確認してから、プロセスをメモリブロックに割り当てます
• それ以外の場合は、（プロセスのサイズ）<=（メモリブロックのサイズ）が成り立たなくなるまで、他のブロックをトラバースし続けます。

アルゴリズム

Start
Step 1->  declare function to calculate the best fit memory block
   void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process)
   Declare int allocation[total_process]
   Call function memset(allocation, -1, sizeof(allocation))
   Loop For i = 0 and i < total_process and i++
      Loop for j = 0 and j < total_blocks and j++
         IF block_size[j] >= process_size[i]
            Set allocation[i] = j
            Set block_size[j] -= process_size[i]
         End
      End
   End
   Loop For i = 0 and i < total_process and i++
      IF allocation[i] != -1
         Set allocation[i] + 1
      End
      Else
         Print Not Allocated
      End
   End
Step 2-> In main()
   Declare an array for blocks as int block_size[] = {300, 50, 200, 350, 70}
   Declare an array for processes int process_size[] = {200, 47, 212, 426, 10}
   Calculate total blocks int total_blocks = sizeof(block_size) / sizeof(block_size[0]
   Calculate total processes int total_process = sizeof(process_size) / sizeof(process_size[0])
   Call First_Fit(block_size, total_blocks, process_size, total_process)
Stop

例

#include<bits/stdc++.h>
using namespace std;
// Function to allocate memory to  
// blocks as per First fit algorithm
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process) {
   int allocation[total_process];
   memset(allocation, -1, sizeof(allocation));
   //this for loop wll pick eact process and allocate a first fit block to it
   for (int i = 0; i < total_process; i++) {
      for (int j = 0; j < total_blocks; j++) {
         if (block_size[j] >= process_size[i]) {
            allocation[i] = j;
            block_size[j] -= process_size[i];
            break;
         }
      }
   }
   cout << "\nProcess No.\tProcess Size\tBlock no.\n";
   for (int i = 0; i < total_process; i++) {
      cout << " " << i+1 << "\t\t" << process_size[i] << "\t\t";
      if (allocation[i] != -1)
         cout << allocation[i] + 1;
      else
         cout << "Not Allocated";
         cout << endl;
   }
}
int main() {
   //create array to store block sizes
   int block_size[] = {300, 50, 200, 350, 70};  
    //create array to store process sizes
   int process_size[] = {200, 47, 212, 426, 10};
    //variable total_blocks that contain total number of blocks
   int total_blocks = sizeof(block_size) / sizeof(block_size[0]);
    //variable total_process that contain total number of blocks
   int total_process = sizeof(process_size) / sizeof(process_size[0]);
    //calling the function First_fit
   First_Fit(block_size, total_blocks, process_size, total_process);
   return 0 ;
}

出力

Process No.    Process Size   Block no.  
1                  200            1  
2                  47             1          
3                  212            4  
4                  426         Not Allocated  
5                  10            1