Definitions, Assumptions and Scheduling Model
Last updated
Sistemas Operativos E De Tempo-real
Last updated
Processors are of the same type and have the same speed. Each task has the same WCET on each processor.
Processors are of the same type but may have different speeds. Task WCETs are smaller on faster processors.
Processors can be of different types. The WCET of a task depends on the processor type and the task itself.
Representing parallel code requires more complex structures than for sequential tasks.
A Directed Acyclic Graphs (DAG) is a graph in which links have a direction and there are no cycles
A special type of Directed Acyclic Graph.
Nodes represent processing.
After a Fork node, all successors have to be executed. The order is not relevant (nor defined).
Join nodes only execute after the completion of all their predecessors.
Nesting is allowed.
The most general graph representation.
OR nodes represent conditional statements.
AND nodes represent parallel computations.
An application can be modeled as a set of tasks, each described by a task graph.
Arrival pattern.
Periodic or Sporadic (period or mit is T).
Preemption.
Allowed, but eventually with critical sections.
Task migration allowed?
May or may not. We will see ...
Task parameters.
τi = {{i, ci, ...i m }, Di , Ti }
ci : WCET of a segment
m: number of segments of τi
dependencies (in form of list(s)).
Consider the following example:
Compute the minimum WCET of task τ1 in isolation, considering the intra-task (segment) precedence relations.
Number of cores is not restricted.
Task attributes.
τ1 = {{2, 3, 1, 1, 2, 3}, 8, 12}
Dependencies: τ1,3 ← {τ1,1 , τ1,2 } and {τ1,4 , τ1,5 , τ1,6 } ← τ1,3
WCET = 7 tu for a number of cores greater or equal to 3.
More processors are not always helpful ...
Immediate results:
If follows immediately that if for any task Cip > Di then the application is not feasible in any number of cores
Sequential Computation time:
CPU utilization of a task:
If the task is schedulable in a single core
If where K is the number of cores, then the task is not schedulable.
Critical path length length of the longest path in the graph.
