Documentation
¶
Overview ¶
Package listsched is list scheduling (Graham, 1969): whenever a machine is free, start the highest-priority ready task that may run beside what is running. It is parametric in the priority, so a caller ranks by critical path, urgency or anything else, and it adds one constraint Graham did not have: a conflict relation, under which two tasks never run at once.
Pick is the one decision the scheduler makes, shared by the simulator here and by any service that dispatches work the same way, so a service's dispatch order is the simulator's prediction by construction. Simulate runs a whole plan to its makespan; LowerBound and GrahamBound turn a measured makespan into a verdict against the optimum without computing it.
Index ¶
- Constants
- Variables
- func GrahamBound(capacity int, optimum time.Duration) time.Duration
- func LowerBound[ID comparable, Kind comparable](plan Plan[ID, Kind]) (time.Duration, error)
- func Pick[ID comparable](ready []ID, running []ID, capacity int, conflicts func(a ID, b ID) bool, ...) []ID
- type Interval
- type Plan
- type Sample
- type Schedule
Constants ¶
const DefaultDuration = time.Second
DefaultDuration is the duration of a task the plan does not time.
Variables ¶
var ( // ErrInvalidPlan reports a plan with no order, no priority or a capacity // below one. ErrInvalidPlan = errors.New("listsched: invalid plan") // ErrStuck reports a plan whose conflicts leave ready tasks that can never // start, which cannot happen for a conflict relation that is irreflexive. ErrStuck = errors.New("listsched: ready tasks can never start") )
Functions ¶
func GrahamBound ¶
GrahamBound is the makespan a list schedule on capacity machines never exceeds: (2 - 1/m) times the optimum (Graham, 1969). Given a lower bound on the optimum instead of the optimum itself the result is still a valid test: a makespan within the bound of the lower bound is within it of the optimum.
func LowerBound ¶
func LowerBound[ID comparable, Kind comparable](plan Plan[ID, Kind]) (time.Duration, error)
LowerBound is a bound no schedule of the plan can beat: the longer of the critical path (the heaviest chain of dependent tasks, which cannot overlap itself) and the total work spread over every machine.
func Pick ¶
func Pick[ID comparable](ready []ID, running []ID, capacity int, conflicts func(a ID, b ID) bool, less func(a ID, b ID) bool) []ID
Pick chooses which ready tasks start now: in priority order, each task that conflicts with nothing running and nothing picked before it, until the capacity is full. Lower-priority tasks are not held back by a blocked higher-priority one; that is what keeps the machines busy, and it is the bucketed order of Δ-stepping rather than a strict serial one.
Types ¶
type Interval ¶
type Interval[ID comparable] struct { Task ID Start time.Duration End time.Duration }
Interval is one task's run in a schedule.
type Plan ¶
type Plan[ID comparable, Kind comparable] struct { // Order is the graph holding the precedence relation; every task is one // of its nodes. Order *inproc.Graph[ID, Kind] // Precedes is the directed acyclic kind of Order that orders tasks. Precedes Kind // Duration is a task's expected duration; a task with none takes // [DefaultDuration]. Duration func(id ID) time.Duration // Conflicts reports whether a and b must not run at once. It is // symmetric and irreflexive; nil means no conflicts. Conflicts func(a ID, b ID) bool // Capacity is how many tasks may run at once. Capacity int // Less reports whether a should start before b when both are ready. Less func(a ID, b ID) bool }
Plan is what the scheduler works from: the precedence order, each task's expected duration, the conflict relation, the capacity and the priority.
type Schedule ¶
type Schedule[ID comparable] struct { // Intervals in start order, the dispatch order. Intervals []Interval[ID] Makespan time.Duration // Concurrency over time: one sample at every start or end. Concurrency []Sample // Peak is the most tasks that ran at once. Peak int }
Schedule is the result of simulating a plan.
func Simulate ¶
func Simulate[ID comparable, Kind comparable](plan Plan[ID, Kind]) (Schedule[ID], error)
Simulate runs the plan: at time zero and at every completion it picks what starts next, until every task has run. Durations are the plan's expected ones, so the result is the prediction a dispatcher using Pick with the same priority realizes when its tasks take as long as expected.
Source Files