From: Haoqiang Zheng <hzheng@cs.columbia.edu>
To: Nick Piggin <piggin@cyberone.com.au>
Cc: William Lee Irwin III <wli@holomorphy.com>,
Mike Galbraith <efault@gmx.de>,
linux-kernel <linux-kernel@vger.kernel.org>
Subject: Re: [CFT][PATCH] new scheduler policy
Date: Mon, 25 Aug 2003 11:11:43 -0400 [thread overview]
Message-ID: <3F4A272F.8000602@cs.columbia.edu> (raw)
In-Reply-To: <3F4A172F.8080303@cyberone.com.au>
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
next prev parent reply other threads:[~2003-08-25 15:12 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-08-19 1:53 [CFT][PATCH] new scheduler policy Nick Piggin
2003-08-19 2:35 ` William Lee Irwin III
2003-08-19 2:46 ` Nick Piggin
2003-08-19 2:59 ` Nick Piggin
2003-08-19 5:15 ` Matt Mackall
2003-08-19 5:34 ` Nick Piggin
2003-08-19 5:45 ` Matt Mackall
2003-08-19 10:24 ` Mike Galbraith
2003-08-19 13:40 ` Nick Piggin
2003-08-19 18:49 ` Mike Galbraith
2003-08-20 2:13 ` William Lee Irwin III
2003-08-25 13:47 ` Haoqiang Zheng
2003-08-25 14:03 ` Nick Piggin
2003-08-25 15:11 ` Haoqiang Zheng [this message]
2003-09-02 14:25 ` Pavel Machek
2003-09-08 13:40 ` Alan Cox
2003-09-08 14:20 ` Haoqiang Zheng
2003-09-08 14:28 ` Alan Cox
2003-09-08 15:10 ` Haoqiang Zheng
2003-08-22 8:55 ` Roger Luethi
2003-08-22 13:08 ` Nick Piggin
2003-08-22 15:11 ` Roger Luethi
2003-08-23 0:22 ` Nick Piggin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3F4A272F.8000602@cs.columbia.edu \
--to=hzheng@cs.columbia.edu \
--cc=efault@gmx.de \
--cc=linux-kernel@vger.kernel.org \
--cc=piggin@cyberone.com.au \
--cc=wli@holomorphy.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).