如何使对象（一个可变堆栈）线程安全？

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，如果你需要共享的可变状态。