[Kst] How to fix our deadlock issues.

[George Staikos]

How to fix our deadlock issues.

Recent changes to object complexity and performance of locking in Kst have
brought some old deadlock scenarios up in frequency and made Kst appear far
less stable.  Past fixes for these deadlocks were apparently insufficient and
only fixes some cases.  The most common scenario is this:

Thread 1 locks Object A
Object A starts to lock dependencies
Context switch
Thread 2 locks Object B
Object B starts to lock dependencies and eventually blocks on Object A
Context switch
Object A continues to lock dependencies and blocks on an object locked by B
-> deadlock

The general solution for this is to lock all objects in a consistent order,
such as pointer value of object or lock.  We do this presently, but only at
each level, which is insufficient in complex object structures.  One possible
solution is for KstDataObject to first obtain all pointers requiring locks,
recursively, and then sort and lock them iteratively.  The problem is that in
order to obtain these pointers, we will need to have locks on the objects, 
thus defeating the goal.  It is proposed to split locking into shallow and 
deep locking, allowing a shallow lock for tree reading, and a deep lock for 
more complex operations.


-- 
George Staikos
KDE Developer				http://www.kde.org/
Staikos Computing Services Inc.		http://www.staikos.net/