LBBA: An efficient online benefit-aware multiprocessor scheduling for QoS via online choice of approximation algorithms

• We propose LBBA, an online benefit-aware scheduling method for aperiodic tasks.
• Efficient strategy for better QoS in overloaded soft real-time multiprocessor systems.
• LBBA maximizes total gained benefit and minimizes the makespan at the same time.
• It uses online choice of two approximation algorithms, Greedy and Load-balancing.
• It improves QoS by maximizing the total gained benefit and reducing missed job ratio.

Maximizing the benefit gained by soft real-time jobs in many applications and embedded systems is highly needed to provide an acceptable QoS (Quality of Service). This paper considers a benefit model for on-line preemptive multiprocessor scheduling. The goal is to maximize the total benefit gained by the jobs that meet their deadlines. This method prioritizes the jobs using their benefit density functions and schedules them in a real-time basis. We propose an online choice of two approximation algorithms in order to partition the jobs among identical processors at the time of their arrival without using any statistics. Our analysis and experiments show that we are able to maximize the gained benefit and decrease the computational complexity (compared to existing algorithms) while minimizing makespan (response time, also referred to as cost), with fewer missed deadlines and more balanced usage of processors. Our solution is applicable to a wide variety of soft real-time applications and embedded systems such as, but not limited to multimedia applications, medical monitoring systems or those with higher utilization such as bursty hosting servers.1