Research On CPS Distributed Task Scheduling Algorithm Based On DAG Model

The computing environment in which most Cyber-Physical Systems are located is distributed environment.Which means,the execution events handled by CPS are generated by different information sources,with large amount of data,complex structure,uneven distribution and other characteristics.However,in CPS there are still many event groups generated by the same information source.For these event groups,Directed Acyclic Graph can accurately simulate the processing flow of event with order constraints in a distributed environment.In this dissertation,we introduce the research background and development status of information physics system,CPS distributed system and DAG model first.Then,we expound classic task scheduling algorithm and scheduling objectives.After that,we detailed describe our main work for different issues in different scheduling environments,which are:(1)Analyze the monotonic rate algorithm and the earliest deadline time-first algorithm which perform well in the homogeneous multi-processor environment.Aiming at solving the high communication overhead and no inter-task dependencies of these two algorithm when applied to the DAG periodic task model,we propose an Allowed Delay Time Shortest First algorithm under complex tree model.This algorithm adapts to the real-time and the need of complex dependencies between working nodes in the DAG,which improves the overall performance of the system.(2)Aiming at the problem that the processor utilization is too low in the heterogeneous parallel computing environment for large-scale task scheduling,this dissertation proposes an Arrived-Heterogeneous earliest Finish Time algorithm,which can guarantee that all subtasks are effectively processed within the time limit.The algorithm performs better than existing algorithms in terms of processor utilization and task scheduling success rate.(3)When applied to hard real-time of heterogeneous parallel computing environment,we find the priority scheduling assignment for the task does not take the loss of the total value caused by the task failure into account in existing fault-tolerant algorithm.This paper proposes a Fault-Tolerant with Least Value Loss First algorithm which can combine the task deadline with task value to set a priority level based on accurately quantify the reliability of each task and the number of minor versions needed to set.Finally,the effectiveness of the above theory is verified by Yartiss-1.0.2 simulation software.