一种基于三支决策的云任务调度优化算法

doi:10.11896/jsjkx.201000023

摘要/Abstract

摘要： 云任务调度作为云计算体系的一个重要组成部分,其调度策略的效果直接影响到云平台资源利用率及用户服务质量。为解决当前云调度策略中Min-Min算法和Ma-Min算法容易因云任务分布导致负载不均衡、资源综合使用率低和任务总体完成时间较大等问题,提出一种基于三支决策的云任务调度优化算法(Cloud Task Scheduling Algorithm based on three-Way Decision,CTSA-3WD)。根据云任务的执行时间和计算资源的实际情况来标定任务集合中的轻负载任务和重负载任务。借鉴三支决策基本思想,根据两种任务在其任务集合中所占比例进行三支划分,有针对性地对划分后的3个任务集合设计合适的调度策略:针对轻负载任务占比高的任务集合,使用Max-Min算法;针对重负载任务占比高的任务集合,使用Min-Min算法;针对轻重负载任务接近的任务集合,采用基于Min-Min和Max-Min的改进任务调度算法。对分配完毕的节点中的关键资源进行重新调度,在满足总体完成时间减少的前提下选择最匹配的任务分配给轻负载资源。CloudSim仿真平台的实验结果表明,所提出的云任务调度优化算法(CTSA-3WD)相比Min-Min,Max-Min及选择调度算法可以有效提高整体资源利用率,提升了用户的服务质量,同时也使得整个系统中的资源达到更好的负载均衡水平。

关键词: 多粒度, 负载均衡, 任务调度, 三支决策, 云计算

Abstract: As an essential component of the cloud computing system,task scheduling directly impacts resource utilization and service quality.To solve the problems existing in Min-Min and Max-Min algorithms in the current cloud platform,such as load imbalance,low comprehensive resource utilization,and sizeable overall task completion time due to task distribution,a task sche-duling optimization algorithm based on the three-way decision (CTSA-3WD) is proposed.First,the algorithm divides tasks into light-load and heavy-load tasks according to their execution time and computational resource requirements.Secondly,the algorithm divides the tasks into three categories according to the proportion of the task set's two types of tasks.It develops scheduling strategies for these three task sets.Specifically,the strategy uses the Max-Min algorithm for tasks with a high percentage of light load tasks and uses the Min-Min algorithm for a high proportion of heavily loaded tasks.An improved task scheduling algorithm based on Min-Min and Max-Min is used for the set,which has close numbers between light and heavy-duty tasks.Third,the critical resources in the allocated nodes are rescheduled.The algorithm selects the best matching tasks to be allocated to the light-load resources,subject to the overall completion time reduction.The experimental based on the CloudSim reveals that the CTSA-3WD algorithm can effectively improve the overall resource utilization and quality of service to users compared to Min-Min,Max-Min,selective scheduling algorithms.Moreover,it also makes the resources in the whole system reach a better load-balancing level.

Key words: Cloud computing, Load balancing, Multi-granularity, Task scheduling, Three-way decisions

中图分类号:

TP301

王政, 姜春茂. 一种基于三支决策的云任务调度优化算法[J]. 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023

WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions[J]. Computer Science, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023

参考文献

[1] PANDA S K,JANA P K.An efficient task scheduling algorithm for heterogeneous multi-cloud environment[J].The Journal of Supercomputing,2015,71(4):1505-1533.
[2] GAVVALA S K,JATOTH C,GANGADHARAN G R,et al.QoS-aware cloud service composition using eagle strategy[J].Future Generation Computer Systems.2019,90:273-290.
[3] KAUR P,MEHTA S.Resource provisioning and work flowscheduling in clouds using augmented Shuffled Frog Leaping Algorithm[J].Journal of Parallel and Distributed Computing,2017,101:41-50.
[4] CHEN X,CHENG L,LIU C,et al.A WOA-Based Optimization Approach for Task Scheduling in Cloud Computing Systems[J].IEEE Systems Journal,2020,14(3):3117-3128.
[5] GE D,DING Z,JI H.A task scheduling strategy based onweighted round robin for distributed crawler[J].Concurrency &Computation Practice & Experience,2016,28(11):3202-3212.
[6] VERMA A,PEDROSA L,KORUPOLU M,et al.Large-scalecluster management at Google with Borg[C]//Proceedings of the Tenth European Conference on Computer Systems.2015:1-17.
[7] YAO Y.Three-way decision and granular computing[J].International Journal of Approximate Reasoning,2018,103:107-123.
[8] YAO Y.Set-theoretic models of three-way decision[J].Granular Computing,2021,6(1):133-148.
[9] JIANG C,GUO D,DUAN Y,et al.Strategy selection under entropy measures in movement-based three-way decision[J].International Journal of Approximate Reasoning,2020,119:280-291.
[10] YAO Y.Tri-level thinking:models of three-way decision[J].International Journal of Machine Learning & Cybernetics,2019:1-13.
[11] GUO D D,JIANG C M.Multi-stage Regional Transformation Strategy in Move-based Three-way Decisions Model [J]Compute Science,2019,46(10):279-285.
[12] BRAUN T D,SIEGEL H J,BECK N,et al.A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[J].Journal of Parallel & Distributed Computing,2001,61(6):810-837.
[13] ETMINANI K,NAGHIBZADEH M.A Min-Min Max-Min selective algorithm for grid task scheduling[C]//2007 3rd IEEE/IFIP International Conference in Central Asia on Internet.IEEE,2007:1-7.
[14] REHMAN A,JAVED K,BABRI H A,et al.Selection of the most relevant terms based on a max-min ratio metric for text classification[J].Expert Systems with Applications,2018,114:78-96.
[15] ZHANG Y,XU B.Task Scheduling Algorithm based-on QoSConstrains in Cloud Computing[J].International Journal of Grid and Distributed Computing,2015,8(6):269-280..
[16] LI Z,SHEN H,MILES C.PageRankVM:A PageRank BasedAlgorithm with Anti-Collocation Constraints for Virtual Machine Placement in Cloud Datacenters[C]//2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS).IEEE,2018.
[17] BEY K B,BENHAMMADI F,BENAISSA R.Balancing heuristic for independent task scheduling in cloud compu[C]//International Symposium on Programming & Systems.IEEE,2015.
[18] WU J W,JIANG C M.Load-aware score scheduling of three-way clustering for cloud task[J].CAAI transactions on intelligentsystems,2019,14(2):316-322.
[19] JIANG C M,WANG K X.Real-time Cloud Tasks Schedule Algorithm for Saving Energy Based on Tri-queue System,2019,51(2):66-71.
[20] INGBO J,JU W,DALI W,et al.The research on meta-jobscheduling heuristics in heterogeneous environments[J].Journal of Intelligent & Fuzzy Systems,2018,34(2):1141-1151.

相关文章 15

[1]	秦琪琦, 张月琴, 王润泽, 张泽华. 基于知识图谱的层次粒化推荐方法 Hierarchical Granulation Recommendation Method Based on Knowledge Graph 计算机科学, 2022, 49(8): 64-69. https://doi.org/10.11896/jsjkx.210600111
[2]	张源, 康乐, 宫朝辉, 张志鸿. 基于Bi-LSTM的期货市场关联交易行为检测方法 Related Transaction Behavior Detection in Futures Market Based on Bi-LSTM 计算机科学, 2022, 49(7): 31-39. https://doi.org/10.11896/jsjkx.210400304
[3]	田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[4]	杨斐斐, 沈思妤, 申德荣, 聂铁铮, 寇月. 面向数据融合的多粒度数据溯源方法 Method on Multi-granularity Data Provenance for Data Fusion 计算机科学, 2022, 49(5): 120-128. https://doi.org/10.11896/jsjkx.210300092
[5]	高捷, 刘沙, 黄则强, 郑天宇, 刘鑫, 漆锋滨. 基于国产众核处理器的深度神经网络算子加速库优化 Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor 计算机科学, 2022, 49(5): 355-362. https://doi.org/10.11896/jsjkx.210500226
[6]	王志成, 高灿, 邢金明. 一种基于正域的三支近似约简 Three-way Approximate Reduction Based on Positive Region 计算机科学, 2022, 49(4): 168-173. https://doi.org/10.11896/jsjkx.210500067
[7]	高诗尧, 陈燕俐, 许玉岚. 云环境下基于属性的多关键字可搜索加密方案 Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing 计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[8]	田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[9]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[10]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[11]	胡艳丽, 童谭骞, 张啸宇, 彭娟. 融入自注意力机制的深度学习情感分析方法 Self-attention-based BGRU and CNN for Sentiment Analysis 计算机科学, 2022, 49(1): 252-258. https://doi.org/10.11896/jsjkx.210600063
[12]	夏中, 向敏, 黄春梅. 基于CHBL的P2P视频监控网络分层管理机制 Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL 计算机科学, 2021, 48(9): 278-285. https://doi.org/10.11896/jsjkx.201200056
[13]	张师鹏, 李永忠. 基于降噪自编码器和三支决策的入侵检测方法 Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions 计算机科学, 2021, 48(9): 345-351. https://doi.org/10.11896/jsjkx.200500059
[14]	王栋, 周大可, 黄有达, 杨欣. 基于多尺度多粒度特征的行人重识别 Multi-scale Multi-granularity Feature for Pedestrian Re-identification 计算机科学, 2021, 48(7): 238-244. https://doi.org/10.11896/jsjkx.200600043
[15]	李艳, 范斌, 郭劼, 林梓源, 赵曌. 基于k-原型聚类和粗糙集的属性约简方法 Attribute Reduction Method Based on k-prototypes Clustering and Rough Sets 计算机科学, 2021, 48(6A): 342-348. https://doi.org/10.11896/jsjkx.201000053

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed