Как сделать объект (изменяемый стек) поточно-ориентированным?

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

Просто потому, что это весело, вы также можете сделать этот потокобезопасным, вставив 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
}

Это полностью исключает блокировку и обеспечивает существенно лучшую пропускную способность, чем версия synchronized.Стоит отметить, что такая фальшивая поточно-ориентированная структура данных редко бывает хорошей идеей.Обработка проблем синхронизации и управления состоянием на уровне структуры данных похожа на попытку обработки исключений ввода-вывода в синтаксическом анализаторе XML: вы пытаетесь решить нужную проблему в неправильном месте и у вас нет информации, необходимой длясделай это.Например, вышеприведенный стек совершенно безопасен, но он определенно не согласован между операциями (например, вы можете поместить и затем вставить в стек и в результате получить None).

Ваш лучший вариант - использоватьнеизменный стек (например, List) и сбросьте , который , в AtomicReference, если вам нужно общее изменяемое состояние.

Answer 2

На мой взгляд, самый простой способ сделать это многозадачно поточнобезопасным будет следующим:

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 если стек уже пуст.

Как примечание, доступ к размеру синхронизирован, но у вас нет возможности гарантировать, что он будет корректным в любой момент после его возврата, поскольку несколько потоков могут получить доступ к стеку, что может изменить его размер. Если вам действительно нужно точно знать размер, вам придется действовать по-другому, синхронизируя весь стек при его использовании.