進程互斥bakery算法改進的思想

　　摘 要： 本文簡要地介紹了bakery算法進程互斥思想，指出它存在的三個缺點。然后在滿足進程互斥設計三要點的前提下，提出快速互斥算法，并且對它的性能和優(yōu)點給出證明，指出快速算法能夠很好地解決bakery算法的缺點。
　　關鍵詞： bakery算法 快速算法 進程互斥 空閑讓進 有限等待
　　
　　1.進程互斥算法的應用背景
　　如今，互聯網上有大量的資源供用戶使用，這些資源很多都是臨界資源。互聯網上大量進程都要使用這些臨界資源。由于臨界資源共享時要互斥訪問，這就使得這些進程在訪問臨界資源時要互斥進入自己的臨界區(qū)。
　　進程互斥進入臨界區(qū)算法設計時要注意三點：（1）互斥訪問（mutual exclusion）［１］［２］［３］，即是每次只能有一個進程進入自己的臨界區(qū)，同一時間不能兩個或兩個以上進程進入臨界區(qū)。（2）空閑讓進（progress），即是當沒有進程在臨界區(qū)執(zhí)行，有一些進程要進入臨界區(qū)時，只有那些不在remainder section中執(zhí)行的進程有權決定誰進入臨界區(qū)，并且這決定不能無限推遲。（3）有限等待（bounded waiting），即是進程從申請進入臨界區(qū)到進入臨界區(qū)這段時間是一段有限的時間，進程不能無限等待進入。
　　互聯網上共享臨界資源進程只有遵循以上三點，進程執(zhí)行的結果才不會出錯。也只有在遵循以上三點的基礎上，互聯網上的應用程序才能為用戶提供可靠的資源訪問。
　　目前，對進程互斥分布式算法設計主要分為三類，即（1）permission-based（e.g.Lamport，Ricart-Agrawala，Singhal，Maekawa ），思想是每一個進程在進入臨界區(qū)之前要得到所有其他進程的準許。（2）token-based （Suzuki-Kazami，Raymond ，Naimi-Trehel，Neilsen-Mizuno，Chang，Singhal and Liu ），思想是整個系統有一個token，只有得到token的進程才能進入臨界區(qū)。（3）Quorum based，思想是所有進程中，部分進程決定某進程是否可以進入臨界區(qū)。
　　2.bakery算法設計的思想
　　Bakery算法是一種簡單的處理n個進程互斥進入臨界區(qū)的算法。它基于面包店里普遍使用的一種算法。顧客進入面包店的時候首先得到一個服務號碼，得到最小號碼的顧客首先得到服務。基于這一思想，bakery算法處理N個進程互斥時對共享變量的讀寫采用原子操作來實現，每個進程都擁有一個屬于自己的共享變量。這個共享變量指示本進程在等待進入臨界區(qū)的位置，只有當本變量指示等待隊列的頭部時，本進程才優(yōu)先進入臨界區(qū)。只有本進程才可以對屬于自己的共享變量讀寫，別的進程只能讀。Bakery算法代碼如圖1。
　　在本算法中，不同顧客可能得到同一個號碼。為此，我們有定義1。
　　定義1：有二元組（number［i］，i）和（number［j］，j），當number［i］＜number［j］或者number［i］=number［j］并且i＜j時，有（number［i］，i）＜（number［j］，j）。
　　定義1的意思是：顧客i的服務號碼number［i］＜顧客j的服務號碼number［j］時，或者顧客i和顧客j的服務號碼相等，但i＜j時，顧客i先服務。在圖1中，Bakery算法滿足下面三個申明。
　　申明（1）（進程互斥）
　　□［?坌0…N-1 i，j，i!=j：：Z（i，j）］，where Z（i，j）：┐（πid［i］ on CS∧id［j］ on CS）
　　申明（2）（空閑讓進）
　　［?坌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為進程i從申請進入臨界區(qū)到進入臨界區(qū)的等待時間。
　　T1為執(zhí)行a2：num［i］=max（num［0］，num［1］，…，num［N-1］）+1所用時間；
　　T2為執(zhí)行臨界區(qū)代碼所用時間。
　　3.用快速算法對bakery算法的改進
　　bakery算法解決了n個進程互斥問題，滿足進程互斥時三要點。但bakery算法存在以下實際的缺點。
　　（1）總是有進程在臨界區(qū)時，進程申請進入臨界區(qū)的服務號將無限變大（unbounded number）。
　　（2）使用的共享變量多，兩個共享數組有2N個共享變量，在分布式環(huán)境下使得進程之間信息交換量增大。
　　（3）程進入臨界區(qū)之前要和N-1個進程的服務號進行比較，不管是否有別的進程要進入臨界區(qū)，這無疑會使進程的運行速度變慢。
　　為此我們提出了進程互斥的快速算法（fast for n processes），可以有效地解決以上bakery算法存在的問題。
　　為了引入快速算法，先還是引入快速算法的簡單情況，兩個進程的快速算法。可以把bakery算法分成六個部分：start，doorway，ticket assignment，wait section，critical section and final。Start即執(zhí)行算法初始化代碼，進程i在doorway處即進程i執(zhí)行完了choosing［i］=true，ticket即執(zhí)行Number［i］=1+max（Number［1］，...，Number［N］），wait section即互斥循環(huán)，critical section即臨界區(qū)，final即出臨界區(qū)善后代碼。而快速算法的思想是設置gate1和gate2，只有同時得到gate1和gate2進程優(yōu)先進入臨界區(qū)，并且后得到者優(yōu)先進入臨界區(qū)。在快速算法中我們假定對共享變量的操作都是原子操作。圖2是兩個進程的快速算法。
　　斷言1：┐（csp∧csq）是重言式（進程互斥）。
　　證明：反正法。假設（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）為真。
　　式子（3）中用∨連接的每一項都是假。（gate1=p）∧（gate1=q）為假，而（gate1=p）∧（waitp=false∧gate2=q）時csp和csq不能同時成立，所以此式也為假，同理（gate1=q）∧（waitq=false∧gate2=p）為假，而（waitq=false∧gate2=p）∧（waitp=false∧gate2=q）也為假，得到矛盾。
　　斷言2：兩個進程的快速算法滿足空閑讓進的原則。
　　
　　證明：（1）當p已經執(zhí)行到臨界區(qū)而q剛執(zhí)行（不同時執(zhí)行算法時），p進入臨界區(qū)。
　　（2）當p，q同時到達時，記late（p，gate1）為p后寫gate1，記late（q，gate1）為q后寫gate1，記late（p，gate2）為p后寫gate2，記late（q，gate2）為q后寫gate2。
　　（2.1）late（p，gate1）∧late（p，gate2）時，csp為真；
　　（2.2）late（p，gate1）∧late（q，gate2）時，csq為真；
　　（2.3）late（q，gate1）∧late（q，gate2）時，csq為真；
　　（2.4）late（q，gate1）∧late（p，gate2）時，csp為真，證明完畢。
　　斷言3：兩個進程的快速算法滿足有限等待的原則。
　　證明：（1）當p已經執(zhí)行到臨界區(qū)而q剛執(zhí)行（不同時執(zhí)行算法時），p進入臨界區(qū)。兩進程直接進入臨界區(qū)，不用等待其他進程。
　　（2）當p，q同時到達時，
　　（2.1）late（p，gate1）∧late（p，gate2）時，csp為真，p直接進入臨界區(qū)；q阻塞在q4，等待時間為p執(zhí)行臨界區(qū)的時間（常數）。
　　（2.2）late（p，gate1）∧late（q，gate2）時，csq為真，q等待常數時間；p阻塞在p2，等待時間為q執(zhí)行臨界區(qū)的時間（常數）。
　　（2.3）late（q，gate1）∧late（q，gate2）時，csq為真，q直接進入臨界區(qū)；q阻塞在q2，等待時間為p執(zhí)行臨界區(qū)的時間（常數）。
　　（2.4）late（q，gate1）∧late（p，gate2）時，csp為真，p等待常數時間，q阻塞在q2，等待時間為p執(zhí)行臨界區(qū)的時間（常數）。證明完畢。
　　快速算法n個進程情況只需對兩個進程情況稍加修改，引入數組wait［n］，n個進程都競爭gate1，gate2。算法如圖3。
　　顯然，快速算法n個進程情況跟快速兩個進程的情況一樣，滿足互斥、空閑讓進、有限等待三要點，顯然有下面斷言。
　　斷言4：如果csi為真，則?坌j（1…N）j≠i，┐csj是重言式（進程互斥）。
　　斷言5：N個進程的快速算法滿足空閑讓進的原則。
　　證明：（1）當N個進程兩兩不同時到達時，各進程直接進入臨界區(qū)。
　　（2）當N個進程同時到達時，最后寫gate2的進程首先進入臨界區(qū)，剩下N-1個進程最后寫gate2的進程首先進入臨界區(qū)。
　　斷言6：N個進程的快速算法滿足有限等待的原則。
　　證明：各個進程的平均等待的時間為O（N２），滿足有限等待。
　　4.快速算法的性能和優(yōu)勢分析
　　我們對快速算法的性能和優(yōu)勢總結以下幾點。
　　（1）總是有進程在臨界區(qū)時，不會出現進程申請進入臨界區(qū)的服務號將無限變大（unbounded number）的情況，因為快速算法n個進程情況沒有用到服務號。
　　（2）使用的共享變量只有N個，即wait［0…N-1］，比bakery算法的2N個共享變量少N個，大大減少在分布式環(huán)境下進程之間信息交換量。
　　（3）bakery算法中，當沒有別的進程進入臨界區(qū)時，本進程進入臨界區(qū)之前要和N-1個進程的服務號進行比較，而快速算法此情況下本進程直接進入臨界區(qū)，提高了速度；當有N個進程競爭進入臨界區(qū)時，快速算法中各個進程少max（Number［1］，...，Number［N］）操作，同時少本進程同其他進程號比較操作，大大提高了進程的執(zhí)行速度。
　　5.結論
　　對bakery算法進行改進后的快速算法克服了服務號將無限變大（unbounded number）的弊端，同時減少了分布式環(huán)境進程之間的信息交換量，提高了進程的執(zhí)行速度，而且滿足進程互斥設計時的互斥，空閑讓進、有限等待三要點。快速算法的引入將大大提高互聯網上的資源共享的效率，提高互聯網應用程序的運行效率。
　　
　　參考文獻：
　　［1］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.
　　注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文