linux-kernel - Re: Definition of fairness (was Re: [patch] CFS scheduler, -v11)

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/