processor-sharing · research · also egalitarian processor sharing, M/G/1-PS

Processor sharing

Processor sharing is an idealized discipline that divides a server's capacity equally among all jobs currently present.

Related Observatory article: Read on hesela.com

With n jobs present, each gets 1/n of the server. The ordinary model has constant total capacity and no switching cost or interruptions. This is an idealization, not a claim that an SSD continuously divides its resources this way. [1]

For independent Poisson arrivals, iid positive service requirements S independent of arrivals, unlimited admission and no abandonment, let rho = lambda E[S] < 1. In stationarity, E[T | S=x] = x/(1-rho), with x measured as processing time at full capacity. Averaging gives E[T] = E[S]/(1-rho). [2]

Thus at fixed arrival rate and mean service requirement, this mean is insensitive to the rest of the service distribution. Equal conditional mean slowdown is not equal realized slowdown, a tail percentile or a deadline guarantee; conditional variance requires separate analysis. [3]

Hesela's constructed 1 ms mean-service example at 200 requests/s gives 1.25 ms mean response under ideal PS for both service distributions. FCFS gives 1.125 ms for constant service and 4.21875 ms for the variable mixture, so PS does not always improve the mean. These are exact formula evaluations, not measurements. [4]

The stationary mean conditions only on S=x, averaging over arrival states; it is not a prediction conditioned on the jobs currently present. For a separate ideal PS batch with no future arrivals, T = x + sum(min(x, r_i)). A 1 ms tagged job with two competitors totaling 2 ms finishes in 2.25 ms for residuals (0.25, 1.75) ms, but 3 ms for (1, 1) ms. Equal count and total work are insufficient. These constructed batches are not stationary means or measurements. [5] [4]

Relations

related
Service time, Pollaczek-Khinchine mean formula, Slowdown fairness

Citations

  1. Nunez Queija. Sojourn Times in a Processor Sharing Queue with Service Interruptions. CWI PNA-R9807 (1998), introduction, pp.1-2. (accessed 2026-11-20)
  2. Wierman, Bansal and Harchol-Balter. M/GI/1/FB and M/GI/1/PS response times. Operations Research Letters 32 (2004), pp.73-74; DOI 10.1016/S0167-6377(03)00061-0. (accessed 2026-11-20)
  3. Wierman and Harchol-Balter. Classifying Scheduling Policies with Respect to Higher Moments of Conditional Response Time. SIGMETRICS 2005, sections 2-3. (accessed 2026-11-20)
  4. Hesela: exact PS/FCFS comparison with rational inputs, assumptions and tests. (accessed 2026-11-20)
  5. Ward and Whitt. Predicting Response Times in Processor-Sharing Queues. Author manuscript, sections 1.2-1.3; equations (1.6), (1.36) and (1.38). (accessed 2026-11-20)
Sources & caveats
  • Primary-source synthesis and exact arithmetic using explicitly invented inputs; no device experiment or latency-distribution claim.
  • Conditional mean slowdown is per job size in a stationary model, distinct from FLIN's flow-level ratio of means.

JSON: /data/terms/processor-sharing.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Processor sharing. Hesela. 2026-11-20. https://hesela.dev/terms/processor-sharing/