On Best-Effort Utility Accrual Real-Time Scheduling on Multiprocessors

Simple item page
dc.contributor.authorGaryali, Piyushen
dc.contributor.committeechairRavindran, Binoyen
dc.contributor.committeememberBroadwater, Robert P.en
dc.contributor.committeememberPlassmann, Paul E.en
dc.contributor.departmentElectrical and Computer Engineeringen
dc.date.accessioned2014-03-14T20:41:48Zen
dc.date.adate2010-08-09en
dc.date.available2014-03-14T20:41:48Zen
dc.date.issued2010-07-16en
dc.date.rdate2010-08-09en
dc.date.sdate2010-07-22en
dc.description.abstractWe consider the problem of scheduling real-time tasks on a multiprocessor system. Our primary focus is scheduling on multiprocessor systems where the total task utilization demand, U, is greater than m, the number of processors on a multiprocessor system---i.e., the total available processing capacity of the system. When U > m, the system is said to be overloaded; otherwise, the system is said to be underloaded. While significant literature exists on multiprocessor real-time scheduling during underloads, little is known about scheduling during overloads, in particular, in the presence of task dependencies---e.g., due to synchronization constraints. We consider real-time tasks that are subject to time/utility function (or TUF) time constraints, which allow task urgency to be expressed independently of task importance---e.g., the most urgent task being the least important. The urgency/importance decoupling allowed by TUFs is especially important during overloads, when not all tasks can be optimally completed. We consider the timeliness optimization objective of maximizing the total accrued utility and the number of deadlines satisfied during overloads, while ensuring task mutual exclusion constraints and freedom from deadlocks. This problem is NP-hard. We develop a class of polynomial-time heuristic algorithms, called the Global Utility Accrual (or GUA) class of algorithms. The algorithms construct a directed acyclic graph representation of the task dependency relationship, and build a global multiprocessor schedule of the zero in-degree tasks to heuristically maximize the total accrued utility and ensure mutual exclusion. Potential deadlocks are detected through a cycle-detection algorithm, and resolved by aborting a task in the deadlock cycle. The GUA class of algorithms include two algorithms, namely, the Non-Greedy Global Utility Accrual (or NG-GUA) and Greedy Global Utility Accrual (or G-GUA) algorithms. NG-GUA and G-GUA differ in the way schedules are constructed towards meeting all task deadlines, when possible to do so. We establish several properties of the algorithms including conditions under which all task deadlines are met, satisfaction of mutual exclusion constraints, and deadlock-freedom. We create a Linux-based real-time kernel called ChronOS for multiprocessors. ChronOS is extended from the PREEMPT_RT real-time Linux patch, which provides optimized interrupt service latencies and real-time locking primitives. ChronOS provides a scheduling framework for the implementation of a broad range of real-time scheduling algorithms, including utility accrual, non-utility accrual, global, and partitioned scheduling algorithms. We implement the GUA class of algorithms and their competitors in ChronOS and conduct experimental studies. The competitors include G-EDF, G-NP-EDF, G-FIFO, gMUA, P-EDF and P-DASA. Our study reveals that the GUA class of algorithms accrue higher utility and satisfy greater number of deadlines than the deadline-based scheduling algorithms by as much as 750% and 600%, respectively. In addition, we observe that G-GUA accrues higher utility than NG-GUA during overloads by as much as 25% while NG-GUA satisfies greater number of deadlines than G-GUA by as much as 5% during underloads.en
dc.description.degreeMaster of Scienceen
dc.identifier.otheretd-07222010-114202en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-07222010-114202/en
dc.identifier.urihttp://hdl.handle.net/10919/34112en
dc.publisherVirginia Techen
dc.relation.haspartGaryali_P_T_2010.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectTime/Utility Functionsen
dc.subjectUtility Accrual Schedulingen
dc.subjectMultiprocessor Real-Time Schedulingen
dc.subjectReal-Time Linuxen
dc.titleOn Best-Effort Utility Accrual Real-Time Scheduling on Multiprocessorsen
dc.typeThesisen
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Garyali_P_T_2010.pdf
Size:
1.91 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses