Есть ли потенциальный голод в этом коде или это только у меня?

Question

Я пытаюсь выучить Scala и до сих пор считаю его отличным языком. Я учусь у "Начинающая Скала" Дэвида Поллака. В главе 3 есть этот фрагмент кода, который иллюстрирует, как писать многопоточный код без синхронизированных блоков (этот код скопирован из книги, он доступен для скачивания с сайта Apress , я не имею в виду нарушать какие-либо законы здесь):

import java.util.concurrent.atomic.{AtomicReference => AtomR, AtomicLong}
import java.util.Random
import scala.collection.immutable.TreeHashMap

object Multics {
  type MT = Map[String, Int]

  val info: AtomR[MT] = new AtomR(TreeHashMap.empty)
  val clashCnt = new AtomicLong

  def main(argv: Array[String]) {
     runThread {
      repeatEvery(1000) {
        println("Clash Count: "+clashCnt+" Total: "+
                info.get.foldLeft(0)(_ + _._2))
      } }

    for (i  old + (name -> 0)}
      repeatEvery(ran.nextInt(100)) {
        doSet(info){old => old + (name -> (old(name) + 1))}
        cnt = cnt + 1
        if (cnt != info.get()(name))
          throw new Exception("Thread: "+name+" failed")
      } }
  }

  def runThread(f: => Unit) =
  (new Thread(new Runnable {def run(): Unit = f})).start

  def doSet[T](atom: AtomR[T])(update: T => T) {
    val old = atom.get
    if (atom.compareAndSet(old, update(old))) ()
    else {
      clashCnt.incrementAndGet
      doSet(atom)(update)
    }
  }

  def repeatEvery(len: => Int)(body: => Unit): Unit = {
    try {
      while(true) {

        Thread.sleep(len)
        body
      }
    } catch {
      case e => e.printStackTrace; System.exit(1)
    }
  }
} 

Насколько я понимаю, в функции doSet есть потенциальная проблема с голоданием (неудачный поток всегда может конфликтовать и вызывать StackOverflowException). Прав ли я, и если да, то как можно улучшить этот код, чтобы решить эту проблему?

Answer 1

Прежде всего, я думаю, что большой кусок кода, который вы вставили из примера книги, отсутствует; это затрудняет понимание вашего вопроса.

Во-вторых, верно, что doSet () потенциально может вызываться многократно рекурсивно, но в этом случае исключение StackOverflowException не возникнет из-за одной сохраняющей благодати: хвостовой рекурсии. doSet () вызывается рекурсивно в конце функции (после рекурсивного вызова больше не выполняется обработка) и не может быть переопределено (определено внутри объекта), что делает его оптимизированным для цикла без каких-либо дополнительных затрат стека.

В 2.8.0 есть аннотация @ scala.annotation.tailrec, которая при использовании в def гарантирует, что рекурсивный вызов внутри def действительно хвостовой рекурсивен.

Answer 2

Похоже, что он использует сравнение и обмен (http://en.wikipedia.org/wiki/Compare-and-swap) вместо блокировки.

Общая идея этого подхода заключается в том, что вы зацикливаетесь, пока вам не удастся последовательно установить значение.

Я не знаю достаточно об этом, чтобы ответить, если есть проблема с голодом. Я предполагаю, что в теории есть проблема с голодом, но на практике все будет хорошо.