DEV Community

loading...

Operating Systems -Scheduling Algorithms Made Easy : FCFS

nagasaisriya profile image code_bts ・3 min read

Introduction

First come first served (FCFS) is the simplest operating system scheduling algorithm which supports both preemptive and non-preemptive scheduling, implemented with a FIFO queue. It automatically executes queued requests and processes them by order of their arrival,the processes which requests the CPU first get the CPU allocation first.

Explanation

First in first out (FIFO) simply queues processes in the order that they arrive in the ready queue. For managing the tasks, as the processes come they are kept at the end of the queue. As CPU finishes each task, it removes it from the start of the queue and heads onto the next task.

FCFS

  • From the above Gantt chart, if the processes arrive in the order P1,P2,P3, and are served in FCFS order,we get the result shown above. The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2, and 27 milliseconds for process P3. Thus, the average waiting time is (0+ 24 + 27)/3 = 17 milliseconds.

  • Advantage:

    • The code for FCFS scheduling is simple to write and understand.
  • Disadvantages:

    • The process will run to the completion and there are high chances of starvation, as it is non preemtive.
    • There is a convoy effect as all the other processes wait for the one big process to get off the CPU. This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.
    • It is poor in performance since the average waiting time is higher as compared to other scheduling algorithms.

Algorithm

Non-preemptive scheduling without arrival time:

  • Firstly, take inputs as number of processes n, processes pn, and burst times bt.
  • Find the waiting time wt for all processes.
  • The first process has no waiting time so waiting time for process 1 will be 0 i.e. wt[0] = 0.
  • Find waiting time for all other processes i.e. for
    • process i -> wt[i] = bt[i-1] + wt[i-1] .
  • Calculate the turnaround time, it is given as tat= wt + bt for all processes.
    • Compute sum of waiting time and turnaround times,
      • Sum of waiting time, sum1 = sum1 + wt[i]
      • Sum of turnaround time, sum2 = sum2 + tat[i]
    • Calculate average waiting time, avg1 = sum1 / n.
    • Similarly, find average turnaround time, avg2 = sum2 / n.

Code

  • This is my code implemented in C++
#include <iostream>
using namespace std;

int main ()
{
    struct fcfs
    {
        int pn[100];
        int bt, wt, tat;
    } b[100];
    int sum1 = 0, sum2 = 0, i, n;
    float avg1 = 0, avg2 = 0;
    printf ("Enter number of processes:\n");
    scanf ("%d", &n);
    printf ("Enter processes and burst times:\n");
    for (i = 0; i < n; i++)
    {
        scanf ("%d", b[i].pn);
        scanf ("%d", &b[i].bt);
    }
    b[0].wt = 0;
    for (i = 0; i < n; i++)
    {
        b[i + 1].wt = b[i].bt + b[i].wt;
        b[i].tat = b[i].wt + b[i].bt;

    }
    //display all processes and details
    printf ("PN\tBT\tWT\tTAT\n");
    for (i = 0; i < n; i++)
    {
        //compute sum of waiting time and turnaround time
        sum1 += b[i].wt;
        sum2 += b[i].tat;
        printf ("%d\t%d\t%d\t%d\n", *b[i].pn, b[i].bt, b[i].wt, b[i].tat);
    }
    // calculate average waiting time and turnaround time
    avg1 = (float) sum1 / n;
    avg2 = (float) sum2 / n;
    printf ("Average waiting time = %.2f\n", avg1);
    printf ("Average turnaround time = %.2f\n", avg2);
    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Sample Input and Output

Input:

Enter number of processes:                                                                                                                    
3                                                                                                                                             
Enter processes and burst times:                                                                                                              
1 24                                                                                                                                          
2 3                                                                                                                                           
3 3 
Enter fullscreen mode Exit fullscreen mode

Output:

PN      BT      WT      TAT                                                                                                                   
1       24      0       24                                                                                                                    
2       3       24      27                                                                                                                    
3       3       27      30                                                                                                                    
Average waiting time = 17.00                                                                                                                  
Average turn around time = 27.00 
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

  • Time Complexity:

    • Best Case : O(n)
    • Average Case : O(n2)
    • Worst Case : O(n2)
  • Space Complexity : O(1)

Discussion (2)

Collapse
davidesp profile image
David-Esp

FCFS is always easy! Maybe SJF non preemptve ... Can be a little bit of challenge !

Collapse
nagasaisriya profile image
code_bts Author

True!!I'll surely try to write SRTF(SJF non preemptive) article soon :)

Forem Open with the Forem app