First-come-first-served scheduling
First-come-first-served is a nonpreemptive scheduling discipline that selects waiting requests in arrival order when service becomes available.
FCFS orders service selection, not requests by size or priority. Once a request starts, a later arrival does not interrupt it. The scheduling rule does not itself require Poisson arrivals; that is a separate assumption in an M/G/1 analysis. [1]
State the queue boundary and how simultaneous arrivals are ordered. With multiple servers, service selection order need not be completion order: an earlier request can take longer on another server. This is a consequence of the model, not a measured storage result. [3]
A FIFO host queue does not establish end-to-end FCFS storage behavior. Linux blk-mq distinguishes staging, dispatch and tagged completion, and does not promise completion order. Higher layers must explicitly arrange any operation ordering they require. [2]
FIFO cache replacement selects an eviction victim; FCFS scheduling selects work for service. They are separate uses of arrival order. [3]
Relations
Citations
- Scully et al. SOAP: One Clean Analysis of All Age-Based Scheduling Policies. PACM 2(1), 16 (2018), section 1. DOI: 10.1145/3179419.
- Linux 6.16: Multi-Queue Block IO Queueing Mechanism, hardware dispatch queues and tag-based completion.
- Hesela: queue order, blocked work and completion boundaries.
Sources & caveats
- Primary-source synthesis and scheduling-model reasoning; no new device benchmark or scheduler implementation.