Cho n tiến trình và m kích thước khối bộ nhớ, nhiệm vụ là tìm khối bộ nhớ phù hợp nhất cho tiến trình tương ứng sử dụng thuật toán First Fit quản lý bộ nhớ.
Thuật toán First Fit quản lý bộ nhớ là gì?
Có nhiều thuật toán phân vùng bộ nhớ được hệ điều hành dùng để cấp phát khối bộ nhớ cho tiến trình như –
- Thuật toán First Fit
- Thuật toán Next Fit
- Thuật toán Best Fit
- Thuật toán Worst Fit
- Thuật toán Quick Fit
Thuật toán First Fit là kỹ thuật đơn giản nhất cấp phát khối bộ nhớ cho tiến trình trong số tất cả. Trong thuật toán này, con trỏ theo dõi tất cả các khối trống trong bộ nhớ và chấp nhận yêu cầu cấp phát khối bộ nhớ cho tiến trình đến. Sau đó con trỏ bắt đầu tìm khối trống lớn nhất đầu tiên cho tiến trình và cấp phát khối bộ nhớ đó cho tiến trình đến. Trong đó, hai phân vùng được tạo: một cho lỗ (hole) và một lưu trữ tiến trình.
Ưu điểm của First Fit là cấp phát bộ nhớ nhanh nhất cho tiến trình đến vì nó cấp phát khối first fit lớn nhất cho tiến trình mới.
Nhược điểm của First Fit là lãng phí bộ nhớ dẫn đến thiếu hụt bộ nhớ cho tiến trình khác.
Ví dụ
Đầu vào: block_size[] = {300, 50, 200, 350, 70}
process_size[] = {200, 47, 212, 426, 10}
Đầu ra:
Process No. Process Size Block no.
1 200 1
2 47 1
3 212 4
4 426 Not Allocated
5 10 1
Cách tiếp cận dùng trong chương trình sau –
- Nhập các khối và tiến trình vào mảng
- Đặt tất cả khối bộ nhớ là trống
- Kiểm tra nếu (kích thước tiến trình) <= (kích thước khối bộ nhớ) thì cấp phát tiến trình vào khối bộ nhớ
- Ngược lại tiếp tục duyệt các khối khác cho đến khi (kích thước tiến trình) <= (kích thước khối bộ nhớ) đúng.
Thuật toán
Bắt đầu
Bước 1 -> Khai báo hàm tính khối bộ nhớ phù hợp nhất
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process)
Khai báo int allocation[total_process]
Gọi hàm memset(allocation, -1, sizeof(allocation))
Vòng lặp Với i = 0 đến i < total_process và i++
Vòng lặp Với j = 0 đến j < total_blocks và j++
NẾU block_size[j] >= process_size[i]
Gán allocation[i] = j
Gán block_size[j] -= process_size[i]
Kết thúc
Kết thúc
Kết thúc
Vòng lặp Với i = 0 đến i < total_process và i++
NẾU allocation[i] != -1
Gán allocation[i] + 1
Kết thúc
NGƯỢC LẠI
In Not Allocated
Kết thúc
Kết thúc
Bước 2 -> Trong main()
Khai báo mảng khối: int block_size[] = {300, 50, 200, 350, 70}
Khai báo mảng tiến trình: int process_size[] = {200, 47, 212, 426, 10}
Tính total_blocks = sizeof(block_size) / sizeof(block_size[0])
Tính total_process = sizeof(process_size) / sizeof(process_size[0])
Gọi First_Fit(block_size, total_blocks, process_size, total_process)
Kết thúc
Ví dụ mã C++
#include<bits/stdc++.h>
using namespace std;
// Hàm cấp phát bộ nhớ cho khối theo thuật toán First fit
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process) {
int allocation[total_process];
memset(allocation, -1, sizeof(allocation));
// Vòng lặp này sẽ chọn mỗi tiến trình và cấp phát khối first fit cho nó
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() {
// Tạo mảng lưu kích thước khối
int block_size[] = {300, 50, 200, 350, 70};
// Tạo mảng lưu kích thước tiến trình
int process_size[] = {200, 47, 212, 426, 10};
// Biến total_blocks chứa tổng số khối
int total_blocks = sizeof(block_size) / sizeof(block_size[0]);
// Biến total_process chứa tổng số tiến trình
int total_process = sizeof(process_size) / sizeof(process_size[0]);
// Gọi hàm First_fit
First_Fit(block_size, total_blocks, process_size, total_process);
return 0;
}
Đầu ra
Process No. Process Size Block no. 1 200 1 2 47 1 3 212 4 4 426 Not Allocated 5 10 1