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, SJF không độc quyền, Round Robin, Độ ưu tiên độc quyền và độ ưu tiên 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ý

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ý

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)

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)

THUẬT TOÁN ROUND ROBIN

Round robin là một giải thuật định thời CPU, trong đó mỗi tiến trình được gán một thời gian giữ CPU nhất định trong một chu kỳ chạy, thời gian đó được gọi là thời gian xoay vòng (quantum).

Giải thuật Round Robin có một số đặc điểm sau:

- Là giải thuật chạy theo cơ chế không độc quyền vì mỗi tiến trình đều có một thời gian xoay vòng như nhau

- Đơn giản, dễ thực thi, và tất cả các tiến trình tránh được tình trạng "đói CPU"

- Khuyết điểm chính của giải thuật là tốn nhiều thời gian chuyển ngữ cảnh

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

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)

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 Round Robin. Với q=3.

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

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

P1=0+(8-3)+(20-11)=14

P2=(3-1)+(17-6)+(24-20)+(29-27)=19

P3=(11-3)+(21-14)+(27-24)=18

P4=14-4=10

P5=6-2=4

- Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=21

P2=36-1=35

P3=29-3=26

P4=17-4=13

P5=8-2=6

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

#include<stdio.h> 

float  tg_cho[100], tg_hoantat[100], tg_cho_tb, tg_ht_tb, tamTT[100], tamDen[100];
int tgxl[100], tg_den[100], tgchomoidoan[100], tien_trinh_nghi[100], tt[100], vtcu[100], sl_tt, quantum, sl;

void NhapTienTrinh()
{
      int i;
      printf("Nhap so tien trinh:\t"); 
      scanf("%d", &sl_tt); 
      for(i = 0; i < sl_tt; i++) 
      {
            printf("\nNhap du lieu chi tiet cho tien trinh thu %d\n", i + 1);
            printf("Thoi gian den hang doi:\t");
            scanf("%d", &tg_den[i]);
            printf("Thoi gian xu ly:\t");
            scanf("%d", &tgxl[i]); 
            tamTT[i] = tgxl[i];
	    tg_cho[i]=0;
	    tg_hoantat[i]=0;
	    tt[i]=i+1;
	    tamDen[i]=tg_den[i];
      } 
      printf("\nNhap thoi gian xoay vong (Time Quantum):\t"); 
      scanf("%d", &quantum); 
}

void XuatTienTrinh()
{
	printf("Tien trinh\tTG den RL\tTG xu ly\tTG cho\tTG hoan tat\n");
	int i;
	for(i=0; i<sl_tt; i++)
		printf("P[%d]\t\t%2d\t\t%2d\t\t%.2f\t%.2f\n", tt[i], tg_den[i], tgxl[i], tg_cho[i], tg_hoantat[i]);
	printf("\nThoi gian cho trung binh: %.2f", tg_cho_tb);
	printf("\nThoi gian hoan tat trung binh: %.2f", tg_ht_tb);
	printf("\n");
}

//Hàm ngắt tiến trình khi hết thời gian xoay vòng (quantum) mà vẫn chưa chạy xong
void xoa(int vt)
{
    int i=vt;
    for(;i<sl;i++)
    {
        tamTT[i]=tamTT[i+1];
        tamDen[i]=tamDen[i+1];
        vtcu[i]=vtcu[i+1];
    }
    sl--;
}

//Hàm xoay vòng của 1 tiến trình
void chen(int vt, int gt, int gtden, int gtvtcu)
{
    int i;
    for(i=sl; i>vt; i--)
    {
        tamTT[i]=tamTT[i-1];
        tamDen[i]=tamDen[i-1];
        vtcu[i]=vtcu[i-1];
    }
    
    tamTT[vt]=gt;
    tamDen[vt]=gtden;
    vtcu[vt]=gtvtcu;
    sl++;
}

//Hàm giải thuật định thời Round Robin
void RoundRobin()
{
    tg_ht_tb=0;
    tg_cho_tb=0;
    tg_cho[0]=0;
    int i, tong_tg_chay=0;
    for(i=0; i<sl_tt; i++)
    {
        int j=i+1;
        for( ; j<sl_tt; j++)
            if(tg_den[i]>tg_den[j])
            {
                int t=tg_den[i];
                tg_den[i]=tg_den[j];
                tg_den[j]=t;
                t=tgxl[i];
                tgxl[i]=tgxl[j];
                tgxl[j]=t;
                t=tt[i];
                tt[i]=tt[j];
                tt[j]=t;
                tien_trinh_nghi[i]=0;
            }
            
            vtcu[i]=i;
            tamTT[i]=tgxl[i];
            tamDen[i]=tg_den[i];
            
    }
    
    sl=sl_tt;
    int j=0;
    //vòng lặp sẽ duyệt qua số lần xoay vòng của tiến trình
    while(sl>0)
    {
        tg_cho[vtcu[0]] += tong_tg_chay - tamDen[0] - tien_trinh_nghi[vtcu[0]];
        tamDen[0]=0;
        
        //trường hợp tiến trình có thời gian xử lý lớn hơn thời gian xoay vòng (quantum)
        if(tamTT[0]>quantum)
        {
            tong_tg_chay += quantum;
            tien_trinh_nghi[vtcu[0]] = tong_tg_chay;
            tamTT[0] -= quantum;
            j=1;
            while(tamDen[j] < tong_tg_chay && j<sl)
            j++;
            if(tamDen[j] != tong_tg_chay)
            {
                j=sl;
            }
            chen(j, tamTT[0], tamDen[0], vtcu[0]);
            xoa(0);
        }
        else    //trường hợp tiến trình có thời gian xử lý nhỏ hơn thời gian xoay vòng (quantum)
        {
            tong_tg_chay += tamTT[0];
            tg_cho_tb += tg_cho[vtcu[0]];
            tg_hoantat[vtcu[0]] = tong_tg_chay - tg_den[vtcu[0]];
            tg_ht_tb += tg_hoantat[vtcu[0]];
            xoa(0);
        }
        
        //tính thời gian chờ trung bình và thời gian hoàn tất trung bình của các tiến trình
        tg_cho_tb /= sl_tt;
        tg_ht_tb /= sl_tt;
    }
}



int main() 
{ 
	NhapTienTrinh();
	RoundRobin();
	XuatTienTrinh();	
}

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 PRIORITY ĐỘC QUYỀN

Định thời ưu tiên là một phương pháp điều phối tiến trình dựa trên mức độ ưu tiên của mỗi tiến trình. Định thời ưu tiên hoạt động theo 2 cơ chế: Độc quyến và không độc quyền.

Với cơ chế độc quyền, một khi tiến trình đã nhận CPU thì nó sẽ chạy cho đến hết thời gian thực thi của nó, bất kể tiến trình khác có độ ưu tiên cao hơn nó.

Ví dụ về thuật toán Priority độ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)

Độ ưu tiên

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 Priority độc quyền.

Biểu đồ Gantt cho thuật toán Priority độ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

P2=7-1=6

P3=25-3=22

P4=33-4=29

P5=23-2=21

- Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=7

P2=23-1=22

P3=33-3=30

P4=36-4=32

P5=25-2=23

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

/////////CHUONG TRINH MINH HOA GIAI THUAT DINH THOI THEO DO UU TIEN - DOC QUYEN //////////////

#include<stdio.h>
struct TienTrinh
{
    int ma_tt,tg_cho,tg_denRL,tg_xuly,tg_hoantat,do_uu_tien;
};
struct TienTrinh a[10];

// Ham hoan doi
void hoandoi(int *b,int *c)
{
    int tem;
    tem=*c;
    *c=*b;
    *b=tem;
}


int main()
{
    int i,j;
    int sotientrinh,kiemtra_tg_denRL=0;
    int tg_tra_CPU=0;
    float TongTG_cho=0,TongTG_hoantat=0,tg_cho_tb,tg_hoantat_tb;
    printf("Nhap so tien trinh \n");
    scanf("%d",&sotientrinh);
    printf("Nhap thoi gian den hang doi, thoi gian xu ly va do uu tien cho moi tien trinh (moi tien trinh nhap 1 dong; moi gia tri cach nhau khoang trang)\n");
    printf("TG-den|TG-xu ly|Do-uu tien\n");
    for(i=0;i<sotientrinh;i++)
    {
        scanf("%d%d%d",&a[i].tg_denRL,&a[i].tg_xuly,&a[i].do_uu_tien);
        a[i].ma_tt=i+1;
        // Kiem tra thoi gian den hang doi cua tien trinh: cung nhau hoac khac nhau 
        if(i==0)
         kiemtra_tg_denRL=a[i].tg_denRL;
         
        if(kiemtra_tg_denRL!=a[i].tg_denRL )
         kiemtra_tg_denRL=1;
        
    }
    // Neu tien trinh den hang doi voi thoi gian khac nhau thi sap xep cac tien trinh dua tren thoi gian den
    if(kiemtra_tg_denRL!=0)
    {
        for(i=0;i<sotientrinh;i++)
        {
            for(j=0;j<sotientrinh-i-1;j++)
            {
                if(a[j].tg_denRL>a[j+1].tg_denRL)
                {
                      hoandoi(&a[j].ma_tt,&a[j+1].ma_tt);
                      hoandoi(&a[j].tg_denRL,&a[j+1].tg_denRL);
                      hoandoi(&a[j].tg_xuly,&a[j+1].tg_xuly);
                      hoandoi(&a[j].do_uu_tien,&a[j+1].do_uu_tien);
                }
            }
        }
    }
    
    
    // Neu tat ca tien trinh den Ready List voi thoi gian khac nhau
    if(kiemtra_tg_denRL!=0)
    {
        a[0].tg_cho=a[0].tg_denRL;
        a[0].tg_hoantat=a[0].tg_xuly-a[0].tg_denRL;
        // cmp_time for completion time
        tg_tra_CPU=a[0].tg_hoantat;
        TongTG_cho=TongTG_cho+a[0].tg_cho;
        TongTG_hoantat=TongTG_hoantat+a[0].tg_hoantat;
        for(i=1;i<sotientrinh;i++)
        {
            int min=a[i].do_uu_tien;
            for(j=i+1;j<sotientrinh;j++)
            {
                if(min>a[j].do_uu_tien && a[j].tg_denRL<=tg_tra_CPU)
                {
                      min=a[j].do_uu_tien;
                      hoandoi(&a[i].ma_tt,&a[j].ma_tt);
                      hoandoi(&a[i].tg_denRL,&a[j].tg_denRL);
                      hoandoi(&a[i].tg_xuly,&a[j].tg_xuly);
                      hoandoi(&a[i].do_uu_tien,&a[j].do_uu_tien);
                      
                }
                
            }
            a[i].tg_cho=tg_tra_CPU-a[i].tg_denRL;
            TongTG_cho=TongTG_cho+a[i].tg_cho;
            // Thoi gian hoan thanh cua tien trinh
            tg_tra_CPU=tg_tra_CPU+a[i].tg_xuly;
            
            // Thoi gian hoan tat cua tien trinh (hoan thanh - thoi gian den Ready List)
            a[i].tg_hoantat=tg_tra_CPU-a[i].tg_denRL;
            TongTG_hoantat=TongTG_hoantat+a[i].tg_hoantat;
            
        }
    }
    
    // Neu tat ca tien trinh den cung thoi gian
    else
    {
        for(i=0;i<sotientrinh;i++)
        {
            int min=a[i].do_uu_tien;
            for(j=i+1;j<sotientrinh;j++)
            {
                if(min>a[j].do_uu_tien && a[j].tg_denRL<=tg_tra_CPU)
                {
                    min=a[j].do_uu_tien;
                      hoandoi(&a[i].ma_tt,&a[j].ma_tt);
                      hoandoi(&a[i].tg_denRL,&a[j].tg_denRL);
                      hoandoi(&a[i].tg_xuly,&a[j].tg_xuly);
                      hoandoi(&a[i].do_uu_tien,&a[j].do_uu_tien);
                }
                
            }
            a[i].tg_cho=tg_tra_CPU-a[i].tg_denRL;
            
             // Thoi gian hoan thanh cua tien trinh
            tg_tra_CPU=tg_tra_CPU+a[i].tg_xuly;
            
            // Thoi gian hoan tat cua tien trinh
           
            a[i].tg_hoantat=tg_tra_CPU-a[i].tg_denRL;
            TongTG_cho=TongTG_cho+a[i].tg_cho;
            TongTG_hoantat=TongTG_hoantat+a[i].tg_hoantat;
            
        }
        
    }
    
   

    // Thuc hien in ket qua
   void red () {        //sử dụng hàm in màu chữ cho text
   printf("\033[0;31m"); //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
      }
      red ();
    printf("Ket qua dinh thoi tien trinh theo DO UU TIEN DOC QUYEN\n");
    printf("Tien trinh\tTG cho\t\tTG hoan tat\n");
    for(i=0;i<sotientrinh;i++)
    {
        printf("%d\t\t%d\t\t%d\n",a[i].ma_tt,a[i].tg_cho,a[i].tg_hoantat);
    }
    
    
    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 PRIORITY KHÔNG ĐỘC QUYỀN

Với cơ chế không độc quyền, khi tiến trình được nhận CPU thì nó sẽ chạy cho đến khi có sự xuất hiện của tiến trình mới đến có độ ưu tiên cao hơn nó. Tiến trình có độ ưu tiên thấp hơn sẽ phải chờ cho đến khi các tiến trình có độ ưu tiên cao hơn chạy xong.

Ví dụ về thuật toán Priority 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)

Độ ưu tiên

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 Priority không độc quyền.

Biểu đồ Gantt cho thuật toán Priority 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+(19-1)=18

P2=1-1=0

P3=25-3=22

P4=33-4=29

P5=17-2=15

- Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=25

P2=17-1=16

P3=33-3=30

P4=36-4=32

P5=19-2=17

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

/////////CHUONG TRINH MINH HOA GIAI THUAT DINH THOI THEO DO UU TIEN - KHONG DOC QUYEN //////////////

#include<stdio.h>
struct TienTrinh
{
    int tg_cho,tg_denRL,tg_xuly,tg_hoantat,do_uu_tien;
};

struct TienTrinh a[10];

int main()
{
    int i,sotientrinh,tam[10],t,dem=0,uu_tien_nho;
    float TongTG_cho=0,TongTG_hoantat=0,tg_cho_tb,tg_hoantat_tb;
    printf("Nhap so tien trinh: ");
    scanf("%d",&sotientrinh);
    printf("Nhap thoi gian den hang doi Ready List, thoi gian xu ly va do uu tien cua cac tien trinh (Moi tien trinh 1 dong, moi gia tri cach nhau khoang trang\n");
    printf("TG_denRL| TG_XuLy| Do_UuTien\n");
    for(i=0;i<sotientrinh;i++)
    {
        scanf("%d%d%d",&a[i].tg_denRL,&a[i].tg_xuly,&a[i].do_uu_tien);
        
        // Sao chep thoi gian xu ly vao Mang tam
        tam[i]=a[i].tg_xuly;
    }
    
    //Gia su khoi tao do uu tien cua tien trinh la MAX (gia tri lon nhat)
    a[9].do_uu_tien=5000;
    
    for(t=0;dem!=sotientrinh;t++)
    {
        uu_tien_nho=9;
        for(i=0;i<sotientrinh;i++)
        {
            if(a[uu_tien_nho].do_uu_tien>a[i].do_uu_tien && a[i].tg_denRL<=t && a[i].tg_xuly>0)
            {
                uu_tien_nho=i;
            }
        }
        
        a[uu_tien_nho].tg_xuly=a[uu_tien_nho].tg_xuly-1;
        
        // Khi tien trinh chay xong
        if(a[uu_tien_nho].tg_xuly==0)
        {
            // 1 tien trinh hoan thanh thi tang bien DEM len
            dem++;
            a[uu_tien_nho].tg_cho=t+1-a[uu_tien_nho].tg_denRL-tam[uu_tien_nho];
            a[uu_tien_nho].tg_hoantat=t+1-a[uu_tien_nho].tg_denRL;
            
            // Tinh Tong thoi gian cho vaf Tong thoi gian hoan tat
            TongTG_cho=TongTG_cho+a[uu_tien_nho].tg_cho;
            TongTG_hoantat=TongTG_hoantat+a[uu_tien_nho].tg_hoantat;
            
        }
    }
    
    tg_cho_tb=TongTG_cho/sotientrinh;
    tg_hoantat_tb=TongTG_hoantat/sotientrinh;
    
    // Thuc hien in ket qua
   void red () {        //sử dụng hàm in màu chữ cho text
   printf("\033[0;31m"); //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
      }
      red ();
    printf("Ket qua dinh thoi tien trinh theo DO UU TIEN KHONG DOC QUYEN\n");
    printf("Tien trinh\tTG cho\t\tTG hoan tat\n");
    for(i=0;i<sotientrinh;i++)
    {
        printf("P%d\t\t%d\t\t%d\n",i+1,a[i].tg_cho,a[i].tg_hoantat);
    }
    
    printf("Thoi gian cho trung binh cua cac tien trinh %f\n",tg_cho_tb);
    printf("Thoi gian hoan tat trung binh cua cac tien trinh %f\n",tg_hoantat_tb);
    
    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 các thuật toán: FCFS, SJF, Round Robin và Priority rồi đó. Hẹn gặp các bạn ở bài học tiếp theo.

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

PreviousTIẾN TRÌNH TRONG LINUX NextĐỒNG BỘ

Last updated 1 year ago