BỘ NHỚ CHÍNH

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