[E-Lang] Deadlock versus Datalock

[Karp, Alan]

Mark Miller wrote:
> 
> So, because of non-determinism, computation can in general diverge.  
> However, for computation that doesn't diverge, the occurrence 
> of datalock 
> bugs are in fact deterministic.  Yes, this last statement is 
> technically 
> tautological, but 
> 

When he worked at HP Labs, Milon Mackey wrote an "instant replay" package
for message passing systems, PVM in particular.  The idea was to capture
enough information about message arrivals to construct a "happens before"
relation.  His mechansims was cheap enough, 2-10% overhead, to leave on all
the time, so we were able to rerun cases and identify the cause of
non-deterministic bugs.

We also considered using this approach for shared memory systems, but we'd
have to call it "run the play again" instead of "instant replay" becasue
capturing the order of memory references is impossible.  The idea was to
capture the sequence of synchonizations and construct a "happens before"
relation.  We couldn't control what happened between synch points, but we
could at least control the order of the synchronizations.

I wonder if such a tool could be used to debug data locks in
non-deterministic programs.

_________________________
Alan Karp
Principal Scientist
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-3
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278
https://ecardfile.com/id/Alan_Karp
http://www.hpl.hp.com/personal/Alan_Karp/