On Non-Preemptive VM Scheduling in the Cloud
On Non-Preemptive VM Scheduling in the Cloud
复制标题
DOI：
10.1145/3219617.3219644
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Konstantinos Psychas;Javad Ghaderi
中科院分区：
文献类型：
--
作者：
Konstantinos Psychas;Javad Ghaderi
我们研究的问题，调度虚拟机（虚拟机）在分布式服务器平台，由云计算应用的动机。VM随时间动态地到达系统，并且在其服务期间需要一定量的资源（例如，存储器、CPU等）。为了避免代价高昂的抢占，我们考虑非抢占式调度：每个VM必须分配给具有足够剩余容量的服务器，并且一旦VM分配给服务器，其服务就不能中断（抢占）。解决这个问题的现有方法要么具有高复杂性，需要服务器之间的同步，要么产生过大的队列大小/延迟。我们提出了一个非抢占式调度算法，解决了这些问题。一般情况下，给定一个近似比为r的背包近似算法，当β < r时，我们的调度算法可以提供吞吐量区域的rβ部分。在背包的贪婪近似算法的特殊情况下，我们进一步证明了这个条件可以放宽到β<1。参数β和r可以被调谐以提供可实现的吞吐量、延迟和调度算法的计算复杂度之间的折衷。最后，大量的仿真结果，使用合成和真实的流量轨迹，以验证我们的算法的性能。
We study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) for the duration of their service. To avoid costly preemptions, we consider non-preemptive scheduling: Each VM has to be assigned to a server which has enough residual capacity to accommodate it, and once a VM is assigned to a server, its service cannot be disrupted (preempted). Prior approaches to this problem either have high complexity, require synchronization among the servers, or yield queue sizes/delays which are excessively large. We propose a non-preemptive scheduling algorithm that resolves these issues. In general, given an approximation algorithm to Knapsack with approximation ratio r , our scheduling algorithm can provide rβ fraction of the throughput region for β < r. In the special case of a greedy approximation algorithm to Knapsack, we further show that this condition can be relaxed to β<1. The parameters β and r can be tuned to provide a tradeoff between achievable throughput, delay, and computational complexity of the scheduling algorithm. Finally extensive simulation results using both synthetic and real traffic traces are presented to verify the performance of our algorithm.