Boost-At-The-Tail: Work-Triggered Frequency Boosting for Fixed-Priority Scheduling

We briefly recall the standard response-time analysis (RTA) for preemptive fixed-priority scheduling. Consider a task set $\mathrm{\Gamma }=\{{\tau }_1,\mathrm{\dots },{\tau }_n\}$ scheduled on a uniprocessor under a fixed-priority policy. Each task ${\tau }_i$ is characterized by a worst-case execution time $C_i$, period $T_i$, and relative deadline $D_i$. We assume constrained deadlines, i.e., $D_i\le T_i$ for all tasks. Let $hp({\tau }_i)$ denote the set of tasks with higher priority than ${\tau }_i$. Under classical RTA, the worst-case response time of task ${\tau }_i$ is computed as the smallest fixed point of the recurrence

with initialization $R_i^{(0)}=C_i$. The iteration continues until convergence or until $R_i^{(k+1)}>D_i$. The task ${\tau }_i$ is deemed schedulable if the iteration converges to a value $R_i\le D_i$; otherwise, it is declared unschedulable. This fixed-point formulation of response-time analysis was introduced by Joseph and Pandya [16]. Rate Monotonic Scheduling (RMS), introduced by Liu and Layland [19], is a special case in which priorities are assigned in order of increasing task periods.

Under fixed-priority scheduling, the response time of a task ${\tau }_i$ is determined by the fixed point of Eq. (1). A deadline violation occurs when the recurrence converges to a value $R_i>D_i$. A key property of Eq. (1) is that $R_i$ appears on both sides of the recurrence through the interference term $\lceil \frac{R_i}{T_j}\rceil C_j$. Therefore, reducing the effective execution time of ${\tau }_i$ can have a compound effect on the computed response time: (1) It directly decreases the base term $C_i$. (2) It may also decrease the number of higher-priority jobs that interfere, because a smaller response-time estimate can reduce one or more ceiling terms $\lceil \frac{R_i}{T_j}\rceil$.

In particular, if a reduction in effective execution time causes the fixed point to cross a release boundary of some higher-priority task ${\tau }_j$, i.e., the value of $\lceil \frac{R_i}{T_j}\rceil$ decreases by one, then the computed interference term is reduced by an entire $C_j$. Thus, a small reduction in effective execution time can remove one full higher-priority job from the worst-case interference bound, which may be sufficient to restore $R_i\le D_i$. This non-linear effect underlies the possibility of restoring schedulability through bounded execution-time reductions. This observation motivates mechanisms that compensate deadline violations by reducing effective execution time through controlled acceleration, rather than by changing task priorities. This perspective is adopted in the subsequent execution-time reduction view and in the design of work-triggered boosting.

The processor supports two discrete operating frequencies: a nominal frequency $f_{\mathrm{n}}$ and a boost frequency $f_{\mathrm{B}}=s_{\mathrm{B}}\cdot f_{\mathrm{n}},$ where $s_{\mathrm{B}}>1$ is a fixed boost speedup factor. When executing at the boost frequency, the processor completes $s_{\mathrm{B}}$ units of nominal work per unit time. We assume that execution demand scales proportionally with frequency; microarchitectural effects such as memory stalls are subsumed into WCET estimation. The processor can switch dynamically between $f_{\mathrm{n}}$ and $f_{\mathrm{B}}$ at runtime; any frequency-transition overhead is assumed negligible for analysis purposes and is conservatively included in the WCET estimates. Modern processors limit short-term boosting through hardware thermal management mechanisms [14]. Processor temperature is modeled as a time-varying state $T(t)$. Boost execution is governed by a hardware thermal hysteresis mechanism with two thresholds . Boosting is permitted only while $T(t)\le T_{\mathrm{b}}$. If $T(t)>T_{\mathrm{b}}$, boosting is disabled by hardware and is re-enabled only once the temperature falls below $T_{\mathrm{a}}$. The system monitors temperature online and enforces this rule at runtime. In this paper, we focus on executions in which boosting remains available (i.e., thermal throttling is avoided), an assumption supported by the experimental observations reported in Sections 7.2 and 7.4. If boost is disabled by hardware thermal control, the system executes at the nominal frequency. Such executions fall outside the normal-mode setting considered in this paper; we discuss possible system-level responses informally in Appendix A.

We adopt a conservative bounded-rate abstraction of thermal dynamics consistent with standard first-order thermal models (e.g., [10, 9]). When executing at the boost frequency and $T(t)\le T_{\mathrm{b}}$, temperature increases at most at rate $r_{\mathrm{h}}>0$. When the processor is idle and $T(t)>T_{\mathrm{a}}$, temperature decreases at least at rate $r_{\mathrm{c}}>0$. When executing at the nominal frequency, temperature is assumed not to increase in a manner that affects boost eligibility. This abstraction is used only to justify bounded boost availability and is not used directly in schedulability analysis.

The platform provides a boost availability contract over arbitrary intervals of length $L$: if $T(t_0)\le T_{\mathrm{b}}$ at the beginning of an interval $[t_0,t_0+L)$, then all boost requests issued within the interval are guaranteed to be honored up to a budget of $k$ time units. This abstraction is consistent with modern processors that regulate short-term boosting via hardware-managed power and thermal windows. For example, Intel Turbo Boost permits elevated performance operation (e.g., PL2) for a bounded duration controlled by a configurable time constant (Tau) [13]. The budget $k$ is chosen conservatively such that even $k$ consecutive time units of boost execution starting from temperature $T_{\mathrm{b}}$ cannot violate the hardware thermal limit $T_{\max }$. Under the bounded-rate abstraction, a sufficient condition is $T_{\mathrm{b}}+k{r}_{\mathrm{h}}\le T_{\max }.$ Because consecutive boost execution represents the thermal worst-case scenario, any execution containing at most $k$ boosted time units within the interval, regardless of interleaving with nominal or idle execution, is also thermally safe. Our schedulability analysis relies solely on the parameters $k$ and $L$; the thermal abstraction serves only as a correctness argument for the existence of this contract.

We formulate offline parameter selection as the problem of finding a minimum execution-time reduction vector $𝚫=({\mathrm{\Delta }}_1,\mathrm{\dots },{\mathrm{\Delta }}_n)$ such that the reduced task set with execution times $C_i^{\prime }=C_i-{\mathrm{\Delta }}_i$ is schedulable under fixed-priority scheduling, and such that each reduction can be realized by bounded boost execution. Each reduction ${\mathrm{\Delta }}_i$ is mapped to a per-job boost allowance

which ensures that $w_i$ units of boost execution compensate for an effective reduction of at least ${\mathrm{\Delta }}_i$ units of nominal work. We define the worst-case cumulative boost demand over any interval of length $L$ as

Intuitively, $\mathrm{BoostUB}(L)$ bounds the worst-case total number of boosted time slots requested if every job uses its entire allowance. This quantity upper-bounds the total number of boost time units that may be requested by all jobs within any interval of length $L$ under the proposed runtime policy. This bound assumes that all jobs release as early as possible and that each job requests its full allowance $w_i$. In our evaluation, we set $L$ to the hyperperiod $H$ to obtain a conservative, cycle-aligned bound; the analysis applies to any platform-defined window length $L$. A task set is admitted in normal mode only if

where $k$ is the platform-provisioned boost budget per interval. We incorporate the admission constraint directly into the offline search: any intermediate reduction vector for which $\mathrm{BoostUB}(L)>k$ holds is treated as infeasible and is not committed.

We define the runtime boost activation policy for the normal-mode setting considered in this paper, where boosting remains available throughout the analyzed interval. Scheduling priorities follow the underlying fixed-priority order, e.g., Rate Monotonic Scheduling. Whenever a job ${\tau }_{i,j}$ is selected for execution at time $t$, the processor frequency is determined based on the job’s worst-case remaining execution demand $C_{i,j}^{\mathrm{rem}}(t)$.

The processor executes at the boost frequency if and only if the work-trigger condition holds:

Otherwise, execution proceeds at the nominal frequency $f_{\mathrm{n}}$. We do not maintain an online boost-budget counter. Instead, we rely on offline admission (Eq. (4)) and the platform-availability argument in Lemma 2 to ensure that the global boost budget within any window of length $L$ is not exceeded under the normal-mode assumptions. Intuitively, the work-trigger condition confines boosting to the final portion of a job’s execution. Moreover, since $C_{i,j}^{\mathrm{rem}}(t)$ is a conservative bound on worst-case remaining execution demand and most jobs complete before their worst-case bound, the trigger is typically not reached in common-case executions. Hence, boost slots are activated only occasionally, mitigating thermal stress in practice. Evaluating the boost trigger requires only a constant-time check of Eq. (5) and simple arithmetic updates of $C_{i,j}^{\mathrm{rem}}(t)$, and thus incurs negligible runtime overhead.

We illustrate Boosted-FP using the periodic task set ${\tau }_1(T_1=6,C_1=3)$, ${\tau }_2(T_2=8,C_2=2)$, and ${\tau }_3(T_3=12,C_3=3)$, scheduled under Rate Monotonic (RM) priorities. The processor supports a boost speed $s_{\mathrm{B}}=1.5$. The hyperperiod of the task set is $H=\mathrm{lcm}(6,8,12)=24$. We assume that boost eligibility is maintained throughout execution and that the platform availability contract holds over the hyperperiod. Standard response-time analysis under nominal execution speed shows that ${\tau }_3$ violates its deadline, while ${\tau }_1$ and ${\tau }_2$ are schedulable. Reducing $C_3$ by one unit restores schedulability, yielding ${\mathrm{\Delta }}_3=1$ and ${\mathrm{\Delta }}_1={\mathrm{\Delta }}_2=0$. The corresponding boost parameter is $w_3=\lceil \frac{1}{s_{\mathrm{B}}-1}\rceil =2,$ and the feasibility condition $s_{\mathrm{B}}{w}_3\le C_3$ is satisfied. Thus, $w_1=w_2=0$ and $w_3=2$. Over one hyperperiod, $\text{BoostUB}(H)=\lceil \frac{24}{12}\rceil w_3=2\cdot 2=4.$ Hence, the task set is admissible in normal mode for any platform budget $k\ge 4$. Since $s_{\mathrm{B}}{w}_3=1.5\times 2=3\ge C_3$, the work-trigger condition $C_{3,j}^{\mathrm{rem}}(t)\le s_{\mathrm{B}}{w}_3$ is satisfied immediately upon release. Consequently, each job of ${\tau }_3$ executes entirely at boost speed whenever it is scheduled. Each job therefore completes in $C_3/s_{\mathrm{B}}=3/1.5=2$ units of processor time. Tasks ${\tau }_1$ and ${\tau }_2$ execute exclusively at nominal speed. Figure 1 shows the resulting schedule over one hyperperiod, where darker segments indicate execution at boost speed. This example illustrates how Boosted-FP restores schedulability while confining boost execution to the task that requires it.

Recall from Section 5.1 that the offline procedure computes, for each task ${\tau }_i$, a reduction parameter ${\mathrm{\Delta }}_i$ and a corresponding boost parameter $w_i$. Based on these values, we define a hypothetical task set ${\mathrm{\Gamma }}^{\prime }$ that is identical to the original task set $\mathrm{\Gamma }$, except that each task ${\tau }_i$ has execution time $C_i^{\prime }=C_i-{\mathrm{\Delta }}_i.$ By Lemma 3, any job of task ${\tau }_i$ executes under Boosted-FP for at most $C_i^{\mathrm{eff}}=C_i-(s_{\mathrm{B}}-1)w_i$ units of processor time, excluding preemption gaps. By construction of $w_i$ (Eq. (2)), we have $(s_{\mathrm{B}}-1)w_i\ge {\mathrm{\Delta }}_i$, and therefore $C_i^{\mathrm{eff}}\le C_i-{\mathrm{\Delta }}_i=C_i^{\prime }.$ Hence, each job of ${\tau }_i$ under Boosted-FP executes for no more processor time than assumed for ${\tau }_i$ in the reduced task set ${\mathrm{\Gamma }}^{\prime }$.

For each job ${\tau }_{i,j}$, the scheduler maintains $C_{i,j}^{\mathrm{rem}}(t)$, which denotes an upper bound on the job’s remaining execution demand measured in units of nominal work. At release time $r_{i,j}$, $C_{i,j}^{\mathrm{rem}}(r_{i,j})=C_i,$ and $C_{i,j}^{\mathrm{rem}}(t)$ is monotonically non-increasing over time. A nominal slot, when ${\tau }_{i,j}$ executes, reduces $C_{i,j}^{\mathrm{rem}}$ by one unit, whereas a boosted slot reduces it by $s_{\mathrm{B}}$ units.

By definition, ${\delta }_{i,j}\ge 0$. The first case corresponds to jobs that complete within their nominal execution region, in which case both unused nominal and boost reservations contribute to the execution slack. The second case corresponds to jobs that complete during boosted execution, where execution slack arises only from the unused portion of the reserved boosted time. Execution slack therefore represents the portion of processor time provisioned by the schedulability analysis that remains unused upon job completion.

Dynamic boost cancellation is applied only when a job becomes eligible for boost execution according to the boost-trigger condition defined in Section 5.2. Recall that a job ${\tau }_{i,j}$ is boosted only when its remaining worst-case execution bound satisfies

where $w_i$ is the boost allowance of task ${\tau }_i$ and $s_{\mathrm{B}}>1$ is the boost factor.

Dynamic boost cancellation operates on a per-job basis. Each active job ${\tau }_{i,j}$ maintains a slack credit variable $S_{i,j}$, which is initialized to zero at job release. When ${\tau }_{i,j}$ completes, it is removed from the active set and its slack credit is discarded (equivalently, set to zero). Slack credits are maintained only for active jobs. Thus, a job ${\tau }_{i,j}$ can only receive slack generated while it is active, i.e., slack produced after its release and before its completion. Slack generated before release is not visible to ${\tau }_{i,j}$, and upon completion its credit is discarded. Although the platform is uniprocessor and executes at most one job at a time, multiple jobs may be active (released but not yet completed) and reside in the ready queue. The slack-credit updates described below are performed by the scheduler atomically at discrete events (job completion and scheduling decisions), and therefore do not require concurrent access or synchronization. Accordingly, the term “active jobs” refers to jobs that are pending at the same time, not to jobs executing in parallel.

When a job ${\tau }_{k,\mathrm{\ell }}$ completes and produces execution slack ${\delta }_{k,\mathrm{\ell }}$, this slack is made available to all active jobs of lower priority:

Whenever job ${\tau }_{i,j}$ satisfies the trigger condition (6), the scheduler first checks whether sufficient slack credit exists: $S_{i,j}\ge (s_{\mathrm{B}}-1).$ If the condition holds, boost execution is canceled and ${\tau }_{i,j}$ executes at nominal speed for the current slot. Otherwise, boost execution proceeds normally. Because execution slack is replicated across multiple active lower-priority jobs, slack consumption must be performed consistently. Therefore, upon canceling a boost for job ${\tau }_{i,j}$, the scheduler subtracts $(s_{\mathrm{B}}-1)$ units of slack from the slack credit of all active jobs of priority lower than or equal to ${\tau }_i$:

Dynamic boost cancellation adapts boost usage to actual execution behavior without weakening the schedulability guarantees established in Section 5.4. Since dynamic boost cancellation never increases execution demand or interference beyond the bounds assumed in the schedulability analysis, all hard real-time guarantees remain valid. We next formalize the slack-credit bookkeeping and show that replicated credits cannot cause over-commitment.

To quantify the relative power and thermal impact of boosted execution, we employ a CMOS-inspired energy model [8] used solely for experimental comparison. When executing at operating point $(V_{dd},f)$, dynamic power is modeled as $P_{\mathrm{dyn}}=C_{\mathrm{eff}}{V}_{dd}^{2}f,$ and leakage power as $P_{\mathrm{leak}}=I_{\mathrm{leak}}\cdot V_{dd},$ where $C_{\mathrm{eff}}$ is the effective switched capacitance per cycle (a technology- and workload-dependent constant aggregating gate switching activity) and $I_{\mathrm{leak}}$ is the leakage current. Both are treated as constants in our model since we report only relative energy quantities normalized to $E_{\mathrm{n}}$, the dynamic energy consumed per slot at $f_{\mathrm{n}}$ (defined below). We assume that supply voltage scales approximately linearly with frequency ($V_{\mathrm{dd}}\propto f$). Under this assumption, dynamic power scales cubically with frequency, whereas leakage power scales linearly. The processor supports two discrete frequencies: nominal $f_{\mathrm{n}}$ and boost $f_{\mathrm{B}}=s_{\mathrm{B}}{f}_{\mathrm{n}}$. Let $E_{\mathrm{n}}$ denote the dynamic energy consumed per slot at $f_{\mathrm{n}}$. Since dynamic power scales cubically with frequency and execution duration scales inversely with frequency, the dynamic energy consumed per slot scales quadratically with frequency. Hence, execution at $f_{\mathrm{B}}$ consumes $s_{\mathrm{B}}^2{E}_{\mathrm{n}}$ dynamic energy per slot. When the processor is idle, no useful switching occurs; however, background activity incurs a fraction of nominal dynamic energy, modeled as $\alpha E_{\mathrm{n}}$, where $\alpha \in [0,1]$. Since our comparisons normalize by the same schedule horizon $H$, and since the focus is relative dynamic switching stress, we report dynamic-energy–based metrics; incorporating leakage would not change qualitative trends. This model is not used in the schedulability analysis and serves only as a proxy for relative power and thermal stress induced by boosting.

We validate that the assumptions underlying our execution model, distinct nominal and boost operating points, and bounded short-term boosting, are observable on commodity hardware. The goal of this experiment is to confirm that the abstraction used in our analysis is consistent with practical processor behavior.

Measurements were conducted on a laptop running Ubuntu 22.04 equipped with an 11th Gen Intel^® Core™ i7-11800H processor (8 cores, nominal frequency 2.30 GHz) with Intel Turbo Boost enabled. We instrumented the processor using the Linux intel_pstate interface and Intel RAPL energy counters. A custom script periodically alternates the processor between three phases: BOOST (Turbo enabled, maximum performance), NOMINAL (Turbo disabled, maximum performance), and IDLE (Turbo disabled, minimum performance). During BOOST and NOMINAL phases, a single core is stressed using stress-ng; during IDLE, the system remains largely inactive. We sample core frequency (kHz), package temperature (^∘C), and RAPL energy (µJ) once per second and derive instantaneous power (W) from successive energy readings. The three-phase pattern is repeated multiple times to observe steady-state behavior and transitions. This setup emulates the average workload model used in our analysis: tasks execute predominantly at nominal speed, occasionally experience short-term boost execution, and are separated by idle or low-activity intervals.

The measurements reveal three clearly separated regimes corresponding to BOOST, NOMINAL, and IDLE phases. In BOOST mode, frequency approaches the turbo range, with increased power and temperature. In NOMINAL mode, frequency stabilizes near the nominal base operating range with reduced power and thermal growth. In IDLE mode, frequency and power drop to minimal levels and temperature decays. Figure 2 illustrates representative time series of frequency, power, and temperature across BOOST, NOMINAL, and IDLE phases. These observations support the model introduced in Section 3: (i) the processor provides two distinct operating points; (ii) boosted execution incurs higher but bounded power and thermal cost; and (iii) idle intervals enable recovery. Hence, the work-triggered boosting abstraction and the $(L,k)$ boost availability contract are compatible with observed hardware behavior.

Although the boost budget bound guarantees schedulability in the worst case, actual job execution times are typically smaller than their WCET. Consequently, reserved boost capacity may remain unused in common-case executions. Dynamic boost cancellation reclaims this slack at runtime by replacing boost execution with accumulated early-completion slack when available. This preserves the worst-case boost bound and schedulability guarantees while reducing common-case energy and thermal overhead.

We compare Boosted-FP against an offline analytical baseline that ensures schedulability via global frequency scaling. Unlike our approach, the baseline does not exploit work-triggered boosting or execution slack reclamation; instead, it uniformly accelerates all execution whenever the task set is not schedulable at nominal frequency under the given fixed-priority (FP) policy.