[go: up one dir, main page]

CN109522101B - 用于调度多个操作系统任务的方法、系统和/或装置 - Google Patents

用于调度多个操作系统任务的方法、系统和/或装置 Download PDF

Info

Publication number
CN109522101B
CN109522101B CN201810862317.4A CN201810862317A CN109522101B CN 109522101 B CN109522101 B CN 109522101B CN 201810862317 A CN201810862317 A CN 201810862317A CN 109522101 B CN109522101 B CN 109522101B
Authority
CN
China
Prior art keywords
task
cpu
bound
tasks
core processor
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.)
Active
Application number
CN201810862317.4A
Other languages
English (en)
Other versions
CN109522101A (zh
Inventor
T.弗林德
C.库马尔
R.U.西达帕
B.S.坎达斯瓦米
V.R.因杜库里
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Samsung Electronics Co Ltd
Original Assignee
Samsung Electronics Co Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Samsung Electronics Co Ltd filed Critical Samsung Electronics Co Ltd
Publication of CN109522101A publication Critical patent/CN109522101A/zh
Application granted granted Critical
Publication of CN109522101B publication Critical patent/CN109522101B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

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/4812—Task transfer initiation or dispatching by interrupt, e.g. masked
    • G06F9/4818—Priority circuits therefor
    • 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
    • G06F9/4893—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues taking into account power or heat criteria
    • 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
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multi Processors (AREA)

Abstract

本文的各种示例实施例提供了一种用于在多核处理器上调度操作系统的多个任务的计算机化方法。该方法包括：识别要在多核处理器上执行的多个任务，以及通过给CPU绑定任务提供比非CPU绑定任务更高的偏好来确定用于调度多个任务的任务调度。此外，该方法包括基于任务调度在多核处理器上调度多个任务。

Description

用于调度多个操作系统任务的方法、系统和/或装置
相关申请的交叉引用
要求根据35 U.S.C§119的优先权权益的权利要求是在2017年9月20日向专利、外观设计和商标控制总局(Office of the Controller General of Patents,Designs&Trade Marks，CGPDTM)提交的编号为201741033259的印度专利申请的基础上提出的，其全部内容通过引用并入本文。
技术领域
本文的各种示例实施例涉及多核处理器、多核计算系统和/或多处理器系统，并且更具体地涉及用于在多核处理器和/或多处理器系统上通过考虑具有相同的优先级的CPU绑定任务和非CPU绑定任务来调度操作系统(OS)任务或决策，并相应地调度CPU绑定任务和非CPU绑定任务的方法、系统、装置和/或非暂时性计算机可读介质。
背景技术
通常，已知使用多核处理器用于一次调度多个任务。任务通常被认为是计算系统中的单个执行线程，无论是多线程应用中的线程还是进程。这些任务可以基于任务的紧急性来调度执行。运行在多核处理器平台上的大多数现有操作系统使用优先级驱动调度机制来处理紧急任务，即，抢占式任务调度器保证最高优先级的准备线程在多核处理器的任何可用核上执行。除非优先级更高的任务抢占正在执行的任务，否则该任务通常会运行一段时间(允许在具有相同优先级的另一任务开始运行之前运行该任务的一长段时间或时间片)或完成其当前的挂起活动。然而，如果两个或更多个任务的优先级相同，则基于FIFO任务调度机制调度任务，其中先到达的任务先被执行，即遵循先入先出(First-In First-Out，FIFO)的顺序，而不管任务的类型或任务的执行时间。当基于FIFO顺序执行具有相同优先级的任务时，可能存在各种坏处，诸如基于执行任务的顺序的核空闲等。此外，任务可能错过它们必须在其间被执行的截止时间。并且，基于优先级反转，可能存在非CPU绑定任务到另一CPU的迁移，这会降低整个系统利用率和效率，例如，通过增加高速缓存未命中(cache miss)和/或高速缓存抖动(cache trashing)。
因此，期望解决前述缺点和/或其它短处，或至少提供有用的替换方案。
发明内容
本文的各种示例实施例通过考虑具有相同优先级的CPU绑定任务和非CPU绑定任务并相应地在多核处理器和/或多处理器系统上调度CPU绑定任务和非CPU绑定任务来提供操作系统(OS)调度决策。
各种示例实施例针对通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好来确定用于调度包括具有相同优先级的CPU绑定任务和非CPU绑定任务的多个任务的任务调度。此外，基于所确定的任务调度，实现了与用于执行多个任务的传统技术定义和/或期望的序列(诸如，FIFO顺序)的偏离。
另外，本文的其它示例实施例在优先级反转发生时将优先级绑定到突变的非CPU绑定任务，以在多核处理器的专用核上执行，从而避免将突变的非CPU绑定任务迁移到多核处理器的另一核(即，CPU)和/或多处理器系统的另一处理器。这允许OS有效地确定每个状态下任务的性质和类型，并相应地调度任务，以避免由于任务迁移到多核处理器的另一核而涉及的延迟。
本文的各种示例实施例通过基于任务的类型有效地调度任务并改进和/或优化系统中的功耗来改进系统负载平衡。
因此，本文的至少一个示例实施例提供一种用于在多核处理器上调度操作系统的任务的计算机化方法。该方法包括：使用多核处理器识别要在多核处理器上执行的具有相同优先级水平的多个任务，多个任务包括至少一个CPU绑定任务和至少一个非CPU绑定任务；使用多核处理器确定多个任务的任务调度，该确定包括给来自多个任务的至少一个CPU绑定任务分配相对于来自多个任务的至少一个非CPU绑定任务更高的偏好；以及使用多核处理器，根据任务调度在多核处理器上调度多个任务。
在至少一个示例实施例中，该方法还包括：使用多核处理器将多个任务与期望的在多核处理器上的任务的执行序列相关联；以及使用多核处理器，基于与期望的在多核处理器上的任务的执行序列偏离的任务调度来调度多个任务。
在至少一个示例实施例中，该方法包括：使用多核处理器，在至少一个非CPU绑定任务正在访问TCM(Tightly Coupled Memory，TCM)数据的同时，将该至少一个非CPU绑定任务绑定到多核处理器的至少一个核，并且使用多核处理器，继续如同CPU绑定任务一样执行该至少一个非CPU绑定任务，直到该至少一个非CPU绑定任务对TCM内容的访问完成。
在至少一个示例实施例中，该方法还包括：使用多核处理器检查过去任务执行统计数值，并使用多核处理器，基于检查的结果自动地调度至少一个非CPU绑定任务。
在至少一个示例实施例中，该检查包括过去任务执行统计数值的调度知晓检查、任务顺序知晓检查、和高速缓存知晓检查中的至少一个。
另外，本文的至少一个示例实施例提供一种用于在多核处理器上调度操作系统(OS)的任务的计算机化方法。该方法包括：使用多核处理器检测当由于继续执行CPU绑定任务所需的条件正在被满足而导致具有比CPU绑定任务更低优先级的非CPU绑定任务的执行在多核处理器上被抢占时的优先级反转；使用多核处理器检测CPU绑定任务的执行被挂起；以及使用多核处理器在多核处理器上调度非CPU绑定任务，该调度包括将非CPU绑定任务绑定到被包括在多核处理器上的至少一个CPU核。
另外，本文的至少一个示例实施例提供一种用于调度任务的装置。该装置包括：存储器，在其上已经存储了计算机可读指令；以及多核处理器，其包括多个CPU核，该多核处理器被配置为执行计算机可读指令以进行以下各项操作：识别要在多核处理器上执行的多个任务，多个任务包括至少一个CPU绑定任务和至少一个非CPU绑定任务，并且多个任务中的每一个任务具有相同的优先级水平，确定用于调度多个任务的任务调度，该确定包括给至少一个CPU绑定任务分配相对于至少一个非CPU绑定任务更高的偏好，以及基于该任务调度在多核处理器上调度多个任务。
另外，本文的至少一个示例实施例提供一种用于调度任务的装置。该装置包括：存储器，已经在其上存储了计算机可读指令；以及多核处理器，其包括多个CPU核，该多核处理器被配置为执行计算机可读指令以进行以下各项操作：检测当由于继续执行CPU绑定任务所需的条件正被满足而导致的具有比CPU绑定任务更低优先级的非CPU绑定任务的执行在多核处理器上被抢占时的优先级反转；检测CPU绑定任务的执行被挂起；以及在多核处理器上调度非CPU绑定任务以用于执行，该调度包括将非CPU绑定任务绑定到多核处理器上的至少一个CPU核。
当结合以下描述和附图考虑时，本文中的示例实施例的这些和其他方面将被更好地领会和理解。然而，应该理解的是，以下描述虽然指示了各种示例实施例及其众多具体细节，但是以例示说明而非限制的方式给出。可以在本文的示例实施例的范围内做出许多改变和修改，而不脱离本发明的精神，并且本文的示例实施例包括所有这样的修改。
附图说明
如附图中所示，从发明构思的非限制性示例实施例的更具体的描述中，发明构思的前述和其它特征将变得清楚，在附图中，贯穿不同的视图，相似的参考标记指代相似的部分。附图不一定按比例绘制，而是将重点放在说明发明构思的原理上。在附图中：
图1是示出根据现有技术的，调度具有相同优先级的CPU绑定任务和非CPU绑定任务的示例情形；
图2是示出根据至少一个示例实施例的，通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好来调度CPU绑定任务和非CPU绑定任务的示例情形；
图3示出根据现有技术的，通过CPU绑定任务进行的非CPU绑定任务的优先级反转的示例情形；
图4是示出根据至少一个示例实施例的，保持互斥体的非CPU绑定任务的优先级反转，以及通过将非CPU绑定任务绑定到在其上执行CPU绑定任务的特定的核来调度非CPU绑定任务的示例情形；
图5是示出根据现有技术的，其中CPU绑定任务中的作业错过截止时间的调度CPU绑定任务和非CPU绑定任务的示例情形；
图6是示出根据至少一个示例实施例的，通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好使得CPU绑定任务中的作业不会错过截止时间的调度CPU绑定任务和非CPU绑定任务的示例情形；
图7是示出根据至少一个示例实施例的，用于在多核处理器上调度具有相同优先级的CPU绑定任务和非CPU绑定任务的操作系统(OS)的装置的各种组件的框图；
图8是示出根据至少一个示例实施例的，通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好来调度任务的计算机化方法的流程图；以及
图9是示出根据至少一个示例实施例的，通过将非CPU绑定任务绑定到在其上执行CPU绑定任务的特定的核来调度任务的计算机化方法的流程图。
具体实施方式
现在将参考附图详细地描述本公开的各种实施例。在下面的描述中，诸如详细的配置和组件的具体细节仅被提供用于帮助对本公开的这些示例实施例的整体理解。因此，本领域技术人员应该清楚，在不脱离本公开的精神和范围的情况下，可以对本文所描述的示例实施例进行各种改变和修改。另外，为了清楚和简洁，可以省略对熟知的功能和结构的描述。
并且，本文描述的各种实施例不一定是互相排斥的，因为某些实施例可以与一个或多个其它实施例组合以形成新的实施例。
这里，本文所使用的术语“或”是指非排他性的，或除非另有指示。本文所使用的示例仅仅意图促进对本文的示例实施例的实践方式的理解，并且意图进一步使本领域技术人员可以实践本文的示例实施例。因此，该示例不应该被解释为限制本文的示例实施例的范围。
如在本领域中传统的那样，可以按照执行所描述的功能或多个功能的框来描述和示出示例实施例。在本文中可以被称为单元或模块等的这些块通过诸如逻辑门、集成电路、微处理器、微控制器、存储器电路、无源电子组件、有源电子组件、光学组件、硬连线电路等的模拟和/或数字电路来物理地实施，并且可以可选地由固件和/或软件驱动。例如，电路可以具体实现在一个或多个半导体芯片中，或诸如印刷电路板等的基底支撑物上。构成块的电路可以通过专用硬件、或通过处理器(例如，一个或多个已编程的微处理器和相关联的电路)来实施、或者通过执行块的一些功能的专用硬件和执行块的其它功能的处理器的组合来实施。示例实施例的每个块可以物理地分成两个或更多个相互作用和离散的块，而不脱离示例实施例的范围。同样地，示例实施例的块可以物理地组合成更复杂的块，而不脱离示例实施例的范围。
通常，根据系统环境和对系统环境的基本假设，任务调度方法会有很大的不同。多核处理器和/或多处理器系统用于基于优先级驱动的调度机制，在多核处理器和/或多处理器系统的不同CPU(和/或核)上顺序地和/或并行地执行任务(即，进程，线程等)。在优先级驱动的调度机制中采用抢占任务调度，其中在任何可用的处理器和/或处理器核上执行最高优先级的任务。在下文中，术语处理器和处理器核以及多核处理器和多处理器系统将可互换地来使用。然而，如果两个或更多个任务的优先级相等，则基于先入先出(FIFO)顺序来调度任务，而不管任务的类型和/或任务的执行时间。
通常，任务可以被分类为CPU绑定任务(也称为核绑定任务)和非CPU绑定任务(也称为自由运行任务)。在核绑定任务(Core Bound Task，CBT)的情况下，CBT被绑定(例如，被调度)以在多核处理器的特定的核上执行，而自由运行任务(Free Running Task，FRT)不绑定到任何特定核，因此可以在多核处理器的任何可用核上执行。但是由于传统技术方法和系统采用的FIFO顺序的任务调度，所以即使可以将FRT迁移到空闲核以用于执行时，也以FIFO的顺序执行任务。
传统技术方法和系统定义了在不考虑任务的类型的情况下，用于执行具有相同优先级的任务的顺序和/或队列/列表。不同于传统技术方法和系统，本发明构思的各种示例实施例可以用于基于要被调度的任务的任务类型来确定用于对任务进行排列以用于执行的任务调度。换句话说，通过考虑要被调度的任务的类型来定义任务调度。
因此，本文的至少一个示例实施例提供计算机化方法，用于改进和/或优化在多核处理器和/或多处理器系统上对操作系统的任务的调度。该方法包括：识别要在多核处理器上执行的具有相同优先级(例如，相同优先级水平)的多个任务，其中多个任务包括至少一个CPU绑定任务和至少一个非CPU绑定任务。此外，该方法包括确定多个任务的任务调度，其中给来自多个任务的至少一个CPU绑定任务提供(例如，分配，授予等)相对于来自多个任务的至少一个非CPU绑定任务更高的偏好。此外，该方法还包括基于任务调度在多核处理器和/或多处理器系统上调度多个任务。
因此，本文的至少一个示例实施例提供用于改进和/或优化在多核处理器和/或多处理器系统上调度操作系统的任务的计算机化方法。该方法包括：检测当由于继续执行CPU绑定任务所需的条件正在被满足而导致具有比CPU绑定任务更低的优先级的非CPU绑定任务的执行在多核处理器和/或多处理器系统上被抢占时的优先级反转。此外，该方法包括检测CPU绑定任务的执行被挂起，并且通过将非CPU绑定任务绑定到多核处理器和/或多处理器系统上的正在其上执行CPU绑定任务的特定核来调度非CPU绑定任务。
不同于传统方法和系统，示例实施例中的至少一个的方法和系统通过考虑要被调度的任务的类型来确定任务调度。由于非CPU绑定任务不具有核紧密度并且可以在任何核上执行，所以至少一个示例实施例给相同优先级的CPU绑定任务提供相对于非CPU绑定任务的更高的偏好以实现改进的和/或优化的任务的调度，这将保证与核和/或处理器相关联(例如，位于、分配给、由其使用等)的更好的核利用率、处理器利用率和/或高速缓存利用率。
至少一个示例实施例可用于通过基于任务的类型(诸如，CPU绑定任务和非CPU绑定任务)定义任务的执行的特定顺序来执行任务，而不是遵循由传统技术调度器所定义的传统技术FIFO排序。因此，与期望的和/或预定义的任务的执行顺序的偏离提供了有效的CPU利用率。
此外，至少一个示例实施例允许调度器在一段时间内自动地学习任务的执行次序，并基于过去任务执行统计数值自动地确定调度决策，以基于该学习将任务分派给不同的核。基于一段时间内的学习做出的调度器的稳健调度决策，可以动态地实现改进和/或优化的高速缓存和核利用率。这样的调度器还存储核执行历史以及针对所有任务的核特定执行持续时间。
此外，至少一个示例实施例允许，基于调度器学习来在核上重新调度在被抢占之前更早被调度的非CPU绑定任务。采取用于重新调度的决策基于两个因素：
1.当前调度和先前调度之间的时间间隙，以及
2.在给定核和/或处理器上的最后执行持续时间。
在传统技术方法和系统中，任务具有大量的等待时间和响应时间。任务的大量的等待时间和响应时间不允许CPU充分使用CPU资源，从而降低有效的CPU利用率。不同于传统技术方法和系统，至少一个示例实施例通过考虑任务的类型来提供改进的和/或优化的任务的调度，从而增强CPU利用。
在传统技术方法和系统中，在已经发生任务的优先级反转之后，突变(bumped)的非CPU绑定任务可能被迁移到另一CPU以用于执行，因为该突变的非CPU绑定任务没有绑定到任何CPU。不同于传统技术方法和系统，至少一个示例实施例可以用于将突变的非CPU绑定任务绑定到在其上执行CPU绑定任务的特定的核，以避免突变的非CPU绑定任务到另一CPU的迁移，即，通过将突变的非CPU绑定任务绑定到特定的CPU，突变的非CPU绑定任务被转换为CPU绑定任务。
在传统技术方法和系统中，任务内的作业可能由于任务调度效率低(诸如调度任务在忙于执行另一任务的CPU和/或处理器上运行)而错过任务必须在其间被执行的截止时间。例如，基于不考虑任务的类型的FIFO顺序来调度任务。不同于传统技术方法和系统，至少一个示例实施例通过考虑要被执行的任务的任务类型来调度任务，其允许任务内的作业不会错过任务必须在其间被执行的截止时间。
现在参考附图，并且更具体地参考图1至图9示出了几个示例实施例，其中贯穿所有附图，相似的参考字符表示相似的特征。
图1是示出根据现有技术的、调度具有相同优先级的CPU绑定任务和非CPU绑定任务的示例情形。
在传统技术方法和系统中，当多个任务的优先级相等时，基于FIFO任务调度机制来调度任务，其中，先到达的任务先被执行，即，遵循FIFO顺序，而不管任务的类型和/或任务的执行时间。
参考图1，考虑三个任务T10-F、T10-C0和T10-C1。T10-F指示作为非CPU绑定任务(例如，FRT)的具有优先级10的第一任务。类似地，T10-C0指示被绑定为在CPU 0上执行(例如，CPU绑定的或核绑定的，并且因此必须由特定的CPU和/或核执行或被分配为由特定的CPU和/或核执行)的具有优先级10的第二任务，以及T10-C1指示被绑定为在CPU 1上执行的具有优先级10的第三任务。此外，可以观察到所有的任务具有相同的优先级，例如，所有三个任务都具有优先级10。存在两个CPU，即CPU 0(或C0)和CPU 1(或C1)。所有三个任务都准备好在时间0处执行，如图1中的任务准备列表所示。按照FIFO顺序将任务添加到任务准备列表中。此外，表1示出了图1中任务被接收的顺序、任务的类型、任务被添加到任务准备列表中的时刻以及每个任务的执行时间。
表1
根据传统技术的FIFO任务调度机制，基于任务的到达将任务顺序地分发给CPU。在传统技术的FIFO任务调度机制中，先到达的任务先执行，即任务调度是基于FIFO顺序。由于任务T10-F是系统接收到的第一个任务(如表1所示)，则调度器(未示出)基于图1的FIFO任务调度算法将任务T10-F分派给CPU 0。任务准备列表接收的下一个任务是任务T10-C0，基于FIFO任务调度算法，任务T10-C0在任务T10-F的执行之后被绑定为(例如，被分派，被分配，被调度等)在CPU 0上执行。因此，当任务T10-C0准备被执行时，CPU 0忙于执行任务T10-F。此外，即使CPU 1空闲，调度器也不能将任务T10-C0分派为在CPU 1上执行，因为任务T10-C0被绑定为由CPU 0执行。因此调度器将任务T10-C0映射为也在CPU 0上执行。但是由于任务T10-F已经在CPU 0上执行，所以在开始任务T10-C0的执行之前，任务T10-C0将必须等待直到任务T10-F的执行在CPU 0上完成。任务T10-C1是任务准备列表中的下一任务。由于任务T10-C1也是CPU绑定任务，并且被绑定为在CPU 1上执行，所以调度器将任务T10-C1分派给CPU 1。因为CPU 1在任务T10-C1被分派给CPU 1之前是空闲的，所以任务T10-C1立即开始执行。
CPU 0的时间轴示出在让出CPU 0之前，任务T10-F将继续执行直到完成。在10毫秒的末尾处，例如在任务T10-F已经让出CPU 0的时候，任务T10-C0将开始在CPU 0上执行。因此，CPU 0活动了(例如，执行任务)20毫秒。此外，任务T10-C0的任务完成时间为20毫秒，因为任务T10-C0只有在任务T10-F在CPU 0上完成执行之后才可以开始执行。CPU 1的时间轴表示在2毫秒中执行了T10-C1，此后，由于在将T10-C1调度到CPU 1之前CPU 1处于空闲状态，所以CPU 1不具有任何要被执行的任务。此外，平均任务完成时间被计算为：
平均任务完成时间＝(T10-F完成时间+T10-C0完成时间+T10-C1完成时间)/3 (1)
＝(10+20+2)/3
＝10.66毫秒，这暗示CPU 0和CPU 1的CPU利用率很差
因此，基于以上平均任务完成时间的计算，观察到当具有相等优先级的任务基于FIFO排序来执行时，存在诸如核空闲、大量和/或增加的任务完成时间等的缺点，这降低了整个系统的利用率和效率。此外，特别因为功耗是主要关心的问题，并且低效的CPU利用率导致增加且不必要的功耗，所以平均任务完成时间和CPU利用率是多核处理器和/或多处理器系统中的重要因素。由于以FIFO顺序序的任务调度，所以并未考虑降低整个系统效率的这些因素。
图2是示出根据至少一个实施例的，通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好来调度CPU绑定任务和非CPU绑定任务的示例情形。
不同于传统技术方法和系统，至少一个示例实施例通过考虑正被调度的任务的类型来调度具有相同优先级的任务。例如，根据至少一个示例实施例，调度器在调度任务的同时，给CPU绑定任务提供相对于非CPU绑定任务更高的偏好。
参考图2，结合图1，考虑三个任务T10-F、T10-C0和T10-C1都具有相同的优先级10。虽然在图2中仅示出了三个任务和两个CPU，但是示例实施例不限于此，并且可以存在任何数量的要被调度的任务和/或任何数量的CPU。另外，虽然图2的三个任务都具有相同的优先级水平，但是示例实施例不限于此，并且任务可以具有任何优先级水平。
参考图2，所有三个任务在时间0处准备，如任务准备列表中所示。此外，表2示出了图2中任务被接收的顺序、任务的类型、任务被添加到任务准备列表中的时刻以及每个任务的执行时间。
表2
根据至少一个示例实施例，基于要被调度的任务的类型将任务顺序地分发给CPU。调度器被配置为在调度任务时，给相同优先级的CPU绑定任务提供相对于相同优先级的非CPU绑定任务更高的偏好。此外，调度器仅仅在特定的CPU已经完成执行绑定到该特定CPU的所有任务之后，才会将非CPU绑定任务分派给该特定的CPU。
在任务准备列表中首先接收到非CPU绑定任务T10-F(如图2所示)，此后，接收到CPU绑定任务T10-C0。但是调度器在分派非CPU绑定任务T10-F之前首先分配CPU绑定任务T10-C0在CPU 0上执行，因为在调度任务时，给予了CPU绑定任务相对于非CPU绑定任务更高的偏好。任务准备列表中的下一个任务是绑定到CPU 1的CPU绑定任务T10-C1。调度器将CPU绑定任务T10-C1分派给CPU 1。此外，根据表2，CPU绑定任务T10-C1的执行时间是2毫秒。在2毫秒的末尾处，当CPU绑定任务T10-C1已经完成在CPU 1上的执行时，调度器将首先接收到的非CPU绑定任务T10-F分派给CPU 1。因此，CPU 0活动了10毫秒(即，CPU绑定任务T10-C0的执行时间)并且CPU 1活动了12毫秒(即，CPU绑定任务T10-C1的执行时间和非CPU绑定任务T10-F的执行时间)。由于基于对任务类型的考虑来调度任务，所以CPU绑定任务T10-C0的执行时间与20毫秒(根据在图1的情况下描述的传统技术FIFO调度机制)相比仅为10毫秒。此外，两个CPU中的所有任务的平均任务完成时间被计算为：
平均任务完成时间＝(T10-F完成时间+T10-C0完成时间+T10-C1完成时间)/3 (1)
＝(12+10+2)/3
＝8毫秒
因此，基于以上平均任务完成时间的示例计算，观察到，当通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好来执行相等优先级的任务时，平均任务完成时间已经被改进了。因此，通过在调度任务时给CPU绑定任务提供相对于非CPU绑定任务更高的偏好，调度器提供了改进的负载平衡、功率改进和/或功率优化以及增加的系统效率。
图3是示出根据现有技术的、由CPU绑定任务进行非CPU绑定任务的优先级反转，以及由CPU绑定任务请求由非CPU绑定任务保持的互斥体的示例情形。
互斥体是作为包括但不限于Unix、Linux、定制内核、实时操作系统(Real timeoperating systems，RTOS)等的所有类型的操作系统的一部分(例如，固有的和/或可用的)的同步实体(例如，同步资源，供多个竞争线程、进程、任务等使用的锁)。互斥体(例如，互相排斥对象)是被创建以使得多个程序任务可以轮流共享相同的系统资源(诸如访问文件、堆、全局资源、软件组件、硬件组件、核、处理器等)的程序对象。当多个竞争对手试图同一时间(例如，同时)访问共享资源时，互斥体表现得就像用于保护共享资源的密钥。例如，当一个或多个任务想要访问共享资源时，(多个)任务必须在它们被授权访问共享资源之前首先获得密钥(例如，互斥体)。当任务已经完成访问共享资源时，它必须释放密钥(例如，互斥体)，从而允许其它任务获得密钥(例如，互斥体)并且然后访问共享资源。只有已经获得互斥体的任务将被允许访问共享资源，并在特定时刻在例如CPU的关键部分中执行。当例如，更高优先级的任务尝试获取被更低优先级的任务保持的CPU相关联的互斥体时，会发生优先级反转。保持互斥体的更低优先级的任务必须在更高优先级的任务可能被执行之前释放互斥体。这会造成不可避免的延迟。
作为另一示例，考虑更低优先级的任务(例如，互斥体拥有任务)可以访问CPU共享资源并且更低优先级的任务在CPU的关键部分中执行。如果更高优先级的任务(例如，互斥体请求任务)抢占更低优先级的任务，并且请求相同的互斥体(例如，由更低优先级的任务保持的互斥体)，则互斥体请求任务的优先级将被分派给互斥体拥有任务，互斥体拥有任务将以更高优先级执行。因此，将更高优先级任务的优先级分配给更低优先级任务以使得更低优先级任务以更高优先级执行的过程被称为优先级反转。
参考图3，考虑由调度器(未示出)在CPU 0上调度两个任务T10-F和T4-C0。在时间0处，任务T10-F正在CPU 0上执行，同时没有其它任务准备在CPU 1上执行。
任务T10-F已经获取了互斥体M1并且正在CPU 0上执行。任务T10-C1正在CPU 1上执行。在时间5处，更高优先级的任务T4-C0已准备好在CPU 0上执行，并抢占更低优先级的任务T10-F。此外，由于任务T4-C0是绑定到CPU 0的CPU绑定任务，因此即使CPU 1正在执行更低优先级的任务或者如果CPU 1空闲，调度器也不能将任务T4-C0调度到CPU 1。任务T10-F还没有完成在CPU 0的关键部分上的执行，因此任务T10-F还没有释放互斥体M1(即，即使在被抢占之后，任务T10-F也拥有互斥体M1)。
执行一段时间之后的任务T4-C0尝试获取由任务T10-F保持的互斥体M1。然而，任务T4-C0将不能获取互斥体M1，因为保持互斥体M1的任务T10-F还没有释放互斥体M1。这将导致任务T10-F到任务T4-F的优先级的突变。这将使任务T4-F成为当时(例如，在那时)最高优先级的任务。任务T10-F将以优先级4而不是优先级10执行。此外，由于优先级反转，任务T10-F将如同任务T4-F一样，以优先级4执行，直到互斥体M1的释放。当任务T4-F完成在CPU0的关键部分中的执行时，它将释放互斥体M1。由于任务T4-F仍是一个非CPU绑定任务(即，自由运行任务)，所以基于情形，有可能任务T4-F被抢占并被迁移到SMP集群内的另一个CPU。即使更低优先级的任务的优先级被突变成更高优先级的任务，但它仍缺乏确定性，因为它仍作为非CPU绑定任务执行，并且基于不同的情形可能被迁移到其它CPU，这导致执行更高优先级的互斥体挂起任务，并且还导致额外的高速缓存抖动。
图4是示出根据至少一个示例实施例的，保持互斥体的非CPU绑定任务的优先级反转，以及通过将非CPU绑定任务绑定到在其上执行CPU绑定任务的特定的核来调度非CPU绑定任务的示例情形。
不同于传统技术方法和系统，在任务的优先级反转之后，可以将突变的非CPU绑定任务迁移到另一CPU以用于执行，至少一个示例实施例将突变的非CPU绑定任务绑定到其中CPU绑定任务正在执行的特定核(和/或特定处理器)，以避免突变的非CPU绑定任务迁移到另一CPU以用于执行，直到突变的非CPU绑定任务释放关键资源(例如，互斥体)。因此，将突变的非CPU绑定任务绑定到正在执行CPU绑定任务的特定核将避免由于任务上下文传递(例如，将与任务相关联的上下文数据加载回存储器)而释放关键资源中涉及的任何延迟和/或由于任何其它CPU更高优先级的活动造成的抢占。
现在参照图4，结合图3，考虑由调度器(未示出)在CPU 0上调度两个任务T10-F和T4-C0。任务T10-F正在执行，同时没有其它任务准备在时间0处执行。
任务T10-F在CPU 0上执行的同时获取互斥体M1。但是在任务T10-F能够完成执行并释放互斥体M1之前，任务T10-F(例如，优先级10)在时间5处被准备好的更高高优先级任务T4-C0(例如，优先级4)抢占。根据示例实施例，由于优先级4是比优先级10更高的优先级，所以任务T4-C0被调度为在时间5处在CPU 0上执行。并且，任务T4-C0是绑定到CPU 0的CPU绑定任务，并且不能被调度在CPU 1上执行，即使CPU 1正在执行更低优先级的任务或者如果CPU 1空闲。此外，任务T4-C0在执行一段时间之后将尝试获取由任务T10-F保持的互斥体M1。然而，任务T4-C0将不能获取互斥体M1，因为保持互斥体M1的任务T10-F还没有释放互斥体M1，因为它还没有完成执行。这将导致任务T10-F的优先级突变到任务T4-C0的优先级水平。
调度器允许非CPU绑定任务T10-F突变优先级，并且还将非CPU绑定任务转换为CPU绑定任务，即，将非CPU绑定任务T10-F转换为与CPU绑定任务T4-C0相同的优先级水平。优先级的突变将对任务T4-C0提供在当时具有最高优先级，并且任务T4-C0将如同CPU绑定任务一样，以优先级4执行。此外，通过将非CPU绑定任务绑定到特定的CPU来执行非CPU绑定任务到CPU绑定任务的转换，因此这里不会存在由于任务上下文传递涉及的延迟和/或由于其它高优先级活动而造成的抢占。此外，任务T4-C0将在CPU的关键部分内完成执行并释放互斥体M1。
作为非CPU绑定任务在CPU 0上执行的任务T10-F将利用CPU 0的资源，诸如高速缓存等。如果任务T10-F由于抢占而被移动到其它CPU中的一个，则存储在与CPU 0相关联的(多个)高速缓存中的任务T10-F高速缓存的内容将丢失。突变的非CPU绑定任务T10-F到CPU绑定任务T4-C0的转换提供了突变的非CPU绑定任务的执行的连续性，并为系统提供确定性。
在至少一个示例实施例中，调度器记录CPU绑定任务的平均执行时间。当发现CPU绑定任务的执行时间低于某个期望的阈值时，可以推迟将非CPU绑定任务强制重新对准到另一CPU。如果另一CPU活动发现挂起的非CPU绑定任务具有更高的优先级，则调度器有两个选项：
1.允许另一CPU挑选更高优先级的非CPU绑定任务来执行，这将减少核空闲。
2.不允许(例如，拒绝，限制等)另一CPU挑选更高优先级的非CPU绑定任务来执行，从而保证更好的高速缓存利用率。
在嵌入式系统中，紧密耦合存储器(TCM)存储更频繁访问的代码和数据(例如，高优先级代码和/或数据)。在至少一个示例实施例中，CPU的高优先级代码和/或数据被放置于CPU的TCM中，并且非CPU绑定任务到CPU绑定任务的转换将提供对此CPU的高优先级代码的无障碍访问。
在另一示例实施例中，用于关键部分的代码的副本被放置于所有CPU的TCM中。非CPU绑定任务到CPU绑定任务的转换将提供对放置于CPU的TCM中的关键部分的代码的访问。
图5是示出根据现有技术的，其中CPU绑定任务中的作业错过截止时间的调度CPU绑定任务和非CPU绑定任务的示例情形。
现在参考图5，考虑在CPU 0上调度两个周期性任务T0和T1的序列。周期性任务T(i)由包括阶段、周期、执行时间、相对截止时间、优先级和核紧密度等的各种参数来定义。参数被描述为：阶段φ(i)是任务到达时间轴的第一时间；周期ρ(i)是在其后任务将再次发生的时间；执行时间e(i)是任务的执行所需的时间；相对截止时间D(i)是指任务必须在其间完成并且在其后任务将期满的截止时间；prio(i)是任务的优先级；bind(i)是任务的核紧密度，即，将任务的类型定义为CPU绑定或非CPU绑定。
这些任务是周期性的，并且可能会在下一个时段再次发生。因此，作业J代表当时呈现的任务。每个任务可以具有任意数量的作业，即，任何任务可以周期性地再次发生任意次。
考虑分别为CPU绑定和非CPU绑定的任务T0(2,10,5,10,5,0)和T1(0,20,10,20,5,#)。T1的作业J(1,1)在时间0处准备好。因为没有其它任务在时间0处准备，所以作业J(1,1)在时间0处开始执行。此外，作业J(1,1)具有10毫秒的执行时间。即使任务T0的作业J(0，1)在时间2处准备好，任务T0也不会被允许在CPU 0上执行，因为基于FIFO顺序，任务T1已经在CPU 0上执行。此外，由于任务T0被绑定到CPU 0，所以即使CPU 1空闲，它也不能在CPU 1上执行。因此，任务T0将必须等待，直到任务T1的执行完成。此外，任务T0的相对截止时间D(i)为10毫秒，并且非CPU绑定任务T1的执行时间为10毫秒，因此任务T0中的作业将错过相对截止时间。
图6是示出根据至少一个示例实施例的，通过给CPU绑定任务提供相对于非CPU绑定任务更高的偏好使得CPU绑定任务中的作业不会错过截止时间的调度CPU绑定任务和非CPU绑定任务的示例情形。
在传统技术方法和系统中，任务内的作业错过任务必须被执行的截止时间，因为任务是基于不考虑任务类型和任务执行时间的FIFO排序机制来调度的。不同于传统技术方法和系统，至少一个示例实施例通过考虑任务的类型来调度任务，其保证任务内的作业(例如，任务包括多个作业)不会错过任务必须被在其间被执行的截止时间。
结合图5参考图6，考虑在CPU 0上调度两个周期性任务T0和T1的序列。
考虑分别为CPU绑定和非CPU绑定的任务T0(2,10,5,10,5,0)和T1(0,20,10,20,5,#)。任务T1的作业J(1,1)在时间0处准备好。因为没有其它任务在时间0处准备好，所以作业J(1,1)在时间0处开始执行。任务T0的作业J(0，1)在时间2处准备好。由于T0是CPU绑定任务，所以调度器将给CPU绑定任务提供相对于非CPU绑定任务更高的偏好，即，调度器在时间2处抢占任务T1的作业J(1,1)并允许任务T0的作业J(0，1)在CPU 0上执行。因此，任务T0的作业J(0，1)将不会错过10毫秒的相对截止时间。此外，由于CPU 1处于空闲状态，所以任务T1的作业J(1,1)被迁移到CPU 1并且在CPU 1上执行。
通过给CPU绑定任务相对于非CPU绑定任务更高的偏好来调度任务允许在截止时间之内执行任务。此外，至少一个示例实施例的调度机制通过在处于空闲状态的CPU 1上执行任务T1的作业J(1,1)来保证更好的系统利用率。因此，通过考虑任务的类型的任务的调度提供增强的CPU利用率和CPU效率。
图7是示出根据至少一个示例实施例的，用于改进和/或最优化在多核处理器130上调度具有相同优先级的CPU绑定任务和非CPU绑定任务的操作系统(OS)的装置100的各种组件的框图。
在至少一个示例实施例中，装置100可以是，例如，移动电话、智能电话、个人数字助理(Personal Digital Assistants，PDA)、平板电脑、可穿戴设备、物联网(Internet ofthings，IoT)设备、智能设备、个人计算机、膝上型计算机、服务器等。
装置100包括操作系统110、作为操作系统110的一部分的调度器120、多核处理器130以及存储器140，但示例实施例并不限于此。
在至少一个示例实施例中，操作系统(OS)110是管理装置元件和软件资源的系统软件，并且在至少一个处理器核和/或处理器上执行。OS 110可以在与多核处理器130分离的处理器上执行，并且/或者可以在多核处理器130的处理器核中的一个或多个处理器核上执行。本文所描述的调度原则用于RTOS，但可以应用于任何系统。
在至少一个示例实施例中，作为操作系统110的一部分的调度器120(例如，调度器120可以被包括在操作系统110中)可以被配置为接收多个任务并以期望的和/或预定义的在多核处理器130上执行的序列来排列多个任务。调度器120基于作为CPU绑定任务和非CPU绑定任务的任务的类型来识别多个任务。
此外，调度器120确定多个任务的优先级。一确定多个任务具有不同的优先级，就遵循在执行更低优先级的任务之前执行更高优先级的任务的传统技术机制。一确定多个任务具有相同的优先级，调度器120就确定用于调度多个任务的任务调度。
调度器120通过给CPU绑定任务提供相对于非CPU绑定任务的更高的偏好来确定用于调度多个任务的任务调度。此外，调度器120基于与期望的和/或预定义的任务的序列偏离的任务调度来调度多个任务。此外，调度器120还可以被配置为基于一段时间内存储在存储器中的核执行历史和所有任务的核特定执行持续时间来确定任务调度。
在另一示例实施例中，调度器120可以被配置为确定由于继续执行CPU绑定任务所需的条件正被满足而造成的具有更低优先级的非CPU绑定任务已经被抢占。例如，继续执行CPU绑定任务所需的条件可以是互斥体(和/或信号标、锁等)被非CPU绑定任务锁住，但并不限于此。
此外，调度器120可以被配置为在执行任务时检测已经发生优先级反转。优先级反转在CPU绑定的更高优先级的任务尝试获取已经由非CPU绑定的更低优先级的任务保持的互斥体时发生。互斥体与保证CPU的关键部分中的代码的互相排斥的执行和/或访问共享的CPU的资源相关联。通常，将互斥体请求CPU绑定更高优先级任务的优先级分配给互斥体拥有非CPU绑定更低优先级任务，以使得非CPU绑定任务以更高优先级执行的过程被称为优先级反转。优先级反转将非CPU绑定任务的优先级改变为更高优先级(即，CPU绑定任务的优先级值将被分派给非CPU绑定任务，或换句话说，非CPU绑定任务的优先级值将被改变为与CPU绑定任务的优先级值相同)。
然而，当更高优先级的CPU绑定任务到达时，非CPU绑定任务仍被迁移到另一核。此外，为了保证继续执行在当时拥有互斥体的非CPU绑定任务，调度器120被配置为将已经进行优先级反转的非CPU绑定任务转换为CPU绑定任务。调度器120通过将非CPU绑定任务绑定到特定的核来将非CPU绑定任务转换成CPU绑定任务，在该特定的核上执行该CPU绑定任务。将非CPU绑定任务绑定到特定的核保证非CPU绑定任务在特定的核上完成执行并且不会迁移到另一核。
在至少一个示例实施例中，调度器120可以被配置为存储CPU执行历史和所有任务的CPU特定执行持续时间。此外，调度器120可以被配置为基于已经执行的任务的统计数值来学习(例如，调度器120被配置为检查过去任务执行统计数值)，该学习包括调度知晓、任务顺序知晓、和高速缓存知晓学习中的至少一个；并且基于该学习自动地调度任务。
在至少一个示例实施例中，多核处理器130可以是能够执行软件的任何类型的一个或多个处理器，诸如微处理器、数字信号处理器、微控制器等，其包括相同集群中的两个或更多个核。根据至少一个其它示例实施例，多核处理器130可以是多处理器系统、分布式处理系统、云处理系统等。
在至少一个示例实施例中，存储器140可以包括非易失性储存元件。这样的非易失性储存元件的示例可以包括磁性硬盘、光盘、软盘、闪速存储器、电可编程存储器(electrically programmable memory，EPROM)的形式、和/或电可擦除及可编程存储器(electrically erasable and programmable memory，EEPROM)。另外，存储器140，在一些示例中，可以考虑为非暂时性存储介质。术语“非暂时性”可以指示存储介质不具体实现为载波或传播的信号。然而，术语“非暂时性”不应该被解释存储器140不可移动。在一些示例中，存储器140可以被配置为存储比存储器的信息量更大的信息。在某个示例中，非暂时性存储介质可以存储能够随着时间改变的数据(例如，在随机存取存储器(Random AccessMemory，RAM)、高速缓存、寄存器等中)。
图8是示出根据至少一个示例实施例的，通过给相同优先级的CPU绑定任务提供相对于非CPU绑定任务更高的偏好来改进和/或优化任务的调度的计算机化方法的流程图。
参考图8，在操作802处，装置100识别要在多核处理器130上执行的具有相同优先级的多个任务。例如，在如图7所示的装置100中，调度器120可以被配置为识别要在多核处理器130上执行的具有相同优先级的多个任务。
在操作804处，装置100通过给相同优先级的CPU绑定任务提供相对于非CPU绑定任务更高的偏好来确定用于调度多个任务的任务调度。例如，在如图7所示的装置100中，调度器120可以被配置为通过给CPU绑定任务提供比非CPU绑定任务更高的偏好来确定用于调度多个任务的任务调度。
在操作806处，装置100根据任务调度，在多核处理器130上调度多个任务。例如，在如图7所示的装置100中，调度器120可以被配置为根据任务调度，来多核处理器130上调度多个任务。
图9是示出根据至少一个示例实施例的，通过将非CPU绑定任务绑定到在其上执行CPU绑定任务的特定的核，来改进和/或优化任务的调度的计算机化方法的流程图。
参考图9，在操作902处，装置100检测当由于继续执行CPU绑定任务所需的条件正被满足而造成具有比CPU绑定任务更低优先级的非CPU绑定任务的执行在多核处理器上被挂起时的优先级反转。例如，在如图7所示的装置100中，调度器120可以被配置为检测，当由于继续执行CPU绑定任务所需的条件正被满足而造成具有比CPU绑定任务更低的优先级的非CPU绑定任务的执行在多核处理器上被挂起时的优先级反转。
在操作904处，装置100检测CPU绑定任务的执行完成。例如，在如图7所示的装置100中，调度器120可以被配置为检测CPU绑定任务的执行完成。
在操作906处，装置100通过将非CPU绑定任务绑定到多核处理器130上的、在其上执行CPU绑定任务的特定的核，来调度非CPU绑定任务。例如，在如图7所示的装置100中，调度器120可以被配置为通过将非CPU绑定任务绑定到多核处理器130上的特定的核来调度CPU绑定任务，在该特定的核上执行CPU绑定任务。
本文所公开的各种示例实施例可以通过在至少一个硬件设备上运行和执行网络管理功能以控制元件的至少一个软件程序来实施。
特定实施例的前述描述将完全地揭示本文的示例实施例的一般特性，在不脱离本发明构思的情况下，其它人能够通过应用当前知识容易地修改这样的特定实施例和/或使这样的特定实施例适应于各种应用，因此，这样的适应和修改应该意图被包含在所公开的示例实施例的等同物的含义和范围之内。要理解，本文所采用的词组或术语是为了描述的目的而并非为了限制。因此，虽然已经按照各种示例描述了本文的示例实施例，但本领域技术人员将认识到本文的示例实施例可以利用如本文所描述的示例实施例的精神和范围内的修改来实践。

Claims (12)

1.一种用于在多核处理器上调度操作系统的任务的计算机化方法，包括：
使用所述多核处理器识别要在多核处理器上执行的具有相同优先级水平的多个任务，所述多个任务包括至少一个CPU绑定任务和至少一个非CPU绑定任务，所述至少一个CPU绑定任务是绑定到在多核处理器的特定核上执行的至少一个任务，并且所述至少一个非CPU绑定任务是要在多核处理器的任何核上执行的至少一个任务；
使用所述多核处理器确定所述多个任务的任务调度，所述确定包括给来自所述多个任务的至少一个CPU绑定任务分配相对于来自所述多个任务的至少一个非CPU绑定任务更高的偏好，所述确定包括：
检查过去任务执行统计数值，并且
基于所述过去任务执行统计数值，自动地学习所述任务调度的多个任务的执行顺序；以及
使用所述多核处理器，基于所述任务调度在多核处理器上调度所述多个任务。
2.如权利要求1所述的方法，还包括：
使用所述多核处理器，将所述多个任务与期望的在多核处理器上的多个任务的执行序列相关联；以及
使用所述多核处理器，基于与期望的在所述多核处理器上的所述多个任务的执行序列偏离的任务调度来调度所述多个任务。
3.如权利要求1所述的方法，还包括：
使用所述多核处理器，在所述至少一个非CPU绑定任务正在访问紧密耦合存储器TCM数据的同时，将所述至少一个非CPU绑定任务绑定到所述多核处理器的至少一个核；以及
使用所述多核处理器，继续如同CPU绑定任务一样执行所述至少一个非CPU绑定任务，直到所述至少一个非CPU绑定任务对TCM内容的访问完成。
4.如权利要求1所述的方法，其中，所述检查包括调度知晓检查、任务顺序知晓检查、和高速缓存知晓检查中的至少一个。
5.一种用于在多核处理器上调度操作系统的任务的计算机化方法，包括：
使用多核处理器识别要在所述多核处理器上执行的多个第一任务，所述多个第一任务包括至少一个CPU绑定第一任务和至少一个非CPU绑定第一任务，并且所述多个第一任务中的每一个具有相同的优先级水平；
使用所述多核处理器确定对所述多个第一任务的调度的任务调度，所述确定包括给所述至少一个CPU绑定第一任务分配相对于所述至少一个非CPU绑定第一任务更高的偏好；
使用所述多核处理器，基于所述任务调度在多核处理器上调度所述多个第一任务；
使用多核处理器检测当由于继续执行CPU绑定第二任务所需的条件正在被满足而导致非CPU绑定第一任务的执行在多核处理器上被CPU绑定第二任务抢占时的优先级反转的发生，所述CPU绑定第二任务具有比所述非CPU绑定第一任务更高的优先级；
使用多核处理器检测所述CPU绑定第二任务的执行被挂起；以及
使用多核处理器调度在多核处理器上执行的所述非CPU绑定第一任务，所述调度包括将非CPU绑定第一任务绑定到被包括在多核处理器中的至少一个CPU核。
6.如权利要求5所述的方法，其中，继续执行非CPU绑定第一任务所需的条件包括互斥体正被非CPU绑定第一任务锁住。
7.如权利要求5所述的方法，还包括：
使用所述多核处理器检查过去任务执行统计数值；以及
使用所述多核处理器，基于所述检查的结果自动地调度所述非CPU绑定第一任务。
8.如权利要求7所述的方法，其中，所述检查包括所述过去任务执行统计数值的调度知晓检查、任务顺序知晓检查、和高速缓存知晓检查中的至少一个。
9.一种用于调度任务的装置，包括：
存储器，在其上已经存储了计算机可读指令；以及
多核处理器，其包括多个CPU核，所述多核处理器被配置为执行计算机可读指令以进行以下各项操作：
识别要在多核处理器上执行的多个任务，所述多个任务包括至少一个CPU绑定任务和至少一个非CPU绑定任务，并且所述多个任务中的每一个具有相同的优先级水平，所述至少一个CPU绑定任务是绑定到在多核处理器的特定核上执行的至少一个任务，并且所述至少一个非CPU绑定任务是要在多核处理器的任何核上执行的至少一个任务，
确定用于调度所述多个任务的任务调度，所述确定包括给所述至少一个CPU绑定任务分配相对于所述至少一个非CPU绑定任务更高的偏好，所述确定包括：
检查过去任务执行统计数值，并且
基于所述过去任务执行统计数值，自动地学习所述任务调度的多个任务的执行顺序，以及
基于所述任务调度在多核处理器上调度所述多个任务。
10.如权利要求9所述的装置，其中，所述多核处理器还被配置为：
将所述多个任务与期望的在多核处理器上的多个任务的执行序列相关联；
基于使多个任务的执行序列偏离期望的在所述多核处理器上的多个任务的执行序列的任务调度来调度所述多个任务。
11.如权利要求9所述的装置，其中，所述多核处理器还被配置为：
在所述至少一个非CPU绑定任务正在访问紧密耦合存储器TCM数据的同时，将所述至少一个非CPU绑定任务绑定到所述多核处理器的至少一个核；并且
如同CPU绑定任务一样，继续执行所述至少一个非CPU绑定任务，直到完成所述至少一个非CPU绑定任务对TCM内容的访问。
12.如权利要求9所述的装置，其中，所述检查包括过去任务执行统计数值的调度知晓检查、任务顺序知晓检查、和高速缓存知晓检查中的至少一个。
CN201810862317.4A 2017-09-20 2018-08-01 用于调度多个操作系统任务的方法、系统和/或装置 Active CN109522101B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
IN201741033259 2017-09-20
IN201741033259 2017-09-20

Publications (2)

Publication Number Publication Date
CN109522101A CN109522101A (zh) 2019-03-26
CN109522101B true CN109522101B (zh) 2023-11-14

Family

ID=65719280

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810862317.4A Active CN109522101B (zh) 2017-09-20 2018-08-01 用于调度多个操作系统任务的方法、系统和/或装置

Country Status (2)

Country Link
US (1) US11055129B2 (zh)
CN (1) CN109522101B (zh)

Families Citing this family (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2020024636A (ja) * 2018-08-08 2020-02-13 株式会社Ｐｒｅｆｅｒｒｅｄ Ｎｅｔｗｏｒｋｓ スケジューリング装置、スケジューリングシステム、スケジューリング方法及びプログラム
CN112039963B (zh) * 2020-08-21 2023-04-07 广州虎牙科技有限公司 一种处理器的绑定方法、装置、计算机设备和存储介质
CN112068960B (zh) * 2020-09-10 2024-02-06 华云数据控股集团有限公司 一种cpu资源分配方法、装置、存储介质及设备
CN112667380B (zh) * 2020-12-30 2024-09-24 珠海亿智电子科技有限公司 多处理器任务调度方法、装置及存储介质
WO2022141300A1 (zh) * 2020-12-30 2022-07-07 华为技术有限公司 一种任务调度方法及装置
CN112799787B (zh) * 2021-02-07 2023-10-03 北京华如科技股份有限公司 一种在仿真运行中改进的并行行为执行冲突消解方法及其存储介质
CN115033352A (zh) * 2021-02-23 2022-09-09 阿里云计算有限公司 多核处理器任务调度方法、装置及设备、存储介质
CN112988351A (zh) * 2021-03-08 2021-06-18 上海英恒电子有限公司 一种基于Vxworks平台的任务调度方法和装置
US20230063676A1 (en) * 2021-04-16 2023-03-02 Apple Inc. Counters For Ensuring Transactional Ordering in I/O Agent
CN114691326A (zh) * 2022-03-16 2022-07-01 中国船舶重工集团公司第七一一研究所 多任务的调度方法、多核处理器及机旁监控系统
US12293220B2 (en) 2022-04-21 2025-05-06 Dell Products L.P. Context-driven framework to migrate the applications and its dependencies by analyzing the relationships
US20240028420A1 (en) * 2022-07-22 2024-01-25 Dell Products L.P. Context driven network slicing based migration of applications and their dependencies
US12254207B2 (en) 2022-07-22 2025-03-18 Dell Products L.P. Method and system for health driven network slicing based data migration
CN115129458B (zh) * 2022-09-02 2022-11-25 腾讯科技（深圳）有限公司 基于容器的进程调度方法、装置、设备及存储介质
US12253933B2 (en) 2022-11-28 2025-03-18 Dell Products L.P. Predictive load driven proactive pre-flight check for applications
CN116319807B (zh) * 2023-03-23 2025-05-27 度小满科技(北京)有限公司 一种服务迁移方法、计算机设备和存储介质
CN116450324A (zh) * 2023-06-20 2023-07-18 北京超星未来科技有限公司 任务处理方法、装置、设备及存储介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103019810A (zh) * 2011-09-19 2013-04-03 辉达公司 具有不同执行优先级的计算任务的调度和管理
CN103080903A (zh) * 2010-08-27 2013-05-01 富士通株式会社 调度器、多核处理器系统以及调度方法
CN103218259A (zh) * 2012-01-18 2013-07-24 辉达公司 计算任务的调度和执行
CN104380257A (zh) * 2012-05-09 2015-02-25 英特尔公司 在处理器核之间调度任务

Family Cites Families (48)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5928322A (en) * 1996-11-20 1999-07-27 Silicon Graphics, Inc. Low-latency real-time dispatching in general purpose multiprocessor systems
US7178145B2 (en) * 2001-06-29 2007-02-13 Emc Corporation Queues for soft affinity code threads and hard affinity code threads for allocation of processors to execute the threads in a multi-processor system
US7167916B2 (en) * 2002-08-30 2007-01-23 Unisys Corporation Computer OS dispatcher operation with virtual switching queue and IP queues
US20070011682A1 (en) * 2003-01-02 2007-01-11 Loboz Charles Z Affinization of transaction types
US7676809B2 (en) * 2003-10-09 2010-03-09 International Business Machines Corporation System, apparatus and method of enhancing priority boosting of scheduled threads
US7904905B2 (en) * 2003-11-14 2011-03-08 Stmicroelectronics, Inc. System and method for efficiently executing single program multiple data (SPMD) programs
KR100617717B1 (ko) * 2004-12-15 2006-08-28 삼성전자주식회사 무선망에서의 스케줄링 방법
US7460558B2 (en) * 2004-12-16 2008-12-02 International Business Machines Corporation System and method for connection capacity reassignment in a multi-tier data processing system network
US7240136B2 (en) * 2004-12-16 2007-07-03 International Business Machines Corporation System and method for request priority transfer across nodes in a multi-tier data processing system network
US7512706B2 (en) * 2004-12-16 2009-03-31 International Business Machines Corporation Method, computer program product, and data processing system for data queuing prioritization in a multi-tiered network
US7788668B2 (en) * 2005-06-09 2010-08-31 Lockheed Martin Corporation System and method for implementing distributed priority inheritance
US7844970B2 (en) * 2006-08-22 2010-11-30 International Business Machines Corporation Method and apparatus to control priority preemption of tasks
US8533696B1 (en) * 2006-09-29 2013-09-10 Emc Corporation Methods and systems for allocating hardware resources to instances of software images
KR20080064608A (ko) * 2007-01-05 2008-07-09 삼성전자주식회사 ＳＰＩ(Ｓｉｍｐｌｅ ＰｒｉｏｒｉｔｙＩｎｈｅｒｉｔａｎｃｅ) 방식에 따른 멀티태스킹 방법 및임베디드 시스템
US8458712B2 (en) * 2008-04-30 2013-06-04 International Business Machines Corporation System and method for multi-level preemption scheduling in high performance processing
US20100138221A1 (en) * 2008-12-02 2010-06-03 Boys Donald R Dedicated hardware/software voice-to-text system
US20110010716A1 (en) * 2009-06-12 2011-01-13 Arvind Raghuraman Domain Bounding for Symmetric Multiprocessing Systems
WO2011051011A1 (en) * 2009-10-29 2011-05-05 International Business Machines Corporation A method, system and program to manage scheduling of processes
US8549524B2 (en) * 2009-12-23 2013-10-01 Sap Ag Task scheduler for cooperative tasks and threads for multiprocessors and multicore systems
US20110276978A1 (en) * 2010-05-10 2011-11-10 Andrew Gaiarsa System and Method for Dynamic CPU Reservation
KR101686010B1 (ko) * 2010-12-21 2016-12-13 삼성전자주식회사 실시간 멀티코어 시스템의 동기화 스케쥴링 장치 및 방법
US8726285B2 (en) * 2011-01-28 2014-05-13 Ciambella Ltd. Method and apparatus for triggering workflow deployment and/or execution
US8479207B2 (en) * 2011-02-25 2013-07-02 Qualcomm Incorporated Priority inheritance in multithreaded systems
US8990823B2 (en) * 2011-03-10 2015-03-24 International Business Machines Corporation Optimizing virtual machine synchronization for application software
US9158592B2 (en) * 2011-05-02 2015-10-13 Green Hills Software, Inc. System and method for time variant scheduling of affinity groups comprising processor core and address spaces on a synchronized multicore processor
EP2541404B1 (en) * 2011-06-30 2014-08-13 Telefonaktiebolaget LM Ericsson (publ) Technique for task sequence execution
KR20130051076A (ko) * 2011-11-09 2013-05-20 한국전자통신연구원 응용프로그램 스케줄링 방법 및 장치
KR101901587B1 (ko) * 2011-12-13 2018-10-01 삼성전자주식회사 연성 실시간 운영체제의 실시간성을 확보하는 방법 및 장치
US9298504B1 (en) * 2012-06-11 2016-03-29 Amazon Technologies, Inc. Systems, devices, and techniques for preempting and reassigning tasks within a multiprocessor system
US9329912B2 (en) * 2012-07-13 2016-05-03 Freescale Semiconductor, Inc. Core-affine processing on symmetric multiprocessing systems
US9063796B2 (en) * 2012-08-02 2015-06-23 GM Global Technology Operations LLC Method and apparatus for improving processing performance of a multi-core processor
US9411641B2 (en) * 2012-10-04 2016-08-09 Lawrence J. Dickson Method and apparatus implemented in processors for real-time scheduling and task organization based on response time order of magnitude
US8949841B2 (en) * 2012-12-27 2015-02-03 Nvidia Corporation Approach for a configurable phase-based priority scheduler
US20140282572A1 (en) * 2013-03-14 2014-09-18 Samsung Electronics Co., Ltd. Task scheduling with precedence relationships in multicore systems
US10209904B2 (en) * 2013-04-09 2019-02-19 EMC IP Holding Company LLC Multiprocessor system with independent direct access to bulk solid state memory resources
EP3039540B1 (en) * 2013-08-26 2021-08-11 VMware, Inc. Virtual machine monitor configured to support latency sensitive virtual machines
KR101709314B1 (ko) * 2013-09-12 2017-02-23 한국전자통신연구원 태스크 우선순위 조정 장치 및 방법
US9298506B2 (en) * 2013-09-30 2016-03-29 Teradata Us, Inc. Assigning resources among multiple task groups in a database system
CN103645954B (zh) * 2013-11-21 2018-12-14 华为技术有限公司 一种基于异构多核体系的cpu调度方法、装置和系统
US9606833B2 (en) * 2014-04-09 2017-03-28 Samsung Electronics Co., Ltd Method and apparatus for providing a preemptive task scheduling scheme in a real time operating system
TWI503742B (zh) * 2014-04-21 2015-10-11 Nat Univ Tsing Hua 多核心處理器系統及其排程方法
KR102182295B1 (ko) * 2014-04-21 2020-11-24 삼성전자 주식회사 하드웨어 기반 태스크 스케쥴링 장치 및 방법
US9489242B2 (en) * 2014-09-30 2016-11-08 Telefonaktiebolaget L M Ericsson (Publ) Algorithm for faster convergence through affinity override
US9612865B2 (en) * 2015-06-15 2017-04-04 International Business Machines Corporation Managed services coordinator
TWI554945B (zh) * 2015-08-31 2016-10-21 晨星半導體股份有限公司 例行工作的分配方法及應用其之多核心電腦
US10509677B2 (en) * 2015-09-30 2019-12-17 Lenova (Singapore) Pte. Ltd. Granular quality of service for computing resources
US10452572B2 (en) * 2016-10-06 2019-10-22 Vmware, Inc. Automatic system service resource management for virtualizing low-latency workloads that are input/output intensive
US11237872B2 (en) * 2017-05-23 2022-02-01 Kla-Tencor Corporation Semiconductor inspection and metrology systems for distributing job among the CPUs or GPUs based on logical image processing boundaries

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103080903A (zh) * 2010-08-27 2013-05-01 富士通株式会社 调度器、多核处理器系统以及调度方法
CN103019810A (zh) * 2011-09-19 2013-04-03 辉达公司 具有不同执行优先级的计算任务的调度和管理
CN103218259A (zh) * 2012-01-18 2013-07-24 辉达公司 计算任务的调度和执行
CN104380257A (zh) * 2012-05-09 2015-02-25 英特尔公司 在处理器核之间调度任务

Also Published As

Publication number Publication date
CN109522101A (zh) 2019-03-26
US20190087224A1 (en) 2019-03-21
US11055129B2 (en) 2021-07-06

Similar Documents

Publication Publication Date Title
CN109522101B (zh) 用于调度多个操作系统任务的方法、系统和/或装置
KR101686010B1 (ko) 실시간 멀티코어 시스템의 동기화 스케쥴링 장치 및 방법
US8914805B2 (en) Rescheduling workload in a hybrid computing environment
US9858115B2 (en) Task scheduling method for dispatching tasks based on computing power of different processor cores in heterogeneous multi-core processor system and related non-transitory computer readable medium
CN108549574B (zh) 线程调度管理方法、装置、计算机设备和存储介质
CN104156264B (zh) 一种基于多gpu的基带信号处理任务并行实时调度方法
Davis A review of fixed priority and EDF scheduling for hard real-time uniprocessor systems
US9298504B1 (en) Systems, devices, and techniques for preempting and reassigning tasks within a multiprocessor system
US10248456B2 (en) Method and system for providing stack memory management in real-time operating systems
CN105487919A (zh) 多核心处理器系统及任务分配方法
CN110347485A (zh) 基于固定优先级的多核抢占式的多级融合实时调度方法
EP4386554A1 (en) Instruction distribution method and device for multithreaded processor, and storage medium
Pang et al. Efficient CUDA stream management for multi-DNN real-time inference on embedded GPUs
CN111597044A (zh) 任务调度方法、装置、存储介质及电子设备
KR101377195B1 (ko) 컴퓨터 마이크로 작업
CN111989651B (zh) 在多核系统中管理内核服务的方法和装置
CN118245188A (zh) 线程控制方法及装置、处理器和计算机可读存储介质
CN110347507A (zh) 基于时间片轮转的多级融合实时调度方法
US11403138B2 (en) Method and electronic device for handling relative priority based scheduling procedure
Li et al. PEP: Proactive checkpointing for efficient preemption on GPUs
CN110333950A (zh) 一种基于静态优先级的多核vcpu调度方法
Khan et al. Smart scheduler for CUDA programming in heterogeneous CPU/GPU environment
Baital et al. Energy efficient dynamic scheduling of dependent tasks for multi‐core real‐time systems using delay techniques
CN110968418A (zh) 基于信号-槽的大规模有约束并发任务的调度方法与装置
CN110955500B (zh) 大规模并发任务的调度方法与装置

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant