算法目的
用於解決多執行緒同步
算法思想
該算法的基本思想源於顧客在麵包店中購買麵包時的排隊原理. 顧客在進入麵包店前, 首先抓一個號, 然後按照號碼由小到大的次序依次進入麵包店購買麵包. 這裡, 麵包店發放的號碼是由小到大的, 但是兩個或兩個以上的顧客卻有可能得到相同的號碼(使所抓號碼不同需要互斥), 如果多個顧客抓到相同的號碼, 則規定按照顧客名字的字典次序進行排序, 這裡假定顧客是沒有重名的. 在計算機系統中, 顧客就相當於進程, 每個進程有一個唯一的標識, 我們用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);
