Grok 4.1 Fast· xai
Frontier Reasoning Traces
Draft a resilient scheduler: priority queues, starvation prevention, locks, and delayed…
- User
Draft a resilient scheduler: priority queues, starvation prevention, locks, and delayed jobs.
- 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_timeon 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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.