佇列(Queue)是我們在設計系統、設計程式時時常會用到的一種資料結構,幾乎每個程式設計者都有使用過佇列的經驗。

小到自己設計的佇列資料結構或內建的佇列類別,或是大到可分散式運作的一組佇列伺服器(Queue Server),佇列的應用在軟體系統中幾乎是無所不在。

不過,儘管如此,如何運用佇列,對軟體開發人員而言,還是一門相當大的學問。在這一回中,就讓我們來略為探討吧。

佇列的不同用法
所謂的「佇列」其實就是一種依照順序存取的抽象資料結構。一般人所最常接觸的,可能是所謂的FIFO(First In First Out)Queue,也就是依照先進先出的原則來存取的佇列。不過,佇列的「順序」不只是先進先出這種規則而已,像所謂Priority Queue(優先序佇列)便是依據佇列中元素被定義的「優先序」來決定存取的先後順序。優先序佇列的例子在生活中也很常見,例如在急診室裡,病人的看診順序就不是依照先到先看診的方式,而是依據病情的緊急程度。

因為佇列的定義很簡單,所以在其中的操作也很簡單。

你所能對佇列做的最根本操作,就是下列兩種:一種是把元素置入佇列中,也就是enqueue,另一種便是將元素自佇列中取出,也就是dequeue。

這兩項操作是佇列的最基本操作,有些佇列還會提供一些額外的操作,像是窺看但不取出佇列最前端(也就是下一個取出)的元素。此外,針對不同的變形,佇列還會有一些不同的特性,像是所謂的Deque(Double Ended Queue),它就是兩端皆可存取的佇列,而不會只可從頂端取出。

不同架構的佇列
在一般的電腦系統裡,佇列依據它是否獨立存在於獨立的行程裡,可區分為兩種:「行程內(In-Process)佇列」,及「以網路為基礎(Network-Based)的佇列」。

所謂的「行程內佇列」代表佇列的程式和使用佇列的客戶端程式是位在同一個行程之內,這通常是我們最常運用佇列的情況。

例如我們在使用C++的STL中的std::queue或是Java內建的java.util.Queue類別時,佇列的程式和使用佇列的客戶端程式,都是運行在同一個行程之內,它們之間,不需要透過網路或其他跨行程通訊(Inter-Process Communication)的方式來進行溝通,也不需要在溝通時,把要操作的元素資料做類似序列化(serialization)的動作,以便傳輸。所以,不會因為資料傳輸,或是為了資料傳輸而做的計算,而付出額外的代價。

因此,使用行程內的佇列在效率上通常會比較好。而另一類以網路為基礎的佇列,佇列是存在於獨立的行程之外,通常這種情況我們就把它稱為佇列伺服器,因為這個獨立的行程透過一個特定的通訊協定,或是跨行程的通訊方法,來對客戶端程式提供佇列的服務。

因為,透過網路或跨行程的通訊方法來存取佇列,都必須針對所欲在佇列中操作元素的資料內容,予以處理,例如像是序列化或是解序列化,也都必須將這些內容,透過網路或通訊的管道來做傳輸。一方面增加了計算量上的負擔,另一方面也增加了傳輸時的負擔,不但耗用頻寬,而且也需要投入計算來處理資料。

不過,以網路為基礎的佇列單節點來看的效率,比較不那麼好,卻擁有一個很重要的優勢,也就是它比較容易擴展規模。行程內的佇列雖然運行效率好,但是,會受限於單一個行程所能配置的資源量,而無法擴展規模。

例如,一個32位元的電腦,有可能作業系統僅能分配4G位元組的記憶體空間給單一行程,若是佇列需要的記憶體空間,因為規模的增加而必須超過4G位元組,那麼,行程內的佇列就會因為記憶體空間的限制,而無法擴展規模。這些硬體資源上的限制,不只會發生在記憶體空間,也會發生在CPU計算能力、檔案儲存空間、網路傳輸頻寬、等等。相較於行程內的佇列,能透過網路為客戶端提供服務的佇列伺服器,反而得以有機會透過在架構中的多個佇列伺服器,來得到更多的資源,以便提供更強大的服務能力。

所謂的規模可擴充性(scalability)指的,不是在效率比較高,而是可以透過投入更多的資源,來得到提供更大規模服務的能力。以網路為基礎的佇列,不但可以透過分散式的架構得到擴充規模的能力,而且,還有機會因此而得到更多容忍錯誤的能力,也就是說,即使有部份的佇列損毀,還能維持一定的服務能力。

用到佇列的幾種理由

我們會基於什麼目的,而在系統或程式中應用佇列呢?通常有三種原因:(1)在演算法中需要佇列特性的資料儲存結構(2)基於資源配置的最佳化(3)進行跨執行緒或跨行程的通訊。

不少我們所熟知的演算法,其中都運用了佇列的資料結構,來存放演算法進行過程中所操作的資料。例如像在圖的走訪(Graph Traversal)中,「廣度優先搜尋(Breadth First Search)」的演算法,就會將每次未走訪過的節點置入一個FIFO佇列中,每次要走訪一個新節點時,都從佇列中取出一個節點來處理;或是像著名的Prim的最小展開樹(Minimal Spanning Tree)演算法中,使用優先序佇列,都是在演算法中利用佇列特性的例子。

同時,在我們實務的開發中,也會遇到所設計的演算法需要利用佇列的特性。

除了演算法中利用佇列循序存取特性的應用之外,利用佇列來做資源配置的最佳化,也是佇列很常看到的應用。

基本上,佇列就是讓你得以在服務成本及服務品質之間,取得平衡的一種機制。資源通常是有限的,資源的量時常決定了服務的品質,因為資源的量愈多、愈充足,服務的品質時常會更好。但是,資源的量通常也決定了服務的成本,因為所使用的資源量愈多,花在資源的代價就愈高。

佇列的第三個常見的應用,便是做為跨執行緒或跨行程的通訊之用。佇列允許你將資料元素置於其中,也允許你自其中取出。所以,想要進行通訊的雙方甚至是多方,便可以將想要通訊的內容置於佇列中。

因為佇列本身具有緩衝、暫存的作用,所以通訊的雙方或多方,可以進行「非同步」的通訊,也就是說,發送訊息和接收訊息的速率和步調不一定得保持完全一致。當發送方上線時,接收方不一定要在線上,反之亦然。非同步和緩衝都是佇列重要的先天特質,接下來你會發現,有很多佇列的應用都是基於這兩項特質而來。像傳統跨行程通訊(Inter-Process Communication,IPC)需面對的生產者及消費者的問題,其中生產者和消費者其實就是在做通訊的活動。

事實上,所謂訊息發送者與訊息接收者的模型中,訊息發送者就像是一個生產者,只不過它所生產的是訊息,而接收者就是消費者,所消費的也是訊息。像我們所常使用的一些即時通訊軟體,都會利用所謂的「訊息佇列(Message Queue)」來儲存訊息。

在下一回中,將更進一步介紹佇列應用實務上的一些議題。

作者簡介


Advertisement

更多 iThome相關內容