Decentralized Utilization Control in Distributed Real-Time Systems

Many real-time systems must control their CPU utiliza-tions in order to meet end-to-end deadlines and prevent over-load. Utilization control is particularly challenging in dis-tributed real-time systems with highly unpredictable work-loads and a large number of end-to-end tasks and processors. This paper presents the Decentralized End-to-end Utilization CONtrol (DEUCON) algorithm that can dynamically enforce desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier work, DEUCON features a novel decentralized control struc-ture that only requires localized coordination among neigh-bor processors. DEUCON is systematically designed based on recent advances in distributed model predictive control theory. Both control-theoretic analysis and simulations show that DEUCON can provide robust utilization guarantees and maintain global system stability despite severe variations in task execution times. Furthermore, DEUCON can effectively distribute the computation and communication cost to dif-ferent processors and tolerate considerable communication delay between local controllers. Our results indicate that DEUCON can provide scalable and robust utilization con-trol for large-scale distributed real-time systems executing in unpredictable environments