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