FCFS Disk Scheduling: Order, Cost and Fairness
Serve requests in the order they arrive, with no reordering at all — the simplest policy, and almost always the most expensive.
How FCFS Disk Scheduling Works
FCFS (First Come First Served) is the simplest disk scheduling algorithm: requests are served in exactly the order they reach the disk queue. It performs no optimisation of any kind, which makes it trivial to implement and trivial to reason about — and, on almost any realistic queue, the most expensive policy available.
- Take the request at the head of the queue the one that arrived first, regardless of where it sits on the disk.
- Move the head to that cylinder the seek cost is the absolute difference between the current position and the target.
- Serve the request, and add that distance to the running total of head movement.
- Repeat for the next arrival no lookahead, no reordering, no consideration of which request happens to be nearby.
- Stop when the queue empties the total head movement is the sum of every individual seek.
- No reordering — arrival order is service order
- Seek cost per request is |target − current|
- Implemented as a plain FIFO queue
- Fair by construction: every request is served in turn
Why It Costs So Much
The problem is that arrival order has no relationship to disk geometry. Two requests that arrive one after another may sit at opposite ends of the platter, and FCFS will dutifully cross the entire disk to serve them in that order — then cross back for the next one.
On the standard queue the head travels 670 cylinders, against 232 for SSTF. The single leg from 183 down to 37 costs 146 cylinders on its own, more than half of SSTF's entire run. The head reverses direction five times in seven requests.
The cost is also unbounded in principle. A workload alternating between cylinder 0 and cylinder 199 makes FCFS pay the full width of the disk on every single request, forever. No amount of queue depth helps, because FCFS never looks past the front of the queue.
- 670 cylinders on the standard queue — worst of the six
- One leg (183 → 37) costs 146 cylinders alone
- Five direction reversals in seven requests
- Alternating extremes make the cost arbitrarily bad
FCFS on the standard request queue
def fcfs(requests, head):
"""Serve requests in arrival order. Returns (order, total head movement)."""
order, total, position = [], 0, head
for cylinder in requests:
total += abs(cylinder - position)
position = cylinder
order.append(cylinder)
return order, total
order, total = fcfs([98, 183, 37, 122, 14, 140, 65], 53)
print(order, total)#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
// Returns total head movement in cylinders; `order` receives the service order.
int fcfs(const vector<int>& requests, int head, vector<int>& order) {
int total = 0, position = head;
// Arrival order, no reordering at all.
for (int cylinder : requests) {
total += abs(cylinder - position);
position = cylinder;
order.push_back(cylinder);
}
total = 0;
position = head;
for (int cylinder : order) {
total += abs(cylinder - position);
position = cylinder;
}
return total;
}
int main() {
vector<int> requests = {98, 183, 37, 122, 14, 140, 65}, order;
int total = fcfs(requests, 53, order);
for (int c : order) cout << c << " ";
cout << "| " << total << " cylinders" << endl;
return 0;
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class FcfsDiskScheduling {
// Returns total head movement in cylinders; `order` receives the service order.
static int fcfs(int[] requests, int head, List<Integer> order) {
int total = 0, position = head;
// Arrival order, no reordering at all.
for (int cylinder : requests) {
total += Math.abs(cylinder - position);
position = cylinder;
order.add(cylinder);
}
total = 0;
position = head;
for (int cylinder : order) {
total += Math.abs(cylinder - position);
position = cylinder;
}
return total;
}
public static void main(String[] args) {
int[] requests = {98, 183, 37, 122, 14, 140, 65};
List<Integer> order = new ArrayList<>();
int total = fcfs(requests, 53, order);
System.out.println(order + " | " + total + " cylinders");
}
}Step through it
Running on requests [98, 183, 37, 122, 14, 140, 65], head at 53
What FCFS Is Actually Good For
Fairness is not a small thing, and it is the one property FCFS holds absolutely. Every request is served after a bounded number of others, so no request can starve — which is exactly the guarantee SSTF fails to provide. In a system where a delayed request means a missed deadline rather than a slow average, that guarantee can matter more than throughput.
It is also the correct choice when there is nothing to optimise. A queue that rarely holds more than one request gives a scheduler nothing to reorder, so the sophisticated algorithms reduce to FCFS anyway while costing more code. Lightly loaded systems and simple embedded controllers sit in exactly that regime.
In practice its main role is as a baseline. The other five algorithms are all judged by how much head movement they save against FCFS on the same queue, which is why exam questions almost always ask for FCFS first.
- Cannot starve any request — its one strong guarantee
- Equivalent to any other algorithm when the queue depth is 1
- Simplest possible implementation: a FIFO queue
- Serves as the comparison baseline for the other algorithms
Where FCFS Still Runs Today
FCFS survived the move away from spinning disks better than any of the seek-optimising algorithms, because the thing it refuses to do — reorder — is exactly what stops mattering when seeking becomes free.
On an SSD or NVMe drive there is no arm and no rotational delay, so servicing block 9 after block 4000 costs the same as servicing block 5. Head movement, the quantity SSTF, SCAN and LOOK exist to minimise, drops out of the cost model entirely. Reordering by block number buys nothing and costs CPU time to compute.
That is why Linux ships a none scheduler and makes it the default for NVMe. Requests pass to the device in arrival order, and the drive's own controller — which alone knows its internal flash layout — handles parallelism across channels. mq-deadline keeps FIFO queues but attaches an expiry to each request, so it is FCFS with a deadline bolted on rather than a sorting algorithm. bfq goes the other way and divides bandwidth fairly between processes, which is a scheduling goal FCFS never addressed.
- SSDs have no seek time, so reordering by block number gains nothing
- Linux defaults NVMe to
none— requests pass straight through in FIFO order mq-deadlineis FCFS plus a per-request expiry, not a seek optimiserbfqtargets fairness between processes, a goal FCFS never had