Re: [CFT][PATCH] new scheduler policy

[Haoqiang Zheng <hzheng@cs.columbia.edu>]

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