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

Modern real-time systems are increasingly deployed at the core of safety-critical and performance-critical applications, from automotive and aerospace control to industrial automation and robotics. Guaranteeing that these systems always react within specified deadlines, while at the same time making effective use of the available processing capacity, requires the use of carefully designed scheduling algorithms supported by rigorous schedulability analysis. Such analysis techniques aim to characterize the worst-case timing behaviour of real-time tasks under a given scheduling policy, and thereby provide a proof that all timing constraints will be met during operation.

Multiprocessor platforms have become pervasive in real-time systems as modern workloads (e.g., automotive, avionics, robotics, multimedia) exceed the capabilities of single-core processors and power/thermal limits hinder further frequency scaling. Consequently, gaining performance now relies on parallelism, which real-time scheduling and analysis must explicitly account for to preserve timing guarantees. Moreover, heterogeneous architectures motivate the uniform-speed multiprocessor model, which captures different effective core capacities in practical settings such as mixed-speed integration, reduced availability due to interference or background services, incremental platform upgrades [2], DVFS/DVS operating modes with speed–energy trade-offs [24, 19], and modern processors combining distinct core “types”, reinforcing the need for schedulability methods that handle speed asymmetries [21, 1].

Among the large variety of real-time scheduling policies that have been proposed in the literature, particular attention has been devoted to optimal algorithms, which are capable of scheduling any task set that is feasible on a given platform. All currently known optimal polynomial-time algorithms assume that task migrations and preemptions are performed at no cost and incur no delay. The reason is that, once preemptions and migrations are explicitly modelled as incurring non-zero delays, the problem complexity changes dramatically: the resulting real-time scheduling problems become computationally hard, even on single-core platforms. For example, the uniprocessor real-time scheduling problem with explicit Cache-Related Preemption Delays (CRPD) has been shown to be strongly $𝒩𝒫$-hard, and no online optimal algorithm exists [18]. This observation highlights why the zero-overhead assumption is adopted when designing optimal multiprocessor schedulers. It is not merely a technical convenience, but a fundamental requirement for obtaining optimal algorithms with tractable schedulability tests. Understanding the capabilities and limitations of optimal algorithms under this zero-overhead assumption is therefore a fundamental step both towards clarifying the core combinatorial difficulties of real-time scheduling and towards bridging the gap between theoretical optimality results and the behaviour of real systems, ultimately enabling the design of scheduling algorithms and analysis techniques that incorporate realistic operational constraints.

For multiprocessor systems, numerous optimal scheduling algorithms have been proposed [6]. Most of these algorithms target platforms with identical processors and task sets composed of periodic tasks with implicit deadlines (i.e., each task must complete before its next release). It is known that only global dynamic-priority scheduling algorithms (i.e., a job priority may change during its execution) can achieve optimality in this setting, in the sense that they can fully utilize all processors. In contrast, fixed-priority scheduling policies and partitioned scheduling strategies have worst-case utilization bounds asymptotically limited to 50%.

Notably, optimal algorithms based on DP-fair [15] principles (i.e., Deadline Partitioning fair scheduling) like those based on the TL-plane abstraction [5, 4, 10, 9] (i.e., a TL-plane defines a plane with Time and Local remaining execution times of jobs) decompose the periodic task scheduling problem into independent time intervals, each bounded by successive task releases/deadlines. Each interval then constitutes an independent subproblem, consisting of a set of local jobs derived from the original periodic tasks. The objective within each subproblem is to ensure that all local jobs complete before the next task deadline, which is common to all local jobs.

In this paper, we focus on uniform multiprocessor systems, in which each processor may operate at a different speed. Several optimal scheduling algorithms have been proposed in this context, each capable of meeting all task deadlines for any feasible task set. More precisely, we refine the PCG (Precaution Cut Greedy) online algorithm [4] so that it achieves the best-known lower bound on the number of preemptions within a TL-plane. In this paper, we introduce ${\text{PCG}}^{\ast }$, an optimal TL-plane algorithm that guarantees at most $2(m-1)$ preemptions per TL-plane, matching the best-known theoretical bound for uniform platforms [12]. To the best of our knowledge, this is the first real-time scheduling algorithm that guarantees this preemption bound. Furthermore, when restricted to identical processors, ${\text{PCG}}^{\ast }$ achieves the best possible preemption bound of $m-1$ [17], thereby matching the preemption bound of the LRE-TL algorithm [9], which is designed for identical multiprocessors. The proposed algorithm advances the state of the art by minimizing preemptions.

We consider a set $\tau =\{{\tau }_1,\mathrm{\dots },{\tau }_n\}$ of independent sequential periodic real-time tasks to be scheduled on a multiprocessor platform. Each task ${\tau }_j=(C_j,T_j)$, for $1\le j\le n$, is characterized by its worst-case execution time $C_j\in {ℝ}^{+}$ on a unit-speed processor and its period $T_j\in \mathbb{N}$, i.e., the interval between two consecutive job releases of ${\tau }_j$. Each job of ${\tau }_j$ must complete execution before the release of its next job, implying an implicit deadline. The utilization factor of task ${\tau }_j$ is defined as $u_j=\frac{C_j}{T_j}$, representing the fraction of processing capacity, on a unit-speed processor, required by ${\tau }_j$ over time. Tasks are synchronously released at time 0.

An event-driven scheduler makes run-time decisions only when specific events occur: job releases, completions, or deadlines. Each such scheduling event defines a scheduling point at which the scheduler may select the jobs to execute.

A task set is said to be feasible if there exists a schedule in which every job completes execution by its deadline. A scheduler is an algorithm that assigns tasks to processors for execution. A scheduling algorithm is deemed optimal if it can successfully schedule every feasible task set.

Our main objective was to define an optimal polynomial-time scheduling algorithm with a guaranteed bound on the number of preemptions, which can only be achieved if preemption overheads are not taken into account in the task model. Accordingly, we propose a scheduling algorithm that does not consider such overheads.

In such scheduling algorithms, a job can be in one of three states: running if it is currently executing on a processor, ready if it is eligible to execute but not assigned to any processor, or completed. During execution, a job may be preempted on its current processor and later resumed – possibly on a different processor, without incurring any overhead, since otherwise no polynomial-time optimal scheduling algorithm can exist. Consequently, preemptions and migrations are not distinguished and are collectively referred to as preemptions throughout this paper, following the terminology used in job scheduling in operational research. This unified terminology enables a direct comparison of scheduling algorithms from both communities with respect to their preemption behaviour.

A processor ${\pi }_i$, $1\le i\le m$, is characterized by its speed $s_i\in {ℝ}^{+}$, representing the amount of processing capacity provided per unit of time. If a task executes for $d$ time units on processor ${\pi }_i$, it completes $d\times s_i$ units of execution. This model is referred to as a uniform multiprocessor platform. When all processor speeds are identical, the platform is called an identical multiprocessor platform, in which case we assume $s_i=1$ for all $i$. We consider a continuous-time model.

In the remainder of this paper, we focus on DP-fair schedules based on the TL-plane abstraction [5]. As shown previously, both the feasibility analysis and the scheduling algorithms are concerned with a single interval delimited by two successive releases/deadlines. We formally proved in [11] that a deterministic DP-fair scheduler generates exactly the same schedule pattern in every interval. Accordingly, the periodic task model is fully represented by a set of local jobs, one for each original periodic task, together with their associated local execution times. For the sake of simplicity, we hereafter refer to them simply as jobs and execution times since we focus on a single TL-plane.

In the TL-plane abstraction, the progress of any job within an interval – bounded by two successive releases/deadlines – can be represented in a two-dimensional plane, referred to as the TL-plane. In this representation, the horizontal axis ($T$) denotes time, while the vertical axis ($L$) denotes the remaining execution time. As established earlier, the initial execution time of the (local) job is equal to the TL-plane length multiplied by the job’s task utilization.

The first TL-plane–based algorithm, LLREF [5], is optimal for identical processor platforms. It follows the Longest Remaining Processing Time (LRPT) principle: at each scheduling point, the $m$ jobs with the longest remaining local execution times are assigned to the $m$ processors until the next scheduling event occurs. These events define scheduling points at which tasks are rescheduled according to LRPT. LRE-TL [9] improves upon LLREF by applying LRPT only at the initialization of each TL-plane, rather than at every scheduling point. Precisely, two types of scheduling events are defined. These types of events are independent and may occur simultaneously²²2LRE-TL also considers $A$-events to handle releases of sporadic tasks. These events are not considered in this paper, since we only focus on periodic tasks.:

• $\mathrm{■}$

  Bottom event ($B$-event): occurs when a task completes, i.e., its local execution time reaches 0.

• $\mathrm{■}$

  Critical event ($C$-event): occurs when a task reaches zero laxity on a processor, i.e., the remaining execution time equals the remaining processor capacity available in the TL-plane.

These ideas were extended to uniform processor platforms in [4]. Before presenting that algorithm, called PCG, we first refine the definition of a $C$-event.

To avoid multiple preemptions, when a job triggers a $C_k$-event, PCG assigns the job to processor ${\pi }_k$ for the remainder of the schedule. From that point on, it is never preempted. From an implementation perspective, the job and its assigned processor are removed from the corresponding lists of jobs and processors. The scheduling problem is thus decomposed into a simpler subproblem for completing the schedule. PCG operates as follows [4]:

• $\mathrm{■}$

  Initialization: Jobs are sorted in non-increasing order of their execution times, and processors are sorted in non-increasing order of their speeds.

• $\mathrm{■}$

  Main loop:

  • –

    At any time $t\ge 0$, upon each $C_k$-event, the corresponding job is permanently assigned to ${\pi }_k$ for the remainder of the TL-plane. Both the job and the processor are then removed from the scheduling problem.

  • –

    At each $B$-event, the corresponding job is removed from the problem.

  • –

    The remaining jobs are assigned to processors according to the LRPT-FM rule, until the next event occurs.

Jobs and processors are sorted in non-increasing order of execution times and processor speeds, respectively. Let $P_k={\sum }_{j=1}^k{p}_j$ for $1\le k\le m-1$, $P_n={\sum }_{j=1}^n{p}_j$, and $S_k={\sum }_{i=1}^k{s}_i$ for $1\le k\le m$. Horváth’s makespan formula can then be expressed as [13]:

As an illustrative example, we consider the set of local jobs defined in Table 1. Horváth’s formula yields a makespan defined in the Equation (3) of:

Hence, this set of jobs is feasible if the interval has a length of at least 3 time units. Figure 2 depicts the corresponding TL-plane computed by PCG: dashed lines represent processor capacities decreasing over time, while solid lines represent the remaining execution times of jobs. Bullets denote scheduling points corresponding to events triggered by jobs. Initially, the five longest jobs are scheduled on the processors according to the LRPT-FM rule. At time 0.5, the ready Job 6 triggers a $C_5$-event, as it must be executed continuously on ${\pi }_5$ to complete by the makespan. Job 6 and processor ${\pi }_5$ are then removed from the scheduling problem. The relative order of the remaining execution times of the running jobs remains unchanged. Job 5, previously executing on ${\pi }_5$, is preempted at time 0.5 and enters the ready state until it triggers a $C_4$-event at time 1.5. Both Job 5 and processor ${\pi }_4$ are then removed. The remaining running jobs are 1, 3, and 2; they are reassigned, in this order, to the fastest processors according to LRPT-FM, while Job 4 waits for an available processor. At time 2, Job 1 triggers a $C_2$-event and is removed along with processor ${\pi }_2$. The updated assignments are: Job 3 on ${\pi }_1$, Job 2 on ${\pi }_3$, and Job 4 continues to wait. Job 3 subsequently triggers a $C_3$-event, leading to the removal of both Job 3 and processor ${\pi }_3$. In the final subproblem, ${\pi }_1$ is the only available processor, executing Job 2 until its completion, which triggers a $B$-event at time 2.8. At the same moment, the ready Job 4 triggers a $C_1$-event and resumes execution on ${\pi }_1$ until the makespan. The schedule is thus completed with a total of 8 preemptions.

The PCG algorithm was proven optimal for scheduling periodic tasks with implicit deadlines in [4], but no preemption bound is guaranteed. We now discuss the limitations of PCG in achieving the best-known bound of $2(m-1)$.

We analyze the number of preemptions triggered at $B$-events by the original PCG algorithm with LRPT-FM sorting applied at each scheduling point. A set of 5 jobs is executed on 5 processors, with parameters given in Table 2. As shown in Figure 3, Job 5 completes on processor ${\pi }_5$ at time 2, triggering a $B$-event. The remaining jobs are then resorted by PCG and reassigned, resulting in 4 preemptions. Around time 4, Jobs 1 and 4 simultaneously trigger $C$-events on ${\pi }_2$ and ${\pi }_3$, causing 4 additional preemptions. Around time 6, Jobs 3 and 2 trigger $C$-events on ${\pi }_1$ and ${\pi }_4$, adding 2 more preemptions. In total, 10 preemptions occur in the TL-plane, exceeding the theoretical bound of $2(m-1)=8$.

No tight preemption bound is known for PCG. However, as previously shown, $B$-events can induce a significant number of preemptions, and this number may increase with the total number of jobs. As mentioned earlier, the best-known algorithms generate at most $2(m-1)$ preemptions, a bound that is independent of the number of jobs. Achieving this bound requires that (i) no preemptions are caused by $B$-events, and (ii) $C$-events yield at most two preemptions.

This paper is motivated by two fundamental questions regarding the behavior of the PCG algorithm:

• $\mathrm{■}$

  Is the application of the LRPT-FM rule necessary at every scheduling point to ensure optimality? This rule requires sorting jobs in non-increasing order of execution times. Avoiding this sorting step can prevent unnecessary preemptions within a TL-plane.

• $\mathrm{■}$

  Is it possible for a real-time algorithm to attain the tight preemption bound of $2(m-1)$ within a TL-plane? Achieving this bound provides a guarantee equivalent to that of the best-known offline polynomial-time scheduler.

We now introduce PCG^∗ and show that it achieves both objectives.

Obviously, identical multiprocessors are a particular case of uniform processor platforms in which all processor speeds are identical. As a consequence, any optimal algorithm for the uniform case is also optimal for identical processor platforms.

Horváth’s feasibility condition is a proper generalization of McNaughton’s condition. We formally exhibit that point in the next result.

We present an experimental comparison of PCG and PCG^∗ on synthetic job sets. Preemptions related to TL-plane switching are not taken into account. Those preemptions do not depend on the scheduling algorithm but on the DP-fair decomposition into independent scheduling subproblems. Hence, to enable a clear comparison on preemptions generated by PCG and PCG^∗, we only focus on preemption within a TL-plane, excluding those generated by TL-plane switching.

We generate synthetic job sets by randomly creating both the job processing requirements and the processor speeds as integers. Each job is characterized by a processing requirement drawn uniformly at random from the interval $[1,100]$. All jobs are released at time 0, corresponding to the beginning of a TL-plane. The platform is modeled as a set of uniform processors: for each processor, we set speeds independently and uniformly from the interval $[1,10]$. For each problem, job processing requirements and processor speeds are sorted in non-increasing order for computing the makespan using Horváth’s formula (i.e., Equation 3). For a given number of jobs $n$ and processors $m$, we generate 1000 synthetic systems, leading to robust statistical results. In Figure 6, the plots on the left show the results for TL-planes whose length is equal to the makespan, while the plots on the right correspond to the same problem sizes but with a TL-plane of length $1.5\times$ the makespan. Even when the TL-plane length equals the makespan, if the maximum in Horváth’s formula is achieved by one of the first $m-1$ terms, some idle times are inserted into the schedule. We consider three problem sizes with $m\in \{2,8,16\}$. As depicted in the plots, the number of preemptions generated by PCG increases as the number of jobs grows. This fact is logical since as the number of jobs increases, more and more $B$-events occur. On each event, PCG sorts jobs according to LRPT-FM, resulting in numerous preemptions. The same phenomenon is amplified whenever the length of the TL-plane increases in comparison with the optimal makespan (i.e., plots on the right in Figure 6). Hence, lower task utilization can lead to more preemptions using PCG. This is not the case for PCG^∗ since $B$-events do not generate any preemption. Using PCG^∗, if the number of jobs increases, then more $B$-events are experienced by the jobs and consequently the number of $C$-events decreases, generating fewer preemptions. That is why fewer preemptions are observed using PCG^∗ when the TL-plane is longer in comparison with the optimal makespan that is the smallest possible TL-plane length in a feasible schedule. This is important when using TL-plane-based scheduling for real-time systems as in most cases, the TL-planes lengths obtained by the DP-fair decomposition are longer than the minimal makespan.

Overall, across all tested configurations, PCG^∗ consistently yields fewer preemptions than PCG, and the gap widens as the TL-plane length increases relative to the makespan.

We have presented PCG^∗, a variant of the Precaution Cut Greedy (PCG) algorithm [4], which is optimal for scheduling periodic tasks on uniform multiprocessor platforms. Our algorithm guarantees at most $2(m-1)$ preemptions per TL-plane on uniform platforms, which constitutes the tightest preemption bound achievable by any polynomial-time algorithm. This is the first real-time scheduling algorithm that guarantees this tight preemption bound for uniform platforms. Both algorithms have similar computational complexity. The numerical experiments presented in this work provide strong evidence that PCG^∗ yields a substantial reduction in the number of preemptions relative to PCG. PCG^∗ also achieves McNaughton’s tighter bound of $m-1$ preemptions [17] when applied to identical platforms. This bound was previously reached by the LRE-TL algorithm [9], which is specifically designed for identical platforms.

In future work, we plan to extend the proposed approach to sporadic task systems, which would allow the scheduler to support genuinely event-driven workloads in which job releases are not strictly periodic. We also intend to develop a work-conserving variant, in order to better accommodate execution-time variability and to avoid leaving processors idle when runnable work is available. Such a variant would additionally facilitate a tighter integration of aperiodic-task servers, thereby improving responsiveness to aperiodic demand while preserving the key structural properties of the TL-plane abstraction.