"Fossies" - the Fresh Open Source Software Archive

Member "xorg-server-1.20.5/doc/smartsched" (30 May 2019, 7173 Bytes) of package /linux/misc/xorg-server-1.20.5.tar.bz2:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    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.