The (default) Linux task scheduler needs to be improved

alex6z · Tux's lil' helper Joined: 20 Jul 2005 Posts: 119

On windows (and I think Mac OSX and Solaris are similar), a process has a priority. If there are two processes running, each one will get half of the CPU. Not only will they get half, but the timeslice is small enough to where the user using the program fells like it is running smoothly. Processes with higher priorities get more CPU attention, the high priority process might get 80% CPU and the other 20%. But the user using the regular priority program will not notice because the program doesn't need all that CPU to work anyway.

If you're using a program that tries to use all the CPU it can get, like most games do, the windows task scheduler works fine. Say I'm playing a game that will run fine on 500MHz. But my CPU is 1GHz. So I'm playing the game, and a process starts in the background - or maybe I'm even compiling a program in the background - the game will continue to run, maybe a bit slower, but otherwise just fine.

Windows' task scheduler is at a disadvantage when it comes to running a program that spends most if it's time sleeping. In linux, when the program wakes up with a game running, it will give full attention to that program for a short while, until the program goes back to sleep, meanwhile causing the game to freeze. In windows this program will only get what it needs to get done half as fast as it would in linux, because linux would give the program full CPU attention and interrupt a game that's running where as windows would give the program half CPU attention and let the game continue to run along side it.

Now in linux this is a different story. The task scheduler works great for servers and programs which spend most of their time sleeping, only coming to life when the user wants it to do something. When running a program that uses all the CPU it also does great. For example a gziping a directory won't cause the sistem to appear to be running any slower, because linux will lower the priority of gzip, allowing the user who might be using a web browser to click a link to a web site and have the page load at full speed as if gzip were not running. This is possible because linux pushes programs which use all available into the background with lower priourity.

1) Now when it comes to an interactive program like a game which tries to use all avilable CPU, it's pretty much a single tasking operating. If I'm playing a game and a program starts running in the background, the game will stop for sometimes even a few seconds which makes the game unplayable!

I have never been able to compile something on gentoo while playing a game. Linux lets the game run for a second, then the game freezes while gcc compiles a package, then the game unfreezes for a second or two and oven and over again! If I lower the priority of the compiler, the game will run but the compiler will only get 2% CPU and the program will never get compiled!

2) Linux's task scheduler is unfair. Two processes running with the same nice value are supposed to get on average the same CPU attention. What happens is, if say, you have gzip running and a program that uses 75% cpu like a movie player, gzip will get 25% CPU and the movie player process will get 75% CPU! This happens because linux lowers the priority of gzip, but lets the movie player keep a high priority because it sleep()s 25% of the time! Two processes which have the same nice value are supposed to get the same over all CPU attention aren't they!?

What this means is that if I were to code gzip so that whenever it's dynamic priority goes above 15 or 16 (lower priority) it would sleep for a moment, Linux would give it high priority above another instance of gzip which just runs without sleeping!

To sup up, what do I do if I want to play a game and compile something in the background? On windows I could do that just fine, but on linux what should I do?

One idea I had to fix this problem is to make it so that linux's task scheduler has a function (sort of similar to sched_yield() I guess) which can be called from a running interactive program like a game say every time it finishes rendering a frame. This would be sort of like a "preferred preemption point" which would tell linux that this is an interactive program which prefers te be preempted every say 15ms, and linux would put it in a correct priority class. This way linux would continue to run the program in real time instead of stopping it for a whole second or two.

Anyway, is there anything I can do about this? Are there alternate task schedulers for linux? Wouldn't it be cool if you could bring up a menu in linux and select a task scheduler while the system is running, and load and unload task scheduler modules!

PaulBredbury · Watchman Joined: 14 Jul 2005 Posts: 7310

You could try the ebuild in this thread, for a scheduler rewrite.

pielgrzym · n00b Joined: 06 Jan 2007 Posts: 55

You should try some kernel patchsets providing experimental linux desktop schedulers (like my favorite Staircase Deadline or Completely Fair Scheduler). Take a look at viper sources - vipernicus created two parallel patchsets with both of abovementioned schedulers:

Viper with Staircase Deadline scheduler
Nicus sources with CFS scheduler

Both of the patchsets are quite heavily patched and experimental, but I never had any problems with them. If you do you could try ck sources (it's a gentoo sources with Staircase Sched patch) availible in the portage.

Those patches change completely the kernel behaviour. I fancy the a lot and I think you will love them

Negated Void · l33t Joined: 25 Dec 2002 Posts: 672

I think you misunderstand how linux's scheduler gives priority to one program over another. The dynamic scheduling doesn't give one process that much of a speed advantage over the other - it takes a significant amount of sleeping to influence a processes priority. The idea behind this is that it allows the scheduler to distinguish CPU bound and IO bound programs - IO bound programs are often just waitting on an event or some IO action, and they will return to sleeping quickly when they get to it. Giving them a higher priority improves the feel of "responsiveness" - shouldn't a GUI event have a higher priority than a gzip process? Chances are you won't notice the difference in the time gzip takes (an IO bound process won't run for a very long time, and overall gzip will get roughly the same cpu time - it'll just be delayed a little), but you'd surely notice the increased reaction time to a mouse click.

Yeah, that module doesn't work the greatest with games - you might want them to continue to receive a high priority even when they're hogging cpu. To accomplish this, you should set priority on the games - running them at a manual nice -10 will ensure that they are always higher priority than other random processes.

The linux scheduler shouldn't award timeslices of "a second or two", and there is already a "this is a good place to preempt me" call - sleep! When your game finishes rendering a frame, it should sleep until it has another to process or it receives an input event, and when it does that the scheduler will be called.

I support the others recommendations that you try the other task schedulers to see if they help you out. Also, try messing with the HZ setting in your kernel.

Have you considered that the bottleneck might not be CPU? In my experience, IO bottlenecks can be much worse - if the compile process in the background, using it's bit of cpu time, starts a lot of hard drive operations, then maybe that'll cause the game to choke up? Make sure you have DMA enabled, but I'm not really sure what to do about IO bottlenecks.

Good Luck,
--Murph

PS - What kernel version are you using?

mudrii · l33t Joined: 26 Jun 2003 Posts: 789 Location: Singapore

Negated Void

Thax for nice explanation
_________________
www.gentoo.ro

pielgrzym · n00b Joined: 06 Jan 2007 Posts: 55

Negated Void, thanks for the explanation! I recently noriced that VirtualBox while loading virtual system, can really freeze my system on Staircaise (not entirely, but redrawing is really slow). I'm sure it's related to I/O since games don't make system so low on responsivity. I guess it might be reiser's fault since it likes to eat cpu (much more in comparision to XFS...). I use SATA disks so there's no chance it's DMA's fault. Can I do something to improove system responsivness even more? I already tried ~800Hz and 1000Hz interrupts. I'm planning to expand my RAM to 3GB (apparently swap can really slow down the whole system...).

Thanks in advance!

alex6z · Tux's lil' helper Joined: 20 Jul 2005 Posts: 119

Hu · Administrator Joined: 06 Mar 2007 Posts: 23193

What game are you running that requires continuous full CPU usage to run effectively?

energyman76b · Advocate Joined: 26 Mar 2003 Posts: 2048 Location: Germany

pielgrzym · n00b Joined: 06 Jan 2007 Posts: 55

energyman76b, never had any kernelish issue with those patchsets. My only bigger system failure was due to FUSE, which sucks on gentoo-sources either

It wasn't anything critical - just some lockups

alex6z, are you sure your machine is powerfull enough for two totally challenging tasks like compilaton and gaming at the same time?

PaulBredbury · Watchman Joined: 14 Jul 2005 Posts: 7310

dsd · Posted: Sat May 19, 2007 11:00 pm Post subject:

not meaning to sound condescending, there are numerous flaws in your understanding of process scheduling above. recommended reading: linux kernel development 2ed, robert love.

regardless, the question of how to handle two CPU-bound processes at once, where one demands extreme interactivity and one completely doesn't, is interesting. i suspect your experience with windows is better here due to the fact that windows 'cheats' by greatly increasing the effective priority of the process owning the currently-focused window.
_________________
http://dev.gentoo.org/~dsd

Sadako · Posted: Sat May 19, 2007 11:07 pm Post subject:

Gergan Penkov · Posted: Sun May 20, 2007 12:29 am Post subject:

Strangely enough I didn't have any problems till now with the kernel scheduling. In fact the linux-kernel scheduling is far superior to windows one, try to open 200mb file with notepad or cat it on windows console and you'll understand what I mean. And the games I've tried run faster and better on linux and the desktop does not need to swap itself in for half an hour after closing them :twisted:

_________________
"I knew when an angel whispered into my ear,
You gotta get him away, yeah
Hey little bitch!
Be glad you finally walked away or you may have not lived another day."
Godsmack

alex6z · Tux's lil' helper Joined: 20 Jul 2005 Posts: 119

energyman76b · Advocate Joined: 26 Mar 2003 Posts: 2048 Location: Germany

alex6z · Tux's lil' helper Joined: 20 Jul 2005 Posts: 119

devsk · Posted: Sun May 20, 2007 3:51 am Post subject:

Negated Void · l33t Joined: 25 Dec 2002 Posts: 672

There's a limit on the dynamic priority system - it never goes beyond +5 or -5 of the static priority. I just checked the current source (since I'm familiar mostly with the 2.4 kernels), and it's still the same.

Thus, if you set something to -10, it will never go above -5. And if you set something to 20, it will *never ever* achieve TASK_INTERACTIVE status.

--Murph