DEV Community: Vadher Nikunj

Queues Explained with Real Examples from the Linux Kernel

Vadher Nikunj — Mon, 02 Nov 2026 05:42:39 +0000

In the last post we looked at the stack, where the last thing in is the first thing out. This time we look at its opposite, the queue. It is just as simple, and the Linux kernel leans on it all the time.

Let's start with the idea, write a small one in C, and then see where the kernel uses it.

What is a queue?

Think of the line at a ticket counter. A new person joins at the back. The person at the front gets served and leaves. Nobody jumps ahead. The first person who came is the first person who gets a ticket.

That rule is called first in, first out, or FIFO. A queue has two main actions:

Enqueue adds a new item at the back
Dequeue takes the item at the front

Most queues also let you check if they are empty or full.

The big difference from a stack is fairness. A queue always serves the item that has waited the longest.

A tiny queue in C

The easy way to build a queue is with an array and two positions. One position, head, marks the front. The other, tail, marks where the next item goes. But there is a catch. If you only ever move forward, you soon reach the end of the array, even though the front part is now empty.

The fix is to wrap around. When tail or head reaches the end, it goes back to 0. This is called a circular buffer, or ring buffer. Picture the array bent into a circle.

#define MAX 8

int queue[MAX];
int head = 0;     /* where the next item is taken from */
int tail = 0;     /* where the next item goes in */
int count = 0;    /* how many items are waiting */

int enqueue(int x) {
    if (count == MAX) return -1;    /* full, so we stop */
    queue[tail] = x;
    tail = (tail + 1) % MAX;        /* wrap around to the start */
    count++;
    return 0;
}

int dequeue(int *x) {
    if (count == 0) return -1;      /* empty, nothing to give */
    *x = queue[head];
    head = (head + 1) % MAX;
    count--;
    return 0;
}

The % MAX part does the wrap. If tail is 7 and MAX is 8, then (7 + 1) % 8 is 0, so the next item goes back at the start. The count tells us if the queue is full or empty, because head == tail can mean either one.

Like the stack, both actions take the same short time no matter how many items are waiting.

Where the Linux kernel uses queues

The examples below are from the Linux 2.6 kernel. Newer kernels have changed some details, but the ideas are still there.

Wait queues for sleeping processes

A process often has to wait for something. It may be waiting for a disk read to finish, or for a resource to be free. There is no point keeping the CPU busy while it waits. So the kernel puts it to sleep on a wait queue and runs something else.

Each wait queue belongs to one kind of event. When the event happens, the kernel wakes the processes sleeping on it. Inside, a wait queue is a doubly linked list. Each item points to a sleeping process. The head of the list also has a lock, because interrupt handlers and normal kernel code can both change it.

There is a nice detail here. Sometimes many processes wait for a resource that only one of them can use. Waking all of them would be a waste, since only one would win and the rest would go back to sleep. This is called the "thundering herd" problem. To avoid it, such processes are marked as exclusive and added at the back of the list, and the kernel wakes only one of them at a time.

Read/write semaphores in strict FIFO order

A semaphore is a kind of lock. When a process can't get it, the process sleeps on the semaphore's wait queue. For read/write semaphores, the kernel handles the waiting processes in strict FIFO order. Each new waiter joins at the back. When the lock is released, the kernel looks at the process at the front first. That is a ticket counter line, written in kernel code.

The runqueue

Processes that are ready to run sit on the runqueue. Older versions kept one big list and had to scan all of it to pick the best process. Linux 2.6 split it into 140 lists, one for each priority level, and each CPU got its own set.

When a process becomes ready, the function enqueue_task() adds it to the tail of the list for its priority. The kernel also has dequeue_task() to take it out. So within one priority level, processes line up and take turns. For round robin real-time processes, the one that gets the CPU is moved to the end of its list, so others of the same priority get a fair share.

Pipes as a circular buffer

When you type ls | grep txt, the two programs talk through a pipe. From Linux 2.6.11, each pipe uses 16 buffers, and the kernel treats them as one circular buffer. Writers keep adding data. Readers keep taking it out from the front. To find the first empty buffer, the kernel adds the current buffer index and the number of full buffers, modulo 16. That is the same % MAX trick from our code above.

Queue or stack?

How do you pick? Ask one question: who should be served next?

If the newest item should go first, use a stack. Function calls and undo work that way.

If the oldest item should go first, use a queue. This is what you want when things arrive over time and each one should get its turn, like print jobs or network packets. It is also the base of breadth first search in graphs, where you visit nodes level by level.

Try it yourself

Add a peek() function to the code above that returns the front item without removing it.
Change the queue to use a linked list instead of an array, so it has no fixed size.
Build a queue using two stacks. It is a common interview question.

What comes next

Next in the series is the linked list, which we have already met twice here, inside wait queues and the runqueue. If you want to write these structures yourself and see them run, our C and data structures course at /courses/c-ds-a/ walks through them step by step.

I first published this on the Jupius Learning blog.

Stacks Explained with Real Examples from the Linux Kernel

Vadher Nikunj — Mon, 02 Nov 2026 05:31:02 +0000

A stack is one of the simplest data structures there is. You can learn the idea in one minute. But it is also one of the most useful, and it sits inside every program you have ever run, including the Linux kernel.

Let's start with the idea, then look at where the kernel uses it.

What is a stack?

Think of a pile of plates. You put a new plate on top. When you need one, you take the top plate. You never pull one from the middle. The last plate you put on is the first one you take off.

That rule has a name: last in, first out, or LIFO. A stack has only two main actions:

Push puts a new item on top
Pop takes the top item off

Most stacks also let you peek at the top item without removing it, and check if the stack is empty.

A tiny stack in C

Here is a stack of integers using a plain array. It is small, but it shows the whole idea.

#define MAX 100

int stack[MAX];
int top = -1;          /* -1 means the stack is empty */

void push(int x) {
    if (top == MAX - 1) return;   /* full, so we stop */
    stack[++top] = x;
}

int pop(void) {
    if (top == -1) return -1;     /* empty, nothing to give */
    return stack[top--];
}

Both actions are quick. They do not depend on how many items are in the stack. That is why stacks are used in places where speed matters a lot.

Where the Linux kernel uses stacks

Every process on Linux gets its own stack inside the kernel. It is separate from the stack your program uses in normal mode. In the Linux 2.6 days on x86, this kernel stack lived in a fixed area of 8 KB, which is two memory pages. The small data block that describes the process sat at the start of that area, and the stack started at the far end and grew backwards toward it.

Notice the detail here. The stack does not grow forward. It starts at the high end and moves down as you push. A register called esp always points to the current top. When the stack is empty, it points just past the end of the area. This is the same thing as top = -1 in our small example, only done at machine level.

Function calls

When one function calls another, the CPU pushes the return address and the local variables on the stack. When the function ends, they are popped, and the program goes back to exactly where it left off. If function A calls B, and B calls C, then C must finish first, then B, then A. That is LIFO again. You never have to think about it, because the stack does it for you.

Interrupts

Now the more interesting case. When a device such as a keyboard or a network card needs attention, the CPU stops what it is doing and runs an interrupt handler. The first thing the kernel does is save the CPU registers on the kernel stack. The last thing it does is restore them, so the interrupted work can carry on as if nothing happened.

Interrupts can also be nested. One handler can be interrupted by another one, and that one by another. How does the kernel remember where to go back to? It just pushes each one on the stack. The newest handler finishes first, then it returns to the one before it, and so on, until the CPU is back to the original work. A stack is the natural fit, because the last thing that started is always the first thing that must finish.

Switching between processes

When the kernel stops one process and starts another, it has to save the state of the first one so it can be continued later. Part of that state is stored in the process's own kernel stack. Because each process has its own stack, the kernel can switch to another process by changing the stack pointer. In the code, the switch is really a swap from one stack to another.

Why the stack is small

You may wonder why the kernel keeps this stack so small. It is because kernel code is careful. It does not use deep chains of function calls or big local arrays. A stack that runs out of space is a serious bug, since the data next to it can be overwritten. The kernel also had a setting for even smaller 4 KB stacks, and in that case it used a few extra stacks just for interrupts, so that deeply nested handlers would not run it out of room.

The lesson for your own code is the same. A stack has a limit, and if you go too deep, for example with a function that calls itself forever, you get the famous stack overflow.

More places you already use stacks

The undo button in your editor
The back button in your browser
Checking that brackets match in code, like { ( ) }
Evaluating expressions like 3 + 4 * 2
Depth first search in graphs and trees

Try it yourself

Write a function that uses a stack to check if a string like {[()]} has matching brackets.
Reverse a string using only push and pop.
What happens in the code above if you call pop() on an empty stack? How would you handle it better?

If you can do these three, you understand stacks well enough for most interviews.

What comes next

Next in the series is the queue. It is the stack's opposite, first in and first out, and the kernel uses it a lot too. If you want to practise as you read, our C and data structures course covers stacks, queues and the rest hands-on.

I first published this on the Jupius Learning blog. If you want to practice, the C, data structures and algorithms course is a good place to start.