Udemy Course Multithreading, Concurrency & Performance 35

Stack — Lock Free Data Structure

考慮一種Stack的資料結構如下

一個有開口的箱子,存放著物件:

Stack:

白箱子,黑框為物件

Stack — Push(T value):

放入新的物件(黑框),也只能從最頂端開始放入如下

Stack — Pop():

這個資料結構下,要移除物件只能從最頂端的物件開始動手

實際上就像LinkedList一樣有順序性:

以下將以Java撰寫出這種資料結構:

1.首先定義出Stack物件

上面this.next等號右邊的next是箱子內的Linkedlist

2.實際的Stack資料操作會有兩個Method(放push & 拿pop)

2.1 放push

2.2拿走pop

由左演變為右

如果放push & 拿走pop都沒寫synchronized仍用MultiThread執行的話?

則會有明顯的Race Condition的狀況,尤指下列位置

考量兩個Method都沒寫synchronized修飾字的情況,將無法確保head & counter準確性

目前Code如下:

接著將捨棄synchronized修飾字,用Atomic方式改寫

(之後為了比較,寫成另一個java檔)

1.StackNode結構不變:

2.建立LockFreeStack class並有以下內容

2.1 LockFreeStack內的push Method

由於是MultiThread考量,要寫成while

2.2 LockFreeStack內的pop Method

2.3比較上述兩個Method寫法:

3.接著還要統計執行的數量:

新增宣告AtomicInteger

目前完整Code如下:

接著比較兩者(Lock(synchronized修飾字) vs Atomic(無Lock))哪個好

在StandardStack那邊寫入Main:

1.Lock(synchronized修飾字)在10秒內的計算次數為

重複執行:

接著在LockFreeStack的Main寫入:

2.Atomic(無Lock)在10秒內的計算次數為

但是再次執行有時候會得到:

完整Code如下:

以下為講師的Code,只切換不同型別的stack物件

在做LockFreeStack型別,不同次得到以下結果

浮動很大

主要跟硬體設備有關,如下也有其他學生問到依樣狀況

問題詳細連結

其他回應:

講師版完整Code如下:

相關CAS知識補充說明

可以看看上面連結更了解Atomic的CAS可能也不是那麼萬能

spinning,只對單一Resource有效,ABA問題...等

參考課程