Reliable And Efficient Concurrent Synchronization For Embedded ...
Reliable and Efficient Concurrent Synchronization for Embedded Real-Time Software
Damian Dechev
Bjarne Stroustrup
Texas A&M University
Texas A&M University
Email: dechev@tamu.edu
Email: bs@cs.tamu.edu
Abstract—The high degree of autonomy and increased com-
3) Predictive Log Synchronization (PLS) [7]
plexity of future robotic spacecraft pose significant challenges in
We demonstrate how each nonblocking technique can be utilized to implement
assuring their reliability and efficiency. To achieve fast and safe
a concurrent shared vector. We analyze each approach according to our frame-
concurrent interactions in mission critical code, we survey the
work of seven evaluation criteria: 1. preservation of program semantics and
practical state-of-the-art nonblocking programming techniques.
space and time complexities, 2. nonblocking guarantees (wait-free vs. lock-
We study in detail three nonblocking approaches: (1) CAS-
free vs. obstruction-free) [3], 3. correctness model (linearizability, Lamport’s
consistency, others) [3], 4. portability (assumptions and reliance on atomic
based algorithms, (2) Software Transactional Memory, and (3)
primitives and hardware instructions), 5. simplicity and ease of use, 6. high
Predictive Log Synchronization. We identify a framework of
degree of parallelism and fast performance, 7. thread-safety (any hazards or
seven critical evaluation criteria and analyze the strengths and
race conditions that each particular approach might need to address). We
weaknesses of each approach. Our study investigates how the
investigate how the application of each synchronization technique can help
application of nonblocking synchronization can help eliminate
eliminate the problems of deadlock, livelock, and priority inversion. Our
the problems of deadlock, livelock, and priority inversion and at
experimental evaluation compares the performance of the three nonblocking
the same time deliver a performance improvement in embedded
approaches and provides an estimate of the possible performance gains of
real-time software.
each in contrast to the application of some of the most optimal blocking
techniques.
I. INTRODUCTION
III. IMPACT FOR SPACE SYSTEMS
Future space exploration projects, such as Mars Science Laboratory (MSL),
A study on the challenges for the development and certification of modern
demand the engineering of some of the most complex embedded software
spacecraft software by Lowry [5] reveals that in July 1997 The Mars
systems. The notion of concurrency is of critical importance for the design and
Pathfinder mission experienced a number of anomalous system resets that
implementation of such systems. The software development and certification
caused an operational delay and loss of scientific data. The follow-up analysis
methodologies applied at NASA [6] do not reach the level of detail of
identified the presence of a priority inversion problem caused by the low-
providing guidelines for the engineering of reliable concurrent software. In
priority meteorological process blocking the the high-priority bus management
this work, we present a detailed survey of the state-of-the-art nonblocking
process. Providing reliable and efficient concurrent synchronization is of
programming techniques that can help in implementing efficient and safe
significant importance for the design and validation of complex autonomous
concurrent interactions in mission critical embedded code.
future robotic spacecraft.
A. Parallelism and Complexity
IV. CONCLUSION
The most common technique for controlling the interactions of concurrent
In this study we investigate how the application of nonblocking syn-
processes is the use of mutual exclusion locks. The application of mutually
exclusive locks poses significant safety hazards and incurs high complexity in
chronization can help eliminate the problems of deadlock, livelock, and
the testing and validation of mission-critical software. Even for efficient and
priority inversion in embedded real-time mission critical software. We apply a
highly optimized locks, the interdependence of processes implied by the use
comparison framework consisting of seven evaluation criteria to analyze three
of locks introduces the dangers of deadlock, livelock, and priority inversion.
The incorrect application of locks is hard to determine with the traditional
known approaches for nonblocking synchronization and explain in detail their
testing procedures and a program can be deployed and used for a long period
strengths and weaknesses. We measure the performance of each nonblocking
of time before the flaws can become evident and eventually cause anomalous
approach and indicate the possible performance gains in contrast to the appli-
behavior.
cation of some of the most optimal blocking techniques. Understanding the
B. Nonblocking Synchronization
advantages (over mutual exclusion) as well as the usability and performance
To achieve higher safety and gain performance, we suggest the application
trade-offs of the modern nonblocking programming techniques is of critical
of nonblocking synchronization. A concurrent object is nonblocking if it
guarantees that some process in the system will make progress in a finite
importance for engineering reliable and efficient concurrent flight software.
amount of steps [3]. Nonblocking algorithms do not apply mutually exclusive
REFERENCES
locks and most commonly rely on a set of atomic primitives supported by
the hardware architecture. The most ubiquitous and versatile data structure
[1] D. Dechev, P. Pirkelbauer, and B. Stroustrup. Lock-Free Dynamically
in the ISO C++ Standard Template Library is vector, offering a combination
Resizable Arrays. In OPODIS 2006.
of dynamic memory management and constant-time random access. Because
[2] D. Dice and N. Shavit. Understanding tradeoffs in software transactional
of the vector’s wide use and challenging parallel implementation of its
memory. In CGO, 2007.
nonblocking dynamic operations, we illustrate the efficiency of each approach
[3] M. Herlihy. The art of multiprocessor programming. In PODC ’06, pages
with respect to its applicability for the design and implementation of a
1–2, New York, NY, USA, 2006. ACM.
shared nonblocking vector. A number of pivotal concurrent applications
[4] M. Ingham, R. Rasmussen, M. Bennett, and A. Moncada. Engineering
in the Mission Data System [4] framework employ a shared STL vector
Complex Embedded Systems with State Analysis and the Mission Data
(in all scenarios protected by mutually exclusive locks). Such is the Data
System. In AIAA, 2004.
Management Service library described by Wagner in [8].
[5] M. R. Lowry. Software Construction and Analysis Tools for Future Space
Missions. In TACAS, 2002.
II. ANALYSIS AND RESULTS
[6] RTCA. Software Considerations in Airborne Systems and Equipment
We survey the practical state-of-the-art nonblocking programming tech-
Certification (DO-178B), 1992.
niques. We study in detail three approaches:
[7] O. Shalev and N. Shavit. Predictive log synchronization. In EuroSys 06.
1) CAS-based algorithms design [1]
[8] D. Wagner.
Data Management in the Mission Data System.
In
2) Software Transactional Memory (STM) [2]
Proceedings of the IEEE System, Man, and Cybernetics Conference, 2005.
