等待隊列
| | | 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狀態(tài)的所有進(jìn)程組織在一起。當要把其他狀態(tài)的進(jìn)程分組時(shí)，不同的狀態(tài)要求不同的處理，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 狀態(tài)的進(jìn)程不鏈接在專(zhuān)門(mén)的鏈表中。沒(méi)有必要把處于這三種狀態(tài)的進(jìn)程進(jìn)行分組。因為對于stopped, zombie, and dead進(jìn)程而言，父進(jìn)程只能通過(guò)PID或者子進(jìn)程鏈表訪(fǎng)問(wèn)他們。
* 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狀態(tài)的進(jìn)程再分成很多類(lèi)，每一類(lèi)對應一個(gè)特定的事件。在這種情況下，進(jìn)程狀態(tài)提供的信息滿(mǎn)足不了對進(jìn)程的快速搜 索，因此，有必要引入另外的進(jìn)程鏈表。這些附加的鏈表叫等待隊列(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.
等待隊列在內核中有很多用途，尤其適合用于中斷處理、進(jìn)程同步及定時(shí)。我們在這里只說(shuō)，進(jìn)程經(jīng)常必須等待某些事件的發(fā)生。例如，等待一個(gè)磁盤(pán)操作的終止，等待釋放系統資源，或者等待時(shí)間經(jīng)過(guò)固定的間隔。
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 實(shí)現了在事件上的條件等待: 希望等待特定事件的進(jìn)程把自己放進(jìn)合適的等待隊列，并放棄控制全。因此，等待隊列表示一組睡眠的進(jìn)程，當某一條件為真時(shí)，由內核喚醒它們。
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:
等待隊列由循環(huán)鏈表實(shí)現，其元素包括指向進(jìn)程描述符的指針。每個(gè)等待隊列都有一個(gè)等待隊列頭(wait queue head),等待隊列頭是一個(gè)類(lèi)型為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.
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.
等待隊列鏈表的每個(gè)元素代表一個(gè)睡眠進(jìn)程，該進(jìn)程等待某一事件的發(fā)生；它的描述符地址存放在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.)
然而，要喚醒等待隊列中所有睡眠的進(jìn)程有時(shí)并不方便。例如，如果兩個(gè)或多個(gè)進(jìn)程正在等待互斥訪(fǎng)問(wèn)某一要釋放的資源，僅喚醒等待隊列中一個(gè)進(jìn)程才有意義。這 個(gè)進(jìn)程占有資源，而其他進(jìn)程繼續睡眠.(這就避免了所謂的"雷鳴般群獸"問(wèn)題，即喚醒多個(gè)進(jìn)程只為了競爭一個(gè)資源，而這個(gè)資源只能有一個(gè)進(jìn)程訪(fǎng)問(wèn)，結果是 其他進(jìn)程必須再次回去睡眠.)
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.
因此，有兩種睡眠進(jìn)程: 互斥進(jìn)程(等待隊列元素的flag字段為1)由內核有選擇地喚醒，而非互斥進(jìn)程(flag值為0)總是由內核在事件發(fā)生時(shí)喚醒。
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)宏定義一個(gè)新的等待隊列，該宏靜態(tài)地聲明和初始化名為name的等待隊列頭變量。 init_waitqueue_head()函數用于初始化已動(dòng)態(tài)分配的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.
等待隊列可以通過(guò) DECLARE_WAITQUEUE()靜態(tài)創(chuàng )建,也可以用 init_waitqueue_head()動(dòng)態(tài)創(chuàng )建。進(jìn)程把自己放入等待隊列中并設置成不可執行狀態(tài)。
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()函數把一個(gè)非互斥進(jìn)程插入等待隊列鏈表的第一個(gè)位置
The add_wait_queue_exclusive( ) function inserts an exclusive process in the last position of a wait queue list.
add_wait_queue_exclusive( )函數把一個(gè)互斥進(jìn)程插入等待隊列鏈表的最后一個(gè)位置
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( )函數從等待隊列鏈表中刪除一個(gè)進(jìn)程
The waitqueue_active( ) function checks whether a given wait queue list is empty.
waitqueue_active( )函數檢查一個(gè)給定的等待隊列是否為空
A process wishing to wait for a specific condition can invoke any of the functions shown in the following list.
希望等待一個(gè)特定事件的進(jìn)程能調用下列函數中的任一個(gè):
* 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.
該函數把當前進(jìn)程的狀態(tài)設置為T(mén)ASK_UNINTERRUPTIBLE，并把它插入到特定的等待隊列。然后，它調用調度程序，而調度程序重新開(kāi)始另一個(gè)進(jìn)程的執行。當睡眠進(jìn)程被喚醒時(shí)，調度程序重新開(kāi)始執行sleep_on()函數，把該進(jìn)程隊列中刪除。
* 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()把 當前進(jìn)程的狀態(tài)設置為T(mén)ASK_INTERRUPTIBLE而不是TASK_UNINTERRUPTIBLE，因此，接受一個(gè)信號就可以喚醒當前進(jìn)程
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狀態(tài)的睡眠進(jìn)程；如果宏的名字中不含字符串"interruptible",則還將考慮處于TASK_UNINTERRUPTIBLE狀態(tài)的睡眠進(jìn)程
* 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”字符串的宏喚醒給定數字的具有所需狀態(tài)的互斥進(jìn)程；名字中含有"all"字符串的宏喚醒具有所需狀態(tài)的所有互斥進(jìn)程。最后，名字中不含"nr"或"all"字符串的宏只喚醒具有所需狀態(tài)一個(gè)互斥進(jìn)程
* 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.
| | |
