Scheduling Analysis Of Parallel Real-Time Tasks Under Partitioned Scheduling

With the widespread application of multi-core processors and the development of parallel programming technology,scheduling and analysis of parallel real-time tasks for multi-core processors has gradually become an important research direction in the field of real-time systems.This thesis focuses on the schedulability analysis problem of parallel real-time task partitioned fixed-priority scheduling,based on the directed acyclic graph task model for parallel real-time task preemptive Research on scheduling algorithms,real-time lock protocols,and schedulability experimental analysis tools.The main content and contributions of this article are as follows:(1)Based on the analysis of non-preemptive P-FP scheduling of parallel real-time tasks,a method for analyzing the schedulability of parallel real-time tasks under preemptive scheduling is proposed.Aiming at the problem of repeatedly traversing the DAG path in non-preemptive P-FP scheduling analysis,the analysis method is improved to improve the time efficiency of the analysis.On this basis,the problem of resource access control for parallel real-time tasks under P-FP scheduling is studied.(2)The serial task-oriented semaphore real-time lock protocol MPCP(Multiprocessor Priority Ceiling Protocol)is extended,and MPCP-p is proposed to support the parallel task model.First,study the lock rules of the parallel real-time task semaphore lock protocol,and propose the arbitration rules for semaphore contention between task nodes under P-FP scheduling.Subsequently,the time characteristics of task blocking are analyzed,and the type of task blocking is defined.On this basis,the analysis method of the worst blocking time of the task is proposed and integrated into the task schedulability analysis.The experimental analysis of schedulability shows that MPCP-p is better than the existing real-time lock protocol based on global scheduling and federated scheduling in most cases.(3)The serial task-oriented spin lock protocol MSRP(Multiprocessor Stack Resource Protocol)is extended,and MSRP-p is proposed to support the parallel task model.For P-FP scheduling,a non-preemptive spinlock protocol schedulability analysis method based on FIFO(First In First Out)queuing is proposed.Through the schedulability analysis,the MSRP-p and similar parallel real-time task lock protocols are compared and analyzed.The results show that MSRP-p is generally better than other existing lock protocols.At the same time,the implementation results show that MSRP-p is usually better than MPCP-p when the critical region is longer,and on the contrary,MPCP-p is better than MSRP-p.This result is consistent with the overall conclusion of the serial task lock protocol research and analysis.(4)Based on the parallel real-time task scheduling and lock protocol analysis method proposed in this thesis,based on the schedulability analysis tool SET-MRTS developed in the laboratory,a schedulability analysis model framework supporting P-FP scheduling of parallel real-time tasks is designed and implemented.And the corresponding algorithm library.