Preempt Less, Schedule Better: Revisiting PCG for Real-Time Uniform Processors

We address the problem of scheduling periodic implicit-deadline real-time tasks on $m$ uniform processors. We introduce PCG$^*$, an optimal TL-plane algorithm based on PCG~\cite{chen2008}, which guarantees at most $2(m - 1)$ preemptions per TL-plane, matching the best-known theoretical bound for uniform platforms. The proposed algorithm advances the state of the art by offering an optimal real-time scheduling solution with a tight preemption bound within TL-planes. The numerical experiments presented in this work provide strong evidence that PCG$^*$ yields a substantial reduction in the number of preemptions relative to PCG. When applied to identical processor platforms, PCG$^*$ is also a best-possible polynomial time algorithm in terms of preemptions in a TL-plane, matching the $(m-1)$ preemption bound achieved by LRE-TL \cite{funk2010}.