Kernel scheduling algorithm and X.Org performance

Dmitry Shatrov erdizz at
Wed Aug 31 05:47:05 PDT 2005

Good day, xorg list. If you think this worths another list please
redirect me.

I would like to talk about X-based desktop responsiveness and how 
it turns out to be related to the kernel's process scheduling 

Recently I had some time to play with my friend's Windows box. And
somehow one thing that I never noticed amazed me. Windows desktop 
perfectly responsive when I drag windows on top of each other. You do
not notice that all the applications whose windows were obscured by a
window you drag wake up and re-parent themselves. It looks just like 
pictures were already there. Compare this to the common X-based 
behavior: pick up any window, drag it over your desktop. Soon you'll
notice that you're able to erase the contents of any window so that it
looks filled with its background color, the desktop icons disappear,
things flicker here and there. The very first thing I hear from my
friends when I first install Linux on their computers (happens from 
to time) is that after they drag a window and see it working as an
eraser they say: "Woo, it's slow". What can I answer then? Tell them
that this thing is network-transparent? I know it is, but they don't 
it and tell their friends that "that Linux thing is slow". Sad.

Still I realize that each component of the desktop in front of me is
carefully designed by its developers and in theory should work pretty
well. Pretending to be a hacker-minded person I tried to understand 
doesn't it work well in the real world.

First, how is the Windows (Microsoft Windows) rendering scheme 
from what we have in X? Let's assume we are on a single physical
machine, no networking. Then it turns out that there's not so many

Actually, the only major point that I can mention is that Windows
graphics subsystem is 'in-kernel'. This only means that it runs in
kernel space, because it is evident that it is separated enough from 
rest of the NT kernel. Graphics system is completely event-driven, so 
really doesn't matter where to place its code. In-kernel solution 

   1. There is one less context switch (i.e one) to transfer a request
from a client to the graphics system.
   2. There is one less context switch (i.e. zero) to transfer an 
event from the kernel to the graphics system.

Guess we all know general pros. and cons. of in-kernel vs user-space
graphics so I'll not reemerge them here. It is only relevant that
in-kernel approach is faster because of 1 and 2.

Do these additional context switches matter? My point is that the 
is that no, they do not. X is able to be just as fast as Windows,
especially if properly programmed.

But let's look from the other side. If a context switch is to happen,
then _when_ should it happen? This question does not exist in MS 
which is equivalent to that it is solved the perfect way. What about 

Three players come up here.

The first player is X server itself. It is a user process that it is a
subject to schedule. The second player is the client. The third is a
window manager, which is also a separate process. The whole team of
processes is being driven by the kernel.

The first problem here is that at this point the inter-operation of
simple parts becomes really complicated. The second problem is that 
kernel treats the players as functionally equivalent entities - user
processes, and applies a general-purpose scheduling algorithm which is
itself quite complicated, gives priority bonuses to processes that are
"interactive enough" etc. Linux 2.6's O(1) scheduler is not so 
to understand (I'd recommend Robert Love's explanation in his "Linux
Kernel Development", 2nd ed. - it's clean and compact), but it is 
difficult to track in the case of X + WM + client interaction.

My guess is that to get the Windows-like picture of operation on X one
should probably do the following:
1) renice Xorg process to -6
2) renice window manager's process to 1 (it's metacity in my case)

Just try it - and - voila. The dragging window is not an eraser any
more. It really feels like on Windows. Lets look what happens in this

0. Our system is currently idle. There's nothing running in the
background, we are dragging a window and there is a window of another
application in the background (e.g. nautilus file manager's window).

1. We press a mouse button on a window manager's title. The kernel
delivers some data to X through a character device (say, /dev/mosue).
X server wakes up immediately, because it is a highest-priority 
It receives SIGIO, recognizes a mouse event and queues it, then it 
up on Select() and transfers the event to the window manager.

At this point we have the whole system working only for the graphics
system, nothing preempts us: we get a mouse interrupt, immediately
handle it in a mouse interrupt handler, then immediately follows a
softirq of the mouse driver that pushes data through /dev/mouse, then
immediately schedule() is called and X server wakes up, and it pushes
data to WM. I bet this is perfectly fast.

2. X has nothing to do now, so WM wakes up. It reads data and sees 
a window should be moved (lets assume that we're already dragging a
window). It performs some geometry calculations and issues certain
commands to X, flushes them out and goes to sleep. Everything is ok at
this point too.

3. X wakes up and reads WM's commands. It says to move a window, so X
actually moves it, but a part of the window at the background is to be
repainted. X issues a repaint command to that client. And also it is
very likely that part of WM's decorations is to be redrawn as well 
point confuses me - when does WM actually paint its decorations? 
me please), so it also gets some events to dispatch. Done with that, X
goes to sleep.

Notice that here we are likely to be fast enough not to receive new
mouse events, because we did not do actual drawing - only some
calculation and three context switches. BUT if a new mouse event 
X will issue commands to the window manager again... And if WM is then
scheduled before the client (whose window is at the background) it 
again issue commands to X server and X will wake up because it is a
high-priority process (if X is at the same priority then it is not 
good too: we see that every day), and this way, especially if repeated
several times, the client misses its time to repaint its window and 
content is erased. This is what users call "slow". This is why we set
WM's priority to 1 (the least of the three): this way the client will
wake up first.

4. Now, the client wakes up. It repaints itself, but this is likely to
take long time (modern desktop programs are quite complicated), and if
somewhere at this point we get a mouse event, the client will be
preempted by the X server, and X will transfer an event to WM. But WM 
a least priority and thus our client will be scheduled back and what 
does will still be adequate: WM didn't make any geometry 
yet. If WM is a higher priority then things may go the bad way as I 

5. Now the client is done with repainting and if a mouse event has
already been processed by X, WM wakes up. The whole cycle repeats from
the point "2". Or from "1", if the mouse hasn't moved yet.

In fact, this picture is even more complicated, because window 
decoration are subject to be redrawn as well, and (just for an 
metacity is quite slow in this. Slow enough to see it visually. The 
that I test this on is a slow one, 700Mhz Celeron + Matrox G400, but I
think it allows me to see the real picture more cleanly.

The most visible problem with these renices is that WM feels a bit
laggy, the window movement is not smooth enough. But on the other 
windows do not erase each other's contents and thus the overall
impression of the system is better. The other nice point is that 
desktops seem to switch faster with low WM priority, because
applications redraw themselves before WM draws its decorations: users
look at the applications first, and their windows swap faster.

Frankly speaking, I'd like to play with the beast by myself a bit more
first and then show you what I've got, but the system looks so
complicated that without your advice there are too many roads to go.

I've prepared two _really trivial_ patches, the are not fixes, nor
features. They are intended for more clear understanding of the 
and to show how trivial the necessary modifications could be.

The first is for Xorg's DIX Dispatch() function (it's against
X11R6.8.1). My point there is that We should give a priority to 
client's commands first, and when we're done with that, handle the
input. I don't base this on some deep research, just an abstract 
about order-of-service. This may event not to make any sense, I wanted
at least to make sure that the build system works and it's possible to
make patches. Though it seems to me that X performs better after the
change than before. Anyway, it seems too simple to me to treat input
events and clients events as something equal. There could be a better

The second patch against linux- makes O(1) scheduler algorithm
as simple as a stick, eliminating temporal priority boosts. It feels 
on a slightly-loaded system, but with 98% of time being idle it is ok,
and the responsiveness of the desktop graphics is much easier to
understand with a simpler scheduling algorithm.

Finally, what I'm suggesting to do:

My point is that it is time to figure out what scheduling algorithm is
the best for X.Org and implement it in the Linux kernel. X server and 
processes may even be considered special in the kernel and handled not
like conventional processes. It may involve some tricks, maybe 
beyond a trivial model (say, divide WM's decoration painting from
geometry recalculation somehow, or whatever matters).

The whole concept of process priorities and process timeslices, and 
a higher-priority process first takes its whole timeslice (500ms is a
normal amount here) and only then all other processes receive control
and we get a "ping - 0.5s hang - ping - 0.5s hang" system.. this 
suit well in a desktop system. And time doesn't make things better. I
upgraded from the 2.6.5 kernel to 2.6.10 and then 2.6.12 kernel 
(I have to patch the kernel for my project each time so do it rarely)
and got the degraded performance. On 2.6.12 I often see how my mouse
freezes or slows down much more often than on 2.6.5. I even had to
"iptables .. -j DROP" some of our LAN's ip addresses because they 
let me work normally while stressing my Samba server. It is evident 
an ordinary user will not end up doing duff -u
linux-2.6.5/kernel/sched.c linux-, so the way 
go should be well-defined or we'll loose it.

Addressing the problem of X vs WM vs clients scheduling may really
improve visible X responsiveness. Each component of the system itself 
already good enough. They just do not interoperate the most efficient
way. So what is the most efficient way? What do you think?

Best regards, Dmitry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: simplify_dispatch_xorg_6.8.1.patch
Type: text/x-patch
Size: 795 bytes
Desc: not available
URL: <>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: simplify_scheduler_2.6.12.5.patch
Type: text/x-patch
Size: 687 bytes
Desc: not available
URL: <>

More information about the xorg mailing list