[jandrewrogers]

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.

[cidd]

First time I heard about "AI-complete" and you mentioned it twice here.

[jandrewrogers]

The concept has not always had this name, that is more recent branding. ~25 years ago it was formalized by a proof that optimal generalized learning is a universal sequence prediction problem. An unfortunate property of universal sequence prediction problems is that they are profoundly intractable and we really don't have a good idea of how to reduce these problems to a tractable approximation on real hardware.

Many basic concepts in computer science are in this class: data compression (see: the Hutter Prize), indexing (see: "learned indexing"), cache replacement algorithms (see: Bélády optimality theorem), etc. We narrowly specialize these algorithms such that they look very different to be computationally feasible but at the limit they are the same algorithm problem.

I find it interesting that database engines are essentially a giant bucket of algorithms all in this class.

[hamstergene]

Same, and it led me discover there was already a wikipedia article about it: https://en.wikipedia.org/wiki/AI-complete

[xyzsparetimexyz]

Shouldn't it just be I-complete? Humans can obviously solve these tasks too