Lock-free data structure for multi-core processors
Jonathan R. Engdahl, Dukki Chung · 2010
Real time control applications are very demanding in terms of closed loop system response. The challenge is to execute an operation in a predictable amount of time. As more control functions are needed, faster computing speed is preferred to achieve the desired control responses. The major processor manufacturers have given up trying to make processors run faster, at least for the time being. Instead, manufacturers are turning to multi-core architectures in which multiple processors (cores) communicate directly through shared hardware caches. Multi-core chips make computing more efficient by exploiting parallelism. This new paradigm is widely available and provides a new way of solving control problems. At the same time, the multi-core architecture poses a challenge because modern control systems are asynchronous: activities can be halted or delayed without warning by interrupts, preemption, and other events. In this paper, a lock-free linked-list queue is described and implemented on a multi-core ARM processor. The lock-free algorithm ensures threads that are competing for access to the queue do not have their execution indefinitely postponed by mutual exclusion; also system-wide progress is guaranteed.