[go: up one dir, main page]

CN109240813B - 一种移动云计算中的任务调度与任务迁移方法 - Google Patents

一种移动云计算中的任务调度与任务迁移方法 Download PDF

Info

Publication number
CN109240813B
CN109240813B CN201810955573.8A CN201810955573A CN109240813B CN 109240813 B CN109240813 B CN 109240813B CN 201810955573 A CN201810955573 A CN 201810955573A CN 109240813 B CN109240813 B CN 109240813B
Authority
CN
China
Prior art keywords
task
task node
state
priority
num
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.)
Expired - Fee Related
Application number
CN201810955573.8A
Other languages
English (en)
Other versions
CN109240813A (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.)
Guangdong University of Technology
Original Assignee
Guangdong University of Technology
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 Guangdong University of Technology filed Critical Guangdong University of Technology
Priority to CN201810955573.8A priority Critical patent/CN109240813B/zh
Publication of CN109240813A publication Critical patent/CN109240813A/zh
Application granted granted Critical
Publication of CN109240813B publication Critical patent/CN109240813B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; 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 OR CALCULATING; 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/485—Task life-cycle, e.g. stopping, restarting, resuming execution
    • G06F9/4856—Task life-cycle, e.g. stopping, restarting, resuming execution resumption being on a different machine, e.g. task migration, virtual machine migration
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; 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/5083—Techniques for rebalancing the load in a distributed system
    • G06F9/5088—Techniques for rebalancing the load in a distributed system involving task migration
    • 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)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

本发明公开了一种移动云计算中的任务调度与任务迁移方法，其步骤包括：将所有任务节点在移动端执行、记录当前移动端上的能耗、计算每一个可迁移任务迁移到云端后移动端节省的能耗并且通过最大优先权调度算法计算任务总完成时间finish_time、选出节省能耗最多且满足时间约束的任务，将该任务迁移至云端，若无符合条件的任务节点，则终止方法过程、重复上述步骤直至所有任务全部完成。

Description

一种移动云计算中的任务调度与任务迁移方法
技术领域
本发明涉及移动云计算领域，更具体地，涉及一种移动云计算中的任务调度与任务迁移方法。
背景技术
随着互联网和通讯技术的发展，移动应用程序对移动设备的计算、存储和电量资源的需求越来越大。然而，由于体积的限制，移动设备的资源往往不能满足移动应用的高需求。然而，云计算的发展，使得移动设备上的部分任务可迁移到云端执行。虽然移动设备上的任务可迁移到云端，但是也带来了通信能耗和通信时延。现有的解决方案大部分是针对任务迁移，或者任务调度中一种情况。针对移动云计算中的联合迁移与调度的问题，是值得进一步研究的课题。
发明内容
针对移动云计算中的联合调度与迁移问题，现有的解决方法是通过优化器进行运算，虽然精度有很大的提升，但是运行消耗的时间和运行消耗的资源代价太大。本发明提出一种移动云计算中的任务调度与任务迁移方法，所述方法以全部任务在移动端执行作为初始解，逐次计算可迁移任务在云端运行的能耗节省量，依次将节省量最大的任务迁移到云端，根据任务间的通信时间，更新各个任务的能耗节省量。
本发明的目的是指在如下约束条件下：在规定完成总任务的时间范围内，迁移到云服务器上的任务可以与移动端上的任务并行执行，也可以和云服务器上的其他任务并行执行。移动端的多个任务只能串行执行。当两个任务节点分处不同端时，他们之间才存在通信时间和通信能耗，否则通信时间和通信能耗均为0。解决的问题是：在上述约束条件下，找到一个迁移策略，完成任务后，使得在移动端的能耗最小。
一种移动云计算中的任务调度与任务迁移方法，其步骤包括：
S1：将所有任务节点在移动端执行；
S2：记录当前移动端上的能耗；
S3：计算每一个可迁移任务迁移到云端后移动端节省的能耗并且通过最大优先权调度算法计算任务总完成时间finish_time；
S4：选出节省能耗最多且满足时间约束的任务，将该任务迁移至云端，若无符合条件的任务节点，则终止方法过程；
S5：重复上述步骤S1、S2、S3、S4。
进一步地，步骤S3中所述一种最大优先权调度算法，步骤包括：
S3.1：首先定义任务节点的优先权，按广度优先遍历的顺序给每个任务节点标记序号；
S3.2：定义任务节点有五种状态，用State(i)表示任务节点i当前所处的状态；
S3.3初始化任务总完成时间finish_time；
S3.4执行云端上的所有就绪任务和移动端上的拥有最大优先权的就绪任务；
S3.5当有一个任务节点完成时，更新各个任务的状态，更新任务的总完成时间；
S3.6当所有任务完成时，计算并返回任务的总完成时间finish_time。
进一步地，步骤S3.1中所述定义任务节点的优先权，按广度优先遍历的顺序给每个任务节点标记序号，具体包括以下步骤：
如果i的序号在j的序号前面，记为i＜j；任务节点的孩子数目记为Child_num(i)，以及任务节点j的孩子数目记为Child_num(j)；任务节点i的优先权记为prior(i)，任务节点j的优先权记为prior(j)；任务节点的优先权定义；
(1)当Child_num(i)>Child_num(j)，则prior(i)>prior(j)；
(2)当Child_num(i)＝Child_num(j)且i>j，则prior(i)<prior(j)；
(3)如果Child_num(i)＝Child_num(j)且i<j，则prior(i)>prior(j)。
进一步地，步骤S3.2中所述定义任务节点有五种状态，具体定义如下：non-active表示未激活状态、active表示激活状态、ready表示就绪、runnable表示可运行、finished表示已完成；
如果任务节点i的所有父节点执行完后，则State(i)＝active；
如果云端上任务节点i的所有父节点执行完后，则State(i)＝runnable；
如果就绪集合中任务节点i的所有父节点执行完后，且拥有最高优先权，则State(i)＝runnable；
如果就绪集合中任务节点i的所有父节点执行完后，优先权不为最高，则State(i)＝ready；
如果任务节点i的所有父节点没有全部执行完，则State(i)＝non-active；
如果任务节点i已经被执行完，则State(i)＝finished。
与现有技术相比，本发明技术方案的有益效果是：
本发明算法的运行时间远小于传统优化器的运行时间，消耗资源大大降低，同时保持较好的精确度。
附图说明
图1为本发明的流程图。
图2为移动设备上一个具有15个子任务的任务图。
具体实施方式
下面结合附图和实施例对本发明的技术方案做进一步的说明。
实施例
移动云计算中的任务调度与任务迁移方法，调度算法的思想为：在给定任务迁移情况下，云端上处于就绪状态的任务可与其他任务并行执行，移动端上处于就绪状态的且拥有最高优先权的任务先执行。每完成一个任务时，更新任务的完成状态，找出目前处于就绪状态的任务。不断的重复上述过程，最终找出在时间限制下的任务调度方案，并计算任务的总完成时间。迁移过程的启发式算法思想：每次从云端迁移一个任务到云端，都要确保在迁移后，移动端的总能耗要比之前要小，以及迁移后的总完成时间要满足时间约束。通过遍历任务图上的所有节点，重复上述过程，得出最终的迁移，调度方案。
该算法分为两部分，第一部分主要是调度算法，用来提供计算总任务完成后的一种近似方法，第二部分迁移方法，其中算法需要调用前面的调度算法。
具体步骤包括：如图2所示，移动移动设备上一个具有15个子任务的任务图。实心节点表示该任务只能在移动端上执行。除实心节点外,均可迁移到云端执行。空心节点表示该任务在云端完成；阴影节点表示该任务在移动端上完成。对于有通讯的两个任务，若同在移动端或同在云端实现，那么这两个任务间的通信时间和通信能耗忽略不计；若有通信的两个任务在不同端实现，则计算任务间的通信时间和通信能耗。
参见图1，一种移动云计算中的任务调度与任务迁移方法，其步骤包括：
S1：将所有任务节点在移动端执行；
S2：记录当前移动端上的能耗；
S3：计算每一个可迁移任务迁移到云端后移动端节省的能耗并且通过最大优先权调度算法计算任务总完成时间finish_time。
其中，最大优先权调度算法计算任务总完成时间步骤包括：
1.首先定义任务结点的优先权，按广度优先遍历的顺序给每个任务节点标上序号。如果i的序号在j的序号前面，记为i<j。其次，任务节点i的孩子数目记为Child_num(i)，以及任务节点j的孩子数目记为Child_num(j)。接着，任务节点i的优先权记为prior(i)，同理，任务节点j的优先权记为prior(j)。
对任务节点优先权大小定义如下：
a.如果Child_num(i)>Child_num(j)，则prior(i)>prior(j)；
b.如果Child_num(i)＝Child_num(j)且i>j，则prior(i)<prior(j)；
c.如果Child_num(i)＝Child_num(j)且i<j，则prior(i)>prior(j)。
2.给出任务结点所处的几种状态：非激活(non-active)、激活(active)、就绪(ready)、可运行(runnable)、已完成(finished)。我们用State(i)表示任务节点i当前所处的状态：
a.如果任务节点i的所有父节点执行完后，则State(i)＝active；
b.如果云端上任务节点i的所有父节点执行完后，则State(i)＝runnable；
c.如果就绪集合中任务节点i的所有父节点执行完后，且拥有最高优先权，则State(i)＝runnable；
d.如果就绪集合中任务节点i的所有父节点执行完后，优先权不为最高，则State(i)＝read；
e.如果任务节点i的所有父节点没有全部执行完，则State(i)＝non-acti；
f.如果任务节点i已经被执行完，则State(i)＝finished。
3.初始化任务总完成时间finish_time。
4.执行云端上的所有就绪任务和移动端上的拥有最大优先权的就绪任务。
5.当有一个任务节点完成时，更新各个任务的状态，更新任务的总完成时间。
6.当所有任务完成时，计算并返回任务的总完成时间finish_time。
S4：选出节省能耗最多且满足时间约束的任务，将该任务迁移至云端，若无符合条件的任务节点，则终止方法过程。
S5：重复上述步骤S1、S2、S3、S4，直至所有任务全部完成。

Claims (2)

1.一种移动云计算中的任务调度与任务迁移方法，其特征在于，其步骤包括：
S1：将所有任务节点在移动端执行；
S2：记录当前移动端上的能耗；
S3：计算每一个可迁移任务迁移到云端后移动端节省的能耗并且通过最大优先权调度算法计算任务总完成时间finish_time，步骤S3中所述最大优先权调度算法，步骤包括：
S3.1：首先定义任务节点的优先权，按广度优先遍历的顺序给每个任务节点标记序号；
S3.2：定义任务节点有五种状态，用State(i)表示任务节点i当前所处的状态；
S3.3初始化任务总完成时间finish_time；
S3.4执行云端上的所有就绪任务和移动端上的拥有最大优先权的就绪任务；
S3.5当有一个任务节点完成时，更新各个任务的状态，更新任务的总完成时间；
S3.6当所有任务完成时，计算并返回任务的总完成时间finish_time；
步骤S3.2中所述定义任务节点有五种状态，具体定义如下：non-active表示未激活状态、active表示激活状态、ready表示就绪、runnable表示可运行、finished表示已完成；
如果任务节点i的所有父节点执行完后，则State(i)＝active；
如果云端上任务节点i的所有父节点执行完后，则State(i)＝runnable；
如果就绪集合中任务节点i的所有父节点执行完后，且拥有最高优先权，则State(i)＝runnable；
如果就绪集合中任务节点i的所有父节点执行完后，优先权不为最高，则State(i)＝ready；
如果任务节点i的所有父节点没有全部执行完，则State(i)＝non-active；
如果任务节点i已经被执行完，则State(i)＝finished；
S4：选出节省能耗最多且满足时间约束的任务，将该任务迁移至云端，若无符合条件的任务节点，则终止方法过程；
S5：重复上述步骤S1、S2、S3、S4。
2.根据权利要求1 所述的一种移动云计算中的任务调度与任务迁移方法，其特征在于，步骤S3.1中所述定义任务节点的优先权，按广度优先遍历的顺序给每个任务节点标记序号，具体包括以下步骤：
如果i的序号在j的序号前面，记为i＜j；任务节点的孩子数目记为Child_num(i)，以及任务节点j的孩子数目记为Child_num(j)；任务节点i的优先权记为prior(i)，任务节点j的优先权记为prior(j)；任务节点的优先权定义；
(1)当Child_num(i)>Child_num(j)，则prior(i)>prior(j)；
(2)当Child_num(i)＝Child_num(j)且i>j，则prior(i)<prior(j)；
(3)如果Child_num(i)＝Child_num(j)且i<j，则prior(i)>prior(j)。
CN201810955573.8A 2018-08-21 2018-08-21 一种移动云计算中的任务调度与任务迁移方法 Expired - Fee Related CN109240813B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810955573.8A CN109240813B (zh) 2018-08-21 2018-08-21 一种移动云计算中的任务调度与任务迁移方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810955573.8A CN109240813B (zh) 2018-08-21 2018-08-21 一种移动云计算中的任务调度与任务迁移方法

Publications (2)

Publication Number Publication Date
CN109240813A CN109240813A (zh) 2019-01-18
CN109240813B true CN109240813B (zh) 2021-12-24

Family

ID=65070123

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810955573.8A Expired - Fee Related CN109240813B (zh) 2018-08-21 2018-08-21 一种移动云计算中的任务调度与任务迁移方法

Country Status (1)

Country Link
CN (1) CN109240813B (zh)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111402353B (zh) * 2020-03-11 2020-12-25 浙江大学 一种基于自适应虚拟化绘制流水线的云-端绘制计算方法
CN116028197A (zh) * 2021-10-25 2023-04-28 中国科学院沈阳自动化研究所 一种基于路径约束的边端协同任务迁移优化方法
CN114281426B (zh) * 2021-12-21 2023-05-16 中国联合网络通信集团有限公司 任务卸载方法、装置、电子设备及可读存储介质
CN114625516A (zh) * 2022-04-07 2022-06-14 工业互联网创新中心（上海）有限公司 任务调度方法、中央控制器、本地控制器及系统

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102467532A (zh) * 2010-11-12 2012-05-23 中国移动通信集团山东有限公司 一种任务处理方法以及任务处理装置
CN103293967A (zh) * 2012-02-29 2013-09-11 陕西省地方电力（集团）有限公司 一种用于智能抄表终端的多任务控制方法
WO2016045515A1 (zh) * 2014-09-23 2016-03-31 同济大学 基于用户满意度的云任务调度算法
CN107360235A (zh) * 2017-07-17 2017-11-17 广东工业大学 一种基于可靠性分级的任务迁移方法
CN107436811A (zh) * 2017-07-07 2017-12-05 广东工业大学 移动云问题中涉及任务调度的任务迁移方法
CN107562527A (zh) * 2017-08-28 2018-01-09 北京翼辉信息技术有限公司 一种rtos上的smp的实时任务调度算法

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102467532A (zh) * 2010-11-12 2012-05-23 中国移动通信集团山东有限公司 一种任务处理方法以及任务处理装置
CN103293967A (zh) * 2012-02-29 2013-09-11 陕西省地方电力（集团）有限公司 一种用于智能抄表终端的多任务控制方法
WO2016045515A1 (zh) * 2014-09-23 2016-03-31 同济大学 基于用户满意度的云任务调度算法
CN107436811A (zh) * 2017-07-07 2017-12-05 广东工业大学 移动云问题中涉及任务调度的任务迁移方法
CN107360235A (zh) * 2017-07-17 2017-11-17 广东工业大学 一种基于可靠性分级的任务迁移方法
CN107562527A (zh) * 2017-08-28 2018-01-09 北京翼辉信息技术有限公司 一种rtos上的smp的实时任务调度算法

Also Published As

Publication number Publication date
CN109240813A (zh) 2019-01-18

Similar Documents

Publication Publication Date Title
CN109240813B (zh) 一种移动云计算中的任务调度与任务迁移方法
US20250077308A1 (en) Distributed computing method, system and device, and storage medium
CN105652833B (zh) 基于双向智能搜索的制造企业车间调度优化方法
CN113867843B (zh) 一种基于深度强化学习的移动边缘计算任务卸载方法
CN115883550B (zh) 任务处理方法、装置、电子设备、存储介质及程序产品
CN104391970B (zh) 一种属性子空间加权的随机森林数据处理方法
CN113887748A (zh) 在线联邦学习任务分配方法、装置、联邦学习方法及系统
WO2021227418A1 (zh) 基于多板fpga异构系统的任务部署方法及设备
CN105760549B (zh) 基于属性图模型的近邻查询方法
CN111190711B (zh) Bdd结合启发式a*搜索的多机器人任务分配方法
CN115688893A (zh) 内存调度方法及装置、电子设备和存储介质
CN106033442A (zh) 一种基于共享内存体系结构的并行广度优先搜索方法
CN106650028A (zh) 一种基于敏捷卫星设计参数的优化方法及系统
CN111931939A (zh) 一种单振幅量子计算模拟方法
CN106201706A (zh) 一种粒子群服务选择方法和系统
CN104866375A (zh) 一种迁移虚拟机的方法及装置
CN103885856A (zh) 一种基于消息再生机制的图计算容错方法及系统
CN110110157A (zh) 一种基于二跳图的超图迭代方法及其应用
CN120578481A (zh) 一种强化学习与启发式驱动的边缘计算依赖任务调度方法
CN112100877B (zh) 一种结构刚度高效拓扑优化方法及系统
CN110362378A (zh) 一种任务调度方法及设备
CN108965016B (zh) 一种虚拟网络的映射方法及装置
CN107885549B (zh) 清除torque计算集群计算节点中残留进程的方法及系统
CN118378679A (zh) 一种图神经网络核心算子加速方法、计算系统及存储介质
CN117040631A (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
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20211224