麵包店算法

麵包店算法該算法的基本思想源於顧客在麵包店中購買麵包時的排隊原理. 顧客在進入麵包店前, 首先抓一個號, 然後按照號碼由小到大的次序依次進入麵包店購買麵包。在計算機系統中, 顧客就相當於進程, 每個進程有一個唯一的標識, 我們用P的下面加一個下標來表示。

基本介紹

• 中文名：麵包店算法
• 外文名：Bakery Algorithm
• 算法目的：用於解決多執行緒同步
• 基本思想源於：顧客在麵包店中購買麵包時的排隊
• 步驟：首先抓一個號, 然後按號入麵包店

算法目的

用於解決多執行緒同步

算法思想

該算法的基本思想源於顧客在麵包店中購買麵包時的排隊原理. 顧客在進入麵包店前, 首先抓一個號, 然後按照號碼由小到大的次序依次進入麵包店購買麵包. 這裡, 麵包店發放的號碼是由小到大的, 但是兩個或兩個以上的顧客卻有可能得到相同的號碼(使所抓號碼不同需要互斥), 如果多個顧客抓到相同的號碼, 則規定按照顧客名字的字典次序進行排序, 這裡假定顧客是沒有重名的. 在計算機系統中, 顧客就相當於進程, 每個進程有一個唯一的標識, 我們用P的下面加一個下標來表示. 例如: 對於 Pi和Pj, 如果有i<j, 則先為Pi服務, 即Pi先進入臨界區

算法代碼

boolean choosing[n];表示進程是否在取號

int number[n];記錄每個進程取到的號碼

這些數據結構分別初始化為false和0，為了方便，定義如下符號：

若a<c或a==c和b<d同時成立，（a，b）<（c，d）

do

{

choosing[i] = true;

number[i] = max{number[0],number[1],…,number[n-1]}+1;//選號碼

choosing[i] = false;

for(j = 0; j<n; j++)

{

while (choosing[j]);

while ((number[j] != 0) && (number[j],j)<(number[i],i));

};

//臨界區

number[i] = 0;

//其餘部分

}while(1);