DAG Task Model Scheduling And Its Synchronization Mechanism Research

In the current embedded multi-core system,there are a large number of tasks that need to be calculated and processed,such as the tasks of each control module in the unmanned vehicle system and large-scale industrial control equipment.There are complex constraint relationships between these tasks,and the DAG task Models are often used to describe the relationships between these tasks.The scheduling algorithm of the DAG task model can also be applied to multi-core systems.In order to shorten the overall task completion time in the system,the research on the scheduling algorithm of the DAG task model has become a key issue.For the DAG task graph with communication overhead,the existing scheduling algorithm based on task replication has the problem of data redundancy,while the scheduling algorithm based on critical path has the problem of large amount of calculation.In addition,in the process of task scheduling,task synchronization is also very important.Most synchronization methods based on the lock mechanism have tasks such as busy status,which wastes CPU resources.When the lock resources are not satisfied,context overhead problems will occur.If the These lock mechanisms are applied to the DAG task synchronization under the multi-core platform,which will not only affect the overall efficiency of the system,but even cause deadlock and crash the system.In view of the problems existing in the current research,in order to further improve the parallel processing capability of the multi-core processor and the overall execution efficiency of the system,and to avoid the problems of the lock mechanism when operating on the buffer,this paper conducts the following research:(1)For the DAG task graph scheduling problem with communication overhead,the NMTD(Node matrix and task duplication scheduling algorithm)scheduling algorithm is proposed.First,the node matrix of each task is calculated,and the minimum cost set is found according to the node matrix,and then according to The merging rule merges the minimum cost set,and finally copies the tasks of the remaining nodes according to the scheduling situation,and obtains the final scheduling sequence,avoiding a large number of task duplication and double calculation of task nodes.Experiments show that with the increase of the acceptance rate of the algorithm,the acceptance rate of the NMTD algorithm tends to a stable state,which is 9.28% higher than that of the DCP algorithm,CPFD algorithm and TTTD algorithm;The overall performance of the acceptance rate is increased by 9.78%,which is higher than other algorithms,and the worst response time is reduced by 7.66%.(2)For the task synchronization problem existing in the DAG task graph scheduling process,a DCAS(Double Compare And Swap)lock-free mechanism is proposed,and it is applied to the buffer application and release process of the Vxworks system to avoid the lock mechanism deadlock and other problems.And it is verified on the LITMUSRT multi-core platform.The results show that compared with the traditional lock mechanism,the response time of using DCAS lock-free mechanism is 10.4% lower than that of the lock mechanism,and the actual task execution time is reduced by 4.2%.