Skip to content
TheChatArchiveThe Chat Archive
Grok 4.1 Fast· xaiHugging Face Frontier Reasoning Traces

Draft a resilient scheduler: priority queues, starvation prevention, locks, and delayed…

  1. User

    Draft a resilient scheduler: priority queues, starvation prevention, locks, and delayed jobs.

  2. Assistant
    import heapq
    import threading
    import time
    import collections
    from dataclasses import dataclass
    from typing import Callable, Any, Optional
    
    @dataclass
    class Job:
        id: int
        func: Callable[[Optional[Any]], Any]
        priority: int
        delay: float
        data: Optional[Any] = None
        retries: int = 0
        max_retries: int = 3
        enqueue_time: float = 0.0
    
    class ResilientScheduler:
        def __init__(self, num_priorities: int = 10, age_factor: float = 0.1):
            """
            Resilient scheduler with:
            - Priority queues (bucketed for efficiency)
            - Starvation prevention (aging via wait-time boost on queue heads)
            - Thread-safe (locks)
            - Delayed jobs (min-heap by wakeup time, ties by priority)
            - Automatic retries with exponential backoff on failure
            """
            self.NUM_PRIORITIES = num_priorities
            self.age_factor = age_factor
            self.lock = threading.Lock()
            self.delayed_heap: list[tuple[float, int, int, Job]] = []  # (wakeup_time, -priority, job_id, job)
            self.ready_queues: list[collections.deque[Job]] = [collections.deque() for _ in range(num_priorities)]
            self.job_counter = 0
            self.workers: list[threading.Thread] = []
            self.running = False
    
        def schedule(self, func: Callable[[Optional[Any]], Any], priority: int = 1, delay: float = 0.0,
                     data: Optional[Any] = None, max_retries: int = 3) -> int:
            """
            Schedule a job.
            :param func: Function to execute: func(data)
            :param priority: 0 to NUM_PRIORITIES-1 (higher = higher priority)
            :param delay: Delay in seconds before eligible
            :param data: Data passed to func
            :param max_retries: Max retries on failure
            :return: Job ID
            """
            priority = min(max(priority, 0), self.NUM_PRIORITIES - 1)
            with self.lock:
                self.job_counter += 1
                wakeup_time = time.time() + delay
                job = Job(self.job_counter, func, priority, delay, data, 0, max_retries)
                heapq.heappush(self.delayed_heap, (wakeup_time, -priority, self.job_counter, job))
                return self.job_counter
    
        def _promote_ready(self, now: float) -> None:
            """Promote delayed jobs that are ready to ready_queues."""
            while self.delayed_heap and self.delayed_heap[0][0] <= now:
                wakeup, neg_prio, jid, job = heapq.heappop(self.delayed_heap)
                job.enqueue_time = now
                prio = min(max(job.priority, 0), self.NUM_PRIORITIES - 1)
                self.ready_queues[prio].append(job)
    
        def _select_and_pop_best(self, now: float) -> Optional[Job]:
            """Select and pop the best job based on priority + aging (starvation prevention)."""
            best_score = float('-inf')
            best_p = -1
            for p in range(self.NUM_PRIORITIES):
                q = self.ready_queues[p]
                if q:
                    head_job = q[0]
                    wait_time = now - head_job.enqueue_time
                    score = p + (self.age_factor * wait_time)
                    if score > best_score:
                        best_score = score
                        best_p = p
            if best_p >= 0:
                return self.ready_queues[best_p].popleft()
            return None
    
        def pop_next_job(self) -> Optional[Job]:
            """Atomically pop the next ready job (promote + select)."""
            with self.lock:
                now = time.time()
                self._promote_ready(now)
                return self._select_and_pop_best(now)
    
        def _execute_job(self, job: Job) -> None:
            """Execute job, handle retries on failure."""
            try:
                job.func(job.data)
                # Success: job discarded
            except Exception as e:
                print(f"Job {job.id} (retry {job.retries + 1}/{job.max_retries}) failed: {e}")
                job.retries += 1
                if job.retries < job.max_retries:
                    # Exponential backoff: 0.1s, 0.2s, 0.4s, ..., capped at 60s
                    backoff = min(2 ** job.retries * 0.1, 60.0)
                    with self.lock:
                        wakeup = time.time() + backoff
                        prio = min(max(job.priority, 0), self.NUM_PRIORITIES - 1)
                        heapq.heappush(self.delayed_heap, (wakeup, -prio, job.id, job))
                else:
                    print(f"Job {job.id} exceeded max retries, discarded.")
    
        def _worker_loop(self) -> None:
            """Worker thread loop."""
            while self.running:
                job = self.pop_next_job()
                if job:
                    self._execute_job(job)
                else:
                    time.sleep(0.01)  # Short sleep to avoid busy-wait
    
        def start(self, num_workers: int = 4) -> None:
            """Start the scheduler with worker threads."""
            if self.running:
                return
            self.running = True
            for _ in range(num_workers):
                t = threading.Thread(target=self._worker_loop, daemon=True)
                t.start()
                self.workers.append(t)
    
        def stop(self, timeout: float = 5.0) -> None:
            """Stop the scheduler gracefully."""
            self.running = False
            for w in self.workers:
                w.join(timeout=timeout)
            self.workers.clear()
    
        def __len__(self) -> int:
            """Number of pending jobs (delayed + ready)."""
            with self.lock:
                return len(self.delayed_heap) + sum(len(q) for q in self.ready_queues)
    
    
    # Example usage
    if __name__ == "__main__":
        def high_prio_job(data):
            print(f"HIGH prio: {data} at {time.time():.1f}")
    
        def low_prio_job(data):
            print(f"LOW prio: {data} at {time.time():.1f}")
    
        def failing_job(data):
            if data["attempt"] < 2:
                raise ValueError("Failing for retry")
            print(f"SUCCESS after retries: {data}")
    
        sched = ResilientScheduler(num_priorities=5, age_factor=0.2)  # Boost by 1 prio every 5s
        sched.start(num_workers=2)
    
        # Schedule jobs
        sched.schedule(high_prio_job, priority=4, delay=1, data="URGENT!")
        sched.schedule(low_prio_job, priority=0, delay=0.5, data="Background")
        sched.schedule(lambda d: failing_job({"attempt": d}), priority=2, delay=0, data=0)
    
        time.sleep(10)  # Let jobs run
        print(f"Pending jobs: {len(sched)}")
        sched.stop()
    

    This draft provides a fully functional, thread-safe scheduler:

    • Priority queues: Fixed buckets (scalable to 10s of priorities) for ready jobs.
    • Starvation prevention: When selecting, computes score = priority + age_factor * wait_time on each queue's head and picks the max (O(num_priorities) = O(1)).
    • Locks: Single threading.Lock() protects all shared state.
    • Delayed jobs: Min-heap ordered by (wakeup_time, -priority, job_id) for efficient promotion.
    • Resilience: Workers daemonized; jobs retried w/ exponential backoff (re-inserted to delayed); failures logged but don't crash scheduler; graceful stop.

    Performance notes: Handles 1000s of jobs fine (heap O(log N), selection O(1)). For millions, consider Redis or DB persistence. Aging favors fairness without heap invalidation hacks.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.