顯示具有 bakery 標籤的文章。 顯示所有文章
顯示具有 bakery 標籤的文章。 顯示所有文章

2008年3月20日 星期四

bakery algorithm

Bakery algorithm originates from a
scheduling algorithm which is applied in
distributed environment. When solving
critical section problem, it is put in a
centralized environment for more than
two processes.

the two process critical section solution
algorithm is roughly as follow:
(from Operatin System Concepts by
Silberschatz Galvin fifth edtion page
161)

repeat
/* 為方便起見 以下以 CS 代表
critical section */
flag[i] = true;
/* flag 是記錄每個 process i 進入 CS 的
"意願" */
turn = j;
/* turn 是此 CS 現在 "准許第 j 號的
process" 進入 CS */
/* 當 j 有意願且輪到 j 時,i 必須等 j
離開 CS, flag[j] 改為 false */
while (flag[j] and turn = j) do no-op;

/* critical section */

flag[i] = false;
/* 每次 process i 離開 CS 後需重新表達
意願才可再進入 */

/* remainder section */
until false;

Begin of Leslie Lamport Bakery
algorithm...

shared array: number[], choosing[];

/* 共有 n 個 (0 到 n-1) process
起始狀態 */
for(j = 0; j < j =" 0;">