Proper synchronization is a necessity for writing multi-threaded programs. Many people think “proper synchronization” means locking, but that’s not quite true. As I and others have pointed out many times, it’s often better to solve synchronization problems in other ways, such as by using algorithms and protocols that reduce the need for locking. However, in the real world programmers are often faced with the problem of adding synchronization to a program that currently lacks it, most often because the program wasn’t originally designed with concurrency in mind. In these cases, changing algorithms or protocols would often be far too invasive, so adding locks around important data structures really is the way to go. Here are some tips for how to do it safely.
The first thing you should do is decide what to lock, and the Golden Rule is: lock data, not code. Far too many times, I’ve seen a single lock associated with some set of functions, serializing all calls to those functions even when operating on separate data structures of the same type. This creates false contention and hurts performance. It also forces all access to those data structures to be done through those functions, which we all know is a good programming model (whether you call it OOP or information hiding), but not all legacy code is written that way. Refactoring everything to work that way is invasive in exactly the way we’re trying to avoid. Since it’s practically always access to the data that really needs to be serialized, the locks should be associated with the data. This is where Java’s locking model goes awry, by the way. Locks are associated with objects, which is great, but the synchronized keyword applies to methods instead of to data members. That can lead to a whole class of annoying bugs when data members are accessed from unsynchronized methods, and don’t tell me it never happens.
The second step is to add the locks. This part is fairly straightforward. Just identify the code that accesses a particular data structure, and put locks around it. Obviously you have to make sure all code paths after the lock is taken have to be accounted for, decide whether to use spinlocks or blocking locks, whether to use mutex locks or reader/writer locks, etc. That’s all Concurrent Programming 101, though, and nothing I need to cover. The only error most people make is to stop at this point and not complete the process described below.
Your third step is to check and make sure you haven’t added a self-deadlock. Self-deadlock occurs when function X takes a lock, then calls (perhaps indirectly) another function Y that tries to take the same lock. This is fairly easy to avoid in new code, but it can be hard to tell whether you’ve added a self-deadlock to unfamiliar code written by someone else. In order to get through this step you’ll need a good cross-reference generator, because you’ll be walking call trees a lot. I’ve had good luck both with Red Hat’s Source Navigator and with Anjuta, but there are many such tools and everyone tends to develop their own preferences. What you want to do is identify all of the functions that take a lock. Then, for each one, identify all of its callers, and their callers, and so on. If you hit another function that takes the same lock before you hit an entry point (main, thread main, callback, API function) you have a potential self-deadlock on your hands. Note that you could do the same thing going downward (to called functions instead of calling) but call trees tend to fan out rather than in so this way tends to involve less work. If you find a self-deadlock, you’ll need to resolve it. Usually only some minor refactoring is involved, such as turning a sequence like “X calls Y, which calls Z” into something like “X calls Y, then Z.” Sometimes you’ll have to resort to using recursive/reentrant locks instead of simple locks. In a few cases life will simply be more difficult, in ways that are hard to characterize or explain how to handle. Now you’re stuck with some more complex refactoring, but at least you know you have a problem and can solve it while coding instead of in testing or in the field.
The last step is the one about which I have the least to say. Self-deadlock is not the only kind of deadlock, obviously; it’s just the kind you’re most likely to introduce with such late-stage modifications to legacy code. The most likely kind of deadlock you’re going to introduce is a lock inversion, where thread/task/activity 1 takes locks X and then Y, while thread 2 takes Y and then X. To determine whether you’ve added an inversion, you have to check the usage of the locks you’ve added against the usage of every other lock already in the system. You can do this using a technique similar to that described above for self-deadlock, but now you have to search both up and down from every newly-locked function once for each existing lock. That can be very painful. Sometimes you just have to suck it up and do this kind of grunt-work – it’s still better to find a bug early than to find it late – but for a non-trivial program you might want to consider investing in a static code checker capable of detecting deadlock automatically. Coverity’s Prevent can do a limited amount of this, and their Extend lets you do a much more thorough job if you invest the time, but they’re very expensive. Unfortunately, none of the free or low-cost alternatives that I’ve seen (and I’ve done detailed evaluations for many) are worth a damn for this particular task, no matter what some of them might claim. It’s actually something I’d like to work on myself, using some of the infrastructure I developed for my stack ripper, if I ever have sufficient spare time to spend on such things.
Couple of things … 1st, fantastic blog. In the world of blogging, this is one of the few ‘whitepapers’ on the topic of scalability that is generally spot on.
2nd, I wanted to just comment on the statement about re: Java & method synchronization. The synchronized keyword does not have to apply to methods, it can be used inline to guard data as you suggest in the article. Moreover, in Java 5.0 and beyond you have a choice with using the newly introduced concurrent locking constructs or the synchronized keyword. In my limited experience of building scalable servers with Java, something I know you have characterized as ‘unfortunate’
, having flexible locking constructs is almost always a better choice. Most web traffic I deal with require ‘read’ access 90% of the time, and so it’s worth my while to have read / write locking structures in place. I haven’t yet achieved a level of performance that would be much better off with the other locking constucts you suggest. (ie my performance targets haven’t required me to stretch that much)
Java also provides a similar tool for lock analysis, jlint, which does the self deadlock code analysis for you. It’s solved two of the nastier deadlock issues I’ve run across in the last few years.
John.
It’s true that you can use synchronized at a sub-function level, and that’s a bit of improvement, but it still has the problems of limiting flexibility and forcing paradigms that I mentioned. Just think how much nicer it would be if you could apply synchronized to a data member instead and have The Right Things happen. I don’t know anything about Java 5.0 so I’ll just plead ignorance.
Jlint was one of the tools I looked at a while back, and I had a different experience. It completely failed to find any of several known deadlocks that I threw at it. In general, many code-analysis tools seem to fall apart when confronted with a program that has a lot of entry points called in unpredictable orders. Then again, looking at the documentation now, there seem to be signs that Jlint has improved a lot in this area, so maybe it’s time to check it out. It should be fun to run it on some of my less favorite programmers’ code.
By the way, I forgot to mention something else about Java. The reason I described its choice for SEDA as unfortunate is because I do a lot of work in the filesystems and elsewhere in the kernel/embedded space where Java (or any interpreted/JIT language) is not a realistic option. If what you’re writing is an end-user or vertical application that will never find its way into the kernel or a device such as a disk array or router, there’s nothing wrong with using Java. It’s a fine language, even if it’s often misused. Any framework that does not accommodate such needs, though, cannot IMO be considered truly general and thus the choice of a language which precludes such deployment was unfortunate.
I know the pain of searching for deadlocks, especially in a large code base. I got so fed up with doing it manually, and couldn’t find any tools to help me so I wrote a tool that can locate potential deadlocks in Windows programs by analysing the lock acquisition ordering as the code runs. It works pretty well, and, integrated with my server testing, allows me to be sure that I haven’t introduced a lock inversion during maintenance.
I may just not understand what you mean by the term ‘data’. To be specific, you can synchronize in Java on anything that is an Object. When you synchronize at the method level you implicitly synchronize on an instance of that object. This does have the limitation, and maybe this is what you meant, that you have to model your data in the object domain before you can declare a lock on it. In my experience this has been limiting when you are working on sets of data, however I have not run across that problem that often.
The other comment … I believe I fall squarely in your ‘unfortunate’ category … right in the middle. I am writing VoIP routing applications in Java, and we debate the Java choice on a weekly basis. Thus far we have almost always exceeded (and this release doubled) the capacity numbers set out as a requirement in the project specification. That will end shortly as our marketing guys catch on, but thus far capacity hasn’t been the defining limitation of our program, thus far it’s been not having enough features built into the project. We turn out features quickly, it’s just the market is very fast, and we believe Java helps us keep up.
In general though, I believe almost everything you have stated here applies to any languages, and I have found it very helpful in considering our general performance strategies. You can write slow code in any language, the trick is writing fast code in the one you are working in.