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.
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.
Instantiates / Related Primes¶
This entry is a kind of Load Balancing.
Load Balancing is the broader abstraction this entry instantiates: 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.
Relationships to Other Abstractions¶
Current abstraction Processor Sharing Domain-specific
Parents (1) — outgoing typed relations
-
Processor Sharing is a kind of Load Balancing Prime
Load Balancing is the broader abstraction this entry instantiates: 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.
Hierarchy paths (2) — routes to 1 parentless root
- Processor Sharing → is a kind of Load Balancing → is a kind of, typical Resource Management → presupposes Allocation → presupposes Scarcity → is a decomposition of Constraint
- Processor Sharing → is a kind of Load Balancing → is a decomposition of Allocation → presupposes Scarcity → is a decomposition of Constraint
Neighborhood in Abstraction Space¶
Processor Sharing sits in a sparse region of the domain-specific corpus (98th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2769 abstractions)
Nearest neighbors
- Polling system — 0.77
- Jackson's Theorem (Queueing Theory) — 0.76
- Unbounded nondeterminism — 0.75
- Offered load — 0.75
- Lindley equation — 0.75
Computed from structural-signature embeddings · 2026-10-25
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 ↩ Show verification details
Supported in partVerified against the publisher's abstract
The abstract confirms the paper models a time-shared processor discipline but states no 1/n capacity rule, so only the frame is supported.
“This paper analyzes a queueing structure for a time‐shared service facility (or processor) and compares these results with a straightforward first‐come first‐served discipline.”
[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 Show verification details
a) Supported in partVerified against the work's full text
BCMP (1975) supports the product-form network half, including processor-sharing centers; it does not mention Kleinrock introducing processor sharing.
“Type 2 and type 4 service centers (processor-sharing scheduling and LCFS) are appropriate mod- els for CPUs since LCFS is an efficient preemptive scheduling method and round robin scheduling approaches processor sharing”
Claim b has not been through verification yet.
[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 ↩ Show verification details
Supported in partVerified against the publisher's abstract
The abstract supports GPS and a packet-by-packet approximation but does not state weight-based share allocation.
“The authors present a practical packet-by-packet service discipline, PGPS that closely approximates GPS.”