M.Sc. Diploma Work

Friday, June 10, 2011 » programming, uni

Final exam, final work and leaving the wall of alma mater. My last big theorem I have choosed, investigated for months and formed a paperwork and program about the theme: lock-free programming. Lockless programming is a way to safely share changing data between multiple threads without the cost of acquiring and releasing locks. This sounds like a silver buller, but lockless programming is complex and subtle, sometimes doesn't give the benefits that it promises. Lock-free data structures guarantee the progress of at least one thread when executing mutlithreaded procedures, thereby helping you avoid deadlock. Lockless programming is a valid technique for multithreaded programming, but it should not be used lightly. Before using it you must understand the complexities, and you should measure carefully to make sure that it is actually giving you the gains that you expect.

Useful literaturs in theme:
Introduction to non-blocking algorithms - Alexandra David
Comparative Performance of Memory Reclamation
Strategies for Lock-free and Concurrently-readable Data Structures - Thomas Edward Hart
The parallelism shift and C++'s memory model - Johan Torp
Concurrent Programming Without Locks - KEIR FRASER, TIM HARRIS
Intermediate/Advanced C++ Programming , A Survey of Concurrent Programming
via Next-Generation C++ Threads - Walter E. Brown, Ph.D.
Lock-Free Programming - Andrei Alexandrescu
Concurrent Data Structures - Mark Moir and Nir Shavit
Understanding and Effectively Preventing the ABA Problem in
Descriptor-based Lock-free Designs - Damian Dechev, Peter Pirkelbauer, Bjarne Stroustrup
Multithreaded C++0x: the Dawn of a new Standard - Michael Wong
C++ Concurrency in Action Practial Multithreading - Anthony Williams
Optimised Lock-Free FIFO Queue - Dominique Fober, Yann Orlarey, Stéphane Letz
Concurrency & Multithreading - Maurice Herlihy & Nir Shavit
The Art of Multiprocessor Programming - Morgan Kaufmann
Concurrent Reading and Writing - Leslie Lamport
Wait-Free Synchronization - MAURICE HERLIHY
DEVELOPMENT ENVIRONMENT, BENCHMARKS, & OPTIMIZATIONS - Ms. Moran Tzafrir
Lock-Free Data Structures - Andrei Alexandrescu
Lock-Free Data Structures with Hazard Pointers - Andrei Alexandrescu, Maged Michael
Lock-free linked lists using compare-and-swap - John D. Valois
Common problems in multi-core programming, Part 3 - Shameem Akhter and Jason Roberts Intel Corp.
A practical nonblocking queue algorithm using compare-and-swap - Chien-Hua Shann, Ting-Lu Huang, Cheng Chen
Intel® C++ Intrinsic Reference
Lock-free Stack and Queue: Java vs .NET - Matko Botin, Davor Runje
Introduction to lock-free/wait-free and the ABA problem - Christian Hergert
Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms - M.M. Michael and M.L. Scott
IEEE Transactions on Parallel and Distributed Systems
Lock-Free Programming - Geoff Langdale
Lock-free Programming - Nathaniel Wesley Filardo
Technical Report Practical lock-freedom - Keir Fraser
An Optimistic Approach to Lock-Free FIFO Queues - Edya Ladan-Mozes and Nir Shavit
DCAS is not a Silver Bullet for Nonblocking Algorithm Design - Victoria University of Wellington, Sun Microsystems Laboratories 1
The Art of Multiprocessor Programming - Maurice Herlihy, Nir Shavit
Comparing the performance of concurrent linked-list implementations in Haskell - Martin Sulzmann, Edmund S. L. Lam, Simon Marlow
A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems - Philippas Tsigas Yi Zhang
Synchronization Algorithms and Concurrent Programming - Gadi Taubenfeld
Spin Locks and Contentions
Concurrent Algorithms and Data Structures for Many-Core Processors - DANIEL CEDERMAN
Párhuzamos programozás…… a gyakorlatban - Tódor Balázs
Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms - Maged M. Michael Michael L. Scott
Correction of a Memory Management Method for Lock-Free Data Structures - M. M. Michael and M. L. Scott.
The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors - T. E. Anderson
Correction of a Memory Management Method for Lock-Free Data Structures - Maged M. Michael Michael L. Scott
???????? Lock-free??
Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms - Maged M. Michael Michael L. Scott
A Pragmatic Implementation of Non-Blocking Linked-Lists - Timothy L. Harris
Practical and Lock-Free Doubly Linked Lists - Hakan Sundell, Philippas Tsigas
LockFree Linked Lists and Skip Lists - Mikhail Fomitchev, Eric Ruppert
MANAGING LONG LINKED LISTS USING LOCK FREE TECHNIQUES - Mohammad Farook and Peter Graham
Lock-Free Linked List Using Compare-and-Swap - John D. Valois
Lock-free Dynamically Resizable Arrays - Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup
ERRATA Lock-Free Linked List Using Compare-and-Swap - John D. Valois
High Performance Dynamic Lock-Free Hash Tables and List-Based Sets - Maged M. Michael
(When) Will CMPs hit the Power Wall? - Cor Meenderinck and Ben Juurlink
Többmagos processzorok programozhatósága - Vágó Gergely
Multi-Core Programming Increasing Performance through Software Multi-threading - Shameem Akhter, Jason Roberts
Párhuzamos programozás Jegyzet
Performance of memory reclamation for lockless synchronization - Thomas E. Harta, Paul E. McKenneyb, Angela Demke Browna, JonathanWalpole
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting - Anders Gidenstam
Maged M. Michael, “Hazard Pointers: Safe Memory Reclamation for Lock Free Objects - Robert T. Bauer
Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects - Maged M. Michael
[pres]Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting - Anders Gidenstam, Marina Papatriantafilou, Hakan Sundell, Philippas Tsigas
[paper]Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting - Anders Gidenstam, Marina Papatriantafilou, Hakan Sundell and Philippas Tsigas
Lock-Free Reference Counting - David L. Detlefs Paul A. Martin Mark Moir Guy L. Steele Jr.
High Performance Dynamic Lock-Free Hash Tables and List-Based Sets Maged M. Michael , IBM Thomas J. Watson Research Center P.O. Box 218 Yorktown Heights NY 10598 USA
Henry Massalin and Carlton Pu. A Lock-Free Multiprocessor OS Kernel. Technical Report No. CUCS-005-91, Columbia University, 1991.
Michael B. Greenwald. Non-Blocking Synchronization and System Design. Ph.D. Thesis, Stanford University Technical Report STAN-CS-TR-99-1624, August 1999
Timothy L. Harris. A Pragmatic Implementation of Non- Blocking Linked Lists. In Proceedings of the 15th International Symposium on Distributed Computing, pages 300–314, October 2001.
Leslie Lamport. Concurrent reading and writing. Communications of the ACM, 20(11):806–811, 1977.
Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124–149, 1991.
Maurice Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems, 15(5):745–770, Novem- ber 1993.
Maged Michael (2004). "Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects". IEEE Transactions on Parallel and Distributed Systems 15 (6): 491–504.
Andrei Alexandrescu and Maged Michael (2004). "Lock-Free Data Structures with Hazard Pointers". Dr Dobbs. (C++ oriented article)
Johan Torp . The parallelism shift and C++'s memory model (September 26, 2008 )
Mark Moir and Nir Shavit. Concurrent Data Structures
. Anthony Williams. C++ Concurrency in Action. Practical Multithreading
Andrei Alexandrescu. Lock-Free Data Structures (December 17, 2007)
Shameem Akhter and Jason Roberts Intel Corp. Common problems in multir-core programming
Matko Botinˇan‡ , Davor Runje§ . Lock-free Stack and Queue: Java vs .NET (2007)
Maurice Herlihy&Nir Shavit. The art of multiprocessor programming (2008)
Vágó Gergely : Többmagos processzorok programozhatósága (2009)
Thomas E. Hart a,*,1 , Paul E. McKenney b , Angela Demke Brown a , Jonathan Walpole . Performance of memory reclamation for lockless synchronization (2007)
Timothy L. Harris.A pragmatic implementation of non-blocking linked-lists
Maged M. Michael Michael L. Scott. Simple, Fast, and Practical Non-Blocking and Blocking
Concurrent Queue Algorithms
David L. Detlefs Paul A. Martin Mark Moir Guy L. Steele Jr. , Lock-Free Reference Counting
Thomas Edward Hart . Comparative Performance of Memory Reclamation Strategies for Lock-free and Concurrently-readable Data Structures

Links:
http://www.rossbencina.com/code/lockfree
http://home.mit.bme.hu/~szell/parhuzamos/Todor_Balazs_Parhuzamos_programozas_a_gyakorlatban.opt.pdf
http://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.codeproject.com/KB/cpp/lockfreeq.aspx
http://h21007.www2.hp.com/portal/download/files/unprot/hpux/comparing_lock_types.pdf
http://www.linuxjournal.com/article/5833?page=0,0
http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/c93.html
http://tothviktor.wordpress.com/2011/02/28/tappool/
http://www.linfo.org/kernel_space.html
http://www.ibiblio.org/pub/Linux/docs/faqs/Threads-FAQ/htmSpace
http://github.com/chergert/dukes_of_hazard
http://git.dronelabs.com/iris
http://publib.boulder.ibm.com/infocenter/iseries/v5r3/index.jsp?topic=/rzahw/rzahwrzahwcascasco.htm
http://www.rossbencina.com/code/lockfree?q=~rossb/code/lockfree/
http://www.codeproject.com/KB/cpp/lockfreeq.aspx
http://www.helenos.org/doc/design/html.chunked/sync.html
http://repnop.org/spinlocks.html
http://tali.admingilde.org/dhwk/vorlesung/ar01s08.html
http://en.wikipedia.org/wiki/Fetch-and-add
http://pine.cs.yale.edu/pinewiki/WaitFreeHierarchy
http://www.antennamagazin.hu/2006-01/11-csiptuning.html
http://www.eetimes.com/electronics-news/4214473/Report--Computing-has-hit--power-wall-
http://en.wikipedia.org/wiki/Multi-core_processor
http://en.wikipedia.org/wiki/Instruction-level_parallelism
http://en.wikipedia.org/wiki/List_of_Intel_microprocessors
http://en.wikipedia.org/wiki/Atomic_%28computer_science%29
http://www.justsoftwaresolutions.co.uk/threading/non_blocking_lock_free_and_wait_free.html
http://en.wikipedia.org/wiki/Non-blocking_algorithm
http://en.wikipedia.org/wiki/Double_compare-and-swap
http://en.wikipedia.org/wiki/Read-copy-update
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2427.html
http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html
http://tothviktor.wordpress.com/2011/02/28/tappool/
http://www.helenos.org/doc/design/html.chunked/sync.html
http://audidude.com/?p=363
http://www.ibm.com/developerworks/java/library/j-jtp11234/
http://julien.benoist.name/lockfree.html
http://www.concurrencykit.org/
http://code.google.com/p/nbds/source/browse/trunk/include/lwt.h?r=25
http://code.google.com/p/concurrent-data-structures-workshop-barriers/source/browse/trunk/CPP/mpp_workshop/cpp_framework.h?r=3

Various implementations:
yamasa-lockfree-62aaec6
inplace-stm v1.00
timharrislist
qprof-0.4
PPP Version
NobleDemo32
lockfree-lib
harris_linkedlist lib
Lawrence Bush's implementation
liblfds
fc_benchmark_15_6_2010
fastflow-1.0.0
cpp_framework_ver3
ck-0.0.2
chergert-dukes_of_hazard-9fea0fd
ch09
cds-0.7.2
cbbs-src-0.2.0

Paperwork and implementation:
[ msc_presentation.pdf ]

Drop a mail to access.
[ diplom.pdf ] [ lock_based_data_structure.zip ]