View source for Processor sharing

{{EngvarB|date=January 2019}}
{{Short description|Form of resource sharing for tasks in computing}}
'''Processor sharing''' or '''egalitarian processor sharing''' is a service [[Policy|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|round-robin]] scheduling algorithms in time-shared computer systems".<ref name="aalto">{{Cite journal | last1 = Aalto | first1 = S. | last2 = Ayesta | first2 = U. | last3 = Borst | first3 = S. | last4 = Misra | first4 = V. | last5 = Núñez-Queija | first5 = R. | title = Beyond processor sharing | doi = 10.1145/1243401.1243409 | journal = ACM SIGMETRICS Performance Evaluation Review | volume = 34 | issue = 4 | pages = 36 | year = 2007 | url = http://dna-pubs.cs.columbia.edu/citation/paperfile/142/beyondps-v13.pdf}}</ref><ref name="kleinrock1967">{{Cite journal | last1 = Kleinrock | first1 = L. |  title = Time-shared Systems: A theoretical treatment | doi = 10.1145/321386.321388 | journal = [[Journal of the ACM]]| volume = 14 | issue = 2 | pages = 242–261 | year = 1967 | url = http://www.lk.cs.ucla.edu/data/files/Kleinrock/Time-Shared%20Systems%20A%20Theoretical%20Treatment.pdf| citeseerx = 10.1.1.74.3945 }}</ref>

==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 distribution|geometric]] stationary distribution.<ref name="aalto" />

The sojourn time jobs experience has no closed form solution, even in an M/M/1 queue.<ref>{{Cite journal | last1 = Borst | first1 = S. | last2 = Núñez-Queija | first2 = R. | last3 = Zwart | first3 = B. | title = Sojourn time asymptotics in processor-sharing queues | doi = 10.1007/s11134-006-7585-9 | journal = [[Queueing Systems]]| volume = 53 | issue = 1–2 | pages = 31–51 | year = 2006 | url = http://alexandria.tue.nl/openaccess/Metis209591.pdf}}</ref>

==Generalized processor sharing==
{{main|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.<ref name="aalto" />

In [[Scheduling (computing)|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."<ref>{{Cite journal | last1 = Li | first1 = T. | last2 = Baumberger | first2 = D. | last3 = Hahn | first3 = S. | doi = 10.1145/1594835.1504188 | title = Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin | journal = ACM SIGPLAN Notices | volume = 44 | issue = 4 | pages = 65 | year = 2009 | url = http://happyli.org/tongli/papers/dwrr.pdf | citeseerx = 10.1.1.567.2170 }}</ref>

==Multilevel processor sharing==

In multilevel processor sharing a finite set of thresholds are defined and jobs partitioned according to how much service they have received. The lowest level (containing jobs which have received the least service) has the highest priority and higher levels monotonically decreasing priorities. Within each level an internal discipline is used.<ref name="aalto" />

==References==

{{Reflist}}

{{Queueing theory}}

[[Category:Queueing theory]]

{{Sourceattribution|Processor sharing}}