Lock-Free Synchronization for Dynamic Embedded Real-Time Systems

Abstract

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger "adversary" than most traditional arrival models. We derive an upper bound on lock-free retries under the UAM with utility accrual scheduling-the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities' accrued timeliness utility is greater under lock-free than lock-based, and the consequent lower and upper bound on the total accrued utility that is possible with lock-free and lock-based sharing. We confirm our analytical results with a POSIX RTOS implementation.