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.
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.
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.
Weighted and generalized processor sharing allocate shares according to class or flow weights and motivate implementable packet schedulers, although packetization prevents exact simultaneous service.
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.
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
- Processor Sharing → Load Balancing → Allocation → Scarcity → 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 (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