基本介紹
- 中文名：佇列機制
- 外文名：queues mechanism
- 1：定義
- 2：分類
- 3：實現
定義,分類,工作佇列機制,訊息佇列機制,
定義
佇列是一種數據結構，它具有先進先出的特點，是一種套用很廣泛的結構。在計算機或計算機之間，為了提高計算機或計算機之間的工作效率，我們經常採用佇列機制。佇列機制簡單來說是基於佇列，利用某種方案來提高工作效率。例如作業系統中作業、進程和執行緒基於佇列機制調度。
分類
關於佇列機制的分類有很多選擇，這裡主要從佇列機製作用來分類，分為以下兩類：
工作佇列機制
核心中提供了許多機制來提供延遲執行，如中斷的下半部處理可延遲中斷上下文中的部分工作；定時器可指定延遲一定時間後執行某工作；工作佇列則允許在進程上下文環境下延遲執行等。除此之外，核心中還曾短暫出現過慢工作機制 (slow work mechanism)，還有異步函式調用 (asynchronous function calls) 以及各種私有實現的執行緒池等。在上面列出的如此多的核心基礎組件中，使用最多則是工作佇列。
下面是一些有關工作佇列的短語
workqueues：所有工作項被 ( 需要被執行的工作 ) 排列於該佇列，因此稱作工作佇列 (workqueues) 。
worker thread：工作者執行緒 (workerthread) 是一個用於執行工作佇列中各個工作項的核心執行緒，當工作佇列中沒有工作項時，該執行緒將變為 idle 狀態。
single threaded(ST):工作者執行緒的表現形式之一，在系統範圍內，只有一個工作者執行緒為工作佇列服務。
multi threaded(MT)：工作者執行緒的表現形式之一，在多 CPU 系統上每個 CPU 上都有一個工作者執行緒為工作佇列服務。
工作佇列機制的準則如下：
面向用戶的準則
(1) 周轉時間短。通常把周轉時間的長短作為評價批處理系統的性能、選擇作業調度方式與算法的重要準則之一。所謂周轉時間，是指從作業被提交給系統開始，到作業完成為止的這段時間間隔(稱為作業周轉時間)。它包括四部分時間：作業在外存後備佇列上等待(作業)調度的時間，進程在就緒佇列上等待進程調度的時間，進程在CPU 上執行的時間，以及進程等待I/O 操作完成的時間。其中的後三項在一個作業的整個處理過程中可能會發生多次。
(2) 回響時間快。常把回響時間的長短用來評價分時系統的性能，這是選擇分時系統中進程調度算法的重要準則之一。所謂回響時間，是從用戶通過鍵盤提交一個請求開始，直至系統首次產生回響為止的時間，或者說，直到螢幕上顯示出結果為止的一段時間間隔。它包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的回響信息回送到終端顯示器的時間。
(3) 截止時間的保證。這是評價實時系統性能的重要指標，因而是選擇實時調度算法的重要準則。所謂截止時間，是指某任務必須開始執行的最遲時間，或必須完成的最遲時間。對於嚴格的實時系統，其調度方式和調度算法必須能保證這一點，否則將可能造成難以預料的後果。
(4) 優先權準則。在批處理、分時和實時系統中選擇調度算法時，都可遵循優先權準則，以便讓某些緊急的作業能得到及時處理。在要求較嚴格的場合，往往還須選擇搶占式調度方式，才能保證緊急作業得到及時處理。
面向系統的準則
(1) 系統吞吐量高。這是用於評價批處理系統性能的另一個重要指標，因而是選擇批處理作業調度的重要準則。由於吞吐量是指在單位時間內系統所完成的作業數，因而它與批處理作業的平均長度具有密切關係。對於大型作業，一般吞吐量約為每小時一道作業；對於中、小型作業，其吞吐量則可能達到數十道作業之多。作業調度的方式和算法對吞吐量的大小也將產生較大影響。事實上，對於同一批作業，若採用了較好的調度方式和算法，則可顯著地提高系統的吞吐量。
(2) 處理機利用率好。對於大、中型多用戶系統，由於CPU 價格十分昂貴，致使處理機的利用率成為衡量系統性能的十分重要的指標；而調度方式和算法對處理機的利用率起著十分重要的作用。在實際系統中，CPU的利用率一般在40%(系統負荷較輕)到90%之間。在大、中型系統中，在選擇調度方式和算法時，應考慮到這一準則。但對於單用戶微機或某些實時系統，則此準則就不那么重要了。
(3) 各類資源的平衡利用。在大、中型系統中，不僅要使處理機的利用率高，而且還應能有效地利用其它各類資源，如記憶體、外存和I/O 設備等。選擇適當的調度方式和算法可以保持系統中各類資源都處於忙碌狀態。但對於微型機和某些實時系統而言，該準則並不重要。
訊息佇列機制
訊息佇列機制是在多個不同的套用之間實現相互通信的一種異步傳輸模式，相互通信的套用可以分布於同一台機器上，也可以分布於相連的網路空間中的任一位置。
常用的通知機制中比較典型的有以下幾種：
1. signal
這種機制下，我們向被通知進程傳送一個特殊的signal（比如SIGUSR1），這樣正在睡眠的讀進程就會被信號中斷，然後醒來。該方法的優點是：讀進程不需要監聽一個額外的eventfd，適合一些不方便使用eventfd的場景；另外，用戶可以選擇是使用實時信號（SIGRTMIN+1），還是使用非實時信號（SIGUSR1）。
該方法的缺點是：通知不實時。因為信號的檢查只有在中斷返回的時候才會進行，這個時間跟作業系統的HZ、jiffies有關。
2. socket
這種機制下，寫進程往socket（domain socket）寫一個字元，然後讀進程通過epoll得到數據到達的通知。
3. fifo
這種機制跟socket類似，寫進程往fifo中寫一個字元，然後讀進程通過epoll得到數據到達的通知。
4. pipe
跟2、3差不多。
5. eventfd/signalfd
跟前面差不多，不過是核心幫我們事先fifo、signal通知，只有比較新的核心版本才支持。這種方式存在的問題是需要在不同進程間傳遞句柄，非fork方式實現比較複雜。
上面這幾種方式的共性是都需要陷入核心，被通知進程只有在核心態才能接收通知，對於處理性能要求高的場景，應該少用通知。所以，當然就看業務場景傳送通知的開銷是不是很大了。如果請求量很大，讀進程一直忙於處理，不會頻繁觸發通知，那就很合適了。
實現
受控並發工作佇列的實現
全局每CPU工作佇列(gcwq) 如果計算機有N個CPU，則核心創建N + 1個gcwq，其結構如下所示：
structglobal_cwq{spinlock_tlock;unsignedintcpu;structlist_headworklist;intnr_workers;intnr_idle;structlist_headidle_list;structhlist_headbusy_hash[BUSY_WORKER_HASH_SIZE];structtimer_listidle_timer;structtimer_listmayday_timer;...}____cacheline_aligned_in_smp;
N個gcwq分別與N個CPU一一綁定，管理相關CPU上的工作者執行緒和中斷產生的工作；第N + 1個gcwq稱為unbound_global_cwq，其中的工作者執行緒未與特定的CPU綁定，WQ_UNBOUND為標誌說明。雖然gcwq也稱作“工作佇列”，但是與用戶創建的工作佇列不同，它是內部管理結構，對用戶不可見。gcwq中的cpu欄位表示與其關聯的CPU編號，worklist雙向鍊表存儲由中斷提交到該CPU上的工作，lock欄位為保護gcwq結構體的自旋鎖。每個gcwq都維護管理一個工作者執行緒池，其中的工作者執行緒有idle（空閒）和busy（工作）兩種狀態；idle_list雙向鍊表中管理處於idle狀態的工作者執行緒，nr_idle記錄其數量；為了快速檢索，使用busy_hash哈希鍊表管理處於busy狀態的工作者執行緒。這些執行緒負責處理worklist鍊表中工作。nr_workers記錄工作者執行緒池中執行緒的數量。
工作佇列機制的運行
當中斷髮生時，核心調用queue_work函式將工作序列提交到gcwq。若相關的執行緒池中沒有執行緒，則核心創建工作者執行緒；否則喚醒一個工作者執行緒工作者執行緒調用worker_thread函式，該函式在執行中使用gcwq中的自旋鎖進行保護，並完成以下動作：
1）執行緒從idle狀態變為busy狀態。
2）對所屬的gcwq的執行緒池進行檢查管理。設執行緒A是當前正在執行的執行緒，若worklist上有多個待處理的工作，則A檢查執行緒池中是否還有處於idle狀態的執行緒，如果存在，設選中的為執行緒B；否則A將創建並喚醒一個新執行緒B，B在創建後進入idle狀態。因此在處理工作時，執行緒池中將保持至少一個處於idle狀態的執行緒待命，以便迅速回響和處理worklist上的後繼工作。
3）執行緒A從gcwq的worklist鍊表中依次取出未處理的工作進行處理。當處理完worklist中所有的工作後，將再一次對執行緒池進行檢查管理，然後進入idle狀態並休眠。
4）一旦執行緒A阻塞且worklist上還有待處理的工作，則執行緒B開始運行，它調用worker_thread函式重複以上過程。當工作者執行緒處理完全部工作後將對執行緒池進行一次檢查管理。此時如果gcwq中空閒的工作者執行緒過多，其判斷條件是nr_idle > 2且(nr_idle - 2) * 4 >= nr_idle，則gcwq將銷毀idle狀態持續時間超過5分鐘的工作者執行緒。每個gcwq的執行緒池最終將維護兩個處於idle狀態的工作者執行緒。
特點
1）由核心根據處理需求，控制工作者執行緒的創建和銷毀，避免創建過多的核心執行緒。在工作佇列空閒時，新機制中的執行緒數大致為( N + 1 ) * 2，工作佇列數量與核心執行緒數基本無關（除非工作佇列設定WQ_RESCUER標誌）。這個改進大大減少核心資源的消耗。
2）同一CPU上一個工作佇列中的工作可以並發的處理。這種並發處理方式相比舊機制的嚴格串列，提高了處理效率。在每個CPU上，一個工作佇列中可並發處理的工作數目是有限制的（見1.4節max_active參數），當達到限制時，將不再喚醒新的工作者執行緒。
3）創建工作佇列時可以指定工作佇列的屬性。用戶可以根據工作性質的不同創建不同的工作佇列，如高優先權的（WQ_HIGHPRI）、未綁定的(WQ_UNBOUND)、不可重入的(WQ_NON_REENTRANT)、帶救援者執行緒的（WQ_RESCUER）。gcwq的worklist鍊表中的工作分為高優先權的工作和普通優先權的工作兩類，高優先權的工作排在鍊表頭部，普通優先權的工作排在鍊表尾部，同一類別的工作之間按照提交的順序排列。而在舊工作佇列機制中則沒有這些屬性，工作按照提交的順序被執行。
4）新工作佇列機制提供4個預定義工作佇列，方便用戶使用工作佇列。這四個預定義的工作佇列分別為events、events_long、events_nrt、events_unbound。其中events 是普通工作佇列，要求其中的工作執行時間儘量短；需要長時間處理的工作可以提交到events_long佇列中；events_nrt是不可重入工作佇列，其中的工作將不會在多個CPU上並發執行；events_unbound佇列就是設定了WQ_UNBOUND標誌的佇列，只要處理的工作數量未達到限制，其中的工作就可以立即被處理。用戶可以根據需要使用這4個預定義工作佇列，當然也可以自己創建工作佇列。
