Vol. 11 No. 5 – May 2013

Download full issue PDF

Structured Deferral: Synchronization via Procrastination

We simply do not have a synchronization mechanism that can enforce mutual exclusion.

Developers often take a proactive approach to software design, especially those from cultures valuing industriousness over procrastination. Lazy approaches, however, have proven their value, with examples including reference counting, garbage collection, and lazy evaluation. This structured deferral takes the form of synchronization via procrastination, specifically reference counting, hazard pointers, and RCU (read-copy-update).

by Paul E. McKenney

Proving the Correctness of Nonblocking Data Structures

So you've decided to use a nonblocking data structure, and now you need to be certain of its correctness. How can this be achieved? When a multithreaded program is too slow because of a frequently acquired mutex, the programmer's typical reaction is to question whether this mutual exclusion is indeed required. This doubt becomes even more pronounced if the mutex protects accesses to only a single variable performed using a single instruction at every site. Removing synchronization improves performance, but can it be done without impairing program correctness?

Nonblocking synchronization can yield astonishing results in terms of scalability and realtime response, but at the expense of verification state space.

by Mathieu Desnoyers

Nonblocking Algorithms and Scalable Multicore Programming

Exploring some alternatives to lock-based synchronization

Real-world systems with complicated quality-of-service guarantees may require a delicate balance between throughput and latency to meet operating requirements in a cost-efficient manner. The increasing availability and decreasing cost of commodity multicore and many-core systems make concurrency and parallelism increasingly necessary for meeting demanding performance requirements. Unfortunately, the design and implementation of correct, efficient, and scalable concurrent software is often a daunting task.

by Samy Al Bahra