Demonstrable Real-time Analysis Theory Of Multiprocessor Scheduling

Global fixed priority(Global Fixed Priority,GFP)multiprocessor scheduling can realize multi-task parallelism in real-time embedded systems,but it increases the difficulty of real-time analysis.The key to solving the real-time analysis of GFP multiprocessor scheduling is to find a critical moment,because this critical moment can lead to the Worst Case Response Time(WCRT).However,under the current basic theoretical conditions of real-time analysis,the preemptive GFP multi-processor scheduling has not been able to find the critical moment,so the optimal solution cannot be proved theoretically.This is also a classic problem in the international realtime analysis theory.Domestic and foreign scholars have proposed many approximate solutions to obtain the upper bound of WCRT under GFP multiprocessor scheduling,but the optimization space to find a more compact WCRT upper bound is very limited,which hinders the development of realtime analysis theory of GFP multiprocessor scheduling.The workload division method based on the window analysis framework has become the current mainstream analysis method,but these mainstream analysis methods focus on optimizing the carry-in workload,ignoring the fact that analysis pessimism also exists in the body workload and the carry-out workload.On the one hand,this paper finds out the parallel execution of the analyzed task in the carry-out workload,conservatively subtracts the minimum parallel time,and optimizes the carry-out interference;on the other hand,this article constructs the overall maximum interference scenario by determining the job release time,which provides a new idea for the calculation of the WCRT upper bound of GFP multiprocessor scheduling.The innovative work of this paper is as follows:(1)A provable real-time analysis theory for optimizing carry-out interference is proposed.Current mainstream analysis methods assume that carry-out interference is contributed by all carry-out workloads,ignoring the fact that there are parallel carry-out workloads.The proposed method first determines whether the workload of each high-priority task is executed in parallel with the analyzed task at the end of the window,then conservatively subtracts the minimum parallel time from the carry-out workload as the carry-out interference,and then Correct the maximum total interference reasonably,finally derives a more compact WCRT boundary and proves that the boundary is still safe.Experiments show that compared with the current mainstream analysis methods,the proposed method achieves a performance improvement of at least 4%.(2)A provable real-time analysis theory for optimizing the overall interference is proposed.The current mainstream analysis method adopts the workload division method for real-time analysis,ignoring the fact that each sub-part will introduce pessimistic analysis.The proposed method first constructs the tightest interference mode for high-priority tasks to ensure that the most interfering tasks are generated,and then construct s the maximum interference value of the first job to ensure that the execution of the analyzed task is delayed to the greatest extent,and then schedule s the execution time and location of each job on the multiprocessor,finally derives a more compact WCRT boundary and proves that the boundary is still safe.Experiments show that compared with the current mainstream analysis methods,the proposed method achieves a performance improvement of at least 5.2%.