Global Sources
EE Times-India
EE Times-India > EDA/IP

Common problems in multi-core programming, Part 3: Nonblocking algorithms, ping-ponging, memory reclamation

Posted: 04 Mar 2009     Print Version  Bookmark and Share

Keywords:non-blocking algorithms  memory reclamation  live locks 

Part 1 of this series discusses threads, data races, deadlocks and live locks. Part 2 focuses on heavily contended locks. This third instalment tackles non-blocking algorithms, ping-ponging and memory reclamation.

One way to solve the problems introduced by locks is to not use locks. Algorithms designed to do this are called non-blocking. The defining characteristic of a non-blocking algorithm is that stopping a thread does not prevent the rest of the system from making progress. There are different non-blocking guarantees:
1) Obstruction freedom—A thread makes progress as long as there is no contention, but live lock is possible. Exponential backoff can be used to work around live lock.
2) Lock freedom—The system as a whole makes progress.
3) Wait freedom—Every thread makes progress, even when faced with contention. Few non-blocking algorithms achieve this.

Non-blocking algorithms are immune from lock contention, priority inversion, and convoying. Non-blocking algorithms have a lot of advantages, but with these come a new set of problems that need to be understood. Non-blocking algorithms are based on atomic operations. A few non-blocking algorithms are simple. Most are complex, because the algorithms must handle all possible interleaving of instruction streams from contending processors.

View the PDF document for more information.

Comment on "Common problems in multi-core progra..."
*  You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.


Go to top             Connect on Facebook      Follow us on Twitter      Follow us on Orkut

Back to Top