Concurrent Java 3 - Higher level abstraction

Critical Sections (Isolation)

我們定義被(low level construct, e.g. lock)保護的某段code稱為critical section，critical section被視為一個atomic unit (mutual exclusion)，所以任何thread一旦開始執行critical section，其他的thread只會看到離開critical section的結果 (可能因為要acquire lock被block住)，而不會看到中間的state變化。

可以抽象的說，我們把此段code獨立出來了，稱為isolated。

Object-based Isolation (Monitor)

critical sections保護的是一段code，但是有時候其中牽涉到的物件其實並沒有shared memory，例如以下linked list deletion:

thread T1 delete B只牽涉到node A和node C，而thread T3 delete E只牽涉到 node D和node F，沒有道理不能同時執行delete(B)和delete(E)

所以我們需要一個object-based isolation，也就是跟關聯物件群有關的孤立，基本規則是:如果兩個isolation關聯的物件群是空集合的話，這兩個isolation就可以run in parallel，否則只能run mutual exclusively。

跟monitor的關係是: monitor是一個class，其instance method可能都isloated on 某個object set M。所以兩個monitors A和B，如果A和B的methods的isolation set都無交集的話，則使用這兩個monitor保護的code可以run in parallel。


一個範例是找出某個undirected graph的spanning tree (可能有多個可能)_:

可以用DFS來走片整個graph:

每個neighbor c可以生出一個thread來執行recursion COMPUTE(c)，但是在MAKEPARENT的method就要注意，有可能兩個vertices要搶當同一個neighbor c的parent，這時候就可以用object isolation on c來保證mutual exclusiveness。 當然同時也不會阻擋跟c無關的parallelism被犧牲，如果把整個MAKEPARENT用critical section保護的話就會犧牲了一些parallelism。

Java Atomic Variable: Object isolation semantics

Java atomic variable實現了部分object isolation semantics，對某個物件提供了atomic operation，並且針對需要atomic operation的patterns可以考慮使用atomic variable，因為這在硬體上有efficient implementation:

1. get and add pattern:

舉例來說，以下integer update就是一個 get-and-add pattern，可以使用atomic integer:

2. compare-and-set
如果要比對某個object reference是否相等才去做事，也可以用atomic reference。