Operating Systems -Scheduling Algorithms Made Easy : FCFS

#computerscience #cpuscheduling #codenewbie

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.

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;

<span class="p">}</span>
<span class="c1">//display all processes and details</span>
<span class="n">printf</span> <span class="p">(</span><span class="s">"PN</span><span class="se">\t</span><span class="s">BT</span><span class="se">\t</span><span class="s">WT</span><span class="se">\t</span><span class="s">TAT</span><span class="se">\n</span><span class="s">"</span><span class="p">);</span>
<span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//compute sum of waiting time and turnaround time</span>
    <span class="n">sum1</span> <span class="o">+=</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">wt</span><span class="p">;</span>
    <span class="n">sum2</span> <span class="o">+=</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">tat</span><span class="p">;</span>
    <span class="n">printf</span> <span class="p">(</span><span class="s">"%d</span><span class="se">\t</span><span class="s">%d</span><span class="se">\t</span><span class="s">%d</span><span class="se">\t</span><span class="s">%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="o">*</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">pn</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">bt</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">wt</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">tat</span><span class="p">);</span>
<span class="p">}</span>
<span class="c1">// calculate average waiting time and turnaround time</span>
<span class="n">avg1</span> <span class="o">=</span> <span class="p">(</span><span class="kt">float</span><span class="p">)</span> <span class="n">sum1</span> <span class="o">/</span> <span class="n">n</span><span class="p">;</span>
<span class="n">avg2</span> <span class="o">=</span> <span class="p">(</span><span class="kt">float</span><span class="p">)</span> <span class="n">sum2</span> <span class="o">/</span> <span class="n">n</span><span class="p">;</span>
<span class="n">printf</span> <span class="p">(</span><span class="s">"Average waiting time = %.2f</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">avg1</span><span class="p">);</span>
<span class="n">printf</span> <span class="p">(</span><span class="s">"Average turnaround time = %.2f</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">avg2</span><span class="p">);</span>
<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>



    

    




}

Sample Input and Output

Input:



Enter number of processes:


3


Enter processes and burst times:


1 24


2 3


3 3

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