Utility-based resource overbooking for Cyber-Physical Systems

The tight coupling among computation, sensing and control found in Cyber-Physical Systems (CPS) often requires information processing to be completed within strict timing deadlines. Traditional hard real-time scheduling algorithms require the use of the worst-case execution times to guarantee that deadlines will be met. Unfortunately, many algorithms with parameters derived from sensing the physical world suffer from large variations in execution time, which leads to pessimistic overall utilization. For example, object tracking in a computer vision system is highly dependent on the number and size of the objects within the camera's field of view. In this paper, we present the formal description of ZS-QRAM [8], a scheduling approach that allows system designers to flexibly assign execution times and application-derived utility to tasks in order to maximize total system utility even in the presence of highly variable processing estimates. In particular, we provide a detailed description of the algorithm, the formal proofs for its temporal protection and a detail evaluation. Our evaluation uses the Utility Degradation Resilience (UDR) metric presented in [8]. Our results show that ZS-QRAM is able to obtain four times as much UDR as ZSRM, a previous overbooking approach, and almost twice as much UDR as Rate-Monotonic with Period Transformation (RM/TP) even when the latter does not provide temporal protection.