|
Linux內(nèi)核中的等待隊(duì)列
Linux 內(nèi)核的等待隊(duì)列是以雙循環(huán)鏈表為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，與進(jìn)程調(diào)度機(jī)制緊密結(jié)合，能夠用于實(shí)現(xiàn)核心的異步事件通知機(jī)制。在Linux2.4.21中，等待隊(duì)列在源 代碼樹include/linux/wait.h中，這是一個(gè)通過(guò)list_head連接的典型雙循環(huán)鏈表，如下圖所示。  在這個(gè)鏈表中，有兩種數(shù)據(jù)結(jié)構(gòu)：等待隊(duì)列頭（wait_queue_head_t）和等待隊(duì)列項(xiàng)（wait_queue_t）。等待隊(duì) 列頭和等待隊(duì)列項(xiàng)中都包含一個(gè)list_head類型的域作為"連接件"。由于我們只需要對(duì)隊(duì)列進(jìn)行添加和刪除操作，并不會(huì)修改其中的對(duì)象（等待隊(duì)列 項(xiàng)），因此，我們只需要提供一把保護(hù)整個(gè)基礎(chǔ)設(shè)施和所有對(duì)象的鎖，這把鎖保存在等待隊(duì)列頭中，為wq_lock_t類型。在實(shí)現(xiàn)中，可以支持讀寫鎖 （rwlock）或自旋鎖（spinlock）兩種類型，通過(guò)一個(gè)宏定義來(lái)切換。如果使用讀寫鎖，將wq_lock_t定義為rwlock_t類型；如果 是自旋鎖，將wq_lock_t定義為spinlock_t類型。無(wú)論哪種情況，分別相應(yīng)設(shè)置wq_read_lock、wq_read_unlock、 wq_read_lock_irqsave、wq_read_unlock_irqrestore、wq_write_lock_irq、 wq_write_unlock、wq_write_lock_irqsave和wq_write_unlock_irqrestore等宏。 等待隊(duì)列頭 struct __wait_queue_head { wq_lock_t lock; struct list_head task_list; }; typedef struct __wait_queue_head wait_queue_head_t; 前面已經(jīng)說(shuō)過(guò)，等待隊(duì)列的主體是進(jìn)程，這反映在每個(gè)等待隊(duì)列項(xiàng)中，是一個(gè)任務(wù)結(jié)構(gòu)指針（struct task_struct * task）。flags為該進(jìn)程的等待標(biāo)志，當(dāng)前只支持互斥。 等待隊(duì)列項(xiàng) struct __wait_queue { unsigned int flags; #define WQ_FLAG_EXCLUSIVE 0x01 struct task_struct * task; struct list_head task_list; }; typedef struct __wait_queue wait_queue_t; 聲明和初始化 #define DECLARE_WAITQUEUE(name, tsk) \ wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk) #define __WAITQUEUE_INITIALIZER(name, tsk) { \ task: tsk, \ task_list: { NULL, NULL }, \ __WAITQUEUE_DEBUG_INIT(name)} 通過(guò)DECLARE_WAITQUEUE宏將等待隊(duì)列項(xiàng)初始化成對(duì)應(yīng)的任務(wù)結(jié)構(gòu)，并且用于連接的相關(guān)指針均設(shè)置為空。其中加入了調(diào)試相關(guān)代碼。 #define DECLARE_WAIT_QUEUE_HEAD(name) \ wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name) #define __WAIT_QUEUE_HEAD_INITIALIZER(name) { \ lock: WAITQUEUE_RW_LOCK_UNLOCKED, \ task_list: { &(name).task_list, &(name).task_list }, \ __WAITQUEUE_HEAD_DEBUG_INIT(name)} 通過(guò)DECLARE_WAIT_QUEUE_HEAD宏初始化一個(gè)等待隊(duì)列頭，使得其所在鏈表為空，并設(shè)置鏈表為"未上鎖"狀態(tài)。其中加入了調(diào)試相關(guān)代碼。 static inline void init_waitqueue_head(wait_queue_head_t *q) 該函數(shù)初始化一個(gè)已經(jīng)存在的等待隊(duì)列頭，它將整個(gè)隊(duì)列設(shè)置為"未上鎖"狀態(tài)，并將鏈表指針prev和next指向它自身。 { q->lock = WAITQUEUE_RW_LOCK_UNLOCKED; INIT_LIST_HEAD(&q->task_list); } static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p) 該函數(shù)初始化一個(gè)已經(jīng)存在的等待隊(duì)列項(xiàng)，它設(shè)置對(duì)應(yīng)的任務(wù)結(jié)構(gòu)，同時(shí)將標(biāo)志位清0。 { q->flags = 0; q->task = p; } static inline int waitqueue_active(wait_queue_head_t *q) 該函數(shù)檢查等待隊(duì)列是否為空。 { return !list_empty(&q->task_list); } static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new) 將指定的等待隊(duì)列項(xiàng)new添加到等待隊(duì)列頭head所在的鏈表頭部，該函數(shù)假設(shè)已經(jīng)獲得鎖。 { list_add(&new->task_list, &head->task_list); } static inline void __add_wait_queue_tail(wait_queue_head_t *head, wait_queue_t *new) 將指定的等待隊(duì)列項(xiàng)new添加到等待隊(duì)列頭head所在的鏈表尾部，該函數(shù)假設(shè)已經(jīng)獲得鎖。 { list_add_tail(&new->task_list, &head->task_list); } static inline void __remove_wait_queue(wait_queue_head_t *head, wait_queue_t *old) 將函數(shù)從等待隊(duì)列頭head所在的鏈表中刪除指定等待隊(duì)列項(xiàng)old，該函數(shù)假設(shè)已經(jīng)獲得鎖，并且old在head所在鏈表中。 { list_del(&old->task_list); } 睡眠和喚醒操作 對(duì) 等待隊(duì)列的操作包括睡眠和喚醒（相關(guān)函數(shù)保存在源代碼樹的/kernel/sched.c和include/linux/sched.h中）。思想是更改 當(dāng)前進(jìn)程（CURRENT）的任務(wù)狀態(tài)，并要求重新調(diào)度，因?yàn)檫@時(shí)這個(gè)進(jìn)程的狀態(tài)已經(jīng)改變，不再在調(diào)度表的就緒隊(duì)列中，因此無(wú)法再獲得執(zhí)行機(jī)會(huì)，進(jìn)入"睡 眠"狀態(tài)，直至被"喚醒"，即其任務(wù)狀態(tài)重新被修改回就緒態(tài)。 常用的睡眠操作有interruptible_sleep_on和 sleep_on。兩個(gè)函數(shù)類似，只不過(guò)前者將進(jìn)程的狀態(tài)從就緒態(tài)（TASK_RUNNING）設(shè)置為TASK_INTERRUPTIBLE，允許通過(guò)發(fā) 送signal喚醒它（即可中斷的睡眠狀態(tài)）；而后者將進(jìn)程的狀態(tài)設(shè)置為TASK_UNINTERRUPTIBLE，在這種狀態(tài)下，不接收任何 singal。以interruptible_sleep_on為例，其展開(kāi)后的代碼是： void interruptible_sleep_on(wait_queue_head_t *q) { unsigned long flags; wait_queue_t wait; /* 構(gòu)造當(dāng)前進(jìn)程對(duì)應(yīng)的等待隊(duì)列項(xiàng) */ init_waitqueue_entry(&wait, current); /* 將當(dāng)前進(jìn)程的狀態(tài)從TASK_RUNNING改為TASK_INTERRUPTIBLE */
current->state = TASK_INTERRUPTIBLE; /* 將等待隊(duì)列項(xiàng)添加到指定鏈表中 */
wq_write_lock_irqsave(&q->lock,flags); __add_wait_queue(q, &wait); wq_write_unlock(&q->lock); /* 進(jìn)程重新調(diào)度，放棄執(zhí)行權(quán) */
schedule(); /* 本進(jìn)程被喚醒，重新獲得執(zhí)行權(quán)，首要之事是將等待隊(duì)列項(xiàng)從鏈表中刪除 */
wq_write_lock_irq(&q->lock); __remove_wait_queue(q, &wait); wq_write_unlock_irqrestore(&q->lock,flags); /* 至此，等待過(guò)程結(jié)束，本進(jìn)程可以正常執(zhí)行下面的邏輯 */ } 對(duì) 應(yīng)的喚醒操作包括wake_up_interruptible和wake_up。wake_up函數(shù)不僅可以喚醒狀態(tài)為 TASK_UNINTERRUPTIBLE的進(jìn)程，而且可以喚醒狀態(tài)為TASK_INTERRUPTIBLE的進(jìn)程。 wake_up_interruptible只負(fù)責(zé)喚醒狀態(tài)為TASK_INTERRUPTIBLE的進(jìn)程。這兩個(gè)宏的定義如下： #define wake_up(x) __wake_up((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1) #define wake_up_interruptible(x) __wake_up((x),TASK_INTERRUPTIBLE, 1) __wake_up函數(shù)主要是獲取隊(duì)列操作的鎖，具體工作是調(diào)用__wake_up_common完成的。 void __wake_up(wait_queue_head_t *q, unsigned int mode, int nr) { if (q) { unsigned long flags; wq_read_lock_irqsave(&q->lock, flags); __wake_up_common(q, mode, nr, 0); wq_read_unlock_irqrestore(&q->lock, flags); } } /* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve number) then we wake all the non-exclusive tasks and one exclusive task. There are circumstances in which we can try to wake a task which has already started to run but is not in state TASK_RUNNING. try_to_wake_up() returns zero in this (rare) case, and we handle it by contonuing to scan the queue. */ static inline void __wake_up_common (wait_queue_head_t *q, unsigned int mode, int nr_exclusive, const int sync) 參數(shù)q表示要操作的等待隊(duì)列，mode表示要喚醒任務(wù)的狀態(tài)，如TASK_UNINTERRUPTIBLE或TASK_INTERRUPTIBLE等。nr_exclusive是要喚醒的互斥進(jìn)程數(shù)目，在這之前遇到的非互斥進(jìn)程將被無(wú)條件喚醒。sync表示？？？ { struct list_head *tmp; struct task_struct *p; CHECK_MAGIC_WQHEAD(q);
WQ_CHECK_LIST_HEAD(&q->task_list); /* 遍歷等待隊(duì)列 */
list_for_each(tmp,&q->task_list) { unsigned int state; /* 獲得當(dāng)前等待隊(duì)列項(xiàng) */ wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list); CHECK_MAGIC(curr->__magic);
/* 獲得對(duì)應(yīng)的進(jìn)程 */ p = curr->task; state = p->state; /* 如果我們需要處理這種狀態(tài)的進(jìn)程 */
if (state & mode) { WQ_NOTE_WAKER(curr); if (try_to_wake_up(p, sync) && (curr->flags&WQ_FLAG_EXCLUSIVE) && !--nr_exclusive) break; } } } /* 喚醒一個(gè)進(jìn)程，將它放到運(yùn)行隊(duì)列中，如果它還不在運(yùn)行隊(duì)列的話。"當(dāng)前"進(jìn)程總是在運(yùn)行隊(duì)列中的（except when the
actual re-schedule is in progress)，and as such you're allowed to do the
simpler "current->state = TASK_RUNNING" to mark yourself runnable
without the overhead of this. */
static inline int try_to_wake_up(struct task_struct * p, int synchronous) { unsigned long flags; int success = 0; /* 由于我們需要操作運(yùn)行隊(duì)列，必須獲得對(duì)應(yīng)的鎖 */
spin_lock_irqsave(&runqueue_lock, flags); /* 將進(jìn)程狀態(tài)設(shè)置為TASK_RUNNING */ p->state = TASK_RUNNING; /* 如果進(jìn)程已經(jīng)在運(yùn)行隊(duì)列中，釋放鎖退出 */ if (task_on_runqueue(p)) goto out; /* 否則將進(jìn)程添加到運(yùn)行隊(duì)列中 */ add_to_runqueue(p); /* 如果設(shè)置了同步標(biāo)志 */
if (!synchronous || !(p->cpus_allowed & (1UL << smp_processor_id()))) reschedule_idle(p); /* 喚醒成功，釋放鎖退出 */ success = 1; out: spin_unlock_irqrestore(&runqueue_lock, flags); return success; } 等待隊(duì)列應(yīng)用模式 等待隊(duì)列的的應(yīng)用涉及兩個(gè)進(jìn)程，假設(shè)為A和B。A是資源的消費(fèi)者，B是資源的生產(chǎn)者。A在消費(fèi)的時(shí)候必須確保資源已經(jīng)生產(chǎn)出來(lái)，為此定義一個(gè)資源等待隊(duì)列。這個(gè)隊(duì)列同時(shí)要被進(jìn)程A和進(jìn)程B使用，我們可以將它定義為一個(gè)全局變量。 DECLARE_WAIT_QUEUE_HEAD(rsc_queue); /* 全局變量 */ 在進(jìn)程A中，執(zhí)行邏輯如下： while (resource is unavaiable) { interruptible_sleep_on( &wq ); } consume_resource(); 在進(jìn)程B中，執(zhí)行邏輯如下： produce_resource(); wake_up_interruptible( &wq ); |
|
|
