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]

Date:	Thu, 12 Apr 2007 10:15:41 -0400
From:	Buytaert_Steven@....com
To:	<andi@...stfloor.org>
Cc:	<linux-kernel@...r.kernel.org>
Subject: RE: sched_yield proposals/rationale

> -----Original Message-----
> > 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()
> 
> A lot of those are probably broken in some way agreed.

OK, so there are 2 options: 1) fix 100 spots or 2) ... ;-)

> [ about giving a thread its full slice quota after yielding ]
> With a particular sleep pattern it could get more CPU time.

I'm not a linux scheduler expert, but I don't understand this. Suppose 2 extreme situations:

1) I have full time slices and call yield, going to the expired list with again full times slices; this is IMHO a NOOP, i.e. fair.

2) I have only a single slice left, NOT yielding would get me to the expired list via scheduler_tick the next timer interrupt and I would get my full time slice quota. DO YIELD at that moment, will give me full time slice quota again (with my proposal). 

> 
> 3) Put the task in the expired list at a random position [...]
> > while (X--) { prev = current; current = current->next }
> 
> You would need to rename the scheduler to "sometimes O(1)" first @)

Again, agreed, but this tight loop would run in code cache completely. We could call it O(1.1) ;-) With a duffs device it would mean a few clock cycles per position.

> Besides - but I guess you're aware of it - any randomized algorithms tend
> to drive benchmarkers and performance analysts crazy because their
> performance
> cannot be repeated. So it's usually better to avoid them unless there is
> really no alternative.

That could already solve your concern from above. Statistically speaking, it will give them (benchmarkers) the smoothest curve they've ever seen.

Please be aware that I'm just exploring options/insight here. It is not something I intend to push inside the mainline kernel. I just want to find reasonable and logic criticism as you and some others have provided already. Thanks for that!

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/