FCFS and SJF



CPU Scheduling in Operating Systems:
In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU).

The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources.

Various scheduling algorithms are used to achieve these objectives.

First-Come-First-Serve (FCFS) Scheduling:

Definition:
  • FCFS is the simplest CPU scheduling algorithm.
  • It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion.
  • Processes are placed in a queue based on their arrival time.
  • The process that arrives first gets executed first.
Execution Order:
  • Processes are executed in the order they arrive.
  • The process at the front of the queue is selected for execution.
Advantages:
  • Easy to implement.
  • Minimal overhead.
Disadvantages:
  • Often results in long waiting times.
  • Leads to the convoy effect (where a long process holds up other processes).

Shortest Job First (SJF) Scheduling:

Definition:
  • SJF selects the process with the smallest burst time for execution next.
  • It can be either preemptive or non-preemptive.
  • Preemptive SJF is also known as Shortest Remaining Time First (SRTF).
Execution Order:
  • Processes are ordered based on their burst times (ascending order).
  • The process with the shortest burst time is executed first.
Advantages:
  • Minimizes average waiting time.
  • Efficient for minimizing turnaround time.
Disadvantages:
  • Long processes may suffer from starvation (never get executed).
  • Requires knowing burst times in advance (which is often not feasible).
Comparison:
  • FCFS executes processes in arrival order, while SJF prioritizes the shortest job.
  • FCFS leads to lower device and CPU utilization, whereas SJF aims for higher effectiveness by reducing average waiting time.
  • FCFS does not suffer from starvation, but SJF may if long processes are continuously preempted.

In summary, FCFS is straightforward but can lead to inefficiencies, while SJF optimizes waiting time but may cause starvation for longer processes.


Let’s start by creating the Gantt charts for the First-Come-First-Serve (FCFS) and Shortest Job First (SJF) scheduling algorithms based on the given processes, CPU burst times, and arrival times. After that, we’ll compute the average waiting time and average turnaround time for each algorithm.
Table
ProcessBurst TimeArrival Time
P18 ms0 ms
P21 ms1 ms
P33 ms2 ms
P42 ms3 ms
P56 ms4 ms

FCFS (First-Come-First-Serve) Scheduling: 
Arrange the processes in the order of their arrival times. Execute the processes in the order they appear in the queue. 

Gantt Chart for FCFS: 
P1 (0–8 ms)
P2 (8–9 ms)
P3 (9–12 ms)
P4 (12–14 ms)
P5 (14–20 ms)

Turnaround Time (TAT) for each process:
TAT=Completion Time-Arrival Time


TAT(P1) = Completion Time(P1) - Arrival Time(P1) = 8 - 0 = 8 ms
TAT(P2) = 9 - 1 = 8 ms
TAT(P3) = 12 - 2 = 10 ms
TAT(P4) = 14 - 3 = 11 ms
TAT(P5) = 20 - 4 = 16 ms

Average Turnaround Time = (8 + 8 + 10 + 11 + 16) / 5 = 10.6 ms

We can also find TAT using this formula if the waiting time is known
TAT=Waiting Time + Burst Time
TAT(P1)=0+8=8ms
TAT(P2)=7+1=8ms
TAT(P3)=7+3=10ms
TAT(P4)=9+2=11ms
TAT(P5)=10+6=16ms

Waiting Time (WT) for each process:
WT(P1) = TAT(P1) - Burst Time(P1) = 8 - 8 = 0 ms
WT(P2) = 8 - 1 = 7 ms
WT(P3) = 10 - 3 = 7 ms
WT(P4) = 11 - 2 = 9 ms
WT(P5) = 16 - 6 = 10 ms

Average Waiting Time = (0 + 7 + 7 + 9 + 10) / 5 = 6.6 ms

We can also find the waiting time recursively
WT(P1)=0
WT(P2)=ArrivalTime(P1)+WT(P1)+BurstTime(P1)-ArrivalTime(P2)=0+0+8-1=7ms
WT(P3)=ArrivalTime(P2)+WT(P2)+BurstTime(P2)-ArrivalTime(P3)=1+7+1-2=7ms
WT(P4)=ArrivalTime(P3)+WT(P3)+BurstTime(P3)-ArrivalTime(P4)=2+7+3-3=9ms
WT(P5)=ArrivalTime(P4)+WT(P4)+BurstTime(P4)-ArrivalTime(P5)=3+9+2-4=10ms

//****************************************************************************//
// C Program Implementation of FCFS Scheduling
//****************************************************************************//
#include <stdio.h>

void findWaitingTime(int processes[], int n, int bt[], int wt[],int at[]) {
    wt[0] = 0;
    for (int i = 1; i < n; i++)
        wt[i] = at[i-1]+ wt[i - 1]+bt[i - 1] -at[i];
}

void findTurnAroundTime(int processes[], int n, int bt[], int wt[],int at[], int tat[]) {
    for (int i = 0; i < n; i++)
        tat[i] = wt[i]+bt[i];
}

void findAvgTime(int processes[], int n, int bt[], int at[]) {
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
    findWaitingTime(processes, n, bt, wt,at);
    findTurnAroundTime(processes, n, bt, wt,at, tat);

    printf("Processes\tArrival time\tBurst time\tWaiting time\tTurnaround time\n");
    for (int i = 0; i < n; i++) {
        total_wt += wt[i];
        total_tat += tat[i];
        printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i + 1, at[i],bt[i], wt[i], tat[i]);
    }

    printf("Average waiting time = %.2f\n", (float)total_wt / n);
    printf("Average turnaround time = %.2f\n", (float)total_tat / n);
}

int main() {
    int processes[] = {1, 2, 3,4,5};
    int n = sizeof(processes) / sizeof(processes[0]);
    int burst_time[] = {8,1,3,2,6};
    int arrival_time[] = {0,1,2,3,4};

    findAvgTime(processes, n, burst_time, arrival_time);
    return 0;
}
Output:
Processes       Arrival time    Burst time      Waiting time    Turnaround time
1                           0                   8                       0                   8
2                           1                   1                       7                   8
3                           2                   3                       7                   10
4                           3                   2                       9                   11
5                           4                   6                       10                 16
Average waiting time = 6.60
Average turnaround time = 10.60

An alternate and efficient implementation with structures

 #include <stdio.h>

// Structure to represent a process
typedef struct {
    int name;      // Process name (1, 2, 3, ...)
    int arrival;    // Arrival time
    int burst;      // Burst time
    int completion; //Completion time
    int waiting; //waiting time
    int turnaround; //turn around time
   
} Process;

int main() {
    // Define the processes
    Process processes[] = {
        {1, 0,8},  // Arrival time = 0, Burst time = 8
        {2, 1,1},  // Arrival time = 1, Burst time = 1
        {3, 2,3},  // Arrival time = 2, Burst time = 3
        {4, 3,2},// Arrival time = 3, Burst time = 2
        {5, 4,6} // Arrival time = 4, Burst time = 6
    };
    int n = sizeof(processes) / sizeof(Process); // Number of processes

       // Initialize variables
    int currenttime = 0;


    printf("Time  |  Process\n");
    printf("------+-------------------\n");

    
        // Iterate through each process
        for (int i = 0; i < n; i++) {
            // Check if the process has arrived and is not yet completed
               int execution_time = processes[i].burst;
          
                currenttime += execution_time;

                // Print the execution
                printf("%-5d |  P%d\n", currenttime, processes[i].name);
                processes[i].completion=currenttime;
                processes[i].turnaround=processes[i].completion-processes[i].arrival;
                processes[i].waiting=processes[i].turnaround-processes[i].burst;
           
        }

   float avgwt=0.0;
   float avgtat=0.0;
   printf("Process  ArrivalTime BurstTime TurnaroundTime    WaitingTime\n");
   for(int i=0;i<n;i++)
   {
       printf("P%d%10d%10d%15d%20d\n",processes[i].name,processes[i].arrival,processes[i].burst,processes[i].turnaround,processes[i].waiting);
       avgwt=avgwt+processes[i].waiting;
       avgtat=avgtat+processes[i].turnaround;
   }
printf("Average Waiting Time=%f\n",avgwt/n);
printf("Average turnaround Time=%f\n",avgtat/n);


    return 0;
}

 Time  |  Process
------+-------------------
8     |  P1
9     |  P2
12    |  P3
14    |  P4
20    |  P5
Process  ArrivalTime BurstTime TurnaroundTime    WaitingTime
P1         0         8              8                   0
P2         1         1              8                   7
P3         2         3             10                   7
P4         3         2             11                   9
P5         4         6             16                  10
Average Waiting Time=6.600000
Average turnaround Time=10.600000
 
 
SJF (Shortest Job First) Scheduling: ( Non Preemptive)
Lets consider all job arrive at time 0
Process     Burst Time
P1            8ms
P2            1ms
P3            3ms
P4            2ms
P5            6ms
Gantt Chart:
P2 (0-1ms)
P4 (1–3 ms)
P3 (3–6 ms)
P5 (6–12 ms)
P1 (12–20 ms)
Waiting Time (WT):
WT(P2)=0
WT(P4)=WT(P2)+Burst Time(P2) etc
P2: 0 ms
P4: 1 ms
P3: 3 ms
P5: 6 ms
P1: 12 ms
Average WT: (0 + 1+ 3 + 6 + 12) / 5 = 4.4 ms
Turnaround Time (TAT):
TAT=WT+Burst Time
P2:0+1= 1 ms
P4: 1+2=3 ms
P3: 3+3=6 ms
P5: 6+6=12 ms
P1: 12+8=20 ms
Average TAT: (1 + 3 + 6 + 12 + 20) / 5 = 8.4 ms

The SJF algorithm results in the minimum average waiting time among all other scheduling algorithms.
//**********************************************************
//C program SJF Non Preemptive  Scheduling
//**********************************************************
#include <stdio.h>
#include <stdbool.h>

// Structure to represent a process
struct Process {
    int pid; // Process ID
    int arrival_time; // Arrival time
    int burst_time; // Burst time
};

// Function to sort processes based on burst time
void sortProcesses(struct Process processes[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (processes[j].burst_time > processes[j + 1].burst_time) {
                // Swap processes[j] and processes[j + 1]
                struct Process temp = processes[j];
                processes[j] = processes[j + 1];
                processes[j + 1] = temp;
            }
        }
    }
}

// Function to calculate waiting time and turnaround time
void calculateTimes(struct Process processes[], int n, int wt[], int tat[]) {
    wt[0] = 0;
    tat[0]=wt[0]+processes[0].burst_time;
    for (int i = 1; i < n; i++) {
        wt[i] = wt[i - 1] + processes[i - 1].burst_time;
        tat[i] = wt[i] + processes[i].burst_time;
    }
}

// Function to calculate average waiting time and turnaround time
void calculateAvgTimes(struct Process processes[], int n) {
    int wt[n], tat[n];
    calculateTimes(processes, n, wt, tat);

    float avg_wt = 0, avg_tat = 0;
    printf("PID \tWT \tTAT\n");
    for (int i = 0; i < n; i++) {
        avg_wt += wt[i];
        avg_tat += tat[i];
        printf("%d\t %d\t %d\n",processes[i].pid,wt[i],tat[i]);
    }

    printf("Average waiting time = %.2f\n", avg_wt / n);
    printf("Average turnaround time = %.2f\n", avg_tat / n);
}

int main() {
    int n = 5; // Number of processes
    struct Process processes[] = {
        {1, 0, 8},
        {2, 1, 1},
        {3, 2, 3},
        {4, 3, 2},
        {5, 4, 6}
    };

    // Sort processes based on burst time
    sortProcesses(processes, n);
        // Calculate average waiting time and turnaround time
    calculateAvgTimes(processes, n);

    return 0;
}
Output:
PID     WT      TAT
2            0       1
4            1       3
3            3       6
5            6       12
1            12      20
Average waiting time = 4.40
Average turnaround time = 8.40
 
 

SJF (Shortest Job First) Scheduling: ( Preemptive)

Gantt Chart:
P1 (0-1ms)   7 remaining
P2 (1–2 ms)   completed P2
P3 (2–3 ms)  2 remaining
P4 (3–5 ms)  completed P4
P3(5-7 ms)   completed P3
P5 (7–13 ms) completed P5
P1 (13–20 ms) completed P1

Turnaround Time (TAT):
P1: 20 ms
P2: 1 ms
P3: 3 ms
P4: 4 ms
P5: 9 ms
Average TAT: (20 + 1 + 3 + 4 + 9) / 5 = 7.4 ms

Waiting Time (WT):
P1: 12 ms
P2: 0 ms
P3: 2 ms
P4: 0 ms
P5: 3 ms
Average WT: (12 + 0 + 2 + 0 + 3) / 5 =  3.4 ms

//******************************************************************
// C Program SJF Preemptive scheduling
//******************************************************************
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

// Structure to represent a process
struct Process {
    int pid; // Process ID
    int arrival_time; // Arrival time
    int burst_time; // Burst time
};

// Function to find the process with the shortest remaining burst time
int findShortestJob(struct Process processes[], int n, int current_time,int rt[]) {
    int shortest_job = -1;
    int min_burst_time = INT_MAX;

    for (int i = 0; i <n; i++) {
        if (processes[i].arrival_time <= current_time && processes[i].burst_time <= min_burst_time && rt[i]!=0) {
            min_burst_time = processes[i].burst_time;
            shortest_job = i;
        }
    }

    return shortest_job;
}

// Function to calculate waiting time and turnaround time
void calculateTimes(struct Process processes[], int n, int wt[], int tat[]) {
    int remaining_time[n];
    for (int i = 0; i < n; i++)
        remaining_time[i] = processes[i].burst_time;

    int completed = 0;
    int current_time = 0;
  int shortest_jobs[50];
  int i=0;
    while (completed < n) {
        int shortest_job = findShortestJob(processes, n, current_time,remaining_time);
        printf("Executing P%d\n",shortest_job); 
        shortest_jobs[i++]=shortest_job;
        if (shortest_job == -1) {
            current_time++;
            continue;
        }

        //if (remaining_time[shortest_job] == processes[shortest_job].burst_time)
        //    {wt[shortest_job] = current_time - processes[shortest_job].arrival_time;}

        remaining_time[shortest_job]--;
        current_time++;

        if (remaining_time[shortest_job] == 0) {
            tat[shortest_job] = current_time - processes[shortest_job].arrival_time;
            wt[shortest_job]=tat[shortest_job]-processes[shortest_job].burst_time;
            completed++;
        }
      
    }
}

// Function to calculate average waiting time and turnaround time
void calculateAvgTimes(struct Process processes[], int n) {
    int wt[n], tat[n];
    calculateTimes(processes, n, wt, tat);
    printf("WT \t TAT\n");
   for(int i=0;i<n;i++)
     printf("%d\t %d\n",wt[i],tat[i]);
    float avg_wt = 0, avg_tat = 0;
    for (int i = 0; i < n; i++) {
        avg_wt += wt[i];
        avg_tat += tat[i];
    }

    printf("Average waiting time = %.2f\n", avg_wt / n);
    printf("Average turnaround time = %.2f\n", avg_tat / n);
}

int main() {
    int n = 5; // Number of processes
    struct Process processes[] = {
        {1, 0, 8},
        {2, 1, 1},
        {3, 2, 3},
        {4, 3, 2},
        {5, 4, 6}
    };

    // Calculate average waiting time and turnaround time
    calculateAvgTimes(processes, n);

    return 0;
}
output:
Executing P0
Executing P1
Executing P2
Executing P3
Executing P3
Executing P2
Executing P2
Executing P4
Executing P4
Executing P4
Executing P4
Executing P4
Executing P4
Executing P0
Executing P0
Executing P0
Executing P0
Executing P0
Executing P0
Executing P0
WT       TAT
12       20
0        1
2        5
0        2
3        9
Average waiting time = 3.40
Average turnaround time = 7.40

Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn.         Familiarization of Basic  Linux Commands- ls, mkdir, rmdir , rm, cat, cp, mv , chmod          User and Group management- useradd, userdel,groupadd,groupdel, passwd           Familiarization of basic  ...
Read more

Banker's Algorithm- Deadlock Detection

The Banker's Algorithm is a deadlock avoidance algorithm used in operating systems to prevent deadlocks in a system with limited resources. It was developed by Edsger Dijkstra in 1965. The algorithm ensures that the system will allocate resources in such a way that it will avoid deadlock, even if resources are requested in an arbitrary order. Let's break down the Banker's Algorithm into steps: 1. System Initialization: At the beginning, the system must know the total number of resources of each type and the maximum demand of each process. It also needs to keep track of the currently available resources of each type. 2. Allocation: When a process requests resources, the system must check if granting those resources would put it in an unsafe state (i.e., could potentially lead to a deadlock). If the request can be granted without causing an unsafe state, the resources are allocated. Otherwise, the process must wait until the requested resources can be safely allocated. Safety...
Read more