dos -> unix

1 files changed, 204 insertions, 204 deletions

diff --git a/xorg-server/doc/smartsched b/xorg-server/doc/smartsched
index 466408431..057a759fd 100644
--- a/xorg-server/doc/smartsched
+++ b/xorg-server/doc/smartsched
@@ -1,204 +1,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: $

+			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: $