C语言FCFS调度程序


假设我们有n个进程,即P1、P2、P3、……、Pn及其对应的突发时间。任务是使用先来先服务(FCFS) CPU调度算法找到平均等待时间和平均周转时间。

什么是等待时间和周转时间?

  • 周转时间是进程提交和完成之间的时间间隔。

    周转时间 = 进程完成时间 – 进程提交时间

  • 等待时间是周转时间和突发时间之差

    等待时间 = 周转时间 – 突发时间

什么是FCFS调度?

先来先服务(FCFS),也称为先进先出(FIFO),是一种CPU调度算法,其中CPU按照进程在就绪队列中排队的顺序分配给进程。

FCFS遵循非抢占式调度,这意味着一旦CPU分配给一个进程,它就不会离开CPU,直到进程终止或由于某些I/O中断而暂停。

示例

假设有四个进程按照P2、P3、P1的顺序到达,它们对应的执行时间如下表所示。此外,假设它们的到达时间为0。

进程到达顺序执行时间(毫秒)
P1315
P213
P323

甘特图显示系统中进程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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

算法

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 
"
);    // 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
"
, i+1, burst_time[i], wait_time[i], tat[i]);    }    printf("Average waiting time = %f
"
, (float)total_wt / (float)n);    printf("Average turn around time = %f
"
, (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

更新于:2023年9月2日

49K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告