Approximation algorithm for periodic real-time tasks with workload-dependent running-time functions

摘要: This paper addresses the problem of resource allocation for distributed real-time periodic tasks, operating in environments that undergo unpredictable changes and defy specification meaningful worst-case execution times. These tasks are supplied by input data originating from various environmental workload sources. Rather than using times (WCETs) to describe CPU usage we assume here profiles given running time terms size each source. The objective is produce an initial robust against fluctuations parameters. We try maximize (workload) can be handled system, hence delay possible (costly) reallocations as long possible. present approximation algorithm based on first-fit binary search call FFBS. As show here, produces solutions often close optimal. In particular, analytically FFBS guaranteed a solution at least 41% optimal, asymptotically, under certain reasonable restrictions system. Moreover, if most 12% system utilization consumed independent (e.g., constant tasks), then 33% asymptotically. simulations compare with set standard (local search) heuristics such hill-climbing, simulated annealing, random search. results suggest FFBS, combination other local improvement strategies, may approach dynamic systems.