C Program for Shortest Job First Scheduling (SJF)

Chiến lược công việc ngắn nhất (Shortest-job-first SJF)

  
Đây là một trường hợp đặc biệt của giải thuật điều phối với độ ưu tiên. Trong giải thuật này, độ ưu tiên p được gán cho mỗi tiến trình là nghịchđảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU được tự do, nó sẽ được cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý.


* Trường hợp độc quyền

*Thời gian xử lý : P1=6,P2=8,P3=4;P4=2
* Thời gian xử lý trung bình : (6+8+4+2)/4=5
*Thời gian đợi : P1=0 p4=5 ; p3=6; p2=9
*Thời gian đợi trung bình: (0+5+6+9)/4=5
* Thời gian lưu lại trong hệ thống : P1=6; P4=2;P3=4;P2=8
* Thời gian lưu lại trung bình: ( 6+2+4+8)/4=5

*Trường hợp không độc quyền:
*Thời gian xử lý : P1=6,P2=8,P3=4;P4=2
* Thời gian xử lý trung bình : (6+8+4+2)/4=5
*Thời gian đợi :
P1=0
P4=2
P1'=3
P3=5
P2=8
*Thời gian đợi trung bình: (0+2+3+5+8)/4=4.5
* Thời gian lưu lại trong hệ thống :
P1 Vòng 1 = 3 vòng 2= 3 khoảng cách giữa 2 vòng =2 => thời gian lưu lại của p1= 3+3+2=8
P4=2
p3=4
P2=8
* Thời gian lưu lại trung bình : (8+2+4+8)/4=5

Code:

#include<stdio.h>

int main()

{

  int time,bt[10],at[10],sum_bt=0,smallest,n,i;

  int sum_turnaround=0,sum_wait=0;

  printf("Enter no of processes : ");

  scanf("%d",&n);

  for(i=0;i<n;i++)

  {

    printf("Enter arrival time for process P%d : ",i+1);

    scanf("%d",&at[i]);

    printf("Enter burst time for process P%d : ",i+1);

    scanf("%d",&bt[i]);

    sum_bt+=bt[i];

  }

  bt[9]=9999;

  printf("\n\nProcess\t|Turnaround Time| Waiting Time\n\n");

  for(time=0;time<sum_bt;)

  {

    smallest=9;

    for(i=0;i<n;i++)

    {

      if(at[i]<=time && bt[i]>0 && bt[i]<bt[smallest])

        smallest=i;

    }

    if(smallest==9)

    {

      time++;

      continue;

    }

    printf("P[%d]\t|\t%d\t|\t%d\n",smallest+1,time+bt[smallest]-at[smallest],time-at[smallest]);

    sum_turnaround+=time+bt[smallest]-at[smallest];

    sum_wait+=time-at[smallest];

    time+=bt[smallest];

    bt[smallest]=0;

  }

  printf("\n\n average waiting time = %f",sum_wait*1.0/n);

  printf("\n\n average turnaround time = %f",sum_turnaround*1.0/n);

  return 0;

}