Back to search

University of Waterloo

Recoverable Mutual Exclusion in Detectable Lock-Based Data Structures

Abstract

dc:description.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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Fahmy, Ahmed
Advisor dc:contributor.advisor
  • Golab, Wojciech

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/21373

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Fahmy, Ahmed. Recoverable Mutual Exclusion in Detectable Lock-Based Data Structures. University of Waterloo, 2025. https://hdl.handle.net/10012/21373