A methodology for creating fast wait-free data structures

ABSTRACT

Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. While many practical lock-free algorithms exist, wait-free algorithms are typically inefficient and hardly used in practice. In this paper, we propose a methodology called fast-path-slow-path for creating efficient wait-free algorithms. The idea is to execute the efficient lock-free version most of the time and revert to the wait-free version only when things go wrong. The generality and effectiveness of this methodology is demonstrated by two examples. In this paper, we apply this idea to a recent construction of a wait-free queue, bringing the wait-free implementation to perform in practice as efficient as the lock-free implementation. In another work, the fast-path-slow-path methodology has been used for (dramatically) improving the performance of a wait-free linked-list.

References

1. Y. Afek and M. Merritt. Fast, wait-free (2k-1)-renaming. In ACM Symp. on Principles of Distr. Comp. (PODC), pages 105--112, 1999.
2. J. H. Anderson and Y.-J. Kim. A new fast-path mechanism for mutual exclusion. Distrib. Comput., 14:17--29, 2001.
3. P. Chuong, F. Ellen, and V. Ramachandran. A universal construction for wait-free transaction friendly data structures. In Proc. ACM Symposium on Parallel Algorithms (SPAA), pages 335--344, 2010.
4. F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking binary search trees. In Proc. ACM PODC, pages 131--140, 2010.
5. P. Fatourou and N. D. Kallimanis. A highly-efficient wait-free universal construction. In Proc. ACM Symposium on Parallel Algorithms (SPAA), pages 325--334, 2011.
6. F. E. Fich, V. Luchangco, M. Moir, and N. Shavit. Obstruction-free algorithms can be practically wait-free. In Proc. Int. Conference on Distributed Computing (DISC), pages 78--92, 2005.
7. T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proc. Int. Conference on Distributed Computing (DISC), pages 300--314, 2001.
8. D. Hendler, I. Incze, N. Shavit, and M. Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In Proc. ACM Symposium on Parallel Algorithms (SPAA), pages 355--364, 2010.
9. D. Hendler, N. Shavit, and L. Yerushalmi. A scalable lock-free stack algorithm. J. Parallel Distrib. Comput., 70(1):1--12, 2010.
10. M. Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, 1991.
11. M. Herlihy. A methodology for implementing highly concurrent objects. ACM Trans. Program. Lang. Syst., 15(5):745--770, 1993.
12. M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Proc. Conf. on Distributed Computing Systems (ICDCS), pages 522--529, 2003.
13. M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
14. M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990.
15. A. Kogan and E. Petrank. Wait-free queues with multiple enqueuers and dequeuers. In Proc. ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), pages 223--234, 2011.
16. E. Ladan-Mozes and N. Shavit. An optimistic approach to lock-free fifo queues. Distributed Computing, 20(5):323--341, 2008.
17. L. Lamport. A fast mutual exclusion algorithm. ACM Trans. Comput. Syst., 5:1--11, 1987.
18. Y. Levanoni and E. Petrank. An on-the-fly reference-counting garbage collector for java. ACM TOPLAS, 28(1):1--69, 2006.
19. M. M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst., 15(6):491--504, 2004.
20. M. M. Michael and M. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proc. ACM Symp. on Principles of Distr. Comp. (PODC), pages 267--275, 1996.
21. M. Moir. Transparent support for wait-free transactions. In Proc. Conf. on Distributed Computing (DISC), 1998.
22. M. Moir, D. Nussbaum, O. Shalev, and N. Shavit. Using elimination to implement scalable and lock-free FIFO queues. In Proc. ACM SPAA, pages 253--262, 2005.
23. S. Timnat, A. Braginsky, A. Kogan, and E. Petrank. Poster paper: Wait-free linked-lists. To appear in Proc. ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), 2012.
24. K. R. Treiber. Systems programming: Coping with parallelism. Technical report RJ-5118, IBM Almaden Research Center, 1986.
25. P. Tsigas and Y. Zhang. A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. In Proc. ACM SPAA, pages 134--143, 2001.
26. J.-H. Yang and J. H. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9:1--9, 1994.
27. P.-C. Yew, N.-F. Tzeng, and D. H. Lawrie. Distributing hot-spot addressing in large-scale multiprocessors. IEEE Trans. Comput., 36:388--395, 1987.

Index Terms

• Information systems

  • Information storage systems

    • Record storage systems

      • Record storage alternatives

        • Linked lists

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Concurrent programming structures