An Efficient Online Benefit-aware Multiprocessor Scheduling Technique for Soft Real-Time Tasks Using Online Choice of Approximation Algorithms
| dc.contributor.advisor | Cheng, Albert M. K. | |
| dc.contributor.committeeMember | Johnsson, Lennart | |
| dc.contributor.committeeMember | Leiss, Ernst L. | |
| dc.contributor.committeeMember | Pavlidis, Ioannis T. | |
| dc.contributor.committeeMember | Subhlok, Jaspal | |
| dc.contributor.committeeMember | Pettitt, B. Montgomery | |
| dc.creator | Sanati, Behnaz 1973- | |
| dc.date.accessioned | 2019-11-13T03:11:02Z | |
| dc.date.available | 2019-11-13T03:11:02Z | |
| dc.date.created | December 2016 | |
| dc.date.issued | 2016-12 | |
| dc.date.submitted | December 2016 | |
| dc.date.updated | 2019-11-13T03:11:03Z | |
| dc.description.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 include 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. The objective of this work is enhancing the QoS by increasing the total benefit, while reducing flow times and deadline misses. This method prioritizes the tasks using their benefit-density functions, which imply their importance to the system, and schedules them in a real-time basis. The first model I propose is for scheduling soft real-time 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. I also propose two more versions of this algorithm for scheduling SRT periodic tasks, with implicit and non-implicit deadlines, in addition to another version with a modified loadbalancing 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 periodic, aperiodic or mixed real-time tasks is also provided in this work. | |
| dc.description.department | Computer Science, Department of | |
| dc.format.digitalOrigin | born digital | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.citation | Portions of this document appear in: Sanati, Behnaz, and Albert MK Cheng. "LBBA: An efficient online benefit-aware multiprocessor scheduling for QoS via online choice of approximation algorithms." Future Generation Computer Systems 59 (2016): 125-135. | |
| dc.identifier.uri | https://hdl.handle.net/10657/5406 | |
| dc.language.iso | eng | |
| dc.rights | The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. UH Libraries has secured permission to reproduce any and all previously published materials contained in the work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s). | |
| dc.subject | Real-time systems | |
| dc.subject | Multiprocessor systems | |
| dc.subject | Task Partitioning | |
| dc.subject | Benefit-aware | |
| dc.subject | Approximation algorithms | |
| dc.subject | Quality of service | |
| dc.subject | Online Scheduling | |
| dc.subject | Semi-partitioning | |
| dc.title | An Efficient Online Benefit-aware Multiprocessor Scheduling Technique for Soft Real-Time Tasks Using Online Choice of Approximation Algorithms | |
| dc.type.dcmi | Text | |
| dc.type.genre | Thesis | |
| thesis.degree.college | College of Natural Sciences and Mathematics | |
| thesis.degree.department | Computer Science | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | University of Houston | |
| thesis.degree.level | Doctoral | |
| thesis.degree.name | Doctor of Philosophy |