Basic concepts

Scheduling Definition

Task scheduling (also applies to messages, with due adaptations).

• Sequence of task executions (jobs) in one or more processors.

• Application of (time) in (task set), assigning to each time instant “t” a task/job “i” that executes in that time instant.

  • 
• σ(t) is a step function, which can be expressed e.g. as a Gantt graph.

A schedule is called feasible if it fulfills all the task requirements.

• temporal, non-preemption, shared resources, precedences, ...

A task set is called schedulable if there is at least one feasible schedule for that task set.

Scheduling problem

Given:

• A task set.

• Requirements of the tasks (or cost function).

Find a time attribution of processor(s) to tasks so that:

• Tasks are completely executed, and

• Meet they requirements (or minimize the cost function).

E.g. J = Ji (Ci = 1, ai = 1, Di = 5), i = {1..5}

Exercise

Build a Gantt diagram for the execution of the following periodic tasks, admitting Di = Ti and no preemption.

• τ = {(1, 5)(6, 10)}

Is the execution order important? Why?

Solution

After 10, the process repeat