Concurrent Algorithm collection
Six years ago, I learned fundamental concurrent algorithms again, to refine my knowledge.
I read this book “The Art of Multiprocessor Programming (M. Herlihy, N. Shavit)” and many papers. Then, I picked fifteen algorithms up and implemented them in C-lang.
The source code of them is uploaded on my GitHub repository. Please check it out and enjoy!
List of implemented algorithms
- “Bringing Practical LockFree Synchronization to 64Bit Applications” by Simon Doherty, Maurice Herlihy, Victor Luchangco, Mark Moir
- “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms” by M. Michael and M. Scott
- Coarse-Grained Synchronization Singly-linked List
- Fine-Grained Synchronization Singly-linked List
- Lazy Synchronization Singly-linked List
- “A Pragmatic Implementation of Non-Blocking Linked-Lists” by Timothy L. Harris
- “Lock-Free Linked Lists and Skip Lists” by Mikhail Fomitchev, Eric Ruppert
- “A Simple Optimistic skip-list Algorithm” by Maurice Herlihy, Yossi Lev, Victor Luchangco, Nir Shavit
- “A Lock-Free concurrent skiplist with wait-free search” by Maurice Herlihy & Nir Shavit
- (Chain) Hash Table
- Open-Addressed Hash Table
- Striped Hash Table
- Refinable Hash Table
- “Cuckoo Hashing” by R.Pagh, F.F.Rodler
- Concurrent Cuckoo Hash Table