<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T17:36:48Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/21183" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/21183</identifier><datestamp>2025-03-26T23:32:29Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Brown, Trevor</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Buhr, Peter</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author">Singh, Ajay</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2024-11-14T15:12:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2024-11-14T15:12:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2024-11-14</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2024-11-11</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/10012/21183</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">This dissertation presents three paradigms to address the challenge of concurrent memory reclamation, manifesting as use-after-free errors that arise in concurrent data structures using non-blocking techniques. Each paradigm aligns with one of our three objectives for practical and safe memory reclamation algorithms.

Objective 1: Design memory reclamation algorithms that are fast, have a bounded memory footprint, and are easy to use — requiring neither intrusive changes to data structures nor specific architecture or compiler support. These algorithms should also deliver consistent performance across various workloads and be applicable to a wide range of data structures. To achieve this, we introduce the neutralization paradigm with the NBR (Neutralization-Based Reclamation) algorithm and its enhanced version, NBR+ (Optimized Neutralization-Based Reclamation). These algorithms use POSIX signals and a lightweight handshaking mechanism to facilitate safe memory reclamation among threads. By relying solely on atomic reads and writes, they achieve bounded garbage and high performance with minimal overhead compared to existing algorithms. They are straightforward to implement, similar in reasoning and programming effort to two-phased locking, and compatible with numerous data structures.

Objective 2: Eliminate the asymmetric synchronization overhead in existing reclamation algorithms, which often incur costly memory fences while eagerly publishing reservations, as seen in algorithms like hazard pointers and hazard eras. We propose the reactive synchronization paradigm, implemented through deferred memory reclamation and POSIX signals. This mechanism enables threads to privately track memory references (or reservations) and share this information on demand, using the publish-on-ping algorithm. This approach serves as a drop-in replacement for hazard pointers and hazard eras and includes a variant (EpochPOP) that combines epochs with the robustness of hazard pointers to approach the performance of epoch-based reclamation.

Objective 3: Completely eliminate the batching common in current reclamation algorithms to allow immediate memory reclamation, similar to sequential data structures, while maintaining high performance. 
We introduce Conditional Access, a hardware-software co-design paradigm implemented in a graphite multi-core simulator. This paradigm leverages cache coherence to enable efficient detection of potential use-after-free errors without explicit shared-memory communication or additional coherence traffic. Conditional Access provides programmers with hardware instructions for immediate memory reclamation with minimal overhead in optimistic data structures.

To validate our claims, we designed and conducted extensive benchmark tests to evaluate all proposed algorithms on high-end machines under various scenarios. We paired these algorithms with several real-world concurrent data structures, representing various memory access patterns, and compared their time and space efficiency against numerous state-of-the-art memory reclamation algorithms, demonstrating significant improvements.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="uri">https://gitlab.com/aajayssingh/nbr_setbench_plus</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="uri">https://gitlab.com/aajayssingh/conditional-access</dim:field>
   <dim:field mdschema="dc" element="subject">concurrent memory reclamation</dim:field>
   <dim:field mdschema="dc" element="subject">safe memory reclamation</dim:field>
   <dim:field mdschema="dc" element="subject">garbage collection</dim:field>
   <dim:field mdschema="dc" element="subject">concurrent algorithms</dim:field>
   <dim:field mdschema="dc" element="subject">concurrency control</dim:field>
   <dim:field mdschema="dc" element="subject">hardware-software codesign</dim:field>
   <dim:field mdschema="dc" element="subject">multicore programming</dim:field>
   <dim:field mdschema="dc" element="subject">concurrent computing</dim:field>
   <dim:field mdschema="dc" element="title">Safe Memory Reclamation Techniques</dim:field>
   <dim:field mdschema="dc" element="type">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms">0</dim:field>
   <dim:field mdschema="uws" element="comment" qualifier="hidden">May I please request to speedup the processing as fast as possible. This will helpo me to quickly obtain the completion certificate to present to my employer. Thank you so much for your understanding.</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Brown, Trevor</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Buhr, Peter</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>