Scalable nonblocking concurrent objects for mission critical code

ABSTRACT

The high degree of complexity and autonomy of future robotic space missions, such as Mars Science Laboratory (MSL), poses serious challenges in assuring their reliability and efficiency. Providing fast and safe concurrent synchronization is of critical importance to such autonomous embedded software systems. The application of nonblocking synchronization is known to help eliminate the hazards of deadlock, livelock, and priority inversion. The nonblocking programming techniques are notoriously difficult to implement and offer a variety of semantic guarantees and usability and performance trade-offs. The present software development and certification methodologies applied at NASA do not reach the level of detail of providing guidelines for the design of concurrent software. The complex task of engineering reliable and efficient concurrent synchronization is left to the programmer's ingenuity. A number of Software Transactional Memory (STM) approaches gained wide popularity because of their easy to apply interfaces, but currently fail to offer scalable nonblocking transactions. In this work we provide an in-depth analysis of the nonblocking synchronization semantics and their applicability in mission critical code. We describe a generic implementation of a methodology for scalable implementation of concurrent objects. Our performance evaluation demonstrates that our approach is practical and outperforms the application of nonblocking transactions by a large factor. In addition, we apply our Descriptor-based approach to provide a solution to the fundamental ABA problem. Our ABA prevention scheme, called the lambda-delta approach, outperforms by a large factor the use of garbage collection for the safe management of each shared location. It offers speeds comparable to the application of the architecture-specific CAS2 instruction used for version counting. The lambda-delta approach is an ABA prevention technique based on classification of concurrent operations and 3-step execution of a Descriptor object. A practical alternative to the application of CAS2 is particularly important for the engineering of embedded systems.

REFERENCES

• 1: Barett, A., Knight, R., Morris, J. and Rasmussen, R.,Mission Planning and Execution Within the Mission Data System,Proceedings of the International Workshop on Planning and Scheduling for Space, 2004.
• 2: Becker, P.,Working Draft, Standard for Programming Language C, ISO WG21 N2009,http://www.open-std.org/JTC1/SC22/WG21/, April, 2006.
• 3: Boehm, H. and Adve, S.,Foundations of the C Concurrency Memory Model,PLDI '08: Proceedings of the ACM SIGPLAN 2008 conference on Programming language design and implementation, ACM Press, 2008.
• 4: Dechev, D., Pirkelbauer, P. and Stroustrup, B.,Lock-Free Dynamically Resizable Arrays,Proceedings of 10th International Conference on Principles of Distributed Systems, OPODIS 2006,Bordeaux, France, December 12--15, 2006, Lecture Notes in Computer Science, Springer, Volume 4305, pages 142--156.
• 5: Dechev, D., Rouquette, N., Pirkelbauer, P. and Stroustrup, B.,Verification and Semantic Parallelization of Goal-Driven Autonomous Software,Proceedings of ACM Autonomics 2008: 2nd International Conference on Autonomic Computing and Communication Systems, 2008.
• 6: Detlefs, D., Flood, C., Garthwaite, A., Martin, P., Shavit, N. and Steele Jr., G.,Even Better DCAS-Based Concurrent Deques, International Symposium on Distributed Computing, DISC 2000.
• 7: Dice, D. and Shavit, N., Understanding Tradeoffs in Software Transactional Memory, Proceedings of the 2007 International Symposium on Code Generation and Optimization (CGO), San Jose, CA, 2007.
• 8: Dvorak, D., Rasmussen, R. and Starbird, T.,State Knowledge Representation in the Mission Data System, Proceedings of IEEE Aerospace Conference, 2002.
• 9: Dvorak, D., Ingham, M., Morris, J., and Gersh, J.,Goal-Based Operations: An Overview, Proceedings of AIAA Infotech, 2007.
• 10: Dvorak, D. and Reinholtz, K.Hard real-time: C versus RTSJ,OOPSLA '04: Companion to the 19th annual ACM SIGPLAN conference on Object--oriented programming systems, languages, and applications, 2004.
• 11: Fraser, K.,Practical lock-freedom, Technical Report UCAM-CL-TR-579, University of Cambridge, Computer Laboratory, 2004, ISSN 1476--2986.
• 12: Fraser, K. and Harris, T.,Concurrent programming without locks,ACM Trans. Comput. Syst., Volume 25, Number 2, 2007, ISSN 0734--2071.
• 13: Gifford, D. and Spector, A.,Case study: IBM's system/360-370 architecture,Commun. ACM, Volume 30, Number 4, 1987, ISSN 0001-0782, pages 291--307.
• 14: Harris, T., Fraser, K. and Pratt, I.,A practical multi-word compare-and-swap operation,Proceedings of the 16th International Symposium on Distributed Computing, 2002.
• 15: Hendler, D., Shavit, N. and Yerushalmi, L.,A scalable lock-free stack algorithm,SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, Barcelona, Spain.
• 16: Herlihy, M. and Shavit, N.,The Art of Multiprocessor Programming, Morgan Kaufmann, March, 2008, ISBN 0123705916.
• 17: Herlihy, M., Luchangco, V. and Moir, M.,The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures,DISC '02: Proceedings of the 16th International Conference on Distributed Computing, 2002.
• 18: Herlihy, M., Luchangco, V. and Moir, M.,Obstruction-Free Synchronization: Double-Ended Queues as an Example,ICDCS '03: Proceedings of the 23rd International Conference on Distributed Computing Systems,IEEE Computer Society, 2003, Washington, DC, USA.
• 19: Herlihy, M., Luchangco, V., Martin, P. and Moir, M.,Nonblocking memory management support for dynamic-sized data structures,ACM Trans. Comput. Syst., Volume 23, Number 2, 2005, ISSN 0734-2071, pages 146--196.
• 20: Ingham, M., Rasmussen, R., Bennett, M. and Moncada, A.,Engineering Complex Embedded Systems with State Analysis and the Mission Data System,Proceedings of First AIAA Intelligent Systems Technical Conference, 2004.
• 21: Intel, IA-32 Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide,http://www.intel.com/cd/software/products/asmo-na/eng/272688.htm, 2004.
• 22: ISO/IEC 14882 International Standard, American National Standards Institute,Programming languages, C, September, 1998.
• 23: Lamport, L.,How to make a multiprocessor computer that correctly executes programs,IEEE Trans. Comput., September, 1979.
• 24: Lowry, M., Software Construction and Analysis Tools for Future Space Missions,International Conference on Tools and Algorithms for Construction and Analysis of Systems 2002, Lecture Notes in Computer Science, Springer, Volume 2280, pages 1--19.
• 25: Maged M.,Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects,IEEE Trans. Parallel Distrib. Syst., Volume 15, Number 6, 2004, ISSN 1045-9219, pages 491--504.
• 26: Spear, M., Shriraman, A., Dalessandro, L., Dwarkadas, S. and Scott, M.,Nonblocking transactions without indirection using Alert-On-Update, http://www.cs.rochester.edu/research/synchronization/rstm/v4api.shtml,Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures SPAA 2007, San Diego, California, USA.
• 27: Stroustrup, B.,The C Programming Language,Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2000, ISBN 0201700735.
• 28: Volpe, R. and Peters S., Rover Technology Development and Mission Infusion for the 2009 Mars Science Laboratory Mission,7th International Symposium on Artificial Intelligence, Robotics, and Automation in Space,Nara, Japan, May, 2003.
• 29: Wagner, D.,Data Management in the Mission Data System,Proceedings of the IEEE System, Man, and Cybernetics Conf., 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Languages, Reliability

Keywords:
ABA problem prevention, C++, autonomous space software, nonblocking synchronization, software transactional memory