Multi-core usage, threads, thread-pools

Question

I have some questions about multi-threaded programming and multi-core usage.

In particular I'm wondering how the operating system and/or framework (this is .NET) deals with cores that are heavily used.

Here's my questions regarding threads:

• When a new thread is spawned, what is the algorithm for assigning the thread to a particular core?
  1. Round-robin type of algorithm
  2. Random
  3. The currently least used core
• If not the currently least used core, would this type of code that determined this dwarf the typical use of a thread and thus just make matters worse?
• Are threads moved from one core to another during their lifetime? If so, is this to handle cores that for some reason gets "overused" and thus the operating system try to shuffle threads over to less used cores to help the system? If not, again, why not?

My final question, which is basically a reuse of the above, is about the .NET ThreadPool class, which handles things like .BeginInvoke and such. Does this class do any of this stuff? If not, why not, or should it?

Is there any way to tweak this handling, sort of hint at the operating system that this particular thread, please pay a bit more attention to it when you assign it a core, since I know it will use a lot of cpu. Would that make sense? Or would "a lot of cpu" just be relative and thus not really good enough?

Answer 1

When a new thread is spawned, what is the algorithm for assigning the thread to a particular core?

That depends entirely on the OS. And the answer is usually a heavily modified round-robin scheme. Every x milliseconds, a core is interrupted, and a new thread placed on it (so there is no "least used core". As long as there are threads ready to run, every core will have something to do).

In Windows, I believe the highest-prioritized thread/process is always selected for execution. (So if you have one process running at high priority on a single-core system, that process will potentially run 100% of the time, starving out every other process. Of course this only applies if that process never blocks, which is unlikely in the real world.

And of course, because a modern OS such as Windows is complex, there's a lot more to it. Certain processes are given preferential treatment from time to time, but as a rule of thumb, Windows will always pick high-priority processes (which is why you could pretty much freeze your computer by giving a process "realtime" priority back in the singlecore days)

Under Linux, lower-prioritized processes are regularly scheduled as well, just not as often.

But the best you can do is typically just assume that the OS will work out a fair scheme, and then try to play nice with the rest of the system. (Yield/block/sleep when you have nothing to do, allowing other threads to run).

Are threads moved from one core to another during their lifetime?

Of course. Imagine you have three threads running on a dualcore system. Show me a fair schedule that doesn't involve regularly moving threads between cores.

My final question, which is basically a reuse of the above, is about the .NET ThreadPool class, which handles things like .BeginInvoke and such. Does this class do any of this stuff? If not, why not, or should it? What stuff? Thread scheduling and choosing cores to run on? No, the threadpool is simply a mechanism to reuse threads for muliple tasks, instead of having to create a new thread for every single task, and then closing it afterwards.

Is there any way to tweak this handling, sort of hint at the operating system that this particular thread

That's what thread/process priority is for. If you have a thread that must get lots of CPU time, even when there are other CPU-intensive threads running, raise the thread's priority. But handle with care. Usually, there aren't many CPU-intensive threads running, which means that even at normal priority, you'll get 99.9% of the CPU time. As I said, Windows schedules higher-prioritized threads very aggressively, so only raise priority if you really mean it.

Answer 2

In addition to jalf's excellent and comprehensive answer, keep in mind that "Parallel Extensions" (which should be rolled into .NET 4.0) has a lot of code dedicated to allocating work (from queues) to cores evenly, including work stealing, and potentially nuggets like caring which core is "closest" to the memory in which the work resides.

So with .NET 4.0, using things like Parallel.For etc, you should get a lot of this for free. And in general, the OS is clever enough that it just works from the outsider's view. jalf has given a lot of details about what happens under the hood, but most of the time you don't need this level of detail, unless you are ironing out some performance issues with highly threaded code.