任务调度器(Task Scheduler)在运行时调度和协调任务。任务是执行特定工作的工作单元。任务调度器负责处理在拥有多个计算资源的计算机上高效调度任务所涉及的细节。
Windows 操作系统提供了一个抢占式内核态调度器:它是一种基于优先级的轮询(round-robin)机制,让每个任务在给定的时间段内独占访问某个计算资源,然后切换到另一个任务。尽管这种机制提供了公平性(每个线程都能向前推进),但它以效率为代价。例如,许多计算密集型算法并不需要公平性;相反,让相关任务在最短的总时间内完成更为重要。协作式调度使应用程序能够更高效地调度工作。
协作式调度是一种机制:让每个任务独占访问某个计算资源,直到任务完成或任务主动让出对资源的访问权。
用户态协作式调度器使应用程序代码能够自行做出调度决策。由于协作式调度让许多调度决策由应用程序做出,它大大减少了与内核态同步相关的开销。
并发运行时(Concurrency Runtime)将协作式调度与操作系统的抢占式调度结合使用,以最大限度地利用处理资源。
调度器设计
并发运行时提供了 Scheduler 接口,用于实现适应应用程序需求的特定调度器。
让我们找出实现该接口的类;为此,我们可以执行以下 CQL 查询:
并发运行时提供了调度器的两个实现:ThreadScheduler 和 UMSThreadScheduler。
如下面的依赖图所示,调度器引用了许多抽象类来实现其目标:
让我们探究调度器所使用的每个抽象类的作用;为此,我们将讨论它们的职责。
任务调度器承担着三大主要职责:
1. 获取资源(处理器、核心、内存):
创建调度器时,它会向运行时资源管理器请求资源,如这篇文章所述。
调度器通过 IResourceManager、ISchedulerProxy 和 IScheduler 接口与资源管理器通信。创建调度器时,我们可以指定其策略。
Concurrency::PolicyElementKey 枚举定义了与任务调度器关联的策略键。
这里有一篇文章解释了每个策略键的用途及其默认值。
下面这张依赖图展示了我们创建调度器时发生的事情:
如果不存在调度器,并发运行时会通过调用 GetDefaultScheduler 方法创建一个默认调度器,并使用默认策略。任务调度器允许应用程序使用一个或多个调度器实例来调度工作,应用程序也可以调用 Scheduler::Create 添加另一个使用特定策略的调度器。
调度器与资源管理器之间的以下交互,说明了资源分配中涉及的每个接口的作用。
- 请求资源分配:
- 从资源管理器获取资源:
2. 管理任务队列:
调度器创建完成后,就可以向它分配任务执行;调度器将这些任务存储在队列中。为了增强类的内聚性,队列不由 ThreadScheduler 类直接管理,而是由 ScheduleGroupBase 类管理。
调度组(schedule group)将相关的任务关联或分组在一起。每个调度器都有一个或多个调度组。当您需要任务之间具有高度的局部性时——例如当一组相关任务在同一处理器节点上执行会受益时——请使用调度组。
如下图所示,运行时提供了两种 ScheduleGroup:FairScheduleGroup 和 CacheLocalScheduleGroup。正如后文将解释的,在这两种组之间的选择会影响调度器用来选择下一个待执行任务的算法。
每个调度器对每个调度节点都有一个默认调度组。运行时为每个处理器封装或非一致性内存架构(NUMA)节点创建一个调度节点。如果您没有显式地将任务与某个调度组关联,调度器会选择将任务加入哪个组。
如下面的依赖图所示,SchedulingRing 负责管理调度组:它包含一个组的列表并负责创建它们。
调度组包含三种队列:
1. FIFO 队列
此队列包含轻量级任务。轻量级任务类似于您提供给 Windows API CreateThread 函数的函数。因此,当您改造现有代码以使用并发运行时的调度功能时,轻量级任务非常有用。
轻量级任务由 RealizedChore 类表示,而调度组的 FIFO 队列由 m_realizedChores 字段表示。
让我们搜索直接使用该队列的方法:
因此,我们可以通过调用 ScheduleGroupBase::ScheduleTask 或 Scheduler::ScheduleTask 向组中添加轻量级任务。
这里有一篇有趣的文章介绍轻量级任务。
2. 工作窃取(work stealing)队列:
与调度组关联的 FIFO 队列只有一个,但调度组引用了一组工作窃取队列:每个工作线程都有自己的本地队列。
附加到调度器的线程称为执行上下文(execution context),简称上下文,因此这个本地队列实际上与 Context 类相关联。
Context 类为执行上下文提供了编程抽象,并提供了协作式阻塞、解除阻塞和让出当前上下文的能力。
为了验证只有 Context 会创建这种队列,让我们搜索直接访问 m_workQueues 字段的方法。
上下文负责创建这个队列,每个上下文都有一个与之关联的本地工作窃取队列。
为了说明工作窃取算法的行为,假设我们有两个分配给调度器的工作线程。
如上所述,每个工作线程都有自己的本地队列。
工作线程 1 的队列中有三个任务:任务 3 和任务 4 正在等待执行,而任务 5 正在运行。
Dispatch 方法发现队列为空,于是任务 3 被从它原来的队列中移动——或者说“窃取”——过来,分配给可用的工作线程。
如何创建由工作窃取队列管理的任务?为了找到答案,让我们搜索间接调用 CreateWorkQueue 方法的方法。
如这张依赖图所示,这类任务可以使用 task_group 类来创建。
相比使用 Scheduler::ScheduleTask 创建轻量级任务,使用 task_group 添加新任务更为可取,因为工作窃取算法能更好地利用分配给调度器的虚拟处理器。
不过,对于轻松迁移使用 CreateThread API 的现有代码,ScheduleTask 可能更合适。
3. 解除阻塞上下文队列
Context类让您能够阻塞或让出当前执行上下文。当当前上下文因资源不可用而无法继续时,阻塞或让出就很有用。Context::Block 方法阻塞当前上下文。被阻塞的上下文会让出其处理资源,以便运行时执行其他任务。Context::Unblock 方法解除被阻塞上下文的阻塞。
当上下文被解除阻塞、可以执行时,它会被加入可运行上下文队列;该队列由 m_runnableContexts 字段表示。
下面这张依赖图展示了上下文被加入可运行队列的几种情况:
因此,上下文在被解除阻塞时,或虚拟处理器从调度器中退役时,会被加入队列。
3. 分发任务:
调度器尝试查找要执行的工作;工作可以是:
- 解除阻塞的上下文。
- 轻量级任务。
- 工作窃取队列中的任务。
如上所述,所有这些工作都存储在由调度组管理的队列中,而每个组又由一个调度环(scheduling ring)管理。
当一个虚拟处理器被分配给调度器时,会创建一个 ThreadProxy 类并与该处理器关联,创建之后会调用 ThreadProxy 的 Dispatch 方法。如下面的依赖图所示,也如前面所解释的,并发运行时使用抽象类来保持低耦合,实际调用的分发实现取决于运行时选择的实现;这一选择由调度器策略决定。
Dispatch 的具体实现会调用执行上下文的 Dispatch 方法。
下面这张依赖图展示了 Context::Dispatch 方法的具体实现所调用的方法:
因此,查找下一个待执行工作的算法由 WorkSearchContext 类实现。
让我们找出 WorkSearchContext 为履行职责而直接使用的所有类:
WorkSearchContext 的职责是提供一个待执行的 WorkItem;它可以是 InternalContextBase、RealizedChore 或 _UnrealizedChore。
为了更好地理解这些类之间的协作,让我们搜索 WorkSearchContext 直接使用的方法:
因此,WorkSearchContext 通过 SchedulerBase 的方法遍历 SchedulingRing 和 ScheduleGroup 类。
对于每个 ScheduleBase,我们查找 RunnableContext、RealizedChore 或 UnrealizedChore。
WorkSearchContext 类由 VirtualProcessor 类创建;如下面的依赖图所示,所用算法在 VirtualProcessor 初始化时指定——为此,它会向调度器询问 SchedulingProtocol,后者描述了调度器将使用的调度算法。
WorkSearchContext 通过接收 Algorithm 枚举的一个值来获知应使用的算法。
因此,该类实现了两种查找工作的算法:
- 缓存局部性(Cache Local)算法:
该算法先在当前调度组内查找可运行的上下文,然后是已实现任务(realized chore),再是未实现任务(unrealized chore);如果当前调度组中没有更多工作,它就在同一调度环中的下一个组里查找。一旦当前调度环中的工作耗尽,它就转向下一个调度环。
因此,调度器倾向于先继续执行当前调度组内的任务,然后再转向另一个调度组。
该算法由 WorkSearchContext::SearchCacheLocal 方法实现;如这张依赖图所示,该方法会调用其他方法来查找可运行上下文、RealizedChore 或 _UnrealizedChore。
该算法的另一个特点是:解除阻塞的上下文按虚拟处理器进行缓存,并且通常由解除其阻塞的那个虚拟处理器以后进先出(LIFO)的顺序调度。
为了验证这一行为,下面是查找可运行上下文时所调用方法的依赖图:
这是未指定算法时调度器选择的默认算法。
- 公平(Fair)算法:
在这种情况下,调度器倾向于每执行完一个任务就在调度组之间轮询。解除阻塞的上下文通常按先进先出(FIFO)方式调度。虚拟处理器不会缓存解除阻塞的上下文。
该算法由 WorkSearchContext::SearchFair 方法实现;如这张依赖图所示,该方法会调用其他方法来查找可运行上下文、RealizedChore 或 _UnrealizedChore。
