How to make object (a mutable stack) thread-safe?

Question

How to make Scala object thread-safe.

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
}

This class is clearly not threadsafe. I want to make it threadsafe.

Thanks in Advance,

HP

Answer 1

Just because it's fun, you can also make this thread-safe by popping head into an AtomicReference and avoiding synchronized altogether. Thusly:

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
}

This avoids locking entirely and provides substantially better throughput than the synchronized version. It's worth noting though that this sort of fake thread-safe data structure is rarely a good idea. Handling synchronization and state management concerns at the level of a data structure is a bit like trying to handle IO exceptions within an XML parser: you're trying to solve the right problem in the wrong place and you don't have the information needed to do that. For example, the stack above is perfectly safe, but it's certainly not consistent across operations (e.g. you could push and subsequently pop onto a stack and get None as a result).

Your better option is to use an immutable stack (like List) and throw that into an AtomicReference if you need shared mutable state.

Answer 2

To my mind, the easiest way to make this meaningfully thread-safe would be as follows:

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 }
}

This implementation would allow you to ensure that push's and pop's would be atomic, with pop returning a Some wrapping the value it removed from the top of the stack or None if the stack was already empty.

As a note, access to the size is synchronized, but you have no way of guaranteeing that it will be correct at any point after it is returned, since multiple threads are able to access the stack, potentially altering its size. If you really do need to know the size exactly accurately, you would have to go about this differently, synchronizing on the whole stack when you use it.