如何使對象（一個可變堆棧）線程安全？

Question

如何使Scala對象線程安全。

class Stack { 
    case class Node(value: Int, var next: Node) 

    private var head: Node = null 
    private var sz = 0 

    def push(newValue: Int) { 
     head = Node(newValue, head) 
     sz += 1 
    } 

    def pop() = { 
     val oldNode = head 
     head = oldNode.next 
     oldNode.next = null 
     sz -= 1 
    } 

    def size = sz //I am accessing sz from two threads 
} 

這個類顯然不是線程安全的。我想讓它線程安全。

由於事先

HP

Answer 1

在我看來，最簡單的方法，使這項有意義的線程安全的情況如下：

class Stack { 
    case class Node(value: Int, var next: Node) 

    private var head: Node = null 
    private var sz : Int = 0 

    def push(newValue: Int) { 
     synchronized { 
      head = Node(newValue, head) 
      sz += 1 
     } 
    } 

    def pop() : Option[Int] = { 
     synchronized { 
      if (sz >= 1) { 
       val ret = Some(head.value) 
       val oldNode = head 
       head = oldNode.next 
       oldNode.next = null 
       sz -= 1 
       ret 
      } else { 
       None 
      } 
     } 
    } 

    def size = synchronized { sz } 
} 

此實現將允許你保證push和pop將是原子，pop返回一個Some包裝它從堆棧頂部刪除的值或None如果堆棧是已經空了。

請注意，對大小的訪問是同步的，但是無法保證它在返回後的任何時刻都是正確的，因爲多個線程可以訪問堆棧，可能會改變其大小。如果你確實需要準確地知道尺寸，那麼你就必須採取不同的方式，在使用時在整個堆棧上進行同步。

Answer 2

僅僅因爲它很有趣，您還可以通過將head彈出爲AtomicReference並完全避免​​來使此線程安全。正是如此：

final class Stack { 
    private val head = new AtomicReference[Node](Nil) 

    @tailrec 
    def push(newValue: Int) { 
    val current = head.get() 
    if (!head.compareAndSet(current, Node(newValue, current))) { 
     push(newValue) 
    } 
    } 

    @tailrec 
    def pop(): Option[Int] = head.get() match { 
    case current @ Cons(v, tail) => { 
     if (!head.compareAndSet(current, tail)) 
     pop() 
     else 
     Some(v) 
    } 

    case Nil => None 
    } 

    def size = { 
    def loop(node: Node, size: Int): Int = node match { 
     case Cons(_, tail) => loop(tail, size + 1) 
     case Nil => size 
    } 

    loop(head.get(), 0) 
    } 

    private sealed trait Node 
    private case class Cons(head: Int, tail: Node) extends Node 
    private case object Nil extends Node 
} 

這避免完全鎖定，並提供比​​版本大幅提高吞吐量。值得注意的是，這種假線程安全的數據結構很少是一個好主意。在數據結構級別處理同步和狀態管理問題有點像嘗試處理XML解析器中的IO異常：您試圖在錯誤的地方解決正確的問題，並且您沒有所需的信息去做。例如，上面的堆棧非常安全，但在操作中它肯定不一致（例如，您可以推入並隨後彈出到堆棧並因此得到None）。

你更好的選擇是使用一個不變的堆棧（如List），並拋出是爲AtomicReference，如果你需要共享的可變狀態。