Overcoming the Zero Cost Preemption Assumption in Scheduling

87 concepts72 papers1 proposal

In theoretical computer science and scheduling theory, mathematical proofs often rely on a highly convenient fiction: the zero-cost preemption assumption. This assumption states that a running task can be paused, resumed, or migrated to another processor instantaneously and without consuming any computational resources. Classic algorithms like Shortest Remaining Processing Time (SRPT) or anytime computation derive elegant performance bounds under this premise.

However, when these algorithms meet physical hardware, the fiction crumbles. In reality, every interruption costs time, energy, and synchronization overhead. A growing body of research focuses on exposing, modeling, and mitigating these hidden costs to bridge the gap between mathematical proofs and real-world system performance.

The Physical Reality of Interruption

Why does preemption cost so much? In physical systems, a task is not an abstract mathematical entity; it is a collection of states distributed across registers, caches, and main memory.

State Preservation and Memory Latency

To pause a task, its current state must be saved so it can be restored later. As Dean et al. noted in their foundational work on anytime algorithms, ignoring context-switching costs significantly degrades performance when deliberation time is limited.

In modern workloads like AI inference, this state isn't just a few CPU registers. It involves swapping massive neural network weights into limited on-chip memory, converting context switching into a dominant component of total service latency (Liang et al.). Similarly, in distributed high-performance computing or cloud environments, preemption requires checkpointing or state serialization, introducing non-negligible delays that can invalidate theoretical latency gains (Scully et al., Grosof et al.).

Migration and Locality Loss

Multi-processor and cloud scheduling algorithms frequently assume that tasks can freely hop between machines or cores to balance workloads (Fox et al., Schwiegelshohn et al.). But moving a thread destroys cache locality and triggers memory bus arbitration delays (Vaze et al., Megow).

Ahmad demonstrated early on that failing to treat data fetch and storage as explicit, costly tasks leads to broken schedules in real-time systems. On modern heterogeneous architectures (such as Arm's big.LITTLE), thread migration incurs significant performance penalties that can completely invalidate timing guarantees if left unmodeled (Sun et al.).

[Zero-Cost Model]  Task A ───► (Pause) ───► Task B Starts (Instant)
                                  │
[Physical Reality] Task A ───► [Save State / Cache Flush] ───► [Load Weights / Context Switch] ───► Task B Starts
                               └─────────────── Preemption Overhead ─────────────────────────┘

The Paradox of Algorithmic Overhead

Sometimes, the scheduling mechanism itself introduces more overhead than the optimization saves. To implement "optimal" scheduling policies, systems must track task priorities or clean up redundant processes, creating a secondary layer of hidden costs.

Priority Queue Contention

Algorithms that continuously re-evaluate task order to accelerate the critical path often rely on concurrent priority queues. However, Whang et al. and Utkoor et al. show that the synchronization and rebalancing overhead of maintaining these queues in multi-core systems can easily exceed the performance benefits. In high-concurrency environments, simpler FIFO queues with work-stealing often outperform complex priority-driven mechanisms because they reduce management latency and lock contention.

The Cost of Housekeeping

In distributed systems using task replication to mitigate slow "straggler" servers, theoretical models assume that redundant tasks can be canceled instantly across a network. In practice, network latency and process termination protocols mean that cancellation itself consumes critical system resources, causing delays that simplified scheduling frameworks ignore (Koole et al., Badita et al.).

Bridging the Gap: Realistic Overhead Modeling

To make scheduling theory useful for physical deployments, researchers are moving away from zero-cost assumptions and directly embedding overhead into mathematical models and hardware designs.

  • Explicit Overhead Integration: Instead of treating context switches as negligible, modern frameworks integrate mode-aware overhead penalties and task buffers directly into response time analyses (Rouzot et al., Ali et al.). This ensures that the transition between execution states accounts for the mandatory work required to maintain safety guarantees.
  • Hardware-Assisted Scheduling: To bypass the heavy computational cycle tax of running scheduling logic within operating system software, systems like the Swarm Processor System offload workload selection directly to dedicated hardware modules (Jeong et al., Caccamo et al.).

By treating preemption, migration, and queue maintenance as physical operations with discrete time and energy costs, the community is developing scheduling policies that remain robust when deployed on actual hardware.

Key Foundational Work

Robot Control Computation in Microprocessor systems with Multiple Arithmetic Processors (1987) — contributed 2 concept elements to this direction.
An Analysis of Time-Dependent Planning (1988) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 68 papers
  2. Version 1 · 2026-10-04 · 71 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_zero_cost_preemption_assumption_f4993347,
  title = {zero-cost preemption assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zero-cost-preemption-assumption/rdr_f499334772b94761b4cbef41548076fb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_zero_cost_preemption_assumption_f4993347_v2,
  title = {zero-cost preemption assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zero-cost-preemption-assumption/rdr_f499334772b94761b4cbef41548076fb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake