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