Linus Torvalds (torvalds.delete@this.linux-foundation.org) on January 4, 2020 12:31 pm wrote:
> Malte Skarupke (malteskarupke.delete@this.web.de) on January 4, 2020 11:22 am wrote:
> > Case 3 is the same situation, thread C is still not being run
> > even though fifteen other threads are calling yield().
>
> The problem with that is "yield" is pretty much undefined. The definition of it is literally
> about single queue of a real-time behavior with a real-time scheduler with priorities.
>
> But that "definition" has almost nothing to do with actual usage. There are various random
> people who use it, and some might use it for locking, while some use it for other things.
>
> What you want to use it for is "schedule the right process". But you don't even
> know what the right process is, or if you do you don't tell the system (because sched_yield()
> literally doesn't have that interface), so the kernel has to guess.
>
> In some cases, "sched_yield()" is basically used by processes that say "I'm CPU-intensive, but I'm not important
> for latency, and I don't want to cause problems for others". You'll find various random GUI programs doing
> that because they are threaded, and one thread does things like update the screen, while another thread does
> calculations. The calculation loop (which is still important, just not latency-critical) might have "sched_yield()
> in it as a cheap way of saying "maybe there's a more important UI event going on".
>
> In other cases, it's a performance optimization, where somebody says "I have done my part of the work and
> written it out, now I'm yielding because there's another user that is likely to want to use it, and that other
> user is actually the more heavy CPU hog and should run before I start generating more data for it".
>
> And in others, it's because they are actually using real-time scheduling - perhaps on dedicated CPU doing the
> true Hard real-time kinds of things - and depend on the FIFO definition within their priority group.
>
> That's the defined usage, but even that is really defined only in the traditional UP sense
> of "there is one process running at a time, and we have one single queue of them".
>
> End result: sched_yield() is basically historical garbage. It's often literally wrong even for the defined
> usage because times have moved on from that whole "we run one thing at a time" long long ago. If your
> RT system actually has multiple concurrent threads (as opposed to being limited to a dedicated CPU) it's
> not really all that well-defined even there. But at least there you can still pretend it is.
>
> So what happens? Pretty much every single use of sched_yield() is some random person
> doing something wrong, and they have added it randomly to their load based on the random
> timing behavior on their machine. They may even have done extensive timings on a benchmark
> of their load in order to find exactly where they should yield.
>
> And then the system topology changes, and you have a hundred other sched_yield() users that
> use it for what they tuned things for, and their load behavior is very different indeed...
>
> In other words, if you think your locking should depend on 'sched_yield()', you're simply wrong.
>
> What do you think "sched_yield()" should do in a NUMA environment where your have 'N' NUMA
> domains, and each NUMA domain has 'M' cores? Perhaps totalling hundreds (or even thousands)
> of cores in total, some running your threads, some running something else entirely?
>
> And the process you want it to wake up is on another core entirely, possibly in a different
> NUMA domain, but that other core is right now running something else? Most people who use "sched_yield()"
> expect it to be a very light-weight operation. You said so yourself in your blog post, since
> you timed it. They expect it to be a light-weight operation exactly because they (incorrectly)
> think it's trivial, and they have literally tuned their load for that case.
>
> In fact, the most probable historical use of "sched_yield()" is because they wrote the
> code twenty years ago, really only did have one single CPU, and they had latency issues
> and did that whole "I want to make sure that if there's a UI process, it gets to run".
>
> But even a regular desktop machine today might have 8 cores and 16 threads, and now one of them has a thread
> that says "Hmm, I have nothing to do, but I can't sleep, so I want to randomly yield to somebody else".
>
> Do you think, for example, that the system should do a very expensive "check every single CPU thread to
> see if one of them has a runnable thread but is running something else, and break the CPU affinity of that
> thread and bring it to this CPU because I have a thread that says 'I'm not important' right now".
>
> So yes, that other thread isn't running right now, but bringing it to this
> CPU might slow it down enormously because now all the caches are gone because
> all the historical data it was working on is in another NUMA domain.
>
> But that would actually be the optimal thing for your locking case. You literally want to find that
> special other runnable thread (but not really any thread - you want to magically the one that isn't
> in a loop doing "yield" and wasting CPU time) that might have run on another CPU, and say "I want 'yield'
> to waste resources to move that thread to my core now, because my core thinks it's done".
>
> And you want to do that regardless of what anybody else used sched_yield() for?
>
> See how simplistic - and self-centered - your expectation is?
>
> And all because you did locking fundamentally wrong.
>
> Yes, it turns out that certain simple schedulers get exactly the behavior you want. The best way
> to get exactly your behavior is to have a single run-queue for the whole system, and make 'sched_yield()'
> always put the thread at the back of that run-queue, and pick the front one instead.
>
> IOW, for your bad, simplistic, and incorrect locking, the optimal scheduler is a stupid one
> that does not try to take any kind of CPU cache placement into account, does not try to at all
> optimize the run-queues to be thread-local, and just basically treats the scheduling decision
> as if we were still running one single CPU core, and that CPU had no cache locality issues.
>
> Guess what? The scheduler that your benchmark thinks is "optimal" is likely the worst of the bunch
> in a lot of other circumstances. But you have a simple benchmark, you have a clear and simple world-view,
> and you think that because of that, your benchmark is meaningful and not giving random numbers, but
> meaningful numbers where low numbers of your benchmark means that the scheduler is "good".
>
> When pretty much exactly the reverse is the case, because your world-view was
> not "simple", it was "simplistic" - to the point of being actively incorrect.
>
> See what I'm trying to explain here?
>
> The fact is, doing your own locking is hard. You need to really understand the issues, and you need to not
> over-simplify your model of the world to the point where it isn't actually describing reality any more.
>
> And no, any locking model that uses "sched_yield()" is simply garbage. Really. If you use
> "sched_yield()" you are basically doing something random. Imagine what happens if you use
> your "sched_yield()" for locking in a game, and somebody has a background task that does
> virus scanning, updates some system DB, or does pretty much anything else at the time?
>
> Yeah, you just potentially didn't just yield cross-CPU, you were yiedling
> to something else entirely that has nothing to do with your locking.
>
> sched_yield() is not acceptable for locking. EVER. Not unless you're
> en embedded system running a single load on a single core.
>
> If I haven't convinced you of that by now, I don't know what I can say.
>
> Good locking simply needs to be more directed than what "sched_yield()" can ever give you outside of a UP
> system without caches. It needs to actively tell the system what you're yielding to (and optimally it would
> also tell the system about whether you care about fairness/latency or not - a lot of loads don't).
>
> But that's not "sched_yield()" - that's something different. It's generally something like std::mutex,
> pthread_mutex_lock(), or perhaps a tuned thing that uses an OS-specific facility like "futex", where
> you do the nonblocking (and non-contended) case in user space using a shared memory location, but when
> you get contention you tell the OS what you're waiting for (and what you're waking up).
>
> Btw, locking can be simple too. If you do a lot of work, and the locking is something "occasional",
> you can use things like just passing a token over a pipe (or even a network connection) as your locking
> mechanism. Yes, the individual locking events end up being somewhat expensive, and it doesn't work
> very well at all for what is one very common case - no locking really needed at all because there's
> really only one active thread, but it can actually be a very simple and effective model.
>
> It turns out people get even that simple model wrong (passing tokens around in a pipe
> is exactly what the GNU make "jobserver" code does as a kind of "counting semaphore"
> implementation), and we found a bug in that user-space jobserver locking just last
> month because it got exposed when we tried to make the kernel more efficient.
>
> But at least that was a conceptually very simple model for doing locking: you create what is
> basically a counting semaphore by initialize a pipe with N characters (where N is your parallelism
> for the semaphore), and then anybody who wants to get the lock does a one-byte read() call
> and anybody who wants to release the lock writes a single byte back to the pipe.
>
> Simple, effective, and works even across processes. It doesn't even perform all that horribly
> because read/write is pretty simple in the end - but it's a system call for each lock/unlock,
> which is totally unacceptable if you compare to something like a shared memory location
> that you can just use a single atomic CPU operation on, of course.
>
> But again, depending on what your locking requirements are, that pipe (or even TCP
> socket) may actually be the right thing. It has advantages in that it can work in
> situations where that "we're all threads that share the same memory" isn't true.
>
> And it can actually out-perform your sched_yield() model.
>
> (Side note: the optimization I did in the kernel was to make the wakeup for a pipe write-to-read operation
> really be directed to just one of the waiting writers. And it turned out that the GNU make jobserver
> had a race that means that sometimes it would lose tokens for a while. And the kernel doing that nice
> targeted wakeup ended up making that race trigger all the time. So what currently happens is that if
> you have one writer and ten readers of the pipe, that one writer will wake up all the readers. But
> that will still work perfectly well for your benchmark, because you didn't overcommit a lot of people
> locking, I think, so you basically don't much see the worst-case thundering-herd issues).
>
> So sadly, I can report that the pipe-based locking isn't fair, and won't
> have great latencies for that reason, because we're working around a bug
> in user space where that fairness caused horrendous performance problems.
>
> Dealing with reality is hard. It sometimes means that you need to make your mental model for how locking
> needs to work a lot more complicated. And sometimes it means that you need to keep your OS kernel doing
> stupid things because people inadvertently depended on the timing of said stupid things.
>
> Which, as mentioned, is a problem for sched_yield() too. Lots of users, all of which are basically buggy-by-definition,
> and all you can do is a bad half-arsed job of trying to make it "kind of work".
>
> Reality is messy.
>
> Linus

Gotta agree with all that. In fact having worked for a while on a TP system I tend to the fascist side on enforcing proper handling of locks. You want the system to know if a process is holding a lock and what other processes are waiting. This will enable it to up the priority if needed and cope with errors better. The only pure yield like operation that should ever be done is deep in the kernel when the only worthwhile thing to do is idle waiting for an event.