1 Client Scheduling in X 2 Keith Packard 3 SuSE 4 10/28/99 5 6History: 7 8Since the original X server was written at Digital in 1987, the OS and DIX 9layers shared responsibility for scheduling the order to service 10client requests. The original design was simplistic; under the maximum 11first make it work, then make it work well, this was a good idea. Now 12that we have a bit more experience with X applications, it's time to 13rethink the design. 14 15The 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 32WaitForSomething 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 42ReadRequestFromClient 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 64Here's what happens in this code: 65 66With 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 89With multiple clients sending streams of requests, the sequence 90of operations is similar, except that ReadRequestFromClient will 91set isItTimeToYield after each 10 requests executed causing the 92server to round-robin among the clients with available requests. 93 94It's important to realize here that any complete requests which have been 95read from clients will be executed before the server will use select again 96to discover input from other clients. A single busy client can easily 97monopolize the X server. 98 99So, the X server doesn't share well with clients which are more interactive 100in nature. 101 102The X server executes at most a buffer full of requests before again heading 103into select; ReadRequestFromClient causes the server to yield when the 104client request buffer doesn't contain a complete request. When 105that buffer is executed quickly, the server spends a lot of time 106in select discovering that the same client again has input ready. Thus 107the server also runs busy clients less efficiently than is would be 108possible. 109 110What to do. 111 112There 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 126And, 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 134Instead of a request-count metric for work, a time-based metric should be 135used. The server should select a reasonable time slice for each client 136and execute requests for the entire timeslice before yielding to 137another client. 138 139Instead of returning immediately from WaitForSomething if clients have 140complete requests queued, the server should go through select each 141time and gather as many ready clients as possible. This involves 142polling instead of blocking and adding the ClientsWithInput to 143clientsReadable after the select returns. 144 145Instead of yielding when the request buffer is empty for a particular 146client, leave the yielding to the upper level scheduling and allow 147the server to try and read again from the socket. If the client 148is busy, another buffer full of requests will already be waiting 149to be delivered thus avoiding the call through select and the 150additional overhead in WaitForSomething. 151 152Finally, the dispatch loop should not simply execute requests from the 153first available client, instead each client should be prioritized with 154busy clients penalized and clients receiving user events praised. 155 156How it's done: 157 158Polling the current time of day from the OS is too expensive to 159be done at each request boundary, so instead an interval timer is 160set allowing the server to track time changes by counting invocations 161of the related signal handler. Instead of using the wall time for 162this purpose, the process CPU time is used instead. This serves 163two purposes -- first, it allows the server to consume no CPU cycles 164when idle, second it avoids conflicts with SIGALRM usage in other 165parts of the server code. It's not without problems though; other 166CPU intensive processes on the same machine can reduce interactive 167response time within the X server. The dispatch loop can now 168calculate an approximate time value using the number of signals 169received. The granularity of the timer sets the scheduling jitter, 170at 20ms it's only occasionally noticeable. 171 172The changes to WaitForSomething and ReadRequestFromClient are 173straightforward, adjusting when select is called and avoiding 174setting isItTimeToYield too often. 175 176The dispatch loop changes are more extensive, now instead of 177executing requests from all available clients, a single client 178is chosen after each call to WaitForSomething, requests are 179executed for that client and WaitForSomething is called again. 180 181Each client is assigned a priority, the dispatch loop chooses the 182client with the highest priority to execute. Priorities are 183updated 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 197The effect of these changes is to both improve interactive application 198response and benchmark numbers at the same time. 199