Using application benefit for proactive resource allocation in asynchronous real-time distributed systems
Tóm tắt
This paper presents two proactive resource allocation algorithms, called 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 application workload during future time intervals. Furthermore, the algorithms consider an adaptation model, where application processes are dynamically replicated for sharing workload increases and a switched real-time Ethernet network as the underlying system model. Given such models, the objective of the algorithms is to maximize the aggregate application benefit and minimize the aggregate missed deadline ratio. Since determining the optimal allocation is computationally intractable, the algorithms heuristically compute near-optimal resource allocations in polynomial-time. While RBA* analyzes the process response times to determine resource allocation decisions, which is computationally expensive, OBA analyzes processor overloads to compute its decisions in a much faster way. RBA* incurs a quadratic amortized complexity in terms of process arrivals for its most computationally intensive component when DASA is used as the underlying scheduling algorithm, whereas OBA incurs a logarithmic amortized complexity for the corresponding component. Our benchmark-driven experimental studies reveal that RBA* produces a higher aggregate benefit and lower missed deadline ratio than OBA.
Từ khóa
#Resource management #Real time systems #Quality of service #Aggregates #Runtime #Application software #Adaptation model #Ethernet networks #Timing #Heuristic algorithmsTài liệu tham khảo
2002, IEEE Trans Computers, 51
koob, 1996, Quorum, Proc Darpa ITO General PI Meeting, 59
lee, 1999, On Quality of Service Management
hull, 1997, An End-to-End QoS Model and Management Architecture, Proc IEEE Workshop Middleware for Distributed Real-Time Systems and Services, 82
10.1109/RTTAS.1999.777680
10.1109/RTTAS.1998.683195
jensen, 1992, Asynchronous Decentralized Real-Time Computer Systems, Real-Time Computing
humphrey, 1997, The DQM Architecture: Middleware for Application Centered QoS Resource Management, Proc IEEE Workshop Middleware for Distributed Real-Time Systems and Services, 97
10.1109/REAL.1998.739756
10.1109/REAL.1998.739732
1997, High Performance Distributed Computing
clark, 1999, An Adaptive, Distributed Airborne Tracking System, Proc Seventh IEEE Int'l Workshop Parallel and Distributed Real-Time Systems, 353
10.1109/RTTAS.2000.852465
10.1023/A:1008141921230
hegazy, 2001, Using Application Benefit for Proactive Resource Allocation in Asynchronous Real-Time Distributed Systems
ravindran, 2001, RBA: A Best Effort Resource Allocation Algorithm for Asynchronous, Real-Time Distributed Systems, J Research and Practice in Information Technology, 33, 213
clark, 1990, Scheduling Dependent Real-Time Activities
10.1109/32.979988
10.1109/REAL.1997.641293
buttazzo, 1997, Hard Real-Time Computing Systems Predictable Scheduling Algorithms and Applications
10.1007/978-1-4615-2271-3_4
10.1109/71.640019
10.1145/321738.321743
devarasetty, 2001, Heuristic Algorithms for Adaptive Resource Management of Periodic Tasks in Soft Real-Time Distributed Systems
locke, 1986, Best-Effort Decision Making for Real-Time Scheduling
mills, 1995, Improved Algorithms for Synchronizing Computer Network Clocks, IEEE/ACM Trans Networks, 245, 10.1109/90.392384
10.1109/RTTAS.1999.777659
10.1049/sej.1993.0034
2002, Quorum