Concurrent Java 5 - Concurrent Data Strucutures

Optimistic Concurrency

這是一個implementation strategy，主是要給impelement concurrent library的人使用的，例如Java的AtomicInteger。

optimistic concurrency是假設multithreads在讀寫shared variables的時候，終究會發生atomic operation，也就是某一thread不受其他thread干擾，彷彿single thread一樣做了該做的事，當此情況發生(當然是opimistic)，即便在多執行續狀況中，答案就是正確的。

不過要這樣搞，就得要在implementation中加入retry 的機制，並且還是要有atomic construct才能達到，例如以下是AtomicInteger可能的使用optimistic concurrency strategy的implementation:

上圖中可以看到，GET_AND_ADD這個implementation有個while (true) loop，loop內就是optimistic trial，不過還\是得依賴COMPARE_AND_SET這個atomic operation，這個operation檢查cur是否還是原來的值，沒被其他thread汙染，如果是的話就set成新值，並且return。

這個implementation保證沒有deadlock，因為沒有任何lock。
也保證沒有livelock，雖然在此沒有證明。

Concurrent Queue

這個也應該會用optimistic concurrency 來比較efficiently implement:

注意tail應該是用AtomicReference instance，所以才會有COMPARE_AND_SET method。
BJ4。

Linearizability

這是在講concurrent program中，任一個thread的執行順序至少要符合其內的先後順序，例如先執行x再執行y，如果發現結果出現最後才執行x的話，就一定是有錯誤的。

某些operation可以linearizable去reason正確性，但有一些operation沒辦法，例如deleteAll()，因為沒有明確定義delete的順序。

Concurrent Minimum Spanning Tree

這邊嘗試把sequential的MST edge contraction演算法給parallelize:

這邊有幾個sychronization要注意:
1. 兩個vertices要被merge的話，應該都要acquire這兩個vertices的lock，避免不同thread同時對其中一個 (不可能是兩個，因為REMOVE是concurrent data structuree的operation，保證是thread-safe)做edge contraction。

2. data structure要選用concurrent data structure，例如ConcurrentLinkedQueue，這樣就能確保REMOVE / INSERT這樣的 operation是thread-safe。