multithreading - 如何使对象(可变堆栈)线程安全？

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
}

这个类显然不是线程安全的。我想让它成为线程安全的。

提前致谢

生命值

Answer 1

正因为它很有趣，您还可以通过将 head 弹出到 AtomicReference 中并完全避免 synchronized 来使其成为线程安全的。因此:

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)并将 that 放入 AtomicReference 中。