Title page for ETD etd-10052001-132416


Type of Document Master's Thesis
Author Hegazy, Tamir A.
URN etd-10052001-132416
Title Using Application Benefit for Proactive Resource Allocation in Asynchronous Real-Time Distributed Systems
Degree Master of Science
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Ravindran, Binoy Committee Chair
Davis, Nathaniel J. IV Committee Member
Midkiff, Scott F. Committee Member
Keywords
  • asynchrounous systems
  • resource allocation
  • computer
  • real-time
  • distributed systems
Date of Defense 2001-09-20
Availability unrestricted
Abstract
This thesis presents two proactive resource allocation algorithms, RBA* and OBA, for asynchronous real-time distributed systems. The algorithms consider an application model where timeliness requirements are expressed using Jensen's benefit functions and propose adaptation functions to describe anticipated workload for future time intervals. Furthermore, an adaptation model is considered where processes are replicated for sharing workload increases. A real-time Ethernet system model is considered where message collisions are resolved. Given such models, the objective is to maximize aggregate application benefit and minimize aggregate missed deadline ratio. Since determining the optimal allocation is computationally intractable, the algorithms heuristically compute the allocation so that it is as "close" as possible to the optimal allocation. While RBA* analyzes process response times to determine the allocation, OBA analyzes processor overloads to compute the decision in a much faster way. RBA* incurs a quadratic amortized complexity in terms of subtask arrivals for the most computationally intensive component when DASA is used as the underlying process-scheduling algorithm, whereas OBA incurs a logarithmic amortized complexity for the corresponding component. To study how different process-scheduling and message-scheduling algorithms affect the performance of the algorithms and to compare their performances, benchmark-driven experiments were conducted. The experimental results reveal that RBA* produces higher aggregate benefit and lower missed deadline ratio when DASA is used for process scheduling and message scheduling. Furthermore, it is observed that RBA* produces higher aggregate benefit and lower missed deadline ratio than OBA, confirming the intuition that accurate response time analysis can lead to better results.
Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Thesis.pdf 367.17 Kb 00:01:41 00:00:52 00:00:45 00:00:22 00:00:01

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.