A correct program must both preserve consistency and be free of deadlocks. In the thread paradigm, for a complex program composed from separately written modules, if there are enough locks (synchronized methods or whatever) sprinkled around to have a high confidence in the program's safety, there should usually be low confidence in the program's liveness (the upper left corner). If locks are only inserted where their deadlock dangers have been carefully examined, a program that one can afford to write will have too few locks to be confident in its safety. By contrast, you can easily write event-loop programs in which you have high confidence in its safety and its liveness.
Other Liveness Issues
Besides deadlock, there are other kinds of bugs which can prevent a program from making progress. While E doesn't have classic deadlock, it still has these vulnerabilities, some of which resemble deadlock.
Livelock -- infinite loops steal the vat's thread
An infinite loop prevents this incarnation of a vat from ever again making progress, just as it would prevent a conventional thread from making progress. As with conventional threads, it does not prevent other vats (threads) from making progress. Unfortunately, since each E object is in only one vat, livelocking a vat does lock up all objects within a vat. (This would be analogous to livelocking a thread that holds a synchronized lock on several objects.)
Fortunately, for a persistent vat, this locks up only the vat incarnation, not the vat itself. By killing the livelocked incarnation, the vat can roll back to its last checkpoint, be reincarnated, and proceed from there. Unfortunately, this doesn't guarantee that it won't livelock again.
Turing's halting problem demonstrates the ultimate unsolvability of this problem.
Datalock -- recursive data definition with no bottom
This also includes when-catches that are "waiting" (posted as callbacks for) promises that the other would resolve.
Gridlock -- messages need space to move
Technically, this looks like a classic deadlock, but it's caused specifically by lack of outgoing buffers. The distinction between deadlock and gridlock? If more buffer space would have caused you not to have locked up yet, then it's gridlock rather than deadlock.
Lost Signal -- overslept, forgot to set the alarm
An example, due to Mark Seaborn (thanks!): If you have a when-catch "waiting" (posted as a callback) for a promise to be resolved, but in the code that's supposed to resolve it, you forget to call "resolve" in all applicable cases. Of course, actual lost signal bugs may be arbitrarily more complicated than this.
Posting Permissions
Reply With Quote