Surplus Fair Scheduling

Ricardo A. Baratto

COMS E6118 – Spring 2004

Proportional-Share

CPU Scheduling

for Symmetric Multiprocessors

What? Why?

Fair resource allocation

Proportional to application's share

WFQ [Demers et al.], [Parekh et al.], Stride [Waldspurger et al.]

SFQ [Goyal et al.]

SMART [Nieh et al.]

The Problem

Unfeasible Weight Assignment: Starvation

Upper Bound on Assignment

Frequent Arrival – Departures: Unfairness

Burst Behavior

Surplus Fair Scheduling

Weight Readjustment

Generalized Multiprocessor Sharing
(Surplus Approximation)

Weight Readjustment

Readjust threads violating feasibility constraint:

Optimal:

Number of threads

Weight change

Efficient

O(p)

GMS and Surplus Approximation

Generalization of GPS [Parekh et al.]

φi: Readjusted weight

Ai(t1, t2): CPU service received

Si: Weighted CPU service = Si + q/φi

αi = Ai(0, t) - AiGMS(0, t)
≈ (φi . Si) - (φi . v)

SFS Algorithm

update Fi and compute Si

compute v: min(Si)

compute αi

schedule ti with min(αi)

If {t} changes: readjust weights

Implementation and Complexity

Three ordered queues:

w: Weight readjustment

S: Virtual time

α: Next to schedule

Add thread: Insert + Readjust = O(t+p)

Delete thread: Delete + Readjust = O(p)

Schedule: Update surplus + Sort = O(t log t)
[~ every p schedules]

Evaluation: Weight Readjustment

Evaluation: Short Jobs

Evaluation: Application Isolation

2004-01-26T20:09:03