DAG Pipeline Scheduler (Rust)
Topics: graphs, topological sort, concurrency, worker pool
Problem
A CI/build pipeline is a DAG of tasks: each task may start only once everything it depends on has
finished. Run the whole graph concurrently but with a cap on how many tasks execute at once.
pub enum ScheduleError { Cycle(Vec<String>), Task(String) }
pub fn schedule<F>(deps: &BTreeMap<String, Vec<String>>, workers: usize, run: F)
-> Result<(), ScheduleError>
where F: Fn(&str) -> Result<(), String> + Sync;
deps maps a task to the tasks it depends on (a dependency that isn't itself a key is a leaf
task). Run every task exactly once.- A task runs only after all of its dependencies have finished.
- At most
workers tasks run concurrently.
- If any
run returns an error, stop starting new tasks and return Task(err) once in-flight
tasks finish.
- If
deps has a cycle, run nothing and return Cycle(tasks) where tasks are the tasks that
could never become ready, sorted.
{web:[api], api:[db], db:[]}, workers=2 → db, then api, then web
{a:[b], b:[a]} → Err(Cycle(["a","b"])) (nothing runs)
This is Kahn's algorithm wearing a thread pool: a task is ready when its in-degree reaches
zero, workers pull ready tasks, and finishing one decrements its dependents. thread::scope lets
the workers borrow the shared state directly; a Condvar parks idle workers until new work appears
or the graph drains.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.