摘 要： 本文簡(jiǎn)要地介紹了bakery算法進(jìn)程互斥思想，指出它存在的三個(gè)缺點(diǎn)。然后在滿足進(jìn)程互斥設(shè)計(jì)三要點(diǎn)的前提下，提出快速互斥算法，并且對(duì)它的性能和優(yōu)點(diǎn)給出證明，指出快速算法能夠很好地解決bakery算法的缺點(diǎn)。
　　關(guān)鍵詞： bakery算法 快速算法 進(jìn)程互斥 空閑讓進(jìn) 有限等待
　　
　　1.進(jìn)程互斥算法的應(yīng)用背景
　　如今，互聯(lián)網(wǎng)上有大量的資源供用戶使用，這些資源很多都是臨界資源?；ヂ?lián)網(wǎng)上大量進(jìn)程都要使用這些臨界資源。由于臨界資源共享時(shí)要互斥訪問，這就使得這些進(jìn)程在訪問臨界資源時(shí)要互斥進(jìn)入自己的臨界區(qū)。
　　進(jìn)程互斥進(jìn)入臨界區(qū)算法設(shè)計(jì)時(shí)要注意三點(diǎn)：（1）互斥訪問（mutual exclusion）［１］［２］［３］，即是每次只能有一個(gè)進(jìn)程進(jìn)入自己的臨界區(qū)，同一時(shí)間不能兩個(gè)或兩個(gè)以上進(jìn)程進(jìn)入臨界區(qū)。（2）空閑讓進(jìn)（progress），即是當(dāng)沒有進(jìn)程在臨界區(qū)執(zhí)行，有一些進(jìn)程要進(jìn)入臨界區(qū)時(shí)，只有那些不在remainder section中執(zhí)行的進(jìn)程有權(quán)決定誰進(jìn)入臨界區(qū)，并且這決定不能無限推遲。（3）有限等待（bounded waiting），即是進(jìn)程從申請(qǐng)進(jìn)入臨界區(qū)到進(jìn)入臨界區(qū)這段時(shí)間是一段有限的時(shí)間，進(jìn)程不能無限等待進(jìn)入。
　　互聯(lián)網(wǎng)上共享臨界資源進(jìn)程只有遵循以上三點(diǎn)，進(jìn)程執(zhí)行的結(jié)果才不會(huì)出錯(cuò)。也只有在遵循以上三點(diǎn)的基礎(chǔ)上，互聯(lián)網(wǎng)上的應(yīng)用程序才能為用戶提供可靠的資源訪問。
　　目前，對(duì)進(jìn)程互斥分布式算法設(shè)計(jì)主要分為三類，即（1）permission-based（e.g.Lamport，Ricart-Agrawala，Singhal，Maekawa ），思想是每一個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前要得到所有其他進(jìn)程的準(zhǔn)許。（2）token-based （Suzuki-Kazami，Raymond ，Naimi-Trehel，Neilsen-Mizuno，Chang，Singhal and Liu ），思想是整個(gè)系統(tǒng)有一個(gè)token，只有得到token的進(jìn)程才能進(jìn)入臨界區(qū)。（3）Quorum based，思想是所有進(jìn)程中，部分進(jìn)程決定某進(jìn)程是否可以進(jìn)入臨界區(qū)。
　　2.bakery算法設(shè)計(jì)的思想
　　Bakery算法是一種簡(jiǎn)單的處理n個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)的算法。它基于面包店里普遍使用的一種算法。顧客進(jìn)入面包店的時(shí)候首先得到一個(gè)服務(wù)號(hào)碼，得到最小號(hào)碼的顧客首先得到服務(wù)?；谶@一思想，bakery算法處理N個(gè)進(jìn)程互斥時(shí)對(duì)共享變量的讀寫采用原子操作來實(shí)現(xiàn)，每個(gè)進(jìn)程都擁有一個(gè)屬于自己的共享變量。這個(gè)共享變量指示本進(jìn)程在等待進(jìn)入臨界區(qū)的位置，只有當(dāng)本變量指示等待隊(duì)列的頭部時(shí)，本進(jìn)程才優(yōu)先進(jìn)入臨界區(qū)。只有本進(jìn)程才可以對(duì)屬于自己的共享變量讀寫，別的進(jìn)程只能讀。Bakery算法代碼如圖1。
　　在本算法中，不同顧客可能得到同一個(gè)號(hào)碼。為此，我們有定義1。
　　定義1：有二元組（number［i］，i）和（number［j］，j），當(dāng)number［i］＜number［j］或者number［i］=number［j］并且i＜j時(shí)，有（number［i］，i）＜（number［j］，j）。
　　定義1的意思是：顧客i的服務(wù)號(hào)碼number［i］＜顧客j的服務(wù)號(hào)碼number［j］時(shí)，或者顧客i和顧客j的服務(wù)號(hào)碼相等，但i＜j時(shí)，顧客i先服務(wù)。在圖1中，Bakery算法滿足下面三個(gè)申明。
　　申明（1）（進(jìn)程互斥）
　　□［?坌0…N-1 i，j，i!=j：：Z（i，j）］，where Z（i，j）：┐（πid［i］ on CS∧id［j］ on CS）
　　申明（2）（空閑讓進(jìn)）
　?。?坌0…N-1 i：：P（i）］→［?坌0…N-1 i：：Q（i）］ where
　　P（i）：πid［i］ on CS→πid［i］ at b1
　　Q（i）：πid［i］ at a1→πid［i］ on CS
　　申明（3）（有限等待）
　　max（Time（i）boundwait）=（N-1）*（T1+T2）其中Time（i）boundwait為進(jìn)程i從申請(qǐng)進(jìn)入臨界區(qū)到進(jìn)入臨界區(qū)的等待時(shí)間。
　　T1為執(zhí)行a2：num［i］=max（num［0］，num［1］，…，num［N-1］）+1所用時(shí)間；
　　T2為執(zhí)行臨界區(qū)代碼所用時(shí)間。
　　3.用快速算法對(duì)bakery算法的改進(jìn)
　　bakery算法解決了n個(gè)進(jìn)程互斥問題，滿足進(jìn)程互斥時(shí)三要點(diǎn)。但bakery算法存在以下實(shí)際的缺點(diǎn)。
　?。?）總是有進(jìn)程在臨界區(qū)時(shí)，進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)的服務(wù)號(hào)將無限變大（unbounded number）。
　　（2）使用的共享變量多，兩個(gè)共享數(shù)組有2N個(gè)共享變量，在分布式環(huán)境下使得進(jìn)程之間信息交換量增大。
　?。?）程進(jìn)入臨界區(qū)之前要和N-1個(gè)進(jìn)程的服務(wù)號(hào)進(jìn)行比較，不管是否有別的進(jìn)程要進(jìn)入臨界區(qū)，這無疑會(huì)使進(jìn)程的運(yùn)行速度變慢。
　　為此我們提出了進(jìn)程互斥的快速算法（fast for n processes），可以有效地解決以上bakery算法存在的問題。
　　為了引入快速算法，先還是引入快速算法的簡(jiǎn)單情況，兩個(gè)進(jìn)程的快速算法?？梢园裝akery算法分成六個(gè)部分：start，doorway，ticket assignment，wait section，critical section and final。Start即執(zhí)行算法初始化代碼，進(jìn)程i在doorway處即進(jìn)程i執(zhí)行完了choosing［i］=true，ticket即執(zhí)行Number［i］=1+max（Number［1］，...，Number［N］），wait section即互斥循環(huán)，critical section即臨界區(qū)，final即出臨界區(qū)善后代碼。而快速算法的思想是設(shè)置gate1和gate2，只有同時(shí)得到gate1和gate2進(jìn)程優(yōu)先進(jìn)入臨界區(qū)，并且后得到者優(yōu)先進(jìn)入臨界區(qū)。在快速算法中我們假定對(duì)共享變量的操作都是原子操作。圖2是兩個(gè)進(jìn)程的快速算法。
　　斷言1：┐（csp∧csq）是重言式（進(jìn)程互斥）。
　　證明：反正法。假設(shè)（csp∧csq）為真。
　　csp→（gate1=p）∨（waitq=false∧gate2=p）（1）
　　csq→（gate1=q）∨（waitp=false∧gate2=q）（2）
　　由（1）、（2）得（（gate1=p）∨（waitq=false∧gate2=p））∧（（gate1=q）∨（waitp=false∧gate2=q））真，得（（gate1=p）∧（gate1=q））∨（（gate1=p）∧（waitp=false∧gate2=q））∨（（gate1=q）∧（waitq=false∧gate2=p））∨（（waitq=false∧gate2=p）∧（waitp=false∧gate2=q））……分配律
　?。?）為真。
　　式子（3）中用∨連接的每一項(xiàng)都是假。（gate1=p）∧（gate1=q）為假，而（gate1=p）∧（waitp=false∧gate2=q）時(shí)csp和csq不能同時(shí)成立，所以此式也為假，同理（gate1=q）∧（waitq=false∧gate2=p）為假，而（waitq=false∧gate2=p）∧（waitp=false∧gate2=q）也為假，得到矛盾。
　　斷言2：兩個(gè)進(jìn)程的快速算法滿足空閑讓進(jìn)的原則。
　　
　　證明：（1）當(dāng)p已經(jīng)執(zhí)行到臨界區(qū)而q剛執(zhí)行（不同時(shí)執(zhí)行算法時(shí)），p進(jìn)入臨界區(qū)。
　?。?）當(dāng)p，q同時(shí)到達(dá)時(shí)，記late（p，gate1）為p后寫gate1，記late（q，gate1）為q后寫gate1，記late（p，gate2）為p后寫gate2，記late（q，gate2）為q后寫gate2。
　?。?.1）late（p，gate1）∧late（p，gate2）時(shí)，csp為真；
　?。?.2）late（p，gate1）∧late（q，gate2）時(shí)，csq為真；
　?。?.3）late（q，gate1）∧late（q，gate2）時(shí)，csq為真；
　?。?.4）late（q，gate1）∧late（p，gate2）時(shí)，csp為真，證明完畢。
　　斷言3：兩個(gè)進(jìn)程的快速算法滿足有限等待的原則。
　　證明：（1）當(dāng)p已經(jīng)執(zhí)行到臨界區(qū)而q剛執(zhí)行（不同時(shí)執(zhí)行算法時(shí)），p進(jìn)入臨界區(qū)。兩進(jìn)程直接進(jìn)入臨界區(qū)，不用等待其他進(jìn)程。
　　（2）當(dāng)p，q同時(shí)到達(dá)時(shí)，
　　（2.1）late（p，gate1）∧late（p，gate2）時(shí)，csp為真，p直接進(jìn)入臨界區(qū)；q阻塞在q4，等待時(shí)間為p執(zhí)行臨界區(qū)的時(shí)間（常數(shù)）。
　　（2.2）late（p，gate1）∧late（q，gate2）時(shí)，csq為真，q等待常數(shù)時(shí)間；p阻塞在p2，等待時(shí)間為q執(zhí)行臨界區(qū)的時(shí)間（常數(shù)）。
　?。?.3）late（q，gate1）∧late（q，gate2）時(shí)，csq為真，q直接進(jìn)入臨界區(qū)；q阻塞在q2，等待時(shí)間為p執(zhí)行臨界區(qū)的時(shí)間（常數(shù)）。
　?。?.4）late（q，gate1）∧late（p，gate2）時(shí)，csp為真，p等待常數(shù)時(shí)間，q阻塞在q2，等待時(shí)間為p執(zhí)行臨界區(qū)的時(shí)間（常數(shù)）。證明完畢。
　　快速算法n個(gè)進(jìn)程情況只需對(duì)兩個(gè)進(jìn)程情況稍加修改，引入數(shù)組wait［n］，n個(gè)進(jìn)程都競(jìng)爭(zhēng)gate1，gate2。算法如圖3。
　　顯然，快速算法n個(gè)進(jìn)程情況跟快速兩個(gè)進(jìn)程的情況一樣，滿足互斥、空閑讓進(jìn)、有限等待三要點(diǎn)，顯然有下面斷言。
　　斷言4：如果csi為真，則?坌j（1…N）j≠i，┐csj是重言式（進(jìn)程互斥）。
　　斷言5：N個(gè)進(jìn)程的快速算法滿足空閑讓進(jìn)的原則。
　　證明：（1）當(dāng)N個(gè)進(jìn)程兩兩不同時(shí)到達(dá)時(shí)，各進(jìn)程直接進(jìn)入臨界區(qū)。
　?。?）當(dāng)N個(gè)進(jìn)程同時(shí)到達(dá)時(shí)，最后寫gate2的進(jìn)程首先進(jìn)入臨界區(qū)，剩下N-1個(gè)進(jìn)程最后寫gate2的進(jìn)程首先進(jìn)入臨界區(qū)。
　　斷言6：N個(gè)進(jìn)程的快速算法滿足有限等待的原則。
　　證明：各個(gè)進(jìn)程的平均等待的時(shí)間為O（N２），滿足有限等待。
　　4.快速算法的性能和優(yōu)勢(shì)分析
　　我們對(duì)快速算法的性能和優(yōu)勢(shì)總結(jié)以下幾點(diǎn)。
　?。?）總是有進(jìn)程在臨界區(qū)時(shí)，不會(huì)出現(xiàn)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)的服務(wù)號(hào)將無限變大（unbounded number）的情況，因?yàn)榭焖偎惴╪個(gè)進(jìn)程情況沒有用到服務(wù)號(hào)。
　?。?）使用的共享變量只有N個(gè)，即wait［0…N-1］，比bakery算法的2N個(gè)共享變量少N個(gè)，大大減少在分布式環(huán)境下進(jìn)程之間信息交換量。
　?。?）bakery算法中，當(dāng)沒有別的進(jìn)程進(jìn)入臨界區(qū)時(shí)，本進(jìn)程進(jìn)入臨界區(qū)之前要和N-1個(gè)進(jìn)程的服務(wù)號(hào)進(jìn)行比較，而快速算法此情況下本進(jìn)程直接進(jìn)入臨界區(qū)，提高了速度；當(dāng)有N個(gè)進(jìn)程競(jìng)爭(zhēng)進(jìn)入臨界區(qū)時(shí)，快速算法中各個(gè)進(jìn)程少max（Number［1］，...，Number［N］）操作，同時(shí)少本進(jìn)程同其他進(jìn)程號(hào)比較操作，大大提高了進(jìn)程的執(zhí)行速度。
　　5.結(jié)論
　　對(duì)bakery算法進(jìn)行改進(jìn)后的快速算法克服了服務(wù)號(hào)將無限變大（unbounded number）的弊端，同時(shí)減少了分布式環(huán)境進(jìn)程之間的信息交換量，提高了進(jìn)程的執(zhí)行速度，而且滿足進(jìn)程互斥設(shè)計(jì)時(shí)的互斥，空閑讓進(jìn)、有限等待三要點(diǎn)。快速算法的引入將大大提高互聯(lián)網(wǎng)上的資源共享的效率，提高互聯(lián)網(wǎng)應(yīng)用程序的運(yùn)行效率。
　　
　　參考文獻(xiàn)：
　?。?］Chen，Y，Welch，J.Self-Stabilizing Mutual Exclusion Using Tokens in Mobile Ad Hoc Networks.Proceedings of the 6th international workshop on Discrete Algorithms and methods for mobile computing and communications，2002：34-42.
　　［2］Sujata Banerjee.A New Token Passing Distributed Mutual Exclusion Algorithm.Proceedings of the Intl.Conf.on Distributed Computing Systems （ICDCS），1996.
　　［3］Hadzilacos V.A Note on Group Mutual Exclusion，Proceedings of the 20th ACM Symposium on Principles of Distributed Computing （PODC），2001.
　　注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文