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 再加油
沒有留言:
張貼留言