  Maximizing resource utilization by performing an efficient resource
provisioning is a key factor for any cloud provider: commercial actors can
maximize their revenues, whereas scientific and non-commercial providers can
maximize their infrastructure utilization. Traditionally, batch systems have
allowed data centers to fill their resources as much as possible by using
backfilling and similar techniques. However, in an IaaS cloud, where virtual
machines are supposed to live indefinitely, or at least as long as the user is
able to pay for them, these policies are not easily implementable. In this work
we present a new scheduling algorithm for IaaS providers that is able to
support preemptible instances, that can be stopped by higher priority requests
without introducing large modifications in the current cloud schedulers. This
scheduler enables the implementation of new cloud usage and payment models that
allow more efficient usage of the resources and potential new revenue sources
for commercial providers. We also study the correctness and the performace
overhead of the proposed scheduler agains existing solutions.
