Title: Design and application of distributed containers in a CPS software control library

Authors: Damian Dechev; Pierre LaBorde

Addresses: University of Central Florida, 4000 Central Florida Blvd., Orlando, FL 32816, USA ' University of Central Florida, 4000 Central Florida Blvd., Orlando, FL 32816, USA

Abstract: Non-blocking synchronisation is known to alleviate the hazards of deadlock, livelock, and priority inversion. We present the design and portable implementation of a lock-free dynamically resizable array. Our lock-free implementation of a shared vector outperforms its lock-based STL counterpart and the implementation provided by Intel by a factor of 10 or more. The ABA problem is fundamental to all CAS-based designs. We offer a solution, called the λδ approach that is practical and efficient and offers speeds comparable to the direct application of the architecture-specific CAS2 instruction used for version counting. Our lock-free vector demonstrated high scalability when compared to the application of non-blocking transactions. We demonstrate the use of our non-blocking synchronisation methodology and our shared vector for the engineering of a framework for verification and semantics parallelisation of the mission data system's (MDS) goal networks which provide for testing and development of autonomous real-time flight applications.

Keywords: lock-free resizable arrays; non-blocking synchronisation; shared vector; concurrency; data structures; parallel programming; embedded computing; distributed containers; CPS software control library; lock-free vector; mission data systems; autonomous flight; real-time flight; semantics; robotic space missions; scalable lightweight concurrent objects; concurrent interactions; mission critical code.

DOI: 10.1504/IJSETA.2015.067524

International Journal of Software Engineering, Technology and Applications, 2015 Vol.1 No.1, pp.2 - 52

Received: 30 Aug 2013
Accepted: 13 Nov 2013
Published online: 18 Mar 2015 *