A Hyperbolic Bound Based Schedulability Test Method For Real-Time Tasks On Multiprocessor

Real-time system is an important research field in computer science, and many real-life real-time systems have been developed and deployed in various application scenarios. With the development of multi-core/multiprocessor systems, real-time systems on multiprocessor are becoming increasingly popular, which has drawn a lot of attention from both academic and industrial community. Among many research issues in real-time multiprocessor systems, establishing schedulability bound is of great significance both theoretically and practically. For a set of real-time tasks on multiprocessor, none of them will miss their corresponding deadline if the utilization of these real-time tasks is less than the schedulbility bound. Therefore, the increase in multiprocessor schedulability bound can greatly improve processor utilization of multiprocessor real-time systems, which means more real-time tasks could be accommodated for a given multiprocessor setting.Lopez proposed a schedulability bound for multiprocessor real-time systems based on rate-monotonic scheduling policy, LL bound (the uniprocessor bound proposed by C.L.Liu), RAD allocation strategy under a partitioned strategy. To the best of our knowledge, it is the state-of-the-art schedulability bound of multiprocessor real-time systems.Bini proposed hyperbolic bound for uniprocessor real-time systems based on rate-monotonic scheduling policy. It was proved that hyperbolic bound is better than LL bound. In view of the advantage of hyperbolic bound over LL bound, we studied the schedulability bound of multi-processor real-time systems based on the hyperbolic bound.The main contributions of this paper are as follows:1. We proposed a new schedulability bound of multi-processor real-time systems based on rate-monotonic scheduling policy, hyperbolic bound and RAD allocation strategy under a partitioned strategy. We proved the correctness of the new bound.2. We analyzed the performance of the new bound. We compared the new bound and the original bound theoretically and experimentally. Although the new bound cannot comprehensively surpass the original one, they are compatible with each other. Experiment results show that combination of the new bound and the original one can significantly increase the number of schedulable task sets.