C Chương trình lập lịch FCFS

Chúng tôi được cung cấp với số lượng n quá trình, tức là P1, P2, P3, ......., Pn và thời gian bùng nổ tương ứng của chúng. Nhiệm vụ là tìm thời gian chờ trung bình và thời gian quay vòng trung bình bằng cách sử dụng thuật toán Lập lịch CPU FCFS.

Thời gian chờ và thời gian quay vòng là gì?

• Thời gian quay vòng là khoảng thời gian từ khi gửi quy trình đến khi hoàn thành quy trình.

  Thời gian quay vòng =hoàn thành quy trình - gửi quy trình

• Thời gian chờ là sự khác biệt giữa thời gian quay vòng và thời gian liên tục

  Thời gian chờ =thời gian quay vòng - thời gian liên tục

Lập lịch FCFS là gì?

First Come, First Served (FCFS) còn được gọi là First In, First Out (FIFO) là thuật toán lập lịch trình CPU trong đó CPU được phân bổ cho các quá trình theo thứ tự chúng được xếp vào hàng đợi sẵn sàng.

FCFS tuân theo lập lịch không ưu tiên có nghĩa là khi CPU được cấp phát cho một quá trình, nó sẽ không rời khỏi CPU cho đến khi quá trình đó không bị kết thúc hoặc có thể bị tạm dừng do một số ngắt I / O.

Ví dụ

Giả sử, có bốn quy trình đến trong chuỗi là P2, P3, P1 với thời gian thực thi tương ứng của chúng như được hiển thị trong bảng bên dưới. Ngoài ra, thời gian đến của họ là 0.

Biểu đồ Gantt hiển thị thời gian chờ của các quá trình P1, P2 và P3 trong hệ thống

Như hình trên,

Thời gian chờ của quy trình P2 là 0

Thời gian chờ của quy trình P3 là 3

Thời gian chờ của quy trình P1 là 6

Thời gian trung bình =(0 + 3 + 6) / 3 =3 mili giây.

Vì chúng tôi đã đưa thời gian đến bằng 0 nên thời gian quay vòng và thời gian hoàn thành sẽ giống nhau.

Ví dụ

Input-:  processes = P1, P2, P3
        Burst time = 5, 8, 12
Output-:
Processes  Burst    Waiting    Turn around
1          5        0           5
2          8        5           13
3          12       13          25
Average Waiting time = 6.000000
Average turn around time = 14.333333

Thuật toán

Start                                                                                                     Step 1-> In function int waitingtime(int proc[], int n, int burst_time[], int wait_time[])
   Set wait_time[0] = 0
   Loop For i = 1 and i < n and i++
      Set wait_time[i] = burst_time[i-1] + wait_time[i-1]
   End For
Step 2-> In function int turnaroundtime( int proc[], int n, int burst_time[], int wait_time[], int tat[])
   Loop For  i = 0 and i < n and i++
      Set tat[i] = burst_time[i] + wait_time[i]
   End For
Step 3-> In function int avgtime( int proc[], int n, int burst_time[])
   Declare and initialize wait_time[n], tat[n], total_wt = 0, total_tat = 0;
   Call waitingtime(proc, n, burst_time, wait_time)
   Call turnaroundtime(proc, n, burst_time, wait_time, tat)
   Loop For  i=0 and i<n and i++
      Set total_wt = total_wt + wait_time[i]
      Set total_tat = total_tat + tat[i]
      Print process number, burstime wait time and turnaround time
   End For
   Print "Average waiting time =i.e. total_wt / n
   Print "Average turn around time = i.e. total_tat / n
Step 4-> In int main()
   Declare the input int proc[] = { 1, 2, 3}
   Declare and initialize n = sizeof proc / sizeof proc[0]
   Declare and initialize burst_time[] = {10, 5, 8}
   Call avgtime(proc, n, burst_time)
Stop

Ví dụ

#include <stdio.h>
// Function to find the waiting time for all processes
int waitingtime(int proc[], int n,
int burst_time[], int wait_time[]) {
   // waiting time for first process is 0
   wait_time[0] = 0;
   // calculating waiting time
   for (int i = 1; i < n ; i++ )
   wait_time[i] = burst_time[i-1] + wait_time[i-1] ;
   return 0;
}
// Function to calculate turn around time
int turnaroundtime( int proc[], int n,
int burst_time[], int wait_time[], int tat[]) {
   // calculating turnaround time by adding
   // burst_time[i] + wait_time[i]
   int i;
   for ( i = 0; i < n ; i++)
   tat[i] = burst_time[i] + wait_time[i];
   return 0;
}
//Function to calculate average time
int avgtime( int proc[], int n, int burst_time[]) {
   int wait_time[n], tat[n], total_wt = 0, total_tat = 0;
   int i;
   //Function to find waiting time of all processes
   waitingtime(proc, n, burst_time, wait_time);
   //Function to find turn around time for all processes
   turnaroundtime(proc, n, burst_time, wait_time, tat);
   //Display processes along with all details
   printf("Processes  Burst   Waiting Turn around \n");
   // Calculate total waiting time and total turn
   // around time
   for ( i=0; i<n; i++) {
      total_wt = total_wt + wait_time[i];
      total_tat = total_tat + tat[i];
      printf(" %d\t  %d\t\t %d \t%d\n", i+1, burst_time[i], wait_time[i], tat[i]);
   }
   printf("Average waiting time = %f\n", (float)total_wt / (float)n);
   printf("Average turn around time = %f\n", (float)total_tat / (float)n);
   return 0;
}
// main function
int main() {
   //process id's
   int proc[] = { 1, 2, 3};
   int n = sizeof proc / sizeof proc[0];
   //Burst time of all processes
   int burst_time[] = {5, 8, 12};
   avgtime(proc, n, burst_time);
   return 0;
}

Đầu ra

Processes  Burst    Waiting    Turn around
1          5        0           5
2          8        5           13
3          12       13          25
Average Waiting time = 6.000000
Average turn around time = 14.333333