linux-kernel - Re: RFC for a new Scheduling policy/class in the Linux-kernel

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:	Tue, 14 Jul 2009 08:48:26 -0600
From:	"Chris Friesen" <cfriesen@...tel.com>
To:	Raistlin <raistlin@...ux.it>
CC:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Douglas Niehaus <niehaus@...c.ku.edu>,
	Henrik Austad <henrik@...tad.us>,
	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Bill Huey <billh@...ppy.monkey.org>,
	Linux RT <linux-rt-users@...r.kernel.org>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	"James H. Anderson" <anderson@...unc.edu>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ted Baker <baker@...fsu.edu>,
	Dhaval Giani <dhaval.giani@...il.com>,
	Noah Watkins <jayhawk@....ucsc.edu>,
	KUSP Google Group <kusp@...glegroups.com>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Giuseppe Lipari <lipari@...is.sssup.it>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

Raistlin wrote:

> Now, all the above is true on UP setups. Extending to SMP (m CPUs) and
> considering the first part of my draft proposal, i.e., having the
> proxying tasks busy waiting (would say "spinning", but that busy wait is
> interruptible, preemptable, etc.) on some CPU while their proxy is being
> scheduled, we are back to the case of having the m highest entity
> running... And thus we are happy!


> Well, so and so. I fact, if you want (and we want! :-D) to go a step
> further, and consider how to remove the --possibly quite log on Linux as
> Peter said-- wasting of CPU time due to busy waiting, what you can do is
> to actually block a proxying task, instead of having it "spinning", so
> that some other task in some other group, which may not be one of the m
> highest prio ones, can reclaim that bandwidth... But... Ladies and
> gentlemen, here it is: BLOCKING. Again!! :-(

Let's call the highest priority task A, while the task holding the lock
(that A wants) is called B.  Suppose we're on an dual-cpu system.

According to your proposal above we would have A busy-waiting while B
runs with A's priority.  When B gives up the lock it gets downgraded and
A acquires it and continues to run.

Alternately, we could have A blocked waiting for the lock, a separate
task C running, and B runs with A's priority on the other cpu.  When B
gives up the lock it gets downgraded and A acquires it and continues to run.

>From an overall system perspective we allowed C to make additional
forward progress, increasing the throughput.  On the other hand, there
is a small window where A isn't running and it theoretically should be.
  If we can bound it, would this window really cause so much difficulty
to the schedulability analysis?

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