Re: [CFT][PATCH] new scheduler policy

Haoqiang Zheng
2003-08-25T15:12:04Z

Nick Piggin wrote:

>
>
> Haoqiang Zheng wrote:
>
>> William Lee Irwin III wrote:
>>
>>> On Tue, Aug 19, 2003 at 12:24:17PM +0200, Mike Galbraith wrote:
>>>
>>>
>>>> Test-starve.c starvation is back (curable via other means), but
>>>> irman2 is utterly harmless. Responsiveness under load is very nice
>>>> until I get to the "very hefty" end of the spectrum (expected).
>>>> Throughput is down a bit at make -j30, and there are many cc1's
>>>> running at very high priority once swap becomes moderately busy.
>>>> OTOH, concurrency for the make -jN in general appears to be up a
>>>> bit. X is pretty choppy when moving windows around, but that
>>>> _appears_ to be the newer/tamer backboost bleeding a kdeinit thread
>>>> a bit too dry. (I think it'll be easy to correct, will let you
>>>> know if what I have in mind to test that theory works out). Ending
>>>> on a decidedly positive note, I can no longer reproduce priority
>>>> inversion troubles with xmms's gl thread, nor with blender.
>>>> (/me wonders what the reports from wine/game folks will be like)
>>>>
>>>
>>>
>>>
>>> Someone else appears to have done some work on the X priority inversion
>>> issue who I'd like to drag into this discussion, though there doesn't
>>> really appear to be an opportune time.
>>>
>>> Haoqiang, any chance you could describe your solutions to the X
>>> priority
>>> inversion issue?
>>>
>>>
>>> -- wli
>>>
>>>
>> I didn't follow the whole discussion. But from what wli has described
>> to me, the problem (xmms skips frames) is pretty like a X scheduler
>> problem.
>>
>> X server works like this:
>> "The X server uses select(2) to detect clients with pending input.
>> Once the set of clients with pending input is determined, the X
>> server starts executing requests from the client with the smallest
>> file descriptor. Each client has a buffer which is used to read some
>> data from the network connection, that buffer can be resized to hold
>> unusually large requests, but is typically 4KB. Requests are executed
>> from each client until either the buffer is exhausted of complete
>> requests or after ten requests. After requests are read from all of
>> the ready clients, the server determines whether any clients still
>> have complete requests in their buffers. If so, the server foregoes
>> the select(2) call and goes back to processing requests for those
>> clients. When all client input buffers are exhausted of complete
>> requests, the X server returns to select(2) to await additional data. "
>> --- Keith Packard, "Efficiently Scheduling {X} Clients", FREENIX-00,
>>
>> Basically, the X server does a round robin for all the clients with
>> pending input. It's not surprising that xmms skip frames when there
>> are a lot of "heavy" x requests pending. I am not sure if this the
>> cause of the problem that you guys are talking about. But anyway, if
>> this the cause, here is my 2 cents:
>>
>> I think the scheduler of X server has to be "smarter". It has to know
>> which X client is more "important" and give the important client a
>> high priority, otherwise the priority inversion problem will be
>> un-avoidable. Suppose the system can provide something like
>> "get_most_important_client()" , the X server can be fixed this way:
>> The X server calls get_most_important_client() before it starts to
>> handle an X request. If the return is not NULL, it handles the
>> request from this "important" client. This way, an "important" x
>> client only need to wait a maximun of a single X request (instead of
>> unlimited number of X requests) to get served.
>>
>> The problem now is how can we decide which X client is the most
>> important? Well, I guess there are a lot of solutions. I have a
>> kernel based solution to this question. The basic idea is: keep
>> the processes blocked by X server in the runqueue. If a certain
>> process (P) of this kind is scheduled, the kernel switch to the X
>> server instead. If the X server get scheduled in this way, it can
>> handle the X requests from this very process (P). If you have
>> interest, you can take a look at
>> http://www.ncl.cs.columbia.edu/publications/cucs-005-03.pdf .
>>
>> Let me know your comments...
>
>
>
>
> Very interesting. I think X could be smarter about scheduling maybe
> quite easily by maintaining a bit more state, say a simple dynamic
> priority thing, just to keep heavy users from flooding out the
> occasional users. But AFAIK, the X club is pretty exclusive, and you
> would need an inside contact to get anything done.
>
> There are still regressions in the CPU scheduler though.
>
> Your last point didn't make sense to me. A client still needs to get CPU
> time. I guess I should look at the paper. Having to teach the scheduler
> about X doesn't sit well with me. I think the best you could hope for
> there
> _might_ be a config option _if_ you could show some significant
> improvements not attainable by modifying either X or the kernel in a more
> generic manner.
>
Yes, this is exactly what Keith Packard did in this paper:
http://keithp.com/~keithp/talks/usenix2000/smart.html . The X scheduler
is certainly "smarter" by giving a higher priority to more interactive X
clients. But I think guessing the importance of a client by the X server
itself is flawed because the X server doesn't have a whole picture of
the system. For example, it doesn't know anything about the "nice" value
of a process. I think the kernel is in the best position to decide
which process is more important. That's why I proposed kernel based
approach.

>
> Your last point didn't make sense to me. A client still needs to get CPU
> time. I guess I should look at the paper. Having to teach the scheduler
> about X doesn't sit well with me. I think the best you could hope for
> there
> _might_ be a config option _if_ you could show some significant
> improvements not attainable by modifying either X or the kernel in a more
> generic manner.
>
My paper is about solving the priority inversion problem in general, not
specific to the X server. But it can be used in this case.

-- Haoqiang