Some tasks are useful only if they finish on time. An audio device must supply the next buffer before the current one finishes playing. A motor controller must update its output within a fixed interval. A trading system may need to respond before an opportunity disappears.

For these systems, eventually producing the right result is not enough, the result must also arrive at the right time.

In a real-time system, correctness depends on both the result and when it is produced.

Real-time scheduling is therefore less about maximizing average throughput or simply making programs run faster. Its goal is to determine whether time-sensitive work can meet its deadlines and to schedule that work predictably.

Suppose two systems process the same periodic task.

System A usually finishes in 1 millisecond but occasionally takes 30 milliseconds:

System B always finishes between 4 and 5 milliseconds:

If the deadline is 10 milliseconds, System B is suitable while System A is not, despite A's better average.

The relevant property is predictability:

A low average or a good p99 does not prove a hard guarantee. The unobserved worst case may still violate the deadline.

Deadlines have different consequences.

Hard real-time

A hard deadline must not be missed. A late result is considered a system failure because it can cause unsafe or invalid behavior.

Examples include selected flight-control operations, protection mechanisms, and precisely timed industrial control.

Hard real-time claims require evidence about worst-case behavior, not merely successful testing.

Firm real-time

A result has no value after its deadline, but an occasional miss does not necessarily constitute total system failure.

A late sensor sample or stale market decision may be discarded. The system should minimize misses, but it can continue operating after one.

Soft real-time

A late result still has value, but quality degrades.

Audio glitches, delayed animation frames, and slow interactive responses are common examples. Occasional misses may be tolerable even though repeated misses produce a poor experience.

The classification belongs to the application requirement. The same 20-millisecond delay can be harmless in one system and unacceptable in another.

A real-time task describes recurring or event-driven work. Each activation of that task is a job.

For example, a temperature-control task may release one job every 10 milliseconds:

Task τ releases job 1 at time 0, job 2 at time 10, and job 3 at time 20.

The task is the recurring specification. A job is one concrete unit of execution with its own release and deadline.

This distinction matters because scheduling decisions are made among currently released jobs, while schedulability analysis usually reasons about the infinite sequence described by each task.

A common model describes task τi using:

For a job released at time ri, its absolute deadline is:

Suppose:

Each job may require up to two milliseconds of CPU time. Jobs are released ten milliseconds apart, and each must finish within seven milliseconds of its own release:

The job is released at time 0, must finish by its absolute deadline at time 7, and the next release comes at time 10. Within that window it needs at most 2 ms of CPU.

When D = T, a job's deadline coincides with the next periodic release. This is called an implicit-deadline task model.

The parameters are promises. If a job actually requires more than C, or arrives sooner than allowed by T, the schedulability analysis no longer describes the workload.

For one job:

A job is released, waits, executes, finishes, and its deadline follows. The gap between finishing and the deadline is the slack.

Important values include:

In real-time analysis, response time commonly means the complete release-to-finish interval. This differs from the earlier CPU-scheduling metric that used response time for delay until first execution. The surrounding context determines the definition.

Lateness is:

A negative lateness means the job finished early. A positive value means it missed.

Tardiness excludes early completion:

A hard real-time task requires zero tardiness for every job covered by the guarantee.

A periodic task releases jobs at regular intervals:

A sporadic task releases jobs irregularly but promises a minimum separation:

This minimum separation gives analysis a bound on how frequently demand can arrive.

An aperiodic task has no simple recurring release pattern. User input and one-off administrative requests are examples.

Hard guarantees require some bound on arrival demand. If an unlimited number of jobs can arrive at once, no finite CPU capacity can guarantee all deadlines.

C must represent a safe bound on CPU demand, often called the worst-case execution time (WCET).

Average execution time is not sufficient:

An analysis using C = 3 ms is invalid when the rare path requires 8 milliseconds.

Bounding execution is difficult because time can vary with:

Testing can find slow cases, but it does not by itself prove that a slower unseen case is impossible. Hard real-time engineering constrains hardware, software paths, and interference so that a defensible bound can be established.

For an implicit-deadline periodic task:

If a task needs two milliseconds every ten milliseconds:

For n tasks on one CPU:

If U > 1, the tasks demand more than one full CPU over time:

U ≤ 1 is necessary for implicit-deadline tasks on one CPU, but it is not sufficient for every scheduling algorithm or every richer task model.

Utilization also ignores direct scheduling overhead unless that overhead is included in the execution budgets.

These terms answer different questions.

Feasible means that some valid schedule exists that meets all deadlines under the model.

Schedulable under an algorithm means the selected scheduling algorithm meets all deadlines.

A task set can be feasible under one algorithm and miss deadlines under another.

Admission control decides whether a new task may enter the guaranteed set:

The test considers the candidate together with everything already admitted. A task that would be feasible on an empty system can still be rejected here.

Without admission control, a system can promise more CPU time than exists. A scheduler cannot enforce mutually impossible guarantees.

In fixed-priority scheduling, every task receives a priority that remains constant across its jobs. The highest-priority ready job executes, and lower-priority work is preempted when necessary.

The schedule is predictable because the ordering rule does not change with absolute deadlines.

Its main design question is priority assignment:

Which task should receive the higher fixed priority?

One classical answer is Rate Monotonic scheduling.

Rate Monotonic (RM) assigns higher priority to tasks with shorter periods.

For:

A has higher RM priority because it releases jobs more frequently.

Classical RM analysis assumes:

The assumptions must match the real workload before the result can be treated as a guarantee.

For n independent implicit-deadline periodic tasks, RM provides a sufficient utilization test:

For two tasks:

For a large number of tasks, the bound approaches:

If the task set is at or below the bound, it is guaranteed schedulable under the model.

If it exceeds the bound, the test is inconclusive. The task set may still be schedulable, so an exact analysis or schedule trace is required.

The bound is sufficient, not necessary.

Earliest Deadline First (EDF) uses dynamic priorities.

At every scheduling decision:

Run the ready job with the earliest absolute deadline.

Suppose:

EDF selects B, then reconsiders whenever a job arrives, finishes, or changes the ready population.

A task does not have one permanent EDF priority. Each job's urgency changes as absolute deadlines differ.

For independent, preemptible, implicit-deadline tasks on one ideal CPU with zero overhead, EDF can schedule every feasible task set:

This utilization result does not automatically apply to arbitrary relative deadlines, execution overruns, resource blocking, or real implementation costs.

Consider:

Both tasks release their first jobs at time 0.

Their total utilization is:

The workload demands about 97.1% of one CPU. It exceeds the two-task RM sufficient bound of about 82.8%, but it remains below 100%.

The utilization values alone tell us:

Now trace the schedules.

A has the shorter period, so RM gives A higher fixed priority.

At time 0, both first jobs are released:

A0 runs first and completes at time 2. B0 then runs:

A0 runs from time 0 to 2, and B0 starts at time 2.

By time 5, B0 has received three of its four required units. A's next job is released:

RM priorities belong to tasks, not individual absolute deadlines. A1 preempts B0 because task A always outranks task B:

B0 is pushed past its deadline at time 7 because A1 outranks it on task priority, regardless of how urgent B0 has become.

B0's deadline is time 7. At that instant, it still has one CPU unit remaining:

Task B also releases its next job, B1, at time 7. The overdue B0 remains the older unfinished job and runs from time 7 to 8 before B1 can begin.

The task set misses a deadline under RM.

Fixed-priority response-time analysis accounts for interference from higher-priority tasks.

For lower-priority B:

The recurrence is:

Start with B's own execution:

Iterate:

The estimate converges to:

Because:

B is not schedulable under this RM priority assignment. The calculation matches the timeline.

At time 0:

EDF runs A0 from time 0 to 2, then B0.

At time 5, A1 arrives with absolute deadline 10. B0 has one unit remaining and an earlier deadline of 7:

EDF does not preempt B0. B0 completes at time 6, before its deadline. A1 then runs:

B0 keeps the CPU here because its deadline at time 7 is nearer than A1's at time 10. Both jobs meet their deadlines.

B's next job arrives at time 7 with deadline 14. A1's deadline is 10, so A1 continues and finishes at time 8.

The first jobs complete as follows:

EDF meets these deadlines. Under the stated ideal assumptions, the utilization theorem establishes schedulability for the continuing implicit-deadline task set because 34/35 ≤ 1.

EDF can use more of an ideal CPU while preserving schedulability. RM can be easier to reason about operationally because the most important task classes retain fixed priority.

Neither algorithm rescues an infeasible workload. A demand of 120% cannot be scheduled on one 100% CPU without rejecting work, changing budgets, extending deadlines, or adding capacity.

Even a correctly admitted system can overload if:

Under fixed priorities, high-priority tasks may continue meeting deadlines while lower-priority tasks absorb the misses.

Under EDF, overdue and near-deadline jobs can compete intensely. Without an overload policy, misses can cascade because late work continues consuming capacity needed by newer jobs.

A real-time design should decide in advance:

Deadline scheduling needs a failure policy as well as a normal policy.

A scheduler cannot dispatch urgent work if the current execution cannot be preempted for an unbounded time.

Scheduling latency can include:

For hard real-time guarantees, every relevant delay needs a defensible upper bound.

A fast timer is not enough. The timer can announce that a job is ready, but the CPU must reach a point where the kernel can safely dispatch it.

Resource sharing can add blocking even when CPU priorities are correct. The important fact here is that this blocking must be included in response-time analysis rather than silently assumed to be zero.

A periodic event may be intended to release exactly every 10 milliseconds:

Variation in release time is release jitter.

Even with exact releases, completion can vary:

Variation in release-to-finish time is response jitter.

Some systems care about jitter even when every deadline is met. Audio samples, control loops, and network transmission schedules can behave poorly when timing varies substantially.

A complete requirement should state both the deadline and any acceptable jitter.

With several CPUs, real-time tasks can be organized in two broad ways.

Partitioned scheduling

Each task is assigned to one CPU, and each CPU is analyzed separately:

Partitioning reduces migration and makes each CPU resemble a uniprocessor problem. A poor partition can leave one CPU overloaded while another has unused capacity.

Global scheduling

Released jobs share a system-wide scheduling population and may migrate:

Global placement can use capacity more flexibly, but analysis and migration behavior become more complex.

A total utilization no greater than the number of CPUs is necessary, but it is not by itself a complete multiprocessor schedulability test. Individual jobs cannot execute on two CPUs simultaneously, deadlines may be shorter than periods, and interference depends on the scheduling model.

Backend services commonly use the word deadline for request timeouts:

A request arrives and its time is consumed by application work, network calls, storage waits, and queueing before the request deadline arrives.

This is an end-to-end deadline, not only a CPU-scheduling deadline.

Giving a request-handling thread stronger CPU priority cannot guarantee the request deadline if the database, network, lock acquisition, or downstream service has unbounded delay.

Real-time reasoning is still useful. The end-to-end budget can be decomposed:

Every component needs a compatible bound before the whole request can have one.

The following C program requests a wakeup every 10 milliseconds using an absolute monotonic-clock schedule. Absolute targets prevent processing time in one iteration from shifting every later target.

The program measures how late it actually resumes after each target:

Save it as periodic-latency.c and compile:

Run it several times:

The exact result depends on the machine, virtualization, power management, kernel, and current workload.

On a Linux test machine, choose one CPU allowed to the shell:

The commands below use CPU 0; replace it if necessary.

Start two CPU-bound competitors on that CPU:

Install cleanup:

Run the measurement on the same CPU:

Then stop the competitors:

Compare the distribution across repeated unloaded and loaded runs. Do not expect one exact number.

The program measures timer and scheduling wakeup lateness under ordinary system conditions. It does not establish a worst-case bound and does not prove real-time schedulability. A successful 200-sample run only says that no worse delay was observed in those samples.

Do not experiment casually with privileged real-time scheduling policies on a shared machine. A runaway high-priority CPU loop can prevent ordinary tasks—including the shell used to stop it—from running.

A relative sleep loop can drift:

Its starts move toward:

The program instead targets:

If one wakeup is late, the next target remains anchored to the original monotonic timeline rather than shifting permanently.

CLOCK_MONOTONIC is appropriate for elapsed intervals because it does not jump when the administrator changes wall-clock time.

The measured lateness includes the fact that timer expiration only makes the thread eligible to resume. The CPU may still be executing other work before the scheduler dispatches it.

Real-time scheduling treats timing as part of correctness. Each job has a release, bounded execution demand, and deadline; hard, firm, and soft systems differ in the consequence of a miss.

Rate Monotonic assigns fixed priority by period, while Earliest Deadline First dynamically selects the job with the earliest absolute deadline. Their schedulability results depend on explicit assumptions about execution bounds, arrivals, preemption, blocking, overhead, and CPU count.

Utilization tests and response-time analysis support admission control, but measurements alone do not prove worst-case guarantees. A complete real-time design must bound every source of delay and define safe behavior when workloads exceed their declared budgets.