Linux scheduling latency

This page contains a collection of notes and tools related to an effort to decrease the typical scheduling latency of the 2.4.x kernel.

Index

timepegs
schedlat
amlat
rtc-debug
downloads
things not to do
Ingo Molnar's patches

Tools

timepegs

The timepeg framework is a base tool which is used to measure time intervals between particular points in the kernel. You're on the wrong page. Go to here and grab it.

schedlat

This is a kernel patch which uses timepegs to measure intervals during which the kernel is ignoring reschedule requests.

What schedlat does is to record the interval between a process entering the kernel and leaving the kernel. A process may enter the kernel in one of the following ways:

Performing a system call
Getting a page fault
Getting scheduled back in while within a system call or pagefault handler

A process exits the kernel by:

Returning from a syscall
Returning from a page fault
Getting scheduled out while within a syscall or pagefault handler.

What schedlat does is to maintain four arrays of timepegs, each dimensioned by NR_syscalls:

                      |           |
                ______|___________|___________________________
syscall_start   | 0 | | | 2 | 3 | | | 5 | 6 | 7 | 8 | 9 |   |
                ------+-----------+--------------------------
                    A |         C |
                ______|________   |   _______________________
switchout       |   | | |   |     |     |   |   |   |   |   |
                ------+--------   |   -----------------------
                      |           |
                ______|________   |   _______________________
switchin        |   | | |   |     |     |   |   |   |   |   |
                ------+--------   |   -----------------------
                    B |           |
                ______|___________|__________________________
syscall_stop    |   | | |   |   | | |   |   |   |   |   |   |
                ------+-----------+--------------------------
                      |           |
                      V           V

Here, one code path enters syscall1, gets scheduled out, then gets scheduled back in and then exits the system call. In this case schedlat will report the "A" and "B" intervals.

The other code path does not get scheduled out - it simply enters and leaves. schedlat will report the "C" interval.

Here's some sample schedlat output:

        start_0004:0 -> stop_0004:0 65401     .30 8035.76     8.64 565621.23
        start_0006:0 -> stop_0006:0 1145      .22 7484.32    10.99   12592.34
   start_0005:0 -> switchout_0005:0 38      70.57 3729.48   253.28    9624.84
switchin_0005:0 -> switchout_0005:0 23      26.72 3208.19   342.06    7867.62
     switchin_0005:0 -> stop_0005:0 38      16.98 2140.33    99.25    3771.69
        start_0054:0 -> stop_0054:0 5105      .32 2001.27     1.76    9021.48
        start_0002:0 -> stop_0002:0 131    217.87 1882.48   428.13   56085.73

This shows syscall 4 taking 8035 microseconds to enter and exit the kernel.

It shows syscall 5 spending 7,484 microseconds between entering the kernel and getting scheduled out, and taking 2,140 microseconds between getting scheduled in and exitting the system call.

schedlat converts page fault events so they look like system call 255. After all, page faults are just another way of entering the kernel and requesting services from it.

Using schedlat

Apply the timepeg patch
Read the timepeg docs
Build and install tpt
Apply the schedlat patch
Run `tpt -s' to clear the timepeg tables
Start `amlat'
Run your tests
Run `tpt -s | sort -nr +5' to see the results

You really should run amlat while testing things! This introduces "scheduling pressure" and ensures that we are pushing all SCHED_OTHER tasks as hard as we can. If `amlat' is not running, the SCHED_OTHER tasks may have no reason to be descheduled!

Schedlat is part of the timepeg patch, below. It is enabled under the `kernel hacking' configuration item.

amlat

amlat is a little user-mode program which does the following:

Turns on a 256Hz interrupt stream from /dev/rtc
Makes itself a SCHED_FIFO task with all memory locked down with mlockall()
Asks that it be sent a SIGIO on every timer expiry (4 millisec intervals)
Reads from /dev/rtc in the SIGIO handler
Generates (inaccurate) scheduling latency info when it is killed with control-C

The importance of amlat is that it introduces scheduling pressure against SCHED_OTHER tasks, and that it does the read from /dev/rtc in the SIGIO handler. This read allows rtc-debug to generate good scheduling latency estimates.

rtc-debug

This is a patch against the /dev/rtc driver. It is VERY useful! It does the following:

Detects when delivery of a SIGIO to amlat fails to set the current tasks's need_resched flag. This happens occasionally and it may be a kernel misdesign/bug. Still investiating. When this situation occurs, rtc-debug simply sets the current process's need-resched flag from within the ISR! A bit rude, but it allows me to get on with testing things...
Detects when a SCHED_OTHER process is being "piggy". Pigginess refers to the act of not calling schedule() for 5 milliseconds after the SIGIO has been sent to amlat. rtc-debug forces a stack backtrace on the piggy process so you can see where it's being piggy.
Measures scheduling latency and generates a histogram of this. Scheduling latency is defined here as the interval between the entry to the RTC interrupt service routine and the reading of /dev/rtc. So this mechanism requires that amlat be running. The histogram is displayed when /dev/rtc is closed (when amlat is killed). The histogram displays something like this:

1:12345 2:1024 4:3

Which would indicate that 12,345 interrupts were serviced in one millisecond, and four interrupts were services in three milliseconds.

Of course, things are worse than this: interrupt service latency will add to these numbers. Did I mention intlat?

If you want to drill down further and find out why there are scheduling 'bumps', rtc-debug won't tell you. schedlat will.

Downloads

Timepegs
amlat
rtc-debug

Paul Winkler has put up a nice page which shows how to build 2.4 kernels (including this patch).

The note below

Low-latency is enabled via the "Processor Type and Features" menu or x86
In the 2.4.1 patch, Low-latency was removed from the config for other architectures. It should work OK, but I can't test it. Drop me a note if you want to experiment with this.
There is a new configuration option Control low latency with sysctl. If you enable this, you can turn the low-latency capability on and off with /proc/sys/kernel/lowlatency. The default value is zero - low-latency disabled.

Don't do that!

There are a few things you can do to your Linux system which will simply kill its scheduling latency. This section describes those things as we discover them. So far, none of these are show-stoppers - it is feasible to setup your system and it software so these things don't happen.

Avoid scrolling the fb console. Pavel says:

With fbcon on machine with loaded PCI bus (usb modem), N can be ~500 milliseconds, even more with really full screen. You know, fbcon is running with interrupts disabled.

Don't run hdparm. It chews 50 milliseconds.
Don't use blkdev_close(). This function can consume tens of milliseconds. It's used by LILO to write to the raw block device.
Don't switch consoles. The console driver can block interrupts for a millisecond or so.

If you observe all the above, you should be able to achieve consistent worse-case scheduling latencies of 0.5 milliseconds on a 500MHz machine.

If something goes wrong and you start seeing scheduling latencies, please try to investigate the source using the above tools (mainly rtc_debug and amlat) and let me know what you're doing to cause this.

Ingo Molnar's patches

Ingo Molnar wrote Linux's first low-latency scheduling patches. Those patches use the same algorithmic approach as the ones here, and these patches borrow a few bits and pieces from Ingo's.

Ingo also has patches against the 2.2 kernels.

His work is available at http://people.redhat.com/mingo/lowlatency-patches/

AKPM Home
Andrew Morton, 7 Jan 2001