Processor Sharing
   HOME

TheInfoList



OR:

Processor sharing or egalitarian processor sharing is a service
policy Policy is a deliberate system of guidelines to guide decisions and achieve rational outcomes. A policy is a statement of intent and is implemented as a procedure or protocol. Policies are generally adopted by a governance body within an or ...
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".


Queueing theory

A single server queue operating subject to Poisson arrivals (such as an
M/M/1 queue In queueing theory, a discipline within the mathematical probability theory, theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service ...
or
M/G/1 queue In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian (modulated by a Poisson process), service times have a General distribution and there is a single server. ...
) with a processor sharing discipline has a
geometric Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
stationary distribution. The sojourn time jobs experience has no closed form solution, even in an
M/M/1 queue In queueing theory, a discipline within the mathematical probability theory, theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service ...
.


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 Queueing theory is the mathematical study of Queue area, waiting lines, or wikt:queue, queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operatio ...
basis, but this assumption is not necessary for many GPS applications. 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."


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.


References

{{Queueing theory Queueing theory