# The (default) Linux task scheduler needs to be improved

## alex6z

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

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

----------

## pielgrzym

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  :Smile: 

----------

## Negated Void

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

Negated Void

Thax for nice explanation

----------

## pielgrzym

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

 *Negated Void wrote:*   

> 
> 
> PS - What kernel version are you using?

 

The regular vanilla-sources.

Look I understand why linux's default task scheduler is this way, it's optimized for a server, and it works quite well on a server.  It also works great on a desktop system where responsiveness after clicking the mouse is important, like you said. Desktop use where CPU intensive applications need to be responsive is a different story.

I'm trying to install one of the patched kernels now.

Sorry it's hard to explain why the kernel doesn't work the way it does.  I can't think of a simple way to explain it.

The problem with the default scheduler is this:  linux gives IO bound programs high priority, and CPU using programs low priority, the problem: it is impossible to run an interacive CPU using program like a game with this scheduler and have something else running in the background.

Also it isn't fair that a gzip like process get's 25% CPU while mplayer gets 75% because it's sleep()ing 25% of the time.  I know it makes mplayer work better, but the scheduler should be fair.

You're suggestion to give the game a high priority with nice -n -10 doesn't work at all.  Nothing else in the background gets to run much at all.  Try this # nice -n -10 yes>/dev/null.  The mouse hardly moves across the screen!  I want to be able to compile a program while playing the game at the same time, at that rate the program would take a week to compile.

The Hz option in the kernel adjusts how fast a high priority process responds.  You could have 10,000 Hz but it wouldn't help you if linux won't schedule the process the way I want.

The "good place to preempt" isn't sleep()!  When you're playing a game you don't want to spend any time sleeping if it doesn't have to.  It would take a lot of work to figure out just how much to sleep() in order get the program where it needs to be in linux's dynamic priority system while letting the game run as fast as possible.

I'm trying out one of the patch sets.

It's hard to explain how the scheduler doesn't work the way it does.  I'll try to make it simple:

Program starts.  pragram uses all the cpu it can get.  Within a fex seconds, linux bumps down the priority to the lowest possible value for a nice value of 0, which is 25.  Another program, like a c compiler for example, starts in the background, linux's default scheduler gives it a dynamic priority of 16.  The first program has completely stopped, and the second program is running.  After a few seconds linux has reduced the priority of the second program to 25.  Now the first program starts to run again, along with the second program.  Both programs are now running in chunks, where if the first program was a game it would get 30 frames, then freeze for half a second, then render 30 frames again.  After this, the second program finished and things go fine again until another program starts up again, which will be right away if it's a c compiler like gcc.

----------

## Hu

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

----------

## energyman76b

 *Hu wrote:*   

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

 

ut2004?

btw, don't use the patched kernels, install the vanilla sources and patch for yourself.

That way you only have one point of failure and no additional risks because of patches you don't need.

Leave the more 'experimental' kernels for people who don't care about stability or have tape backups.

You'll find the cfs patch here:

http://people.redhat.com/mingo/cfs-scheduler/

I had some good experiences with cfs - and Ingo Molnar reacts quickly on any kind of input.

ps. I just do a tape backup with mbuffer&tar on a dlt - because I want to turn /home into a reiser4 partition. Yay! EXPERIMENTAL!

----------

## pielgrzym

energyman76b, never had any kernelish issue with those patchsets. My only bigger system failure was due to FUSE, which sucks on gentoo-sources either  :Wink:  It wasn't anything critical - just some lockups  :Smile: 

alex6z, are you sure your machine is powerfull enough for two totally challenging tasks like compilaton and gaming at the same time?Last edited by pielgrzym on Sat May 19, 2007 10:20 pm; edited 1 time in total

----------

## PaulBredbury

 *alex6z wrote:*   

> nice -n -10 yes>/dev/null

 

My mouse still works perfectly, with ubuntu-sources-2.6.22_p4-r10 (my ebuild), and usbhid.mousepoll=2 in /boot/grub/menu.lst. But then, I have a Core 2 Duo. Is that cheating?  :Smile: 

----------

## dsd

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.

----------

## Sadako

 *PaulBredbury wrote:*   

>  *alex6z wrote:*   nice -n -10 yes>/dev/null 
> 
> My mouse still works perfectly, with ubuntu-sources-2.6.22_p4-r10 (my ebuild), and usbhid.mousepoll=2 in /boot/grub/menu.lst. But then, I have a Core 2 Duo. Is that cheating? 

 

Works fine on my lowly socket 939 X2 also, however I think us dual-core users should try the following instead;

```
nice -n -10 yes > /dev/null & nice -n -10 yes > /dev/null
```

(lets see how your core 2 handles that.   :Razz:  )

----------

## Gergan Penkov

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 Evil: 

----------

## alex6z

 *PaulBredbury wrote:*   

> But then, I have a Core 2 Duo. Is that cheating? 

 

Yes. Any kinda of dual core hyperthreading is cheating.  Try this:

nice -n -12>/dev/null

And run it again in another terminal, to keep both cores busy!

Maybe I don't understand linux's default task scheduling model well enough, but I know enough about it to know that there is a serious problem when you are trying to run a CPU intensive  interactive process like a game when there is something going on in the background.  The program in the background is usually IO bound and will interrupt the game until it finishes.  For example, if apache/php is running in the background, and you're playing a game, if you're server gets a hit, the game will stop until apache finishes, unless the background process stays running long enough to where linux kicks it down to the same priority level as the game and both programs start running together, but even when this happens the game will run in bursts.

Try this experiment

Start up top in a terminal window.

Start a game the runs in a window and uses all the CPU it can get.  I chose the game heroes  You should see that after several seconds the dynamic priority goes from 15 to 25 for the heroes process.

Ok, now it's time to do somethnig in the background.

run this:

```
$ yes > /dev/null
```

When you start it the game should freeze for a moment, then as the dynamic priority of yes gets bumped down to 25 like the game, they start to run together.  On my system, I notice that the framerate in the game comes in bursts.  It renders some frames, then freezes (while yes runs) and then the game runs again.  This fine for a program like gzip, the system will run quite efficiently like this, but this is not good for interactive programs.

Now this is what happens when you're compiling stuff in the background, or when your web server gets a hit, or any other program that's been sleeping wakes up and decides to take a chunk of CPU while the game is running.  Try this example:

```
while true; do seq 1 500000 > /dev/null; echo hit\!; sleep 1; done;
```

Adjust the count on seq so that it takes about a half to three seconds to finish counding.  That above simulates a web server in the background getting hits or a package compiling.  When you're playing heroes you should notice that the game freezes each time that script goes through it's loop.  One simple solutin to this problem would be to have programs start out with a low dynamic priority and work their way up to 15, instead of working their way down to 25 while causing games like this to freeze.Last edited by alex6z on Sun May 20, 2007 2:09 am; edited 1 time in total

----------

## energyman76b

 *Hopeless wrote:*   

>  *PaulBredbury wrote:*    *alex6z wrote:*   nice -n -10 yes>/dev/null 
> 
> My mouse still works perfectly, with ubuntu-sources-2.6.22_p4-r10 (my ebuild), and usbhid.mousepoll=2 in /boot/grub/menu.lst. But then, I have a Core 2 Duo. Is that cheating?  
> 
> Works fine on my lowly socket 939 X2 also, however I think us dual-core users should try the following instead;
> ...

 

well, my X2 handles that fine.

----------

## alex6z

 *energyman76b wrote:*   

> 
> 
> well, my X2 handles that fine.

 

try nice -n -12 or -15, run that twice and the drag a window around the screen, X should stop running smoothly.  nice -n -10 happens to be just the spot where the kernel will bump the priority from 5 to 15 which is the same as X so X will seem to run fine.  Now if you try nice -n -12 it should go from 3 to 13 with X still having a dynamic priority number of 15 so the mouse will not move smoothly.  If you have a fast system, you might be able to move the mouse fine, but try dragging a window with it.

----------

## devsk

 *alex6z wrote:*   

>  *PaulBredbury wrote:*   But then, I have a Core 2 Duo. Is that cheating?  
> 
> Yes. Any kinda of dual core hyperthreading is cheating.  Try this:
> 
> nice -n -12>/dev/null
> ...

 I think you have some very good points to make. And yes, people with dual cores: don't cheat like that...  :Laughing:   Start two such instances of 'yes' in two different windows and watch you mouse freeze.

 *Quote:*   

> One simple solutin to this problem would be to have programs start out with a low dynamic priority and work their way up to 15, instead of working their way down to 25 while causing games like this to freeze.

 I actually like this idea a lot. Simple yet workable.

----------

## Negated Void

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

----------

