这段代码中是否存在潜在的饥饿，还是仅仅是我？

问题描述：

我正在尝试学习Scala，并发现它迄今为止已经是一门很棒的语言。我从David Pollak学习"Beginning Scala"。在第3章中有一段代码，它演示了如何编写没有同步块的多线程代码（该代码是从本书复制的，可以从Apress site下载，我不打算在这里打破任何规律）：这段代码中是否存在潜在的饥饿，还是仅仅是我？

 
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）。我是否对，如果是这样，那么如何改进这个代码来解决这个问题呢？

你的代码肯定是不完整的（一个无用的东西就是它不能编译的事实;-)。请用http://uys.be/Multics.scala替换它（我没有足够的点来编辑问题）。 – opyate 2009-12-05 23:51:06

答

首先，我认为你从本书例子中粘贴的代码的大部分缺失;这让你很难理解你的问题。其次，确实可以递归地调用doSet（）多次，但是在这种情况下不会发生StackOverflowException，因为一次保存宽限期：尾递归。 doSet（）在函数的末尾被递归地调用（在递归调用之后不再进行处理），并且不能被重写（在对象内定义），其限定它优化成循环而没有任何堆栈开销。

在2.8.0中，有一个名为@ scala.annotation.tailrec的注释，它在def上使用时将确保def内的递归调用确实是尾递归。

整个代码被粘贴，你只需要滚动它。 – 2009-08-22 18:18:41

如果我正确理解你的答案，饥饿在这里是可能的（尽管极不可能），它会导致无限循环，即使通过StackOverflowException也不会停止？ – 2009-08-22 18:26:16

我在说的是doSet（）可能会被递归调用多次，但由于不涉及堆栈帧的消耗，所以没有堆栈溢出的危险。至于线程匮乏，它实际上取决于你对饥饿的定义。有了今天的硬件，我无法真正看到2000年以来的任何线程开始挨饿超过几秒钟。 – 2009-08-23 06:18:32

答

它看起来像使用比较和交换（http://en.wikipedia.org/wiki/Compare-and-swap）而不是锁定。

这种方法的一般想法是，你循环，直到你设置的值始终如一。

我不知道如何解决饥饿问题。我的猜测是理论上存在饥饿问题，但在实践中它会没事的。

这段代码中是否存在潜在的饥饿，还是仅仅是我？

相关推荐