linux-kernel - [RFC] Extend Linux to support proportional-share scheduling

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-next>] [day] [month] [year] [list]

Date:	Tue, 5 Jun 2007 18:56:17 -0700
From:	"Li, Tong N" <tong.n.li@...el.com>
To:	<linux-kernel@...r.kernel.org>
Cc:	"Ingo Molnar" <mingo@...e.hu>, "Con Kolivas" <kernel@...ivas.org>,
	"Linus Torvalds" <torvalds@...ux-foundation.org>,
	"Arjan van de Ven" <arjan@...radead.org>,
	"Siddha, Suresh B" <suresh.b.siddha@...el.com>,
	"Barnes, Jesse" <jesse.barnes@...el.com>,
	"William Lee Irwin III" <wli@...omorphy.com>,
	"Bill Huey \(hui\)" <billh@...ppy.monkey.org>, <vatsa@...ibm.com>,
	<balbir@...ibm.com>, "Nick Piggin" <npiggin@...e.de>,
	"Bill Davidsen" <davidsen@....com>,
	"John Kingman" <kingman@...ragegear.com>,
	"Peter Williams" <pwil3058@...pond.net.au>,
	"Willy Tarreau" <w@....eu>, <seuler.shi@...il.com>
Subject: [RFC] Extend Linux to support proportional-share scheduling

Hi all,

I've ported my code to mainline 2.6.21.3. You can get it at
http://www.cs.duke.edu/~tongli/linux/. As I said before, the intent of
the patch is not to compete with CFS and SD because the design relies on
the underlying scheduler for interactive performance. The goal here is
to present a complementary design that can ensure stronger MP fairness,
which I think is lacking in the existing proposals. Here's a brief
overview of the design (I call it Trio for the lack of a better name).
Any comments or suggestions will be highly appreciated.

Trio extends the existing Linux scheduler with support for
proportional-share scheduling. It uses a scheduling algorithm, called
Distributed Weighted Round-Robin (DWRR), which retains the existing
scheduler design as much as possible, and extends it to achieve
proportional fairness with O(1) time complexity and a constant error
bound, compared to the ideal fair scheduling algorithm. The goal of Trio
is not to improve interactive performance; rather, it relies on the
existing scheduler for interactivity and extends it to support MP
proportional fairness.

Trio has two unique features: (1) it enables users to control shares of
CPU time for any thread or group of threads (e.g., a process, an
application, etc.), and (2) it enables fair sharing of CPU time across
multiple CPUs. For example, with ten tasks running on eight CPUs, Trio
allows each task to take an equal fraction of the total CPU time,
whereas no existing scheduler achieves such fairness. These features
enable Trio to complement the mainline scheduler and other proposals
such as CFS and SD to enable greater user flexibility and stronger
fairness.

  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/