CN102027447A - 调度器中的局部任务集合 - Google Patents
调度器中的局部任务集合 Download PDFInfo
- Publication number
- CN102027447A CN102027447A CN2009801184584A CN200980118458A CN102027447A CN 102027447 A CN102027447 A CN 102027447A CN 2009801184584 A CN2009801184584 A CN 2009801184584A CN 200980118458 A CN200980118458 A CN 200980118458A CN 102027447 A CN102027447 A CN 102027447A
- Authority
- CN
- China
- Prior art keywords
- task
- scheduler
- processing resources
- resource
- release
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/48—Program initiating; Program switching, e.g. by interrupt
- G06F9/4806—Task transfer initiation or dispatching
- G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
- G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2209/00—Indexing scheme relating to G06F9/00
- G06F2209/48—Indexing scheme relating to G06F9/48
- G06F2209/483—Multiproc
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
- G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Debugging And Monitoring (AREA)
- Multi Processors (AREA)
Abstract
计算机系统的进程中的调度器包括对应于被分配到该调度器的每一处理资源的局部任务集合和至少一个一般任务集合。调度器将变为解锁的每一任务分配到与使得该任务变成解锁的处理资源对应的局部集合。当处理资源变为可用时,处理资源试图执行在对应的局部集合中最近最后添加的任务。如果在对应的局部集合中没有任务,则可用处理资源试图执行来自一般集合的任务。
Description
背景
在计算机系统中执行的进程可包括调度进程的任务以便在计算机系统中执行的任务调度器。这些调度器可用确定要如何执行进程的任务的各种算法来操作。然而,这些算法可能不能充分利用计算机系统的底层硬件拓扑结构。例如,这些算法可能不能充分利用带有存储器分层结构和多个处理器的计算机系统中的存储器局部性效应。结果,调度器可能不能优化计算机系统中的进程的执行。
概述
提供本概述是为了以简化的形式介绍将在以下详细描述中进一步描述的一些概念。本概述并不旨在标识所要求保护的主题的关键特征或必要特征,也不旨在用于限制所要求保护的主题的范围。
计算机系统的进程中的调度器包括对应于被分配到该调度器的每一处理资源的局部任务集合和至少一个一般任务集合。调度器将变为解锁的每一任务分配到与使得该任务变为解锁的处理资源相对应的局部集合。当处理资源变为可用时,处理资源试图执行相应的局部集合中最近最后添加的任务。如果在相应的局部集合中没有任务,则可用处理资源试图执行来自一般集合或另一处理资源的局部集合的任务。
附图简述
包括、合并在本发明书内并构成其一部分的附图提供了对各实施例的进一步理解。附图示出各实施例,并且与说明书一起用于解释本发明的原理。其他实施例和各实施例的许多预期优点将随着参考下面的详细描述进行更好的理解而得到认识。附图的元素不一定相对于彼此而缩放。相同的附图标记指代对应的类似部分。
图1是示出在运行时环境中带有局部任务集合的调度器的一实施例的框图。
图2是示出用于分配调度器中的执行上下文的方法的一实施例的流程图。
图3是示出用于选择执行上下文以供执行的方法的一实施例的流程图。
图4是示出供在调度器中使用的调度组的一实施例的框图。
图5A-5B是示出在带有局部任务集合的调度器中执行执行上下文的实施例的框图。
图6A-6B是示出被配置成实现包括带有局部任务集合的调度器的运行时环境的计算机系统的实施例的框图。
详细描述
在以下详细描述中,对附图进行了参考,附图构成了实施例的一部分且在其中作为示例示出了可在其中实践本发明的各特定实施例。就此,诸如“顶部”、“底部”、“前方”、“后方”、“前导”、“尾部”等的方向性术语参考正在描述的附图的方向来使用。因为实施例的各组件可位于多个不同的方向,所以方向性术语出于说明的目的来使用而不是限制。可以理解,可以使用其它实施例并且可以做出结构上或逻辑上的改变而不背离本发明的范围。因此,以下详细描述并不旨在限制,并且本发明的范围由所附权利要求来限定。
应该理解,此处描述的各示例性实施例的特征可相互组合,除非另外具体注明。
图1是示出运行时环境10的进程12中的任务调度器22的一实施例的框图。调度器22包括一组虚拟处理器32(1)-32(N)以及对应的局部任务集合44(1)-44(N),其中N是大于或等于二的整数且表示第N个虚拟处理器32或第N个局部集合44,如以下更详细地描述的。
运行时环境10表示计算机系统中的操作的运行时模式,如图6A和6B中示出且在下文中更详细地描述的计算机系统100的实施例100A和100B,其中该计算机系统正在执行指令。计算机系统从诸如图6A中示出且在下文中更详细描述的运行时平台122等运行时平台中生成运行时环境10。
运行时环境10包括至少一个调用的进程12、资源管理层14和一组硬件线程16(1)-16(M),其中M是大于或等于一的整数且表示第M个硬件线程16。运行时环境10使用资源管理层14和硬件线程16(1)-16(M)来允许执行来自进程12的任务以及来自与进程12共存的任何其他进程的任务(未示出)。运行时环境10结合资源管理层14来操作以允许进程12获得计算机系统的处理器和其他资源(例如,硬件线程16(1)-16(M))。
运行时环境10包括生成调度器22的调度器功能。在一实施例中,调度器功能被实现为调度器应用程序编程接口(API)。在其他实施例中,调度器功能可使用其他合适的编程构造来实现。当进程12被调用时,调度器功能在进程12中创建调度器22,其中调度器22用于调度进程12的任务以供一个或多个硬件线程16(1)-16(M)执行。运行时环境10可使用知道调度器功能所提供的设施的附随工具来利用应用程序或库开发者在其程序(例如,进程12)中表达的精细粒度并发性。
进程12包括对主存一个或多个执行上下文(即线程)的处理和其他资源的分配。进程12从资源管理层14获得对计算机系统中的处理和其他资源(例如,硬件线程16(1)-16(M))的访问。进程12使用该处理和其他资源来使任务被执行。
进程12在不同长度的任务中生成工作,其中每一任务与调度器22中的执行上下文相关联。每一任务包括当由计算机系统执行时执行工作单元的指令序列。每一执行上下文形成在分配的处理资源上执行相关联的任务的线程。每一执行上下文包括程序状态信息和机器状态信息。执行上下文可在没有剩余任务要执行的情况下终止。对于每一任务,运行时环境10和/或进程12或者将任务分配到调度器22以被调度来执行,或者以其他方式使该任务不使用调度器22来执行。
进程12可被配置成在基于诸如栈模型或解释器模型等任何合适的执行模型的计算机环境中操作,且可表示任何合适类型的代码,如应用程序、库函数或操作系统服务。进程12具有与包括定义的存储器地址空间的一组分配的资源相关联的程序状态和机器状态。进程12独立于运行时环境10中的任何共存进程而自主地或基本自主地执行。因此,进程12不会无意地更改共存进程的程序状态或分配到共存进程的任何资源的机器状态。类似地,共存进程不会无意地更改进程12的程序状态或分配到进程12的任何资源的机器状态。
资源管理层14通过将一个或多个硬件线程16分配到进程12来将处理资源分配到进程12。资源管理层14与图1的实施例中的计算机环境的操作系统(未在图1中示出)分开存在。在其他实施例中,资源管理层14或其部分或全部功能可被包括在操作系统中。
硬件线程16驻留在计算机系统的一组或一个或多个处理器封装(例如,图6中示出且在下文更详细地描述的的处理器封装102)的执行核中。每一硬件线程16被配置成独立于或基本独立于其他执行核来执行指令,且包括机器状态。硬件线程16可被包括在单个处理器封装中,或者可分布在多个处理器上。处理器封装中的每一执行核可包括一个或多个硬件线程16。
处理器12隐式地或显式地使得调度器22经由运行时环境10提供的调度器功能来创建。当进程12使用计算机系统中可用的API或编程语言特征时,可隐式地创建调度器实例22。响应于API或编程语言特征,运行时环境10创建带有默认策略的调度器22。为了显式地创建调度器22,进程12可调用运行时环境10提供的调度器功能并为调度器22指定策略。
调度器22以对于进程12透明的方式与资源管理层14进行交互来协商计算机系统的处理和其他资源。资源管理层14基于供需和调度器22的任何策略来将硬件线程16分配到调度器22。
在图1示出的实施例中,调度器22通过创建形成底层硬件线程16的抽象的虚拟处理器32来管理处理资源。调度器22包括一组虚拟处理器32(1)-32(N)。调度器22通过将每一虚拟处理器32映射到硬件线程16来将虚拟处理器32复用到硬件线程16上。调度器22可将一个以上的虚拟处理器32映射到特定硬件线程16上,但只可将一个硬件线程16映射到每一虚拟处理器32。在其他实施例中,调度器22以其他合适的方式来管理处理资源以使得硬件线程16执行进程12的指令。
调度器22包括一般任务集合37和局部任务集合44(1)-44(N),其中局部集合44(1)-44(N)与相应的虚拟处理器32(1)-32(N)对应。一般集合37可被组织成任何合适的类型、数量的任务子集和/或任务子集的组合。在一实施例中,一般集合37可包括一组一个或多个调度组80,如图4的实施例中示出且在下文中更详细地描述的。在其他实施例中,一般集合37可按其他合适的方式来组织。
调度器22中的执行上下文集包括一组执行上下文34(1)-34(N)以及由相应的处理器32(1)-32(N)执行的对应的相关联的任务36(1)-36(N)、一组零个或多个可运行执行上下文38、以及一组零个或多个阻塞的(即,依赖于等待的)执行上下文40。每一执行上下文34、38和40包括指示执行上下文34、38和40是正在执行的、可运行的(例如,响应于变为解锁或被添加到调度器22)还是阻塞的状态信息。正在执行的执行上下文34已经被附加到虚拟处理器32且当前正在执行。可运行的执行上下文38包括相关联的任务39且准备好由可用虚拟处理器32来执行。阻塞的执行上下文40包括相关联的任务41且正在等待另一执行上下文34、38或40正在生成或者将要生成的数据、消息或事件。
调度器22中的执行上下文集还包括相应的局部集合44(1)-44(N)中的可运行执行上下文46(1)-46(N)的集合。每一执行上下文46具有通过任务36的执行解锁的相关联的任务47,其中任务36在与包括执行上下文46的局部集合44对应的虚拟处理器32上执行或当前正在执行。
在虚拟处理器32上执行的每一执行上下文34可在其执行过程中生成按任何合适的方式(例如,添加到工作队列(未在图1中示出))来组织的附加任务42。可以通过使用运行时环境10提供的应用程序接口(API)或编程语言特征以及一实施例中相应的工具来创建工作。当处理资源对调度器22可用时,任务被分配到在获得新任务之前将其在虚拟处理器32上执行完全的执行上下文34或38。在虚拟处理器32上执行的执行上下文34还可通过生成将由另一执行上下文40使用的数据、消息或事件来解锁其他执行上下文40。
调度器22中的每一任务可以是实现的(例如,实现的任务36和39),这指示执行上下文34或38已经或将要被附加到该任务且该任务准备好执行。实现的任务通常包括解锁的执行上下文和调度的代理。未实现的任务被称为未实现的。未实现的任务(例如,任务42)可作为父任务的执行所生成的子任务来创建,且可由并行构造来生成(例如,并行、并行的、开始和完成)。调度器22可被组织成用于带有执行上下文的逻辑上独立的任务(即,实现的任务)的同步集合(例如,栈和/或队列),以及用于依赖任务(即,未实现的任务)的工作窃取(workstealing)队列的列表,如以下图4的实施例所描述的。
在完成、阻塞或以其他方式中断(即,显式产生或迫使抢先)在虚拟处理器32上运行的执行上下文34之后,虚拟处理器32变成可用于执行另一实现的任务39或未实现的任务42。调度器22搜索可运行执行上下文38或未实现的任务42来附加到可用虚拟处理器32以便按任何合适的方式来执行。例如,调度器22可在搜索要执行的未实现的任务42之前首先搜索要执行的可运行执行上下文38。调度器22不断地将执行上下文38附加到可用虚拟处理器32以便执行,直到执行了调度器22的所有执行上下文38。
局部集合44可允许调度器22利用可随硬件线程16出现的存储器局部性效应。在执行进程12时,调度器22将每一依赖于等待的执行上下文40以及变为解锁的任务41分配到与使得任务41变为解锁的处理资源(例如,虚拟处理器32和硬件线程16的组合)对应的局部集合44。解锁任务41以及相关联的执行上下文40响应于被添加到局部集合44中而变为可运行任务47以及相关联的执行上下文46。
当处理资源(例如,虚拟处理器32)变为可用时,处理资源试图执行与对应的局部集合44中的执行上下文46相关联的最近最后添加的任务47(即,处理资源解锁的最近任务47)。通过这样做,调度器22增加了每一解锁任务47将能够利用存储在使得任务47变为解锁的处理资源的存储区分层结构中高处的数据的可能性。结果,与在还未包括存储在存储器分层结构中高处的这些数据的另一处理资源中相比,解锁任务47可在该处理资源中更高效地执行。
例如,如果执行上下文34(1)上的任务36(1)在经由虚拟处理器32(1)在硬件线程16(1)上执行的同时解锁任务41以及执行上下文40,则执行上下文34(1)可能产生任务41将消费的至少某些数据。因为执行上下文34(1)产生的数据可能已经引起任务41的解锁,所以该数据可能在硬件线程16(1)的存储器分层结构中的高处(例如,该数据在硬件线程16(1)可访问的一个或多个高速缓存的高层中是热的)。在该示例中,调度器22将解锁任务41和相关联的执行上下文40分配到局部集合44(1)来增加解锁任务41被同一硬件线程16(1)执行(经由虚拟处理器32(1))的可能性。
在一实施例中,局部集合44中的每一个被实现为工作窃取队列来允许处理起源从以下更详细地描述的其他处理资源的局部集合44窃取任务47以及可运行执行上下文46。在该实施例中,当访问与该处理资源对应的局部集合44时,处理资源弹出最近最后添加的任务47和相关联的执行上下文46以便执行。当访问与另一处理资源对应的局部集合44时,处理资源窃取最近最早添加的任务47和相关联的执行上下文46以便执行。通过这样做,调度器22允许局部集合44在没有锁或仅有局部集合44的最小锁定的情况下来操作。在其他实施例中,局部集合44可被实现为其他类型的集合。
图2是示出用于分配调度器22中的依赖于等待的执行上下文40的方法的一实施例的流程图。将参考图1中的调度器22的实施例来描述图2的方法。
调度器22判定任务41以及依赖于等待的执行上下文40是否成为解锁的,如框52中所指示的。调度器22可在使得进程12被执行的同时不断地执行该功能。为了做出判定,调度器22检测解锁执行上下文40的数据、一个或多个消息、和/或一个或多个事件已经由执行执行上下文34的虚拟处理器32生成。调度器22还标识使得执行上下文38变为解锁的虚拟处理器32。
响应于判定任务41以及依赖于等待的执行上下文40成为解锁的,调度器22判定与使得执行上下文40变为解锁的虚拟处理器32对应的局部集合44是否已满,如框54中所指示的。调度器22可以限制或可以不限制每一局部集合44的大小。例如,调度器22可将存储在每一局部集合44中的执行上下文46的数量限制为四。
如果局部集合44当前正存储最大数量的执行上下文46(即,局部集合44已满),则调度器22将最近最早添加的任务47和相关联的执行上下文46从局部集合44移动到一般集合37(例如,到执行上下文38的集合),如框56中所指示的。调度器22从局部集合44中移除最近最早添加的执行上下文46并将执行上下文46添加到一般集合37中来为新解锁的执行上下文40留出空间。在将执行上下文46从局部集合44溢出到一般集合37时,调度器22将局部集合44作为FIFO(先进先出)缓冲区来操作以将局部集合44中的最近最早添加的执行上下文46溢出到一般集合37。
在其他实施例中,当局部集合44已满时,调度器22可将解锁任务41和相关联的执行上下文40添加到一般集合37。
在一般集合37包括两个或更多子集合的实施例中,调度器22可将执行上下文46添加到关联于与从中移除执行上下文46的局部集合44对应的虚拟处理器32的子集合中。虚拟处理器32可通过最近访问该子集合来与该子集合相关联以获得可运行执行上下文38。
在确保局部集合44中存在用于解锁任务41的空间之后,调度器22将解锁任务41和相关联的执行上下文40分配到与使得任务41变为解锁的虚拟处理器32对应的局部集合44,如框58中所指示的。调度器22将任务41和相关联的执行上下文40添加到局部集合44中,从而使得任务41和相关联的执行上下文40变为任务47和相关联的执行上下文46的集合中最近最后添加的一个。
图3是示出用于选择执行上下文以便执行的方法的一实施例的流程图。将参考图1中的调度器22的实施例来描述图3的方法。
调度器22判定虚拟处理器32是否变为可用的,如框62中所指示的。调度器22可在使得进程12被执行的同时不断地执行该功能。在完成、阻塞或以其他方式中断(即,显式产生或迫使抢先)在虚拟处理器32上运行的执行上下文34之后,虚拟处理器32变为可用于执行另一执行上下文38或46和/或另一任务42。
当调度器22判定虚拟处理器32变为可用时,调度器22开始搜索可运行执行上下文来附加到可用虚拟处理器32以便执行。调度器22首先试图在局部集合44中定位与可用虚拟处理器32对应的可运行执行上下文46,如框64中所指示的。
如果可运行执行上下文46存在于局部集合44中,则调度器22使得虚拟处理器32执行局部集合44中的最近最后添加的执行上下文46,如框66中所指示的。当可运行执行上下文46存在于局部集合44中时,调度器22将局部集合44作为LIFO(后进先出)缓冲区来操作以移除最近最后添加的执行上下文46以便执行。可运行执行上下文46是局部集合44中最近最后添加的执行上下文46,且由在虚拟处理器32上执行的执行上下文34解锁。结果,可运行执行上下文46可具有使得与虚拟处理器32对应的硬件线程16可访问存储器分层结构中的高处的等待依赖性相关的数据的最大可能性。
如果可运行执行上下文46不存在于局部集合44中,则调度器22试图在一般集合37中定位可运行执行上下文38,如框68中所指示的。
在一般集合37包括两个或更多子集合的实施例中,调度器22可试图在可用虚拟处理器32最近最后从中获得可运行执行上下文38的子集合中定位可运行执行上下文38。
如果可运行执行上下文38存在于一般集合37中,则调度器22使得虚拟处理器32执行来自一般集合37的可运行执行上下文38,如框70中所指示的。
如果可运行执行上下文38不存在于一般集合37中,则调度器22试图在与调度器22的另一虚拟处理器32对应的局部集合44中定位可运行执行上下文46,如框72中所指示的。在一实施例中,调度器22按照循环次序访问与其他虚拟处理器32对应的局部集合44,直到定位到可运行执行上下文46。在其他实施例中,调度器22按其他合适的次序访问与其他虚拟处理器32对应的局部集合44。
如果可运行执行上下文46存在于调度器22的另一虚拟处理器32的局部集合中,则调度器22使得可用虚拟处理器32执行其他虚拟处理器32的局部集合44中的最近最早添加的执行上下文46,如框74中所指示的。当在另一局部集合44中找到可运行执行上下文46时,调度器22将该另一局部集合44作为FIFO(先进先出)缓冲区来操作以移除最近最早添加的执行上下文46以便执行。由此,调度器22窃取局部集合44中的最近最早添加的执行上下文46且在调度器22的局部集合44中的执行上下文46之间提供了公平性和进展的机制。另外,调度器22通过弹出最近最早添加的执行上下文46以便执行来最小化对最可能获益于在其他虚拟处理器32上运行的执行上下文46的干扰。
如果可运行执行上下文46不存在于调度器22的其他虚拟处理器32的任何局部集合44中,则调度器22可在其他位置搜索可运行执行上下文,如框76中所指示的。例如,在一般集合37包括两个或更多子集合的实施例中,调度器22可试图通过按照循环次序搜索一般集合37的其他子集合来定位可运行执行上下文38。作为另一示例,调度器22可搜索一般集合37的一个或多个子集合的一个或多个工作窃取队列(未示出)来定位可运行的未实现的任务42。当定位到可运行执行上下文或其他可运行任务42时,调度器22使得可用虚拟处理器32执行可运行执行上下文或其他可运行任务42。
现在将参考图4来描述一般集合37的子集合的一个实施例。图4是示出被配置为调度组80(1)-80(P)以便由运行时环境10在调度器22中使用的子集合的一实施例的框图。
进程12可将任务分组成调度组80(1)-80(P),从而使得每一调度组80包括一组相关执行上下文或任务且用于为工作的局部性、公平性、和/或进展提供结构。分组可取决于逻辑上相关的工作(例如,从公共根任务传下来的任务集合)、硬件拓扑结构(例如,非均匀存储器体系结构(NUMA))或其组合。调度组80可允许调度器22改进可伸缩性、局部性、和公平性。
每一调度组80包括可运行集合82、工作队列84、和一组零个或多个工作窃取队列86。每一可运行集合82包含可运行执行上下文38的列表。当新的可运行执行上下文由进程12呈现给调度器22时或者当可运行执行上下文46如上所述地从局部集合44被溢出到一般集合37中时,调度器22将执行上下文添加到可运行集合82。工作队列84包含工作窃取队列86的列表,如箭头88所指示的,且跟踪正在执行来自工作窃取队列86的任务42的执行上下文34。每一工作窃取队列86包括一个或多个未实现的任务42。
现在将参考图5A-5B中的示例来描述图1的实施例中对调度组80的使用。图5A-5B是示出在带有局部集合44的调度器22中执行执行上下文的实施例的框图。
在图5A的示例中,虚拟处理器32(1)和32(2)当前正在执行来自调度组80(1)的相应的执行上下文34(1)和34(2),如相应的箭头90(1)和90(2)所指示的。调度组80(1)包括十个依赖于等待的执行上下文40(1)-40(10)-上下文A、B、C、D、E、V、W、X、Y和Z-如框92中所示。
执行上下文34(1)通过执行产生用于阻塞的执行上下文40(1)-40(5)-上下文A、B、C、D和E的数据、一个或多个消息、或一个或多个事件的函数来解锁五个执行上下文40(1)-40(5)。函数A.PRODUCE()产生用于阻塞的执行上下文A的数据或消息,函数B.PRODUCE()产生用于阻塞的执行上下文B的数据或消息,以此类推。
类似地,执行上下文34(2)通过执行产生用于阻塞的执行上下文40(6)-40(10)-上下文V、W、X、Y和Z的数据或消息的函数来解锁五个执行上下文40(6)-40(10)。函数V.PRODUCE()产生用于阻塞的执行上下文V的数据或消息,函数W.PRODUCE()产生用于阻塞的执行上下文W的数据或消息,以此类推。
如上参考图2所描述的,调度器将虚拟处理器32(1)解锁的每一执行上下文40(1)-40(5)添加到局部集合44(1)上,并按照解锁的次序将其添加到可运行执行上下文46(1)的集合中,如图5B所示。类似地,调度器将虚拟处理器32(2)解锁的每一执行上下文40(6)-40(10)压到局部集合44(2)上,且按照解锁的次序将其压进可运行执行上下文46(2)的集合中。
在图5B的示例中,每一局部集合44(1)和44(2)被配置成最多存储四个执行上下文46。在局部集合44中已经有四个执行上下文46的情况下第五个执行上下文40被解锁时,调度器22将最近最早添加的执行上下文46溢出到调度组80(1)的可运行集合82(1)中。在图5B的示例中,调度器22如箭头94所指示地将来自局部集合44(1)的执行上下文A溢出到可运行集合82(1)中,来允许执行上下文E被添加到局部集合44(1)中。同样,调度器22如箭头96所指示地将来自局部集合44(2)的执行上下文V溢出到可运行集合82(1)中,来允许执行上下文Z被添加到局部集合44(2)中。
箭头98指示执行上下文46(1)和46(2)被添加到相应的局部集合44(1)和44(2)的次序,其中时间t1发生在时间t2之前(即,t1<t2)。另外,箭头99指示与执行上下文46(1)和46(2)对应的数据在与相应的虚拟处理器32(1)和32(2)对应的硬件线程16(1)和16(2)的存储器分层结构中有多热的可能性幅度。
当虚拟处理器32(1)和32(2)变为可用时,虚拟处理器32(1)和32(2)将首先试图在相应的局部集合44(1)和44(2)中定位相应的可运行执行上下文46(1)和46(2),如以上参考图3所描述的。在图5B的示例中,虚拟处理器32(1)移除并执行执行上下文E(即,最近最后添加的执行上下文46(1)),而虚拟处理器32(2)移除并执行执行上下文Z(即,最近最后添加的执行上下文46(2))。如箭头99所示,执行上下文E和Z最可能具有相应的硬件线程16(1)和16(2)的相应的存储器分层结构中的最热数据。例如,如果以上执行上下文34、40和46在大型数字矩阵上操作时,则与执行上下文E和Z相关联的大量矩阵数据可能位于相应的硬件线程16(1)和16(2)可访问的相应的存储器分层结构中的高处(例如,在相应的硬件线程16(1)和16(2)可访问的相应的高速缓存中很热)。
最终,如上参考图3所述的,局部集合44(1)和44(2)中的可运行执行上下文46(1)和46(2)由虚拟处理器32(1)、32(2)、和/或从局部集合44(1)和/或44(2)窃取执行上下文46(1)和/或46(2)的其他虚拟处理器32来执行。
当可用虚拟处理器32不能在对应的局部集合44中定位可运行执行上下文46时,虚拟处理器32试图按以下次序定位可运行执行上下文,直到找到可运行执行上下文。虚拟处理器32查看对应的调度组80中的可运行集合82,然后循环通过其他虚拟处理器32的局部集合44,再循环通过其余调度组80的可运行集合82。
如果在调度器22中没有找到可运行执行上下文,则虚拟处理器32试图从工作窃取队列86窃取未实现的任务42。因此,只有无法在对应的局部集合44、对应的调度组80、其他局部集合44和其余调度组80中找到可运行执行上下文之后,调度器22才尝试广义的窃取。
在图5A-5B的示例中,未在局部集合44(3)(未示出)或对应的调度组80(2)的可运行集合82(2)中定位到可运行执行上下文的可用虚拟处理器32(3)(未在图5A-5B中示出)可从局部集合44(1)窃取执行上下文B(即,最近最早添加的执行上下文46(1)),或者从局部集合44(2)窃取执行上下文W(即,最近最早添加的执行上下文46(2))。如果局部集合44(1)和44(2)以及其余局部集合44为空,则虚拟处理器32(3)可从对应的调度组80(1)的可运行集合82(1)窃取执行上下文V。
图6A-6B是分别示出被配置成实现包括带有局部集合44(1)-44(N)的调度器22的运行时环境10的计算机系统100的实施例100A和100B的框图。
如图6A所示,计算机系统100A包括一个或多个处理器封装102、存储器系统104、零个或多个输入/输出设备106、零个或多个显示设备108、零个或多个外围设备110、和零个或多个网络设备112。处理器封装102、存储器系统104、输入/输出设备106、显示设备108、外围设备110和网络设备112使用包括任何合适的类型、数量和配置的控制器、总线、接口、和/或其他有线或无线连接的一组互连114来进行通信。
计算机系统100A表示出于通用或专用目的而配置的任何合适的处理设备。计算机系统100A的示例包括服务器、个人计算机、膝上型计算机、图形输入板计算机、个人数字助理(PDA)、移动电话、和音频/视频设备。计算机系统100A的组件(即,处理器封装102、存储器系统104、输入/输出设备106、显示设备108、外围设备110、网络设备112和互连114)可包含在公共外壳(未示出)中或任何合适数量的独立外壳(未示出)中。
处理器封装102包括硬件线程16(1)-16(M)。处理器封装102中的每一硬件线程16被配置成访问并执行存储在存储器系统104中的指令。这些指令可包括基本输入输入系统(BIOS)或固件(未示出)、操作系统(OS)120、运行时平台122、应用程序124和资源管理层14(也在图1中示出)。每一硬件线程16可结合或响应于从输入/输出设备106、显示设备108、外围设备110、和/或网络设备112接收到的信息来执行指令。
计算机系统100A引导并执行OS 120。OS 120包括硬件线程16可执行来管理计算机系统100A的组件并提供允许应用程序124访问并使用该组件的一组功能的指令。在一实施例中,OS 120是Windows操作系统。在其他实施例中,OS 120是适于和计算机系统100A一起使用的另一操作系统。
资源管理层14包括可结合OS 120来执行以如上参考图1所述地分配包括硬件线程16的计算机系统100A的资源的指令。资源管理层14可作为对一个或多个应用程序124可用的功能库或者作为OS 120的一个集成部分被包括在计算机系统100A中。
运行时平台122包括可结合OS 120和资源管理层14来执行以生成运行时环境10并向应用程序124提供运行时功能的指令。这些运行时功能包括如上参考图1所详细描述的调度器功能。运行时功能可作为应用程序124的一部分、作为对一个或多个应用程序124可用的功能库、或者作为OS 120和/或资源管理层14的一个集成部分被包括在计算机系统100A中。
每一应用程序124包括可结合OS 120、资源管理层14和/或运行时平台122来执行以使计算机系统100A执行所需操作的指令。每一应用程序124表示可与使用运行时平台122提供的局部集合44(1)-44(N)的调度器22一起执行的一个或多个进程,诸如如上所述的进程12。
存储器系统104包括被配置成存储指令和数据的任何合适的类型、数量和配置的易失性或非易失性存储设备。存储器系统104的存储设备表示存储包括OS 120、资源管理层14、运行时平台122和应用程序124的计算机可执行指令的计算机可读存储介质。这些指令可由计算机系统来执行以执行此处描述的OS 120、资源管理层14、运行时平台122和应用程序124的功能和方法。存储器系统104中的存储设备的示例包括硬盘驱动器、随机存取存储器(RAM)、只读存储器(ROM)、闪存驱动器和卡、以及磁盘和光盘。
存储器系统104存储从处理器封装102、输入/输出设备106、显示设备108、外围设备110和网络设备112接收的指令和数据。存储器系统104向处理器封装102、输入/输出设备106、显示设备108、外围设备110和网络设备112提供存储的指令和数据。
输入/输出设备106包括被配置成将指令或数据从用户输入到计算机系统100A并将指令或数据从计算机系统100A输出到用户的任何合适的类型、数量和配置的输入/输出设备。输入/输出设备106的示例包括键盘、鼠标、触摸垫、触摸屏、按钮、拨盘、旋钮和开关。
显示设备108包括被配置成向计算机系统100A的用户输出文本和/或图形信息的任何合适的类型、数量和配置的显示设备。显示设备108的示例包括监视器、显示屏和投影仪。
外围设备110包括被配置成用计算机系统100A中的一个或多个其他组件来操作以执行通用或专用处理功能的任何合适的类型、数量和配置的外围设备。
网络设备112包括被配置成允许计算机系统100A通过一个或多个网络(未示出)进行通信的任何合适的类型、数量和配置的网络设备。网络设备112可根据任何合适的网络协议和/或配置来操作以允许计算机系统100A将信息发送给网络或者从网络接收信息。
图6B是示出计算机系统100的实施例100B的框图。计算机系统100B也包括至少一个处理器封装102和存储器系统104。处理器封装102包括处理器封装102(1)-102(R)而存储器系统104包括存储器设备128(1)-128(R),其中R是大于或等于二的整数且表示第R个处理器封装102和第R个存储器设备128。OS 120、运行时平台122、应用程序124和资源管理层14中的每一个可被存储在存储器设备128(1)-128(R)中任何合适的一个中。
在图6B的实施例中,每一处理器封装102(1)-102(R)和相应的存储器设备128(1)-128(R)形成一个节点。这些节点由任何合适的类型、数量的节点互连130和/或节点互连130的组合来互连。
每一处理器封装102包括一组硬件线程16(1)-16(4),其中每一硬件线程包括一L1(一级)高速缓存(未示出)。每一处理器封装102还包括与相应的硬件线程16(1)(1)-16(1)(4)对应的一组L2(二级)高速缓存132(1)-132(4)。每一处理器封装102还包括对硬件线程16(1)-16(4)的集合、系统资源接口136、纵横交换机138、存储器控制器140和节点接口142可用的L3(三级)高速缓存。系统资源接口136提供对节点资源(未示出)的访问。纵横交换机138将系统资源接口与存储器控制器140和节点接口142互连。存储器控制器140连接到存储器设备128。节点接口142连接到一个或多个节点互连130。
参考以上图1-5B中描述的实施例,调度器22可使用局部集合44来试图利用计算机系统100B中的存储器局部性效应。例如,当在硬件线程16(1)(1)上的执行上下文34上执行的任务经由虚拟处理器32(1)来解锁任务41以及执行上下文40时,任务41将消费的至少某些数据可能在处理器封装102(1)的L1高速缓存(未示出)、L2高速缓存132(1)(1)、和/或L3高速缓存134(1)中。通过将解锁任务41分配到局部集合44(1),调度器22提高了硬件线程16(1)(1)经由虚拟处理器32(1)来执行任务41并利用L1高速缓存(未示出)、L2高速缓存132(1)(1)、和/或L3高速缓存134(1)中的热数据的可能性。
如上所述的调度器中的局部集合的使用可向调度器提供对依赖于等待的执行上下文的执行进行加权以及最大化依赖于等待的执行上下文之间的存储器局部性效应的能力。结果,调度器可增加依赖于等待的执行上下文在相同硬件资源上执行的可能性。
另外,通过将所选工作窃取概念包括在以上实施例中,调度器可保留执行上下文之间的公平性和进展。
局部集合还可减少正在搜索要执行的执行上下文的处理资源之间的争用。结果,调度器还可缩放至带有大量处理资源的计算机系统。
尽管此处说明并描述了具体实施例,但本领域技术人员可以理解,可用各种替换和/或等价实现来替换此处示出并描述的具体实施例而不背离本发明的范围。本申请旨在覆盖此处讨论的具体实施例的任何改编或变型。因此,本发明旨在仅由权利要求书及其等效方案来限制。
Claims (14)
1.一种方法,包括:
检测到在计算机系统(100A/100B)上执行的进程(12)的调度器(22)中的第一任务(41)已经由在被分配到所述调度器的多个处理资源(16/32)中的第一个上执行的第二任务(36)变为解锁;以及
将所述第一任务分配到与所述多个处理资源中的第一个相关联的多个局部集合(44)中的第一个。
2.如权利要求1所述的方法,其特征在于,还包括:
检测到所述调度器中的第三任务(41)已经由在被分配到所述调度器的多个处理资源(16/32)中的第二个上执行的第四任务(36)变为解锁;以及
将所述第三任务分配到与所述多个处理资源中的第二个相关联的多个局部集合(44)中的第二个。
3.如权利要求1所述的方法,其特征在于,还包括:
响应于检测到所述多个局部集合中的第一个已满,在将所述第一任务分配到所述多个局部集合中的第一个之后将所述多个局部集合中的第一个中的第三任务(47)重新分配到一般集合(37)。
4.如权利要求3所述的方法,其特征在于,所述第三任务是所述多个局部集合中的第一个中的最近最早添加的任务。
5.如权利要求1所述的方法,其特征在于,还包括:
将第三任务分配到所述调度器中的一般集合(37)。
6.如权利要求1所述的方法,其特征在于,还包括:
响应于所述第一任务是所述多个局部集合中的第一个中的最近最后添加的任务,当所述多个处理资源中的第一个变为可用时,用所述多个处理资源中的第一个执行所述第一任务。
7.如权利要求1所述的方法,其特征在于,还包括:
响应于所述第一任务是所述多个局部集合中的第一个中的最近最早添加的任务,当所述多个处理资源中的第二个变为可用时,用所述多个处理资源中的第二个执行所述第一任务。
8.一种存储计算机可执行指令的计算机可读存储介质(104/128/132/134),所述指令在由计算机系统(100A/100B)执行时执行一种方法,所述方法包括:
在所述计算机系统上执行的进程(12)中创建调度器(22),所述调度器带有至少一个一般集合(37)和对应于被分配到所述调度器的多个处理资源(16/32)中的每一个的独立局部集合(44);以及
将所述调度器中的第一解锁任务(41)分配到所述多个处理资源中与使得所述第一解锁任务变为可运行的第一个处理资源对应的局部集合。
9.如权利要求8所述的计算机可读存储介质,其特征在于,所述方法还包括:
将所述调度器中的第二解锁任务(41)分配到与所述多个处理资源中使得所述第二解锁任务变为可运行的第二个处理资源对应的局部集合。
10.如权利要求8所述的计算机可读存储介质,其特征在于,所述方法还包括:
响应于检测到与所述多个处理资源中的第一个对应的局部集合已满,将第二解锁任务(47)从所述局部集合移动到所述一般集合。
11.如权利要求8所述的计算机可读存储介质,其特征在于,所述方法还包括:
将所述调度器接收的新任务(38/42)分配到所述一般集合。
12.如权利要求8所述的计算机可读存储介质,其特征在于,所述方法还包括:
响应于所述第一任务是与所述多个处理资源中的第一个处理资源对应的局部集合中的最近最后添加的任务,当所述多个处理资源中的第一个处理资源变为可用时,用所述多个处理资源中的第一个处理资源执行所述第一解锁任务。
13.如权利要求8所述的计算机可读存储介质,其特征在于,所述方法还包括:
响应于所述第一解锁任务不是与所述多个处理资源中的第一个处理资源对应的局部集合中的最近最后添加的任务,当所述多个处理资源中的第一个处理资源变为可用时,用所述多个处理资源中的第一个处理资源来执行第二解锁任务(47),所述第二解锁任务是与所述多个处理资源中的第一个处理资源对应的局部集合中的最近最后添加的任务。
14.如权利要求8所述的计算机可读存储介质,其特征在于,所述方法还包括:
响应于所述第一解锁任务是与所述多个处理资源中的第一个处理资源对应的局部集合中的最近最早添加的任务,当所述多个处理资源中的第二个处理资源变为可用时,用所述多个处理资源中的第二个处理资源执行所述第一任务。
Applications Claiming Priority (3)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US12/121,789 US8566830B2 (en) | 2008-05-16 | 2008-05-16 | Local collections of tasks in a scheduler |
US12/121,789 | 2008-05-16 | ||
PCT/US2009/038662 WO2009139967A2 (en) | 2008-05-16 | 2009-03-27 | Local collections of tasks in a scheduler |
Publications (2)
Publication Number | Publication Date |
---|---|
CN102027447A true CN102027447A (zh) | 2011-04-20 |
CN102027447B CN102027447B (zh) | 2013-12-04 |
Family
ID=41317378
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN2009801184584A Active CN102027447B (zh) | 2008-05-16 | 2009-03-27 | 调度器中的局部任务集合 |
Country Status (5)
Country | Link |
---|---|
US (1) | US8566830B2 (zh) |
EP (1) | EP2288989B1 (zh) |
JP (1) | JP5643190B2 (zh) |
CN (1) | CN102027447B (zh) |
WO (1) | WO2009139967A2 (zh) |
Cited By (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN104081355A (zh) * | 2011-12-16 | 2014-10-01 | 萨热姆通信宽带简易股份有限公司 | 软件总线 |
CN104657204A (zh) * | 2013-11-22 | 2015-05-27 | 华为技术有限公司 | 短任务处理方法、装置及操作系统 |
CN113590301A (zh) * | 2021-09-30 | 2021-11-02 | 苏州浪潮智能科技有限公司 | 一种深度学习业务的任务调度方法及相关装置 |
CN113760502A (zh) * | 2021-02-02 | 2021-12-07 | 北京沃东天骏信息技术有限公司 | 用于集群的资源分配方法、装置及系统 |
Families Citing this family (17)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US8112751B2 (en) * | 2007-03-01 | 2012-02-07 | Microsoft Corporation | Executing tasks through multiple processors that process different portions of a replicable task |
US9417914B2 (en) * | 2008-06-02 | 2016-08-16 | Microsoft Technology Licensing, Llc | Regaining control of a processing resource that executes an external execution context |
WO2009153619A1 (en) * | 2008-06-19 | 2009-12-23 | Freescale Semiconductor, Inc. | A system, method and computer program product for debugging a system |
WO2009153620A1 (en) * | 2008-06-19 | 2009-12-23 | Freescale Semiconductor, Inc. | A system, method and computer program product for scheduling a processing entity task |
US20110099552A1 (en) * | 2008-06-19 | 2011-04-28 | Freescale Semiconductor, Inc | System, method and computer program product for scheduling processor entity tasks in a multiple-processing entity system |
US8806497B2 (en) * | 2010-03-05 | 2014-08-12 | Microsoft Corporation | System and method for altering the work definitions in an iterative parallel opportunistic work stealing scheduler |
JP2013524386A (ja) | 2010-04-13 | 2013-06-17 | イーティー インターナショナル,インコーポレイティド | ランスペース方法、システムおよび装置 |
US20120102505A1 (en) * | 2010-10-25 | 2012-04-26 | Microsoft Corporation | Dynamic process virtualization |
CN103262064A (zh) | 2010-12-16 | 2013-08-21 | Et国际有限公司 | 分布式计算体系结构 |
US9841958B2 (en) | 2010-12-23 | 2017-12-12 | Microsoft Technology Licensing, Llc. | Extensible data parallel semantics |
US20140282578A1 (en) * | 2013-03-14 | 2014-09-18 | Justin S. Teller | Locality aware work stealing runtime scheduler |
US9424102B2 (en) | 2014-05-14 | 2016-08-23 | International Business Machines Corporation | Task grouping by context |
CN107870822B (zh) * | 2016-09-26 | 2020-11-24 | 平安科技(深圳)有限公司 | 基于分布式系统的异步任务控制方法及系统 |
US10592280B2 (en) * | 2016-11-23 | 2020-03-17 | Amazon Technologies, Inc. | Resource allocation and scheduling for batch jobs |
US20220012089A1 (en) * | 2020-07-13 | 2022-01-13 | Accenture Global Solutions Limited | System for computational resource prediction and subsequent workload provisioning |
CN111930522A (zh) * | 2020-09-24 | 2020-11-13 | 常州微亿智造科技有限公司 | Gpu虚拟化和资源调度方法和装置 |
US12086634B2 (en) * | 2021-07-23 | 2024-09-10 | VMware LLC | Optimizing VM NUMA configuration and workload placement in a heterogeneous cluster |
Citations (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5349656A (en) * | 1990-11-28 | 1994-09-20 | Hitachi, Ltd. | Task scheduling method in a multiprocessor system where task selection is determined by processor identification and evaluation information |
US5692193A (en) * | 1994-03-31 | 1997-11-25 | Nec Research Institute, Inc. | Software architecture for control of highly parallel computer systems |
US20030037091A1 (en) * | 2001-08-09 | 2003-02-20 | Kozo Nishimura | Task scheduling device |
US20040154021A1 (en) * | 2003-01-30 | 2004-08-05 | Vasudevan Sangili | Apparatus and method to minimize blocking overhead in upcall based MxN threads |
US20060123420A1 (en) * | 2004-12-01 | 2006-06-08 | Naohiro Nishikawa | Scheduling method, scheduling apparatus and multiprocessor system |
CN1818875A (zh) * | 2006-03-16 | 2006-08-16 | 浙江大学 | 嵌入式操作系统分组硬实时任务调度的实现方法 |
US20070204268A1 (en) * | 2006-02-27 | 2007-08-30 | Red. Hat, Inc. | Methods and systems for scheduling processes in a multi-core processor environment |
Family Cites Families (17)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JPH02171952A (ja) | 1988-12-26 | 1990-07-03 | Hitachi Ltd | マルチプロセッサにおけるディスパッチ方式 |
JPH06214811A (ja) | 1993-01-20 | 1994-08-05 | Toshiba Corp | スケジューリング方式 |
US5379428A (en) | 1993-02-01 | 1995-01-03 | Belobox Systems, Inc. | Hardware process scheduler and processor interrupter for parallel processing computer systems |
US6105053A (en) | 1995-06-23 | 2000-08-15 | Emc Corporation | Operating system for a non-uniform memory access multiprocessor system |
JPH11259318A (ja) | 1998-03-13 | 1999-09-24 | Hitachi Ltd | ディスパッチ方式 |
US6952827B1 (en) * | 1998-11-13 | 2005-10-04 | Cray Inc. | User program and operating system interface in a multithreaded environment |
EP1182570A3 (en) * | 2000-08-21 | 2004-08-04 | Texas Instruments Incorporated | TLB with resource ID field |
WO2005022381A2 (en) | 2003-08-28 | 2005-03-10 | Mips Technologies, Inc. | Integrated mechanism for suspension and deallocation of computational threads of execution in a processor |
US20050108711A1 (en) | 2003-11-13 | 2005-05-19 | Infineon Technologies North America Corporation | Machine instruction for enhanced control of multiple virtual processor systems |
US7873776B2 (en) | 2004-06-30 | 2011-01-18 | Oracle America, Inc. | Multiple-core processor with support for multiple virtual processors |
US20060168214A1 (en) | 2004-10-29 | 2006-07-27 | International Business Machines Corporation | System for managing logical partition preemption |
US20060130062A1 (en) | 2004-12-14 | 2006-06-15 | International Business Machines Corporation | Scheduling threads in a multi-threaded computer |
US7752620B2 (en) | 2005-06-06 | 2010-07-06 | International Business Machines Corporation | Administration of locks for critical sections of computer programs in a computer that supports a multiplicity of logical partitions |
JP2007179100A (ja) | 2005-12-26 | 2007-07-12 | Sharp Corp | ジョブキューシステムおよびジョブ管理方法、制御プログラム、可読記録媒体 |
US7873964B2 (en) * | 2006-10-30 | 2011-01-18 | Liquid Computing Corporation | Kernel functions for inter-processor communications in high performance multi-processor systems |
EP2109819B1 (en) * | 2007-02-06 | 2017-08-02 | MBA Sciences, Inc. | A resource tracking method and apparatus |
WO2009029549A2 (en) * | 2007-08-24 | 2009-03-05 | Virtualmetrix, Inc. | Method and apparatus for fine grain performance management of computer systems |
-
2008
- 2008-05-16 US US12/121,789 patent/US8566830B2/en active Active
-
2009
- 2009-03-27 WO PCT/US2009/038662 patent/WO2009139967A2/en active Application Filing
- 2009-03-27 JP JP2011509510A patent/JP5643190B2/ja active Active
- 2009-03-27 EP EP09747053.8A patent/EP2288989B1/en active Active
- 2009-03-27 CN CN2009801184584A patent/CN102027447B/zh active Active
Patent Citations (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5349656A (en) * | 1990-11-28 | 1994-09-20 | Hitachi, Ltd. | Task scheduling method in a multiprocessor system where task selection is determined by processor identification and evaluation information |
US5692193A (en) * | 1994-03-31 | 1997-11-25 | Nec Research Institute, Inc. | Software architecture for control of highly parallel computer systems |
US20030037091A1 (en) * | 2001-08-09 | 2003-02-20 | Kozo Nishimura | Task scheduling device |
US20040154021A1 (en) * | 2003-01-30 | 2004-08-05 | Vasudevan Sangili | Apparatus and method to minimize blocking overhead in upcall based MxN threads |
US20060123420A1 (en) * | 2004-12-01 | 2006-06-08 | Naohiro Nishikawa | Scheduling method, scheduling apparatus and multiprocessor system |
US20070204268A1 (en) * | 2006-02-27 | 2007-08-30 | Red. Hat, Inc. | Methods and systems for scheduling processes in a multi-core processor environment |
CN1818875A (zh) * | 2006-03-16 | 2006-08-16 | 浙江大学 | 嵌入式操作系统分组硬实时任务调度的实现方法 |
Non-Patent Citations (1)
Title |
---|
BORIS WEISSMAN: "active threads: an extensible and portable light-weight thread system", 《INTERNATIONAL COMPUTER SCIENCE INSTITUTE》 * |
Cited By (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN104081355A (zh) * | 2011-12-16 | 2014-10-01 | 萨热姆通信宽带简易股份有限公司 | 软件总线 |
CN104081355B (zh) * | 2011-12-16 | 2018-03-09 | 萨热姆通信宽带简易股份有限公司 | 软件总线 |
CN104657204A (zh) * | 2013-11-22 | 2015-05-27 | 华为技术有限公司 | 短任务处理方法、装置及操作系统 |
CN104657204B (zh) * | 2013-11-22 | 2018-05-04 | 华为技术有限公司 | 短任务处理方法、装置及操作系统 |
CN113760502A (zh) * | 2021-02-02 | 2021-12-07 | 北京沃东天骏信息技术有限公司 | 用于集群的资源分配方法、装置及系统 |
CN113590301A (zh) * | 2021-09-30 | 2021-11-02 | 苏州浪潮智能科技有限公司 | 一种深度学习业务的任务调度方法及相关装置 |
Also Published As
Publication number | Publication date |
---|---|
CN102027447B (zh) | 2013-12-04 |
EP2288989A2 (en) | 2011-03-02 |
WO2009139967A2 (en) | 2009-11-19 |
JP5643190B2 (ja) | 2014-12-17 |
US8566830B2 (en) | 2013-10-22 |
EP2288989A4 (en) | 2016-06-22 |
WO2009139967A3 (en) | 2010-03-18 |
EP2288989B1 (en) | 2018-08-01 |
JP2011521354A (ja) | 2011-07-21 |
US20090288086A1 (en) | 2009-11-19 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN102027447B (zh) | 调度器中的局部任务集合 | |
CN102027452B (zh) | 调度器中的调度集合 | |
CN102047218B (zh) | 进程中的调度器实例 | |
CN101702134B (zh) | 无操作系统干预情况下调度os隔离定序器上的线程的机制 | |
CN102402419A (zh) | 用所选执行运行时执行的用户代码的运行时不可知表示 | |
US8959517B2 (en) | Cancellation mechanism for cancellable tasks including stolen task and descendent of stolen tasks from the cancellable taskgroup | |
US8468528B2 (en) | Method for selective flushing logs within multiple queues concurrently | |
CN102047217A (zh) | 重新获取对执行外部执行上下文的处理资源的控制 | |
US8291426B2 (en) | Memory allocators corresponding to processor resources | |
US8806180B2 (en) | Task execution and context switching in a scheduler | |
US9304831B2 (en) | Scheduling execution contexts with critical regions | |
US9384063B2 (en) | Eliding synchronization in a concurrent data structure |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
C06 | Publication | ||
PB01 | Publication | ||
C10 | Entry into substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
C14 | Grant of patent or utility model | ||
GR01 | Patent grant | ||
ASS | Succession or assignment of patent right |
Owner name: MICROSOFT TECHNOLOGY LICENSING LLC Free format text: FORMER OWNER: MICROSOFT CORP. Effective date: 20150506 |
|
C41 | Transfer of patent application or patent right or utility model | ||
TR01 | Transfer of patent right |
Effective date of registration: 20150506 Address after: Washington State Patentee after: Micro soft technique license Co., Ltd Address before: Washington State Patentee before: Microsoft Corp. |