Bounding Carry-in Interference to Improve Fixed-Priority Global Multiprocessor Scheduling Analysis

The analysis of global multiprocessor scheduling is more difficult than its uniprocessor counterpart. Due to the unknown critical instant, existing techniques use over-approximations of task interference for efficient yet pessimistic analysis. In this paper, we proposed a new technique to improve the precision of interference estimation. The key is to identify and resolve contradicting assumptions made in the analysis procedure. The resulting new analysis method improves the analysis precision at the price of a higher complexity. Then we introduce techniques to optimize the new method for better efficiency. Experiments with randomly generated task sets are conducted to evaluate both the precision and efficiency of the proposed new method.