2011年3月8日 星期二

[Distributed Algorithms] 第二堂: Mutual exclusion

今天講了三個主題:
 Asynchronous shared memory model,
 Mutual exclusion problem definition,
 Dijkstra's mutual exclusion algorithm 
老師花了很長的時間再講 OS 的 Mutual Exclusion,
old-hw1.pdf 是 mutual exclusion 的 algorithm,
http://en.wikipedia.org/wiki/Eisenberg_McGuire_algorithm 不過 wiki 的這個版本就講得蠻清楚的了。


old-hw1_ans.pdf 裡面是解答。


證明要證明三件事:

  • Safety
  • Progress (Liveness)
  • bound waiting of (n-1) turn
這演算法基本上是講你要進入 CS ,第一要聲明想進去,第二要拿到權杖 (turn)...
好像以前補 OS 的時候有講到這個演算法 (遙遠的回憶啊~~)

我自己的問題是 turn := i 這行需不需要 atomic ...

這次還不習慣老師講解的方式,筆記做的很糟糕~~
我抓的 pdf 和課本好像也不太對 = =

XD 再加油





沒有留言:

張貼留言