[Distributed Algorithms] 第二堂: Mutual exclusion (3)

一開始先證明 Burnme 演算法，"存在"這個觀念就很重要了 = =
不過剛開始超想睡覺，一度有昏睡過去，就沒有聽清楚老師在講什麼。


接下來講的是 Bakery Algorithm

以前 OS 課本有，好像有點印象 = =
觀念就是拿號碼牌，但因為 muti-process 可能有兩個拿到同樣號碼的號碼牌，所以需要用 choosing 擋住。
老師舉了一個例子，把 choosing 拿掉時，兩個 process 進入 CS 的例子。


這個 algorithm 假設，號碼牌是 unbounded，有人好像花很多時間用改善到 bounded 但....
















再來介紹，Lower bound on the number of register
說明為什麼 n 個 process 要有 n 個 shared variable 才能夠保證同步。(有用到鴿籠原理)
這證明用到很多 lemma ，indistinguishable、idle 的定義。

若是硬體有支援， compare and swap 這樣的 test-and-set 指令的話，那同步演算法就很好設計了，
Read modify write shared variable (但是硬體昂貴) 證明 Bounded by pass 

• 只要 1 個 register 就好 (跟 shared memory model不同)
• 但是 number of bits 要夠用 

嘆!!