面向分布式环境的信号驱动任务调度算法

doi:10.11959/j.issn.1000-436x.2015162

Abstract

Abstract:

In order to optimize the performance of user services in IaaS,the task scheduling algorithm for IaaS based on signal-driven is proposed,by which CS(control subsystem) and NS(inquiry nodes subsystem) based on the structural characteristics of the IaaS is established,and the DAG scheduling model based on the structural characteristics of the inquiry task is created.Then the conversion mechanism for the task partitions is created,constructing the signal communication mechanism for CS and NS,changing the status of the task partitions by signal-driven between the CS and NS,completing the task partitions allocation by POSS (parallel optimization selective strategy) in the scheduling time.This algorithm with low complexity is compatible with the distributed architecture of IaaS,because of utilizing dual system control mode.The effectiveness and practicality of this algorithm is verified by experiment.

Key words: IaaS, cloud computing, task scheduling, signal-driven, parallel optimization

Yu XIN,Jing YANG,Zhi-qiang XIE. Task scheduling algorithm for distributed environment based on signal-driven[J]. Journal on Communications, 2015, 36(7): 1-72.

Figures/Tables 15

References 23

[1]	ZHANG J X , GU Z M , ZHENG C . Survey of research progress on cloud computing[J]. Application Research of Computers, 2010,27(2): 429-433.
[2]	谢亚龙, 丁丽萍, 林渝淇等. ICFF：一种IaaS模式下的云取证框架[J]. 通信学报, 2013,34(5): 200-206. XIE Y L , DING L P , LIN Y Q . ICFF:a cloud forensics framework under the IaaS model[J]. Journal on Communications, 2013,34(5): 200-206.
[3]	AMAZON Inc. Amazon elastic compute cloud (Amazon EC2)[EB/OL]. .
[4]	NURMI D , WOLSKI R , GRZEGORCZYK C , et al. The eucalyptus open-source cloud-computing system[A]. Proceedings of the 9th IEEE/ACM Conference on International Computing and the Grid[C]. Tsukuba,Japan, 2009. 124-131.
[5]	COMPUTING R C . Openstack open source cloud computing software[EB/OL]. .
[6]	LU X Y , LIN J , ZHA L , et al. Vega LingCloud:a resource single leasing point system to support heterogeneous application modes on shared infrastructure[A]. Proceedings of the 9th IEEE Conference on Parallel and Distributed Processing with Applications[C]. Busan,Korea, 2011. 99-106.
[7]	MARCOS D , COSTANZO A , BUYYA R . A cost-benefit analysis of using cloud computing to extend the capacity of clusters[J]. Cluster Computing, 2010,13(3): 335-347.
[8]	MARCOS D , COSTANZO A , BUYYA R . Evaluating the cost-benefit of using cloud computing to extend the capacity of clusters[A]. Proceedings of the 18th ACM international Conference on High Performance Distributed Computing[C]. Munich,Germany, 2009. 141-150.
[9]	NAN X , HE Y , GUAN L . Optimal resource allocation for multimedia cloud based on queuing model[A]. Proceedings of the 13th IEEE Conference on Multimedia Signal[C]. Hangzhou,China, 2011. 1-6.
[10]	KLLAPI H , SITARIDI E , TSANGARIS M M , et al. Schedule optimization for data processing flows on the cloud[A]. Proceedings of the 2011 ACM SIGMOD Conference on Management of Data[C]. Athens,Greece, 2011. 289-300.
[11]	LIN C , LU S . Scheduling scientific workflows elastically for cloud computing[A]. Proceedings of the 2011 IEEE Conference on Cloud Computing[C]. Washington DC,USA, 2011. 746-747.
[12]	TOPCUOGLU H , HARIRI S . Performance-effective and low- complexity task scheduling for heterogeneous computing[J]. Parallel and Distributed Systems, 2002(13): 260-274.
[13]	谢志强, 刘胜辉, 乔佩利 . 基于ACPM和BFSM的动态Job-Shop调度算法[J]. 计算研究与发展, 2003,40(7): 977-983. XIE Z Q , LIU S H , QIAO P L . Dynamic job-shop scheduling algorithm based on ACPM and BFSM[J]. Journal of Computer Research and Development, 2003,40(7): 977-983.
[14]	LUIZ F B , EDMUNDO R M . Towards the scheduling of multiple workflows on computational grids[J]. Journal of Grid Computing, 2010,8(3): 419-441.
[15]	谢志强, 杨静, 杨光 . 可动态生成具有优先级工序集的动态Job-Shop调度算法[J]. 计算机学报, 2008,31(3): 502-508. XIE Z Q , YANG J , YANG G . Dynamic Job-Shop scheduling algorithm with dynamic set of operation having priority[J]. Chinese Journal of Computers, 2008,31(3): 502-508.
[16]	LUIZ F B , RIZOS S , EDMUNDO R M . DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[A]. Proceedings of the 18th Euromicro Conference on Parallel,Distributed and Network-Based Processing[C]. Pisa,Italy, 2010. 27-34.
[17]	谢志强, 辛宇, 杨静 . 可回退抢占的设备驱动综合调度算法[J]. 自动化学报, 2011,37(11): 1332-1343. XIE Z Q , XIN Y , YANG J . Machine-driven integrated scheduling algorithm with rollback-preemptive[J]. Acta Automatica Sinica, 2011,37(11): 1332-1343.
[18]	RIZOS S , HENAN Z . A hybrid heuristic for DAG scheduling on heterogeneous systems[A]. Proceedings of the 18th IEEE International Parallel and Distributed Processing Symposium (IPDPS)[C]. Santa Fe,USA, 2004. 266-286.
[19]	谢志强, 杨静, 周勇等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报, 2011,34(2): 406-412. XIE Z Q , YANG J , ZHOU Y , et al. Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J]. Chinese Journal of Computers, 2011,34(2): 406-412.
[20]	TAYAL S . Tasks scheduling optimization for the cloud computing systems[J]. International Journal of Advanced Engineering Sciences And Technologies, 2011,5(2): 111-115.
[21]	PANDEY S , WU L , GURU S M , et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[A]. Proceedings of the 24th IEEE Conference on Advanced Information Networking and Applications[C]. Perth,Australia, 2010. 400-407.
[22]	WU Z , NI Z , GU L , et al. A revised discrete particle swarm optimization for cloud workflow scheduling[A]. Proceedings of the 2010 IEEE Conference on Computational Intelligence and Security[C]. Guangzhou,China, 2010. 184-188.
[23]	LUIZ F B , EDMUNDO R M . Towards the scheduling of multiple workflows on computational grids[J]. Journal of Grid Computing, 2010,8(3): 419-441.

Metrics

Recommended 0

No Suggested Reading articles found!

分片	rank
v₁	132.67
v₂	101.67
v₃	59.33
v₄	96.00
v₅	70.67
v₆	64.67
v₇	38.67
v₈	10.67

current	RT(before)	DT(before)	RT(after)	DT(after)	next current
0	10.11959/j.issn.1000-436x.2015162.F005	d₁:Idled₂:Idled₃:Idle		d₁:v₁:17d₂:Idled₃:Idle	17
17	10.11959/j.issn.1000-436x.2015162.F006	d₁:Idled₂:Idled₃:Idle	10.11959/j.issn.1000-436x.2015162.F007	d₁:v₂:39d₂:Idled₃:Idle	30
30	10.11959/j.issn.1000-436x.2015162.F008	d₁:v₂:39d₂:Idled₃:Idle	10.11959/j.issn.1000-436x.2015162.F009	d₁:v₂:39d₂:v₄:39d₃:Idle	32
32	10.11959/j.issn.1000-436x.2015162.F010	d₁:v₂:39d₂:v₄:39d₃:Idle	10.11959/j.issn.1000-436x.2015162.F011	d₁:v₂:39d₂:v₄:39d₃:v₅:50	33
33	10.11959/j.issn.1000-436x.2015162.F012	d₁:v₂:39d₂:v₄:39d₃:v₅:50	10.11959/j.issn.1000-436x.2015162.F013	d₁:v₂:39d₂:v₄:39d₃:v₅:50	39
39	10.11959/j.issn.1000-436x.2015162.F014	d₁:Idled₂:Idled₃:v₅:50	10.11959/j.issn.1000-436x.2015162.F015	d₁:Idled₂:v₃:44d₃:v₅:50	44
44	10.11959/j.issn.1000-436x.2015162.F016	d₁:Idled₂:Idled₃:v₅:50	10.11959/j.issn.1000-436x.2015162.F017	d₁:Idled₂:Idled₃:v₅:50	50
50	10.11959/j.issn.1000-436x.2015162.F018	d₁:Idled₂:Idled₃:Idle	10.11959/j.issn.1000-436x.2015162.F019	d₁:Idled₂:Idled₃:Idle	52
52	10.11959/j.issn.1000-436x.2015162.F020	d₁:Idled₂:Idled₃:Idle	10.11959/j.issn.1000-436x.2015162.F021	d₁:Idled₂:v₆:101d₃:Idle	57
57	10.11959/j.issn.1000-436x.2015162.F022	d₁:Idled₂:v₆:101d₃:Idle	10.11959/j.issn.1000-436x.2015162.F023	d₁:Idled₂:v₆:101d₃:Idle	60
60	10.11959/j.issn.1000-436x.2015162.F024	d₁:Idled₂:v₆:101d₃:Idle		d₁:Idled₂:v₆:101d₃:v₇:75	75

Sig_A	Sig_T	Sig_R	Sig_F
作用：CS向NS分配任务分片执行任务	作用：CS向NS分配数据传输任务S_ID：传递数据的虚拟设备ID	作用：NS向CS反馈已收到所有所需数据	作用：NS向CS反馈已执行完毕的任务分片
分片：分配执行的任务分片	D_ID：接受数据的虚拟设备ID	分片：就绪的任务分片	分片：执行完毕的任务分片
DB_ID：执行任务分片的虚拟设备ID	分片：需要传递数据的任务分片	DB_ID：就绪任务分片所在的虚拟设备ID	DB_ID：执行完毕的虚拟设备ID

Task scheduling algorithm for distributed environment based on signal-driven

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 23

Related Articles 15

Metrics

Recommended 0

分片	d₁	d₂	d₃
v₁	17	19	21
v₂	22	27	23
v₃	15	5	9
v₄	17	9	20
v₅	30	27	18
v₆	49	49	46
v₇	17	16	15
v₈	13	10	9

[1]	Ling MA, Qiliang FAN, Ting XU, Guanchen GUO, Shenglin ZHANG, Yongqian SUN, Yuzhi ZHANG. Scheduling framework based on reinforcement learning in online-offline colocated cloud environment [J]. Journal on Communications, 2023, 44(6): 90-102.
[2]	Weifeng LU, Ning LI, Jia XU, Lijie XU, Jian XU. Joint scheduling algorithm for correlative tasks in multi-access edge computing [J]. Journal on Communications, 2023, 44(4): 87-98.
[3]	Huaqun WANG, Zhe LIU, Debiao HE, Jiguo LI. Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud [J]. Journal on Communications, 2021, 42(7): 52-60.
[4]	Jianhong ZHANG, Menglong WU, Jing WANG, Pei LIU, Zhengtao JIANG, Changgen PENG. Secure and verifiable multi-keyword searchable encryption scheme in cloud [J]. Journal on Communications, 2021, 42(4): 139-149.
[5]	Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application [J]. Journal on Communications, 2021, 42(3): 11-22.
[6]	Jiawei ZHANG, Jianfeng MA, Zhuo MA, Teng LI. Time-based and privacy protection revocable and traceable data sharing scheme in cloud computing [J]. Journal on Communications, 2021, 42(10): 81-94.
[7]	Wenjuan WANG, Xuehui DU, Dibin SHAN. Construction method of attack scenario in cloud environment based on dynamic probabilistic attack graph [J]. Journal on Communications, 2021, 42(1): 1-17.
[8]	Youliang TIAN,Qin LUO. Verifiable multi-keyword search scheme based on improved Merkle-Tree authentication method [J]. Journal on Communications, 2020, 41(9): 118-129.
[9]	Na WANG,Kun ZHENG,Junsong FU,Jian LI. Method of ciphertext retrieval in mobile edge computing based on block segmentation [J]. Journal on Communications, 2020, 41(7): 95-102.
[10]	Lindong ZHAO,Wenqin ZHUANG,Jianxin CHEN,Liang ZHOU. Hierarchical task offloading in heterogeneous cellular network:modeling and optimization [J]. Journal on Communications, 2020, 41(4): 34-44.
[11]	Qinqin TANG,Renchao XIE,Xu LIU,Yasheng ZHANG,Ci HE,Chengcheng LI,Tao HUANG. MEC enabled satellite-terrestrial network:architecture,key technique and challenge [J]. Journal on Communications, 2020, 41(4): 162-181.
[12]	Bing LIANG,Wen JI. Multiuser computation offloading for edge-cloud collaboration using submodular optimization [J]. Journal on Communications, 2020, 41(10): 25-36.
[13]	Gang LI,Zhijun WU. Task scheduling algorithm for system-wide information management based on multiple QoS constraints [J]. Journal on Communications, 2019, 40(7): 27-37.
[14]	SU Mingfeng,WANG Guojun,LI Renfa. Multidimensional QoS cloud computing resource scheduling method based on stakeholder perspective [J]. Journal on Communications, 2019, 40(6): 102-115.
[15]	CHEN Xingshu,HUA Qiang,WANG Yitong,GE Long,ZHU Yi. Research on low-rate DDoS attack of SDN network in cloud environment [J]. Journal on Communications, 2019, 40(6): 210-222.