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: <20070509202418.GE31925@holomorphy.com>
Date:	Wed, 9 May 2007 13:24:18 -0700
From:	William Lee Irwin III <wli@...omorphy.com>
To:	Srivatsa Vaddagiri <vatsa@...ibm.com>
Cc:	Ingo Molnar <mingo@...e.hu>, Mike Galbraith <efault@....de>,
	linux-kernel@...r.kernel.org,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Con Kolivas <kernel@...ivas.org>,
	Nick Piggin <npiggin@...e.de>,
	Arjan van de Ven <arjan@...radead.org>,
	Peter Williams <pwil3058@...pond.net.au>,
	Thomas Gleixner <tglx@...utronix.de>, caglar@...dus.org.tr,
	Willy Tarreau <w@....eu>,
	Gene Heskett <gene.heskett@...il.com>, Mark Lord <lkml@....ca>,
	tingy@...umass.edu, tong.n.li@...el.com
Subject: Re: Definition of fairness (was Re: [patch] CFS scheduler, -v11)

On Wed, May 09, 2007 at 11:32:05PM +0530, Srivatsa Vaddagiri wrote:
> 	I had a question with respect to the definition of fairness used, esp
> for tasks that are not 100% cpu hogs.
> Ex: consider two equally important tasks T1 and T2 running on same CPU and 
> whose execution nature is:
> 	T1 = 100% cpu hog
> 	T2 = 60% cpu hog (run for 600ms, sleep for 400ms)
> Over a arbitrary observation period of 10 sec, 
> 	T1 was ready to run for all 10sec
> 	T2 was ready to run for 6 sec
> Over this observation period, how much execution time should T2 get,
> under a "fair" scheduler?
> I was expecting both T2 and T1 to get 5 sec (50:50 split). Is this a
> wrong expectation of fairness?
> Anyway, results of this experiment (using testcase attached) is below.
> T2 gets way below its fair share IMO (under both cfs and sd).

It's not even feasible much of the time. Suppose your task ran for
100ms then slept for 900ms. It can't get more than 10% of the CPU in
any scheduler, work-conserving or not.

Second, anything that would credit tasks for sleep in such a manner
would flunk ringtest.c or otherwise analogues arranged to pass
feasibility checks.

Fairness applies only to running tasks. The fair share of CPU must be
granted while the task is running. As for sleep, it has to use its
fair share of CPU or lose it. The numerous of pathologies that arise
from trying to credit tasks for sleep in this fashion this are why
fairness in the orthodox sense I describe is now such a high priority.

However, it is possible to credit tasks for sleep in other ways. For
instance, EEVDF (which is very close to CFS) has a deadline parameter
expressing latency in addition to one expressing bandwidth that could,
in principle, be used for the purpose of crediting sleeping tasks. It's
not clear to me whether trying to use it for such purposes would be
sound, or, for that matter, whether tasks should receive latency
credits for sleep as opposed to other sorts of behaviors even if
utilizing the latency parameter for credits and bonuses for various
sorts of behavior is sound.


-- wli
-
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/

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ