FCFS First Come First Serve - CPU Scheduling

 

FCFS (First Come First Served) 

CPU SCHEDULING

---

1. AIM

To input a list of processes with their arrival times and burst times, simulate the FCFS CPU Scheduling Algorithm, and compute:

• Completion Time

• Turnaround Time

• Waiting Time

• Average Waiting Time

---

2. THEORY

CPU Scheduling

CPU scheduling determines the order of execution of processes in a ready queue.

FCFS Scheduling (Non-Preemptive)

• FCFS executes processes in the order of arrival.

• The process that comes first gets the CPU first.

• It is simple but suffers from convoy effect.

Important Performance Metrics

1. Completion Time (CT)
   Time at which a process finishes execution.

2. Turnaround Time (TAT)

   $$TAT=CT-ArrivalTime$$

3. Waiting Time (WT)

   $$WT=TAT-BurstTime$$

---

3. ALGORITHM

1. Input the number of processes n.

2. Input each process's:

   • Process ID

   • Arrival Time

   • Burst Time

3. Sort processes in ascending order of arrival time.

4. For each process:

   • If CPU is idle, start at arrival time

   • Compute Completion Time

   • Compute Turnaround Time

   • Compute Waiting Time

5. Compute average waiting time.

6. Display the scheduling table.

---

4. PROGRAM (C Program for FCFS Scheduling)

#include <stdio.h>

struct Process {
    int pid;
    int arrival;
    int burst;
    int completion;
    int turnaround;
    int waiting;
};

int main() {
    int n;
    printf("Enter the number of processes: ");
    scanf("%d", &n);

    struct Process p[n];

    // Input process details
    for (int i = 0; i < n; i++) {
        p[i].pid = i + 1;
        printf("Enter Arrival Time of P%d: ", i + 1);
        scanf("%d", &p[i].arrival);
        printf("Enter Burst Time of P%d: ", i + 1);
        scanf("%d", &p[i].burst);
    }

    // Sort by Arrival Time (FCFS rule)
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (p[j].arrival > p[j + 1].arrival) {
                struct Process temp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = temp;
            }
        }
    }

    int currentTime = 0;
    double totalWaiting = 0;

    // Calculate CT, TAT, WT
    for (int i = 0; i < n; i++) {

        if (currentTime < p[i].arrival)
            currentTime = p[i].arrival;

        currentTime += p[i].burst;
        p[i].completion = currentTime;

        p[i].turnaround = p[i].completion - p[i].arrival;
        p[i].waiting = p[i].turnaround - p[i].burst;

        totalWaiting += p[i].waiting;
    }

    // Output Table
    printf("\nFCFS Scheduling:\n");
    printf("PID\tAT\tBT\tCT\tTAT\tWT\n");
    for (int i = 0; i < n; i++) {
        printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
               p[i].pid, p[i].arrival, p[i].burst,
               p[i].completion, p[i].turnaround, p[i].waiting);
    }

    printf("\nAverage Waiting Time = %.2f\n", totalWaiting / n);

    return 0;
}

---

5. SAMPLE OUTPUT

Input:

Enter the number of processes: 3
Enter Arrival Time of P1: 0
Enter Burst Time of P1: 5
Enter Arrival Time of P2: 1
Enter Burst Time of P2: 3
Enter Arrival Time of P3: 2
Enter Burst Time of P3: 8

Output:

FCFS Scheduling:
PID    AT    BT    CT    TAT    WT
P1     0     5     5     5      0
P2     1     3     8     7      4
P3     2     8     16    14     6

Average Waiting Time = 3.33

---

6. RESULT

FCFS scheduling was successfully simulated.
The program computed:

• Completion time

• Turnaround time

• Waiting time

• Average waiting time

for all processes based on their arrival and burst times.