Javalobby - Comments for "ReentrantLock and the Dining Philosophers"

The point of this post is

puredanger — Wed, 13 Feb 2008 11:41:48 -0500

The point of this post is really about how ReentrantLock gives you options that don't exist with synchronized blocks and methods. It's not an argument for or against the use of locks for protecting access to shared data.

In general, having one entity tell others what to do sounds to me like a prescription for low concurrency because all of the entities then have to coordinate at the central point. But it's hard to even talk about this without talking about real examples.

I don't know about you, but I lock my house, my car, etc every day. :) Lock-based access to shared state is *one* style of concurrent programming and happens to be the most prevalent in Java (for better or worse and mean argue for worse). Message-passing/actor-based or lock-free styles also exist and they all have their pros and cons.

I've written about ConcurrentSkipListMap in the past, which is an incredibly cool high-concurrency sorted map in Java 6 written with lock-free code. Lock-free data structures and algorithms rock. They're also incredibly tricky to get right (if you actually read the code for something like ConcurrentSkipListMap/Set or LinkedBlockingQueue). ReentrantLock itself is implemented with lock-free code actually.

I think the Dining

gschwarz — Wed, 13 Feb 2008 10:39:49 -0500

I think the Dining Philosophers is not such a great example of multithreading, because you can solve it simply by using one of the philosophers as an orchestrator directing other philosophers to eat.

This is how we solve this situations in real life anyway, using an arbitrator when people can't agree on their own.

If you can't show a problem in real life that uses locks, why do you think locks are such a great idea? I don't see deadlocks in real life, why should computer programs have it? Are we using the wrong abstractions?

A much better idea, IMHO, is to remove the use of locks by using lock free data structures and algorithms.

See: http://www.ibm.com/developerworks/java/library/j-jtp11234/

Yep, this is an excellent

puredanger — Tue, 12 Feb 2008 15:29:57 -0500

Yep, this is an excellent point. tryLock() and any retry strategy can avoid deadlock but does not alleviate the potential for livelock where all threads are constantly retrying and never succeeding. In that case, you don't deadlock, but make no further progress.

I believe TCP uses an exponential backoff for stuff like this (although I haven't studied this in 10 years). A fascinating topic in itself, but outside the scope of this article... :)

Be wary of tryLock() usage.

abies — Tue, 12 Feb 2008 14:51:33 -0500

Be wary of tryLock() usage. You may end up in livelock if you use it in trivial way. Imagine two threads and two resources A and B. Thread 1 locks A and then B, thread 2 locks B and then A (clear possibility of deadlock). If you implement trivial idea of tryLock(), thread 1 will lock A and then tryLock B, releasing A if it fails. Unfortunately, at the very same time, thread 2 might have a lock on B, tryLocking A. Both will release their base locks and try entire operation again, possibly failing in same way over and over.

One possibility of avoiding is to wait random amount of time between retries - at least statistically it reduces the chances of livelock (ethernet is solving collisions this way).

If somebody wants small puzzle to think about here it is:

You have two classes, A and B. Each of them has a field pointing to other class (0..1-to-0..1 relationship), it's own lock and a bit of extra state. You have two different paths in code which have to update states of both objects in transaction (so they require locking both of them), but they have the pointer to instance of A, or instance of B (they have to retrieve the pointer to second object in pair from field of first one). And now complicated part - as part of this operation, relationship can change (so a1<->b1 and null<->b2 will become a1<->b2 and null<->b1).