Formula sheet

Real-Time Task Scheduling Formula Sheet

Computer engineering formula sheet for real-time task scheduling, covering utilization, hyperperiods, deadline margin, response-time analysis, rate-monotonic bounds, EDF feasibility, jitter, blocking, queues, watchdog timing, and validation metrics.

Branch: Computer Engineering
Content: Formula sheet
Updated: Jun 20, 2026
Revision: v1.0.0 · reviewed

This formula sheet collects first-pass checks for real-time task scheduling in embedded systems, operating systems, control firmware, industrial controllers, robotics, power electronics, medical devices, and edge computers. Use it to screen CPU utilization, deadlines, jitter, blocking, queues, watchdog timing, and validation evidence.

The formulas are not a substitute for worst-case execution-time analysis, hardware measurement, scheduler documentation, or fault testing. They are useful only when task periods, deadlines, priorities, release jitter, interrupt load, shared resources, and safe states are defined.

Task Model

A periodic task is commonly described by:

\tau_i=(C_i,T_i,D_i,J_i,B_i)

where:

$C_i$ is worst-case execution time;
$T_i$ is period or minimum inter-arrival time;
$D_i$ is relative deadline;
$J_i$ is release jitter;
$B_i$ is blocking time from lower-priority work or shared resources.

Use worst-case or justified upper-bound values for hard real-time claims. Typical execution time is not enough.

CPU Utilization

Utilization of one periodic task:

\displaystyle U_i=\frac{C_i}{T_i}

Total utilization:

\displaystyle U=\sum_i\frac{C_i}{T_i}

For a single processor, a necessary condition is:

U\leq1

This condition is necessary, not always sufficient, because deadlines, priorities, blocking, jitter, interrupts, and non-preemptive sections also matter.

Interrupt Load

For periodic or bounded-rate interrupts:

U_{ISR}=\sum_i f_iC_i

where $f_i$ is interrupt frequency and $C_i$ is worst-case interrupt execution time.

Remaining utilization budget:

U_{remaining}=1-U_{tasks}-U_{ISR}

Interrupt execution should include entry overhead, exit overhead, shared-data handling, and any disabled-interrupt interval caused by the handler.

Hyperperiod

For periodic tasks with integer periods, the hyperperiod is:

H=\operatorname{lcm}(T_1,T_2,\ldots,T_n)

The hyperperiod is the schedule repeat window for simple periodic task sets.

Large hyperperiods can make exhaustive schedule testing expensive. In that case, combine analytical checks with targeted worst-case phasing tests.

Deadline Margin

For a measured or bounded response time $R_i$ :

M_i=D_i-R_i

The task meets its deadline when:

M_i\geq0

Relative margin:

\displaystyle M_{rel,i}=\frac{D_i-R_i}{D_i}

Use response time from the start event that matters to the system: sensor sample, interrupt arrival, message arrival, command request, or control-cycle release.

Rate-Monotonic Utilization Bound

For $n$ independent periodic tasks with deadlines equal to periods under rate-monotonic priority assignment, a sufficient utilization bound is:

U\leq n(2^{1/n}-1)

As $n$ grows, this bound approaches:

\ln 2\approx0.693

This is a conservative sufficient test. A task set above the bound may still be schedulable, but it needs more detailed analysis.

Earliest Deadline First Feasibility

For independent preemptive periodic tasks with deadlines equal to periods on one processor, earliest deadline first has the utilization condition:

U\leq1

When deadlines are shorter than periods, use processor-demand or response-time analysis rather than this simplified screen.

EDF can be efficient, but overload behavior, implementation cost, priority inversions, and certification evidence must still be reviewed.

Fixed-Priority Response-Time Analysis

For a task $\tau_i$ under fixed-priority preemptive scheduling, a common response-time iteration is:

\displaystyle R_i^{(k+1)}=C_i+B_i+\sum_{j\in hp(i)}\left\lceil\frac{R_i^{(k)}+J_j}{T_j}\right\rceil C_j

where $hp(i)$ is the set of tasks with higher priority than $\tau_i$ .

Start with:

R_i^{(0)}=C_i+B_i

The task passes when the iteration converges and:

R_i\leq D_i

The formula depends on assumptions about preemption, priorities, release jitter, blocking, and independence. Those assumptions must be documented.

Blocking Time

If a task can be blocked by one non-preemptive lower-priority critical section, a screening value is:

B_i=\max(CS_{lp})

where $CS_{lp}$ is the set of lower-priority critical sections that can block task $\tau_i$ .

Priority inheritance or priority ceiling protocols can bound priority inversion, but they must be configured and tested. Unbounded locks are incompatible with hard real-time claims.

Release Jitter

Peak-to-peak release jitter:

J_{pp}=t_{release,max}-t_{release,min}

Relative jitter:

\displaystyle J_{rel}=\frac{J}{T}

Sample-time error due to jitter:

\displaystyle e_t=\frac{J}{T_s}

Jitter can affect control stability, sensor timing, communication windows, and actuator synchronization. Measure it under representative interrupt and bus load.

Non-Preemptive Section Check

If interrupts or preemption are disabled for:

t_{np,max}

then any event requiring response within deadline $D_e$ must satisfy:

t_{np,max}+t_{response,rest}\leq D_e

Long non-preemptive sections are common sources of missed deadlines. Flash writes, logging, drivers, and critical sections should be reviewed explicitly.

Queue Stability

For arrival rate $\lambda$ , service rate $\mu$ , and $c$ equivalent servers:

\displaystyle \rho=\frac{\lambda}{c\mu}

A stable queue requires:

\rho<1

Queue fill during a service gap:

Q_{gap}=\lambda t_{gap}

Queue capacity is a design decision, not a substitute for service capacity. Define overflow policy, backpressure, drop behavior, and fault response.

Buffer Fill Time

If input rate is greater than output rate:

R_{in}>R_{out}

buffer fill time is:

\displaystyle t_{fill}=\frac{B_{buffer}}{R_{in}-R_{out}}

This is useful for detecting overload windows. It does not prove long-term stability if the average output rate remains lower than input rate.

Watchdog Timing

A basic watchdog timing condition is:

t_{normal,max}<t_{watchdog}<t_{unsafe}

where $t_{normal,max}$ is the longest acceptable normal refresh interval and $t_{unsafe}$ is the time before uncontrolled behavior becomes unacceptable.

Watchdog coverage should include stuck loops, interrupt lockout, scheduler starvation, communication deadlock, brown-out, memory corruption, and failed recovery.

Deadline Miss Ratio

Measured deadline miss ratio:

\displaystyle DMR=\frac{N_{miss}}{N_{jobs}}

For hard real-time functions, the target is usually:

N_{miss}=0

For soft real-time functions, the acceptable ratio must be tied to service quality, safety, or user impact.

Timing Measurement Summary

Mean response time:

\displaystyle \bar{R}=\frac{1}{N}\sum_iR_i

Worst observed response time:

R_{max}=\max(R_1,R_2,\ldots,R_N)

Execution-time margin:

M_C=C_{budget}-C_{measured,max}

For hard timing claims, mean response time is not enough. Record maximum observed value, test duration, workload, instrumentation overhead, and why the unobserved worst case is bounded.

Practical Checklist

Use this formula sheet with a short release checklist:

Define every periodic task, interrupt, queue, deadline, and safe state.
Use worst-case execution time or justified measured upper bounds.
Account for interrupts, blocking, release jitter, and disabled-preemption regions.
Check CPU utilization, response time, queue stability, and watchdog windows.
Measure timing on representative hardware under nominal, overload, and fault conditions.
Record scheduler configuration, priority table, clock settings, compiler version, and firmware build identity.
Link timing margins to validation tests and field diagnostics.

Real-time scheduling is not only a scheduler selection problem. It is a system evidence problem: the hardware, firmware, drivers, queues, interrupts, control loops, diagnostics, and release records must all support the same timing claim.

REF

Disciplines