In proportional-share frameworks, resource rights are encapsulated by shares, which are owned by clients that consume resources.4 A client is entitled to consume resources proportional to its share allocation; it is guaranteed a minimum resource fraction equal to its fraction of the total shares in the system. Shares represent relative resource rights that depend on the total number of shares contending for a resource. Client allocations degrade gracefully in overload situations, and clients proportionally benefit from extra resources when some allocations are underutilized.
Both randomized and deterministic algorithms have been proposed for proportional-share allocation of space-shared resources. The dynamic min-funding revocation algorithm [31,32] is simple and effective. When one client demands more space, a replacement algorithm selects a victim client that relinquishes some of its previously-allocated space. Memory is revoked from the client that owns the fewest shares per allocated page. Using an economic analogy, the shares-per-page ratio can be interpreted as a price; revocation reallocates memory away from clients paying a lower price to those willing to pay a higher price.