嵌入式Linux中的進(jìn)程同步無(wú)競爭態(tài)讀寫(xiě)

引 言
在對實(shí)時(shí)采集更新的數據進(jìn)行處理時(shí)，往往會(huì )遇到數據更新速度與數據處理的速度不匹配的問(wèn)題。這種情況下，會(huì )出現數據丟失而導致數據處理結果不準確，甚至會(huì )帶來(lái)不可預測的后果，因此需要一種機制來(lái)協(xié)調數據更新與數據處理，從而保證數據的完整性和處理結果的準確性。作為一個(gè)多任務(wù)、多用戶(hù)操作系統，Linux支持多個(gè)進(jìn)程在系統中并發(fā)運行，由于進(jìn)程本身的動(dòng)態(tài)特性，用來(lái)描述實(shí)時(shí)數據處理非常合適，因此，解決好Linux進(jìn)程間的同步與通信問(wèn)題就能解決實(shí)時(shí)數據處理的問(wèn)題。
在Linux環(huán)境下，進(jìn)程通常存在運行(running)、阻塞(blocked)、就緒(ready)、終止(terminated)四種狀態(tài)。當多個(gè)進(jìn)程并發(fā)執行時(shí)，往往會(huì )出現進(jìn)程間的競態(tài)。我們希望進(jìn)程能協(xié)調彼此間的行為，使得一個(gè)進(jìn)程只有在其他的進(jìn)程執行到一個(gè)特定的點(diǎn)時(shí)才會(huì )執行一個(gè)動(dòng)作，即控制同步；同時(shí)，當并發(fā)進(jìn)程訪(fǎng)問(wèn)共享數據時(shí)不應當出現競爭條件。這一點(diǎn)通過(guò)在訪(fǎng)問(wèn)共享數據時(shí)執行互斥來(lái)確保，即數據訪(fǎng)問(wèn)同步。
實(shí)現同步的基本技術(shù)是阻塞一個(gè)進(jìn)程，直到一個(gè)特定條件滿(mǎn)足為止；實(shí)現數據訪(fǎng)問(wèn)同步是通過(guò)阻塞一個(gè)進(jìn)程直到另外的進(jìn)程完成訪(fǎng)問(wèn)共享數據。

1 有限長(cháng)度緩沖區的生產(chǎn)者一消費者問(wèn)題模型
當僅存在單個(gè)生產(chǎn)者和消費者時(shí)，生產(chǎn)進(jìn)程和消費進(jìn)程所對應的是同樣的數據結構，它們共享同一個(gè)數據空間。生產(chǎn)進(jìn)程和消費進(jìn)程如何進(jìn)行相互協(xié)調，使得消費進(jìn)程每次使用的數據都是生產(chǎn)進(jìn)程新生產(chǎn)寫(xiě)人的，又使生產(chǎn)進(jìn)程新寫(xiě)入的數據不會(huì )覆蓋還未被消費進(jìn)程讀出使用的數據，是該問(wèn)題模型實(shí)現的關(guān)鍵問(wèn)題。
在生產(chǎn)者一消費者問(wèn)題模型中，生產(chǎn)者進(jìn)程不斷生產(chǎn)產(chǎn)品并把它們放入緩沖區，消費者進(jìn)程不斷從緩沖區中取走產(chǎn)品進(jìn)行消費。當緩沖區中產(chǎn)品已經(jīng)放滿(mǎn)時(shí)，表示生產(chǎn)速度高于消費速度，出現了供過(guò)于求，此時(shí)生產(chǎn)者必須等待產(chǎn)品被消費；當緩沖區為空時(shí)，表示消費速度高于生產(chǎn)速度，出現了供不應求，此時(shí)消費者進(jìn)程必須等待產(chǎn)品的生產(chǎn)。生產(chǎn)和消費的進(jìn)程必須達到同步運行，才能實(shí)現供需平衡。
處理讀寫(xiě)同步的兩種常見(jiàn)的策略被稱(chēng)為“強讀者同步(strong reader synchronization)”和“強寫(xiě)者同步(strongwriter synchronization)”。在強讀者同步中，總是給讀者以?xún)?yōu)先權，只要寫(xiě)者當前沒(méi)有進(jìn)行寫(xiě)操作，讀者就可以獲得訪(fǎng)問(wèn)權；在強寫(xiě)者同步中，寫(xiě)者總是獲得優(yōu)先權，只要強讀者當前沒(méi)有進(jìn)行讀操作，寫(xiě)者就可以獲得訪(fǎng)問(wèn)權。而生產(chǎn)者消費者同步與單純的讀寫(xiě)同步又有不同，消費者可以通過(guò)訪(fǎng)問(wèn)資源對資源進(jìn)行刪除或銷(xiāo)毀。
一個(gè)有限長(cháng)度緩沖區的生產(chǎn)者消費者問(wèn)題模型，是由若干生產(chǎn)者和消費者進(jìn)程以及一個(gè)有限的緩沖池構成的。每個(gè)緩沖區能夠存儲一個(gè)信息記錄，一個(gè)生產(chǎn)者一次生產(chǎn)一個(gè)信息記錄。產(chǎn)生一個(gè)記錄之后，等待單獨進(jìn)入一個(gè)空的緩沖區后將記錄寫(xiě)入緩沖區。一個(gè)消費者進(jìn)程一次消費一個(gè)信息記錄。當它需要消費時(shí)，它等待單獨進(jìn)入一個(gè)滿(mǎn)的緩沖區后將記錄讀出。
通過(guò)上面的描述可以得出，解決生產(chǎn)者一消費者問(wèn)題模型的方案需要滿(mǎn)足以下幾個(gè)條件：
◇生產(chǎn)者不應覆蓋一個(gè)滿(mǎn)的緩沖區；
◇消費者不應使用一個(gè)空的緩沖區；
◇生產(chǎn)者和消費者應按互斥方式訪(fǎng)問(wèn)數據緩沖區；
◇數據必須按照先進(jìn)先出(FIFO)方式；
◇不能出現忙等待。
必須避免數據寫(xiě)進(jìn)程不斷、反復地檢查緩沖區直到找到一個(gè)空緩沖區為止，而讀進(jìn)程也必須避免不斷檢查直到找到一個(gè)滿(mǎn)緩沖區為止。這相當于系統內部產(chǎn)生忙等待，是在僅使用臨界段(CS)算法實(shí)現進(jìn)程同步時(shí)難以避免的問(wèn)題。
針對問(wèn)題模型解決方案的限制條件，采用信號量方式解決實(shí)時(shí)更新數據處理的進(jìn)程同步問(wèn)題，即上述的生產(chǎn)者一消費者問(wèn)題模型。
信號量是一個(gè)非負值的共享整數值，只能用于初始化和不可分操作。不可分操作是指在對一個(gè)數據D進(jìn)行操作時(shí)不能與任何其他對D的操作重疊的操作。定義操作P和V為不可分操作。P和V的不可分性意味著(zhù)這些操作不能并發(fā)執行，避免了對信號量的競爭條件。定義P和V的操作語(yǔ)義為：

由上述定義的語(yǔ)義看，對一個(gè)信號量S的操作，P和V為改變S的值，或者掛起或喚醒一個(gè)對S進(jìn)行P操作的進(jìn)程。被掛起的進(jìn)程為阻塞狀態(tài)，因而避免了忙等待問(wèn)題。一個(gè)二進(jìn)制的信號量只取0和1，用來(lái)實(shí)現互斥。
在P和V操作中，對進(jìn)程的阻塞和喚醒需要操作系統的進(jìn)程管理組件的參與，因此信號量會(huì )被操作系統實(shí)現而不是應用程序實(shí)現。
生產(chǎn)者一消費者問(wèn)題模型描述：

2 結構設計
對于有限緩沖區的生產(chǎn)者消費者問(wèn)題模型的執行包括以下部件：共享數據一緩沖區組、操作一緩沖區的訪(fǎng)問(wèn)、進(jìn)程一生產(chǎn)者消費者。
在生產(chǎn)者一消費者同步中，由生產(chǎn)者創(chuàng )建資源，與單純的讀程序不同，消費者可以通過(guò)訪(fǎng)問(wèn)資源，將資源刪除或銷(xiāo)毀。由于生產(chǎn)者進(jìn)程和消費者進(jìn)程共享一個(gè)緩沖區，因此在插入和刪除條目時(shí)必須同步。實(shí)現中必須避免表l所列的同步異常問(wèn)題。

生產(chǎn)者一消費者問(wèn)題的傳統的信號量解決方案使用了2個(gè)信號量，分別用來(lái)表示緩沖區中的條目數和空閑槽的數目。當進(jìn)程需要特定類(lèi)型的資源時(shí)，它可以通過(guò)函數調用對相應的信號量進(jìn)行減量操作；同樣，當進(jìn)程釋放資源時(shí)，它可以通過(guò)函數調用來(lái)對相應的信號量進(jìn)行增量操作。由于信號量永遠不會(huì )降到零以下，所以進(jìn)程不能使用不存在的資源。因此，始終將計數信號量初始化為開(kāi)始時(shí)可用的資源數。
定義循環(huán)隊列緩沖區存放待處理數據，控制臺數據處理進(jìn)程從該循環(huán)隊列緩沖區中消費數據，并將該數據存儲位標記為“廢棄”。數據采集寫(xiě)進(jìn)程僅能將數據存放于標記為“廢棄”的循環(huán)隊列緩沖區中，如圖1所示。

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

對于只有單個(gè)生產(chǎn)者和消費者，通過(guò)使用修正的使用信號量方式的生產(chǎn)者一消費者問(wèn)題模型解決方案來(lái)實(shí)現。

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

3 討論

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

在實(shí)行多讀、多寫(xiě)進(jìn)程同步解決方案時(shí)，必須要避免不同計數器的競爭條件，因而必須在臨界段（CS）中執行對允許讀或寫(xiě)操作條件的檢查。