FIFO Semantics (Queue Discipline)¶

First-in-first-out ordering enforces fairness and preserves arrival sequence - essential when processing order must match arrival order or when all requests deserve equal treatment.

Tension Addressed¶

Simplicity vs. Capability

Recognizable As¶

Message queues; breadth-first traversal; print spoolers; request buffering; any producer-consumer pattern; "waiting line" analogies

Canonical Sources¶

Knuth, TAOCP Vol. 1, Section 2.2.1 (1968); Hoare, "Monitors: An Operating System Structuring Concept" (1974)

Transfers To¶

Operating Systems (I/O scheduling), Distributed Systems (message passing), Networks (packet ordering), Concurrency (work queues)

The queue embodies fairness - no starvation, bounded wait times. This makes it fundamental to concurrent and distributed systems.