X

An Oracle blog about Transactional locks

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

Dave Dice
Senior Research Scientist

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.

Be the first to comment

Comments ( 0 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.