In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Behnaz Sanati

will defend her dissertation

An Efficient Online Benefit-Aware SRT Multiprocessor Scheduling via Online Choice of Approximation Algorithms for QoS Enhancement

Abstract

Maximizing the benefit gained by soft real-time tasks in many applications and embedded systems is highly needed to provide an acceptable QoS (Quality of Service). Examples of such applications and embedded systems can be real-time medical monitoring systems, video streaming servers, multiplayer video games, and mobile multimedia devices. In these systems, tasks are not equally critical (or beneficial). Each task comes with its own benefit density function which can be different from the others’. The sooner a task completes the more benefit it gains. In this work, a novel online benefit-aware preemptive approach is presented in order to enhance scheduling of soft real-time aperiodic and periodic tasks in multiprocessor systems. Our objective is enhancing the QoS by increasing the total benefit, while reducing flow times and deadline misses. We analyze the theoretical performance of our models. This method prioritizes the tasks using their benefit density functions, which implies their importance to the system, and schedules them in a real-time basis. The first model proposed schedules aperiodic tasks. An online choice of two approximation algorithms, greedy and load-balancing, is used in order to distribute the low priority tasks among identical processors at the time of their arrival without using any statistics. The results of theoretical analysis and simulation experiments show that this method is able to maximize the gained benefit and decrease the computational complexity (compared to existing algorithms) while minimizing makespan with fewer missed deadlines and more balanced usage of processors. Two more versions of this algorithm are proposed for scheduling soft real-time periodic tasks, with implicit and non-implicit deadlines, in addition to another version with a modified load-balancing factor. The extensive simulation experiments and empirical comparison of these algorithms with the state-of-the-art, using different utilization levels and various benefit density functions show that these new techniques outperform the existing ones. A general framework for benefit-aware multiprocessor scheduling in applications with mixed real-time tasks is also provided in this work. 

Date: Tuesday, November 29, 2016
Time: 11:00 AM 
Place: PGH 501D
Advisor: Dr. Albert Cheng

Faculty, students, and the general public are invited.