Understanding CPU Scheduling: First-Come First-Served (FCFS) with Examples and Diagrams

In operating systems, CPU scheduling determines the order in which processes are executed on the CPU. One of the simplest scheduling algorithms is First-Come First-Served (FCFS), where processes are executed in the order they arrive.

In this blog post, we will:

1. Understand FCFS scheduling with an example.
2. Learn how to calculate waiting times.
3. Compute average and maximum waiting times.
4. Visualize the process execution using Mermaid Gantt charts.
5. Solve a real problem step-by-step.

---

1. What is FCFS Scheduling?

• First-Come First-Served (FCFS) is a non-preemptive scheduling algorithm.
• The process that arrives first gets the CPU first.
• Once a process starts execution, it runs until completion.

Example Scenario

Consider the following processes:

Process	Arrival Time	CPU Burst Time
P1	0	5
P2	2	7
P3	4	3
P4	6	9
P5	8	1
P6	10	5

We will schedule them using FCFS.

---

2. Step-by-Step Execution Schedule

Since FCFS follows the arrival order, the CPU executes processes as follows:

1. P1 arrives at t=0 and runs for 5 units.
   • Start Time: 0
   • End Time: 5
2. P2 arrives at t=2 but must wait until P1 finishes (t=5).
   • Start Time: 5
   • End Time: 5 + 7 = 12
3. P3 arrives at t=4 but must wait until P2 finishes (t=12).
   • Start Time: 12
   • End Time: 12 + 3 = 15
4. P4 arrives at t=6 but must wait until P3 finishes (t=15).
   • Start Time: 15
   • End Time: 15 + 9 = 24
5. P5 arrives at t=8 but must wait until P4 finishes (t=24).
   • Start Time: 24
   • End Time: 24 + 1 = 25
6. P6 arrives at t=10 but must wait until P5 finishes (t=25).
   • Start Time: 25
   • End Time: 25 + 5 = 30

---

3. Calculating Waiting Times

The waiting time for a process is the time it spends waiting in the ready queue before execution.

• Waiting Time = Start Time - Arrival Time

Let’s compute it for each process:

Process	Arrival Time	Start Time	Waiting Time
P1	0	0	0 - 0 = 0
P2	2	5	5 - 2 = 3
P3	4	12	12 - 4 = 8
P4	6	15	15 - 6 = 9
P5	8	24	24 - 8 = 16
P6	10	25	25 - 10 = 15

---

4. Average and Maximum Waiting Time

Now, we compute:

1. Average Waiting Time: [ \frac{0 + 3 + 8 + 9 + 16 + 15}{6} = \frac{51}{6} = 8.5 ]
2. Maximum Waiting Time:
   • The highest waiting time is 16 (for P5).

---

5. Evaluating the Given Problem

The original question asks which statement is true based on the computed waiting times. The options were:

1. Average wait time is more than 7.5; maximum wait time is more than 15.0
   • ✅ True (Average = 8.5 > 7.5, Max = 16 > 15.0)
2. Average wait time is more than 7.5; maximum wait time is less than 15.5
   • ❌ False (Max is 16, which is not less than 15.5)
3. Average wait time is less than 7.0; maximum wait time is more than 15.0
   • ❌ False (Average is 8.5, which is not less than 7.0)
4. Average wait time is more than 8.5; maximum wait time is less than 17.0
   • ❌ False (Average is exactly 8.5, not more than 8.5)

Final Answer

✅ Option 1 is correct because:

• Average waiting time (8.5) > 7.5
• Maximum waiting time (16) > 15.0

---

6. Key Takeaways

1. FCFS is simple but can lead to long waiting times (known as the convoy effect).
2. Waiting time depends on the order of arrival.
3. Non-preemptive (once a process starts, it runs to completion).
4. Not optimal for minimizing waiting time (other algorithms like SJF or Round Robin may perform better).

---

7. Practice Problem

Try solving this yourself:

Process	Arrival Time	Burst Time
A	0	3
B	2	6
C	4	4
D	6	5

Compute:

1. Gantt Chart for FCFS.
2. Waiting times for each process.
3. Average and maximum waiting times.

Solution

1. Gantt Chart:

   A (0-3) → B (3-9) → C (9-13) → D (13-18)
   

2. Waiting Times:
   • A: 0
   • B: 3 - 2 = 1
   • C: 9 - 4 = 5
   • D: 13 - 6 = 7
3. Average Waiting Time: (0 + 1 + 5 + 7)/4 = 3.25
4. Maximum Waiting Time: 7 (for D)

---

Conclusion

FCFS is straightforward but can lead to inefficiencies. Understanding how to compute waiting times helps in evaluating scheduling algorithms.