Build just finished. Which tasks can start now?

transcript

Your build step just finished. Which tasks can start now? Scanning every task is the first mistake on the list.

The slow way: loop over every task and its dependencies. After every finish. Order V times E, again and again. Instead keep two maps. Children: who depends on each task. Unmet: how many of a task's dependencies haven't succeeded. When the count hits zero, it's ready.

Build succeeds. Walk only its children. Test's count: 1 to 0. Into the ready heap. Package: 2 to 1. It still waits for test. Each edge touched once. That's Kahn's topological sort, run live.

But here's the catch. Package's two dependencies finish at once. Both read 2. Both write 1. Package never starts.

So the counts change under the scheduler's lock. Pushing to the ready heap, too. But the task itself runs outside it. Or four workers become one.

Count unmet dependencies. Release a task when its count hits zero. The moment its last dependency succeeds, it starts.

Full breakdown in the lecture.