1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
Client Scheduling in X
Keith Packard
SuSE
10/28/99
History:
Since the original X server was written at Digital in 1987, the OS and DIX
layers shared responsibility for scheduling the order to service
client requests. The original design was simplistic; under the maximum
first make it work, then make it work well, this was a good idea. Now
that we have a bit more experience with X applications, it's time to
rethink the design.
The basic dispatch loop in DIX looks like:
for (;;)
{
nready = WaitForSomething (...);
while (nready--)
{
isItTimeToYield = FALSE;
while (!isItTimeToYield)
{
if (!ReadRequestFromClient (...))
break;
(execute request);
}
}
}
WaitForSomething looks like:
for (;;)
if (ANYSET (ClientsWithInput))
return popcount (ClientsWithInput);
select (...)
compute clientsReadable from select result;
return popcount (clientsReadable)
}
ReadRequestFromClient looks like:
if (!fullRequestQueued)
{
read ();
if (!fullRequestQueued)
{
remove from ClientsWithInput;
timesThisConnection = 0;
return 0;
}
}
if (twoFullRequestsQueued)
add to ClientsWithInput;
if (++timesThisConnection >= 10)
{
isItTimeToYield = TRUE;
timesThisConnection = 0;
}
return 1;
Here's what happens in this code:
With a single client executing a stream of requests:
A client sends a packet of requests to the server.
WaitForSomething wakes up from select and returns that client
to Dispatch
Dispatch calls ReadRequestFromClient which reads a buffer (4K)
full of requests from the client
The server executes requests from this buffer until it emptys,
in two stages -- 10 requests at a time are executed in the
inner Dispatch loop, a buffer full of requests are executed
because WaitForSomething immediately returns if any clients
have complete requests pending in their input queues.
When the buffer finally emptys, the next call to ReadRequest
FromClient will return zero and Dispatch will go back to
WaitForSomething; now that the client has no requests pending,
WaitForSomething will block in select again. If the client
is active, this select will immediately return that client
as ready to read.
With multiple clients sending streams of requests, the sequence
of operations is similar, except that ReadRequestFromClient will
set isItTimeToYield after each 10 requests executed causing the
server to round-robin among the clients with available requests.
It's important to realize here that any complete requests which have been
read from clients will be executed before the server will use select again
to discover input from other clients. A single busy client can easily
monopolize the X server.
So, the X server doesn't share well with clients which are more interactive
in nature.
The X server executes at most a buffer full of requests before again heading
into select; ReadRequestFromClient causes the server to yield when the
client request buffer doesn't contain a complete request. When
that buffer is executed quickly, the server spends a lot of time
in select discovering that the same client again has input ready. Thus
the server also runs busy clients less efficiently than is would be
possible.
What to do.
There are several things evident from the above discussion:
1 The server has a poor metric for deciding how much work it
should do at one time on behalf of a particular client.
2 The server doesn't call select often enough to detect less
aggressive clients in the face of busy clients, especially
when those clients are executing slow requests.
3 The server calls select too often when executing fast requests.
4 Some priority scheme is needed to keep interactive clients
responding to the user.
And, there are some assumptions about how X applications work:
1 Each X request is executed relatively quickly; a request-granularity
is good enough for interactive response almost all of the time.
2 X applications receiving mouse/keyboard events are likely to
warrant additional attention from the X server.
Instead of a request-count metric for work, a time-based metric should be
used. The server should select a reasonable time slice for each client
and execute requests for the entire timeslice before yielding to
another client.
Instead of returning immediately from WaitForSomething if clients have
complete requests queued, the server should go through select each
time and gather as many ready clients as possible. This involves
polling instead of blocking and adding the ClientsWithInput to
clientsReadable after the select returns.
Instead of yielding when the request buffer is empty for a particular
client, leave the yielding to the upper level scheduling and allow
the server to try and read again from the socket. If the client
is busy, another buffer full of requests will already be waiting
to be delivered thus avoiding the call through select and the
additional overhead in WaitForSomething.
Finally, the dispatch loop should not simply execute requests from the
first available client, instead each client should be prioritized with
busy clients penalized and clients receiving user events praised.
How it's done:
Polling the current time of day from the OS is too expensive to
be done at each request boundary, so instead an interval timer is
set allowing the server to track time changes by counting invocations
of the related signal handler. Instead of using the wall time for
this purpose, the process CPU time is used instead. This serves
two purposes -- first, it allows the server to consume no CPU cycles
when idle, second it avoids conflicts with SIGALRM usage in other
parts of the server code. It's not without problems though; other
CPU intensive processes on the same machine can reduce interactive
response time within the X server. The dispatch loop can now
calculate an approximate time value using the number of signals
received. The granularity of the timer sets the scheduling jitter,
at 20ms it's only occasionally noticeable.
The changes to WaitForSomething and ReadRequestFromClient are
straightforward, adjusting when select is called and avoiding
setting isItTimeToYield too often.
The dispatch loop changes are more extensive, now instead of
executing requests from all available clients, a single client
is chosen after each call to WaitForSomething, requests are
executed for that client and WaitForSomething is called again.
Each client is assigned a priority, the dispatch loop chooses the
client with the highest priority to execute. Priorities are
updated in three ways:
1. Clients which consume their entire slice are penalized
by having their priority reduced by one until they
reach some minimum value.
2. Clients which have executed no requests for some time
are praised by having their priority raised until they
return to normal priority.
3. Clients which receive user input are praised by having
their priority rased until they reach some maximal
value, above normal priority.
The effect of these changes is to both improve interactive application
response and benchmark numbers at the same time.
$XFree86: $
|
