Stephen Toub - MSFT

One of the ways in which the Task Parallel Library achieves good performance is through “work-stealing”.  Work-stealing is supported in the .NET 4 ThreadPool for access through the Task Parallel Library and its default scheduler.  This manifests as every thread in the ThreadPool having its own queue for work; when that thread creates Tasks, by default these tasks are enqueued into the thread’s local queue, rather than into the global queue that a call to ThreadPool.QueueUserWorkItem would typically target.  When a thread goes in search for work to be executed, it starts with its local queue, an operation which enable some extra efficiencies due to improved cache locality, minimized contention, and so forth.  However, this logic also affects fairness.

A typical thread pool will have a single queue that maintains all of the work to be executed.  When threads in the pool are ready to process another work item, they’ll dequeue the work from the head of the queue, and when new work arrives to be executed by the pool, it’ll be enqueued onto the queue’s tail.  This provides a level of fairness between work items, in that work items that arrive first are more likely to be picked off and start executing first.

Work-stealing perturbs that fairness.  Threads external to the pool could be queuing up work, but if the threads in the pool are also generating work, the work generated by the pool will be preferred over the other work items, based on the search order employed by the threads in the pool (which start searching for work first with their local queues, only proceeding on to the global queue and then on to other threads’ queues if work wasn’t available locally).  This behavior is typically expected and even desired, in that if a work item being executed is generating more work, that generated work is typically considered part of the overall operation being processed, and thus it makes sense it would be preferred over other unrelated work.  For example, imagine a quicksort operation, where each recursive sort invocation potentially results in several further recursive calls; those calls, which in a parallel implementation are likely individual tasks, are part of the all-up sort operation.

Still, there are some scenarios where this default behavior is inappropriate, where fairness should be maintained between particular work items generated by threads in the pool and work items generated by other threads.  This is often the case for long chains of continuations, where the work generated isn’t considered part of the current work but rather a follow-on to the current work.  In those cases, you may want that follow-on work to be prioritized in a fair manner with other work in the system.  This is where TaskCreationOptions.PreferFairness can prove useful.

When a Task is scheduled to the default scheduler, the scheduler looks to see whether the current thread from which the Task is being queued is a ThreadPool thread that has its own local queue.  If it isn’t, the work item will be queued to the global queue.  If it is, the scheduler will also check whether the TaskCreationOptions value for the Task includes the PreferFairness flag, which is not on by default.  If the flag is set, even if the thread does have its own local queue, the scheduler will still enqueue the Task to the global queue rather than to the local queue.  In this manner, that Task will be considered fairly along with all other work items queued globally.

What was just described is the current implementation of the PreferFairness flag in the default scheduler.  The implementation could of course change, but what won’t change is the purpose of the flag: by specifying PreferFairness, you’re telling the system that this Task shouldn’t be prioritized just because it’s coming from a local queue.  You’re telling the system that you want the system to do its best to ensure that this Task is prioritized in a first-come, first-serve nature.

One other thing to note is that Task itself knows nothing of this flag; it’s just a flag set as an option on the Task.  It’s the scheduler that decides how it wants to handle this particular option, just as with TaskCreationOptions.LongRunning.  The default scheduler handles it as described above, but another scheduler (such as one you write) may do with this flag whatever it wants, including ignoring it.  Hence the naming “Prefer” rather than something stricter like “Guarantee”.


Discussion is closed.

Feedback usabilla icon