Notes - MIECT
Sistemas Operativos E De Tempo-real
Notes - MIECT
Sistemas Operativos E De Tempo-real
  • Sistemas Operativos e de Tempo-real
  • Basic Concepts About Real-Time Systems
    • Preliminaries
    • Definitions
    • Objective of the Study of RTS
    • Requirements of Real-Time Systems
  • Real Time Model
    • Real Time Model
    • Temporal Control
    • Task states and execution
    • Kernel/RTOS Architecture
      • Time Management Functions
    • Examples of RTOS
  • Practical Class 01
    • Real-Time Services in Linux
    • Using the Linux real-time services
  • Scheduling Basics
    • Basic concepts
    • Scheduling Algorithms
      • Basic algorithms
    • Static Cyclic Scheduling
    • Exercise
  • Fixed Priority Scheduling
    • Online scheduling with fixed priorities
    • Schedulability tests based on utilization
      • Deadline Monotonic Scheduling DM
    • Response-time analysis
  • Practical Class 2
    • Xenomai brief introduction
    • API
    • Developing an application
  • Dynamic Priority Scheduling
    • On-line scheduling with dynamic priorities
    • Analysis: CPU utilization bound
    • Analysis: CPU Load Analysis
    • Other deadline assignment criteria
  • Exclusive Access to Shared Resources
    • The priority inversion problem
    • Techniques for allowing exclusive access
    • Priority Inheritance Protocol
    • Priority Ceiling Protocol
    • Stack Resource Policy
    • Notes
  • Aperiodic Servers
    • Joint scheduling of periodic and aperiodic tasks
    • Aperiodic Servers
    • Fixed Priority Servers
    • Dynamic Priority Servers
  • Limited preemption, release jitter and overheads
    • Non-preemptive scheduling
    • Impact of Release Jitter
    • Accounting for overheads
    • Considerations about the WCET
  • Profiling and Code Optimization
    • Code optimization techniques
      • CPU independent optimization techniques
      • Cache impact
      • Optimization techniques dependent on memory architecture
      • Architecture-dependent optimization techniques
    • Profiling
  • Multiprocessor Scheduling, V1.2
    • Introduction
    • Definitions, Assumptions and Scheduling Model
    • Scheduling for Multicore Platforms
    • Task allocation
Powered by GitBook
On this page
  • Definitions - Processor types
  • Multiprocessor types usually considered
  • Task Models - DAG
  • Fork-Join Model Task Model
  • And-Or Graphs
  • Application Model
  • Assumptions
  • Task and system characteristics
  • Example
  • Additional definitions and observations
  • Critical path
  1. Multiprocessor Scheduling, V1.2

Definitions, Assumptions and Scheduling Model

PreviousIntroductionNextScheduling for Multicore Platforms

Last updated 2 years ago

Definitions - Processor types

Multiprocessor types usually considered

Identical

Processors are of the same type and have the same speed. Each task has the same WCET on each processor.

Uniform

Processors are of the same type but may have different speeds. Task WCETs are smaller on faster processors.

Heterogeneous

Processors can be of different types. The WCET of a task depends on the processor type and the task itself.

Task Models - DAG

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

Fork-Join Model Task Model

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.

And-Or Graphs

The most general graph representation.

  • OR nodes represent conditional statements.

  • AND nodes represent parallel computations.

Application Model

An application can be modeled as a set of tasks, each described by a task graph.

Assumptions

Task and system characteristics

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)).

Example

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 ...

Additional definitions and observations

Immediate results:

Critical path

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.

What is the critical path length?