Home

Welcome to the libmtds wiki!

Table of content

Getting started:

1. Intro to the lock-free algorithms

Containers:

1. Single-lock queue
2. Two-lock queue
3. M&S queue
4. Treiber stack

Tests:

1. Tests
2. Benchmarks

Extension ideas:

Containers:

• Lock-free ordered-list
• Lock-free skip-list
• Single-lock queue
• Two-lock queue
• M&S queue
• Bounded lock-free queue
• Lock-free priority queue
• Basket lock-free queue
• Treiber stack
• Bounded lock-free stack
• Lock-free hash-map

Memory reclamation:

• Tagged pointers
• Hazard pointers
• Pass the Buck
• Epoch-based

Tests:

• Better tests for the ABA problem

Related sources:

• Lock-free queue and stack presentation

  • Link (available via ucu domain): https://docs.google.com/presentation/d/1fm7U9CsRRkOpguCzBExag8tiIhrLXymqdQDEl7lcF6o/edit?usp=sharing
  • There were 2 presentations. The following link by default displays the final presentation, yet the midterm one can be found in the version history (it is marked there as a MIDTERM_PRESENTATION)

• All used materials and links are attached at the end of each page separately, depending on the topic