Quản lý bộ nhớ là chức năng của hệ điều hành trong việc xử lý và di chuyển các tiến trình qua lại giữa bộ nhớ chính và đĩa trong quá trình thực thi. Hệ điều hành theo dõi từng vị trí bộ nhớ, bất kể nó được cấp phát cho một số tiến trình hay nó đang trống. Hệ điều hành kiểm tra lượng bộ nhớ được cấp cho các tiến trình. Nó quyết định tiến trình nào sẽ nhận được bộ nhớ vào thời điểm nào. Nó theo dõi bất cứ khi nào một số bộ nhớ được giải phóng hoặc không được cấp phát và tương ứng nó sẽ cập nhật trạng thái.
Bài học này giúp các bạn chạy thử các giải thuật cấp phát bộ nhớ chính trong hệ điều hành. Cụ thể các bạn sẽ viết và chạy các thuật toán cấp phát bộ nhớ là: FirstFit, BestFit và WorstFit.
Trước khi viết chương trình minh họa, chúng ta cùng khảo sát một ví dụ để phân tích việc cấp phát bộ nhớ bằng các thuật toán đã đề cập ở trên.
Bài toán: Cho 6 phân vùng nhớ theo thứ tự: 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, và 125 KB. Các tiến trình với kích thước theo thứ tự: 115 KB, 500 KB, 358 KB, 200 KB, và 375 KB sẽ được cấp phát bộ nhớ như thế nào theo các giải thuật: first-fit, best-fit, và worst-fit.
Bảng phân tích việc cấp phát bộ nhớ theo các thuật toán như sau:
Theo giải thuật First-fit
Yêu cầu (Kích thước tiến trình)
Kích thước hole được chọn
Các kích thước hole còn lại
115KB
300KB
185KB, 600KB, 350KB, 200KB, 750KB, 125KB
500KB
600KB
185KB, 100KB, 350KB, 200KB, 750KB, 125KB
358KB
750KB
185KB, 100KB, 350KB, 200KB, 392KB, 125KB
200KB
350KB
185KB, 100KB, 150KB, 200KB, 392KB, 125KB
375KB
392KB
185KB, 100KB, 150KB, 200KB, 17KB, 125KB
Theo giải thuật Best-fit
Yêu cầu
Kích thước hố nhớ được chọn
Các kích thước hố nhớ còn lại
115KB
125KB
300KB, 600KB, 350KB, 200KB, 750KB, 10KB
500KB
600KB
300KB, 100KB, 350KB, 200KB, 750KB, 10KB
358KB
750KB
300KB, 100KB, 350KB, 200KB, 392KB, 10KB
200KB
200KB
300KB, 100KB, 350KB, 392KB, 10KB
375KB
392KB
300KB, 100KB, 350KB, 17KB, 10KB
Theo giải thuật Worst-fit
Yêu cầu
Kích thước hố nhớ được chọn
Các kích thước hố nhớ còn lại
115KB
750KB
300KB, 600KB, 350KB, 200KB, 635KB, 125KB
500KB
635KB
300KB, 600KB, 350KB, 200KB, 135KB, 125KB
358KB
600KB
300KB, 242KB, 350KB, 200KB, 135KB, 125KB
200KB
350KB
300KB, 242KB, 150KB, 200KB, 135KB, 125KB
375KB
Không thể thực thi
300KB, 242KB, 150KB, 200KB, 135KB, 125KB
Chương trình minh họa giải thuật First-Fit
#include<stdio.h>
int main()
{
static int khoinho[10], tientrinh[10];
int phanmanh[10], kichthuockhoi[10], kichthuoctientrinh[10];
int m, n, sokhoi, sotientrinh, temp;
printf("\nNhập tổng số khối nhớ:");
scanf("%d", &sokhoi);
printf("Nhập tổng số tiến trình:");
scanf("%d", &sotientrinh);
printf("\nNhập kích thước (dung lượng) của mỗi khối nhớ:\n");
for(m = 0; m < sokhoi; m++)
{
printf("Khối.[%d]:", m+1);
scanf("%d", &kichthuockhoi[m]);
}
printf("Nhập kích thước của mỗi tiến trình:\n");
for(m = 0; m < sotientrinh; m++)
{
printf("Tiến trình.[%d]:", m+1);
scanf("%d", &kichthuoctientrinh[m]);
}
for(m = 0; m < sotientrinh; m++)
{
for(n = 0; n < sokhoi; n++)
{
if(kichthuockhoi[n] >= kichthuoctientrinh[m])
{
khoinho[m]=n;
kichthuockhoi[n]=kichthuockhoi[n] - kichthuoctientrinh[m];
temp=kichthuockhoi[n];
tientrinh[m] = n;
break;
}
}
phanmanh[m] = temp;
}
printf("\nTiến trình\t\tKích thước tiến trình\t\tKhối nhớ\t\tPhân mảnh");
for(m = 0; m < sotientrinh; m++)
{
printf("\n%d\t\t\t%d\t\t\t\t%d\t\t\t%d", m+1, kichthuoctientrinh[m],tientrinh[m]+1, phanmanh[m]);
}
printf("\n");
return 0;
}
Kết quả chạy chương trình trên hệ điều hành CentOS, biên dịch bằng GCC
Chương trình minh họa giải thuật Best-Fit
#include <stdio.h>
#include <string.h>
/*Hàm nhập mảng 1 chiều*/
void nhapmang(int array[], int length){
for (short i = 0; i < length; i++)
{
printf("Kích thước thứ %d:",i+1);
scanf("%d", &array[i]);
}
}
void bestFit(int kichthuockhoi[], int m, int kichthuoctientrinh[], int n)
{
//Mảng lưu trữ thứ tự các khối nhớ
int khoinho[n];
//Khởi tạo CHƯA có khối nhớ nào được cấp cho tiến trình
memset(khoinho, -1, sizeof(khoinho));
/*
Hàm memset() trong C được sử dụng để lấp đầy một khối bộ nhớ với một giá trị cụ thể.
Cú pháp của hàm memset() như sau:
void * memset (void * ptr, int x, size_t n);
ptr: Địa chỉ bắt đầu của bộ nhớ sẽ được lấp đầy
x: Giá trị được điền
n: Số byte được điền bắt đầu từ con trỏ ptr
*/
//Chọn từng tiến trình và duyệt tìm khối có kích thước phù hợp với nó nhất
for (int i=0; i<n; i++)
{
// Tìm khối nhớ đủ và tốt nhất cho tiến trình
int khoitotnhat = -1;
for (int j=0; j<m; j++)
{
if (kichthuockhoi[j] >= kichthuoctientrinh[i])
{
if (khoitotnhat == -1)
khoitotnhat = j;
else if (kichthuockhoi[khoitotnhat] > kichthuockhoi[j])
khoitotnhat = j;
}
}
// Khi tìm thấy khối nhớ tốt nhất cho tiến trình hiện hành
if (khoitotnhat != -1)
{
// Cấp phát khối nhớ j cho tiến trình p[i]
khoinho[i] = khoitotnhat;
// Giảm kích thước cho khối nhớ này.
kichthuockhoi[khoitotnhat] -= kichthuoctientrinh[i];
}
}
printf("\nTiến trình\tKích thước\tKhối nhớ số\n");
for (int i = 0; i < n; i++)
{
printf("\n%d\t\t\%d\t\t", i+1, kichthuoctientrinh[i]);
if (khoinho[i] != -1)
printf("%d",khoinho[i] + 1);
else
printf("Chưa được cấp phát\n");
}
}
int main(){
int sokhoi,sotientrinh;
printf("Nhập số khối nhớ: ");
scanf("%d", &sokhoi);
int mang1[sokhoi];
printf("Nhập kích thước cho mỗi khối nhớ:\n");
nhapmang(mang1, sokhoi);
printf("Nhập số tiến trình: ");
scanf("%d", &sotientrinh);
int mang2[sotientrinh];
printf("Nhập kích thước cho mỗi tiến trình:\n");
nhapmang(mang2, sotientrinh);
bestFit(mang1, sokhoi, mang2, sotientrinh);
return 0 ;
}
Kết quả chạy chương trình trên hệ điều hành CentOS, biên dịch bằng GCC
Chương trình minh họa giải thuật Worst-Fit
#include <stdio.h>
#include <string.h>
/*Hàm nhập mảng 1 chiều*/
void nhapmang(int array[], int length){
for (short i = 0; i < length; i++)
{
printf("Kích thước thứ %d:",i+1);
scanf("%d", &array[i]);
}
}
void WorstFit(int kichthuockhoi[], int m, int kichthuoctientrinh[], int n)
{
//Mảng lưu trữ thứ tự các khối nhớ
int khoinho[n];
//Khởi tạo CHƯA có khối nhớ nào được cấp cho tiến trình
memset(khoinho, -1, sizeof(khoinho));
/*
Hàm memset() trong C được sử dụng để lấp đầy một khối bộ nhớ với một giá trị cụ thể.
Cú pháp của hàm memset() như sau:
void * memset (void * ptr, int x, size_t n);
ptr: Địa chỉ bắt đầu của bộ nhớ sẽ được lấp đầy
x: Giá trị được điền
n: Số byte được điền bắt đầu từ con trỏ ptr
*/
//Chọn từng tiến trình và duyệt tìm khối có kích thước phù hợp với nó nhất
for (int i=0; i<n; i++)
{
// Tìm khối nhớ to nhất cho tiến trình
int khoitonhat = -1;
for (int j=0; j<m; j++)
{
if (kichthuockhoi[j] >= kichthuoctientrinh[i])
{
if (khoitonhat == -1)
khoitonhat = j;
else if (kichthuockhoi[khoitonhat] < kichthuockhoi[j])
khoitonhat = j;
}
}
// Khi tìm thấy khối nhớ to nhất cho tiến trình hiện hành
if (khoitonhat != -1)
{
// Cấp phát khối nhớ j cho tiến trình p[i]
khoinho[i] = khoitonhat;
// Giảm kích thước cho khối nhớ này.
kichthuockhoi[khoitonhat] = kichthuockhoi[khoitonhat] - kichthuoctientrinh[i];
}
}
printf("\nTiến trình\tKích thước\tKhối nhớ số\n");
for (int i = 0; i < n; i++)
{
printf("\n%d\t\t\%d\t\t", i+1, kichthuoctientrinh[i]);
if (khoinho[i] != -1)
printf("%d",khoinho[i] + 1);
else
printf("Chưa được cấp phát\n");
}
}
int main(){
int sokhoi,sotientrinh;
printf("Nhập số khối nhớ: ");
scanf("%d", &sokhoi);
int mang1[sokhoi];
printf("Nhập kích thước cho mỗi khối nhớ:\n");
nhapmang(mang1, sokhoi);
printf("Nhập số tiến trình: ");
scanf("%d", &sotientrinh);
int mang2[sotientrinh];
printf("Nhập kích thước cho mỗi tiến trình:\n");
nhapmang(mang2, sotientrinh);
WorstFit(mang1, sokhoi, mang2, sotientrinh);
return 0 ;
}
Kết quả chạy chương trình trên hệ điều hành CentOS, biên dịch bằng GCC
