1,721,111 research outputs found
Exact GPS simulation and optimal fair scheduling with logarithmic complexity
No full textGeneralized processor sharing (GPS) is a fluid scheduling policy providing perfect fairness over both constant-rate and variable-rate links. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one maximum packet size. To the best of our knowledge, the only packet scheduler guaranteeing the minimum deviation is worst-case fair weighted fair queueing , which requires on-line GPS simulation. Existing algorithms to perform GPS simulation have worst-case computational complexity per packet transmission (being the number of competing flows). Hence, has been charged for complexity too. However it has been proven that the lower bound complexity to guarantee deviation is, yet a scheduler achieving such a result has remained elusive so far. In this paper, we present L-GPS, an algorithm that performs exact GPS simulation with worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. We also present , an implementation of based on L-GPS. has complexity with small constants, and, since it achieves the minimum possible deviation, it does match the aforementioned complexity lower bound. Furthermore, both L-GPS and comply with constant-rate as well as variable-rate links. We assess the effectiveness of both algorithms by simulating real-world scenarios
Reducing the execution time of fair-queueing packet schedulers
No full textDeficit Round Robin (DRR) is probably the most scalable fair-queueing packet scheduler. Unfortunately, it suffers from high delay and jitter with respect to a perfectly fair (and smooth) service. Schedulers providing much better service guarantees exist, but have a higher computational cost.
In this paper we deal with this issue by proposing a modification scheme for reducing the amortized execution time of the latter, more accurate schedulers. Modified schedulers preserve guarantees close to the original ones, and can also handle seamlessly both leaves and internal nodes in a hierarchical setting.
We also present Quick Fair Queueing Plus (QFQ+), a fast fair-queueing scheduler that we defined using this scheme, and that is now in mainline Linux. On one hand, QFQ+ guarantees near-optimal worst-case deviation with respect to a perfectly fair service. On the other hand, with QFQ+, the time and energy needed to process packets are close to those needed with DRR, and may be even lower than with DRR exactly in the scenarios where the better service properties of QFQ+ make a difference
Using a lag-balance property to tighten tardiness bounds for global EDF
No full textSeveral tardiness bounds for global EDF and global-EDF-like schedulers have been proposed over the last decade. These bounds contain a component that is explicitly or implicitly proportional to how much the system may be cumulatively lagging behind, in serving tasks, with respect to an ideal schedule. This cumulative lag is in its turn upper-bounded by upper-bounding each per-task component in isolation, and then summing individual per-task bounds. Unfortunately, this approach leads to an over-pessimistic cumulative upper bound. In fact, it does not take into account a lag-balance property of any work-conserving scheduling algorithm. In this paper we show how to get a new tardiness bound for global EDF by integrating this property with the approach used to prove the first tardiness bounds proposed in the literature. In particular, we compute a new tardiness bound for implicit-deadline tasks, scheduled by preemptive global EDF on a symmetric multiprocessor. According to our experiments, as the number of processors increases, this new tardiness bound becomes tighter and tighter than the tightest bound available in the literature, with a maximum tightness improvement of 29 %. A negative characteristic of this new bound is that computing its value takes an exponential time with a brute-force algorithm (no faster exact or approximate algorithm is available yet). As a more general result, the property highlighted in this paper might help to improve the analysis for other scheduling algorithms, possibly on different systems and with other types of task sets. In this respect, our experimental results also point out the following negative fact: existing tardiness bounds for global EDF, including the new bound we propose, may become remarkably loose if every task has a low utilization (ratio between the execution time and the minimum inter-arrival time of the jobs of the task), or if the sum of the utilizations of the tasks is lower than the total capacity of the system
Extending WF2Q+ to support a dynamic traffic mix
No full textWF2Q+ is a packet scheduler providing optimal QoS guarantees at a low computational complexity. It allows a fraction of the total link capacity to be reserved to each packet flow to transmit, and it guarantees to each flow the minimum possible deviation with respect to its reserved service over any time interval. WF2Q+ has been defined assuming that the set of the packet flows to transmit is fixed and known at system design time. Unfortunately, such assumption is widely violated in many systems, such as Web servers or Internet routers. In this paper we propose a general scheme for extending WF2Q+ to support also the case where the set of packet flows to transmit is unknown beforehand and varies over time. The scheme preserves the service guarantees provided by WF2Q+, and allows different tradeoffs to be realized between computational complexity and system responsiveness to changing traffic mixes. After investigating the pros and cons of the possible solutions based on such general scheme, we present a simple and efficient algorithm for enabling WF2Q+ to support a dynamic traffic mi
Providing Near-Optimal Fair-Queueing Guarantees at Round-Robin Amortized Cost
No full textRound-robin schedulers are the most efficient solution for
providing strong QoS guarantees on high-speed links. Yet these
schedulers suffer from a high worst-case delay with respect
to an ideal, perfectly fair service. More costly schedulers are
needed to provide better service guarantees.
In this paper we tackle this problem by proposing a simple
modification scheme for reducing the amortized execution
time of fair-queueing schedulers. We prove that, applying
this scheme to existing accurate schedulers, we can define
new schedulers providing near-optimal service guarantees at
an amortized computational cost close to that of just Deficit
Round Robin (DRR).
Finally, we show Quick Fair Queueing Plus (QFQ+), a
new scheduler obtained by applying our scheme to QFQ.
QFQ+ replaced QFQ in the Linux kernel. According to our
experimental results, and exactly in the scenarios where QFQ+
provides better service guarantees than a round-robin sched-
uler, the time and the energy needed to process packets with
QFQ+ is lower than with DRR
Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler
No full textGeneralized Processor Sharing (GPS) is a fluid scheduling policy providing perfect fairness. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one packet size. To the best of our knowledge, the only packet scheduler guaranteeing such minimum deviation is Worst-case Fair Weighted Fair Queueing (WF2Q), that requires on-line GPS simulation. Existing algorithms to perform GPS simulation have O(N) complexity per packet transmission (Nbeing the number of competing flows). Hence WF2Q has been charged for O(N) complexity too. Schedulers with lower complexity have been devised, but at the price of at least O(N) deviation from the GPS service, which has been shown to be detrimental for real-time adaptive applications and feedback based applications. Furthermore, it has been proven that the lower bound complexity to guarantee O(1) deviation is Omega(log N), yet a scheduler achieving such result has remained elusive so far.In this paper we present an algorithm that performs exact GPS simulation with O(log N) worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. In particular, using our algorithm within WF2Q, we achieve the minimum deviation from the GPS service with O(log N) complexity, thus matching the aforementioned lower bound. Furthermore, we assess the effectiveness of the proposed solution by simulating real-world scenarios
An Upper Bound to the Lateness of Soft Real-time Tasks Scheduled by EDF on Multiprocessors
No full textMultiprocessors are now commonplace for efficiently achieving high computational power, even in embedded systems. A considerable research effort is being addressed to schedulability analysis of global scheduling in symmetric multiprocessor platforms (SMP), where there is a global queue of ready tasks, and preemption and migration are allowed. In many soft real-time applications (as e.g. multimedia and telecommunication) a bounded lateness is often tolerated. Unfortunately, when considering priority-driven scheduling of periodic/sporadic tasks, previous results only focused on guaranteeing all deadlines, and provided worst-case utilization bounds that are lower than the maximum available computational power. In particular, until now, the existence of an upper bound on the lateness of soft real-time tasks for a fully utilized SMP was still an open problem. In this paper we do solve this problem by providing an upper bound to the lateness of periodic/sporadic tasks - with relative deadlines equal to periods/minimum inter-arrival times - scheduled by EDF on a SMP, under the only assumption that the total utilization is no higher than the total system capacit
Hybrid: achieving deterministic fairness and high throughput in disk scheduling
No full textMany computer applications require moving data from/to disk devices. Since the throughput of disk devices is extremely sensitive to the locality of accesses, the disk schedulers proposed in the literature typically assume the knowledge of the disks' physical parameters (e.g. seek and rotational latency) to meet the different Quality of Service requirements. Unfortunately, the unavoidable discrepancies between the estimated and actual values of such parameters affect the service guarantees, both in terms of response time and disk bandwidth distribution
High Throughput Disk Scheduling with Fair Bandwidth Distribution
No full textMainstream applications–such as file copy/transfer, Web, DBMS, or video streaming–typically issue synchronous diskrequests. As shown in this paper, this fact may cause work-conserving schedulers to fail both to enforce guarantees and to provide a high disk throughput. A high throughput can be however recovered by just idling the disk for a short time interval after the completion of each request. In contrast, guarantees may still be violated by existing timestamp-based schedulers, because of the rules they use to tag requests.Budget Fair Queueing (BFQ), the new disk scheduler presented in this paper, is an example of how disk idling, combined with properback-shifting of request timestamps, may allow a timestamp-based disk scheduler to preserve both guarantees and a high throughput.Under BFQ each application is always guaranteed–over any time interval and independently of whether it issues synchronous requests–a bounded lag with respect to its reserved fraction of the total number of bytes transferred by the disk device.We show the single-disk performance of our implementation of BFQ in the Linux kernel through experiments with real and emulated mainstream applications
Design and testing of scalable Web-based systems with performance constraints
No full textModern Web sites provide multiple services that are deployed through complex infrastructures consisting of distributed components, processes and server nodes. The importance and the economic impact of consumer-oriented Web sites introduces significant requirements, mainly in terms of user perceived performance and scalability. This paper presents some methods for the design and testing of modern, dynamic Web sites and for the improvement of existing systems that must satisfy some performance constraints even in the case of unpredictable load variations. A case study describes the application of the proposed methods to a typical consumer-oriented Web site
- …
