CoreSource checked

Proportional Share Scheduling

Proportional Share Scheduling allocates service according to fairness or proportional-share rules.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Intermediate
Family: Scheduling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready

Overview

Proportional Share Scheduling is a scheduling method that selects or admits work using a concrete priority, fairness, deadline, or capacity rule. It helps expose the policy tradeoff behind queue order, fairness, deadlines, or resource use.

Core Concepts

priority ruleresource allocationqueue disciplinetask order

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use Proportional Share Scheduling when queue order, resource assignment, or deadline policy must be explicit.
Use it when comparing fairness, latency, throughput, or utilization policies matters.

When Not to Use

Avoid when the policy would hide starvation, unfairness, or deadline misses.
Avoid when task durations or priorities are too uncertain for the rule to be meaningful.

What It Does

Ranks ready work with a scheduling rule
Updates waiting time, deadlines, or capacity
Returns an order, assignment, or admission decision

Use Cases

CPU scheduling
Network queue management
Workflow and batch processing

Inputs

Jobs or requests
Timing constraints
Resource limits

Outputs

Execution order
Resource assignment
Timing decision

Key Formulas (1)

Resource share

share_i = weight_i / ∑(weights)

share_i = weight_i / sum(weights)

Allocates service in proportion to each runnable job's weight.

Pseudocode

1.Collect ready jobs, queues, or tasks
2.Compute the method's priority, fairness, or capacity score
3.Select the next job or resource assignment
4.Update waiting time, capacity, or completion state
5.Repeat until all work is scheduled or admitted

Canonical Example

Input: jobs = [{id:A, time:3}, {id:B, time:1}], resource = one worker
Output: ordered or assigned jobs according to the scheduling rule
Explanation: Proportional Share Scheduling computes the priority or capacity rule and chooses the next job from the ready set.

Implementation Notes

Make tie-breaking deterministic and visible in tests.
Track waiting time, service time, and resource state separately.
State whether the policy is preemptive and what fairness, latency, or deadline objective it optimizes.

Common Pitfalls

Forgetting tie-breaking rules makes schedules unstable across runs.
Ignoring starvation and fairness edge cases can make good averages hide bad tail behavior.
Ignoring preemption cost, release times, or starvation can make a schedule look correct only in toy cases.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show queued jobs moving onto processors, links, or time slots as the scheduling rule changes priorities.

Step 1 of 5: Collect ready jobs, queues, or tasks

scheduling

Notes

Proportional Share Scheduling operates in O(n log n) time and O(n) space within the Scheduling family. Key governing relation: share_i = weight_i / sum(weights). Often compared with Round Robin Scheduling and Priority Scheduling.