Yuxu Ge
Article · 2026-02-25

The Cost of Absolute Priority: When "Work Stealing" Meets Hierarchical Scheduling

When building high-throughput task schedulers, the conventional advice is familiar: "Separate critical tasks from background tasks; critical tasks must execute first." The reasoning is sound—no thread handling user requests should be blocked by log compression. This led to a classic pattern: Absolute Priority, where a two-tier design guarantees critical work before any secondary activity begins.

What is Absolute Priority?

In standard task scheduling (such as the Go Runtime or typical thread pools), tasks are treated as peers or with only minor weight differences. However, in extreme scenarios—real-time search, high-frequency trading—systems must deliver not just speed but deterministic speed.

The solution introduces two queue levels:

  1. Major Queue: Stores core path tasks with absolute execution priority.
  2. Minor Task Source Collection: Stores dynamically generated secondary work (background cleanup, log aggregation). Worker threads access these only when the Major Queue is empty.

This is less "scheduling" than "priority-based multiplexing."

Code Reproduction (Go)

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

// Task represents an executable task
type Task func()

// PriorityTaskScheduler demonstrates the two-tier task scheduling logic in industrial systems
// The Major queue has absolute priority, and the Minor queue is processed only when Major is empty
type PriorityTaskScheduler struct {
	major chan Task

	// minors stores dynamically created minor task sources
	// This is a typical "read-heavy, write-light" scenario, suitable for sync.Map
	minors      sync.Map
	minorsCount int64
}

func NewPriorityTaskScheduler(buffer int) *PriorityTaskScheduler {
	return &PriorityTaskScheduler{
		major: make(chan Task, buffer),
	}
}

// PushMajor submits tasks to the high-priority path
func (s *PriorityTaskScheduler) PushMajor(t Task) {
	s.major <- t
}

// NewMinorQueue creates a new low-priority task source
// In the original design, this often corresponds to a temporary subset of tasks or a background job
func (s *PriorityTaskScheduler) NewMinorQueue(buffer int) chan Task {
	minor := make(chan Task, buffer)
	id := atomic.AddInt64(&s.minorsCount, 1)
	s.minors.Store(id, minor)
	return minor
}

// Pop simulates the logic of a worker thread fetching tasks
// Core logic: check Major first, then Minor
func (s *PriorityTaskScheduler) Pop() Task {
	// 1. Absolute priority check: attempt to fetch from the major path
	select {
	case t := <-s.major:
		return t
	default:
		// 2. Only when the major path is empty, scan the minor paths
		// This logic is called "Stealing," but it's essentially a fallback process
		return s.stealFromMinors()
	}
}

func (s *PriorityTaskScheduler) stealFromMinors() Task {
	var found Task

	// Simulate the iteration logic for Minors in the original code
	// If there are many Minor queues, this will become a performance killer
	s.minors.Range(func(key, value interface{}) bool {
		ch, ok := value.(chan Task)
		if !ok {
			return true
		}

		select {
		case t, open := <-ch:
			if !open {
				// Automatic cleanup: if the queue is closed, remove it from the pool
				s.minors.Delete(key)
				return true
			}
			found = t
			return false // Found a task, stop iterating
		default:
			return true // Continue checking the next one
		}
	})

	return found
}

func main() {
	scheduler := NewPriorityTaskScheduler(10)

	// Create a minor task stream
	lowPriority := scheduler.NewMinorQueue(5)

	// Populate tasks
	// Note: Although low-priority tasks are added first, they will be executed later
	lowPriority <- func() { fmt.Println("Executing: Low-priority task (Minor)") }
	scheduler.PushMajor(func() { fmt.Println("Executing: High-priority task (Major)") })

	fmt.Println("Starting scheduler...")

	// Demonstrate consumption order
	for i := 0; i < 2; i++ {
		if t := scheduler.Pop(); t != nil {
			t()
		} else {
			fmt.Println("No tasks available")
		}
	}
}

The select structure in Pop captures the design's essential decision path: check Major first, drain it completely, then examine Minor queues.

Design Trade-offs Analysis

1. Isolation vs. Fairness

The chief advantage is inviolability of the core path. As long as the Major queue holds tasks, worker threads ignore Minor entirely. Under load, this delivers extremely low latency jitter for critical operations.

The cost is severe: starvation. Under continuous high load, Major queue arrivals never cease. Tasks in Minor queues may never execute. In distributed systems, this means background heartbeats, metrics, or garbage collection tasks freeze indefinitely. Nodes then fail health checks and face eviction—despite being resourced and operational.

2. Scanning Overhead

The iteration logic in stealFromMinors reveals a performance risk. When Major is empty, worker threads repeatedly scan the minors list. With 1000 Minor queues in the system (say, one per connection) and most empty, each Pop becomes an $O(N)$ full scan.

This produces CPU cache thrashing. Searching for possibly nonexistent low-priority work incurs numerous invalid memory accesses that flush productive cache lines. In C++ or Rust implementations, designers often resort to lock-free structures (hazard pointers, lock-free linked lists) to reduce contention during scanning. This complexity significantly raises maintenance cost.

3. The Hidden Burden of Dynamic Lifecycles

Note the detail s.minors.Delete(key). In the original design, reference counting automatically removes sub-queues when producers release them.

This "automatic cleanup" reduces cognitive load on business logic but increases scheduler burden. The scheduler must not only dispatch tasks but also monitor the lifecycle of task sources. This violates Single Responsibility, inflating the scheduling core.

When to Use?

Absolute Priority solves a real problem but at steep cost.

Suitable for:

Unsuitable for:

Before adopting this pattern, answer honestly: Can my secondary tasks tolerate indefinite postponement? If not, a weighted round-robin or time-sliced scheduler is the safer choice.

© 2026 Yuxu Ge ·