Task Inlining - Query

Question

I was reading a question on difference between Thread and Task. I got this link to read on: Task Schedulers on MSDN.

But i got confused on this paragraph:

In some cases, when a Task is waited on, it may be executed synchronously on the Thread that is performing the wait operation. This enhances performance, as it prevents the need for an additional Thread by utilizing the existing Thread which would have blocked, otherwise. To prevent errors due to re-entrancy, task inlining only occurs when the wait target is found in the relevant Thread's local queue.

I want to understand the highlighted portion. Moreover, i local cache and global queue is also bit confusing... i am really curious to understand the TaskScheduler... Please help..

Answer 1

First, what are the local and global queues? This is an optimization of parallel processing in .Net 4.0. If you have lots of small Tasks and only one global queue, you get a lot of contention. That's because all threads are taking Tasks to process from the same place (the front of the global queue) and they are also placing new Tasks to the same place (the rear of the global queue). This requires lots of synchronization between the threads, which can affect performance.

The TPL in .Net 4.0 instead uses a technique called “work-stealing”: There one global queue, as before, and each ThreadPool worker thread (but not other threads) also has a local queue. If a non-worker thread starts a Task, it goes to the rear of the global queue, as before. If a worker thread starts a Task, it goes to the rear of its local queue.

Now to the interesting part. If a worker thread should process a new Task, it looks for it in these places (in this order):

1. the rear of its local queue
2. the front of the global queue
3. the front of other threads' local queues

The last part is why this is called “work-stealing”: a worker thread can “steal” a Task to process from another thread. A thread doesn't need to use synchronization to access the rear of its local queue, because no other thread can access it. And processing Tasks in LIFO order locally is also good for caching, because the last Task (and the data it uses) are the most likely to still be in the CPU cache.

For another explanation of all this (with pictures), see Work-Stealing in .NET 4.0.

---

What does this have to do inlining and reentrancy? I have no idea. I could understand why there could be a reentrancy problem if the Tasks used some thread static fields, but that has nothing to do with the queues. This problem could happen no matter which queue the inlined Task came from. I can't think of any situation where Tasks from the local queue are guaranteed to be safe to inline, but Tasks from other queues may not be safe.

Answer 2

Local/Global queue term originally comes from ThreadPool internals, TaskScheduler based on ThreadPool so terms are the same... Read more here on MSDN: ThreadPool Global Queue vs. Local Queues. Also svick's answer is greatly describes this point.

To prevent errors due to re-entrancy, task inlining only occurs when the wait target is found in the relevant Thread's local queue.

I believe waiting target is a WaitHandle instance on which a Thread is blocked. So if a WaitHandle instance is found in a lcoal queue of a waiting Thread - it would be automatically considered as inlined Task's local queue item.

And please reffer to Task.Wait and “Inlining” article by Stephen Toub for clear description of this process.