C++ Program for FCFS Scheduling Algorithm

Introduction

In this lab, we will implement the First Come First Serve (FCFS) Scheduling Algorithm using C++. FCFS is the simplest CPU scheduling algorithm that allocates the CPU to processes in the order they request it. The process that arrives first in the ready queue is served first.

This algorithm is easy to understand and implement but may not provide optimal performance in terms of average waiting time. By the end of this lab, you will understand how the FCFS algorithm works and be able to calculate important metrics like waiting time and turnaround time for processes.

Understanding FCFS and Creating the Program Structure

First Come First Serve (FCFS) is a non-preemptive scheduling algorithm where processes are executed in the order they arrive in the ready queue. In this step, we will create our program file and set up the basic structure.

Let's start by creating a new C++ file:

1. Open the WebIDE interface and navigate to the file explorer panel
2. Right-click in the explorer panel and select "New File"
3. Name the file fcfs.cpp and press Enter

Now, let's add the necessary header files and namespace declaration to our program:

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

This code sets up the basic structure of our program with:

• #include <iostream> - For input/output operations
• #include <iomanip> - For formatting the output table
• using namespace std; - To use the standard namespace
• A main() function with a title display

Let's compile and run the program to ensure everything is set up correctly:

g++ fcfs.cpp -o fcfs
./fcfs

You should see the following output:

FCFS Scheduling Algorithm Implementation
----------------------------------------

This confirms that our basic program structure is working correctly. In the next step, we'll implement the functionality to input process details.

Implementing Process Input Functionality

In this step, we'll implement the functionality to collect information about the processes to be scheduled. For FCFS scheduling, we need to know:

1. The number of processes
2. The burst time for each process (execution time required by each process)

Let's modify our fcfs.cpp file to include this functionality:

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                  // Number of processes
    int burst_time[20];     // Array to store burst time of each process

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Display the entered data
    cout << "\nProcess\tBurst Time" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

Let's go through what we've added:

1. Variables to store the number of processes (n) and the burst time for each process (burst_time[20]).
2. Input prompts to collect the number of processes and the burst time for each process.
3. Input validation to ensure the number of processes is within a reasonable range (1-20) and burst times are positive.
4. A table display to show the entered data for verification.

Let's compile and run our updated program:

g++ fcfs.cpp -o fcfs
./fcfs

When you run the program, you'll be prompted to enter the number of processes and their burst times. Try entering the following data:

3
5
9
4

This represents 3 processes with burst times of 5, 9, and 4 time units respectively. You should see output similar to:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time
--------------------
P1      5
P2      9
P3      4

This confirms that our input functionality is working correctly. In the next step, we'll calculate the waiting time and turnaround time for each process.

Calculating Waiting Time and Turnaround Time

In this step, we'll calculate two important metrics for each process:

1. Waiting Time (WT): The time a process waits in the ready queue before getting CPU time.
2. Turnaround Time (TAT): The total time taken from process submission to completion.

Let's understand how these are calculated in FCFS:

• For the first process (P1), the waiting time is always 0 (it starts immediately).
• For subsequent processes, the waiting time is the sum of burst times of all previous processes.
• The turnaround time for each process is the sum of its burst time and waiting time.

Now, let's modify our fcfs.cpp file to add these calculations:

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    return 0;
}

Let's understand what we've added:

1. Two new arrays: waiting_time[20] and turnaround_time[20] to store the waiting and turnaround times for each process.
2. Variables to track the total waiting time and total turnaround time.
3. Calculations for waiting time:
   • The first process has a waiting time of 0.
   • For each subsequent process, the waiting time is the sum of burst times of all previous processes.
4. Calculations for turnaround time:
   • For each process, turnaround time = burst time + waiting time.
5. A formatted table to display the results.

Let's compile and run our updated program:

g++ fcfs.cpp -o fcfs
./fcfs

Try entering the same data as before:

3
5
9
4

You should see output similar to:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Let's analyze the results:

• P1: Waiting time = 0, Turnaround time = 5 (its burst time)
• P2: Waiting time = 5 (P1's burst time), Turnaround time = 14 (5 + 9)
• P3: Waiting time = 14 (P1 + P2's burst times), Turnaround time = 18 (14 + 4)

This confirms our waiting time and turnaround time calculations are working correctly. In the next step, we'll calculate the average times and display the final results.

Calculating Average Times and Displaying Final Results

In this final step, we'll calculate the average waiting time and average turnaround time for all processes. These averages are important metrics to evaluate the efficiency of a scheduling algorithm.

Let's modify our fcfs.cpp file to add these calculations and complete our program:

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    // Calculate average waiting time and average turnaround time
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Display the results with two decimal places
    cout << fixed << setprecision(2);
    cout << "\nAverage Waiting Time: " << avg_waiting_time << " time units" << endl;
    cout << "Average Turnaround Time: " << avg_turnaround_time << " time units" << endl;

    // Visual representation of the FCFS schedule (Gantt chart in text)
    cout << "\nGantt Chart:" << endl;
    cout << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }
    cout << endl << "|";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "P" << i + 1;
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "|";
    }

    cout << endl << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }

    cout << endl;
    cout << "0";
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += burst_time[i];
        for (int j = 0; j < burst_time[i] * 2 - 1; j++) {
            cout << " ";
        }
        if (current_time < 10) cout << " ";
        cout << current_time;
    }
    cout << endl;

    return 0;
}

Let's understand what we've added:

1. Two new variables: avg_waiting_time and avg_turnaround_time to store the average times.
2. Calculations for the average times:
   • Average waiting time = Total waiting time / Number of processes
   • Average turnaround time = Total turnaround time / Number of processes
3. Formatted output to display the average times with two decimal places.
4. A simple text-based Gantt chart to visualize the FCFS schedule:
   • Each process is represented by its ID (P1, P2, etc.)
   • The width of each process block is proportional to its burst time
   • Time markers are shown at the bottom

Let's compile and run our final program:

g++ fcfs.cpp -o fcfs
./fcfs

Try entering the same data as before:

3
5
9
4

You should see output similar to:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Average Waiting Time: 6.33 time units
Average Turnaround Time: 12.33 time units

Gantt Chart:
 --------------------
|   P1    |    P2    |  P3  |
 --------------------
0         5         14     18

Looking at the results:

• Average Waiting Time: (0 + 5 + 14) / 3 = 6.33 time units
• Average Turnaround Time: (5 + 14 + 18) / 3 = 12.33 time units

The Gantt chart visually represents how the processes are scheduled over time:

• P1 runs from time 0 to 5
• P2 runs from time 5 to 14
• P3 runs from time 14 to 18

This completes our implementation of the FCFS scheduling algorithm. You can experiment with different numbers of processes and burst times to see how it affects the average waiting time and turnaround time.

Summary

In this lab, we have successfully implemented the First Come First Serve (FCFS) CPU scheduling algorithm using C++. Here are the key concepts and skills you have learned:

1. FCFS Algorithm Basics: Understanding how processes are scheduled in the order they arrive.

2. Performance Metrics Calculation:

   • Waiting Time: The time a process waits before execution begins
   • Turnaround Time: The total time from submission to completion
   • Average Waiting Time and Average Turnaround Time: Key performance indicators for scheduling algorithms

3. C++ Programming Concepts:

   • Arrays to store process information
   • Loops for iterative calculations
   • Input/output operations with validation
   • Formatted output for better data presentation

4. Visualization Techniques: Creating a text-based Gantt chart to visualize the scheduling timeline

The FCFS algorithm is simple to understand and implement but may not always provide optimal performance. It can lead to the "convoy effect" where short processes get stuck waiting behind long processes, increasing average waiting time.

This implementation serves as a foundation for understanding more complex scheduling algorithms like Shortest Job First (SJF), Priority Scheduling, and Round Robin (RR) that aim to optimize different aspects of process scheduling.