Non-blocking Synchronization

Learn about non-blocking synchronization and thread-safe data structures that can be built using them.

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:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.