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.
International Journal of Software Engineering, Technology and Applications, 2015 Vol.1 No.1, pp.2 - 52
Available online: 16 Feb 2015 *Full-text access for editors Access for subscribers Free access Comment on this article