TẮC NGHẼN

Giải thuật Banker

Giải thuật Banker là một giải thuật cấp phát tài nguyên và tránh tắc nghẽn của hệ điều hành. Banker được thực thi bằng cách mô phỏng việc cấp phát cho số lượng tối đa có thể xác định trước của tất cả các tài nguyên, sau đó thực hiện kiểm tra trạng thái an toàn để kiểm tra các hoạt động có thể xảy ra, trước khi quyết định có nên cho phép cấp phát hay không.

Các cấu trúc dữ liệu sau được sử dụng để triển khai giải thuật Banker: Gọi n là số tiến trình; m là số tài nguyên

• Available: vector với độ dài m, là số thực thể đang khả dụng (có sẵn). Nếu available[j]=k, có k thực thể của tài nguyên Rj là khả dụng.

• Max: ma trận nxm, số thực thể tối đa mà tiến trình yêu cầu. Nếu Max[i,j]=k, thì tiến trình Pi có thể yêu cầu nhiều nhất k thực thể của tài nguyên Rj.

• Allocation: ma trận nxm, số thực thể của tài nguyên đã cấp phát cho tiến trình. Nếu Allocation[i,j]=k, thì hiện hành tiến trình Pi được cấp phát k thực thể của tài nguyên Rj.

• Need: ma trận nxm, số thực thể tiến trình cần để hoàn thành tác vụ. Nếu Need[i,j]=k, thì tiến trình Pi cần thêm k thực thể của Rj để hoàn thành tác vụ.

Need[i,j]=Max[i,j]-Allocation[i,j]

Giải thuật Banker bao gồm 2 thuật toán: Thuật toán xác định trạng thái an toàn và thuật toán yêu cầu tài nguyên.

Giải thuật xác định trạng thái an toàn

Bước 1. Gọi Work và Finish là 2 vector với độ dài tương ứng là m và n. Khởi tạo:

Work = Available

Finish [i] = false với i = 0, 1, …, n- 1

Bước 2. Tìm i thỏa 2 điều kiện:

Finish[i]=false

Needi <= Work

Nếu không tồn tại i như vậy thì qua Bước 4

Bước 3.

Work = Work + Allocationi

Finish[i] = true

Quay lại Bước 2

Bước 4. Nếu Finish [i] == true với tất cả i, thì hệ thống ở trạng thái an toàn

Giải thuật yêu cầu tài nguyên của tiến trình Pi

Requesti – vector tài nguyên yêu cầu của tiến trình Pi. Nếu Requesti[j]=k thì tiến trình Pi muốn k thực thể của tài nguyên Rj

Bước 1. Nếu Requesti <= Needi tới Bước 2. Ngược lại, đưa ra lỗi vì tiến trình vượt quá đòi hỏi tối đa.

Bước 2. Nếu Requesti <= Available tới Bước 3. Ngược lại, Pi phải chờ vì tài nguyên không có sẵn.

Bước 3. Giả sử hệ thống đã cấp phát cho Pi các tài nguyên mà nó yêu cầu và cập nhật tình trạng hệ thống như sau:

Available = Available – Requesti;

Allocationi = Allocationi + Requesti;

Needi = Needi – Requesti;

• Nếu trạng thái là an toàn --> tài nguyên được cấp phát cho Pi.

• Nếu trạng thái là không an toàn --> Pi phải chờ, và trạng thái cấp phát tài nguyên cũ được phục hồi.

Ví dụ về giải thuật Banker

Xem xét trạng thái của một hệ thống như sau:

Sử dụng giải thuật Banker, trả lời các câu hỏi sau:

1. Cho biết kết quả của ma trận Need

2. Hệ thống có trong trạng thái an toàn không?

3. Nếu P1 yêu cầu (0,4,2,0), thì yêu cầu có thể được cấp không?

Thực thi giải thuật Banker, ta có các kết quả phân tích như sau:

Ta có công thức: Need[i,j] = Max[i,j] – Allocation[i,j]

Hệ thống ở trạng thái an toàn vì:

o Với Available=(1,5,2,0) thì hoặc P0, hoặc P3 có thể chạy.

o Chọn P3 chạy. Khi P3 chạy xong, nó giải phóng tài nguyên của nó, khi đó Available=(1,11,5,2)

o P0 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(1,11,6,4)

o P1 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(2,11,6,4)

o P2 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(3,14,11,8)

o P4 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(3,14,12,12)

o Như vậy hệ thống đã kết thúc an toàn với chuỗi an toàn: <P3,P0,P1,P2,P4>

Nếu P1 yêu cầu (0,4,2,0), thì yêu cầu có thể được cấp không?

Yêu cầu của P1 đều nhỏ hơn Need hiện tại của nó và Available, nên tài nguyên hệ thống sẽ thay đổi như sau khi thực hiện yêu cầu của P1:

Một thứ tự hoàn thành của các tiến trình như sau: <P0,P2,P3,P1,P4>

Giải thích thứ tự nhận và trả tài nguyên của các tiến trình:

o P0 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(1,1,1,2)

o P2 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(2,4,6,6)

o P3 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(2,10,9,8)

o P1 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(3,14,11,8)

o P4 chạy xong, trả lại tài nguyên cho hệ thống, khi đó Available=(3,14,12,12)

Chương trình C minh họa giải thuật Banker

#include <stdio.h>
 
int main()
{
      int dem = 0, m, n, tientrinh, tam, tainguyen; 
      int bangtainguyen[5] = {0, 0, 0, 0, 0};
      int tainguyensanco[5], tainguyenhienhanh[5][5], yeucautoida[5][5];
      int tainguyentoida[5], dangchay[5], trangthaiantoan = 0;
      printf("\nNhập số tiến trình:\t");
      scanf("%d", &tientrinh);
      for(m = 0; m < tientrinh; m++) 
      {
            dangchay[m] = 1;
            dem++;
      }
      printf("\nNhập tổng số loại tài nguyên cấp phát:\t");
      scanf("%d", &tainguyen);
      printf("\nNhập tổng số tài nguyên mỗi loại (cách nhau bằng khoảng trắng):\t");
      for(m = 0; m < tainguyen; m++) 
      { 
            scanf("%d", &tainguyentoida[m]);
      }
      printf("\nNhập ma trận tài nguyên đã cấp phát (mỗi tiến trình 1 dòng, mỗi phần từ cách nhau khoảng trắng):\n");
      for(m = 0; m < tientrinh; m++) 
      {
            for(n = 0; n < tainguyen; n++) 
            {
                  scanf("%d", &tainguyenhienhanh[m][n]);
            }
      }
      printf("\nNhập ma trận tài nguyên yêu cầu tối đa của các tiến trình (mỗi tiến trình 1 dòng, mỗi phần từ cách nhau khoảng trắng):\n");
      for(m = 0; m < tientrinh; m++) 
      {
            for(n = 0; n < tainguyen; n++) 
            {
                  scanf("%d", &yeucautoida[m][n]);
            }
      }
      
      ///////////////////KẾT QUẢ///////////////////////////
      void blue () {        //sử dụng hàm in màu chữ cho text
        printf("\033[0;34m"); //Mã màu xanh dương. Một số mã khác: Red \033[0;31m - Green \033[0;32m - Yellow \033[0;33m - Purple \033[0;35m
      }
      blue ();
      printf("KẾT QUẢ GIẢI THUẬT BANKER \n");
      printf("\nTổng mỗi loại tài nguyên của hệ thống \n");
      for(m = 0; m < tainguyen; m++) 
      {
            printf("\t%d ", tainguyentoida[m]);
      }
      printf("\n Ma trận tài nguyên đã cấp phát\n");
      for(m = 0; m < tientrinh; m++) 
      {
            for(n = 0; n < tainguyen; n++) 
            {
                  printf("\t%d", tainguyenhienhanh[m][n]);
            }
            printf("\n");
      }
      printf("\nMa trận tài nguyên tối đa mà các tiến trình cần dùng \n");
      for(m = 0; m < tientrinh; m++) 
      {
            for(n = 0; n < tainguyen; n++) 
            {
                  printf("\t%d", yeucautoida[m][n]);
            }
            printf("\n");
      }
      for(m = 0; m < tientrinh; m++) 
      {
            for(n = 0; n < tainguyen; n++) 
            {
                  bangtainguyen[n] = bangtainguyen[n] + tainguyenhienhanh[m][n];
            }
      }
      printf("\nTài nguyên đã cấp phát \n");
      for(m = 0; m < tainguyen; m++) 
      {
            printf("\t%d", bangtainguyen[m]);
      }
      for(m = 0; m < tainguyen; m++) 
      {
            tainguyensanco[m] = tainguyentoida[m] - bangtainguyen[m];
      }
      printf("\nTài nguyên có sẵn của hệ thống:");
      for(m = 0; m < tainguyen; m++) 
      {
            printf("\t%d", tainguyensanco[m]);
      }
      printf("\n");
      while(dem != 0) 
      {
            trangthaiantoan = 0;
            for(m = 0; m < tientrinh; m++) 
            {
                  if(dangchay[m]) 
                  {
                        tam = 1;
                        for(n = 0; n < tainguyen; n++) 
                        {
                              if(yeucautoida[m][n] - tainguyenhienhanh[m][n] > tainguyensanco[n]) 
                              {
                                    tam = 0;
                                    break;
                              }
                        }
                        if(tam) 
                        {
                               printf("\nTiến trình %d thực thi \n", m + 1);
                               dangchay[m] = 0;
                               dem--;
                               trangthaiantoan = 1;
                               for(n = 0; n < tainguyen; n++) 
                               {
                                     tainguyensanco[n] = tainguyensanco[n] + tainguyenhienhanh[m][n];
                               }
                               break;
                        }
                  }
            }
            if(!trangthaiantoan) 
            {
                  printf("\nCác tiến trình đang ở trạng thái không an toàn \n");
                  break;
            } 
            else 
            {
                  printf("\nTiến trình ở trạng thái an toàn \n");
                  printf("\nTài nguyên sẵn có của hệ thống\n");
                  for(m = 0; m < tainguyen; m++) 
                  {
                        printf("\t%d", tainguyensanco[m]);
                  }
                  printf("\n");
            }
      }
      return 0;
}

Kết quả chạy chương trình (biên dịch bằng GCC trong môi trường hệ điều hành CentOS)