Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1109288052.pdf (1.09 MB)

ETD Abstract Container

Abstract Header

REAL-TIME SCHEDULING ALGORITHMS FOR PRECEDENCE RELATED TASKS ON HETEROGENEOUS MULTIPROCESSORS

AULUCK, NITIN
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1109288052

Abstract Details

2005, PhD, University of Cincinnati, Engineering : Computer Science.
The problem of real-time scheduling has been very well researched for the single processor case and the identical multiprocessor case. There are a number of efficient algorithms and schedulability tests that enable the system designer to model his/her application as a set of real-time tasks. However, it may very well be the case that the multiprocessor system consists of processors with different speeds and configurations. This heterogeneity makes the scheduling problem much more complex. Real-time scheduling on heterogeneous multiprocessors has not received much attention in the scheduling literature. We propose several algorithms for scheduling a set of precedence related tasks on heterogeneous multiprocessors. In the first section, we propose a reliability driven algorithm for scheduling periodic tasks on heterogeneous systems. We relax the assumption that all the processors in the system are equally reliable. We introduce a new metric called cost of dependability. The periodic tasks are assigned to processors in such a way that the reliability of the system is maximized. We observe that our scheme generate schedules that are consistently more reliable than the schedules generated by algorithms that do not take the reliability of the processors into account. In the second section, we propose a duplication based algorithm for scheduling a set of soft deadline tasks on a system of heterogeneous multiprocessors. We observe that communicating tasks assigned to different processors have to incur a delay by using the inter-processor communication channel. By duplicating any of these two tasks on either assigned processor, we can cut down on that delay. Hence tasks can start (and hence finish) earlier. This leads to a larger number of tasks meeting their deadlines and hence an increase in the guarantee ratio of the real-time application. The next section extends the concept of task duplication to a set of hard deadline tasks. The deadlines are hard in that even a single deadline miss could lead to catastrophic results. By employing task duplication, we observe that a larger number of task sets are able to finish execution before their deadlines. Hence, the success ratio of the application experiences an increment. Based on our simulation results, we observe that our proposed algorithm offers a higher success ratio as compared to the other algorithms that do not use task duplication. It may very well be the case that the real-time application consists of a mix of tasks with hard and soft deadlines. In the next section, we propose an integrated scheme for scheduling a mix of hard and soft deadline tasks on heterogeneous multiprocessors. We observe that our scheme offers a better schedulability as compared to the other algorithms in the literature when sufficient processors are available and when communication is a dominant factor in the system. Moreover, our algorithm is scalable in that the application can be scheduled even if sufficient processors are not available for the initial cluster generation.
Dr. Dharma Agrawal (Advisor)
128 p.
Computer Science
Real-Time Systems; Task Scheduling; Heterogeneous Multiprocessors; Hard and Soft Deadlines; Scalability; Task Duplication

Recommended Citations

Citations

  • AULUCK, N. (2005). REAL-TIME SCHEDULING ALGORITHMS FOR PRECEDENCE RELATED TASKS ON HETEROGENEOUS MULTIPROCESSORS [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1109288052

    APA Style (7th edition)

  • AULUCK, NITIN. REAL-TIME SCHEDULING ALGORITHMS FOR PRECEDENCE RELATED TASKS ON HETEROGENEOUS MULTIPROCESSORS. 2005. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1109288052.

    MLA Style (8th edition)

  • AULUCK, NITIN. "REAL-TIME SCHEDULING ALGORITHMS FOR PRECEDENCE RELATED TASKS ON HETEROGENEOUS MULTIPROCESSORS." Doctoral dissertation, University of Cincinnati, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1109288052

    Chicago Manual of Style (17th edition)

ucin1109288052
791
© 2005, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.