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

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

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

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

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

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

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

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

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

3 討論

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

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