GIẢI THUẬT ĐỊNH THỜI CPU

GIẢI THUẬT ĐỊNH THỜI CPU

Định thời là một chức năng cơ bản của hệ điều hành. Hầu như tất cả các tài nguyên máy tính đều được lập lịch trước khi sử dụng. Có nhiều giải thuật định thời khác nhau, trong đó mỗi giải thuật định thời đều có cách tiếp cận khác nhau để giúp hệ điều hành điều phối các tiến trình.

Trong bài học này, các bạn sẽ được học một số thuật toán định thời CPU bao gồm: FCFS, SJF độc quyền và SJF không độc quyền.

Mỗi thuật toán đều được minh họa viết bằng ngôn ngữ C để giúp các bạn hiểu rõ hơn về nguyên lý hoạt động của các tiến trình trong hệ điều hành.

Chúng ta cùng bắt đầu với từng giải thuật nhé.

 

THUẬT TOÁN FCFS

Thuật toán đến trước được phục vụ trước (First Come First Serve) thường được viết tắt là FCFS . Nó hoạt động trên nguyên tắc vào trước ra trước (FIFO – First In First Out) .

Các tiến trình đến trong hàng đợi hệ thống (hàng đợi Ready List) được thực thi dựa trên cơ sở “ai đến trước thì được phục vụ trước“. Đây là một thuật toán định thời theo cơ chế độc quyền. .

Khi CPU được cấp phát cho một tiến trình cụ thể, tiến trình đó sẽ thực hiện cho đến khi hoàn thành. CPU không thể rời khỏi tiến trình hiện tại trước khi nó được hoàn thành. Vì vậy, CPU không thể chuyển sang tiến trình khác trong hàng đợi.

FCFS không được tối ưu hóa cho các hệ thống chia sẻ thời gian. Thời gian chờ trung bình cho thuật toán FCFS phụ thuộc nhiều vào thời gian xử lý của các tiến trình.

Ưu điểm của FCFS

  • Đơn giản và dễ thực hiện
  • Mọi tiến trình đều được thực thi
  • Khả năng đói CPU thấp

Nhược điểm của FCFS

  • Hiệu suất kém do thời gian chờ trung bình cao
  • Không có tùy chọn ưu tiên cho một tiến trình.
  • Thời gian hoàn tất trung bình của tiến trình cao
  • Không hiệu quả cho các hệ thống chia sẻ thời gian

Ví dụ về thuật toán FCFS

Cho bảng dữ liệu định thời như sau:

Tiến trình Thời gian xử lý
P1 24
P2 3
P3 3

Tính thời gian chờ, thời gian hoàn tất của từng tiến trình; thời gian chờ trung bình, thời gian hoàn tất trung bình theo giải thuật FCFS

Biểu đồ Gantt cho thuật toán FCFS với dữ liệu đã cho là

  • Thời gian chờ (waiting time) của mỗi tiến trình:

P1=0

P2=24

P3=27

  • Thời gian chờ trung bình: (0+24+27)/3 = 17
  • Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=24

P2=27

P3=30

  • Thời gian hoàn tất trung bình: (24+27+30)/3 = 27

Chương trình C minh họa thuật toán định thời FCFS

#include<stdio.h>
 
int main()
{
        float TG_XuLy[30], TG_Cho[30], TG_HoanTat[30];
        float TG_cho_TB = 0.0, TG_HoanTat_TB = 0.0;
        int count, j, So_TienTrinh;
        printf("Nhap so Tien trinh thuc thi:\t");
        scanf("%d", &So_TienTrinh);
        printf("\nNhap thoi gian xu ly cua moi Tien trinh:\n\n");
        for(count = 0; count < So_TienTrinh; count++)
        {
                printf("P[%d]:", count + 1);
                scanf("%f", &TG_XuLy[count]);
        }
        TG_Cho[0] = 0;   
        for(count = 1; count < So_TienTrinh; count++)
        {
                TG_Cho[count] = 0;
                for(j = 0; j < count; j++)
                {
                        TG_Cho[count] = TG_Cho[count] + TG_XuLy[j];
                }
        }
        printf("\nTien Trinh\tTG Xu ly\tTG cho\t\tTG Hoan tat\n");
        for(count = 0; count < So_TienTrinh; count++)
        {
                TG_HoanTat[count] = TG_XuLy[count] + TG_Cho[count];
                TG_cho_TB = TG_cho_TB + TG_Cho[count];
                TG_HoanTat_TB = TG_HoanTat_TB + TG_HoanTat[count];
                printf("\nP[%d]\t\t%.2f\t\t%.2f\t\t%.2f", count + 1, TG_XuLy[count], TG_Cho[count], TG_HoanTat[count]);
        }
        printf("\n");
        TG_cho_TB = TG_cho_TB / count;
        TG_HoanTat_TB = TG_HoanTat_TB / count;
        printf("\nThoi gian cho trung binh = %f", TG_cho_TB);
        printf("\nThoi gian hoan tat trung binh = %f", TG_HoanTat_TB);
        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)

 

THUẬT TOÁN SJF ĐỘC QUYỀN

Thuật toán định thời công việc đầu tiên ngắn nhất (SJF – Shortest Job First) là một thuật toán định thời công việc rất phổ biến trong các hệ điều hành. Thuật toán này được thiết kế để khắc phục những thiếu sót của thuật toán FCFS.

Ban đầu, hàng đợi công việc chứa nhiều tiến trình để thực thi. Theo thuật toán SJF độc quyền, các tiến trình được so sánh với nhau và tiến trình có thời gian xử lý ngắn nhất (thời gian thực thi) sẽ được thực thi đầu tiên.

Các tiến trình còn lại cũng được thực hiện theo thứ tự thời gian xử lý của chúng. Nếu có hai hoặc nhiều tiến trình có cùng thời gian thực thi, thì các tiến trình sẽ được thực hiện theo thứ tự đến hàng đợi của chúng.

Khi CPU bắt đầu thực hiện một tiến trình, nó phải hoàn thành tiến trình thành công và sau đó chuyển sang tiến trình khác trong hàng đợi.

Ưu điểm

  • Thời gian phản hồi của các tiến trình tốt hơn.
  • Thông lượng tốt hơn nhiều vì thời gian thực hiện ít hơn.
  • Hiệu suất tổng thể của hệ thống là hiệu quả.

Nhược điểm

  • Thời gian thực hiện của tất cả các tiến trình trong hàng đợi công việc phải được biết trước để áp dụng thuật toán một cách hiệu quả cho tất cả các tiến trình.
  • Các tiến trình có thời gian thực thi lớn hơn sẽ có thời gian chờ cao hơn và điều này có thể dẫn đến đói CPU.

Ví dụ về thuật toán SJF độc quyền

Cho bảng dữ liệu định thời như sau:

Tiến trình Thời gian xử lý
P1 6
P2 8
P3 7
P4 3

Tính thời gian chờ, thời gian hoàn tất của từng tiến trình; thời gian chờ trung bình, thời gian hoàn tất trung bình theo giải thuật SJF độc quyền

Biểu đồ Gantt cho thuật toán SJF độc quyền với dữ liệu đã cho là

  • Thời gian chờ (waiting time) của mỗi tiến trình:

P1=3

P2=16

P3=9

P4=0

  • Thời gian chờ trung bình: (3+16+9+0)/4 = 7
  • Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=9

P2=24

P3=16

P4=3

  • Thời gian hoàn tất trung bình: (9+24+16+3)/4 = 13

Chương trình C minh họa thuật toán định thời SJF độc quyền

#include<stdio.h>
 
int main()
{
      int tam, i, j, soTT, tong = 0, vitri;
      float tgchotb, tghttb; //thoi gian cho trung binh va thoi gian hoan tat trung binh
      int tgxl[20], tt[20], tgcho[20], tght[20];
      printf("\nNhap so tien trinh:\t");
      scanf("%d", &soTT); 
      for(i = 0; i < soTT; i++)
      {
            printf("Nhap thoi gian xu ly cua tien trinh[%d]:\t", i + 1);
            scanf("%d", &tgxl[i]);
            tt[i] = i + 1;
      }
      for(i = 0; i < soTT; i++)
      {
            vitri = i;
            for(j = i + 1; j < soTT; j++)
            {
                  if(tgxl[j] < tgxl[vitri])
                  {
                        vitri = j;
                  }
            }
            tam = tgxl[i];
            tgxl[i] = tgxl[vitri];
            tgxl[vitri] = tam;
            tam = tt[i];
            tt[i] = tt[vitri];
            tt[vitri] = tam;
      } 
      tgcho[0] = 0;
      for(i = 1; i < soTT; i++)
      {
            tgcho[i] = 0;
            for(j = 0; j < i; j++)
            {
                  tgcho[i] = tgcho[i] + tgxl[j];
            } 
            tong = tong + tgcho[i];
      }
      tgchotb = (float)tong / soTT;
      tong = 0;
      printf("\nTiến trình\tTG Xử lý\t TG chờ\t\t TG hoàn tất\n");
      for(i = 0; i < soTT; i++)
      {
            tght[i] = tgxl[i] + tgcho[i];
            tong = tong + tght[i];
            printf("\nP[%d]\t\t%d\t\t %d\t\t %d\n", tt[i], tgxl[i], tgcho[i], tght[i]);
      }
      tghttb = (float)tong / soTT;
      printf("\nThời gian chờ trung bình:\t%f\n", tgchotb);
      printf("\nThời gian hoàn tất trung bình:\t%f\n", tghttb);
      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)

THUẬT TOÁN SJF KHÔNG ĐỘC QUYỀN

Theo thuật toán SJF, các công việc trong hàng đợi được so sánh với nhau và công việc có thời gian xử lý ngắn nhất sẽ được thực thi trước.

Các tiến trình còn lại cũng được thực hiện theo thứ tự thời gian xử lý của chúng. Tuy nhiên, có thể có các tình huống trong đó một hoặc nhiều tiến trình có cùng thời gian thực hiện.

Trong những trường hợp như vậy, các tiến trình dựa trên cơ chế “đến trước được phục vụ trước” hay nói cách khác, phương pháp FIFO được sử dụng.

Thuật toán SJF theo cơ chế không độc quyền có nghĩa là CPU có thể rời khỏi một tiến trình trong khi nó đang thực thi và chuyển sang tiến trình khác trong hàng đợi.

Ưu điểm

  • Thời gian phản hồi tốt hơn nhiều so với thuật toán FCFS.
  • Thời gian chờ trung bình tối thiểu.
  • Thông lượng tốt vì thời gian xử lý của các tiến trình ít hơn.
  • Thời gian xuay vòng tối ưu.

Nhược điểm

  • Thời gian thực hiện của tất cả các tiến trình trong hàng đợi phải được biết trước, điều này không thể thực hiện được trong tất cả các tình huống.
  • Các tiến trình có thời gian xử lý lớn hơn sẽ có thời gian chờ cao và điều này có thể dẫn đến đói CPU.

Ví dụ về thuật toán SJF không độc quyền

Cho bảng dữ liệu định thời như sau:

Tiến trình Thời gian đến Ready List (RL) Thời gian xử lý (thực thi)
P1 0 7
P2 1 16
P3 3 8
P4 4 3
P5 2 2

Tính thời gian chờ, thời gian hoàn tất của từng tiến trình; thời gian chờ trung bình, thời gian hoàn tất trung bình theo giải thuật SJF không độc quyền

Biểu đồ Gantt cho thuật toán SJF không độc quyền với dữ liệu đã cho là

  • Thời gian chờ (waiting time) của mỗi tiến trình:

P1=0+(7-2)=5

P2=20-1=19

P3=12-3=9

P4=4-4=0

P5=2-2=0

  • Thời gian chờ trung bình: (5+19+9+0+0)/5 = 6.6
  • Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=12

P2=36-1=35

P3=20-3=17

P4=7-4=3

P5=4-2=2

  • Thời gian hoàn tất trung bình: (12+35+17+3+2)/5 = 13.8

Chương trình C minh họa thuật toán định thời SJF không độc quyền

#include <stdio.h>
 
int main() 
{
      int tgdenRL[10], tgxl[10], tam[10];
      int i, nhonhat, dem = 0, thoigian, soTT;
      double tgcho = 0, tght = 0, ketthuc;
      float tgchotb, tghttb;
      printf("\nNhap so tien trinh:\t");
      scanf("%d", &soTT); 
      printf("\nNhap du lieu chi tiet cho %d tien trinh\n", soTT);
      for(i = 0; i < soTT; i++)
      {
            printf("\nNhap thoi gian den hang doi Ready cua tien trinh thu %d :", i+1);
            scanf("%d", &tgdenRL[i]);
            printf("Nhap thoi gian xu ly cua tien trinh thu %d :", i+1);
            scanf("%d", &tgxl[i]); 
            tam[i] = tgxl[i];
      }
      tgxl[9] = 60;  //Gia su thoi gian xu ly cua tien trinh cuoi cung la 60 giay
      for(thoigian = 0; dem != soTT; thoigian++)
      {
            nhonhat = 9; //Xet tien trinh co thoi gian nho nhat (tien trinh sau cung)
            for(i = 0; i < soTT; i++)
            {
                  if(tgdenRL[i] <= thoigian && tgxl[i] < tgxl[nhonhat] && tgxl[i] > 0)
                  {
                        nhonhat = i;
                  }
            }
            tgxl[nhonhat]--;
            if(tgxl[nhonhat] == 0)
            {
                  dem++;
                  ketthuc = thoigian + 1;
                  tgcho = tgcho + ketthuc - tgdenRL[nhonhat] - tam[nhonhat];
                  tght = tght + ketthuc - tgdenRL[nhonhat];
            }
      }
      tgchotb = tgcho / soTT; 
      tghttb = tght / soTT;
      printf("\n\nThoi gian cho trung binh:\t%lf\n", tgchotb);
      printf("Thoi gian hoan tat trung binh:\t%lf\n", tghttb);
      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)

 

Bạn vừa hoàn thành bài học với 2 thuật toán: FCFS và SJF rồi đó.

Hẹn gặp các bạn ở bài học tiếp theo với 2 thuật toán: Round Robin và Độ ưu tiên.

Chúc các bạn học tập thật tốt.

 

5 1 vote
Article Rating
guest
0 Comments
Inline Feedbacks
View all comments