Reduction of task migrations and preemptions in optimal real-time scheduling for multiprocessors by using dynamic T-L plane

• Published in: Journal of systems architecture 2017-09, Vol.79, p.19-30
• Main Authors: Pham, Ngoc-Son, Kim, Youngmin, Baek, Kwang-Hyun, Lee, Chan-Gun
• Format: Article
• Language: English
• Subjects: Dynamic T-L plane abstraction; Optimal scheduling; Real-time scheduling; Task migration; Task preemption
• ISSN: 1383-7621; 1873-6165
• DOI: 10.1016/j.sysarc.2017.07.003

•A significant number of task preemptions and task migrations is reduced by D-TLPA compared with state-of-the-art algorithms.•The proposed algorithm is totally executed on-line making it affective when dealing with systems where the condition changes dynamically at run-time, for example, when tasks are frequently added or removed.•The concept of the proposed idea is simple and easy to realize in practice. The complexity bound is also presented to prove the feasibility of the proposed algorithm. A new method for optimally scheduling tasks in multiprocessors is proposed in this paper: Dynamic Time and Local Remaining Execution Time Plane Abstraction (D-TLPA). Unlike the conventional T-L plane abstraction method where the positions of T-L planes are fixed according to the fluid schedule of tasks, in this algorithm, the T-L planes can move dynamically up and down in order to reduce unnecessary occurrences of events, resulting in a reduction in the number of task preemptions and migrations. A sub-procedure called T-L Planes Movement (TLPM) is presented to move T-L planes in a proper manner so that all tasks are schedulable. To further reduce task preemptions, tasks preferentially maintain their execution status through consecutive T-L planes with the Running Task Execute First (RTEF) algorithm. Simulations were run on various random task sets, and significant improvements in the number of task preemptions and migrations were seen with this algorithm compared to other state-of-the-art algorithms. The complexity bound is also presented to prove the feasibility of the proposed algorithm.