linux-kernel - Re: periods and deadlines in SCHED

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: <1280823360.1923.419.camel@laptop>
Date:	Tue, 03 Aug 2010 10:16:00 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Bjoern Brandenburg <bbb@...il.unc.edu>
Cc:	Raistlin <raistlin@...ux.it>,
	linux-kernel <linux-kernel@...r.kernel.org>,
	Song Yuan <song.yuan@...csson.com>,
	Dmitry Adamushko <dmitry.adamushko@...il.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Nicola Manica <nicola.manica@...i.unitn.it>,
	Luca Abeni <lucabe72@...il.it>,
	Claudio Scordino <claudio@...dence.eu.com>,
	Harald Gustafsson <harald.gustafsson@...csson.com>,
	bastoni@...unc.edu, Giuseppe Lipari <lipari@...is.sssup.it>,
	rostedt <rostedt@...dmis.org>,
	Gregory Haskins <ghaskins@...ell.com>
Subject: Re: periods and deadlines in SCHED_DEADLINE

On Sun, 2010-07-11 at 08:46 +0200, Bjoern Brandenburg wrote:
> I'd be hesitant to just assume that it "approximates G-EDF"
> sufficiently well to apply any of the published G-EDF tests.

OK, suppose that for each cpu we keep the earliest and next-earliest
deadline in a table. Then on wakeup (job release) we pick the cpu with
the currently last deadline to preempt (we push the task).

On sleep (job completion) we look for the earliest among all
next-earliest deadlines to select the next runnable task (we pull the
task).

If we serialize all this using one big lock around this [ {earliest,
next-earliest} ] table, we've basically implemented G-EDF, agreed?

Now replace that global lock with an algorithm that looks at the table,
finds the last-earliest or earliest-next-earliest in a lock-less
fashion, then locks the target cpu's rq->lock, verifies the result and
either continues or tries again.

So we replace the global lock with cmpxchg like loops using 2 per-cpu
locks. Our current SCHED_FIFO balancer does just this and is found to be
a very good approximation of global-fifo (iirc there's one funny case,
but I can't remember, maybe Steve or Gregory can remember the details).

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