馬俊強(qiáng)

摘要：在中斷驅(qū)動(dòng)的程序設(shè)計(jì)中，工作隊(duì)列是一種強(qiáng)有力的工具。但是在Linux2.6.35及其以前的內(nèi)核版本中，每創(chuàng)建一個(gè)工作隊(duì)列就創(chuàng)建與CPU數(shù)目相同的內(nèi)核線程，耗費(fèi)大量的內(nèi)核資源；工作只能嚴(yán)格串行的處理，效率低。為了適應(yīng)大規(guī)模多處理器硬件平臺(tái)，提高處理效率，Linux2.6.36內(nèi)核開發(fā)了受控并發(fā)工作隊(duì)列機(jī)制。這種新機(jī)制由內(nèi)核根據(jù)需要?jiǎng)?chuàng)建或銷毀線程，工作可以并發(fā)的處理，可望替代之前長(zhǎng)期使用的專用線程工具。文章詳細(xì)介紹和剖析新工作隊(duì)列機(jī)制，并通過實(shí)驗(yàn)，對(duì)比新舊工作隊(duì)列機(jī)制的資源消耗和工作效率。結(jié)果表明，新工作隊(duì)列機(jī)制大大減少內(nèi)核資源的耗費(fèi)，提高了處理效率。

關(guān)鍵詞： Linux內(nèi)核； 中斷驅(qū)動(dòng)； 工作隊(duì)列； 受控并發(fā)工作隊(duì)列

中圖分類號(hào)：TP316.81 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）06-1227-04

Analysis and Comparison of the New and Old Work Queue in Linux Kernel

MA Jun-qiang

（School of Information Science and Engineering， Xiamen University， Xiamen 361005， China）

Abstract： Work Queue is a powerful tool in interrupt-driven programming. But in Linux kernels of 2.6.35 and before， it consumes a lot of kernel resources in that whenever a Work Queue is created， the same number of kernel threads as CPUs are created. The efficiency to processing works in Work Queue is low due to strictly sequential processing. In order to adapt the hardware platforms with large-scale multiprocessors and increase the processing efficiency， the Linux kernel of 2.6.36 developed Concurrency Managed Workqueue. With this new mechanism， the kernel creates and destroys the threads according to the processing requirements， and works can be concurrently processed. The new Work Queue is hoped to replace the private thread tools that had been used long time. The paper introduces and analyses this new mechanism in detail， and compares the resource consumes and processing efficiency between the new and old mechanisms by experiments. The results show that the new mechanism of Work Queue greatly reduces consumes of kernel resources and increases the processing efficiency.

Key words： Linux kernel； interrupt-driven； work queue； concurrency managed workqueue

當(dāng)一個(gè)中斷發(fā)生時(shí)，并不是相關(guān)的各個(gè)操作都具有相同的急迫性，把所有的操作都放進(jìn)中斷處理程序本身也不合適。Linux內(nèi)核將整個(gè)中斷處理流程簡(jiǎn)單分為兩個(gè)部分，第一部分是中斷處理程序，稱為上半部（Top Half），在運(yùn)行時(shí)禁止可屏蔽中斷，用于完成關(guān)鍵性的、緊急的處理；其余部分稱為下半部（Bottom Half），在運(yùn)行時(shí)開中斷，主要完成與中斷處理密切相關(guān)的工作，即延后執(zhí)行工作（Deferring Work）。Linux內(nèi)核提供三種不同形式的下半部實(shí)現(xiàn)機(jī)制：軟中斷（Softirq）、Tasklet和工作隊(duì)列（Work Queue）。其中軟中斷和Tasklet運(yùn)行在中斷上下文中，不可阻塞。而工作隊(duì)列由特殊的內(nèi)核線程—工作者線程（Worker Thread）來執(zhí)行，運(yùn)行在進(jìn)程上下文，可以阻塞。但是由于舊工作隊(duì)列機(jī)制的缺陷，其應(yīng)用并不普遍，取而代之的是使用專用線程池，如flush-x：y，bdi-default等。新工作隊(duì)列機(jī)制為內(nèi)核提供一種通用的線程池機(jī)制，以替代這些專用線程池[1]。實(shí)際上，只要涉及中斷驅(qū)動(dòng)的程序設(shè)計(jì)，工作隊(duì)列都是一種強(qiáng)有力的工具，比如在實(shí)時(shí)控制系統(tǒng)中，可以創(chuàng)建工作隊(duì)列方便高效地響應(yīng)和執(zhí)行由外部事件驅(qū)動(dòng)的任務(wù)。文章將重點(diǎn)介紹和分析新工作隊(duì)列機(jī)制。對(duì)新舊工作隊(duì)列機(jī)制的介紹分析，選擇的內(nèi)核版本分別是2.6.36和2.6.35。

工作隊(duì)列的設(shè)計(jì)思想可以類比于現(xiàn)實(shí)中的生產(chǎn)流水線 [2]：流水線相當(dāng)于工作隊(duì)列中的worklist鏈表，加工部件相當(dāng)于中斷發(fā)生時(shí)所產(chǎn)生的工作序列，工人就是工作者線程。當(dāng)中斷發(fā)生時(shí)，內(nèi)核將本次中斷延后執(zhí)行的工作序列，放到worklist工作鏈表中，喚醒工作者線程執(zhí)行工作。工作者線程在執(zhí)行時(shí)可能阻塞；當(dāng)worklist中的工作處理完畢后，工作者線程進(jìn)入空閑狀態(tài)。從Linux 2.5.41內(nèi)核引入工作隊(duì)列直到2.6.35內(nèi)核， 其運(yùn)行機(jī)制沒有大的改動(dòng)，主要缺點(diǎn)是，在有N個(gè)CPU的計(jì)算機(jī)中，每當(dāng)創(chuàng)建一個(gè)工作隊(duì)列時(shí)，就創(chuàng)建N條流水線，為每條流水線創(chuàng)建一個(gè)工作者線程，內(nèi)核可以向這N條流水線提交該種類的工作（由響應(yīng)中斷的CPU決定）。因此，如果創(chuàng)建X個(gè)工作隊(duì)列，則需要?jiǎng)?chuàng)建N * X個(gè)工作者線程，但是只有當(dāng)流水線上有工作時(shí)，線程才運(yùn)行，其余流水線上的線程都處于空閑狀態(tài)。大量的線程需要消耗線程的ID資源和大量?jī)?nèi)存，同時(shí)也會(huì)增加調(diào)度器的負(fù)擔(dān)。這種情況在擁有大量CPU的超級(jí)計(jì)算機(jī)上顯得尤為浪費(fèi)。另一方面，一條流水線上只有一個(gè)工作者線程，因此同一流水線上工作的處理是嚴(yán)格串行的，嚴(yán)重制約處理的效率。

為適應(yīng)大規(guī)模多處理器硬件平臺(tái)，提高工作隊(duì)列的處理效率，從2.6.36內(nèi)核開始對(duì)工作隊(duì)列進(jìn)行徹底的改造。在新的工作隊(duì)列機(jī)制中，內(nèi)核始終維持N + 1條“工作流水線”，即全局每CPU工作隊(duì)列g(shù)cwq（Global Percpu Workqueue，詳見1.1節(jié)）。新機(jī)制的流水線是通用的，所有來自同一個(gè)CPU的中斷所產(chǎn)生的工作序列，都放在這條流水線上。每條流水線上的工作者線程“按需分配”，即當(dāng)一個(gè)工作者線程阻塞時(shí)，可以讓另一個(gè)工作者線程來處理該流水線上剩余的工作。當(dāng)流水線上需要新的工作者線程時(shí)，就創(chuàng)建新線程；而當(dāng)流水線上線程過多時(shí)，就銷毀線程。同一條流水線上可以有多個(gè)工作同時(shí)被指派給多個(gè)工作者線程，當(dāng)然任何時(shí)刻一條流水線上只有一個(gè)工作者線程在運(yùn)行。這種新的工作隊(duì)列機(jī)制稱為受控并發(fā)工作隊(duì)列（Concurrency Managed Workqueue）[3-5]。

1 受控并發(fā)工作隊(duì)列

1.1 全局每CPU工作隊(duì)列（gcwq）

如果計(jì)算機(jī)有N個(gè)CPU，則內(nèi)核創(chuàng)建N + 1個(gè)gcwq，其結(jié)構(gòu)如下所示：

struct global_cwq {

spinlock_t lock；

unsigned int cpu；

struct list_head worklist；

int nr_workers；

int nr_idle；

struct list_head idle_list；

struct hlist_head busy_hash[BUSY_WORKER_HASH_SIZE]；

struct timer_list idle_timer；

struct timer_list mayday_timer；

...

} ____cacheline_aligned_in_smp；

N個(gè)gcwq分別與N個(gè)CPU一一綁定，管理相關(guān)CPU上的工作者線程和中斷產(chǎn)生的工作；第N + 1個(gè)gcwq稱為unbound_global_cwq，其中的工作者線程未與特定的CPU綁定，詳見1.4節(jié)WQ_UNBOUND標(biāo)志說明。雖然gcwq也稱作“工作隊(duì)列”，但是與用戶創(chuàng)建的工作隊(duì)列不同，它是內(nèi)部管理結(jié)構(gòu)，對(duì)用戶不可見。gcwq中的cpu字段表示與其關(guān)聯(lián)的CPU編號(hào)，worklist雙向鏈表存儲(chǔ)由中斷提交到該CPU上的工作，lock字段為保護(hù)gcwq結(jié)構(gòu)體的自旋鎖。每個(gè)gcwq都維護(hù)管理一個(gè)工作者線程池，其中的工作者線程有idle（空閑）和busy（工作）兩種狀態(tài)；idle_list雙向鏈表中管理處于idle狀態(tài)的工作者線程，nr_idle記錄其數(shù)量；為了快速檢索，使用busy_hash哈希鏈表管理處于busy狀態(tài)的工作者線程。這些線程負(fù)責(zé)處理worklist鏈表中工作。nr_workers記錄工作者線程池中線程的數(shù)量。

1.2 新工作隊(duì)列機(jī)制的運(yùn)行

當(dāng)中斷發(fā)生時(shí)，內(nèi)核調(diào)用queue_work函數(shù)將工作序列提交到gcwq。若相關(guān)的線程池中沒有線程，則內(nèi)核創(chuàng)建工作者線程；否則喚醒一個(gè)工作者線程（異常情況處理見1.4節(jié)WQ_RESCUER屬性）。工作者線程調(diào)用worker_thread函數(shù)，該函數(shù)在執(zhí)行中使用gcwq中的自旋鎖進(jìn)行保護(hù)，并完成以下動(dòng)作：

1）線程從idle狀態(tài)變?yōu)閎usy狀態(tài)。

2）對(duì)所屬的gcwq的線程池進(jìn)行檢查管理。設(shè)線程A是當(dāng)前正在執(zhí)行的線程，若worklist上有多個(gè)待處理的工作，則A檢查線程池中是否還有處于idle狀態(tài)的線程，如果存在，設(shè)選中的為線程B；否則A將創(chuàng)建并喚醒一個(gè)新線程B，B在創(chuàng)建后進(jìn)入idle狀態(tài)。因此在處理工作時(shí)，線程池中將保持至少一個(gè)處于idle狀態(tài)的線程待命，以便迅速響應(yīng)和處理worklist上的后繼工作。

3）線程A從gcwq的worklist鏈表中依次取出未處理的工作進(jìn)行處理。當(dāng)處理完worklist中所有的工作后，將再一次對(duì)線程池進(jìn)行檢查管理，然后進(jìn)入idle狀態(tài)并休眠。

4）一旦線程A阻塞且worklist上還有待處理的工作，則線程B開始運(yùn)行，它調(diào)用worker_thread函數(shù)重復(fù)以上過程。

如3）所述，當(dāng)工作者線程處理完全部工作后將對(duì)線程池進(jìn)行一次檢查管理。此時(shí)如果gcwq中空閑的工作者線程過多，其判斷條件是nr_idle > 2且（nr_idle - 2） * 4 >= nr_idle，則gcwq將銷毀idle狀態(tài)持續(xù)時(shí)間超過5分鐘的工作者線程。每個(gè)gcwq的線程池最終將維護(hù)兩個(gè)處于idle狀態(tài)的工作者線程。

1.3新工作隊(duì)列機(jī)制的改進(jìn)

1）由內(nèi)核根據(jù)處理需求，控制工作者線程的創(chuàng)建和銷毀，避免創(chuàng)建過多的內(nèi)核線程。在工作隊(duì)列空閑時(shí)，新機(jī)制中的線程數(shù)大致為（ N + 1 ） * 2，工作隊(duì)列數(shù)量與內(nèi)核線程數(shù)基本無關(guān)（除非工作隊(duì)列設(shè)置WQ_RESCUER標(biāo)志，見1.4節(jié)）。這個(gè)改進(jìn)大大減少內(nèi)核資源的消耗。

2）同一CPU上一個(gè)工作隊(duì)列中的工作可以并發(fā)的處理。這種并發(fā)處理方式相比舊機(jī)制的嚴(yán)格串行，提高了處理效率。在每個(gè)CPU上，一個(gè)工作隊(duì)列中可并發(fā)處理的工作數(shù)目是有限制的（見1.4節(jié)max_active參數(shù)），當(dāng)達(dá)到限制時(shí)，將不再喚醒新的工作者線程。

3）創(chuàng)建工作隊(duì)列時(shí)可以指定工作隊(duì)列的屬性。用戶可以根據(jù)工作性質(zhì)的不同創(chuàng)建不同的工作隊(duì)列，如高優(yōu)先級(jí)的（WQ_HIGHPRI）、未綁定的（WQ_UNBOUND）、不可重入的（WQ_NON_REENTRANT）、帶救援者線程的（WQ_RESCUER）[3][5]等。在圖1中，gcwq的worklist鏈表中的工作分為高優(yōu)先級(jí)的工作和普通優(yōu)先級(jí)的工作兩類，高優(yōu)先級(jí)的工作排在鏈表頭部，普通優(yōu)先級(jí)的工作排在鏈表尾部，同一類別的工作之間按照提交的順序排列。而在舊工作隊(duì)列機(jī)制中則沒有這些屬性，工作按照提交的順序被執(zhí)行。

圖1 gcwq的worklist鏈表中的工作分布

4）新工作隊(duì)列機(jī)制提供4個(gè)預(yù)定義工作隊(duì)列，方便用戶使用工作隊(duì)列。這四個(gè)預(yù)定義的工作隊(duì)列分別為events、events_long、events_nrt、events_unbound。其中events是普通工作隊(duì)列，要求其中的工作執(zhí)行時(shí)間盡量短；需要長(zhǎng)時(shí)間處理的工作可以提交到events_long隊(duì)列中；events_nrt是不可重入工作隊(duì)列，其中的工作將不會(huì)在多個(gè)CPU上并發(fā)執(zhí)行；events_unbound隊(duì)列就是設(shè)置了WQ_UNBOUND標(biāo)志的隊(duì)列，只要處理的工作數(shù)量未達(dá)到限制，其中的工作就可以立即被處理。用戶可以根據(jù)需要使用這4個(gè)預(yù)定義工作隊(duì)列，當(dāng)然也可以自己創(chuàng)建工作隊(duì)列。

1.4 創(chuàng)建工作隊(duì)列

調(diào)用下面的宏創(chuàng)建一個(gè)工作隊(duì)列：alloc_workqueue（name， flags， max_active）。

參數(shù)name：指定工作隊(duì)列的名稱。

參數(shù)flags：標(biāo)志位，指明工作隊(duì)列的屬性，摘要解釋如下：

WQ_NON_REENTRANT：默認(rèn)時(shí)，工作隊(duì)列中的多個(gè)同一種類的工作，在一個(gè)CPU上不可重入，但是允許在不同CPU上重入（即允許在不同CPU上并發(fā)的處理）。如果設(shè)置此標(biāo)志，則工作隊(duì)列中的多個(gè)同一種類的工作在不同CPU上也不可重入。此時(shí)工作可能需要從響應(yīng)中斷的CPU遷移到另一個(gè)CPU上：當(dāng)中斷產(chǎn)生工作時(shí)，如果以前產(chǎn)生的同類工作正在另一個(gè)CPU上處理，則將該工作提交到這個(gè)CPU上。

WQ_UNBOUND：如果設(shè)置此標(biāo)志，則內(nèi)核將為工作隊(duì)列設(shè)置WQ_HIGHPRI標(biāo)志，其上的工作都將插入到unbound_global_cwq的worklist鏈表上。unbound_global_cwq中工作將按照提交的順序被處理。通常，為了更好地利用CPU緩存，工作在所提交的CPU上處理，而unbound_global_cwq中的工作者線程未與特定的CPU綁定，其中的工作可能運(yùn)行在任意一個(gè)CPU上，因此無法有效利用CPU緩存。此標(biāo)志是為需要大量CPU周期的工作設(shè)置的，此時(shí)各個(gè)CPU的負(fù)載均衡更為重要，所以此類工作最好由調(diào)度器決定在哪一個(gè)CPU上運(yùn)行。

WQ_RESCUER：如果設(shè)置此標(biāo)志，則為工作隊(duì)列專門創(chuàng)建一個(gè)救援者線程（Rescure Thread）。創(chuàng)建救援者線程的目的是避免長(zhǎng)時(shí)間的等待或死鎖。由于內(nèi)核創(chuàng)建工作者線程時(shí)使用GFP_KERNEL標(biāo)志來分配內(nèi)存，可能導(dǎo)致創(chuàng)建過程長(zhǎng)時(shí)間阻塞，因此在創(chuàng)建時(shí)，內(nèi)核設(shè)置一個(gè)定時(shí)器mayday_timer。如果定時(shí)器超時(shí)，但線程仍未創(chuàng)建成功，那么內(nèi)核就喚醒各個(gè)工作隊(duì)列中的救援者線程，執(zhí)行rescuer_thread函數(shù)處理的剩余工作。所有在處理時(shí)可能與內(nèi)存回收?qǐng)?zhí)行路徑重疊的工作隊(duì)列，必須設(shè)置這個(gè)標(biāo)志。

WQ_HIGHPRI：如果設(shè)置此標(biāo)志，則該工作隊(duì)列中的工作都是高優(yōu)先級(jí)的，其中的工作將被插入到目標(biāo)gcwq的工作列表worklist的最后一個(gè)高優(yōu)先級(jí)工作后面，即高優(yōu)先級(jí)的工作排在worklist隊(duì)列頭，且依據(jù)提交的順序被處理。只要資源可用，總是盡可能快地處理高優(yōu)先級(jí)工作。

參數(shù)max_active：一個(gè)工作隊(duì)列在每個(gè)CPU上可能并發(fā)執(zhí)行的最大工作數(shù)目。對(duì)綁定的工作隊(duì)列，max_active最大值512；默認(rèn)值為0，此時(shí)max_active為256；對(duì)于未綁定的工作隊(duì)列，max_active的最大值為max（512， 4 * num_possible_cpus（））。建議內(nèi)核開發(fā)者使用默認(rèn)值。

2 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果

通過兩個(gè)實(shí)驗(yàn)來對(duì)比新舊工作隊(duì)列機(jī)制的資源消耗和工作效率，實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境

2.1新舊工作隊(duì)列機(jī)制中可創(chuàng)建的最大工作隊(duì)列數(shù)

表2 最大工作隊(duì)列數(shù)

在本實(shí)驗(yàn)中，測(cè)試機(jī)器的pid_max設(shè)置為32768。由表2可以看出，在舊工作隊(duì)列機(jī)制中，可創(chuàng)建的工作隊(duì)列數(shù)目隨著CPU數(shù)目的增加而減少，主要受限于內(nèi)核可創(chuàng)建的線程數(shù)；在新工作隊(duì)列機(jī)制中，可創(chuàng)建的工作隊(duì)列數(shù)目隨著內(nèi)存的增加而增加，與系統(tǒng)可創(chuàng)建的最大線程數(shù)無關(guān)。新工作隊(duì)列機(jī)制中的最大工作隊(duì)列數(shù)主要受限于內(nèi)核可分配的percpu空間。這是因?yàn)槊縿?chuàng)建一個(gè)工作隊(duì)列都需要分配一定大小且地址對(duì)齊的percpu空間，隨著創(chuàng)建的工作隊(duì)列數(shù)的增加，內(nèi)核中將沒有可用的percpu空間，從而導(dǎo)致創(chuàng)建工作隊(duì)列失敗。

2.2在新舊工作隊(duì)列機(jī)制中，同一CPU上一個(gè)工作隊(duì)列中10個(gè)工作的執(zhí)行效率的比較

實(shí)驗(yàn)所用的工作隊(duì)列不帶任何標(biāo)志位，每個(gè)工作分別有三種休眠時(shí)間0s、1s或5s，用來模擬處理的時(shí)間。新工作隊(duì)列機(jī)制的并發(fā)工作數(shù)有1、5、256三種情況。實(shí)驗(yàn)結(jié)果見表3。

表3 同一CPU上一個(gè)工作隊(duì)列中10個(gè)工作的處理時(shí)間

如果所有工作都不休眠或者max_active等于1，則新舊工作隊(duì)列機(jī)制下10個(gè)工作的處理時(shí)間基本相同。當(dāng)工作有休眠且max_active大于1時(shí)，一旦處理工作的線程休眠，則內(nèi)核立即喚醒新的線程執(zhí)行后繼的工作，直到正在執(zhí)行的工作數(shù)等于max_active。實(shí)驗(yàn)結(jié)果表明，新工作隊(duì)列機(jī)制可以顯著提高處理的效率。

3 結(jié)束語

舊工作隊(duì)列機(jī)制應(yīng)用于大規(guī)模多處理器硬件平臺(tái)會(huì)耗費(fèi)大量的內(nèi)核資源，工作的處理效率也很低。以往的補(bǔ)救方法是使用專用線程工具。Linux2.6.36內(nèi)核開發(fā)受控并發(fā)工作隊(duì)列，由內(nèi)核“按需分配”工作者線程，大大減少內(nèi)核資源的耗費(fèi)；同時(shí)，工作可以并發(fā)處理，提高了處理效率。新機(jī)制提供的通用的線程池有望替代內(nèi)核中專用線程池，成為中斷驅(qū)動(dòng)程序設(shè)計(jì)的強(qiáng)有力的工具。

新工作隊(duì)列機(jī)制的設(shè)計(jì)也存在一些缺陷。首先，優(yōu)先級(jí)只分為高優(yōu)先級(jí)和普通優(yōu)先級(jí)，略顯粗糙，無法區(qū)分一個(gè)工作隊(duì)列中不同工作之間的差別。其次，工作隊(duì)列的優(yōu)先級(jí)與內(nèi)核線程的優(yōu)先級(jí)無關(guān)，在資源比較緊張時(shí)，可能無法滿足硬實(shí)時(shí)任務(wù)的需要。再有，max_active參數(shù)的設(shè)置不是針對(duì)一個(gè)工作隊(duì)列，而是針對(duì)一個(gè)CPU上所有工作隊(duì)列，也不夠靈活。如果這些問題得到改進(jìn)，新機(jī)制將能更方便地應(yīng)用于實(shí)時(shí)系統(tǒng)。

參考文獻(xiàn)：

[1] Tejun Heo .backing-dev： replace private thread pool with workqueue.txt [EB/OL]. [2010-09].http：//lwn.net/Articles/403653.

[2] 陳學(xué)松.深入Linux設(shè)備驅(qū)動(dòng)程序內(nèi)核機(jī)制[M].北京：電子工業(yè)出版社，2012：214-230.

[3] Tejun Heo.workqueue.txt [EB/OL]. [2010-09].http：//lxr.linux.no/linux+v-2.6.36.4/Documentation/workqueue.txt.

[4] Jonathan Corbet .Concurrency-managed workqueues [EB/OL]. [2010-09].http：//lwn.net/Articles/355700.

[5] Jonathan Corbet .Working on workqueues [EB/OL]. [2010-09].http：//lwn.net/Articles/403891.