tech-sjh

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;">

沒有留言:

張貼留言

版權宣告、免責聲明


姓名標示、非商業性、相同方式分享3.0台灣授權條款授權。
免責聲明: 本文所載資料僅供參考,並不構成投資建議,
讀者閱讀或使用該資料所導致結果需要自擔風險與責任,
作者概不承擔閱讀人行為之任何風險與責任。
除非有特別宣稱,作者言論並不代表所屬任何團體、公司、或其他人意見。