2011年3月21日 星期一

[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 要夠用 
嘆!!




沒有留言:

張貼留言