Practical performance analysis of real-time multiprocessor scheduling algorithms

Abstract

This paper presents a practical performance analysing of two real-time multiprocessor scheduling algorithms, namely, Largest Remaining Execution-Time and Local Time Domain (LRE-TL) and Unfair Semi-Greedy (USG). The analysis is intended to reflect the behindthe- scene time overhead incurred by optimal real-time algorithms such as LRE-TL. The overhead is known to be capable of dismissing the actual optimality of such algorithms in practical applications. Here, the time overhead is measured in terms of the number of scheduler invocations and the time required by the scheduling event handlers. In the implementation of the proposed analysis method, the CPU profiler of Oracle JavaTM VisualVM was used to monitor the executions of LRE-TL and USG. The profiler measured the number of invocations of the scheduling event handlers for each algorithm and the total time required for all the invocations. The results revealed that USG outperformed LRE-TL on both measures, indicating that optimal algorithms may prove to be non-optimal in practical applications.

Keywords: Real-time; Multiprocessor; Scheduling