Linux等待队列

How Processes Are Organized
------------------------------------   
    The runqueue lists group all processes in a TASK_RUNNING state. When it comes to grouping processes in other states, the various states call for different types of treatment, with Linux opting for one of the choices shown in the following list.
    运行队列链表把处于TASK_RUNNING状态的所有进程组织在一起。当要把其他状态的进程分组时，不同的状态要求不同的处理，Linux选择了下列方式之一:
    * Processes in a TASK_STOPPED, EXIT_ZOMBIE, or EXIT_DEAD state are not linked in specific lists. There is no need to group processes in any of these three states, because stopped, zombie, and dead processes are accessed only via PID or via linked lists of the child processes for a particular parent.
    * TASK_STOPPED, EXIT_ZOMBIE, or EXIT_DEAD 状态的进程不链接在专门的链表中。没有必要把处于这三种状态的进程进行分组。因为对于stopped, zombie, and dead进程而言，父进程只能通过PID或者子进程链表访问他们。

    * Processes in a TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE state are subdivided into many classes, each of which corresponds to a specific event. In this case, the process state does not provide enough information to retrieve the process quickly, so it is necessary to introduce additional lists of processes. These are called wait queues and are discussed next.
    * 把TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE状态的进程再分成很多类，每一类对应一个特定的事件。在这种情况下，进程状态提供的信息满足不了对进程的快速搜 索，因此，有必要引入另外的进程链表。这些附加的链表叫等待队列(wait queue)

Wait queues
------------------------------------
    Wait queues have several uses in the kernel, particularly for interrupt handling, process synchronization, and timing. We'll just say here that a process must often wait for some event to occur, such as for a disk operation to terminate, a system resource to be released, or a fixed interval of time to elapse.
     等待队列在内核中有很多用途，尤其适合用于中断处理、进程同步及定时。我们在这里只说，进程经常必须等待某些事件的发生。例如，等待一个磁盘操作的终止，等待释放系统资源，或者等待时间经过固定的间隔。
    Wait queues implement conditional waits on events: a process wishing to wait for a specific event places itself in the proper wait queue and relinquishes control. Therefore, a wait queue represents a set of sleeping processes, which are woken up by the kernel when some condition becomes true.
    Wait queues 实现了在事件上的条件等待: 希望等待特定事件的进程把自己放进合适的等待队列，并放弃控制全。因此，等待队列表示一组睡眠的进程，当某一条件为真时，由内核唤醒它们。
   
    Wait queues are implemented as doubly linked lists whose elements include pointers to process descriptors. Each wait queue is identified by a wait queue head, a data structure of type wait_queue_head_t:
    等待队列由循环链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头(wait queue head),等待队列头是一个类型为wait_queue_head_t的数据结构:

• wait_queue_head_t

    struct __wait_queue_head {
        spinlock_t lock;
        struct list_head task_list;
    };
    typedef struct __wait_queue_head wait_queue_head_t;

wait_queue_head_t.lock
    Because wait queues are modified by interrupt handlers as well as by major kernel functions, the doubly linked lists must be protected from concurrent accesses. Synchronization is achieved by the lock spin lock in the wait queue head.

• wait_queue_t

    Elements of a wait queue list are of type wait_queue_t:

    struct __wait_queue {
        unsigned int flags;
        struct task_struct * task;
        wait_queue_func_t func;
        struct list_head task_list;
    };
    typedef struct __wait_queue wait_queue_t;   
   
    Each element in the wait queue list represents a sleeping process, which is waiting for some event to occur; its descriptor address is stored in the task field. The task_list field contains the pointers that link this element to the list of processes waiting for the same event. 
    等待队列链表的每个元素代表一个睡眠进程，该进程等待某一事件的发生；它的描述符地址存放在task字段中。

    However, it is not always convenient to wake up all sleeping processes in a wait queue. For instance, if two or more processes are waiting for exclusive access to some resource to be released, it makes sense to wake up just one process in the wait queue. This process takes the resource, while the other processes continue to sleep. (This avoids a problem known as the "thundering herd," with which multiple processes are wakened only to race for a resource that can be accessed by one of them, with the result that remaining processes must once more be put back to sleep.)
    然而，要唤醒等待队列中所有睡眠的进程有时并不方便。例如，如果两个或多个进程正在等待互斥访问某一要释放的资源，仅唤醒等待队列中一个进程才有意义。这 个进程占有资源，而其他进程继续睡眠.(这就避免了所谓的"雷鸣般群兽"问题，即唤醒多个进程只为了竞争一个资源，而这个资源只能有一个进程访问，结果是 其他进程必须再次回去睡眠.)

wait_queue_t.flags
    Thus, there are two kinds of sleeping processes: exclusive processes (denoted by the value 1 in the flags field of the corresponding wait queue element) are selectively woken up by the kernel, while nonexclusive processes (denoted by the value 0 in the flags field) are always woken up by the kernel when the event occurs.
    因此，有两种睡眠进程: 互斥进程(等待队列元素的flag字段为1)由内核有选择地唤醒，而非互斥进程(flag值为0)总是由内核在事件发生时唤醒。

wait_queue_t.func
    A process waiting for a resource that can be granted to just one process at a time is a typical exclusive process. Processes waiting for an event that may concern any of them are nonexclusive. Consider, for instance, a group of processes that are waiting for the termination of a group of disk block transfers: as soon as the transfers complete, all waiting processes must be woken up. As we'll see next, the func field of a wait queue element is used to specify how the processes sleeping in the wait queue should be woken up.
                        
                       
                               task_struct             task_struct
                               |---------|<--+         |---------|<--+
                               |         |   |         |         |   |
                               |         |   |         |         |   |
                               |         |   |         |         |   |
                               |---------|   |         |---------|   |
                                             |                       |
                           wait_queue_t      |     wait_queue_t      |
                         |---------------|   |   |---------------|   |
 wait_queue_head_t       |    flags      |   |   |    flags      |   |
 |---------------|       |    *task      |---+   |    *task      |---+
 |     lock      |       |    func       |       |    func       |
 |---------------|       |---------------|       |---------------|
 |list_head *next|------>|list_head *next|------>|list_head *next|
 |list_head *prev|<------|list_head *prev|<------|list_head *prev|
 |---------------|       |---------------|       |---------------|




Handling wait queues
------------------------------------
DECLARE_WAITQUEUE()
init_waitqueue_head()
    A new wait queue head may be defined by using the DECLARE_WAIT_QUEUE_HEAD(name) macro, which statically declares a new wait queue head variable called name and initializes its lock and task_list fields. The init_waitqueue_head( ) function may be used to initialize a wait queue head variable that was allocated dynamically.
    可以用DECLARE_WAIT_QUEUE_HEAD(name)宏定义一个新的等待队列，该宏静态地声明和初始化名为name的等待队列头变量。 init_waitqueue_head()函数用于初始化已动态分配的wait queue head变量

    Wait queues are created statically via DECLARE_WAITQUEUE() or dynamically via init_waitqueue_head(). Processes put themselves on a wait queue and mark themselves not runnable.
    等待队列可以通过 DECLARE_WAITQUEUE()静态创建,也可以用 init_waitqueue_head()动态创建。进程把自己放入等待队列中并设置成不可执行状态。

    The init_waitqueue_entry(q, p) function initializes a wait_queue_t structure q as follows:

    q->flags = 0;
    q->task = p;
    q->func = default_wake_function;

add_wait_queue( )
add_wait_queue_exclusive( )
    The add_wait_queue( ) function inserts a nonexclusive process in the first position of a wait queue list.
    add_wait_queue()函数把一个非互斥进程插入等待队列链表的第一个位置

    The add_wait_queue_exclusive( ) function inserts an exclusive process in the last position of a wait queue list.
    add_wait_queue_exclusive( )函数把一个互斥进程插入等待队列链表的最后一个位置

try_to_wake_up( )
    The nonexclusive process p will be awakened by default_wake_function( ), which is a simple wrapper for the try_to_wake_up( ) function

remove_wait_queue( )
    The remove_wait_queue( ) function removes a process from a wait queue list.
    remove_wait_queue( )函数从等待队列链表中删除一个进程




The waitqueue_active( ) function checks whether a given wait queue list is empty.
waitqueue_active( )函数检查一个给定的等待队列是否为空


 
          



A process wishing to wait for a specific condition can invoke any of the functions shown in the following list.
希望等待一个特定事件的进程能调用下列函数中的任一个:

    * The sleep_on( ) function operates on the current process:

    void sleep_on(wait_queue_head_t *wq)
    {
        wait_queue_t wait;
        init_waitqueue_entry(&wait, current);
        current->state = TASK_UNINTERRUPTIBLE;
        add_wait_queue(wq,&wait); /*  wq points to the wait queue head  */
        schedule( );
        remove_wait_queue(wq, &wait);
    }
The function sets the state of the current process to TASK_UNINTERRUPTIBLE and inserts it into the specified wait queue. Then it invokes the scheduler, which resumes the execution of another process. When the sleeping process is awakened, the scheduler resumes execution of the sleep_on( ) function, which removes the process from the wait queue.
该函数把当前进程的状态设置为TASK_UNINTERRUPTIBLE，并把它插入到特定的等待队列。然后，它调用调度程序，而调度程序重新开始另一个进程的执行。当睡眠进程被唤醒时，调度程序重新开始执行sleep_on()函数，把该进程队列中删除。

    * The interruptible_sleep_on( ) function is identical to sleep_on( ), except that it sets the state of the current process to TASK_INTERRUPTIBLE instead of setting it to TASK_UNINTERRUPTIBLE, so that the process also can be woken up by receiving a signal.
    interruptible_sleep_on()与sleep_on()函数基本上是一样的，但是interruptible_sleep_on()把 当前进程的状态设置为TASK_INTERRUPTIBLE而不是TASK_UNINTERRUPTIBLE，因此，接受一个信号就可以唤醒当前进程
   
   







      The kernel awakens processes in the wait queues, putting them in the TASK_RUNNING state, by means of one of the following macros:
 
      wake_up,
      wake_up_nr,
      wake_up_all,
      wake_up_interruptible,
      wake_up_interruptible_nr,
      wake_up_interruptible_all,
      wake_up_interruptible_sync,
      wake_up_locked.
     
      One can understand what each of these nine macros does from its name:

    *   All macros take into consideration sleeping processes in the TASK_INTERRUPTIBLE state; if the macro name does not include the string "interruptible," sleeping processes in the TASK_UNINTERRUPTIBLE state also are considered.
        所有宏都考虑到了处于TASK_INTERRUPTIBLE状态的睡眠进程；如果宏的名字中不含字符串"interruptible",则还将考虑处于TASK_UNINTERRUPTIBLE状态的睡眠进程
    *   All macros wake all nonexclusive processes having the required state
    *   The macros whose name include the string "nr" wake a given number of exclusive processes having the required state; this number is a parameter of the macro. The macros whose names include the string "all" wake all exclusive processes having the required state. Finally, the macros whose names don't include "nr" or "all" wake exactly one exclusive process that has the required state.
        名字中含有“nr”字符串的宏唤醒给定数字的具有所需状态的互斥进程；名字中含有"all"字符串的宏唤醒具有所需状态的所有互斥进程。最后，名字中不含"nr"或"all"字符串的宏只唤醒具有所需状态一个互斥进程
       
    *   The macros whose names don't include the string "sync" check whether the priority of any of the woken processes is higher than that of the processes currently running in the systems and invoke schedule( ) if necessary. These checks are not made by the macro whose name includes the string "sync"; as a result, execution of a high priority process might be slightly delayed.
    *   The wake_up_locked macro is similar to wake_up, except that it is called when the spin lock in wait_queue_head_t is already held.