David Dice's Weblog

Musing about Lock-free and wait-free algorithms for real-time environments

Intuitively, programmers tend to think that lock-free algorithms are a good match for real-time environments. On a multiprocessor system, however, a low-priority thread might repeatedly perform a short lock-free update that causes a higher priority thread trying a longer update to fail and retry repeatedly. In theory this could lead to indefinite postponement and lack of progress for the higher priority thread. (Because the operation attempted by the higher priority thread is longer, it's also more vulnerable to interference). Wait-free algorithms provide a solution, of course. Wait-freedom guarantees that each individual thread will make progress after a fixed amount of (virtual) processing time. Unfortunately we don't know of as many wait-free algorithms as we do lock-free. But if you care about real-time, RTJ (real-time Java) provides locks with all the semantics you'd want.

The same argument, by the way, will apply to many hardware and software transactional memory implementations. A lower priority thread may be able to cause a transaction in a higher priority thread to repeatedly abort.

Posted at 06:11PM Sep 01, 2006 by David Dice in General  |  Comments[0]