Introduction
First Come First Served (FCFS) is the simplest CPU scheduling algorithm. Processes are scheduled in the order of their arrival time. Non-preemptive: once a process starts execution, it runs to completion. Widely used for batch systems and simple operating environments.
"The first come, first served principle is fundamental in queuing and scheduling, providing fairness but often compromising efficiency." -- A. S. Tanenbaum
Definition and Overview
Basic Concept
Processes queued in order of arrival. The CPU allocates time strictly based on arrival sequence. No preemption allowed.
Non-preemptive Behavior
Once a process gains CPU, runs till completion or I/O wait. No interruption by new arrivals or higher priority.
Queue Structure
Typically implemented as a FIFO (First-In-First-Out) queue. Simple linear data structure.
Algorithm Description
Stepwise Procedure
1. Maintain a queue of ready processes sorted by arrival time.
2. Select the first process in the queue.
3. Allocate CPU until process completes.
4. Remove completed process from queue.
5. Repeat for next process.
Pseudocode
while (readyQueue not empty) { currentProcess = dequeue(readyQueue); execute(currentProcess); currentProcess.status = finished;}Handling Arrival Times
Processes arriving during CPU execution wait until current completes. Next process selected after completion.
Key Properties
Non-preemptive
No interruption once execution starts. Simplicity but potential for long wait times.
Fairness
Strict order of arrival ensures fairness. No starvation possible.
Deterministic
Scheduling order predictable if arrival times known.
Queue Type
FIFO queue guarantees order preservation.
Performance Metrics
Waiting Time
Time a process spends waiting in the ready queue before execution.
Turnaround Time
Total time from process arrival to completion.
Throughput
Number of processes completed per unit time.
CPU Utilization
Percentage of time CPU is busy.
| Metric | Definition |
|---|---|
| Waiting Time | Start time - Arrival time |
| Turnaround Time | Completion time - Arrival time |
| Throughput | Processes completed / Total time |
Advantages
Simplicity
Easy to implement and understand. Minimal overhead.
Fairness
Processes served in exact order of arrival. No starvation.
Predictability
Scheduling order and completion times easily calculated if arrival and burst times known.
Low Context Switching
No preemption reduces number of context switches.
Limitations and Drawbacks
Convoy Effect
Long process at front delays all subsequent shorter processes.
High Average Waiting Time
Non-preemption leads to inefficient CPU utilization for short jobs waiting behind long ones.
Non-responsive to Priority
No mechanism to prioritize important or time-critical processes.
Not Suitable for Interactive Systems
Delays degrade user experience in real-time environments.
Comparison with Other Scheduling Algorithms
FCFS vs Shortest Job First (SJF)
SJF reduces average waiting time by scheduling shortest processes first. FCFS simpler but less efficient.
FCFS vs Round Robin (RR)
RR preemptive, improves response times for interactive tasks. FCFS non-preemptive and simpler.
FCFS vs Priority Scheduling
Priority scheduling considers importance; FCFS ignores priority, ensuring fairness but less flexibility.
Summary Table
| Algorithm | Preemptive | Average Waiting Time | Fairness |
|---|---|---|---|
| FCFS | No | High | Yes |
| SJF | No | Low | No |
| Round Robin | Yes | Medium | Yes |
| Priority Scheduling | Optional | Variable | No |
Illustrative Example
Process Data
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
Gantt Chart and Calculations
Time: 0 5 8 16 |----|----|-----| P1 P2 P3Waiting Time Calculation:WT(P1) = 0 - 0 = 0WT(P2) = 5 - 1 = 4WT(P3) = 8 - 2 = 6Turnaround Time Calculation:TAT(P1) = 5 - 0 = 5TAT(P2) = 8 - 1 = 7TAT(P3) = 16 - 2 = 14Average Waiting Time = (0 + 4 + 6) / 3 = 3.33Average Turnaround Time = (5 + 7 + 14) / 3 = 8.67Implementation Considerations
Data Structures
Ready queue as FIFO linked list or array. Arrival times stored in process control blocks.
Process State Transitions
New arrivals added at queue tail. Running process transitions to terminated on completion.
System Calls and Interrupts
Scheduler invoked on process termination or new arrival if CPU idle.
Complexity
Time complexity O(1) for enqueue/dequeue operations. Minimal overhead.
Possible Optimizations
Batching Similar Processes
Group short processes together to reduce convoy effect.
Combining with Priority Scheduling
Hybrid approach to improve responsiveness.
Dynamic Reordering
Adjust queue order based on burst time or deadlines.
Idle CPU Utilization
Idle detection and context switching enhancements.
Applications and Use Cases
Batch Processing Systems
Simple queues with minimal interaction. FCFS fits well.
Non-Interactive Environments
Environments where fairness prevails over response time.
Embedded Systems
Low overhead scheduling with predictable timing.
Educational Context
Teaching basic scheduling concepts and queue management.
References
- Silberschatz, A., Galvin, P. B., & Gagne, G. "Operating System Concepts," 10th ed., Wiley, 2018, pp. 220-240.
- Tanenbaum, A. S., & Bos, H. "Modern Operating Systems," 4th ed., Pearson, 2015, pp. 130-150.
- Stallings, W. "Operating Systems: Internals and Design Principles," 9th ed., Pearson, 2018, pp. 160-180.
- Gandhi, R. "CPU Scheduling Algorithms: A Comparative Study," International Journal of Computer Applications, vol. 120, no. 3, 2015, pp. 15-22.
- Kumar, S., & Singh, R. "Evaluation of Scheduling Algorithms in Operating Systems," Journal of Computer Science, vol. 11, no. 6, 2015, pp. 523-530.