linux-kernel - RE: [REPORT] cfs-v4 vs sd-0.44

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]

Date:	Mon, 23 Apr 2007 17:59:06 -0700
From:	"Li, Tong N" <tong.n.li@...el.com>
To:	"Jeremy Fitzhardinge" <jeremy@...p.org>,
	"Linus Torvalds" <torvalds@...ux-foundation.org>
Cc:	"Ingo Molnar" <mingo@...e.hu>, "Nick Piggin" <npiggin@...e.de>,
	"Juliusz Chroboczek" <jch@....jussieu.fr>,
	"Con Kolivas" <kernel@...ivas.org>, "ck list" <ck@....kolivas.org>,
	"Bill Davidsen" <davidsen@....com>, "Willy Tarreau" <w@....eu>,
	"William Lee Irwin III" <wli@...omorphy.com>,
	<linux-kernel@...r.kernel.org>,
	"Andrew Morton" <akpm@...ux-foundation.org>,
	"Mike Galbraith" <efault@....de>,
	"Arjan van de Ven" <arjan@...radead.org>,
	"Peter Williams" <pwil3058@...pond.net.au>,
	"Thomas Gleixner" <tglx@...utronix.de>, <caglar@...dus.org.tr>,
	"Gene Heskett" <gene.heskett@...il.com>
Subject: RE: [REPORT] cfs-v4 vs sd-0.44

I don't know if we've discussed this or not. Since both CFS and SD claim
to be fair, I'd like to hear more opinions on the fairness aspect of
these designs. In areas such as OS, networking, and real-time, fairness,
and its more general form, proportional fairness, are well-defined
terms. In fact, perfect fairness is not feasible since it requires all
runnable threads to be running simultaneously and scheduled with
infinitesimally small quanta (like a fluid system). So to evaluate if a
new scheduling algorithm is fair, the common approach is to take the
ideal fair algorithm (often referred to as Generalized Processor
Scheduling or GPS) as a reference model and analyze if the new algorithm
can achieve a constant error bound (different error metrics also exist).
I understand that via experiments we can show a design is reasonably
fair in the common case, but IMHO, to claim that a design is fair, there
needs to be some kind of formal analysis on the fairness bound, and this
bound should be proven to be constant. Even if the bound is not
constant, at least this analysis can help us better understand and
predict the degree of fairness that users would experience (e.g., would
the system be less fair if the number of threads increases? What happens
if a large number of threads dynamically join and leave the system?).

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