隊列機制

隊列是一種數據結構，它具有先進先出的特點，是一種應用很廣泛的結構。在計算機或計算機之間，為了提高計算機或計算機之間的工作效率，我們經常採用隊列機制。

關於隊列機制的分類有很多選擇，這裏主要從隊列機制作用來分類，分為以下兩類：

內核中提供了許多機制來提供延遲執行，如中斷的下半部處理可延遲中斷上下文中的部分工作；定時器可指定延遲一定時間後執行某工作；工作隊列則允許在進程上下文環境下延遲執行等。除此之外，內核中還曾短暫出現過慢工作機制 (slow work mechanism)，還有異步函數調用 (asynchronous function calls) 以及各種私有實現的線程池等。在上面列出的如此多的內核基礎組件中，使用最多則是工作隊列。

下面是一些有關工作隊列的短語

workqueues：所有工作項被 ( 需要被執行的工作 ) 排列於該隊列，因此稱作工作隊列 (workqueues) 。

worker thread：工作者線程 (workerthread) 是一個用於執行工作隊列中各個工作項的內核線程，當工作隊列中沒有工作項時，該線程將變為 idle 狀態。

single threaded(ST):工作者線程的表現形式之一，在系統範圍內，只有一個工作者線程為工作隊列服務。

multi threaded(MT)：工作者線程的表現形式之一，在多 CPU 系統上每個 CPU 上都有一個工作者線程為工作隊列服務。 ^[1] 

工作隊列機制的準則如下：

(1) 週轉時間短。通常把週轉時間的長短作為評價批處理系統的性能、選擇作業調度方式與算法的重要準則之一。所謂週轉時間，是指從作業被提交給系統開始，到作業完成為止的這段時間間隔(稱為作業週轉時間)。它包括四部分時間：作業在外存後備隊列上等待(作業)調度的時間，進程在就緒隊列上等待進程調度的時間，進程在CPU 上執行的時間，以及進程等待I/O 操作完成的時間。其中的後三項在一個作業的整個處理過程中可能會發生多次。

(2) 響應時間快。常把響應時間的長短用來評價分時系統的性能，這是選擇分時系統中進程調度算法的重要準則之一。所謂響應時間，是從用户通過鍵盤提交一個請求開始，直至系統首次產生響應為止的時間，或者説，直到屏幕上顯示出結果為止的一段時間間隔。它包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的響應信息回送到終端顯示器的時間。

(3) 截止時間的保證。這是評價實時系統性能的重要指標，因而是選擇實時調度算法的重要準則。所謂截止時間，是指某任務必須開始執行的最遲時間，或必須完成的最遲時間。對於嚴格的實時系統，其調度方式和調度算法必須能保證這一點，否則將可能造成難以預料的後果。

(4) 優先權準則。在批處理、分時和實時系統中選擇調度算法時，都可遵循優先權準則，以便讓某些緊急的作業能得到及時處理。在要求較嚴格的場合，往往還須選擇搶佔式調度方式，才能保證緊急作業得到及時處理。

(1) 系統吞吐量高。這是用於評價批處理系統性能的另一個重要指標，因而是選擇批處理作業調度的重要準則。由於吞吐量是指在單位時間內系統所完成的作業數，因而它與批處理作業的平均長度具有密切關係。對於大型作業，一般吞吐量約為每小時一道作業；對於中、小型作業，其吞吐量則可能達到數十道作業之多。作業調度的方式和算法對吞吐量的大小也將產生較大影響。事實上，對於同一批作業，若採用了較好的調度方式和算法，則可顯著地提高系統的吞吐量。

(2) 處理機利用率好。對於大、中型多用户系統，由於CPU 價格十分昂貴，致使處理機的利用率成為衡量系統性能的十分重要的指標；而調度方式和算法對處理機的利用率起着十分重要的作用。在實際系統中，CPU的利用率一般在40%(系統負荷較輕)到90%之間。在大、中型系統中，在選擇調度方式和算法時，應考慮到這一準則。但對於單用户微機或某些實時系統，則此準則就不那麼重要了。

(3) 各類資源的平衡利用。在大、中型系統中，不僅要使處理機的利用率高，而且還應能有效地利用其它各類資源，如內存、外存和I/O 設備等。選擇適當的調度方式和算法可以保持系統中各類資源都處於忙碌狀態。但對於微型機和某些實時系統而言，該準則並不重要。 ^[2] 

消息隊列機制是在多個不同的應用之間實現相互通信的一種異步傳輸模式，相互通信的應用可以分佈於同一台機器上，也可以分佈於相連的網絡空間中的任一位置。

常用的通知機制中比較典型的有以下幾種：

1. signal