DAG Pipeline Scheduler (Go)
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.
func Schedule(deps map[string][]string, workers int, run func(task string) error) error
type CycleError struct { Tasks []string }
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 that first error once
in-flight tasks finish.
- If
deps has a cycle, run nothing and return a *CycleError whose 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]} → *CycleError{Tasks:[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 — possibly making them
ready. A sync.Cond lets idle workers sleep until new work appears or the graph drains.
Run
go test -v ./challenges/dag-scheduler/go/
Sign in to submit your solution.