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] The model was first proposed by Leonard Kleinrock and called priority processor sharing.[2]
Generalized processor sharing
Generalized processor sharing is a multi-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.1243409instead. - ^ a b 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.321388instead. - ^ 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-9instead. - ^ 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-8instead. - ^ 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.1504188instead.
| Single queueing nodes | |
|---|---|
| Arrival processes | |
| Queueing networks | |
| Service policies | |
| Key concepts | |
| Limit theorems | |
| Extensions | |
| Information systems | |
