參考Ktor Pool implementation，可能有人解釋這種 pop 和 push 實作背后的概念。我試圖單步執行代碼，但在研究代碼后我仍然不聰明。
以下是我難以理解的代碼片段：
private fun pushTop(index: Int) {
require(index > 0) { "index should be positive" }
while (true) { // lock-free loop on top
val top = this.top // volatile read
val topVersion = (top shr 32 and 0xffffffffL) 1L
val topIndex = (top and 0xffffffffL).toInt()
val newTop = topVersion shl 32 or index.toLong()
next[index] = topIndex
if (Top.compareAndSet(this, top, newTop)) return
}
}
private fun popTop(): Int {
// lock-free loop on top
while (true) {
// volatile read
val top = this.top
if (top == 0L) return 0
val newVersion = (top shr 32 and 0xffffffffL) 1L
val topIndex = (top and 0xffffffffL).toInt()
if (topIndex == 0) return 0
val next = next[topIndex]
val newTop = newVersion shl 32 or next.toLong()
if (Top.compareAndSet(this, top, newTop)) return topIndex
}
}
這可以寫成更簡單的方式嗎？
uj5u.com熱心網友回復：
有兩件事使這段代碼看起來有點不尋常。首先是它被設計為由多個執行緒訪問而不使用鎖。第二個是它使用單個 64 位值來存盤兩個 32 位整數。
鎖定自由
這看起來像是無鎖堆疊的一些變體。它被設計為由多個執行緒同時訪問。粗略的演算法是這樣作業的：
- 獲取舊值并記下它
- 確定新值應該是什么
- 當且僅當該值仍然與我們在開始時看到的舊值匹配時，才執行原子比較和設定以替換該值
- 如果比較并設定失敗（即在我們計算新值時其他人更改了值），則回圈回到開始并重試
像這樣的無鎖演算法可能更適合某些型別的應用程式的性能。另一種方法是鎖定整個堆疊，以便當一個執行緒正在使用堆疊時，所有其他執行緒都必須等待。
位移位
使這段代碼看起來更復雜的另一件事是它似乎在一個變數中存盤了兩個值。index傳遞給的值pushTop是一個 32 位整數。然后version在存盤之前與 32 位遞增計數器組合。所以top實際上是一個 64 位值，其中前 32 位是“版本”，后 32 位是我們傳入的“索引”。同樣，這種緊湊的存盤格式可能是一種性能優化。
如果我們向 中的代碼添加一些注釋pushTop，它看起來像這樣：
val top = this.top // get the current 64-bit value containing 'version' and 'index'
val topVersion = (top shr 32 and 0xffffffffL) 1L // get the 32 high bits (version) and add 1
val topIndex = (top and 0xffffffffL).toInt() // get the 32 low bits (the old index)
val newTop = topVersion shl 32 or index.toLong() // combine version and new index to a new 64-bit value
您可以在popTop. 如果堆疊包含重復項，則可能包含版本號，以便無鎖演算法可以區分相同值的不同副本之間的差異。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/324549.html