Skip to content

Day84 - Wait Queue Internals

Today's Goal

Understand how Linux tasks sleep and wake through wait queues, and learn the internal relationship between wait queues, task states, blocking I/O, and event-driven drivers.

What I Learned

Wait Queue Architecture

A wait queue is the fundamental sleep/wakeup mechanism used throughout the Linux kernel.

Core components:

  • wait_queue_head_t
  • wait_queue_entry_t
  • prepare_to_wait()
  • finish_wait()
  • wait_event()
  • wake_up()

Conceptually:

Task
  ↓
wait_event()
  ↓
Wait Queue
  ↓
Sleep

wake_up()
  ↓
Task Runnable

Wait Queue Data Structure

A wait queue consists of:

struct wait_queue_head
{
    struct wait_queue_entry *head;
};

struct wait_queue_entry
{
    struct task_struct *task;
    struct wait_queue_entry *next;
};

The wait queue maintains a list of tasks waiting for an event.

Lab1 implemented:

  • Wait queue initialization
  • Wait queue insertion
  • Wait queue removal
  • Queue traversal and dump

Task State

Linux tasks can transition between different states.

The lab focused on:

TASK_RUNNING
TASK_INTERRUPTIBLE

State transition:

RUNNING
   ↓
prepare_to_wait()
   ↓
INTERRUPTIBLE
   ↓
finish_wait()
   ↓
RUNNING

Lab2 implemented task state transitions and wait queue membership management.

wait_event() and wake_up()

The high-level API used by drivers is typically:

wait_event(...)
wake_up(...)

Internally:

wait_event()
    ↓
prepare_to_wait()
    ↓
Sleep
    ↓
finish_wait()

wake_up()
    ↓
Wake sleeping tasks

Lab3 used:

  • pthread_cond_wait()
  • pthread_cond_broadcast()

to simulate Linux task sleep and wakeup behavior.

Blocking Driver Pattern

A common driver pattern:

User read()
    ↓
wait_event()
    ↓
Sleep

IRQ/Event
    ↓
wake_up()

User read()
    ↓
Continue

This pattern forms the basis of:

  • Blocking character drivers
  • Event-driven drivers
  • Sensor drivers
  • Network receive paths

Labs Completed

Lab1 - Wait Queue Data Structure

Implemented:

  • init_waitqueue_head()
  • add_wait_queue()
  • remove_wait_queue()
  • wait_queue_dump()

Verified:

  • Queue insertion
  • Queue removal
  • Linked-list traversal

Lab2 - Task State and Wait Queue Membership

Implemented:

  • TASK_RUNNING
  • TASK_INTERRUPTIBLE
  • prepare_to_wait()
  • finish_wait()

Verified:

  • Sleep transition
  • Wake transition
  • Queue membership updates

Lab3 - wait_event() and wake_up()

Implemented:

  • wait_event()
  • wake_up()
  • Reader thread
  • Writer thread

Verified:

Reader Sleep
    ↓
Condition Update
    ↓
Wake Up
    ↓
Reader Continue

Key Takeaways

  • Wait queues are the foundation of Linux sleep/wakeup behavior.
  • Tasks enter a wait queue before sleeping.
  • wait_event() is the common driver-facing API.
  • wake_up() resumes tasks waiting for an event.
  • Blocking I/O is fundamentally built on wait queues.
  • Future topics such as poll() and completions are built on the same foundation.

Next Step

Day85 - poll() Internals

Topics:

  • poll()
  • poll_wait()
  • poll_table
  • Event notification
  • Relationship between poll and wait queues
  • Driver poll implementation

Goal:

Understand how Linux event-driven I/O is built on top of wait queues and how user-space event loops interact with kernel wait queues.