On the Duality between Resource Reservation and Proportional Share Resource Allocation

摘要: We describe a new framework for resource allocation that unifies the well-known proportional share and reservation policies. By exploiting duality between these policies, we provide level of integration scheduling batch, interactive, real time applications not achieved before. To each client associate weight represents rate at which has to pay resource, fraction should receive. These two parameters are interdependent. A fixed corresponds allocation, while reservation. Furthermore, once one parameter is other results automatically: if asks then competition determines it pay, fixed, service implement this have developed algorithm, called Earliest Eligible Virtual Deadline First, achieves optimal accuracy, i.e., difference receive in an ideal system, actually received system bounded by size quantum. This tight bound makes possible support highly predictable, real-time services. As proof concept implemented prototype CPU scheduler under FreeBSD operating system. The experimental show our goal providing integrated batch applications. Moreover, accuracy implementation was within 10% theoretical bounds.