linux-kernel - Re: [patch 0/4] [RFC] Another proportional weight IO controller

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20081126222103.GD29897@gandalf.sssup.it>
Date:	Wed, 26 Nov 2008 23:21:03 +0100
From:	Fabio Checconi <fchecconi@...il.com>
To:	Nauman Rafique <nauman@...gle.com>
Cc:	Paolo Valente <paolo.valente@...more.it>,
	Vivek Goyal <vgoyal@...hat.com>,
	Ryo Tsuruta <ryov@...inux.co.jp>, linux-kernel@...r.kernel.org,
	containers@...ts.linux-foundation.org,
	virtualization@...ts.linux-foundation.org, jens.axboe@...cle.com,
	taka@...inux.co.jp, righi.andrea@...il.com, s-uchida@...jp.nec.com,
	fernando@....ntt.co.jp, balbir@...ux.vnet.ibm.com,
	akpm@...ux-foundation.org, menage@...gle.com, ngupta@...gle.com,
	riel@...hat.com, jmoyer@...hat.com, peterz@...radead.org
Subject: Re: [patch 0/4] [RFC] Another proportional weight IO controller

> From: Nauman Rafique <nauman@...gle.com>
> Date: Wed, Nov 26, 2008 11:41:46AM -0800
>
> On Wed, Nov 26, 2008 at 6:06 AM, Paolo Valente <paolo.valente@...more.it> wrote:
> > Fabio and I are a little bit worried about the fact that the problem
> > of working in the time domain instead of the service domain is not
> > being properly dealt with.  Probably we did not express ourselves very
> > clearly, so we will try to put in more practical terms.  Using B-WF2Q+
> > in the time domain instead of using CFQ (Round-Robin) means introducing
> > higher complexity than CFQ to get almost the same service properties
> > of CFQ.  With regard to fairness (long term) B-WF2Q+ in the time domain
> 
> Are we talking about a case where all the contenders have equal
> weights and are continuously backlogged? That seems to be the only
> case when B-WF2Q+ would behave like Round-Robin. Am I missing
> something here?
> 

It is the case with equal weights, but it is really a common one.


> I can see that the only direct advantage of using WF2Q+ scheduling is
> reduced jitter or latency in certain cases. But under heavy loads,
> that might result in request latencies seen by RT threads to be
> reduced from a few seconds to a few msec.
> 
> > has exactly the same (un)fairness problems of CFQ.  As far as bandwidth
> > differentiation is concerned, it can be obtained with CFQ by just
> > increasing the time slice (e.g., double weight => double slice).  This
> > has no impact on long term guarantees and certainly does not decrease
> > the throughput.
> >
> > With regard to short term guarantees (request completion time), one of
> > the properties of the reference ideal system of Wf2Q+ is that, assuming
> > for simplicity that all the queues have the same weight, as the ideal
> > system serves each queue at the same speed, shorter budgets are completed
> > in a shorter time intervals than longer budgets.  B-WF2Q+ guarantees
> > O(1) deviation from this ideal service.  Hence, the tight delay/jitter
> > measured in our experiments with BFQ is a consequence of the simple (and
> > probably still improvable) budget assignment mechanism of (the overall)
> > BFQ.  In contrast, if all the budgets are equal, as it happens if we use
> > time slices, the resulting scheduler is exactly a Round-Robin, again
> > as in CFQ (see [1]).
> 
> Can the budget assignment mechanism of BFQ be converted to time slice
> assignment mechanism? What I am trying to say here is that we can have
> variable time slices, just like we have variable budgets.
> 

Yes, it could be converted, and it would do in the time domain the
same differentiation it does now in the service domain.  What we would
lose in the process is the fairness in the service domain.  The service
properties/guarantees of the resulting scheduler would _not_ be the same
as the BFQ ones.  Both long term and short term guarantees would be
affected by the unfairness given by the different service rate
experienced by the scheduled entities.


> >
> > Finally, with regard to completion time delay differentiation through
> > weight differentiation, this is probably the only case in which B-WF2Q+
> > would perform better than CFQ, because, in case of CFQ, reducing the
> > time slices may reduce the throughput, whereas increasing the time slice
> > would increase the worst-case delay/jitter.
> >
> > In the end, BFQ succeeds in guaranteeing fairness (or in general the
> > desired bandwidth distribution) because it works in the service domain
> > (and this is probably the only way to achieve this goal), not because
> > it uses WF2Q+ instead of Round-Robin.  Similarly, it provides tight
> > delay/jitter only because B-WF2Q+ is used in combination with a simple
> > budget assignment (differentiation) mechanism (again in the service
> > domain).
> >
> > [1] http://feanor.sssup.it/~fabio/linux/bfq/results.php
> >
> > --
> > -----------------------------------------------------------
> > | Paolo Valente              |                            |
> > | Algogroup                  |                            |
> > | Dip. Ing. Informazione     | tel:   +39 059 2056318     |
> > | Via Vignolese 905/b        | fax:   +39 059 2056199     |
> > | 41100 Modena               |                            |
> > |     home:  http://algo.ing.unimo.it/people/paolo/       |
> > -----------------------------------------------------------
> >
> >
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/