โปรแกรม C++ สำหรับอัลกอริธึม First Fit ในการจัดการหน่วยความจำ

ด้วยจำนวนกระบวนการ n รายการและขนาดของบล็อกหน่วยความจำ m และภารกิจคือการค้นหาบล็อกหน่วยความจำที่เหมาะสมที่สุดสำหรับกระบวนการที่เกี่ยวข้องโดยใช้อัลกอริธึมการจัดการหน่วยความจำที่พอดีอันดับแรก

อัลกอริธึมการจัดการหน่วยความจำ First Fit คืออะไร

มีอัลกอริธึมการแบ่งหน่วยความจำหลายแบบที่ระบบปฏิบัติการใช้เพื่อจัดสรรบล็อกหน่วยความจำให้กับกระบวนการต่างๆ เช่น -

• First Fit Algorithm
• Next Fit Algorithm
• อัลกอริธึมที่พอดีที่สุด
• อัลกอริทึมที่แย่ที่สุด
• Quick Fit Algorithm

First Fit Algorithm เป็นเทคนิคที่ง่ายที่สุดในการจัดสรรบล็อกหน่วยความจำให้กับกระบวนการทั้งหมด ในอัลกอริธึมนี้ ตัวชี้จะติดตามบล็อคว่างทั้งหมดในหน่วยความจำและยอมรับคำขอในการจัดสรรบล็อกหน่วยความจำให้กับกระบวนการที่จะมาถึง หลังจากที่ตัวชี้นั้นเริ่มค้นหาบล็อกว่างแรกที่ใหญ่ที่สุดสำหรับกระบวนการและจัดสรรบล็อกหน่วยความจำนั้นให้กับกระบวนการที่จะมาถึง ในส่วนนี้ จะมีการสร้างพาร์ติชั่นสองพาร์ติชั่น พาร์ติชั่นหนึ่งสำหรับรู และพาร์ติชั่นหนึ่งสำหรับจัดเก็บกระบวนการ

ข้อได้เปรียบ ของการใช้ 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