Waiting queue implementation in Linux system

In software development, tasks often have to go to sleep because some conditions are not met, and then continue to run when the conditions are met, and enter the running state. This requirement needs to be supported by the queue mechanism. A mechanism for waiting queues is provided in Linux, which is widely used in the kernel.

The process of using a wait queue in the Linux kernel is very simple. First define a wait_queue_head, then if a task wants to wait for an event, then call wait_event (wait queue, event).

Waiting queues are widely used, but the kernel implementation is quite simple. It involves two important data structures: __wait_queue_head, which describes the chain header of the wait queue, which contains a linked list and an atomic lock. The structure is defined as follows:

struct __wait_queue_head {

spinlock_t lock; /* protect atomic locks waiting for queues*/

struct list_head task_list; /* wait queues*/

};

__wait_queue, the structure is correct An abstraction of waiting for a task. Each wait task is abstracted into a wait_queue and mounted on wait_queue_head. The structure is defined as follows:

struct __wait_queue {

unsigned int flags;

void *private; /* usually points to the current task control block */

/* Task wakeup operation method, which is provided in the kernel, usually autoremove_wake_function */

wait_queue_func_t func;

struct list_head task_list; /* mount mount_queue_head mount point*/< Br>

};

The idea of ​​waiting queues in Linux is as shown in the following figure. When a task needs to sleep on a wait_queue_head, it encapsulates its own process control block information into wait_queue, and then Mounted to the linked list of wait_queue to perform scheduled sleep. When certain events occur, another task (process) wakes up one or all of the tasks on wait_queue_head. Wake-up work sets the tasks in the wait queue to a schedulable state and removes them from the queue.

is first used to define a wait_queue_head waiting queue, which can be accomplished by DECLARE_WAIT_QUEUE_HEAD macro, which is a method of statically defined. This macro defines a wait_queue_head and initializes the locks in the structure as well as the wait queue. Of course, the method of dynamic initialization is also very simple, you can initialize the lock and queue.

When a task needs to wait for an event to occur, it usually calls wait_event, which defines a wait_queue, describes the waiting task, initializes wait_queue with the current process description block, and then adds wait_queue to wait_queue_head. The function implementation flow is described as follows:

1. Initialize a wait task described by wait_queue with the current process description block (PCB).

2, waiting for the queue lock resource protection, will wait for the task to join the waiting queue.

3. Determine whether the waiting condition is satisfied. If it is satisfied, it will wait for the task to be removed from the queue and exit the function.

4, if the conditions are not met, then the task scheduling, the CPU resources to other tasks.

5. After the sleep task is awakened, repeat steps (2) and (3). If the confirmation condition is met, exit the wait event function.

Waiting queue programming interface

1

wait_event

This is a macro that puts the current task in a wait event state. The input parameters are as follows:

@wq:wait queue

@conditions:wait condition

2

wait_event_timeout

function is similar to wait_event There is an extra timeout mechanism. There is an extra timeout in the parameter.

3

wait_event_interruptible

This is a macro that can be woken up by a message compared to the first two macros. If it is awakened by a message, then return - ERESTARTSYS. The input parameters are as follows:

@wq:wait queue

@condition:wait condition

@rt: return value

4

wait_event_interruptible_timeout

Compared with (3), the timeout mechanism is more

5

wake_up

wake up waiting One task in the queue

6

wake_up_all

wake up all tasks in the wait queue