A case for an interleaving constrained shared-memory multi-processor

ABSTRACT

Shared-memory multi-threaded programming is inherently more difficult than single-threaded programming. The main source of complexity is that, the threads of an application can interleave in so many different ways. To ensure correctness, a programmer has to test all possible thread interleavings, which, however, is impractical.

Many rare thread interleavings remain untested in production systems, and they are the root cause for a majority of concurrency bugs. We propose a shared-memory multi-processor design that avoids untested interleavings to improve the correctness of a multi-threaded program. Since untested interleavings tend to occur infrequently at runtime, the performance cost of avoiding them is not high.

We propose to encode the set of tested correct interleavings in a program's binary executable using Predecessor Set (PSet) constraints. These constraints are efficiently enforced at runtime using processor support, which ensures that the runtime follows a tested interleaving. We analyze several bugs in open source applications such as MySQL, Apache, Mozilla, etc., and show that, by enforcing PSet constraints, we can avoid not only data races and atomicity violations, but also other forms of concurrency bugs.

REFERENCES

• 1: The open source database benchmark. http://osdb.sourceforge.net/.
• 2: Christian Bienia , Sanjeev Kumar , Jaswinder Pal Singh , Kai Li, The PARSEC benchmark suite: characterization and architectural implications, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454128]
• 3: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 4: Joseph Devietti , Brandon Lucia , Luis Ceze , Mark Oskin, DMP: deterministic shared memory multiprocessing, Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, March 07-11, 2009, Washington, DC, USA
• 5: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.256-267, January 14-16, 2004, Venice, Italy
• 6: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 7: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 8: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 9: Shan Lu , Soyeon Park , Chongfeng Hu , Xiao Ma , Weihang Jiang , Zhenmin Li , Raluca A. Popa , Yuanyuan Zhou, MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 10: Shan Lu , Soyeon Park , Eunsoo Seo , Yuanyuan Zhou, Learning from mistakes: a comprehensive study on real world concurrency bug characteristics, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 11: Shan Lu , Joseph Tucek , Feng Qin , Yuanyuan Zhou, AVIO: detecting atomicity violations via access interleaving invariants, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 12: Brandon Lucia , Joseph Devietti , Karin Strauss , Luis Ceze, Atom-Aid: Detecting and Surviving Atomicity Violations, Proceedings of the 35th International Symposium on Computer Architecture, p.277-288, June 21-25, 2008
• 13: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 14: Satish Narayanasamy , Zhenghao Wang , Jordan Tigani , Andrew Edwards , Brad Calder, Automatically classifying benign and harmful data racesallusing replay analysis, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 15: Robert H. B. Netzer, Optimal tracing and replay for debugging shared-memory parallel programs, Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, p.1-11, May 17-18, 1993, San Diego, California, United States
• 16: Marek Olszewski , Jason Ansel , Saman Amarasinghe, Kendo: efficient deterministic multithreading in software, Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, March 07-11, 2009, Washington, DC, USA
• 17: Milos Prvulovic , Josep Torrellas, ReEnact: using thread-level speculation mechanisms to debug data races in multithreaded codes, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 18: Milos Prvulovic , Zheng Zhang , Josep Torrellas, ReVive: cost-effective architectural support for rollback recovery in shared-memory multiprocessors, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 19: Shaz Qadeer, Taming Concurrency: A Program Verification Perspective, Proceedings of the 19th international conference on Concurrency Theory, August 19-22, 2008, Toronto, Canada [doi>10.1007/978-3-540-85361-9_4]
• 20: Feng Qin , Joseph Tucek , Jagadeesan Sundaresan , Yuanyuan Zhou, Rx: treating bugs as allergies---a safe method to survive software failures, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 21: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 22: Daniel J. Sorin , Milo M. K. Martin , Mark D. Hill , David A. Wood, SafetyNet: improving the availability of shared memory multiprocessors with global checkpoint/recovery, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 23: Y. Wang, T. Kelly, M. Kudlur, S. Lafortune, and S. A. Mahlke. Gadara: Dynamic deadlock avoidance for multithreaded programs. In OSDI '08: Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, December 2008.
• 24: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 25: Min Xu , Rastislav Bodík , Mark D. Hill, A serializability violation detector for shared-memory server programs, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery

General Terms:
Design, Reliability, Verification

Keywords:
concurrency bugs, multiprocessors, parallel programming, software reliability