iTWire - The nuts and bolts of the Linux process scheduler

Today on iTWire iPhone IT News Telecommunications People Our Blogs Tech Lifestyle Releases Science Discuss Events IT&T JOBS

Bringing the world of Linux to you, David cuts through the tech and shows you how it works and how to use it, in terms that apply to any distro.

IT NEWS Sustainability

- Virtualisation

Technology news and Jobs

The Linux distillery

The nuts and bolts of the Linux process scheduler

by David M Williams

Monday, 18 February 2008

Page 2 of 3

Every Linux process is given a quantum – or time slice – to do its work in before the kernel stops it, to let another run. If the process yields voluntarily then that’s cool; this generally happens automatically whenever a read or write to an I/O device is called. In this case, the process is said to have yielded. If the time slice expires the kernel stops the process. These processes are said to be pre-empted.

These aren’t the only two scenarios. A process might be waiting for something to happen – for example many network services – like web servers, or SMTP – sit around waiting for a client to connect before they have any work to do. It’s not just a matter of reading data from a slow disk or slow-typing user, but actually having no activities to perform until an event takes place.

In this case, the process is said to be blocked. It won’t run again until the event takes place. A blocked process won’t use the CPU at all and simply does not need to be scheduled to run again until the event takes place which wakes it up.

There’s more to the scheduler than this. Whenever it has the opportunity to give a process a chance to run the scheduler has to figure out which one it should opt for. To help make the choice, Linux gives each process a priority. Higher priority processes may run before a lower priority one. This priority is influenced by the user but ultimately the kernel has control and may increase or lower the priority as time goes on. In particular, a bonus is given to processes which play nice – namely those which are rarely pre-empted because they yield frequently.

Nicely, this bonus scheme tends to favour those processes which are interacting with users. An application which regularly takes keyboard input will be regularly yielding whenever it is waiting for input. On the other hand, a program performing a lot of calculations and has to pre-empted isn’t really dealing with the user at all. This type of process will receive a negative bonus value.

You can see this illustrated. Make two scripts; one will do a lot and the other not so much.

#!/bin/bash
while [ true ]
do
sleep 0.1
done

and

#!/bin/bash
x = 0
while [ true ]
do
x = $(($x + 1))
done

The first script spends all its time sleeping. The other script constantly increments a number. This is pretty meaningless but the purpose is to chew up the CPU endlessly. Let’s call them yielder.sh and preempter.sh respectively.

Set them running like so:

./yielder.sh &
./preempter.sh &

Next, check their priority level by repeatedly running this command:

ps –C yielder –C preempter –o etime,pri,cmd

What do you see? Please read on.

CONTINUED