這個思想來自于面包店, 醫(yī)院等, 需要排隊取號的場所. 顧客進(jìn)入面包店前蹭越，首先抓取一個號碼竭沫，然后按號碼從小到大的次序依次進(jìn)入面包店購買面包.
注意點(diǎn)：
- 面包店按由小到大的次序發(fā)放號碼
- 兩個或兩個以上的顧客有可能得到相同號碼
- 當(dāng)多個顧客抓到相同號碼伙判，則較小的先執(zhí)行
1 // 變量說明:
2 // i 表示當(dāng)前進(jìn)程PID
3 // j 表示當(dāng)前迭代到的進(jìn)程PID
4 // choosing[i] 表示當(dāng)前進(jìn)程i是否正在取號, 默認(rèn)值為false
5 // number[i] 表示當(dāng)前進(jìn)程i的排隊號, 默認(rèn)值為0
6
7 process(i) {
8 while (true) {
9 // 當(dāng)前進(jìn)程i正在取號
10 choosing[i] = true;
11 // number為上一個已發(fā)放的排隊號加1
12 number[i] = 1 + max(number[1], number[2], ..., number[n-1]);
13 // 當(dāng)前進(jìn)程i取號完畢
14 choosing[i] = false;
15
16 // 迭代所有進(jìn)程
17 for (j = 0; j < n; j++) {
19 // 若當(dāng)前迭代到的進(jìn)程j正在取號, 則等待其取號完畢
20 while(choosing[j]);
21
22 // 同時滿足, 當(dāng)前進(jìn)程才能通過阵谚，若多個進(jìn)程取到相同的號碼
// 若j < i，則進(jìn)程j先執(zhí)行严卖，進(jìn)程i在此死循環(huán)等候席舍，等到j(luò)執(zhí)行完，此時number[j]會變?yōu)?
23 while (number[j] != 0 && (number[j], j) < (number[i], i));
24 }
25
26 // 臨界區(qū)代碼
27
28 // 當(dāng)前進(jìn)程注銷排隊號
29 // 一旦線程在臨界區(qū)執(zhí)行完畢哮笆，需要把自己的排隊簽到號碼置為0来颤，表示處于非臨界區(qū)
30 number[i] = 0;
31
32 // 其它代碼
33
34 }
35 }
代碼示例分析，三個進(jìn)程p0 p1 p2：
p0 p1 p2
0 0 1 // p2一騎絕塵稠肘，率先執(zhí)行完所有代碼福铅，此時choosing[0][1]為false，且number[0][1]為0
1 1 0 // p1先迭代项阴，看到p0滑黔，會等到p0也進(jìn)入迭代，此時都會進(jìn)入第二個while循環(huán)
// p1迭代時环揽，number[0] != 0 并且 (number[0], 0) < (number[1], 1)略荡，所以死循環(huán)卡住
// p0迭代時，j = 0不會卡浊附骸汛兜；
// j = 1，(number[1], 1) < (number[0], 0)不滿足通今，也不會卡字嗝；
// j = 2也不會卡住辫塌，因此會進(jìn)入臨界區(qū)執(zhí)行帝嗡，并且最后number[0]
0 1 0 // 此時p1檢測到number[0]為0，跳出死循環(huán)
具體解釋：
-
- 進(jìn)程需要排隊等待的三種情況:
- 情況1: 存在沒有取得排隊號的進(jìn)程
- 情況2: 當(dāng)前迭代到的進(jìn)程沒有取得排隊號
- 情況3: 當(dāng)前迭代到的進(jìn)程的排隊號小于當(dāng)前進(jìn)程的排隊號, 或當(dāng)前迭代到的進(jìn)程PID小于當(dāng)前進(jìn)程PID
- 只有當(dāng)前進(jìn)程注銷了排隊號, 在排隊的其它進(jìn)程才能進(jìn)入臨界區(qū), 滿足進(jìn)程互斥和有限等待
- 符號說明: (a, b) < (c, d) 表示 (a < c) or ((a == c) and (b < d))
- 使用choosing數(shù)組是必須的, 假設(shè)不使用choosing數(shù)組, 就可能會出現(xiàn)這種情況: 設(shè)進(jìn)程i的優(yōu)先級高于進(jìn)程j(即 i < j), 兩個進(jìn)程獲得了相同的number, 進(jìn)程i在寫number[i]之前, 被優(yōu)先級低的進(jìn)程j搶先獲得了CPU時間片, 這時進(jìn)程j讀取到的number[i]為0, 因此進(jìn)程j進(jìn)入了臨界區(qū). 隨后進(jìn)程i又獲得CPU時間片, 它讀取到的number[i]與number[j]相等, 且i < j, 因此進(jìn)程i也進(jìn)入了臨界區(qū). 這樣, 兩個進(jìn)程同時在臨界區(qū)內(nèi)訪問, 可能會導(dǎo)致數(shù)據(jù)腐爛(data corruption). 算法使用了choosing數(shù)組變量, 使得修改number數(shù)組的元素值變得"原子化", 解決了上述問題
