Fragmentation Aware Resource Allocation and Scheduling

47 concepts33 papers1 proposal

When allocating computational resources—whether they are CPU cores in a cloud cluster, channels in a wireless spectrum, or disk access pipelines—schedulers face a silent efficiency killer: resource fragmentation.

Fragmentation occurs when continuous or multi-dimensional resources are allocated and freed dynamically, leaving behind isolated "gaps" of idle capacity. While the total amount of idle resources across a system might be large, these resources are often stranded in fragments too small or structurally mismatched to satisfy incoming requests.

To solve this, modern scheduling paradigms move away from naive first-come, first-served approaches. Instead, they use fragmentation-aware scheduling, a family of strategies that combine geometric resource packing with size-based job prioritization to maximize throughput and minimize latency.

The Cost of Stranded Capacity

To understand why fragmentation-aware scheduling works, we must first understand how uncoordinated allocations strand resources. In a heterogeneous cloud data center, jobs require specific ratios of multiple resources (e.g., 2 CPUs for every 10 GB of RAM). If a scheduler assigns jobs to servers without considering these ratios, it risks exhausting one resource type while leaving the other completely unusable.

Wei Wang et al. address this in Dominant Resource Fairness in Cloud Computing Systems with Heterogeneous Servers by aligning the specific resource demand ratios of incoming jobs with the available resource profiles of specific servers. By matching complementary workloads, the system prevents a situation where memory-heavy jobs strand CPU capacity, or vice-versa.

When fragmentation becomes severe, the entire scheduling perspective must adapt. As Peng Si Ow et al. observe in Reactive Plan Revision, effective schedulers must dynamically switch between an order-centric perspective (focusing on individual job deadlines) and a resource-centric perspective (focusing on packing efficiency). When fragmentation is high, a resource-centric approach becomes essential to aggregate scattered capacity and maintain system throughput.

The Geometry of Resource Packing

The most intuitive way to mitigate fragmentation is to control the geometry of how gaps are filled. If a scheduler fills resource gaps haphazardly, it slices the remaining capacity into progressively smaller, unusable pieces.

Two primary strategies prevent this decay: Largest-First Allocation and Resource Concentration.

Largest-First Allocation

Counterintuitively, the best way to preserve usable space for small tasks is to force large tasks into the largest available gaps first. In a series of theoretical and empirical studies on dynamic spectrum access, including Channel fragmentation in dynamic spectrum access systems, Ed Coffman et al. (and similarly Edward G. Coffman Jr. et al. in Channel Fragmentation in Dynamic Spectrum Access Systems - a Theoretical Study) analyzed the "Largest-First Scan" (LFS) algorithm.

By scanning available resource gaps and prioritizing the largest segments for new allocations, LFS drastically reduces the total number of fragments per channel compared to linear or circular scanning. Filling the largest blocks first ensures that the remaining unallocated capacity stays consolidated, maximizing the probability that future, complex requests can be fulfilled.

Resource Concentration

Rather than spreading workloads evenly across an entire cluster, schedulers can concentrate resources on a minimal subset of active applications. Francesco Pace et al. demonstrate this in Flexible Scheduling of Distributed Analytic Applications through their system, Zoe.

By isolating and concentrating resources on the core components of a few applications rather than distributing them broadly, individual jobs finish much faster. This accelerated completion clears the scheduling queue rapidly, returning large, contiguous blocks of resources back to the system and keeping the overall cluster healthy.

Marrying Packing with Size-Based Prioritization

While packing resources efficiently keeps utilization high, it introduces a classic scheduling conflict: maximizing raw utilization can lead to terrible latency for individual jobs. In single-resource theory, minimizing average response time requires Shortest Remaining Processing Time (SRPT) or Shortest Job First (SJF) scheduling, as explored by Kyle Fox et al. in Online Scheduling on Identical Machines using SRPT, Do Bao Son et al. in EVOLUTIONARY ALGORITHM FOR TASK OFFLOADING IN VEHICULAR FOG COMPUTING, and Chang Liu in Disk scheduling policies with lookahead.

How do we simultaneously optimize for geometric packing (to avoid fragmentation) and job size (to minimize latency)?

ServerFilling-SRPT

Isaac Grosof et al. solved this open problem in Optimal Scheduling in the Multiserver-job Model under Heavy Traffic. They introduced a policy that first selects a pool of the shortest available jobs (satisfying the SRPT condition for latency) but places them into service by prioritizing those with the largest individual resource requirements.

By packing the resource-heavy jobs from the short-job pool first, the system prevents large resource blocks from being fragmented by tiny tasks. This dual-layered approach allows multi-server systems to remain stable under heavy traffic loads where traditional greedy heuristics fail.

Maximize Departure Frequency

Prioritizing smaller resource footprints can also act as a defense mechanism against system bloat. As Rahul Vaze argues in Scheduling Multi-Server Jobs is Not Easy, prioritizing jobs with smaller resource requirements maximizes the frequency of job departures. Clearing numerous small tasks quickly prevents the accumulation of total system flow time, ensuring that large, resource-heavy jobs do not block the entire system and cause widespread queue stagnation.

Backfilling

When large jobs must wait for a massive contiguous block of resources to clear, they inevitably create temporary, idle fragments around them. Schedulers use backfilling to exploit these temporary gaps.

As detailed by Zhen Li 0009 et al. in Bandwidth-Guaranteed Resource Allocation and Scheduling for Parallel Jobs in Cloud Data Center, a backfilling scheduler allows smaller, shorter waiting jobs to slip into these idle resource fragments while the primary, larger job awaits its full allocation. This ensures that the fragments produce useful work rather than remaining wasted.

Traditional FCFS (Stranded Capacity):
[ Large Job Waiting... (Blocked) ] [ Idle Fragment ] [ Idle Fragment ]

Backfilling Scheduler (Fragmentation-Aware):
[ Large Job Waiting... (Blocked) ] [ Short Job A ]   [ Short Job B ]
                                   └────── Filled Idle Gaps ──────┘

Handling Disruptions and Preemption

In real-world deployments, scheduling is rarely static. Hardware failures, emergency tasks, and data locality constraints constantly disrupt optimized packing plans. Fragmentation-aware scheduling must therefore be reactive.

When hardware failures reduce the available resource pool, queues quickly congest. Cheul-Woo Ro demonstrates in Scheduling Analysis of Failure-aware VM in Cloud System that applying priority-based scheduling to favor tasks with smaller computational requirements effectively clears queue congestion during recovery periods.

If an emergency task arrives and resources are completely packed, the scheduler must resort to preemption. To minimize the chaotic "ripple effects" of breaking an active plan, schedulers use highly targeted preemption rules:

  • Minimizing Discarded Work: Zhiyi Huang et al. show in Online Makespan Minimization: The Power of Restart that when a system must restart or preempt tasks, it should target the running task with the smallest total processing time. This minimizes the absolute volume of discarded computational work, keeping the cost of adaptation low.
  • Resource Stealing Rules: In industrial sensor networks, Changqing Xia et al. (Scheduling for Emergency Tasks in Industrial Wireless Sensor Networks) implement a "stealing mechanism" that acquires resources for emergency tasks by prioritizing flows that have already been preempted or those that offer the most exact fit for the required resource gap, preventing unnecessary widespread disruption.

Finally, schedulers must know when to stop optimizing. In big data workflows, schedulers often delay jobs to wait for data to become local to a specific node. However, Zhao Zhang et al. (Scientific Computing Meets Big Data Technology: An Astronomy Use Case) note that when processing large volumes of small files, the idle time spent waiting for data locality can exceed actual data transfer times. In these scenarios, disabling delay scheduling entirely prevents resource underutilization, proving that fragmentation awareness requires a fine balance between spatial packing efficiency and temporal execution speed.

Key Foundational Work

FPGA Implementation of a Prototype WDM On-Line Scheduler (2000) — contributed 1 concept elements to this direction.
Reactive Plan Revision (1988) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fragmentation_aware_scheduling_c1cb96f6,
  title = {fragmentation-aware scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fragmentation-aware-scheduling/rdr_c1cb96f6d121413b9f9aef556914c169},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_fragmentation_aware_scheduling_c1cb96f6_v1,
  title = {fragmentation-aware scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fragmentation-aware-scheduling/rdr_c1cb96f6d121413b9f9aef556914c169/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake