Operating Systems: Queues, Linked Lists, Trees

Operating system kernels (Linux, Android OS) manage raw hardware, hardware interrupts, process life cycles, and virtual memory mappings using carefully selected data structures.

1. Process Scheduling: The Linux Completely Fair Scheduler (CFS)

How does the Linux kernel choose which thread runs on a CPU core among hundreds of competing processes?

The Structure: Red-Black Tree

• Every runnable process is stored in a Red-Black Tree ordered by its accumulated execution time (vruntime).
• The process that has run the least amount of CPU time sits at the leftmost leaf node of the tree.
• Picking the next thread to execute takes O(1) time by tracking rb_leftmost.
• Updating and reinserting a process after its time quantum takes O(log n) time.

Copy codeLinux CFS Runqueue (Red-Black Tree):
                  [ Task 3 (vruntime: 120ms) ]
                 /                             \
     [ Task 1 (vruntime: 50ms) ]        [ Task 4 (vruntime: 180ms) ]
      /
[ Task 2 (20ms) ]  <-- Next process selected to run!

2. Hardware Interrupts & Device Drivers: Circular Ring Buffers

When a network card receives Ethernet packets or an audio chip receives microphone data:

• Data arrives asynchronously via hardware interrupts.
• If the CPU had to allocate heap nodes for each incoming packet, the OS would crash from memory allocation stalls.
• The Solution: A fixed-size Circular Ring Buffer with DMA (Direct Memory Access). The hardware writes into the tail, and the kernel reads from the head without locks or allocations.

3. Kernel Object Tracking: Circular Doubly Linked Lists

Inside the Linux kernel source code (include/linux/list.h), the kernel defines a universal doubly linked list node:

Copy codestruct list_head {
    struct list_head *next, *prev;
};

Instead of wrapping data around nodes, Linux embeds list_head directly inside structs (processes, open files, network sockets). This allows any kernel struct to be part of multiple linked lists simultaneously without allocating wrapper memory!

Summary

• Red-Black Trees power the Linux Completely Fair Scheduler (CFS) to pick the next runnable process in O(1).
• Ring Buffers handle real-time hardware DMA data streams without memory allocations.
• Embedded Doubly Linked Lists link kernel objects into multiple tracking queues concurrently.