Skip to content

Day84 - Wait Queue Internals

Goal

Understand the internal structure and behavior of Linux wait queues.

Topics covered:

  • wait_queue_head_t
  • wait_queue_entry_t
  • Task states
  • prepare_to_wait()
  • finish_wait()
  • wait_event()
  • wake_up()
  • Blocking I/O architecture

Background

Wait queues are one of the most important synchronization mechanisms in the Linux kernel.

They provide the foundation for:

  • Blocking I/O
  • Event-driven drivers
  • poll()
  • Completions
  • Driver sleep/wakeup behavior

Conceptually:

Task
  ↓
Wait Queue
  ↓
Sleep

Event
  ↓
wake_up()
  ↓
Task Runnable

Lab1 - Wait Queue Data Structure

Objective

Implement a minimal wait queue using a singly linked list.

Data Structures

struct task_struct {
    int pid;
    const char *name;
};

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

struct wait_queue_head {
    struct wait_queue_entry *head;
};

APIs

Implemented:

void init_waitqueue_head(struct wait_queue_head *wq);

void add_wait_queue(
        struct wait_queue_head *wq,
        struct wait_queue_entry *entry);

void remove_wait_queue(
        struct wait_queue_head *wq,
        struct wait_queue_entry *entry);

void wait_queue_dump(
        struct wait_queue_head *wq);

Verification

Add reader1

[WAITQ]
 [0] task=reader1

Add reader2

[WAITQ]
 [0] task=reader1
 [1] task=reader2

Add reader3

[WAITQ]
 [0] task=reader1
 [1] task=reader2
 [2] task=reader3

Remove reader2

[WAITQ]
 [0] task=reader1
 [1] task=reader3

Learning Points

  • Wait queues are fundamentally linked lists.
  • Each entry represents a waiting task.
  • Queue insertion and removal are core operations.

Lab2 - Task State and Wait Queue Membership

Objective

Add task state transitions.

Task States

Implemented:

enum task_state {
    TASK_RUNNING,
    TASK_INTERRUPTIBLE,
};

APIs

Implemented:

void prepare_to_wait(
        struct wait_queue_head *wq,
        struct wait_queue_entry *entry);

void finish_wait(
        struct wait_queue_head *wq,
        struct wait_queue_entry *entry);

State Transition

TASK_RUNNING
        ↓
prepare_to_wait()
        ↓
TASK_INTERRUPTIBLE
        ↓
finish_wait()
        ↓
TASK_RUNNING

Verification

Reader Sleep

[WAITQ]
 [0] task=reader1, state=INTERRUPTIBLE

Reader Wake

[TASK]
task=reader1
state=RUNNING

Learning Points

  • Sleeping tasks are inserted into a wait queue.
  • Waking tasks are removed from a wait queue.
  • Task state and queue membership are closely related.

Lab3 - wait_event() and wake_up()

Objective

Simulate Linux task sleep/wakeup behavior.

Additional Structures

struct wait_queue_head {
    struct wait_queue_entry *head;

    pthread_mutex_t lock;
    pthread_cond_t wait_cond;
};

APIs

Implemented:

void wait_event(
        struct wait_queue_head *wq,
        struct wait_queue_entry *entry,
        bool *condition);

void wake_up(
        struct wait_queue_head *wq);

Reader Thread

wait_event()
        ↓
Sleep

Writer Thread

condition = true
        ↓
wake_up()

Verification

[READER] wait for condition

[WAIT] reader goes to sleep

[WRITER] set condition

[WRITER] wake up wait queue

[WAIT] reader wakes up

[READER] condition ready, continue

Internal Flow

Reader
    ↓
wait_event()
    ↓
prepare_to_wait()
    ↓
TASK_INTERRUPTIBLE
    ↓
pthread_cond_wait()

Writer
    ↓
condition = true
    ↓
wake_up()
    ↓
pthread_cond_broadcast()

Reader
    ↓
finish_wait()
    ↓
TASK_RUNNING

Learning Points

  • wait_event() is the driver-facing API.
  • prepare_to_wait() and finish_wait() are internal helpers.
  • Wait queues implement the sleep/wakeup mechanism used throughout the kernel.

Blocking Driver Pattern

A common driver architecture:

User read()
    ↓
wait_event()
    ↓
Sleep

IRQ/Event
    ↓
data_ready = true
    ↓
wake_up()

User read()
    ↓
Continue

This pattern is used by:

  • GPIO event drivers
  • Sensor drivers
  • Network receive paths
  • Blocking character devices

Summary

This lab implemented a simplified wait queue subsystem and demonstrated:

  • Queue management
  • Task state transitions
  • Sleep/wakeup behavior
  • Blocking driver architecture

These concepts form the foundation of Linux event-driven and blocking I/O mechanisms.