REAL-TIME COMPUTING WITH LOCK-FREE SHARED OBJECTS

This article considers the use of lock-free shared objects within hard real-time systems. As the name suggests, loch-free shared objects are distinguished by the fact that they are accessed without locking. As such, they do not give rise to priority inversions, a key advantage ov er conventional, lock-based object-sharing approaches. Despite this ad vantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operati ons to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The m ain contribution of this article is to show that such interferences ca n be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. I n the first part of the article, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on th ese conditions, it is formally shown that lock-free shared objects oft en incur less overhead than object implementations based on wait-free algorithms or lock-based schemes. In the last part of the article, thi s conclusion is validated experimentally through work involving a real -time desktop videoconferencing system.