Comments
Hacker News
I think everyone learns these lessons the hard way. I know I did.
The difficulty of designing robust schedulers in real systems comes from the confluence of two properties: a theoretically optimal schedule guarantees no bound on task latency and runtime scheduling is AI-complete.
In practice, we need latencies to be bounded, often tightly. The scheduler implementation must operate within a limited memory and compute budget, which is not a property of anything that requires "AI-complete" algorithms -- best you can do is extremely narrow and very loose approximations.
Because of these constraints, any general purpose scheduler will be brittle or have poor efficiency (typically both). At the same time, designing a bespoke implementation-specific scheduler is exceedingly non-trivial for all but the simplest applications. Closest simple examples with literature are cache replacement algorithms, which are a very narrow case of scheduling where unbounded latency is not a problem.
Solving these kinds of design problems has historically fallen under the rubric of "latency-hiding" (e.g. in HPC). There is vanishingly little literature for software and hardware has many constraints and properties that don't apply to software.
Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- I think everyone learns these lessons the hard way. I know I did.
The difficulty of designing robust schedulers in real systems comes from the confluence of two properties: a theoretically optimal schedule guarantees no bound on task latency and runtime scheduling is AI-complete.
In practice, we need latencies to be bounded, often tightly. The scheduler implementation must operate within a limited memory and compute budget, which is not a property of anything that requires "AI-complete" algorithms -- best you can do is extremely narrow and very loose approximations.
Because of these constraints, any general purpose scheduler will be brittle or have poor efficiency (typically both). At the same time, designing a bespoke implementation-specific scheduler is exceedingly non-trivial for all but the simplest applications. Closest simple examples with literature are cache replacement algorithms, which are a very narrow case of scheduling where unbounded latency is not a problem.
Solving these kinds of design problems has historically fallen under the rubric of "latency-hiding" (e.g. in HPC). There is vanishingly little literature for software and hardware has many constraints and properties that don't apply to software.