{'fraction_non_alphanumeric': 0.030612575801796542, 'fraction_numerical': 0.009939358562765508, 'mean_word_length': 4.629849383842994, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
PSBS: Practical Size-Based Scheduling

Size-based schedulers have very desirable performance properties: optimal or near-optimal response time can be coupled with strong fairness guarantees. Despite this, such systems are very rarely implemented in practical settings, because they require knowing a priori the amount of work needed to complete jobs: this assumption is very difficult to satisfy in concrete systems. It is definitely more likely to inform the system with an estimate of the job sizes, but existing studies point to somewhat pessimistic results if existing scheduler policies are used based on imprecise job size estimations. We take the goal of designing scheduling policies that are explicitly designed to deal with inexact job sizes: first, we show that existing size-based schedulers can have bad performance with inexact job size information when job sizes are heavily skewed; we show that this issue, and the pessimistic results shown in the literature, are due to problematic behavior when large jobs are underestimated. Once the problem is identified, it is possible to amend existing size-based schedulers to solve the issue. We generalize FSP -- a fair and efficient size-based scheduling policy -- in order to solve the problem highlighted above; in addition, our solution deals with different job weights (that can be assigned to a job independently from its size). We provide an efficient implementation of the resulting protocol, which we call Practical Size-Based Scheduler (PSBS). Through simulations evaluated on synthetic and real workloads, we show that PSBS has near-optimal performance in a large variety of cases with inaccurate size information, that it performs fairly and it handles correctly job weights. We believe that this work shows that PSBS is indeed pratical, and we maintain that it could inspire the design of schedulers in a wide array of real-world use cases.


Introduction
In computer systems, several situations can be modeled as queues where jobs (e.g., batch computations or data transfers) queue to access a shared resource (e.g., processor or network). In this context, size-based scheduling protocols, which prioritize jobs that are closest to completion, are well known to have very desirable properties: the shortest remaining processing time policy (SRPT) provides optimal mean response time [Schrage and Miller, 1966], while the fair sojourn protocol (FSP) [Friedman and Henderson, 2003] provides similar efficiency while guaranteeing strong fairness properties at the same time.
Despite these characteristics, however, scheduling policies similar to SRPT or FSP are very rarely deployed in production: the de facto standard are size-oblivious policies similar to processor sharing (PS), which divides resources evenly among jobs in the queue. A key reason is that, in real systems, job size is almost never known a priori. It is, instead, often possible to provide estimations of job size, which may vary in precision depending on the use case; however, the impact of errors due to these estimations in realistic scenarios is not yet well understood.
Perhaps surprisingly, very few works tackled the problem of size-based scheduling with inaccurate job size information: as we discuss more in depth in Section 2, the existing literature gives somewhat pessimistic results, suggesting that size-based scheduling is effective only when the error on size estimation is small; known analytical results depend on restrictive assumptions on size estimations, while simulation-based analyses only cover a limited family of workloads. More importantly, no study we are aware of tackled the design of size-based scheduling techniques that are explicitly designed with the goal of coping with errors in job size information. In this work, our endeavor is to create a practical size-based scheduling protocol, that has an efficient implementation and handles imprecise size information. In addition, the scheduler should allow setting weights to jobs, to control the relative proportion of the resources assigned to them.
In Section 3, we provide a qualitative analysis of the impact of size estimation errors on the behavior of scheduling: we show that, for heavy-tailed job size distributions, both FSP and SRPT behave problematically when large jobs are under-estimated: this phenomenon, indeed, explains the pessimistic results that have been observed in previous work.
Fortunately, it is possible to modify scheduling protocols to solve the aforementioned problem: in Section 4, we design a family of new scheduling protocols that drastically improve the behavior of FSP and SRPT when errors are present. FSP-based protocols behave in a particularly desirable way, but FSP has two issues that limit it in practical situations: an inefficient O(n) implementation, and the lack of support for weights to differentiate jobs. We design a generalization of FSP which we call PSBS (Practical Size-Based Scheduler) that solves this issue, with an O(log n) implementation and support for job weights.
We developed a simulator, described in Section 5, to study the behavior of size-based and size-oblivious scheduling policies in a wide variety of scenarios. Our simulator allows both replaying real traces and generating synthetic ones varying system load, job size distribution and inter-arrival time distribution; for both synthetic and real workloads, scheduling protocols are evaluated on errors that range between relatively small quantities and others that may vary even by orders of magnitude. The simulator is released as open-source software, to help reproducibility of our results and to facilitate further experimentation on the topic.
From the experimental results of Section 6, we highlight the following ones, validated both on synthetic and real traces: 1. When job size is not heavily skewed, SRPT and FSP outperform size-oblivious disciplines even when job size estimation is very imprecise, albeit past work would hint towards important performance degradation; on the other hand, when the job size distribution is heavy-tailed, performance degrades noticeably; 2. The scheduling disciplines we propose do not suffer from the performance issues of FSP and SRPT; they provide good performance for a large part of the parameter space that we explore, being outperformed by a processor sharing strategy only when both the job size distribution is heavily skewed and size estimations are very inaccurate; 3. PSBS handles job weights correctly and behaves fairly, guaranteeing that most jobs complete in an amount of time that is proportional to their size.
As we discuss in Section 7, we conclude that our work highlights and solves a key weakness of size-based scheduling protocols when size estimation errors are present; the fact that PSBS consistently performs close to optimally highlights that size-based schedulers are more viable in real systems than what was known from the state of the art; we believe that our work can help inspiring both the design of new size-based schedulers for real systems and analytic research that can provide better insight on scheduling when errors are present.

Related Work
We discuss two main areas of related work: first, results for size-based scheduling on single-server queues when job sizes are known only approximately; second, practical approaches devoted to the estimation of job sizes.

Single-Server Queues
Performance evaluation of scheduling policies in single-server queues has been the subject of many studies in the last 40 years. Most of these works, however, focus on extreme situations: either the size of a given job is completely unknown, or it is known perfectly. In the first case (size-oblivious scheduling), smart scheduling choices can still be taken by considering the overall job size distribution: for example, in the common case where job sizes are skewed -i.e., a small percentage of jobs are responsible for the majority of work performed in the system -it is smart to give priority to younger jobs, because they are likely to complete faster. Least-Attained-Service (LAS) [Rai et al., 2003], also known in the literature as Foreground-Background (FB) [Kleinrock, 1975] and Shortest Elapsed Time (SET) [Coffman and Denning, 1973], employs this principle. Similar principles guide the design of multi-level queues [Guo and Matta, 2002;Kleinrock, 1976].
When job size is known a priori, scheduling policies taking into account this information are well known to perform better (e.g., obtain shorter response times) than size-oblivious ones. Unfortunately, job sizes can often be only known approximatedly, rather than exactly. Since in our paper we consider this case, we review the literature that targets this problem.
Perhaps surprisingly, not much work considers the effect of inexact job size information on size-based scheduling policies. Lu et al. [2004] have been the first to consider this problem, showing that size-based scheduling is useful only when job size evaluations are reasonably good (high correlation, greater than 0.75, between the real job size and its estimate). Their evaluation focuses on a single heavy-tailed job size distribution, and does not explain the causes of the observed results. Instead, we show the effect of different job size distributions (heavy-tailed, memoryless and light-tailed), and we show how to modify the size-based scheduling policies to make them robust to job estimation errors. Wierman and Nuyens [2008] provide analytical results for a class of size-based policies, but consider an impractical assumption: results depend on a bound on the estimation error. In the common case where most estimations are close to the real value but there are outliers, bounds need to be set according to outliers, leading to pessimistic predictions on performance. In our work, instead, we do not impose any bound on the error.
Other works examined the effect of imprecise size information in size-based schedulers for web servers [Harchol-Balter et al., 2003] and MapReduce [Chang et al., 2011]. In both cases, these are simulation results that are ancillary to the proposal of a scheduler implementation for a given system, and they are limited to a single type of workload.
To the best of our knowledge, these are the only works targeting job size estimation errors in size-based scheduling. We remark that, by using an experimental approach and replaying traces, we can take into account phenomena that are not represented in the abstract M/G/1 or G/G/1 models, such as periodic temporal patterns or correlations between job size and submission time.

Job Size Estimation
In the context of distributed computational systems, FLEX [Wolf et al., 2010] and HFSP [Pastorelli et al., 2013] proved that size-based scheduling can perform well in practical scenarios. In both cases, job size estimation is performed with very simple approaches (i.e., by sampling the execution time of a part of the job): such rough estimates are sufficient to provide good performance, and our results provide an explanation to this.
In several practical contexts, rough job size estimations are easy to perform. For instance, web servers can use the size of files to serve as an estimator of job size [Schroeder and Harchol-Balter, 2006], and the variability of the end-to-end transmission bandwidth will determine the variability of the estimation error. More elaborate ways to estimate the job size are in several cases already available, since job size estimation is relevant in many domains; examples are approaches that deal with predicting the size of MapReduce jobs [Agarwal et al., 2012;Popescu et al., 2012;Verma et al., 2011] and of database queries [Lipton and Naughton, 1995]. The estimation error can be always evaluated a posteriori, and this evaluation can be used to decide if the size-based scheduling works better than policies blind to size.

Scheduling Based on Estimated Sizes
We now introduce the SRPT and FSP size-based scheduling protocols, and describe the effects that estimation errors have on their behavior, focusing on the difference between over-and under-estimation. We notice that under-estimation triggers a behavior which is problematic in particular for heavy-tailed job size distributions: this is the key insight that will lead to the design of PSBS.

SRPT and FSP
The SRPT policy gives priority to the job with smallest remaining processing time. SRPT is preemptive: a new job with size smaller than the remaining processing time of the running one will preempt (i.e., interrupt) the latter. When the scheduler has access to exact job sizes, SRPT has optimal mean sojourn time (MST) [Schrage and Miller, 1966] -sojourn time, or response time, is the time that passes between a job's submission and its completion.
SRPT may cause starvation (i.e., never providing access to resources): for example, if small jobs are constantly submitted, large jobs may never get served. FSP (also known in literature as fair queuing [Nagle, 1987] and Vifi [Gorinsky and Jechlitschek, 2007]) is a policy that doesn't suffer from starvation by virtue of job aging: FSP serves the job that would complete earlier in a virtual emulated system running a processor sharing (PS) discipline: since all jobs eventually complete in the virtual system, they will also eventually be scheduled in the real one.
In the absence of errors, a policy such as FSP is particularly desirable because it obtains a value of MST which is close to what is provided by SRPT while guaranteeing a strong notion of fairness in the sense that FSP dominates PS: no jobs complete later in FSP than in PS [Friedman and Henderson, 2003]. When errors are present, such a property cannot be guaranteed; however, as our experimental results in Section 6.5 show, FSP still preserves better fairness than SRPT even when errors are present.

Dealing With Errors: SRPTE and FSPE
We now consider the behavior of SRPT and FSP when the scheduler has access to estimated job sizes rather than exact ones. For clarity, we will refer hereinafter to SRPTE and FSPE in this case.
In Figure 1 on the following page, we provide an illustrative example where a single job size is over-or under-estimated while the others are estimated correctly, focusing (because of its simplicity) on SRPTE; job sojourn times are represented by the horizontal arrows. The left column of Figure 1 illustrates the effect of over-estimation. In the top, we show how the scheduler behaves without errors, while in the bottom we show what happens when the size of job J 1 is over-estimated. The graphs shows the remaining (estimated) processing time of the jobs over time (assuming a normalized service rate of 1). Without errors, jobs J 2 does not preempt J 1 , and J 3 does not preempt J 2 . Instead, when the size of J 1 is over-estimated, both J 2 and J 3 preempt J 1 . Therefore, the only job suffering (i.e., experiencing higher sojourn time) is the one that has been over-estimated. Jobs with smaller sizes are always able to preempt an over-estimated job, therefore the basic property of SRPT (favoring small jobs) is not significantly compromised.
The right column of Figure 1 illustrates the effect of under-estimation. With no estimation errors (top), a large job, J 4 , is preempted by small ones (J 5 and J 6 ). If the size of the large job is under-estimated (bottom), its estimated remaining processing time eventually reaches zero: we call late a job with zero or negative estimated remaining processing time. A late job cannot be preempted by newly arrived jobs, since their size estimation will always be larger than zero. In practice, since preemption is inhibited, the under-estimated job monopolizes the system until the end of its service, with a negative impact on multiple waiting jobs.
This phenomenon is particularly harmful when job sizes are heavily skewed: if the workload has few very large jobs and many small ones, a single late large job can significantly delay several small ones, which will need to wait for the late job to complete before having an opportunity of being served.
Even if the impact of under-estimation seems straightforward to understand, surprisingly no work in the literature has ever discussed it. To the best of our knowledge, we are the first to identify this problem, which significantly influences scheduling policies dealing with inaccurate job size.
In FSPE, the phenomena we observe are analogous: job size over-estimation delays only the over-estimated job; under-estimation can result in jobs terminating in the virtual PS queue before than in the real system; this is impossible in absence of errors due to the dominance result introduced in Section 3.1. We therefore define late jobs in FSPE as those whose execution is completed in the virtual system but not yet in the real one and we notice that, analogously to SRPTE, also in FSPE late jobs can never be preempted by new ones, and they block the system until they are all completed.

Our Solution
Now that we have identified the issue with existing size-based scheduling policies, we propose a strategy to avoid it. Several alternatives are envisionable, including for example updating job size estimations if new information becomes available as work progresses; however, such a solution may not be always feasible, because it could introduce additional delays or due to limitations in terms of information or computational resources available to the scheduler.
We propose, instead, a solution that requires no additional job size estimation, based on the intuition that late jobs should not prevent executing other ones. This goal is achievable by performing simple modifications to preemptive size-based scheduling disciplines such as SRPT and FSP. The key property is that the scheduler takes corrective actions when one or more jobs are late, guaranteeing that -even when very large late jobs are being executed -newly arrived small jobs will get executed soon.
We conclude this section by showing our proposal, PSBS; it implements this idea while being efficient (O(log n) behavior) and allowing the usage of different weights to differentiate jobs.

Using PS and LAS for Late Jobs
From our analysis of Section 3.2, we understand that current size-based schedulers behave problematically when one or more jobs become late. Fortunately, it is possible to understand if jobs are late from the internal state of the scheduler: in SRPT, a job is late if its size is less than or equal to zero; in FSP, a job is late if it is completed in the virtual time but not in the real time.
How should the scheduler behave in case of late jobs? One possible solution could be to re-estimate the size of the late jobs and update their position in the queue (if necessary, by preempting them). While this solution seems appealing, it may introduce additional problems as discussed above. Instead, we consider a different, simpler approach, which does not involve new estimates -as we will show in Section 6, our solution provides almost optimal results, without re-estimating the job size.
The key idea of our proposal is that late jobs should not monopolize the system resources. The solution is to modify the scheduler such that it provides service to a set of jobs, which we call eligible jobs, rather than a single job at a time. In particular, we consider the following jobs as eligible: • For our amended version of SRPTE, all the late jobs, plus the non-late job with the highest-priority; • For our amended version of FSPE, only the late jobs.
The difference between the two cases is due to the fact that, in SRPTE, jobs can only become late while they are being served because the scheduler decreases the remaining processing time only for them; therefore, non-late jobs need a chance to be served. In FSPE, conversely, jobs become late depending on the simulated behavior of the virtual time, independently from which jobs are served in the real time.
We take into account two choices for scheduling eligible jobs: PS and LAS (see Section 2.1). PS divides resources evenly between all jobs, while LAS divides resources evenly between the job(s) that received the least amount of service until the current time.
The alternatives proposed so far lead to four scheduling policies that we evaluate experimentally in Section 6: 1. SRPTE+PS. Behaving as SRPTE as long as no jobs are late, switching to PS between all late jobs and the highest-priority non-late job; 2. SRPTE+LAS. As above, but using LAS instead of PS; 3. FSPE+PS. Behaving as FSPE as long as no jobs are late, switching to PS between all late jobs; 4. FSPE+LAS. As above, but using LAS instead of PS.
We point out that, in the absence of errors or just of size underestimations, jobs are guaranteed to be never late; this means that in such cases these scheduling policies will be equivalent to SRPT and FSP, respectively. For a more precise description, we point the interested reader to their implementation in our simulator. 1

PSBS
In Section 6.1 we show how the scheduling protocols we propose outperform, in most cases, both esisting size-based scheduling policies and size-oblivious ones such as PS and LAS. Betweeen the scheduling protocols just introduced, we point out that FSPE+PS is the only one that guarantees to avoid starvation: every job will eventually complete in the virtual time, and therefore will be scheduled in a PS fashion. Conversely, both SRPTE and LAS can starve large jobs if smaller ones are continuously submitted.
Due to this property and to the good performance we observe in the experiments of Section 6.2, we consider FSPE+PS to be a desirable policy. There are, however, a few shortcomings to this choice: first, this scheduler does not handle weights that can be used to differentiate jobs; second, its implementation is inefficient, requiring O(n) computation. Here, we propose PSBS, a generalization of FSPE+PS, which solves these problems, both allowing different job weights and having an efficient O(log n) implementation.

Job Weights
Neither FSP nor PS support job differentiation through job weights. In particular, FSP schedules jobs based on their completion time in a virtual time that simulates an environment using PS, which treats all running jobs equally.
To differentiate jobs in PSBS, we use Generalized Processor Sharing (GPS) [Kleinrock, 1976] in the place of PS, both in the virtual time and in the scheduling for late jobs. GPS is a generalization of PS whereby each job is given a weight, and resources are shared between processes proportionally to their weight. By assigning a different weight to jobs, we can therefore prioritize more important jobs. When all weights are the same, GPS is equivalent to PS; analogously, with no differences of weights the scheduling choices of PSBS are equivalent to those of FSPE+PS.

Implementation
FSP uses a virtual emulated system running a processor sharing (PS) discipline to keep track of the job completion order; FSP then schedules one job at a time following such an order. Every time a new job arrives, FSP needs to update the virtual remaining size of each job in the virtual emulated system, so that it can correctly compute the new job virtual finish times and the corresponding job completion order. Let n be the number of running jobs in the virtual emulated system: existing implementations of FSP [Dell'Amico et al., 2014;Friedman and Henderson, 2003] have O(n) complexity due to the job virtual remaining size update at each arrival.
In our implementation, we aim at reducing the complexity of the update procedure. Before showing the details of the algorithm, we discuss a simple example that helps to understand the main idea used to design our solution. Consider three jobs (J 1 , J 2 and J 3 ) with sizes s 1 = 10, s 2 = 5 and s 3 = 2 respectively, weights w 1 = w 2 = w 3 = 1, which arrive at times t = 0, t = 3 and t = 5 respectively. Figure 2 shows the evolution of the virtual emulated system, i.e., how the remaining virtual size decreases in the virtual time. For instance, when job J 3 arrives, since it will complete in the virtual time before jobs J 1 and J 2 , it will be executed immediately in the real system (job J 2 will be preempted). In order to compute the completion time, it is necessary to compute the exact virtual remaining size of the jobs currently in the system.
We instead introduce a new variable, which we call virtual lag g. The key idea is that we store, for each job i, a job virtual lag g i so that i completes in the virtual time when the virtual lag g = g i . We fulfill this property by updating g at a rate that depends on the number of jobs in the system: for each time unit in the virtual time, g increases by 1/w v , where w v is the sum of the weights w i of each job i running in the virtual emulated system.
Given a job i with weight w i and size s i that arrives at the system when the virtual lag g has a value g = x, the job virtual lag is given by g i = x + s i /w i . The job virtual lag g i is computed just once, when the job arrives, and it does not need to be updated when other jobs arrive. In fact, only the global virtual lag g needs to be updated according to the number of jobs in the system. Figure 2 shows the job virtual lag computed when virtual time Remaining virtual size s 1 = 10 g 1 = 10 s 2 = 5 g 2 = 8 s 3 = 2 g 3 = 6 Figure 2: Example of virtual time t and virtual lag g, used for sorting jobs.
each jobs arrives (value of g i below s i ) and the value of the global virtual lag g (below the virtual time t). Indeed, each job i completes when g = g i , but the only variable we update at each job arrival is g, leaving untouched the values g i of the job virtual lags. For instance, when job J 3 arrives, the virtual lag g has value 4, therefore the job virtual lag will be g 3 = 4 + 2 (since the size and the weights of job J 3 are s 3 = 2 and w 3 = 1). It takes 6 time units (in the virtual time) to complete job J 3 , which corresponds to 2 time units in the virtual lag. It is simple to show that, given any positive value for s i and w i , the order at which jobs complete in the virtual time and in the virtual lag is exactly the same. Therefore, at each job arrival, it is sufficient to update the global virtual lag g, compute the job virtual lag g i and store the object in a priority queue, where the order is kept according to the values of g i . The overall complexity is dominated by the maintenance of the priority queue, which is O(log n), since it is not necessary to update the virtual remaining size of all jobs in the system to compute the completion order.
The implementation of our solution, shown in Algorithm 1 on the next page, follows the nomenclature used in the original description of FSP [Friedman and Henderson, 2003, Section 4.4]. We remark that, in the absence of errors and when all job weights are the same, PSBS is equivalent to FSP: therefore, our implementation of PSBS is also the first O(log n) implementation of FSP.
Computation is triggered by three events: if a job i of weight w i and estimated size s i arrives at timet, JobArrival(t, i, s i , w i ) is called; when a job i completes, Real-JobCompletion(i) is called; finally, when a job completes in virtual time at timet, VirtualJobCompletion(t) is called (NextVirtualCompletionTime is used to discover when to call VirtualJobCompletion). After each event, the ProcessJob procedure is called to determine the new set of scheduled jobs: its output is a set of (j, s) pairs where j is the ALGORITHM 1: PSBS. """Set up the scheduler state.
O and E contain (i, gi, wi) tuples: i is the job id, gi is the value of g at which the job completes in the virtual time and wi is the weight. They are sorted by gi. """ def Init: if L is not empty: # we were scheduling late jobs job identifier and s is the fraction of system resources allocated to it. As auxiliary data structures, we keep two priority queues, O and E. O stores jobs that are running both in the real time and in the virtual time, while E stores "early" jobs that are still running in the virtual time but are completed in the real time. For each job i, we store in O or E an immutable tuple (i, g i , w i ) containing respectively the job id, the virtual lag g i and the weight. We use binary min-heaps to represent O and E, using the g i values as ordering key: binary heaps are efficient data structures offering worst-case O(log n) "push" and "pop" operations, O(1) lookup of the first value and eassentially optimal memory efficiency, by virtue of being an implicit data structure requiring no pointers [Cormen et al., 2001]. In addition, the push operation has of O(1) complexity on average [Porter and Simon, 1975].
The state of the scheduler is completed by a mapping L from the identifiers of late jobs to their weight, a counter t representing the virtual time, and two variables w v and w L representing the sum of weights for jobs that are respectively active in the virtual time and late. Some additional bookkeeping, not included here for simplicity, would be needed to handle jobs that complete even when they are not scheduled (e.g., because of error conditions or after being killed): we refer the interested reader to the implementation in our simulator. The ProcessJob procedure, when L is not empty, has O(|L|) complexity due to the fact that the output itself has size L. This is however very unlikely to be a limitation in practical cases, since real-world implementations of schedulers allocate resources one by one in discrete slots: schedulers such as PS or GPS are abstractions of mechanisms such as round-robin or max-min fair schedulers, which can be implemented efficiently; a real-world implementation of PSBS would adopt similar strategy to mimick the GPS-like resource sharing when L is not empty. We also note that, when there are no job size estimation errors and PSBS is used to implement FSP, L is guaranteed to always be empty and therefore ProcessJob will have O(1) complexity.
As we have seen, with the exclusion of ProcessJob as discussed above, all the procedures of the scheduler have at most O(log n) computational complexity. Coupled with the fact that O(log n) operations have low constant factors because they are implemented on binary heaps, which are very efficient data structures, we believe that these performance guarantees are sufficient for a very large set of practical situations: for ex-ample, CFS -the current Linux scheduler -has O(log n) complexity since it uses a tree structure [Tim Jones, 2009].

Evaluation Methodology
Understanding size-based scheduling systems when there are estimation errors is not a simple task. The complexity of the system makes an analytical study feasible only if strong assumptions, such as a bounded error [Wierman and Nuyens, 2008], are imposed. Moreover, to the best of our knowledge, the only analytical result known for FSP (without estimation errors) is its dominance over PS, making analytical comparisons between SRPTE-based and FSPE-based scheduling policies even more difficult.
For these reasons, we evaluate our proposed scheduling policies through simulation. The simulative approach is extremely flexible, allowing to take into account several parameters -distribution of the arrival times, of the job sizes, of the errors. Previous simulative studies (e.g., [Lu et al., 2004]) have focused on a subset of these parameters, and in some cases they have used real traces. In our work, we developed a tool that is able to both reproduce real traces and generate synthetic ones. Moreover, thanks to the efficiency of the implementation, we were able to run an extensive evaluation campaign, exploring a large parameter space. For these reasons, we are able to provide a broad view of the applicability of size-based scheduling policies, and show the benefits and the robustness of our solution with respect to the existing ones.

Scheduling Policies Under Evaluation
In this work, we take into account different scheduling policies, both size-based and size-oblivious. For the size-based disciplines, we consider SRPT as a reference for its optimality with respect to the MST. When introducing the errors, we evaluate SRPTE, FSPE and our proposals described in Section 4.
As size-oblivious policies, we have implemented the First In, First Out (FIFO) and Processor Sharing (PS) disciplines, along with GPS, the generalization of PS with weights [Kleinrock, 1976]. These policies are the default disciplines used in many scheduling systems -e.g., the default scheduler in Hadoop [White, 2009] implements a FIFO policy, while Hadoop's FAIR scheduler is inspired by PS; the Apache web server delegates scheduling to the Linux kernel, which in turn implements a PS-like strategy [Schroeder and Harchol-Balter, 2006]. Since PS scheduling divides evenly the resources among running jobs, it is generally considered as a reference for its fairness (see the next section on the performance metrics). Finally, we consider also the Least Attained Service (LAS) [Rai et al., 2003] policy. LAS scheduling is a preemptive policy that gives service to the job that has received the least service, sharing it equally in a PS mode in case of ties. LAS scheduling has been designed considering the case of heavy-tailed job size distributions, where a large percentage of the total work performed in the system is due to few very large jobs, since it gives higher priority to small jobs than what PS would do.

Parameter Explanation
Default sigma σ in the log-normal error distribution 0.5 shape shape for Weibull job size distribution 0.25 timeshape shape for Weibull inter-arrival time 1 njobs number of jobs in a workload 10,000 load system load 0.9 Table 1: Simulation parameters.

Performance Metrics
We evaluate scheduling policies according to two main aspects: mean sojourn time (MST) and fairness. Sojourn time is the time that passes between the moment a job is submitted and when it completes; such a metric is widely used in the scheduling literature.
The definition of fairness is more elusive: in his survey on the topic, Wierman [2011] affirms that "fairness is an amorphous concept that is nearly impossible to define in a universal way". When the job size distribution is skewed, it is intuitively unfair to expect similar sojourn times between very small jobs and much larger ones; a common approach is to consider slowdown, i.e. the ratio between a job's sojourn time and its size, according to the intuition that the waiting time for a job should be somewhat proportional to its size. In this work we focus on the per-job slowdown, in order to check that as few jobs as possible experience "unfair" high slowdown values; moreover, in accordance with the definition by Wierman [2007] we also evaluate conditional slowdown, which evaluates the expected slowdown given a job size, verifying whether jobs of a particular size experience an "unfair" high expected slowdown value.

Parameter Settings
We empirically evaluate scheduling policies in a wide spectrum of cases. Table 1 synthetizes the input parameters of our simulator; they are discussed in the following.
Job Size Distribution Job sizes are generated according to a Weibull distribution, which allows us to evaluate both heavy-tailed and light-tailed job size distributions. The shape parameter allows to interpolate between heavy-tailed distributions (shape < 1), the exponential distribution (shape= 1), the Raleigh distribution (shape = 2) and light-tailed distributions centered around the '1' value (shape > 2). We set the scale parameter of the distribution to ensure that its mean is 1.
Since scheduling problems have been generally analyzed on heavy-tailed workloads with job sizes using distributions such as Pareto, we consider a default heavy-tailed case of shape = 0.25. In our experiments, we vary the shape parameter between a very skewed distribution with shape = 0.125 and a light-tailed distribution with shape = 4.

Size Error Distribution
We consider log-normally distributed error values. A job having size s will be estimated asŝ = sX, where X is a random variable with distribution Log-N (0, σ 2 ). (1) This choice satisfies two properties: first, since error is multiplicative, the absolute errorŝ−s is proportional to the job size s; second, under-estimation and over-estimation are equally likely, and for any σ and any factor k > 1 the (non-zero) probability of underestimatingŝ ≤ s k is the same of over-estimatingŝ ≥ ks. This choice also is substanciated by empirical results: in our implementation of the HFSP scheduler for Hadoop [Pastorelli et al., 2013], we found that the empirical error distribution was indeed fitting a log-normal distribution.
The sigma parameter controls σ in Equation 1, with a default -used if no other information is given -of 0.5; with this value, the median factor k reflecting relative error is 1.40. In our experiments, we let sigma vary between 0.125 (median k is 1.088) and 4 (median k is 14.85).
It is possible to compute the correlation between the estimated and real size as σ varies. In particular, when sigma is equal to 0.5, 1.0, 2.0 and 4.0, the correlation coefficient is equal to 0.9, 0.6, 0.15 and 0.05 respectively.
The mean of this distribution is always larger than 1, and, as sigma grows, the system is biased towards overestimating the aggregate size of several jobs, limiting the underestimation problems that our proposals are designed to solve. Even in this setting, the results in Section 6 show that the improvements we obtain are still significant.

Job Arrival Time Distribution
For the job inter-arrival time distribution, we use again a Weibull distribution for its flexibility to model heavy-tailed, memoryless and lighttailed distributions. We set the default of its shape parameter (timeshape) to 1, corresponding to "standard" exponentially distributed arrivals. Also here, timeshape varies between 0.125 (very bursty arrivals separated by long intervals) and 4 (regular arrivals).

Other Parameters
The load parameter is the mean arrival rate divided by the mean service rate. As default value, we use the same value of 0.9 used by Lu et al. [2004]; in our experiments we let the load parameter vary between 0.5 and 0.999.
The number of jobs (njobs) in each simulation round is 10,000. For each experiment, we perform at least 30 repetitions, and we compute the confidence interval for a confidence level of 95%. For very heavy-tailed job size distributions (shape ≤ 0.25), results are very variable and therefore, in order to obtain stable averages, we performed hundreds and/or thousands of experiment runs, at least until the confidence levels have reached the 5% of the estimated values.

Simulator Implementation Details
Our simulator is available under the Apache V2 license. 3 It has been conceived with ease of prototyping in mind: for example, our implementation of FSPE as described in Section 3 requires 53 lines of code. Workloads can be both replayed from real traces and generated synthetically.
The simulator has been written with a focus on computational efficiency. It is implemented using an event-based paradigm, and we used efficient data structures based on B-trees. 4 As a result of these choices, a "default" workload of 10,000 jobs is simulated in around half a second, while using a single core in our 2011 laptop with an Intel T7700 CPU. We use IEEE 754 double-precision floating point values to represent time and job sizes.

Experimental Results
We now proceed to an extensive report of our experimental findings. We first provide a high-level view showing that our proposals outperform PS, excepting only extreme cases of both error and job skew (Section 6.1); we then proceed to a more in-depth comparison of our proposals, to validate our choice of using FSPE+PS as a base for PSBS (Section 6.2). We then evaluate the performance of PSBS against existing schedulers, while varying the two parameters that most influence scheduler performance: shape (Section 6.3) and sigma (Section 6.4). We proceed to show that PSBS handles jobs fairly (Section 6.5) and that job weights are handled correctly (Section 6.6); we conclude our analysis on synthetic workloads by showing that our results hold even while varying settings over the parameter space (Section 6.7). We conclude our analysis by comparing PSBS to existing schedulers on real workloads extracted from Hadoop logs and an HTTP cache (Section 6.8).
For all the results shown in the following, the parameters whose values are not explicitly stated take the default values shown in Table 1 on page 14. For the readability of the figures, we do not show the confidence intervals: for all the points, in fact, we have performed a number of runs sufficiently high to obtain a confidence interval smaller than 5% of the estimated value. Where not otherwise stated, all the w i parameters representing the weight of each job i have always been set to 1.

Mean Sojourn Time Against PS
We begin our analysis by comparing the size-based scheduling policies, using PS as a baseline because PS and its variants are the most widely used set of scheduling policies in real systems. In Figure 3 on the following page we plot the value of the MST obtained using SRPTE, FSPE and the four alternatives we propose in Section 4.1, normalizing it against the MST of PS. We vary the sigma and shape parameters influencing respectively job size distribution and error rate; we will see that these two parameters are the ones that influence performance the most. Values lower than one (below the dashed line in the plot) represent regions where size-based schedulers perform better than PS.
In accordance to intuition and to what is known from the literature, we observe that the performance of size-based scheduling policies depends on the accuracy of job size  estimation: as sigma grows, performance suffers. In addition, from Figures 3a and 3d, we observe a new phenomenon: job size distribution impacts performance even more than size estimation error. On the one hand, we notice that large areas of the plots (shape > 0.5) are almost insensitive to estimation errors; on the other hand, we see that MST becomes very large as job size skew grows (shape < 0.25). We attribute this latter phenomenon to the fact that, as we highlight in Section 3, late jobs whose estimated remaining (virtual) size reaches zero are never preempted. If a large job is under-estimated and becomes late with respect to its estimation, small jobs will have to wait for it to finish in order to be served.
As we see in Figures 3b, 3c, 3e and 3f, our proposals outperform PS in a large class of heavy-tailed workloads where SRPTE and FSPE suffer. The net result is that the size-based policies we propose are outperformed by PS only in extreme cases where both the job size distribution is extremely skewed and job size estimation is very imprecise.
It may appear surprising that, when job size skew is not extreme, size-based scheduling can outperform PS even when size estimation is very imprecise: even a small correlation between job size and its estimation can direct the scheduler towards choices that are beneficial on aggregate. In fact, as we see more in detail in the following (Section 6.3), sub-optimal scheduling choices become less penalized as the job size skew diminishes.

Comparing Our Proposals
How do the schedulers we proposed in Section 4.1 compare? In Figure 4 on the previous page we delve in the detail by examining the empirical cumulative distribution function (ECDF) of the slowdown for all jobs we simulate while varying the shape parameter (sigma maintains its default value of 0.5); we plot the results for PS as a reference and observe that the staircase-like pattern observable in Figure 4a is a clustering around integer values obtained if a small job gets submitted while n larger ones are running.
We observe that, in general, our proposals pay off: for all values of shape considered, the slowdown distribution of our proposals is well lower than the one of PS. We also observe a difference between the schedulers based on SRPTE and those based on FSPE: a noticeably larger number of jobs experience an optimal slowdown of 1 when using a scheduler based on FSPE. This is because, when using FSPE-based scheduling policies, the number of jobs that are eligible for PS-or LAS-based scheduling is higher: only late jobs are eligible to be scheduled, unlike what happens in SRPTE-based policies; as a consequence, several small jobs suffer in SRPTE-based policies because they are preempted too aggressively. This confirms the soundness of the design policy we adopted in Section 4.1: minimizing the number of eligible jobs for PS-or LAS-based scheduling. Figure 4 shows that even allowing to schedule a single non-late jobs can hurt performance.
Since the number of late jobs is generally small, differences in scheduling between FSPE+PS and FSPE+LAS are rare. This is confirmed by noticing that the lines for the two schedulers in Figure 4 are essentially analogous; we conclude that FSPE+PS and FSPE+LAS have essentially analogous performance. This fact and the property that FSPE+PS avoids starvation, as noted in Section 4.2, motivated us to develop PSBS as a generalization of FSPE+PS.

Impact of Shape
After validating the choice of implementing PSBS as a generalization of FSPE+PS, we now examine how it performs when compared to the optimal MST that SRPT obtains. In the following Figures, we show the ratio between the MST obtained with the scheduling policies we implemented and the optimal one of SRPT, while fixing sigma to its default value of 0.5.
From Figure 5 on the preceding page, we see that the shape parameter is fundamental for evaluating scheduler performance. We notice that PSBS has almost optimal performance for all shape values considered, while SRPTE and FSPE perform poorly for highly skewed workloads. Regarding non size-based policies, PS is outperformed by LAS for heavy-tailed workloads (shape < 1) and by FIFO for light-tailed ones having shape > 1; PS provides a reasonable trade-off when the job size distribution is unknown. When the job size distribution is exponential (shape = 1), non size-based scheduling policies perform analogously; this is a result which has been proven analytically (see e.g. the work by Harchol-Balter [2009] and the references therein). It is interesting to consider the case of FIFO: in it, jobs are scheduled in series, and the priority between jobs is not correlated with job size: indeed, the MST of FIFO is equivalent to the one of a random scheduler executing jobs in series [Klugman et al., 2012]. FIFO can be therefore seen as the limit case for a size-based scheduler such as FSPE or SRPTE when estimations carry no information at all about job sizes; the fact that errors become less critical as skew diminishes can be therefore explained with the similar patterns observed for FIFO.

Impact of Sigma
The shape of the job size distribution is fundamental in determining the behavior of scheduling algorithms, and heavy-tailed job size distributions are those in which the behavior of size-based scheduling differs noticeably. Because of this, and since heavytailed workloads are central in the literature on scheduling, we focus on those.
In Figure 6 on the next page, we show the impact of the sigma parameter representing error for three heavily skewed workloads. In all three plots, the values for FIFO fall outside of the plot. These plots demonstrate that PSBS is robust with respect to errors in all the three cases we consider, while SRPTE and FSPE suffer as the skew between job sizes grows. In all three cases, PSBS performs better than PS as long as sigma is lower than 2: this corresponds to lax bounds on size estimation quality, requiring a correlation coefficient between job size and its estimate of 0.15 or more.
In all three plots, PSBS performs better than SRPTE; the difference between PSBS and FSPE, instead, becomes discernible only for shape < 0.25. We explain this difference by noting that, when several jobs are in the queue, size reduction in the virtual queue of FSPE is slow: this leads to less jobs being late and therefore non preemptable. As the distribution becomes more heavy-tailed, more jobs become late in FSPE and differences between FSPE and PSBS become significant, reaching differences of even around one order of magnitude.
In particular in Figure 6b, there are areas (0.5 < sigma < 2) in which increasing errors  decreases (slightly) the MST of FSPE. This counterintuitive phenomenon is explained by the characteristics of the error distribution: the mean of the log-normal distribution grows as sigma grows, therefore the aggregate amount of work for a set of several jobs is more likely to be over-estimated; this reduces the likelihood that several jobs at once become late and therefore non-preemptable. In other words, FSPE works better with estimation means that tend to over-estimate job size; however, it is always better to use PSBS, which provides a more reliable and performant solution to the same problem.

Fairness
We now consider the topic of fairness, intending here -as discussed in Section 5.2 -that jobs' running time should be proportional to their size, and therefore slowdowns should not be very large.
Conditional Slowdown To better understand the reason for the unfairness of FIFO, SRPTE and FSPE, in Figure 7 we evaluate mean conditional slowdown, comparing job size with the average slowdown (job sojourn time divided by job size) obtained at that size using our default simulation parameters. The figure has been obtained by sorting jobs by size and binning them in 100 equally sized classes of jobs with similar size; points plotted are obtained by averaging job size and slowdown in each of the 100 classes. The almost parallel lines of FIFO, SRPTE and FSPE for smaller jobs are explained by the fact that, below a certain size, job sojourn time is essentially independent from job size: indeed, it depends on the total size of older (for FIFO) or late (for SRPTE and FSPE) jobs at submission time.
We confirm experimentally the fact that the expected slowdown in PS is constant, irrespectively of job size [Wierman, 2007]; PSBS and LAS, on the other hand, have close to optimal slowdown for small jobs. The better MST of PSBS is instead due to better performance for larger jobs, which are more penalized in LAS. Per-Job Slowdown The results we have shown testify that, for PSBS and similarly to LAS, slowdown values are homogeneous across classes of job sizes: neither small nor big jobs are penalized when using PSBS. This is a desirable result, but the reported results are still averages: in order to ensure that sojourn time is commensurate to size for all jobs, we need to investigate the per-job slowdown distribution.
In Figure 8, we plot the CDF of per-job slowdown for our default simulator parameters. By serving efficiently smaller jobs, all size-based scheduling techniques and LAS manage to obtain an optimal slowdown of 1 for the majority of jobs. However, some jobs experience very high slowdown values: jobs with a slowdown larger than 100 are around 1% for FSPE and around 8% for SRPTE.
PS, LAS, and PSBS perform well in terms of fairness, with no jobs experiencing slowdown higher than 100 in our experiment runs. 5 While PS is generally considered the reference for a "fair" scheduler, it obtains slightly better slowdown than LAS and PSBS only for the most extreme cases, while being outperformed for a large majority of the jobs.

Job Weights
We now consider how PSBS handles job weights. We consider workloads generated with all the default values shown in Table 1. We randomly assign jobs to different weight classes numbered from 1 to 5 with uniform probability: a job i in weight class c i has weight w i = 1/c β i , where β ≥ 0 is a parameter that allows us to tune how much we want to skew scheduling towards favoring high-weight jobs. A β = 0 value corresponds to uniform weights, w i = 1 for each job; as β grows, job weights differentiate so that more and more resources are assigned to high-weight jobs.
In Figure 9 on the following page, we plot the mean sojourn time that jobs in each weight class experience. Jobs have a mean size of 1: therefore, the best MST obtainable would be 1, which corresponds to the bottom of the graph. For comparison, we compare the results of PSBS with those obtained by generalized processor sharing (GPS) while using the same weights.
For workloads ranging between heavily skewed (shape = 0.25) to close to uniform (shape = 4), PSBS outperforms GPS. Obviously, β = 0 leads to uniform MST between weight classes; raising the values of β improves the performance of high-weight jobs to the detriment of low-weight ones. When β = 2, the MST of jobs in class 1 is already very close to the optimal value of 1; we do not consider values of β > 2 because it would impose performance losses to low-weight jobs without significant benefits to high-weight ones. It is interesting to point out that the trade-off due to the choice of β is not uniform across values of shape: when the workload is close to uniform (shape = 4), improvements in sojourn times for high-weight jobs are quantitatively similar to the losses paid by lowweight ones; this is because high-weight jobs are likely to preempt low-weight ones with similar sizes. Conversely, with heavily skewed workloads (shape = 0.25) sojourn time improvements for high-weight jobs are smaller than losses for low-weight ones: this is because, in skewed workloads, large high-weight jobs are likely to preempt small lowweight ones: this results in small improvements in sojourn time for the high-weight jobs, counterbalanced by large losses for the low-weight ones.

Other Settings
Until here, we focused on the sigma and shape parameters, because they are the ones that we found out to have the most influence on scheduler behavior. We now examine the impact on schedulers of other settings that deviate from our default ones.
Pareto Job Size Distribution In the literature, workloads are often generated using the Pareto distribution. To help comparing our results to the literature, in Figure 10 we show results for job sizes having a Pareto distribution, using x m = 0 and α = {1, 2}. The results we observe for the Weibull distribution are still qualitatively valid for the Pareto distribution; the value of α = 1 is roughly comparable to a shape of 0.15 for the Weibull distribution, while α = 2 is comparable to a shape of around 0.5, where the three size-based disciplines we take into account still have similar performance.   Impact of Other Parameters In Figure 11, we show the impact of varying load and timeshape, while keeping sigma and shape at their default values. Figure 11a shows that performance of size-based scheduling protocols is not heavily impacted by load, as the ratio between the MST obtained and the optimal one remains roughly constant (note that the graph shows a ratio, and not the absolute values which increase as the load increases); conversely, size-oblivious schedulers such as PS and LAS deviate more from optimal as the load grows. Figure 11b shows the impact of changing the timeshape parameter: with low values of timeshape, job submissions are bursty and separated by long pauses; with high values job submissions are more evenly spaced. We note that size-based scheduling policies respond very well to bursty submissions where several jobs are submitted at once: in this case, adopting a size-based policy that focuses all the system resources on the smallest jobs pays best; as the intervals between jobs become more regular, SRPTE and FSPE become slightly less performant; PSBS remains close to optimal.
PSBS and the Parameter Space With Figure 12, we show that the results of Figure 11 generalize to other parameter choices: by letting shape vary together with load, timeshape and njobs, we notice that FSPE+PS always performs better than PS. The V-shaped pattern, where the difference in performance between the two schedulers is larger for "central" values of the shape parameter is essentially due to the fact that, as we can see in Figure 5 on page 19, PS performs closer to optimal for extreme values of the shape parameter.

Real Workloads
We now consider two real workloads in order to confirm that the phenomena we observed in our experiments are not an artifact of the synthetic traces that we generated, and that they indeed apply in realistic cases. From the traces we obtain two data points per job: submission time and job size. In this way, we move away from the assumptions of the G/G/1 model, and we provide results that can account for more general cases where periodic patterns and correlation between job size and submission times are present.
Hadoop at Facebook We consider a trace from a Facebook Hadoop cluster in 2010, covering one day of job submissions. The trace has been collected and analized by Chen et al. [2012]; it is comprised of 24,443 jobs and it is available online. 6 For the purposes of this work, we consider the job size as the number of bytes handled by each job (summing input, intermediate output and final output): the mean size is 76.1 GiB, and the largest job processes 85.2 TiB. To understand the shape of the tail for the job size distribution, in Figure 13 we plot the complementary CDF (CCDF) of job sizes (normalized against the mean); the distribution is heavy-tailed and the largest jobs are around 3 orders of magnitude larger than the average size. For homogeneity with the previous results, we set the processing speed of the simulated system (in bytes per second) in order to obtain a load (total size of the submitted jobs divided by total length of the submission schedule) of 0.9.
In Figure 14 on the next page, we show MST, normalized against optimal MST, while varying the error rate. We remark that these results are very similar to those that we observe from Figure 6 on page 21: also in this case, FSPE and PSBS perform well even when job size estimation errors are far from negligible. These results show that this workload is well represented by our synthetic workloads, when shape is around 0.25.
We performed more experiments on these traces; extensive results are available in a technical report [Dell'Amico, 2013].
Web Cache IRCache 7 is a research project for web caching; traces from the caches are freely available. We performed our experiments on a one-day trace of a server from 2007 totaling 206,914 requests; 8 the mean request size in the traces is 14.6KiB, while the maximum request size is 174 MiB. In Figure 13 on the previous page we show the CCDF of job size; as compared to the Facebook trace analyzed previously, the workload is more heavily tailed: the biggest requests are four orders of magnitude larger than the mean. As before, we set the simulated system processing speed in bytes per second to obtain a load of 0.9. In Figure 15 on the preceding page we plot the evolution of MST as the sigma parameter controlling error grows. Since the job size distribution is more heavily tailed, sojourn times are more influenced by job size estimation errors (notice the logarithmic scale on the y axis), confirming the results we have from Figure 3 on page 17. The performance of FSPE does not worsen monotonically as error grows, but rather becomes better for 0.5 < sigma < 1; this is a phenomenon that we also observe -albeit to a lesser extent -for synthetic workloads in Figure 6b on page 21 and for the Facebook workload in Figure 14 on the previous page. The explanation that we provided in Section 6.4 applies: since the mean of the log-normal distribution grows as sigma grows, the aggregate amount of work for a given set of jobs is likely to be over-estimated in total, reducing the likelihood that several jobs at once become late and therefore non-preemptable. Also in this case, we still remark that PSBS consistently outperforms FSPE.

Conclusion
This work shows that size-based scheduling is an applicable and performant solution in a wide variety of situations where job size is known approximately rather than exactly. The limitations shown by previous work are, in a large part, solved by the approach we took in PSBS; analogous measures can be taken in other preemtpive size-based scheduling disciplines.
PSBS is a generalization of FSP, and it thus behaves equivalently to it in the absence of errors, thereby maintaining all its desirable properties such as dominance over PS; to the best of our knowledge, PSBS is also the first O(log n) implementation of FSP.
PSBS also solves a fairness problem: while FSPE and SRPTE penalize small jobs and results in slowdown values which are not proportionate to their size, PSBS has an optimal slowdown equal to 1 for most small jobs.
We maintain that, thanks to its efficient implementation, solid performance in case of estimation errors, and support for job weights, PSBS is a practical size-based policy that can guide the design of schedulers in real, complex systems. We argue that, if even rough estimates can be produced to estimate job sizes, it is worthy to try size-based scheduling: our proposal, PSBS, is reasonably easy to implement and provides close to optimal response times and good fairness in all but the most extreme of cases.
We released our simulator as free software; it can be reused for: (i) reproducing our experimental results; (ii) prototype new scheduling algorithms; (iii) predict system behavior in particular cases, by replaying traces.