FCFS Disk Scheduling Algorithm
Every time a program reads or writes data, a request goes to the disk. When multiple requests pile up faster than the disk can serve them, the OS needs a strategy to decide the order in which those requests get handled.
That strategy is the disk scheduling algorithm, and the absolute simplest one available is FCFS.
What is FCFS Disk Scheduling?
First Come First Served (FCFS) does exactly what the name suggests. Requests are queued up in the exact order they arrive, and the disk head visits them in that same order without any reordering or optimization.
No request jumps the queue based on its position, priority, or how conveniently it sits near the current head location. This makes FCFS completely fair. Every request waits its turn, and no request ever gets permanently ignored (starved).
The trade-off is efficiency: the disk head might end up traveling enormous distances back and forth across the disk simply because requests happened to arrive in an inconvenient order.
How the Algorithm Works
The process is completely straightforward:
- Maintain a queue of incoming disk requests.
- Each new request joins the back of the queue.
- When the disk head is free, move it to the track requested at the front of the queue.
- Serve that request (read or write the data).
- Remove it from the queue.
- Repeat until the queue is empty.
Worked Example
Let's trace the algorithm. We are given an initial head position of 40, and a queue of track requests in arrival order: 120, 15, 80, 55, 170, 30, 100, 60.
| Movement | Calculation | Distance (Tracks) |
|---|---|---|
| 40 → 120 | |40 - 120| | 80 |
| 120 → 15 | |120 - 15| | 105 |
| 15 → 80 | |15 - 80| | 65 |
| 80 → 55 | |80 - 55| | 25 |
| 55 → 170 | |55 - 170| | 115 |
| 170 → 30 | |170 - 30| | 140 |
| 30 → 100 | |30 - 100| | 70 |
| 100 → 60 | |100 - 60| | 40 |
Total Head Movement = 80 + 105 + 65 + 25 + 115 + 140 + 70 + 40 = 640 tracks.
Average Seek Time = 640 / 8 = 80 tracks per request.
Notice the wild swings: the head jumps from 120 all the way back to 15, then out to 80, back to 55, all the way to 170, then back to 30. Each of these long jumps represents real time the disk spends moving rather than serving data.
FCFS Head Movement Sequence. Notice the wild zig-zagging across the disk tracks.
Implementation
Python Implementation
def fcfs_disk_scheduling(requests, initial_head):
total_movement = 0
current_position = initial_head
sequence = []
for track in requests:
movement = abs(current_position - track)
total_movement += movement
sequence.append((current_position, track, movement))
current_position = track
print("Head Movement Sequence:")
for step in sequence:
print(f" {step[0]} -> {step[1]} : {step[2]} tracks")
print(f"\nTotal Head Movement: {total_movement} tracks")
print(f"Average Seek Time : {total_movement / len(requests):.2f} tracks")
return total_movement
initial_head = 40
requests = [120, 15, 80, 55, 170, 30, 100, 60]
fcfs_disk_scheduling(requests, initial_head)C++ Implementation
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int fcfs_disk_scheduling(vector<int>& requests, int initial_head) {
int total_movement = 0;
int current_position = initial_head;
cout << "Head Movement Sequence:" << endl;
for (int track : requests) {
int movement = abs(current_position - track);
cout << " " << current_position << " -> " << track
<< " : " << movement << " tracks" << endl;
total_movement += movement;
current_position = track;
}
cout << "\nTotal Head Movement: " << total_movement << " tracks" << endl;
cout << "Average Seek Time : "
<< (float)total_movement / requests.size() << " tracks" << endl;
return total_movement;
}
int main() {
int initial_head = 40;
vector<int> requests = {120, 15, 80, 55, 170, 30, 100, 60};
fcfs_disk_scheduling(requests, initial_head);
return 0;
}Java Implementation
public class FCFSDiskScheduling {
public static void main(String[] args) {
int initialHead = 40;
int[] requests = {120, 15, 80, 55, 170, 30, 100, 60};
int totalMovement = 0;
int currentPosition = initialHead;
System.out.println("Head Movement Sequence:");
for (int track : requests) {
int movement = Math.abs(currentPosition - track);
System.out.println(" " + currentPosition + " -> " + track
+ " : " + movement + " tracks");
totalMovement += movement;
currentPosition = track;
}
System.out.println("\nTotal Head Movement: " + totalMovement + " tracks");
System.out.printf("Average Seek Time : %.2f tracks%n",
(float) totalMovement / requests.length);
}
}Practice Problem Walkthrough
Let's try another one. Disk requests arrive in this order: 200, 50, 150, 90, 180, 30. The head starts at track 110.
| Movement | Calculation | Distance (Tracks) |
|---|---|---|
| 110 → 200 | |110 - 200| | 90 |
| 200 → 50 | |200 - 50| | 150 |
| 50 → 150 | |50 - 150| | 100 |
| 150 → 90 | |150 - 90| | 60 |
| 90 → 180 | |90 - 180| | 90 |
| 180 → 30 | |180 - 30| | 150 |
Total Head Movement = 90 + 150 + 100 + 60 + 90 + 150 = 640 tracks.
Average Seek Length = 640 / 6 = ~106.67 tracks.
Advantages and Disadvantages
| Advantages | Disadvantages |
|---|---|
| The simplest disk scheduling algorithm to understand and implement. | Total head movement is often far higher than necessary. |
| Completely fair since every request is treated equally regardless of its position. | The disk head can zigzag wildly across tracks because arrival order has nothing to do with physical proximity. |
| No starvation since every request eventually reaches the front of the queue. | Average seek time grows huge when requests are scattered across the disk. |
| Predictable behavior making it easy to reason about. | Not suitable for high throughput systems where disk performance is critical. |
When FCFS Makes Sense
Despite its inefficiency, FCFS has practical value in specific situations. Systems with light or predictable disk loads where requests do not pile up much will not suffer significantly from the lack of optimization.
It also works well as a baseline for comparing more sophisticated algorithms: if a new scheduling approach cannot outperform plain FCFS, it is not worth the added complexity.
For high demand environments like database servers or systems doing heavy file I/O, algorithms like SSTF, SCAN, or C-SCAN significantly reduce head movement and are worth the added implementation effort.
Calculate FCFS Head Movement
Question 1 of 1Test your ability to trace the FCFS algorithm.