Non-blocking Synchronization

Introduction

Much of the performance improvements seen in classes such as Semaphore and ConcurrentLinkedQueue versus their synchronized equivalents come from the use of atomic variables and non-blocking synchronization. Non-blocking algorithms use machine-level atomic instructions such as compare-and-swap instead of locks to provide data integrity when multiple threads access shared resources. Non-blocking algorithms are harder to design and implement but out perform lock-based alternatives in terms of liveness and scalability. As the name suggests, non-blocking algorithms don’t block when multiple threads contend for the same data, and as a consequence greatly reduce scheduling overhead. These algorithms don’t suffer from deadlocks, liveness issues and individual thread failures. More formally:

• An algorithm is called non-blocking if the failure or suspension of a thread doesn’t cause the failure or suspension of another thread.

• An algorithm is called lock free if at every step of the algorithm some thread participant of the algorithm can make progress.

Nonblocking counter

Designing a thread-safe counter would require using locks so that threads don’t step over each other. An increment operation on a long variable consists of three steps. Fetching the current value, incrementing it and then writing it back. All three have to be executed atomically to achieve thread-safety. A lock-based implementation of the lock appears below: