โปรแกรม C สำหรับ FCFS Scheduling

เราได้รับจำนวน n กระบวนการ เช่น P1, P2, P3,.......,Pn และเวลาระเบิดที่เกี่ยวข้องกัน งานคือการค้นหาเวลารอโดยเฉลี่ยและเวลาตอบสนองโดยเฉลี่ยโดยใช้อัลกอริทึม FCFS CPU Scheduling

เวลารอและเวลาตอบสนองคืออะไร

• เวลาตอบสนองคือช่วงเวลาระหว่างการส่งกระบวนการและเสร็จสิ้น

  เวลาดำเนินการ =เสร็จสิ้นกระบวนการ – การส่งกระบวนการ

• เวลารอคือความแตกต่างระหว่างเวลาตอบสนองกับเวลาที่ระเบิด

  เวลารอ =เวลาตอบสนอง – เวลาที่ระเบิด

กำหนดการ FCFS คืออะไร

First Come, First Served (FCFS) หรือที่รู้จักในชื่อ First In, First Out (FIFO) คืออัลกอริธึมการตั้งเวลา CPU ซึ่ง CPU จะถูกจัดสรรให้กับกระบวนการตามลำดับที่เข้าคิวในคิวที่พร้อม

FCFS ทำตามการตั้งเวลาแบบไม่ยึดเอาเสียก่อน ซึ่งหมายความว่าเมื่อ CPU ถูกจัดสรรให้กับกระบวนการ จะไม่ออกจาก CPU จนกว่ากระบวนการจะไม่ถูกยกเลิกหรืออาจหยุดทำงานเนื่องจากการขัดจังหวะ I/O บางอย่าง

ตัวอย่าง

สมมติว่ามีสี่กระบวนการที่มาถึงตามลำดับคือ P2, P3, P1 พร้อมเวลาดำเนินการที่เกี่ยวข้องดังแสดงในตารางด้านล่าง อีกทั้งใช้เวลามาถึงเป็น 0

แผนภูมิแกนต์แสดงเวลารอของกระบวนการ P1, P2 และ P3 ในระบบ

ดังที่แสดงไว้ข้างต้น

เวลารอของกระบวนการ P2 คือ 0

ระยะเวลารอของกระบวนการ P3 คือ 3

เวลารอของกระบวนการ P1 คือ 6

เวลาเฉลี่ย =(0 + 3 + 6) / 3 =3 มิลลิวินาที

เนื่องจากเราใช้เวลาในการมาถึงเป็น 0 เวลาจึงหมุนรอบและเวลาเสร็จจะเท่ากัน

ตัวอย่าง

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

อัลกอริทึม

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

ตัวอย่าง

#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;
}

ผลลัพธ์

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