linux-kernel - RE: sched_yield proposals/rationale

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: <585DC2133F7C974F87D4EC432896F1720309F3DB@CORPUSMX10A.corp.emc.com>
Date:	Thu, 12 Apr 2007 09:05:25 -0400
From:	Buytaert_Steven@....com
To:	<andi@...stfloor.org>
Cc:	<linux-kernel@...r.kernel.org>
Subject: RE: sched_yield proposals/rationale

> -----Original Message-----
> From: Andi Kleen
> [ ... about use of sched_yield ...]
> On the other hand when they fix their code to not rely on sched_yield
> but use [...]

Agreed, but $ find . -name "*.[ch]" | xargs grep -E "yield[ ]*\(" | wc over
the 2.6.16 kernel yields 105 hits, note including comments... An interesting spot is e.g. fs/buffer.c free_more_memory()

> The only way I could think of to make sched_yield work the way they
> expect would be to define some way of gang scheduling and give
> sched_yield semantics that it preferably yields to other members
> of the gang. [...]

That would indeed make things too complicated.

> [about question 1]
> That would still not unbreak most applications I would suspect -- they
> will likely try to yield multiple times before using up a full time slice
> unless their event handlers are very compute intensive.

No, they only get 1 go again on the active queue, until they pass the proper exit to the expired queue via scheduler_tick. And they are enqueued at the end of the active queue with whatever slices they have left, thus fair.
 
> In general other subsystems (e.g. VM) had had quite bad experiences
> with similar "one more try" hacks -- they tend to be not robust and
> actually penalize some loads.
> 
> > 2) When a task is eventually put in the expired list in sched_yield,
> > give it back the full time slices round (as done in scheduler_tick), not > > with the remaining slices as is done now?
> 
> That would likely be unfair and exploitable.

I don't understand; how more unfair would it be than passing via scheduler_tick? Grabbing a resource with a single time slice left would be more unfair towards other tasks IMHO when you get moved to the expired list with the resource in still in your possession.

> 
> > 3) Put the task in the expired list at a random position, not at the end
> > is done now?
> 
> Sounds like an interesting approach, but to do it in O(1) you would
> need a new data structure with possibly much larger constant overhead.

Agreed, but not dramatic. Suppose you need to insert at position X, you would do, on the linked list after proper setup:

while (X--) { prev = current; current = current->next }

You could have a small duffs device to reduce the X-- checking overhead.

Thanks for the insight Andi!

Steven Buytaert
--
La perfection est atteinte non quand il ne reste rien ajouter, mais quand il ne reste rien à enlever. (Antoine de Saint-Exupéry)
-
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/