Messages in this thread |  | | | Date | Tue, 17 Feb 1998 00:39:00 +0100 (MET) | | From | Rik van Riel <> | | Subject | Re: Linux scheduler (fwd) |
| |
On Mon, 16 Feb 1998, Andrew J. Anderson wrote:
> "quantum expiration policy" that reduces your CPU window if > you get an involuntary context switch -- this keeps CPU hogs from choking > the machine. > > "sleep return priority" that is generally higher than the current priorty > (this keeps interactive performance good) -- the idea being that the > process blocked on IO and is now ready to do something. > > "maximum wait" that defines how long a process will wait on the current > run queue level before being escalated to a higher level. (This is how > Solaris addresses starvation.) > > "long wait priority" that handles nice'd processes to make sure that they > get some CPU time. This is roughly double the maximum wait by default.
I've been suggesting something like this to the QNX-sched author as well. But in a more non-tunable way. It lacked the OS/2 like maximum wait, however.
I can remember something like this from the linux-1.2 days (kswap reduced the timeslice to 4*HZ/loadavg to have better scheduling).
Here are two scheduling algorithms that might be worthwhile for Linux. Personally, I prefer the second one, but the first one might be implemented with the least change to the current kernel.
--------------> BSD-and-OSF-like-algoritm <----------- I think I (or we?) really should look into this and provide: - on-the-fly priority changes (not just when all timeslices are finished) a-la BSD - max-wait extra-extra bonus. (nice +20 --> max-wait *= 20 ??) - SCHED_BG extra-low-priority without max-wait - realy-low latency for interactive processes !!!!! Solaris and OS/2 haven't done this properly, thereby earning their nicknames Slowlaris and 'half an OS'. - very long timeslices for processes niced >= 10, so their influence on the VM subsystem is smaller than it is now -----------> QNX-and-CTSS-like-algoritm <---------------- A-la QNX, a process in the highest priority ring is executed and demoted once it's timeslice is over (if it uses it's entire timeslice). Only when no processes remain up-there, the scheduler moves down to the lower queues.
QNX-sched like demotions / promotions.
*NEW* Every level down, the length of the timeslice doubles, so a 10% CPU task will remain 'stuck' at a certain level, and thus it will _always_ have a higher priority than any idle-eater, and have near-realtime performance (compared to idle-eaters). This might be a good way to get more-than-just-reasonable performance for games and mod-players on multiuser machines. This won't reduce the number of context switches, since a long-slice process _will_ be interrupted by high-priority processes. It's just that after the interruption the system will continue with the same low-prio task, and not with it's competitor...
*NEW* Tasks get promoted above their maximum priority, when they suffer from starvation, but this is for one full timeslice only... OTOH, when it never finishes a timeslice, it might just remain in the high queue (so a +20 niced vi still get's good performance :-) For this the max-wait might be multiplied by the nice level the process is on.
*NEW* When a task reaches the max-wait value, it gets (for one slice) promoted to real-time priority, _and_ the _system-wide_ timeslice length gets halved for 5 seconds, so the system can overcome temporary extra loads.
*NEW* Introduction of a SCHED_BG task without a max-wait value. There's no way to rescue your vi from this... So maybe we shouldn't introduce this feature :-)
*NEW* Euhmm, what did I forget?
The existing QNX-sched patch is probably a good base for the second approach. Somebody just might code it up in half a week :-)
Rik. +-----------------------------+------------------------------+ | For Linux mm-patches, go to | "I'm busy managing memory.." | | my homepage (via LinuxHQ). | H.H.vanRiel@fys.ruu.nl | | ...submissions welcome... | http://www.fys.ruu.nl/~riel/ | +-----------------------------+------------------------------+ - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu
|  |