Is there potential starvation in this code or is it just me?

Question

I am trying to learn Scala and find it a great language so far. I learn from "Beginning Scala" by David Pollak. In chapter 3 there is this piece of code, which illustrates how to write multi-threaded code without synchronized blocks (this code is copied from the book, it's available for download from Apress site, I don't mean to break any laws here):

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

From what I understand, there is potential starvation problem in function doSet (unlucky thread might always clash and cause StackOverflowException). Am I right and if so, how can this code be improved to fix this issue?

Answer 1

It looks like its using Compare and Swap (http://en.wikipedia.org/wiki/Compare-and-swap) instead of locking.

The general idea with this approach is that you loop until you manage to set the value consistently.

I don't know enough about this to answer if there is a starvation problem. My guess is that in theory there is a starvation problem, but in practice it will be fine.

Answer 2

First of all, I think a big chuck of the code you pasted from the book example is missing; it makes it quite difficult to understand your question.

Secondly, it is true that doSet() can potentially be called many times recursively but a StackOverflowException will not occur in this case because of one saving grace: tail recursion. doSet() is called recursively at the end of of the function (no more processing is done after the recursive call) and can not be overridden (defined inside an object) which qualify it to be optimized into a loop without any stack overhead.

In 2.8.0, there is an annotation called @scala.annotation.tailrec which, when used on a def, will ensure that the recursive call inside the def is indeed tail recursive.