long term scheduling

Posted Aug 6, 2004 3:05 UTC (Fri) by giraffedata (guest, #1954)
Parent article: Token-based thrashing control

Much older operating systems do a similar thing, but simpler, called long term scheduling. Above the regular CPU dispatch queue, you have a list of processes waiting to get into the dispatch queue. While a time slice on the CPU might be .1 second, a time slice in the dispatch queue might be 5 seconds. You don't let the dispatch queue ever contain so many processes that their working sets won't all fit in memory at the same time.

So a process gets into the inner circle, quickly faults in his working set, gets a lot of work done against that memory across many CPU time slices, then steps out and his page frames get quickly stolen by the next guy.

The fact that a process can spend a long time waiting in the outer circle is just recognition of the fact that you can't get blood from a stone. If you want an interactive system, you have to have enough memory for everyone.

long term scheduling

Posted Aug 6, 2004 17:46 UTC (Fri) by riel (subscriber, #3142) [Link]

The thing is, long term sheduling isn't simpler. It works fine when you have to deal with one kind of workload on one type of system, but the variety of hardware and workloads that Linux has to deal with is way bigger than the variety any of the commercial Unixen has had to deal with.

I've tried implementing good long term scheduling (aka load control) strategies for Linux in the past, but those efforts have always ran into trouble when it comes to the magic knobs needed for such a system. The 64MB RAM system with a few apps behaves very differently from the 1GB RAM system with many apps, or the 1GB RAM system with a few scientific calculations, or ...

The token based thrashing prevention, OTOH, seems to just work. No magic involved. It's turned out to be a lot simpler than any long term scheduling algorithm I've ever seen.