Recoverable Mutual Exclusion in Detectable Lock-Based Data Structures

Abstract

Persistent memory (PM) is an emerging technology that offers the speed of DRAM combined with the persistence of traditional storage. This advancement provides unique opportunities and challenges for designing data structures that remain consistent and recoverable after system failures. This thesis presents significant advancements in the design and implementation of recoverable synchronization algorithms and data structures optimized for PM. The research focuses on addressing the challenges of recoverable mutual exclusion (RME) and the development of detectable lock-based data structures, offering innovative solutions that enhance performance and reliability in concurrent systems. A major contribution of this work is the introduction of the Recoverable Filter (RF) lock, a novel approach that enhances RME lock performance in the Non-Uniform Memory Access (NUMA) multi-processor architecture, where memory access time depends on the memory location relative to the processor. Such a technique transforms NUMA-oblivious RME locks into NUMA-aware ones without requiring modifications to the underlying locks. This solution tackles the dual challenges of recoverability and NUMA-awareness, a combination not previously addressed in the literature on RME locks. Comprehensive empirical evaluations using prominent RME algorithms, specifically GH and JJJ, demonstrate that the RF lock significantly boosts performance by up to 45% in multi-socket configurations, while maintaining minimal overhead in single-socket setups. These findings underscore the effectiveness of the RF lock in leveraging memory locality to improve efficiency. Additionally, this thesis introduces DULL, a Detectable Unrolled Lock-based Linked List, designed for persistent memory environments. DULL distinguishes itself as the fastest detectable lock-based linked list and the first to achieve strict-linearizability. The implementation of DULL utilizes volatile RME locks to address the intricate challenge of preserving essential lock properties, such as mutual exclusion and deadlock-freedom, across system failures. Performance evaluations reveal that DULL outperforms existing solutions in update-intensive scenarios and maintains scalability even under high processor subscription levels. By exploring the challenges of designing concurrent recoverable algorithms with incorporated locks, this thesis makes substantial contributions to the field of concurrent data structures and synchronization algorithms. The innovative solutions presented herein lay a robust foundation for future research and practical applications, enhancing the reliability and performance of concurrent systems in persistent memory environments.