EEVDF: Proportional Resource Allocation

The core of the paper presents a novel proportional share allocation algorithm for time-shared resources. The algorithm operates by dividing resource allocation into time quanta of size 'q'. Each client is assigned a weight that directly influences its share of the resource. A key concept is the definition of fairness within an idealized system where resource allocation is continuous (arbitrarily small time intervals). The algorithm's primary contribution is to ensure, under steady-state conditions, that the difference between a client's allocated service time in the real system and its expected service time in the idealized system remains within the bounds of the time quantum 'q'. This provides a strong guarantee of fairness. The algorithm effectively supports dynamic operations, such as clients joining or leaving the system and changes in client weights. It leverages an efficient augmented binary search tree data structure, resulting in an O(log n) time complexity for these operations, where 'n' represents the number of competing clients. This efficiency is a significant advantage for managing dynamic resource demands.

The proposed algorithm is compared to existing schedulers, categorized into proportional share and real-time schedulers. Proportional share schedulers, similar to the proposed algorithm, allocate resources based on client weights, aiming for proportional service. Real-time schedulers, in contrast, function using an event-driven model, where clients are defined by events, service times, and deadlines. They prioritize meeting deadlines through strict admission policies. The paper highlights the strengths of each approach: proportional share schedulers offer greater flexibility and graceful degradation under overload, while real-time schedulers provide stronger guarantees for applications with strict time constraints, such as multimedia. However, real-time schedulers are noted to have limitations in supporting batch applications, due to the mismatch between the event-driven model and the characteristics of batch tasks. This contrast emphasizes the unique advantage of the new algorithm's applicability to a wider range of application types.

Real-time schedulers, while effective for multimedia and interactive applications, are shown to be less suitable for batch applications. Their inherent event-driven nature does not align well with the characteristics of batch tasks, which often lack precise service time predictability and may exhibit significant variations in processing time. The difficulty of accurately determining service time for batch applications, along with the restrictive admission policies of real-time schedulers, are identified as key drawbacks. These limitations lead many general-purpose operating systems to employ conventional algorithms (e.g., round-robin) for batch scheduling alongside real-time schedulers for other application types. This necessitates a more unified approach capable of seamlessly integrating diverse application types, a problem directly addressed by the proposed EEVDF algorithm. The paper emphasizes the need for a scheduler that accommodates both time-critical and non-time-critical tasks without compromising fairness or efficiency.

The Earliest Eligible Virtual Deadline First (EEVDF) algorithm is introduced as a solution for proportional share resource allocation, combining the advantages of proportional share and real-time approaches. The algorithm uses virtual time to track the progress of work in an idealized fluid-flow system. Each client's request is associated with a virtual eligible time and a virtual deadline. A request becomes eligible when the service time the client should have received (based on its weight) equals the service time it has already received. This mechanism ensures fairness by slowing down clients that have received more than their fair share and allowing others to catch up. The algorithm then allocates a new time quantum to the eligible request with the earliest virtual deadline. The use of virtual time and eligible time, in conjunction with virtual deadlines, distinguishes this algorithm from existing proportional share algorithms. The system allows requests of any duration, providing flexibility in managing diverse workloads.

The EEVDF algorithm's design supports higher-level resource abstractions, such as tickets and currencies, and processor capacity reserves, enabling seamless integration with existing resource management mechanisms. The efficient implementation of dynamic operations—clients joining or leaving, and weight changes—is a core feature. This is achieved through the augmented binary search tree, allowing for O(log n) complexity. The algorithm adapts to changing resource demands without significant performance penalties. The paper notes that while higher-level abstractions for priority management exist, they are considered outside the scope of this specific algorithm's core functionality, implying potential for future integration.

The paper addresses the complexities of managing dynamic client operations, focusing on client departures. A key problem is how to fairly distribute the resource share of a departing client among the remaining active clients. The paper analyzes two scenarios: a client leaving with a negative lag (having received more service than its entitlement) and a client leaving with a positive lag (having received less service). In the case of a negative lag, the departing client's excess service time represents a loss for other clients. The proposed solution distributes this loss proportionally among the remaining active clients, according to their weights. This approach ensures fairness and is computationally efficient, only requiring a simple update to the virtual time. This strategy is compared to, but distinguished from, similar approaches in existing algorithms like Waldspurger and Weihl's stride scheduling. The overall goal is to maintain proportional fairness amongst clients even amidst dynamic changes in their participation.

The section explores the challenges involved when a client rejoins the competition after a period of inactivity. The central question focuses on whether and how to compensate a client that left with a positive lag (unutilized share). Not compensating could lead to unfairness, as the unutilized service could accumulate over multiple periods of inactivity. Conversely, compensating a client could harm other currently active clients, creating a new form of unfairness. An example is given to illustrate how compensating a rejoining client for past losses could negatively impact other active clients, highlighting the complexity of finding an equitable solution. The paper indicates that a simple solution is not readily available, and the optimal approach necessitates balancing fairness with the complexity of tracking and distributing past unutilized shares.

Three strategies for handling dynamic operations are presented, each focusing on the management of client lag and virtual time. The first approach involves directly updating the virtual time to account for all changes that occurred since a client's idealized departure time. However, this method is deemed computationally expensive due to the overhead of storing event history and performing the necessary “undo” operations. The second strategy simplifies this by assuming no events occur during a time quantum; this assumption reduces complexity but might introduce some limitations. The third approach allows dynamic operations only when a client's lag is zero. This strategy simplifies the virtual time updates but necessitates managing the timing of dynamic operations, ensuring zero lag before an event. The challenge is updating the virtual time slope when a client leaves with a positive lag. The paper explores different trade-offs among these strategies in terms of complexity, fairness, and accuracy.

A detailed examination of the third strategy, which enforces zero lag before dynamic operations, reveals further complexities. The method aims to simplify the system by reducing all situations to cases where clients have a non-negative lag upon leaving. To handle clients that would otherwise leave with a negative lag, the strategy utilizes dummy requests of zero length. This ensures that such clients are handled as if they left with non-negative lags. The paper justifies this by demonstrating that in a continuously varying virtual time system, requests are completed within one time quantum of their deadline. Moreover, any unused service time from a client's departing request is randomly distributed amongst other clients without updating their lags, a simplistic yet effective strategy for this particular case. This strategy directly addresses the challenges of dynamic client management and fairness while simplifying implementation.

The fairness analysis begins by establishing that the EEVDF algorithm is work-conserving. This crucial property ensures that the resource is never idle as long as at least one client has an eligible pending request. This is demonstrated through Lemma 2, which proves the existence of at least one eligible pending request whenever there's an active client. Building upon this, Theorem 1 provides tight bounds for the client lag (the difference between a client's ideal and actual service time) in a steady-state system. These bounds are critical in quantifying the algorithm's fairness and performance. The analysis shows that in steady-state conditions, the client lag remains within the bounds of a single time quantum (q), a key result highlighting the algorithm's effectiveness in maintaining fairness even under continuous resource requests. The work-conserving nature is a significant feature demonstrating efficient resource utilization.

Further analysis focuses on the impact of request duration on the algorithm's performance. It's shown that when all requests have durations no greater than the time quantum 'q', the algorithm achieves tight and optimal bounds for client lag with respect to any proportional share allocation algorithm (Lemma 5). This demonstrates that the algorithm's effectiveness is particularly strong when dealing with small, frequent requests. However, the paper also acknowledges a trade-off between allocation accuracy and system overhead: shorter requests lead to better accuracy but increase the number of requests processed. Longer requests reduce overhead but can decrease the accuracy of the allocation. This analysis underscores the flexibility of EEVDF in accommodating diverse client needs by allowing requests of varying durations. Clients can choose between better accuracy (shorter requests) and lower overhead (longer requests) depending on their specific requirements.

The bounds established in Theorem 1 highlight the algorithm's ability to maintain tight control over client lag, regardless of request length. The analysis specifies that shorter requests lead to better allocation accuracy, while longer requests decrease the system overhead. This allows for a client-specific trade-off between these two factors. The algorithm's robustness is demonstrated through examples that show how EEVDF can handle the diverse demands of different application types. For computationally intensive tasks, longer requests might be acceptable, while time-critical applications like multimedia require shorter requests to meet strict delay constraints. This adaptability underscores EEVDF’s versatility in managing a diverse mix of applications, providing tight bounds for client lag across the spectrum of computational demands and time sensitivities. The results are significant because they provide quantifiable guarantees on the fairness of resource allocation, irrespective of request characteristics.

The paper contrasts the EEVDF algorithm with the well-known Rate Monotonic (RM) and Earliest Deadline First (EDF) real-time scheduling algorithms. RM assigns priorities based on task periods, with shorter periods receiving higher priority. EDF dynamically assigns priorities based on deadlines, giving the closest deadline the highest priority. While both RM and EDF are used in real-time systems and aim to meet deadlines, they impose strict admission policies to ensure schedulability. The paper highlights the limitations of these real-time schedulers, particularly their difficulty in seamlessly supporting batch applications and their inflexibility in dynamic environments where applications might terminate or their resource demands change. In contrast, EEVDF is presented as a more flexible alternative, capable of handling both real-time and batch applications effectively within a unified framework, offering strong timeliness guarantees without the restrictive admission policies of RM and EDF. The comparison emphasizes that EEVDF provides an integrated solution for diverse applications types that traditional real-time schedulers struggle to manage.

The EEVDF algorithm is compared to Time-Function Scheduling (TFS), another approach to resource allocation. TFS uses time-dependent priority functions, where priority increases linearly with waiting time and resets upon scheduling. Clients are grouped into classes, each with its own priority function, and served in a round-robin fashion within each class. While TFS can achieve proportional share allocation by assigning equal shares to clients within a class, its accuracy depends on the frequency of priority updates, which can be computationally expensive. This contrasts with EEVDF, which achieves efficient dynamic operations with O(log n) complexity using an augmented binary search tree. The comparison emphasizes that EEVDF offers superior accuracy and efficiency in handling dynamic operations compared to TFS's more expensive priority update mechanism.

The EEVDF algorithm shares similarities with fair queueing algorithms used in network bandwidth allocation, particularly the packet-by-packet fair queueing (PFQ) algorithm and its approximation, self-clocked fair queueing (SCFQ). Both PFQ and EEVDF utilize a virtual time model to achieve fairness, however a key distinction is that PFQ makes a packet eligible upon arrival, while EEVDF makes a packet eligible only after previous messages from the same session are processed. This difference, as demonstrated through an example, is shown to be crucial in improving session lag from O(n) to O(1) in EEVDF, where 'n' represents the number of active sessions. The use of virtual time in SCFQ differs from EEVDF's utilization of idealized virtual time. This difference is important for maintaining the work-conserving property, and could make the SCFQ-type virtual time less appropriate for EEVDF due to increased complexity and reduced efficiency.

A comparison is made between EEVDF and stride scheduling, another algorithm for processor scheduling that extends fair queueing concepts. Stride scheduling uses a global pass (similar to virtual time) and client strides (inversely proportional to weight) to allocate time quanta to the client with the lowest pass. While the basic stride scheduling guarantees a client lag of O(nc), a hierarchical approach reduces this to O(log nc), where nc is the number of active clients. However, EEVDF offers improved lag bounds (bounded by one time quantum). The paper further contrasts EEVDF with lottery scheduling. Lottery scheduling uses tickets to represent client shares; a lottery determines which client receives the resource. While simple and efficient for dynamic operations, lottery scheduling's client lag is proportional to the square root of allocated quanta, which is less favorable compared to EEVDF's fixed bounds. This demonstrates the trade off between simple implementation and the guarantee of strong bounds on the client lag.

The EEVDF algorithm is contrasted with the Pseudo-Deadlines (PD) algorithm, a proportional share scheduling algorithm for multiple resources. PD guarantees a client lag bounded by one time quantum for multiple resources, but lacks explicit support for dynamic operations and non-uniform quanta. EEVDF, while demonstrating similar O(log n) time complexity for client selection in the single-resource case, provides efficient support for dynamic operations and handles fractional and non-uniform time quanta. This comparison highlights that EEVDF combines the strengths of proportional share scheduling with efficient handling of dynamic system changes, a critical aspect often lacking in other robust algorithms, such as the PD algorithm.

The conclusion summarizes the key contributions of the Earliest Eligible Virtual Deadline First (EEVDF) algorithm. EEVDF is presented as a new proportional share resource allocation scheduler offering flexible control and strong timeliness guarantees. It provides a unified approach for scheduling multimedia, interactive, and batch applications by uniformly converting application requirements into a sequence of resource requests. A key achievement is the guarantee that, under steady-state conditions, the difference between a client's ideal service time (in an idealized system) and its actual service time remains bounded by one time quantum. This improves upon previous bounds for proportional share allocation in dynamic systems, both for processors and communication bandwidth. The algorithm also supports efficient dynamic operations (clients joining, leaving, or changing weights) and accommodates both fractional and non-uniform time quanta. This combination of features – strong timeliness guarantees, efficient dynamic operation handling, and support for diverse application types – sets EEVDF apart from existing scheduling algorithms.

The paper outlines directions for future research, focusing on the exploration of hierarchical and heterogeneous scheduling schemes. The authors suggest investigating scenarios where clients are grouped into classes, with a higher-level proportional scheduler allocating shares to classes and a lower-level scheduler (e.g., round-robin) managing resources within each class. Another promising avenue involves applying this approach to process-thread hierarchies; a proportional scheduler could manage CPU time slices for processes, and processes would use different policies to select threads. The potential of these approaches to flexible resource management in modern operating systems is highlighted. The authors envision that applications would utilize their own algorithms for managing shares of allocated resources, suggesting a more distributed and application-specific approach to resource management, building upon the foundation established by EEVDF.