Processor sharing

Short description: Form of resource sharing for tasks in computing

Processor sharing or egalitarian 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]

## Contents

* 1 Queueing theory
* 2 Generalized processor sharing
* 3 Multilevel processor sharing
* 4 References

## 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]

## Generalized processor sharing

Main page: 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."[4]

## 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.[1]

## References

1. ↑ 1.0 1.1 1.2 1.3 Aalto, S.; Ayesta, U.; Borst, S.; Misra, V.; Núñez-Queija, R. (2007). "Beyond processor sharing". ACM SIGMETRICS Performance Evaluation Review 34 (4): 36. doi:10.1145/1243401.1243409. http://dna-pubs.cs.columbia.edu/citation/paperfile/142/beyondps-v13.pdf.
2. ↑ Kleinrock, L. (1967). "Time-shared Systems: A theoretical treatment". Journal of the ACM 14 (2): 242–261. doi:10.1145/321386.321388. http://www.lk.cs.ucla.edu/data/files/Kleinrock/Time-Shared Systems A Theoretical Treatment.pdf.
3. ↑ Borst, S.; Núñez-Queija, R.; Zwart, B. (2006). "Sojourn time asymptotics in processor-sharing queues". Queueing Systems 53 (1–2): 31–51. doi:10.1007/s11134-006-7585-9. http://alexandria.tue.nl/openaccess/Metis209591.pdf.
4. ↑ Li, T.; Baumberger, D.; Hahn, S. (2009). "Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin". ACM SIGPLAN Notices 44 (4): 65. doi:10.1145/1594835.1504188. http://happyli.org/tongli/papers/dwrr.pdf.

* 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 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 first
* 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/ Processor sharing. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Processor_sharing&oldid=2169691"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template