Waiting queue wait_ queue

1. Basic introduction
Waiting queues have long existed as a basic functional unit linux The kernel , It's based on queues, data structures , Closely cooperate with the process scheduling mechanism , It can be used to implement asynchronous event notification mechanism in kernel . Waiting queues can also be used to synchronize access to system resources . When in use, it is made into a common queue data structure , Just wait queue is a collection of several dormant processes , And the kernel implements this queue to initialize the queue 、 Queue entry 、 A series of queues API, You only need to call the system's API that will do .
Simply understand the waiting queue : A queue of dormant processes , Wait for a specific event to wake up .

2 Part of the concept of waiting queues
Wait for the queue header ：
Wait for the queue header , As the name suggests, it is the head of the waiting queue . A waiting queue has a waiting queue header , When other processes wake up , Wake up only the first dormant process waiting for the head of the queue .

Wait for the queue ：
The head of a waiting queue is the head of a waiting queue , Every process that accesses a device is a queue entry , When the device is unavailable, the corresponding waiting queue items of these processes should be added to the waiting queue .

Suppose a scenario : The whole grade students gather on the playground to get books , Different classes are in a team （ Waiting in line ）. When called to which class , The first student in the class came up to get the book （ Queue wakeup ）, Students who didn't call their names waited in place （ Dormancy process , Wait for the queue ）. At this time, the class is a waiting queue head . The queue of students in the same class is the waiting queue .

3. Queue operations provided by the kernel API
3.1 Wait for the queue header ：
Prototypes of structures ：

struct __wait_queue_head {
    spinlock_t lock;
    struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
Waiting for queue header initialization :

#if 0
// initiate static
DECLARE_WAIT_QUEUE_HEAD(name); 
#else
// dynamic initialization
wait_queue_head_t my_queue;
init_waitqueue_head(&my_queue);
#endif
3.2 Wait for the queue ：
Prototypes of structures ：

struct __wait_queue {
    unsigned int flags;
    void *private;
    wait_queue_func_t func;
};
typedef struct __wait_queue wait_queue_t;
Waiting queue item definition ：

DECLARE_WAITQUEUE(name, tsk)
3.3 Add or remove waiting queue items
The current process , Sleep it first （ Task scheduling ）, Then join the waiting queue , It is convenient for other processes to wake up ; Process after wakeup , You need to move out of the waiting queue .

void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
3.４ sleep
Automatic sleep
Linux The simplest way to sleep in the kernel is a macro definition , be called wait_event( There are several variants ); It combines the details of dealing with sleep and the examination of the conditions in which the process is waiting . wait_event The form of :

queue It's the head of the waiting queue ,condition Is the condition , If the wait_event front condition == 0 , Call wait_event after , The current process will sleep , On the contrary, it will not sleep .
 
wait_event(queue, condition);               Set the status of the current process to TASK_UNINTERRUPTIBLE   , then schedule()
 
wait_event_interruptible(queue, condition);                          TASK_INTERRUPTIBLE     , then schedule()
 
wait_event_timeout(queue, condition, timeout);                       TASK_UNINTERRUPTIBLE   , then schedule_timeout()
 
wait_event_interruptible_timeout(queue, condition, timeout);         TASK_INTERRUPTIBLE     , then schedule_timeout()
TASK_INTERRUPTIBLE And TASK_UNINTERRUPTIBLE The difference lies in , Whether its sleep will be interrupted by the signal , Other processes send a signal, such as kill ,TASK_INTERRUPTIBLE Will wake up to deal with . However TASK_UNINTERRUPTIBLE Can't .schedule(), Process scheduling , and schedule_timeout() After scheduling , Wake up automatically after a certain time ( Time out wake up ), If you wake up ,condition Still false , Then continue to sleep , And vice versa .

Manual sleep

DECLARE_WAITQUEUE(name, tsk)   Create a waiting queue ：
tsk Generally, it is current current. This macro defines and initializes a macro named name Waiting queue .
  Will wait for the queue header Join in / remove Waiting in line ：
        void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait);
        void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait);
        void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait);
Set process state ：
        set_current_state(TASK_INTERRUPTIBLE) etc.
Process scheduling ：  
        schedule() perhaps schedule_timeout()
It is more convenient to use automatic sleep .

3.4 Wake up the
When the process enters the waiting queue to sleep , Other processes can actively call the waiting queue header to wake up the first waiting queue item . If it is automatic sleep , First judge condition： If true, execute , Otherwise continue to sleep .

void wake_up(wait_queue_head_t *q)
void wake_up_interruptible(wait_queue_head_t *q)
summary ：
At the beginning of my study , It seems that its function is similar to that of semaphore . Finally, after thinking , Sum up the differences .
Semaphore ： Its function is to protect the critical area , That is, when the critical area is occupied , Other passive threads accessing the critical area sleep . After the semaphore is released , The second thread can access .
Waiting in line ： Is to sleep the current process first , It cannot be executed until the process is awakened by other processes , And it has timeout wake-up function .