KDevelop and multi-threaded programming

As part of the definition-use chain work that I have been doing for KDevelop, yesterday I wrote a browser for each document's chain. There was just one catch... none of the chain is protected for multithreaded access at the moment.

I'm pretty new to multithreaded programming, so I started with reading the Qt docs. Well, as those of you who have read it know, it is intended for programmers with a familiarity with the issues presented. Nevertheless, it did a fair job of explaining to me the issues.

This got me to where KDevelop is now - that is, it runs, shuts down, and can have its parse jobs interrupted without crashing. However, when I came to the definition-use chain, I knew it would take more than just what I could do with fine-grained mutexes to this point.

The difficulty with designing locking for this group of explicitly shared objects is that at first glance they can cross reference each other wherever they like, thanks to the #include directive. So, I was about to start on fine-grained locking inside each class across all classes. However, it just didn't feel right.

So, the reason I'm blogging now is because I've hopefully found a solution to this problem. In fact, when you look closer at the design of the chain, only certain objects create cross references - top level contexts, definitions which are separate to their declarations, and uses of definitions. Even better, the builders only need to acquire one of each type of lock at any one time, so hopefully this will avoid deadlocks too.

Thus, I'm planning to lock each of these three categories with separate per-object read/write locks. This even has the benefit that the second pass of the chain builder (the use pass) only has to write lock the use locks, and read lock the top context. Wish me luck...

PS: I was saddened to hear of the passing of Steve Irwin today, although he was a little overly Australian, he was unashamedly so...


Please excuse me if you already know this, but just in the case that you don't:

The golden rule to avoid deadlocks (as it is well known to kernel developers :) ), is that if you want to hold multiple locks, they should always be locked in the same order. Thus you have to define a partial ordering in the set of all the locks, where two locks must be comparable if they will ever happen to be locked together (of course a total ordering for all the locks will do, but it is not required).
Then just always lock all the locks in order of "importance".
Suppose that you have to lock A, B and C, and that we decided that in our ordering A>B>C. Thus, if B and C are already locked you have to do:
Instead, if A and B are already locked you can just do:

This will prevent the infamus thing of thread 1 locking A and trying to lock B, while thread 2 locked B and is trying to lock A (generalized with many lock and threads).

By Maurizio Monge at Mon, 09/04/2006 - 16:25

Thanks for that. It certainly makes sense... I think I'll grab one of the references that Qt links to, because it's tips like these that I'll need to master.

By Hamish at Tue, 09/05/2006 - 12:13