引 言

在對實時采集更新的數(shù)據(jù)進行處理時，往往會遇到數(shù)據(jù)更新速度與數(shù)據(jù)處理的速度不匹配的問題。這種情況下，會出現(xiàn)數(shù)據(jù)丟失而導(dǎo)致數(shù)據(jù)處理結(jié)果不準(zhǔn)確，甚至?xí)聿豢深A(yù)測的后果，因此需要一種機制來協(xié)調(diào)數(shù)據(jù)更新與數(shù)據(jù)處理，從而保證數(shù)據(jù)的完整性和處理結(jié)果的準(zhǔn)確性。作為一個多任務(wù)、多用戶操作系統(tǒng)，Linux 支持多個進程在系統(tǒng)中并發(fā)運行，由于進程本身的動態(tài)特性，用來描述實時數(shù)據(jù)處理非常合適，因此，解決好Linux進程間的同步與通信問題就能解決實時數(shù)據(jù)處理的問題。

在Linux環(huán)境下，進程通常存在運行（running）、阻塞（blocked）、就緒（ready）、終止（terminated）四種狀態(tài)。當(dāng)多個進程并發(fā)執(zhí)行時，往往會出現(xiàn)進程間的競態(tài)。我們希望進程能協(xié)調(diào)彼此間的行為，使得一個進程只有在其他的進程執(zhí)行到一個特定的點時才會執(zhí)行一個動作，即控制同步；同時，當(dāng)并發(fā)進程訪問共享數(shù)據(jù)時不應(yīng)當(dāng)出現(xiàn)競爭條件。這一點通過在訪問共享數(shù)據(jù)時執(zhí)行互斥來確保，即數(shù)據(jù)訪問同步。

實現(xiàn)同步的基本技術(shù)是阻塞一個進程，直到一個特定條件滿足為止；實現(xiàn)數(shù)據(jù)訪問同步是通過阻塞一個進程直到另外的進程完成訪問共享數(shù)據(jù)。

1 有限長度緩沖區(qū)的生產(chǎn)者一消費者問題模型

當(dāng)僅存在單個生產(chǎn)者和消費者時，生產(chǎn)進程和消費進程所對應(yīng)的是同樣的數(shù)據(jù)結(jié)構(gòu)，它們共享同一個數(shù)據(jù)空間。生產(chǎn)進程和消費進程如何進行相互協(xié)調(diào)，使得消費進程每次使用的數(shù)據(jù)都是生產(chǎn)進程新生產(chǎn)寫人的，又使生產(chǎn)進程新寫入的數(shù)據(jù)不會覆蓋還未被消費進程讀出使用的數(shù)據(jù)，是該問題模型實現(xiàn)的關(guān)鍵問題。

在生產(chǎn)者一消費者問題模型中，生產(chǎn)者進程不斷生產(chǎn)產(chǎn)品并把它們放入緩沖區(qū)，消費者進程不斷從緩沖區(qū)中取走產(chǎn)品進行消費。當(dāng)緩沖區(qū)中產(chǎn)品已經(jīng)放滿時，表示生產(chǎn)速度高于消費速度，出現(xiàn)了供過于求，此時生產(chǎn)者必須等待產(chǎn)品被消費；當(dāng)緩沖區(qū)為空時，表示消費速度高于生產(chǎn)速度，出現(xiàn)了供不應(yīng)求，此時消費者進程必須等待產(chǎn)品的生產(chǎn)。生產(chǎn)和消費的進程必須達到同步運行，才能實現(xiàn)供需平衡。

處理讀寫同步的兩種常見的策略被稱為“強讀者同步（strong reader synchronization）”和“強寫者同步（strongwriter synchronization）”。在強讀者同步中，總是給讀者以優(yōu)先權(quán)，只要寫者當(dāng)前沒有進行寫操作，讀者就可以獲得訪問權(quán)；在強寫者同步中，寫者總是獲得優(yōu)先權(quán)，只要強讀者當(dāng)前沒有進行讀操作，寫者就可以獲得訪問權(quán)。而生產(chǎn)者消費者同步與單純的讀寫同步又有不同，消費者可以通過訪問資源對資源進行刪除或銷毀。

一個有限長度緩沖區(qū)的生產(chǎn)者消費者問題模型，是由若干生產(chǎn)者和消費者進程以及一個有限的緩沖池構(gòu)成的。每個緩沖區(qū)能夠存儲一個信息記錄，一個生產(chǎn)者一次生產(chǎn)一個信息記錄。產(chǎn)生一個記錄之后，等待單獨進入一個空的緩沖區(qū)后將記錄寫入緩沖區(qū)。一個消費者進程一次消費一個信息記錄。當(dāng)它需要消費時，它等待單獨進入一個滿的緩沖區(qū)后將記錄讀出。

通過上面的描述可以得出，解決生產(chǎn)者一消費者問題模型的方案需要滿足以下幾個條件：

◇生產(chǎn)者不應(yīng)覆蓋一個滿的緩沖區(qū)；

◇消費者不應(yīng)使用一個空的緩沖區(qū)；

◇生產(chǎn)者和消費者應(yīng)按互斥方式訪問數(shù)據(jù)緩沖區(qū)；

◇數(shù)據(jù)必須按照先進先出（FIFO）方式；

◇不能出現(xiàn)忙等待。

必須避免數(shù)據(jù)寫進程不斷、反復(fù)地檢查緩沖區(qū)直到找到一個空緩沖區(qū)為止，而讀進程也必須避免不斷檢查直到找到一個滿緩沖區(qū)為止。這相當(dāng)于系統(tǒng)內(nèi)部產(chǎn)生忙等待，是在僅使用臨界段（CS）算法實現(xiàn)進程同步時難以避免的問題。

針對問題模型解決方案的限制條件，采用信號量方式解決實時更新數(shù)據(jù)處理的進程同步問題，即上述的生產(chǎn)者一消費者問題模型。

信號量是一個非負值的共享整數(shù)值，只能用于初始化和不可分操作。不可分操作是指在對一個數(shù)據(jù)D進行操作時不能與任何其他對D的操作重疊的操作。定義操作P 和V為不可分操作。P和V的不可分性意味著這些操作不能并發(fā)執(zhí)行，避免了對信號量的競爭條件。定義P和V的操作語義為：

由上述定義的語義看，對一個信號量S的操作，P和V為改變S的值，或者掛起或喚醒一個對S進行P操作的進程。被掛起的進程為阻塞狀態(tài)，因而避免了忙等待問題。一個二進制的信號量只取0和1，用來實現(xiàn)互斥。

在P和V操作中，對進程的阻塞和喚醒需要操作系統(tǒng)的進程管理組件的參與，因此信號量會被操作系統(tǒng)實現(xiàn)而不是應(yīng)用程序?qū)崿F(xiàn)。

生產(chǎn)者一消費者問題模型描述：

2 結(jié)構(gòu)設(shè)計

對于有限緩沖區(qū)的生產(chǎn)者消費者問題模型的執(zhí)行包括以下部件：共享數(shù)據(jù)一緩沖區(qū)組、操作一緩沖區(qū)的訪問、進程一生產(chǎn)者消費者。

在生產(chǎn)者一消費者同步中，由生產(chǎn)者創(chuàng)建資源，與單純的讀程序不同，消費者可以通過訪問資源，將資源刪除或銷毀。由于生產(chǎn)者進程和消費者進程共享一個緩沖區(qū)，因此在插入和刪除條目時必須同步。實現(xiàn)中必須避免表l所列的同步異常問題。

生產(chǎn)者一消費者問題的傳統(tǒng)的信號量解決方案使用了2個信號量，分別用來表示緩沖區(qū)中的條目數(shù)和空閑槽的數(shù)目。當(dāng)進程需要特定類型的資源時，它可以通過函數(shù)調(diào)用對相應(yīng)的信號量進行減量操作；同樣，當(dāng)進程釋放資源時，它可以通過函數(shù)調(diào)用來對相應(yīng)的信號量進行增量操作。由于信號量永遠不會降到零以下，所以進程不能使用不存在的資源。因此，始終將計數(shù)信號量初始化為開始時可用的資源數(shù)。

定義循環(huán)隊列緩沖區(qū)存放待處理數(shù)據(jù)，控制臺數(shù)據(jù)處理進程從該循環(huán)隊列緩沖區(qū)中消費數(shù)據(jù)，并將該數(shù)據(jù)存儲位標(biāo)記為“廢棄”。數(shù)據(jù)采集寫進程僅能將數(shù)據(jù)存放于標(biāo)記為“廢棄”的循環(huán)隊列緩沖區(qū)中，如圖1所示。

在沒有多個生產(chǎn)者或消費者的情況下，如果仔細實現(xiàn)，循環(huán)緩沖區(qū)就不需要鎖。生產(chǎn)者是唯一允許修改寫入索引以及該索引指向的數(shù)組位置的進程。只要寫入者在更新寫入索引之前將新的值保存到緩沖區(qū)，則讀取者將始終看到一致的數(shù)據(jù)結(jié)構(gòu)；同時，讀取者是唯一可以訪問讀取索引以及該索引指向位置的數(shù)據(jù)的進程。只要確保兩個指針不要互相重疊，生產(chǎn)者和消費者可以在無竟態(tài)的情況下訪問該緩沖區(qū)，如圖2所示。

對于只有單個生產(chǎn)者和消費者，通過使用修正的使用信號量方式的生產(chǎn)者一消費者問題模型解決方案來實現(xiàn)。

以上用信號量方式解決了優(yōu)先緩沖區(qū)問題，信號量“empty”和“full”的值分別指示空和滿的緩沖區(qū)的數(shù)量，如圖3所示。緩沖區(qū)指針i和j用來確保緩沖區(qū)按先進先出的順序提供并使用。只要系統(tǒng)中存在一些滿的和空的緩沖區(qū)，數(shù)據(jù)更新進程和數(shù)據(jù)處理進程就能無競態(tài)并發(fā)執(zhí)行。筆者在華恒ARM嵌入式平臺 HHARM2410-R5上按照上述方案成功實現(xiàn)了用例測試。

3 討論

以上的結(jié)構(gòu)設(shè)計，將生產(chǎn)者與消費者分別簡化為一個。當(dāng)存在多個生產(chǎn)者和消費者的情況時，可以上述修正的解決方案為基礎(chǔ)，設(shè)計多個計數(shù)器來統(tǒng)計并行讀者（reader）、并行寫者（writer）、讀者或待讀者（pre_reader）、寫者或待寫者（pre_writer）的數(shù)量。計數(shù)器的值在進程中的相應(yīng)位置進行增減。讀者和寫者在被允許閱讀和寫入之前必須被阻塞，這可以通過P操作來完成。當(dāng)讀者或?qū)懻咴谶M程被阻塞時控制開始閱讀或書寫的條件并未滿足。這些條件隨著任意一個計數(shù)器值的變化而改變，所以，進程在完成閱讀或書寫后必須執(zhí)行相應(yīng)的V操作。

在實行多讀、多寫進程同步解決方案時，必須要避免不同計數(shù)器的競爭條件，因而必須在臨界段（CS）中執(zhí)行對允許讀或?qū)懖僮鳁l件的檢查。