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?

Your code is definitely not complete (a dead give-away is the fact that it does not compile ;-). Please replace it with uys.be/Multics.scala (I don't have enough points to edit questions yet). — opyate

Walter Chang Walter Chang · Accepted Answer · 2009-08-22T15:52:20

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.

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

2 Answers