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

โจทย์

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

First Fit Memory Management Algorithm คืออะไร?

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

• First Fit Algorithm
• Next Fit Algorithm
• Best Fit Algorithm
• Worst Fit Algorithm
• Quick Fit Algorithm

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

ข้อดี ของการใช้ First Fit Algorithm คือการจัดสรรหน่วยความจำให้โปรเซสที่มาถึงเร็วที่สุด เนื่องจากจัดสรร first fit algorithm ที่ใหญ่ที่สุดให้โปรเซสใหม่

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

แนวทางที่ใช้ในโปรแกรมต่อไปนี้

• รับบล็อกและโปรเซสในอาเรย์
• ตั้งค่าบล็อกหน่วยความจำทั้งหมดเป็นว่าง
• ตรวจสอบถ้า (ขนาดโปรเซส) <= (ขนาดบล็อกหน่วยความจำ) แล้วจัดสรรโปรเซสให้บล็อกหน่วยความจำ
• มิฉะนั้น วนลูปตรวจสอบบล็อกอื่นๆ จนกว่า (ขนาดโปรเซส) <= (ขนาดบล็อกหน่วยความจำ) จะเป็นจริง

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ประกาศฟังก์ชันคำนวณ best fit memory block
  void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process)
  ประกาศ int allocation[total_process]
  เรียกฟังก์ชัน memset(allocation, -1, sizeof(allocation))
  วนลูป For i = 0 ถึง total_process และ i++
    วนลูป for j = 0 ถึง total_blocks และ j++
      ถ้า block_size[j] >= process_size[i]
        ตั้งค่า allocation[i] = j
        ตั้งค่า block_size[j] -= process_size[i]
      จบถ้า
    จบวน
  จบวน
  วนลูป For i = 0 ถึง total_process และ i++
    ถ้า allocation[i] != -1
      ตั้งค่า allocation[i] + 1
    จบถ้า
    มิฉะนั้น
      พิมพ์ Not Allocated
    จบมิฉะนั้น
  จบวน
ขั้นตอน 2 → ใน main()
  ประกาศอาเรย์สำหรับบล็อก int block_size[] = {300, 50, 200, 350, 70}
  ประกาศอาเรย์สำหรับโปรเซส int process_size[] = {200, 47, 212, 426, 10}
  คำนวณ total blocks int total_blocks = sizeof(block_size) / sizeof(block_size[0])
  คำนวณ total processes int total_process = sizeof(process_size) / sizeof(process_size[0])
  เรียก First_Fit(block_size, total_blocks, process_size, total_process)
หยุด

ตัวอย่างโค้ด C++

#include<bits/stdc++.h>
using namespace std;
// ฟังก์ชันจัดสรรหน่วยความจำให้บล็อกตาม 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));
  // ลูปนี้จะเลือกแต่ละโปรเซสและจัดสรร first fit block ให้
  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() {
  // สร้างอาเรย์เก็บขนาดบล็อก
  int block_size[] = {300, 50, 200, 350, 70};
  // สร้างอาเรย์เก็บขนาดโปรเซส
  int process_size[] = {200, 47, 212, 426, 10};
  // ตัวแปร total_blocks เก็บจำนวนบล็อกทั้งหมด
  int total_blocks = sizeof(block_size) / sizeof(block_size[0]);
  // ตัวแปร total_process เก็บจำนวนโปรเซสทั้งหมด
  int total_process = sizeof(process_size) / sizeof(process_size[0]);
  // เรียกฟังก์ชัน 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