为什么 CLR ThreadPool 工作线程使用 LIFO 顺序处理来自本地队列的任务?

Why does CLR ThreadPool worker thread use LIFO order to process tasks from the local queue?

背景:

当任务被非工作线程调度到线程池中的工作线程处理时,它们进入一个全局队列。工作线程使用这个全局队列来获取任务,以 FIFO(先进先出)的顺序进行处理。这是有道理的,因为最先安排的任务应该最先完成。

现在,如果工作进程正在处理任务并产生新的子任务,它们将存储在进程的本地队列中。当工作进程完成其当前任务时,它检查本地队列并使用 LIFO(后进先出)顺序从队列中提取任务。

[编辑] 资料来源:

  1. CLR via C#, 4th Edition by Jeffrey Richter(第 725 页)
  2. Microsoft's Task Scheduler Documentation

问题:

在本地队列中使用后进先出顺序的基本原理是什么?

这在Microsoft's documentation for the task scheduler中明确提到:

The local queues are accessed on last-in, first-out order (LIFO) in order to preserve cache locality and reduce contention.

乔·达菲也 discusses this more here。他说:

1) By executing the work most recently pushed into the queue in LIFO order, chances are that memory associated with it will still be hot in the cache.

2) By stealing in FIFO order, chances are that a larger “chunk” of work will be stolen (possibly reducing the chance of needing additional steals). The reason for this is that many work stealing workloads are divide-and-conquer in nature; in such cases, the recursion forms a tree, and the oldest items in the queue lie closer to the root; hence, stealing one of those implicitly also steals a (potentially) large subtree of computations that will unfold once that piece of work is stolen and run.