FCFS Scheduling Overview

Overview

This lecture explains the First Come First Serve (FCFS) scheduling algorithm, demonstrates calculations for turnaround and waiting times with examples, and introduces the convoy effect issue.

FCFS Scheduling Algorithm

• FCFS stands for First Come First Serve scheduling algorithm.
• In FCFS, the process that arrives first in the ready queue is executed first by the CPU.
• FCFS is a non-preemptive scheduling algorithm—once a process starts, it runs until it finishes.

Example Calculation (with Arrival and Burst Times)

• Example with five processes (P0–P4), each having arrival and burst times.
• Burst time is the time required by a process for execution.
• Use a Gantt chart to visualize execution order and timing.
• Completion time (CT) is when a process finishes executing.
• Turnaround time (TAT) = Completion Time (CT) - Arrival Time (AT).
• Waiting time (WT) = Turnaround Time (TAT) - Burst Time (BT).
• Calculated average turnaround time: 8.6 milliseconds.
• Calculated average waiting time: 4.6 milliseconds.

Example Calculation (No Arrival Times)

• When arrival times are not given, order is determined by listed process order.
• Gantt chart can help track the timing for each process.
• Turnaround time equals completion time if arrival time is zero for all.
• Changing the order of process arrivals affects average waiting time.
• If long processes come first, short ones wait longer.

Convoy Effect in FCFS

• Convoy effect occurs when a long process is scheduled before short ones, forcing the latter to wait.
• If short processes come first, waiting times are minimized for all.
• FCFS suffers from the convoy effect when high burst time processes arrive before low burst time processes.

Key Terms & Definitions

• FCFS — First Come First Serve scheduling, a non-preemptive algorithm where processes run in the order they arrive.
• Burst Time (BT) — Time required by a process for execution.
• Arrival Time (AT) — Time when a process enters the ready queue.
• Completion Time (CT) — Time when a process finishes execution.
• Turnaround Time (TAT) — CT minus AT; total time from submission to completion.
• Waiting Time (WT) — TAT minus BT; time a process spends waiting in the ready queue.
• Convoy Effect — Delay caused when short processes are forced to wait behind a long process.

Action Items / Next Steps

• Practice solving FCFS problems with different arrival and burst times.
• Review concepts of completion time, turnaround time, and waiting time.
• Read more about other scheduling algorithms and compare them with FCFS.