Abstract Autoscaling enables container cluster orchestrators to automatically adjust computational resources, such as containers and Virtual Machines (VMs), to handle fluctuating workloads effectively. This adaptation can involve modifying the amount of resources (horizontal scaling) or adjusting their computational capacity (vertical scaling). The motivation for our work stems from the limitations of previous autoscaling approaches, which are either partial (scaling containers or VMs, but not both) or excessively complex to be used in real systems. This complexity arises from their use of models with a large number of variables and the addressing of two simultaneous challenges: achieving the optimal deployment for a single scheduling window and managing the transition between successive scheduling windows. We propose an Integer Linear Programming (ILP) model to address the challenge of autoscaling containers and VMs jointly, both horizontally and vertically, to minimize deployment costs. This model is designed to be used with predictive autoscalers and be solved in a reasonable time, even for large clusters. To this end, improvements and reasonable simplifications with respect to previous models have been carried out to drastically reduce the size of the resource allocation problem. Furthermore, the proposed model provides an enhanced representation of system performance in comparison to previous approaches. A tool called Conlloovia has been developed to implement this model. To evaluate its performance, we have conducted a comprehensive assessment, comparing it with two heuristic allocators with different problem sizes. Our findings indicate that Conlloovia consistently demonstrates lower deployment costs in a significant number of cases. Conlloovia has also been evaluated with a real application, using synthetic and real workload traces, as well as different scheduling windows, with deployment costs approximately 20% lower than heuristic allocators.

This paper describes a stochastic analysis framework which computes the response time distribution and the deadline miss probability of individual tasks, even for systems with a maximum utilization greater than one. The framework is uniformly applied to fixed-priority and dynamic-priority systems and can handle, tasks with arbitrary relative deadlines and execution time distributions.

The exact stochastic analysis of most real-time systems is becoming unaffordable in current practice. On one side, the exact calculation of the response time distribution of the tasks is not possible except for simple periodic and independent task sets. On the other side, in practice, tasks introduce complexities like release jitter, blocking in shared resources, stochastic dependencies, etc, which can not be handled by the periodic and independent task set model. This paper introduces the concept of pessimism in the stochastic analysis of real-time systems in the following sense: the exact probability of missing any deadline is always lower than that derived from the pessimistic analysis. Therefore, if real-time constraints are expressed as probabilities of missing deadlines, the pessimistic stochastic analysis provides safe results. Some applications of the pessimism concept are presented. Firstly, the practical problems that arise in the stochastic analysis of periodic and independent task sets are addressed. Secondly, we extend to the stochastic case some well known techniques of the deterministic analysis, such as the blocking in shared resources, and the task priority assignment.

The utilization bound for real-time rate monotonic (RM) scheduling on uniprocessors is extended to multiprocessors with partitioning-based scheduling. This allows fast schedulability tests to be performed on multiprocessors and quantifies the influence of key parameters, such as the number of processors and task sizes on the schedulability of the system. The multiprocessor utilization bound is a function of the allocation algorithm, so among all the allocation algorithms there exists at least one allocation algorithm providing the minimum multiprocessor utilization bound, and one allocation algorithm providing the maximum multiprocessor utilization bound. We prove that the multiprocessor utilization bound associated with the allocation heuristic worst fit (WF) coincides with that minimum if we use Liu and Layland's bound (LLB) as the uniprocessor schedulability condition. In addition, we present a class of allocation algorithms sharing the same multiprocessor utilization bound which coincides with the aforementioned maximum using LLB. The heuristics first fit decreasing (FFD) and best fit decreasing (BFD) belong to this class. Thus, not even an optimal allocation algorithm can guarantee a higher multiprocessor utilization bound than that of FFD and BFD using LLB. Finally, the pessimism of the multiprocessor utilization bounds is estimated through extensive simulations.

This paper describes a stochastic analysis method for general periodic real-time systems. The proposed method accurately computes the response time distribution of each task in the system, thus making it possible to determine the deadline miss probability of individual tasks, even for systems with maximum utilization factor greater than one. The method uniformly covers both fixed-priority scheduling (such as rate monotonic) as well as dynamic-priority scheduling (such as earliest deadline first) and can handle arbitrary relative deadlines and execution time distributions. The accuracy of the method is proven by comparing the results from the analysis with those obtained from simulations, as well as other methodologies in the literature.

This paper deals with the problem of finding utilization bounds for multiprocessor rate monotonic scheduling with partitioning. The minimum and maximum utilization bounds among all the reasonable allocation algorithms are calculated. We prove that the utilization bound associated with the reasonable allocation heuristic Worst Fit (WF) is equal to that minimum. In addition, we prove that the utilization bound associated with the heuristics First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) is equal to the maximum, of value (n+1)(2/sup 1/2/-1), where n is the number of processors.

Presents the utilization bound for earliest deadline first (EDF) scheduling on homogeneous multiprocessor systems with partitioning strategies. Assuming that tasks are pre-emptively scheduled on each processor according to the EDF algorithm, and allocated according to the first-fit (FF) heuristic, we prove that the worst-case achievable utilization is 0.5(n+1), where n is the number of processors. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value /spl alpha/, the previous bound is raised, and the new utilization bound considering /spl alpha/ is calculated. In addition, we prove that no uniprocessor scheduling algorithm/allocation algorithm pair can provide a higher worst-case achievable utilization than that of EDF-FF. Finally, simulation provides the average-case achievable utilization for EDF-FF.