[go: up one dir, main page]

CN114035930A - 用于任务调度的方法及装置、电子设备、可读存储介质 - Google Patents

用于任务调度的方法及装置、电子设备、可读存储介质 Download PDF

Info

Publication number
CN114035930A
CN114035930A CN202111432359.2A CN202111432359A CN114035930A CN 114035930 A CN114035930 A CN 114035930A CN 202111432359 A CN202111432359 A CN 202111432359A CN 114035930 A CN114035930 A CN 114035930A
Authority
CN
China
Prior art keywords
task
team leader
end time
queue
team
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
Application number
CN202111432359.2A
Other languages
English (en)
Other versions
CN114035930B (zh
Inventor
周彦茂
孙晓宁
夏云霓
肖旋
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.)
Chongqing University
Original Assignee
Chongqing University
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 Chongqing University filed Critical Chongqing University
Priority to CN202111432359.2A priority Critical patent/CN114035930B/zh
Publication of CN114035930A publication Critical patent/CN114035930A/zh
Application granted granted Critical
Publication of CN114035930B publication Critical patent/CN114035930B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

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

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本申请涉及计算机技术领域，公开一种用于任务调度的方法，包括：获取若干个移动车辆发送的任务分配请求；根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务；在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；根据第一结束时间将队首任务分配到目标服务器。通过第一结束时间对任务进行调度这种方式能够使得任务调度更合理，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。本申请还公开一种用于任务调度的装置及电子设备、可读存储介质。

Description

用于任务调度的方法及装置、电子设备、可读存储介质
技术领域
本申请涉及计算机技术领域，例如涉及一种用于任务调度的方法及装置、电子设备、可读存储介质。
背景技术
随着车联网技术的不断发展，通过利用边缘计算平台的便捷、高效以及资源配置的可扩展性，为非中心化、移动、请求各异性的移动车辆提供计算、存储等服务，已经成为现今搭建诸多具有移动特性的信息服务的一种流行模式，能够更快速提供用户所需的资源，使得用户只需投入很少的管理工作，与服务供应商进行很少的交互。
在实现本公开实施例的过程中，发现相关技术中至少存在如下问题：
现有的车载边缘环境下的任务调度策略在对移动车辆中的任务进行调度时没有考虑任务需求以及任务先后顺序，导致任务常常难以在要求的截止期限内完成，用户体验较差。
发明内容
为了对披露的实施例的一些方面有基本的理解，下面给出了简单的概括。所述概括不是泛泛评述，也不是要确定关键/重要组成元素或描绘这些实施例的保护范围，而是作为后面的详细说明的序言。
本公开实施例提供了一种用于任务调度的方法及装置、电子设备、可读存储介质，以能够提高任务在要求的截止期限内完成的概率。
在一些实施例中，所述用于任务调度的方法，包括：获取若干个移动车辆发送的任务分配请求；根据所述任务分配请求获取任务队列；所述任务队列包括各所述移动车辆分别对应的若干个待分配任务；所述任务队列中的各所述待分配任务按照任务优先级从高到低进行排序；确定队首任务的任务状态；所述队首任务为所述任务队列中任务优先级最高的待分配任务；在所述队首任务的任务状态处于就绪状态的情况下，获取所述队首任务对应的第一结束时间，并确定所述队首任务对应的目标服务器；所述第一结束时间为松弛结束时间中的最小值；所述松弛结束时间为各未执行任务对应的最晚结束时间与各所述未执行任务对应的最大执行时延之间的差值，所述未执行任务为在所述队首任务后未执行的任务；根据所述第一结束时间将所述队首任务分配到所述目标服务器。
在一些实施例中，所述用于任务调度的装置包括：处理器和存储有程序指令的存储器，所述处理器被配置为在执行所述程序指令时，执行上述用于任务调度的方法。
在一些实施例中，所述电子设备包括上述的用于任务调度的装置。
在一些实施例中，所述可读存储介质存储有程序指令，所述程序指令在运行时，执行上述的用于任务调度的方法。
本公开实施例提供的用于任务调度的方法及装置、电子设备、可读存储介质，可以实现以下技术效果：通过在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；根据第一结束时间将队首任务分配到目标服务器。由于第一结束时间为松弛结束时间中的最小值；松弛结束时间为各未执行任务对应的最晚结束时间与各未执行任务对应的最大执行时延之间的差值，未执行任务为在队首任务后未执行的任务。通过考虑了任务序列中未执行任务的最晚结束时间和最大执行时延，根据第一结束时间对任务进行调度这种方式能够使得任务调度更合理，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。
以上的总体描述和下文中的描述仅是示例性和解释性的，不用于限制本申请。
附图说明
一个或多个实施例通过与之对应的附图进行示例性说明，这些示例性说明和附图并不构成对实施例的限定，附图中具有相同参考数字标号的元件示为类似的元件，附图不构成比例限制，并且其中：
图1是本公开实施例提供的一个用于任务调度的方法的示意图；
图2是本公开实施例提供的一个用于确定目标服务器的方法的示意图；
图3是本公开实施例提供的另一个用于任务调度的方法的示意图；
图4是本公开实施例提供的另一个用于任务调度的方法的示意图；
图5是本公开实施例提供的另一个用于任务调度的方法的示意图；
图6是本公开实施例提供的一个用于任务调度的装置的示意图。
具体实施方式
为了能够更加详尽地了解本公开实施例的特点与技术内容，下面结合附图对本公开实施例的实现进行详细阐述，所附附图仅供参考说明之用，并非用来限定本公开实施例。在以下的技术描述中，为方便解释起见，通过多个细节以提供对所披露实施例的充分理解。然而，在没有这些细节的情况下，一个或多个实施例仍然可以实施。在其它情况下，为简化附图，熟知的结构和装置可以简化展示。
本公开实施例的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本公开实施例的实施例。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含。
除非另有说明，术语“多个”表示两个或两个以上。
本公开实施例中，字符“/”表示前后对象是一种“或”的关系。例如，A/B表示：A或B。
术语“和/或”是一种描述对象的关联关系，表示可以存在三种关系。例如，A和/或B，表示：A或B，或，A和B这三种关系。
术语“对应”可以指的是一种关联关系或绑定关系，A与B相对应指的是A与B之间是一种关联关系或绑定关系。
结合图1所示，本公开实施例提供一种用于任务调度的方法，包括：
步骤S101，获取若干个移动车辆发送的任务分配请求。
步骤S102，根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；任务队列中的各待分配任务按照任务优先级从高到低进行排序。
步骤S103，确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务。
步骤S104，在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；第一结束时间为松弛结束时间中的最小值；松弛结束时间为各未执行任务对应的最晚结束时间与各未执行任务对应的最大执行时延之间的差值，未执行任务为在队首任务后未执行的任务。
步骤S105，根据第一结束时间将队首任务分配到目标服务器。
采用本公开实施例提供的用于任务调度的方法，通过获取若干个移动车辆发送的任务分配请求；根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务；在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；根据第一结束时间将队首任务分配到目标服务器。由于第一结束时间为松弛结束时间中的最小值；松弛结束时间为各未执行任务对应的最晚结束时间与各未执行任务对应的最大执行时延之间的差值，未执行任务为在队首任务后未执行的任务。通过考虑了任务序列中未执行任务的最晚结束时间和最大执行时延，根据第一结束时间对任务进行调度这种方式能够使得任务调度更合理，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。
可选地，任务队列中的各待分配任务的任务优先级通过以下方式获得：获取各待分配任务分别对应的第一结束时间；根据各第一结束时间获取各待分配任务分别对应的任务优先级。
可选地，任务队列中的各待分配任务之间存在依赖关系，各待分配任务之间存在依赖关系为用户输入的关系。在一些实施例中，任务1和任务2存在依赖关系，例如：在任务1执行结束后才能开始执行任务2；或，在任务1和任务2执行结束后才能开始执行任务3。任务1和任务2不存在依赖关系。例如：任务1和任务2是并列的，即任务1和任务2能够同时执行。在一些实施例中，通过待分配任务间的依赖关系对各待分配任务进行预先调度，能够有效减少任务的迁移次数。
可选地，通过以下方式获取各待分配任务分别对应的第一结束时间：通过计算
Figure BDA0003380552630000051
获得各待分配任务分别对应的第一结束时间；其中，SLFTi,m为第i个车辆中的第m个待分配任务对应的第一结束时间；Ti,n为第i个车辆中的第n个待分配任务；suc(Ti,m)为第i个车辆中的第m个待分配任务后的所有直接后续任务的集合；LFTi,n为第i个车辆中的第n个待分配任务对应的最晚结束时间；
Figure BDA0003380552630000052
为第i个车辆中的第n个待分配任务对应的最大执行时延。
可选地，通过以下方式获取第i个车辆中的第j个任务对应的最大执行时延：通过计算
Figure BDA0003380552630000053
获得第i个车辆中的第j个任务对应的最大执行时延；其中，
Figure BDA0003380552630000054
为第i个车辆中的第j个任务对应的最大执行时延；S为服务器的数量；di,j为第i个车辆中的第j个任务的任务大小；fo为服务器o的计算速度。
可选地，根据各第一结束时间获取各待分配任务分别对应的任务优先级，包括：在待分配任务的第一结束时间越早的情况下，确定该待分配任务的任务优先级越高。
可选地，确定队首任务的任务状态，包括：获取队首任务对应的就绪时间和第一当前时间；在第一当前时间大于或等于就绪时间的情况下，确定队首任务的任务状态处于就绪状态。
可选地，在确定队首任务的任务状态处于就绪状态后，还包括：将该队首任务从该任务队列中移除，并将该队首任务的任务状态调整为已分配状态。这样，通过对任务队列中的队首任务的任务状态进行分析，在队首任务的任务状态处于就绪状态的情况下，将队首任务从该任务队列中移除，这样任务队列中将会出现新的队首任务，新的队首任务为当前任务队列中任务优先级最高的待分配任务，便于服务器对任务队列中的待分配任务进行调度。
可选地，获取队首任务对应的就绪时间，包括：获取已执行任务的第二结束时间；已执行任务为在队首任务前被执行的所有任务；第二结束时间为已执行任务的真实结束时间中的最大值；将第二结束时间确定为就绪时间。
在一些实施例中，将Ti,k确定为队首任务，Ti,k为第i个车辆中的第k个任务，通过计算
Figure BDA0003380552630000061
获得队首任务对应的就绪时间；其中，RTi,k为队首任务对应的就绪时间；Ti,h为在Ti,k前的已执行任务；pre(Ti,k)为在Ti,k前的所有已执行任务的集合；RFTi,h为已执行任务Ti,h的第二结束时间。在一些实施例中，第二结束时间为真实结束时间。
可选地，获取队首任务对应的第一结束时间，包括：获取队首任务对应的最晚结束时间和队首任务对应的最大执行时延；根据最晚结束时间和最大执行时延获取队首任务对应的第一结束时间。
可选地，获取队首任务对应的最晚结束时间，包括：通过计算
Figure BDA0003380552630000062
获得队首任务对应的最晚结束时间；其中，LFTi,k为队首任务Ti,k对应的最晚结束时间；Ti,j为在队首任务Ti,k后的未执行任务；suc(Ti,k)为在队首任务Ti,k后的所有未执行任务的集合；LFTi,j为第i辆车中第j个任务的最晚结束时间；
Figure BDA0003380552630000063
为第i个车辆中的第j个任务对应的最小执行时延。
在一些实施例中，服务器有S个，通过计算
Figure BDA0003380552630000064
获得第i个车辆中的第j个任务对应的最小执行时延；其中，
Figure BDA0003380552630000065
为第i个车辆中的第j个任务对应的最小执行时延；di,j为第i个车辆中的第j个任务的任务大小；fo为服务器o的计算速度。
可选地，确定队首任务对应的目标服务器，包括：获取队首任务的任务大小；根据任务大小获取队首任务对应不同服务器的执行时延；将最短的执行时延对应的服务器确定为目标服务器。
结合图2所示，本公开实施例提供一种用于确定目标服务器的方法，包括：
步骤S201，获取队首任务的任务大小。
步骤S202，根据任务大小获取队首任务对应不同服务器的执行时延。
步骤S203，将最短的执行时延对应的服务器确定为目标服务器。
采用本公开实施例提供的用于确定目标服务器的方法，通过获取队首任务的任务大小，通过获取各队首任务在不同服务器上的执行时延，将最短的执行时延对应的服务器确定为目标服务器，能够确定出性能最好的服务器，这样能够以最快的速度完成队首任务。
可选地，根据任务大小获取队首任务对应不同服务器的执行时延，包括：根据预设算法利用任务大小进行计算，获得队首任务对应不同服务器的执行时延。
在一些实施例中，队首任务为Ti,k，服务器有S个，根据预设算法利用任务大小进行计算，获得队首任务对应不同服务器的执行时延，包括：通过计算
Figure BDA0003380552630000071
获得队首任务对应不同服务器的执行时延；其中，ETi,k,s为队首任务Ti,k在服务器s上的执行时延；di,k为队首任务Ti,k的任务大小；fs为服务器s的计算速度。通过计算获得S个执行时延，从S个执行时延中选出最短的执行时延，将最短的执行时延对应的服务器确定为目标服务器。
在一些实施例中，在对队首任务进行分配时，若队首任务对应的目标服务器正在执行其他任务，此时获取该目标服务器正在执行的其他任务对应的执行时延，将队首任务对应的最短的执行时延和该目标服务器正在执行的其他任务对应的执行时延进行求和，获得第一时延；并从S个执行时延中获取队首任务对应的第二短的执行时延，将第二短的执行时延确定为第二时延；获取第二时延与第一时延进行对比，获得对比结果；在对比结果为第二时延小于第一时延的情况下，将第二时延对应的服务器确定为队首任务对应的目标服务器；在对比结果为第二时延大于第一时延的情况下，将最短的执行时延对应的服务器确定为队首任务对应的目标服务器。
这样，通过从不同服务器中筛选出执行时延最短的服务器，将执行时延最短的服务器确定为目标服务器，能够保证待分配任务能够及时被执行，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。
可选地，在对队首任务进行分配时，若队首任务对应的目标服务器正在执行其他任务，只有在目标服务器将其他任务执行完，才开始执行队首任务。
在一些实施例中，车辆与应用程序为一对一的关系，因此，各车辆中的待分配任务为应用程序中的待分配任务，通过计算
Figure BDA0003380552630000081
获得最后期限满足率；其中，DMR为最后期限满足率；ct为应用程序Ai是否满足MakeSpani≤dli，若满足，则ct＝1；若不满足，则ct＝0；MakeSpani为应用程序Ai中所有任务均完成的时间；dli为应用程序Ai中所有任务均完成的最大截止期限；I为应用程序的总数量。
在一些实施例中，通过优化公式使得最后期限满足率处于目标范围内，包括：通过计算
Figure BDA0003380552630000082
获得最低的平均应用程序完成时间；其中，DMR为最后期限满足率；norm(Makespani)为第i个应用程序的完成时间正则化后的结果；I为应用程序的总数量。在一些实施例中，该优化公式还包括以下约束条件：RSTi,k,s≥xi,k,r*xn,j,s*dj,i*EFTn,j，Makespani≥dli；其中，RSTi,k,s为任务Ti,k在服务器s上的真实开始时间，EFTn,j为任务Tn,j的最早结束时间，
Figure BDA0003380552630000083
Figure BDA0003380552630000084
MakeSpani为应用程序Ai中所有任务均完成的时间，dli为应用程序Ai中所有任务均完成的最大截止期限。
在一些实施例中，通过计算
Figure BDA0003380552630000091
获得第i个应用程序的完成时间正则化后的结果；其中，norm(Makespani)为第i个应用程序的完成时间正则化后的结果；Makespani,j为第i个应用程序中第j个任务的完成时间；
Figure BDA0003380552630000092
为第i个应用程序的最快完成时间；
Figure BDA0003380552630000093
为第i个应用程序的最慢完成时间。这样，通过上述限定条件能够获得尽可能低的平均应用程序完成时间和尽可能高的最后期限满足率，并且每个应用程序都能在其相应的截止时间前结束，提高了任务在最大截止期限内的完成率，提高了用户体验。
可选地，确定队首任务的任务状态后，还包括：在队首任务的任务状态未处于就绪状态的情况下，将队首任务从任务队列中移除，并将队首任务添加至等待队列中；等待队列中的各任务按照任务优先级从高到低进行排序；确定任务队列中的队首任务的任务状态；在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；根据第一结束时间将队首任务分配到目标服务器；遍历任务队列，直到任务队列中的所有待分配任务调度完成。
在一些实施例中，获取若干个车辆发送的任务分配请求，并根据各任务分配请求的任务优先级从高到低对各待分配任务进行排序，获得任务序列；先确定任务序列中的队首任务，即任务队列中任务优先级最高的待分配任务的任务状态，在队首任务的任务状态处于就绪状态的情况下，将队首任务从任务队列中移除，并获取队首任务的第一结束时间，并确定队首任务对应的目标服务器；根据第一结束时间将队首任务分配到目标服务器；在队首任务的任务状态未处于就绪状态的情况下，将将队首任务从任务队列中移除，并将队首任务添加至等待队列中，此时将任务队列中任务优先级最高的待分配任务确定为新的队首任务，并确定新的队首任务的的任务状态，在新的队首任务状态处于就绪状态的情况下，获取新的队首任务对应的第一结束时间，并确定新的队首任务对应的目标服务器；根据第一结束时间将新的队首任务分配到目标服务器；遍历任务队列，直到任务队列中的所有待分配任务调度完成。
可选地，结合图3所示，本公开实施例提供一种用于任务调度的方法，包括：
步骤S301，获取若干个移动车辆发送的任务分配请求。
步骤S302，根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；任务队列中的各待分配任务按照任务优先级从高到低进行排序。
步骤S303，确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务。
步骤S304，在队首任务的任务状态未处于就绪状态的情况下，将队首任务从任务队列中移除，并将队首任务添加至等待队列中；等待队列中的各任务按照任务优先级从高到低进行排序。
步骤S305，确定任务队列中的队首任务的任务状态。
步骤S306，在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器。
步骤S307，根据第一结束时间将队首任务分配到目标服务器。
步骤S308，遍历任务队列，直到任务队列中的所有待分配任务调度完成。
采用本公开实施例提供的用于任务调度的方法，通过对队首任务的任务状态进行确定，并将队首任务从任务队列中移除，能够避免重复调度同一个任务，保证任务队列中的所有待分配任务都能够按照任务优先级被调度，使得任务调度更合理，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。
可选地，在遍历任务队列，直到任务队列中的所有待分配任务调度完成后，还包括：等待第三结束时间后，重新获取若干个车辆的任务分配请求，根据任务分配请求对车辆的任务进行调度。第三结束时间为所有车辆中任务大小最大的待分配任务的执行时延。这样，每过第三结束时间，通过服务器主动对任务进行调度，能够更合理的调度任务，使得任务能够在要求的截止期限内完成，提高用户体验。
可选地，结合图4所示，本公开实施例提供一种用于任务调度的方法，包括：
步骤S401，获取若干个移动车辆发送的任务分配请求。
步骤S402，根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；任务队列中的各待分配任务按照任务优先级从高到低进行排序。
步骤S403，确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务。
步骤S404，在队首任务的任务状态未处于就绪状态的情况下，将队首任务从任务队列中移除，并将队首任务添加至等待队列中；等待队列中的各任务按照任务优先级从高到低进行排序。
步骤S405，确定任务队列中的队首任务的任务状态。
步骤S406，在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器。
步骤S407，根据第一结束时间将队首任务分配到目标服务器。
步骤S408，遍历任务队列，直到任务队列中的所有待分配任务调度完成。
步骤S409，等待第三结束时间后，重新获取若干个车辆的任务分配请求，根据任务分配请求对车辆的任务进行调度。第三结束时间为所有车辆中任务大小最大的待分配任务的执行时延。
采用本公开实施例提供的用于任务调度的方法，通过对队首任务的任务状态进行确定，并将队首任务从任务队列中移除，能够避免重复调度同一个任务，保证任务队列中的所有待分配任务都能够按照任务优先级被调度，每过第三结束时间，通过服务器主动对任务进行调度，能够更合理的调度任务，使得任务能够在要求的截止期限内完成，提高用户体验。
可选地，根据第一结束时间将队首任务分配到目标服务器，包括：获取第二当前时间；在第二当前时间大于第一结束时间的情况下，将队首任务分配到目标服务器；或，在第二当前时间小于或等于第一结束时间的情况下，对等待队列中的各任务进行任务调度后，再将队首任务分配到目标服务器。
可选地，在第二当前时间小于或等于第一结束时间的情况下，对等待队列中的各任务进行任务调度后，再将队首任务分配到目标服务器，包括：获取等待队列中的各待分配任务的第一结束时间和任务大小；根据等待队列中的各待分配任务的任务大小确定等待队列中的各待分配任务对应的目标服务器；在第二当前时间大于等待队列中的各待分配任务的第一结束时间的情况下，将等待队列中的各待分配任务分配到与其对应的目标服务器；再将队首任务分配到与队首任务对应的目标服务器。
这样，通过获取第二当前时间，根据第二当前时间和待分配任务的第一结束时间对待分配任务进行调度，优化了任务的调度，有效增加了任务的截止期限满足率，提高了在要求的截止期限内任务的完成率。
可选地，结合图5所示，本公开实施例提供一种用于任务调度的方法，包括：
步骤S501，获取若干个移动车辆发送的任务分配请求；
步骤S502，根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；任务队列中的各待分配任务按照任务优先级从高到低进行排序；
步骤S503，确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务；
步骤S504，在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；第一结束时间为松弛结束时间中的最小值；松弛结束时间为各未执行任务对应的最晚结束时间与各未执行任务对应的最大执行时延之间的差值，未执行任务为在队首任务后未执行的任务；
步骤S505，获取第二当前时间，并将第二当前时间与第一结束时间进行对比，在第二当前时间大于第一结束时间的情况下，执行步骤S506；或，在第二当前时间小于或等于第一结束时间的情况下，执行步骤S507。
步骤S506，将队首任务分配到目标服务器。
步骤S507，对等待队列中的各任务进行任务调度后，再将队首任务分配到目标服务器。
采用本公开实施例提供的用于任务调度的方法，通过获取队首任务的第一结束时间和第二当前时间，根据第一结束时间和第二当前时间对队首任务进行分配，由于考虑了任务序列中未执行任务的最晚结束时间和最大执行时延，根据第一结束时间对任务进行调度这种方式能够使得任务调度更合理，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。
在一些实施例中，服务器包括本地层中的服务器、VEC(Vehicular EgdeComputer，车载边缘计算)层中的服务器和中心云端层中的服务器。VEC层中的服务器为RSU(Road Side Unit，路侧单元)包括的若干个边缘服务器。通过RSU的覆盖半径和RSU与道路的距离能够确定RSU将道路分成相应的若干段，若干段道路分别具有不同的长度。移动车辆中的任务有S+2个，RSU中的边缘服务器有S个，通过将第1个任务调度到本地层中的服务器执行，S+1个任务在RSU中的边缘服务器执行，第S+2个任务在中心云端层执行，通过将任务调度到不同的服务器上执行，能够避免传统的移动环境云系统的任务调度仅依靠中心云端层的资源，从而能够对一些实时性任务进行及时处理，使得任务调度更合理，能够提高任务在要求的截止期限内完成的概率，提高用户体验。
可选地，获取各车辆分别对应的上传时延，包括：确定各车辆的待分配任务对应的服务器；将服务器对应的上传时延确定为各车辆分别对应的上传时延。
在一些实施例中，在待分配任务对应的服务器为VEC层中的边缘服务器的情况下，通过计算
Figure BDA0003380552630000131
获得边缘服务器对应的上传时延；其中，
Figure BDA0003380552630000132
为边缘服务器对应的上传时延；di,k为第i个车辆对应的第k个任务的任务大小；
Figure BDA0003380552630000133
为边缘服务器对应的传输速率。可选地，通过香农定理计算
Figure BDA0003380552630000134
获得边缘服务器对应的传输速率；其中，
Figure BDA0003380552630000141
为边缘服务器对应的传输速率；BV2E为车辆和边缘服务器之间的带宽；N0为噪声功率；Pi为第i个车辆的传输功率；
Figure BDA0003380552630000142
为第i个车辆与边缘服务器j之间的信道增益。
在一些实施例中，在待分配任务对应的服务器为集中式云的服务器的情况下，通过计算通过计算
Figure BDA0003380552630000143
获得边缘服务器对应的上传时延；其中，
Figure BDA0003380552630000144
为集中式云的服务器对应的上传时延；di,k为第i个车辆对应的第k个任务的任务大小；
Figure BDA0003380552630000145
为集中式云的服务器对应的传输速率。可选地，通过计算
Figure BDA0003380552630000146
获得边缘服务器对应的传输速率；其中，
Figure BDA0003380552630000147
为集中式云的服务器对应的传输速率；BV2C为车辆和集中式云的服务器之间的带宽；N0为噪声功率；Pi为第i个车辆的传输功率；
Figure BDA0003380552630000148
为第i个车辆与边缘服务器j之间的信道增益。
这样，通过将任务调度到不同的服务器上运行，能够达到移动车辆对所执行的任务总体容错率的要求，将一个任务的多个冗余副本放置于不同的边缘服务器上，副本数量越多则任务最终的成功率越高，在计算各个移动车辆所需的任务副本数量时，由于无法预知任务副本放置的服务器，通过用平均任务成功执行率作为计算的参考因素。
结合图6所示，本公开实施例提供一种用于任务调度的装置，包括处理器(processor)600和存储器(memory)601。可选地，该装置还可以包括通信接口(Communication Interface)602和总线603。其中，处理器600、通信接口602、存储器601可以通过总线603完成相互间的通信。通信接口602可以用于信息传输。处理器600可以调用存储器601中的逻辑指令，以执行上述实施例的用于任务调度的方法。
采用本公开实施例提供的用于任务调度的装置，通过获取若干个移动车辆发送的任务分配请求；根据任务分配请求获取任务队列；任务队列包括各移动车辆分别对应的若干个待分配任务；确定队首任务的任务状态；队首任务为任务队列中任务优先级最高的待分配任务；在队首任务的任务状态处于就绪状态的情况下，获取队首任务对应的第一结束时间，并确定队首任务对应的目标服务器；根据第一结束时间将队首任务分配到目标服务器。由于第一结束时间为松弛结束时间中的最小值；松弛结束时间为各未执行任务对应的最晚结束时间与各未执行任务对应的最大执行时延之间的差值，未执行任务为在队首任务后未执行的任务。通过考虑了任务序列中未执行任务的最晚结束时间和最大执行时延，根据第一结束时间对任务进行调度这种方式能够使得任务调度更合理，从而能够提高任务在要求的截止期限内完成的概率，提高用户体验。
本公开实施例提供一种电子设备，包括上述的用于任务调度的装置。
可选地，电子设备包括服务器等。
此外，上述的存储器601中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取可读存储介质中。
存储器601作为一种计算机可读可读存储介质，可用于存储软件程序、计算机可执行程序，如本公开实施例中的方法对应的程序指令/模块。处理器600通过运行存储在存储器601中的程序指令/模块，从而执行功能应用以及数据处理，即实现上述实施例中用于任务调度的方法。
存储器601可包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序；存储数据区可存储根据终端设备的使用所创建的数据等。此外，存储器601可以包括高速随机存取存储器，还可以包括非易失性存储器。
本公开实施例提供了一种可读存储介质，存储有程序指令，程序指令在运行时，执行上述用于任务调度的方法。
本公开实施例提供了一种计算机程序产品，所述计算机程序产品包括存储在计算机可读可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行上述用于任务调度的方法。
上述的计算机可读可读存储介质可以是暂态计算机可读可读存储介质，也可以是非暂态计算机可读可读存储介质。
本公开实施例的技术方案可以以软件产品的形式体现出来，该计算机软件产品存储在一个可读存储介质中，包括一个或多个指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本公开实施例所述方法的全部或部分步骤。而前述的可读存储介质可以是非暂态可读存储介质，包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等多种可以存储程序代码的介质，也可以是暂态可读存储介质。
以上描述和附图充分地示出了本公开的实施例，以使本领域的技术人员能够实践它们。其他实施例可以包括结构的、逻辑的、电气的、过程的以及其他的改变。实施例仅代表可能的变化。除非明确要求，否则单独的部件和功能是可选的，并且操作的顺序可以变化。一些实施例的部分和特征可以被包括在或替换其他实施例的部分和特征。而且，本申请中使用的用词仅用于描述实施例并且不用于限制权利要求。如在实施例以及权利要求的描述中使用的，除非上下文清楚地表明，否则单数形式的“一个”(a)、“一个”(an)和“所述”(the)旨在同样包括复数形式。类似地，如在本申请中所使用的术语“和/或”是指包含一个或一个以上相关联的列出的任何以及所有可能的组合。另外，当用于本申请中时，术语“包括”(comprise)及其变型“包括”(comprises)和/或包括(comprising)等指陈述的特征、整体、步骤、操作、元素，和/或组件的存在，但不排除一个或一个以上其它特征、整体、步骤、操作、元素、组件和/或这些的分组的存在或添加。在没有更多限制的情况下，由语句“包括一个…”限定的要素，并不排除在包括所述要素的过程、方法或者设备中还存在另外的相同要素。本文中，每个实施例重点说明的可以是与其他实施例的不同之处，各个实施例之间相同相似部分可以互相参见。对于实施例公开的方法、产品等而言，如果其与实施例公开的方法部分相对应，那么相关之处可以参见方法部分的描述。
本领域技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，可以取决于技术方案的特定应用和设计约束条件。所述技术人员可以对每个特定的应用来使用不同方法以实现所描述的功能，但是这种实现不应认为超出本公开实施例的范围。所述技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统、装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。
本文所披露的实施例中，所揭露的方法、产品(包括但不限于装置、设备等)，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，可以仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另外，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例。另外，在本公开实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。
附图中的流程图和框图显示了根据本公开实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这可以依所涉及的功能而定。在附图中的流程图和框图所对应的描述中，不同的方框所对应的操作或步骤也可以以不同于描述中所披露的顺序发生，有时不同的操作或步骤之间不存在特定的顺序。例如，两个连续的操作或步骤实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这可以依所涉及的功能而定。框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

Claims (10)

1.一种用于任务调度的方法，其特征在于，包括：
获取若干个移动车辆发送的任务分配请求；
根据所述任务分配请求获取任务队列；所述任务队列包括各所述移动车辆分别对应的若干个待分配任务；所述任务队列中的各所述待分配任务按照任务优先级从高到低进行排序；
确定队首任务的任务状态；所述队首任务为所述任务队列中任务优先级最高的待分配任务；
在所述队首任务的任务状态处于就绪状态的情况下，获取所述队首任务对应的第一结束时间，并确定所述队首任务对应的目标服务器；所述第一结束时间为松弛结束时间中的最小值；所述松弛结束时间为各未执行任务对应的最晚结束时间与各所述未执行任务对应的最大执行时延之间的差值，所述未执行任务为在所述队首任务后未执行的任务；
根据所述第一结束时间将所述队首任务分配到所述目标服务器。
2.根据权利要求1所述的方法，其特征在于，所述确定队首任务的任务状态，包括：
获取所述队首任务对应的就绪时间和第一当前时间；
在所述第一当前时间大于或等于所述就绪时间的情况下，确定所述队首任务的任务状态处于就绪状态。
3.根据权利要求2所述的方法，其特征在于，获取所述队首任务对应的就绪时间，包括：
获取已执行任务的第二结束时间；所述已执行任务为在所述队首任务前被执行的所有任务；所述第二结束时间为所述已执行任务的真实结束时间中的最大值；
将所述第二结束时间确定为就绪时间。
4.根据权利要求1所述的方法，其特征在于，获取所述队首任务对应的第一结束时间，包括：
获取所述队首任务对应的最晚结束时间和所述队首任务对应的最大执行时延；
根据所述最晚结束时间和所述最大执行时延获取所述队首任务对应的第一结束时间。
5.根据权利要求1所述的方法，其特征在于，确定所述队首任务对应的目标服务器，包括：
获取所述队首任务的任务大小；
根据所述任务大小获取所述队首任务对应不同服务器的执行时延；
将最短的执行时延对应的服务器确定为目标服务器。
6.根据权利要求1所述的方法，其特征在于，所述确定队首任务的任务状态后，还包括：
在所述队首任务的任务状态未处于就绪状态的情况下，将所述队首任务从所述任务队列中移除，并将所述队首任务添加至等待队列中；所述等待队列中的各任务按照所述任务优先级从高到低进行排序；
确定所述任务队列中的队首任务的任务状态；
在所述队首任务的任务状态处于就绪状态的情况下，获取所述队首任务对应的第一结束时间，并确定所述队首任务对应的目标服务器；
根据所述第一结束时间将所述队首任务分配到所述目标服务器；
遍历所述任务队列，直到所述任务队列中的所有待分配任务调度完成。
7.根据权利要求6所述的方法，其特征在于，根据所述第一结束时间将所述队首任务分配到所述目标服务器，包括：
获取第二当前时间；
在所述第二当前时间大于所述第一结束时间的情况下，将所述队首任务分配到所述目标服务器；或，
在所述第二当前时间小于或等于所述第一结束时间的情况下，对所述等待队列中的各任务进行任务调度后，再将所述队首任务分配到所述目标服务器。
8.一种用于任务调度的装置，包括处理器和存储有程序指令的存储器，其特征在于，所述处理器被配置为在运行所述程序指令时，执行如权利要求1至7任一项所述的用于任务调度的方法。
9.一种电子设备，其特征在于，包括如权利要求8所述的用于任务调度的装置。
10.一种可读存储介质，存储有程序指令，其特征在于，所述程序指令在运行时，执行如权利要求1至7任一项所述的用于任务调度的方法。
CN202111432359.2A 2021-11-29 2021-11-29 用于任务调度的方法及装置、电子设备、可读存储介质 Active CN114035930B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202111432359.2A CN114035930B (zh) 2021-11-29 2021-11-29 用于任务调度的方法及装置、电子设备、可读存储介质

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202111432359.2A CN114035930B (zh) 2021-11-29 2021-11-29 用于任务调度的方法及装置、电子设备、可读存储介质

Publications (2)

Publication Number Publication Date
CN114035930A true CN114035930A (zh) 2022-02-11
CN114035930B CN114035930B (zh) 2024-05-10

Family

ID=80139135

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202111432359.2A Active CN114035930B (zh) 2021-11-29 2021-11-29 用于任务调度的方法及装置、电子设备、可读存储介质

Country Status (1)

Country Link
CN (1) CN114035930B (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2024012280A1 (zh) * 2022-07-11 2024-01-18 上海寒武纪信息科技有限公司 用于任务调度的方法、设备、板卡及其计算机可读存储介质

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108536527A (zh) * 2018-02-08 2018-09-14 山东省科学院自动化研究所 一种嵌入式软件的任务调度方法及装置
CN109327406A (zh) * 2018-11-30 2019-02-12 上海海事大学 一种用于差分队列服务队列数据包的服务质量保障的方法
CN109558292A (zh) * 2017-09-26 2019-04-02 阿里巴巴集团控股有限公司 一种监控方法及装置
CN110837410A (zh) * 2019-10-30 2020-02-25 北京奇艺世纪科技有限公司 任务调度方法、装置、电子设备及计算机可读存储介质
CN111444012A (zh) * 2020-03-03 2020-07-24 中国科学院计算技术研究所 一种保证延迟敏感应用延迟slo的动态调控资源方法及系统
CN111858013A (zh) * 2020-06-19 2020-10-30 中科院计算所西部高等技术研究院 工作流作业调度控制方法
CN111930488A (zh) * 2020-09-11 2020-11-13 北京国科环宇科技股份有限公司 一种操作系统任务调度的优先级继承方法及系统
CN112822268A (zh) * 2021-01-06 2021-05-18 大连理工大学 一种工业物联网中面向多服务共存以及确定性网络需求的ip层数据包调度算法

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109558292A (zh) * 2017-09-26 2019-04-02 阿里巴巴集团控股有限公司 一种监控方法及装置
CN108536527A (zh) * 2018-02-08 2018-09-14 山东省科学院自动化研究所 一种嵌入式软件的任务调度方法及装置
CN109327406A (zh) * 2018-11-30 2019-02-12 上海海事大学 一种用于差分队列服务队列数据包的服务质量保障的方法
CN110837410A (zh) * 2019-10-30 2020-02-25 北京奇艺世纪科技有限公司 任务调度方法、装置、电子设备及计算机可读存储介质
CN111444012A (zh) * 2020-03-03 2020-07-24 中国科学院计算技术研究所 一种保证延迟敏感应用延迟slo的动态调控资源方法及系统
CN111858013A (zh) * 2020-06-19 2020-10-30 中科院计算所西部高等技术研究院 工作流作业调度控制方法
CN111930488A (zh) * 2020-09-11 2020-11-13 北京国科环宇科技股份有限公司 一种操作系统任务调度的优先级继承方法及系统
CN112822268A (zh) * 2021-01-06 2021-05-18 大连理工大学 一种工业物联网中面向多服务共存以及确定性网络需求的ip层数据包调度算法

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
MAINAK ADHIKARI: ""DPTO : A Deadline and Priority-Aware Task Offloading in Fog Computing Framework Leveraging Multilevel Feedback Queueing"", 《IEEE INTERNET OF THINGS JOURNAL》, vol. 7, no. 7, 31 July 2020 (2020-07-31), pages 5773 - 5782, XP011798178, DOI: 10.1109/JIOT.2019.2946426 *
YANMAO ZHOU: ""A Novel Approach to Applications Deployment with Multiple Interdenpendent Tasks in a Hybrid Three-Layer Vehicular Computing Environment"", 《2021 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC)》, 6 January 2022 (2022-01-06), pages 251 - 256 *
周凯: ""高性能计算中作业调度技术与集群管理系统的研究"", 《中国优秀硕士学位论文全文数据库 工程科技II辑》, no. 2016, 15 March 2016 (2016-03-15), pages 028 - 101 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2024012280A1 (zh) * 2022-07-11 2024-01-18 上海寒武纪信息科技有限公司 用于任务调度的方法、设备、板卡及其计算机可读存储介质

Also Published As

Publication number Publication date
CN114035930B (zh) 2024-05-10

Similar Documents

Publication Publication Date Title
CN114138486B (zh) 面向云边异构环境的容器化微服务编排方法、系统及介质
CN109428912B (zh) 一种分布式系统资源分配方法、装置及系统
CN111381950B (zh) 一种面向边缘计算环境基于多副本的任务调度方法和系统
CN110308984B (zh) 一种用于处理地理分布式数据的跨集群计算系统
US20050081208A1 (en) Framework for pluggable schedulers
WO2024021489A1 (zh) 一种任务调度方法、装置及Kubernetes调度器
KR101471749B1 (ko) 클라우드 서비스의 가상자원 할당을 위한 퍼지 로직 기반의 자원평가 장치 및 방법
CN107659433A (zh) 一种云资源调度方法及设备
JP4912927B2 (ja) タスク割当装置、及びタスク割当方法
WO2018126771A1 (zh) 一种存储控制器及io请求处理方法
CN111209091A (zh) 混合云环境下含隐私数据的Spark任务的调度方法
CN116483546B (zh) 分布式训练任务调度方法、装置、设备及存储介质
Qureshi et al. Grid resource allocation for real-time data-intensive tasks
CN106201681B (zh) Hadoop平台下基于预释放资源列表的任务调度方法
CN115361349B (zh) 资源使用方法和装置
CN110048966B (zh) 基于截止时间的最小化系统开销的Coflow调度方法
CN105740249B (zh) 一种大数据作业并行调度过程中的处理方法及其系统
CN114035930A (zh) 用于任务调度的方法及装置、电子设备、可读存储介质
US20170344266A1 (en) Methods for dynamic resource reservation based on classified i/o requests and devices thereof
CN111930485B (zh) 一种基于性能表现的作业调度方法
CN114091807B (zh) 多无人机任务分配及调度方法、装置、系统及存储介质
JP6773229B2 (ja) ストレージコントローラおよびｉｏリクエスト処理方法
CN115756874A (zh) 多机房作业调度方法、装置、介质及电子设备
JP6540107B2 (ja) 並列演算装置、並列演算システム、およびジョブ制御プログラム
JP6191361B2 (ja) 情報処理システム、情報処理システムの制御方法及び制御プログラム

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