Processor Sharing¶

An ideal preemptive service discipline that divides a server's instantaneous capacity among all jobs currently present, usually equally or by fixed weights.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2548
Origin domain: computer science
Subdomain: queueing theory
Aliases: Processor-sharing discipline, Egalitarian processor sharing, PS queue

Core Idea¶

Processor sharing is an ideal preemptive service discipline in which every job present at a single server receives service immediately and simultaneously. With (n) jobs in an unweighted model, each receives (1/n) of the server's instantaneous capacity; the allocation changes whenever a job arrives or departs.^[1]

The abstraction is the continuous-time limit of increasingly fine round-robin time slicing. It removes quantum and context-switch detail so that queueing analysis can focus on arrival processes, service requirements, response times, and fairness.^[2]

The recognition invariant is one divisible service capacity + a changing set of resident jobs + concurrent fractional allocation + immediate reallocation at population changes.

Structural Signature¶

A queueing station with total service rate specified.
A time-varying population of jobs with remaining service requirements.
Immediate service for every resident job rather than one job at a time.
Equal instantaneous shares in ordinary processor sharing.
Optional positive weights in generalized or discriminatory variants.
Preemption with no modeled switching penalty.
Share recomputation on every arrival and departure.
Sojourn time dependent on concurrent population and job size.
Work conservation whenever at least one eligible job is present.
A fluid or infinitesimal-quantum interpretation.
Stability governed by offered load relative to capacity.

What It Is Not¶

Processor sharing is not routing work among several processors; that is load distribution across servers. It is not ordinary nonpreemptive first-come, first-served service, and it is not literal parallel execution unless the physical system actually provides it. It is also not a claim that real schedulers have zero context-switch overhead.

Round robin approximates processor sharing only as its quantum becomes small relative to service times and overhead remains negligible.

Scope of Application¶

The model applies to time-shared computers, bandwidth sharing, packet and flow models, service systems, and product-form queueing networks. Kleinrock introduced it to analyze time-shared processors; the BCMP theorem later established broad product-form networks containing processor-sharing centers.^[3]

Weighted and generalized processor sharing allocate shares according to class or flow weights and motivate implementable packet schedulers, although packetization prevents exact simultaneous service.^[4]

Clarity¶

State the arrival process, service-demand distribution, capacity, discipline, weighting rule, eligibility set, and whether service requirements are known. Distinguish job-level processor sharing from flow-level bandwidth sharing and distinguish the mathematical fluid model from its discrete scheduler approximation.

Manages Complexity¶

The abstraction collapses rapid preemption and interleaving into an instantaneous rate allocation. That replacement can make response-time and network calculations tractable without encoding every scheduling quantum. It also exposes how occupancy dilutes per-job rate and how job-size variability changes individual delay.

Abstract Reasoning¶

Specify the server capacity and admitted job set.
Assign each resident job an equal or weighted fraction.
Decrease remaining work at the allocated rate.
Add arrivals and remove completed jobs at event times.
Recompute shares after every population change.
Derive occupancy, sojourn-time, slowdown, or throughput measures.
Check stability and conservation of work.
Add quantum, overhead, or packetization only when implementation fidelity requires it.

Knowledge Transfer¶

The portable pattern is continuous redivision of a finite capacity among all currently eligible claimants. It transfers to link bandwidth, cloud-resource shares, fair scheduling, and fluid approximations of multiplexed service. The proposed immediate parent is Load Balancing.

Examples¶

Two jobs. Two equal jobs at one unit-rate server each receive rate (½); when one completes, the other receives the full rate.

Short job amid long jobs. A newly arrived short job begins immediately rather than waiting for every earlier long job, though its rate is reduced by all concurrent jobs.

BCMP station. A processor-sharing service center may participate in a multiclass product-form network under the theorem's conditions.^[3]

Structural Tensions¶

Fair sharing versus shortest completion time.
Continuous idealization versus scheduling overhead.
Immediate service versus reduced per-job rate.
Equal shares versus differentiated weights.
Work conservation versus eligibility constraints.
Analytic tractability versus implementation fidelity.

Structural–Framed Character¶

Divisible capacity, concurrent claims, proportional allocation, and event-driven redistribution are structural. Jobs, service requirements, queues, sojourn times, and scheduler quanta supply the constitutive queueing frame.

Structural Core vs. Domain Accent¶

The portable core is dynamic fractional allocation among active claimants. The domain accent is a queueing server whose jobs accumulate and consume stochastic service requirements.

Load Balancing is the proposed immediate parent: the discipline continually apportions one constrained service resource. Fairness, Scheduling, Resource Management, Preemption, Multiplexing, and Capacity are related. Unlike dispatching, however, processor sharing does not choose among multiple destinations.

The prospective queue contains one strict edge to prime:load_balancing. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Processor Sharing Domain-specific

Parents (1) — more general patterns this builds on

Processor Sharing is a kind of Load Balancing Prime

Load Balancing is the proposed immediate parent: the discipline continually apportions one constrained service resource.

Hierarchy paths (2) — routes to 1 parentless root

Processor Sharing → Load Balancing → Resource Management → Allocation → Scarcity → Constraint

Show alternative path (1)

Neighborhood in Abstraction Space¶

Processor Sharing sits in a sparse region of the domain-specific corpus (98^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Polling system — 0.77
Unbounded nondeterminism — 0.75
Offered load — 0.75
Lindley equation — 0.75
BCMP network — 0.75

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Multiprocessor load balancing.
First-come, first-served scheduling.
Round robin with a material time quantum.
Simultaneous multithreading as a hardware mechanism.
Generalized processor sharing, which introduces weights.
Packet scheduling that only approximates a fluid server.

References¶

[1] Leonard Kleinrock, “Analysis of a Time-Shared Processor,” Naval Research Logistics Quarterly 11, no. 1 (1964): 59–73, doi:10.1002/nav.3800110105. registry ↩

[2] Leonard Kleinrock, Queueing Systems, Volume 2: Computer Applications (Wiley, 1976), treatment of time-sharing and processor-sharing systems. registry ↩

[3] Forest Baskett, K. Mani Chandy, Richard R. Muntz, and Fernando G. Palacios, “Open, Closed, and Mixed Networks of Queues with Different Classes of Customers,” Journal of the ACM 22, no. 2 (1975): 248–260, doi:10.1145/321879.321887. registry ↩a ↩b

[4] Abhay K. Parekh and Robert G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,” IEEE/ACM Transactions on Networking 1, no. 3 (1993): 344–357, doi:10.1109/90.234856. registry ↩