Workload Schedulers -- Genesis, Algorithms and Differences

• The paper covers process schedulers.Source: TYPE OF PAPER AND KEYWORDS · p. 1
• The paper covers job schedulers.Source: TYPE OF PAPER AND KEYWORDS · p. 1
• The paper covers scheduling algorithms.Source: TYPE OF PAPER AND KEYWORDS · p. 1

1 INTRODUCTION

• Scheduling research allocates available resources to optimize one or more performance measures.Source: §1 · p. 1
• Simple strategies are popular for online requests because they need not know unscheduled or currently running jobs, but ignoring system conditions may reduce utilization and raise costs.Source: §1 · p. 1
• More complex methods can use static infrastructure data, but may omit running jobs; fixed-priority scheduling can indefinitely block lower-priority tasks, while aging raises their priority over time.Source: §1 · pp. 1–2
• The introduction traces networked computing research to metacomputing, a term established in 1987.Source: §1 · p. 2
• Distributed scheduling differs because geographically separated machines make data transfer costly, and load balancers also handle fault tolerance and user sessions.Source: §1 · p. 2
• Approximation methods are used because optimal scheduling across parallel nodes is difficult within fixed time; cited worst-case guarantee ratios are 19/12 for an LPT variant and 13/11 for first-fit decreasing.Source: §1 · p. 2
• The paper analyzes selected past and current schedulers to trace how scheduling algorithms and concepts developed, rather than surveying every available scheduler.Source: §1 · p. 2
• The paper compares scheduler classes and proposes a novel categorization of modern workload schedulers, with a possible unification of future designs.Source: §1 · p. 2

2.1 Cooperative Scheduling

• Cooperative scheduling relies on applications voluntarily yielding CPU time, so a process that monopolizes the CPU can make the system hang.Windows 95 added rudimentary preemption only for 32-bit applications.Source: §2.1 · pp. 2–3

2.2 Multi-Level Feedback Queue

• MLFQ promotes jobs that exceed their queue’s time allotment, favoring short processes, though it performs poorly in the worst case.The section describes MLFQ as widely implemented across operating systems.Source: §2.2 · p. 3

2.3 O(n) Scheduler

• The O(n) scheduler assigns epoch-based time slices using static priority and some unused time from the prior epoch, but scales poorly as each event scans planned processes.Source: §2.3 · p. 3

2.4 O(1) Scheduler

• The O(1) scheduler runs in constant time regardless of process count, but complex sleep-time heuristics can misclassify interactive processes [81][51][65].Source: §2.4 · p. 3

2.5 Completely Fair Scheduler

• CFS aims to share processor time fairly, using a red-black tree keyed by spent processor time and prioritizing processes with more sleeping time [65].Source: §2.5 · p. 3

2.6 Brain Fuck Scheduler

• BFS lowers latency but raises process turnaround time compared with CFS, trading interactivity against performance.It was designed for desktop machines with fewer CPU cores and does not require heuristic adjustments or tuning parameters.Source: §2.6 · p. 3

3 CLUSTER SYSTEMS JOBS SCHEDULERS

• Cluster schedulers must handle varying workloads, complex policies and fairness, growing clusters, mixed jobs and services, heterogeneous resources, and hardware or node-performance problems [23][47][13][76][31].Source: §3 · p. 4

3.1 Simple Linux Utility for Resource Management

• SLURM uses best-fit scheduling based on Hilbert curves or fat-tree topology and can scale to thousands of processors.The paper reports that approximately half of the world’s supercomputers use SLURM as workload manager.Source: §3.1 · p. 4

3.2 Maui Cluster Scheduler

• Maui combines FCFS with advance reservations, backfilling, and fair-share policies [25].Source: §3.2 · p. 4

3.3 Moab High-Performance Computing Suite

• Moab extends Maui with triggers, configurable policies, administration tools, a web portal, and reported scalability beyond 15,000 nodes [77] (Young, 2014).The paper also reports hundreds of thousands of queued submissions and over 500 users.Source: §3.3 · p. 4

3.4 Univa Grid Engine

• Univa Grid Engine supports reservations, checkpointing, Hadoop and EC2 integration, and default FCFS or optional Equal-Share scheduling, with additional strategies available [79].The text also notes that the product’s source-code release history led to multiple open-source forks.Source: §3.4 · p. 4

3.5 LoadLeveler

• LoadLeveler supports FCFS, backfilling, and gang scheduling, allows administrators to replace SYSPRIO, and can checkpoint jobs or communicate with Maui [23][53].Source: §3.5 · pp. 4–5

3.6 Load Sharing Facility

• LSF supports FCFS, fair-share, backfilling, and SLA scheduling; its priority-escalation feature raises priorities over time for long-waiting jobs.Source: §3.6 · p. 5

3.7 Portable Batch System

• PBS offers FCFS, SJF, fair-share, and custom schedulers, with SJF as the default and a starvation rule that pauses other jobs until a marked job finishes [8][23].The paper distinguishes OpenPBS, TORQUE, and commercial PBS Professional.Source: §3.7 · p. 5

3.8 Globus toolkit

• Globus uses DUROC to divide a job into subjobs and GRAM to negotiate resources through local managers before starting the job.Co-allocation across grids may improve performance when communication overhead is low [22].Source: §3.8 · p. 5
• DUROC provides no job queue, so submissions fail when resources are not immediately available or cannot be negotiated, and one task failure fails the whole job.Source: §3.8 · p. 5

3.9 GridWay

• GridWay’s submission agent combines a resource selector that ranks hosts with a performance evaluator that can request migration after detecting slowdown.Jobs can update requirements during execution, and the scheduler weighs potential migration benefits against migration overhead.Source: §3.9 · p. 6
• GridWay’s self-adapting behavior requires modifying the application’s source code.Source: §3.9 · p. 6

3.10 HTCondor

• HTCondor began as a 1984 cycle-scavenging project and retained a largely stable architecture while adding features and expanding its node pool.It can now manage cluster workloads.Source: §3.10 · p. 6
• DAGMan orchestrates jobs according to graph dependencies, then submits them to HTCondor, which assigns them to available machines.Users also receive fair-share machine time by priority, with FIFO personal queues and priority pre-emption.Source: §3.10 · p. 6

3.11 Mesos

• Mesos uses a master to offer resources to independent frameworks, which choose whether to accept offers and which tasks to run.ZooKeeper elects a replacement master after failure.Source: §3.11 · p. 6
• Mesos works best with small, short-lived tasks and frequent resource release; serialized offer decisions can let a slow scheduler impair system performance.Only one framework can examine an offer at a time in the described design.Source: §3.11 · p. 6

3.12 Open MPI

• Open MPI assigns processes by slot or node using round robin, subject to node suitability and configured slot policies.Its runtime supports multiple communication channels and can handle network-device failures when a node has several devices.Source: §3.12 · pp. 6–7

3.13 Autopilot

• Autopilot automates data-centre provisioning, deployment, monitoring, and hardware lifecycle operations, while applications retain control of job-placement policies.Its stated aim is to reduce around-the-clock staffing needs and capital expense.Source: §3.13 · p. 7

3.14 TORQUE

• TORQUE uses a master server and node daemons, with a default FIFO scheduler that allocates nodes under configured resource policies.Users can select an alternative scheduler such as Maui or Moab.Source: §3.14 · p. 7
• Initial experiments with TORQUE’s planning-based extension show promising results compared with various backfilling strategies.The extension periodically improves schedules using Tabu Search, optimizing metrics such as makespan, slowdown, response time, or wait time.Source: §3.14 · p. 7

3.15 Borg and Omega

• Borg used one centralized scheduling algorithm for all jobs, whereas Omega deploys several schedulers in parallel against shared resource state.In Omega, conflicting allocations return affected jobs to the queue for another scheduling attempt.Source: §3.15 · pp. 7–8
• Omega eliminates head-of-line job blocking and offers better scalability, with scalability benefits often outweighing the added resource-collision computation costs.The study reports that scalability targets were achieved.Source: §3.15 · p. 8
• Google users overestimated requested memory in over 90% of cases, sometimes wasting close to 98% of requested resources.The passage attributes overestimation to preventing jobs from being killed for exceeding allocated memory.Source: §3.15 · p. 8

4 BIG DATA SCHEDULERS

• Big-data processing requires parallel software on large server farms, and its workload and cluster-utilization challenges motivate specialized frameworks.The section introduces frameworks including Dryad, MapReduce, Hadoop, HaLoop, Spark, and CIEL.Source: §4 · p. 8, §4.1 · p. 8, §4.2 · p. 9

4 BIG DATA SCHEDULERS; 4.1 Dryad; 4.6 CIEL

• Dryad represents applications as dataflow graphs whose vertices can be re-executed after failures, while Big Data frameworks commonly co-locate processing with stored data.Big-data systems often specialize in a limited set of problems; CIEL uses a master-worker execution model and its own Skywriting language.Source: §4.1 · p. 8, §4 · p. 8, §4.6 · p. 11

4.2 MapReduce

• MapReduce’s key contributions are scalability and fine-grained fault tolerance, with parallel map work feeding a reduce operation over gathered values.The reduce iterator can process a list too large to fit in machine memory.Source: §4.2 · p. 9

4.3 Hadoop

• Hadoop places map tasks near input data and runs speculative backup tasks to mitigate stragglers; Google estimated backup tasks can improve job response times by 44%.Placement preference proceeds from the same node to the same rack, then a remote rack.Source: §4.3 · p. 9

4.3.1 FIFO scheduler

• Hadoop’s early FIFO scheduler could delay low-priority jobs indefinitely, while a long-running low-priority job could block a later high-priority job because pre-emption was unsupported.Source: §4.3.1 · p. 9

4.3.2 Fair Scheduler; 4.3.3 Capacity Scheduler

• Fair Scheduler allocates user pools a max-min fair share with minimum capacities and pre-emption, while Capacity Scheduler organizes capacity among potentially hierarchical FIFO queues.Fair Scheduler can let idle pools’ slots be used by other pools; Capacity Scheduler’s queue sharing resembles pool sharing.Source: §4.3.2 · p. 10, §4.3.3 · p. 10

4.4 HaLoop

• HaLoop reduces query runtimes by 1.85 and shuffles only 4% of data between mappers and reducers.It adds caching and loop-aware optimizations for iterative jobs.Source: §4.4 · p. 10

4.5 Spark

• Spark outperforms Hadoop by an order of magnitude for iterative machine-learning and interactive-data-analysis applications while retaining MapReduce scalability and fault tolerance.On Facebook workload traces, cluster throughput might increase by up to two times; delayed scheduling also seeks locality with minimal fairness impact.Source: §4.5 · pp. 10–11

5 SUMMARY

• Operating-system process schedulers evolved to maximize responsiveness while maintaining performance, with modern algorithms designed for low overhead.They generally expose few configuration parameters because most end users are non-technical; multicore processors encouraged development toward parallel execution.Source: §5 · p. 11
• Modern operating-system schedulers also use cache locality when assigning tasks to CPU cores.The passage connects this development to the popularization of multicore processors.Source: §5 · p. 12
• Cluster job schedulers balance proportional resource sharing and stable throughput, while supporting fault tolerance and sometimes minimizing power consumption.First-Come-First-Served with backfilling is described as the most popular approach; growing cluster size has prompted research into parallel scheduling models such as Omega.Source: §5 · p. 12
• Big Data schedulers inherit cluster-scheduler designs but specialize frameworks to run tasks near where their input data is stored.Big Data nodes both store distributed file-system data and provide a parallel execution environment.Source: §5 · p. 12

6 CONCLUSIONS

• Scheduling strategies across operating-system, cluster, and distributed systems share similarities, with multicore processors shifting operating-system design toward parallel execution resembling cluster schedulers.Earlier operating-system schedulers focused primarily on responsiveness and performance.Source: §6 · p. 12
• Experiments with CIEL show that distributed-node task-allocation strategies can be adapted to the operating-system level, while Linux’s Completely Fair Scheduler reflects mixing local and distributed-system concepts.The paper identifies the Completely Fair Scheduler as based on a fairness model.Source: §6 · p. 12
• The paper expects research across scheduler classes to become more joined, combining operating-system and distributed-cluster design ideas.It contrasts this direction with earlier circular-queue approaches and notes modern strategies such as parallel competing schedulers, fairness, checkpointing, and backup tasks.Source: §6 · p. 12