Processor sharing

Processor sharing is a service policy where the customers, clients or jobs are all served simultaneously, each receiving an equal fraction of the service capacity available. In such a system all jobs start service immediately (there is no queueing).

The processor sharing algorithm "emerged as an idealisation of round-robin scheduling algorithms in time-shared computer systems."^[1]^[2]

Queueing theory

A single server queue operating subject to Poisson arrivals (such as an M/M/1 queue or M/G/1 queue) with a processor sharing discipline has a geometric stationary distribution.^[1]

The sojourn time jobs experience has no closed form solution, even in an M/M/1 queue.^[3]

Discriminatory processor sharing

Discriminatory processor sharing is a multi-class adaptation of the policy where jobs are assigned classes and each class assigned a positive weighting factor. Service capacity is split between all the jobs present according to their service weights.^[4] If all the class weights are equal then DPS is the same as PS.^[1]

Generalized processor sharing

Generalized processor sharing is a mult-class adaptation of the policy which shares service capacity according to positive weight factors to all non-empty job classes at the node, irrespective of the number of jobs of each class present. Often it is assumed that the jobs within a class form a queue and that queue is served on a first-come, first-served basis, but this assumption is not necessary for many GPS applications.^[1]

In processor scheduling, generalized processor sharing is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness."^[5]

References

^ ^a ^b ^c ^d Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/1243401.1243409, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/1243401.1243409 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/321386.321388, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/321386.321388 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/s11134-006-7585-9, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/s11134-006-7585-9 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/s11134-006-7586-8, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/s11134-006-7586-8 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/1594835.1504188, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/1594835.1504188 instead.

[aalto-1] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/1243401.1243409, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/1243401.1243409 instead.

[2] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/321386.321388, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/321386.321388 instead.

[3] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/s11134-006-7585-9, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/s11134-006-7585-9 instead.

[4] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/s11134-006-7586-8, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/s11134-006-7586-8 instead.

[5] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/1594835.1504188, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/1594835.1504188 instead.

[1]

[2]

[3]

[4]

[5]

v t e Queueing theory
Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue
Arrival processes	Poisson point process Markovian arrival process Rational arrival process
Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network
Service policies	FIFO LIFO Processor sharing Round-robin Shortest job next Shortest remaining time
Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method
Limit theorems	Fluid limit Mean-field theory Heavy traffic approximation Reflected Brownian motion
Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue
Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering
Category