How Queues Work, with Examples from the Linux Kernel

The article explains the queue, a first-in, first-out data structure defined by enqueue and dequeue operations. It shows how a fixed-size circular buffer in C avoids wasted space by wrapping the head and tail indices back to the start of the array. It then describes how the Linux kernel uses queues, specifically wait queues that put processes to sleep until an event occurs. The piece also covers exclusive waiters, which prevent the thundering herd problem by waking only one process at a time. Finally, it notes that read/write semaphores serve their waiters in strict FIFO order.