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
  • On-line scheduling with dynamic priorities
  • Schedulability tests
  • EDF Scheduling
  • Example
  • Notion of fairness
  1. Dynamic Priority Scheduling

Analysis: CPU utilization bound

PreviousOn-line scheduling with dynamic prioritiesNextAnalysis: CPU Load Analysis

Last updated 2 years ago

On-line scheduling with dynamic priorities

Schedulability tests

Since the schedule is built online it is important to determine a priori if a given task set meets or not its temporal requirements.

There are three types of schedulability tests:

  • Based on CPU utilization.

  • Based on CPU load (processor demand).

  • Based on response time.

EDF Scheduling

EDF tests based on CPU utilization (n independent tasks, with full preemption).

  • D = T

    • <=> Task set is schedulable.

    • Allows using 100% of CPU with timeliness guarantees.

  • D < T

    • <=> Task set is schedulable.

    • Sufficient condition, only.

    • Pessimistic test (as for RM, inflates the utilization).

Example

RM Scheduling

  • In fact τ3 fails a deadline!

EDF Scheduling

Note

  • No deadline misses.

  • Less preemptions.

  • Higher jitter on quicker tasks.

  • The worst-case response time does not coincide necessarily with the synchronous release.

Notion of fairness

Be fair on the attribution of resources (e.g. CPU).

EDF is intrinsically fairer than RM, in the sense that tasks see its relative deadline increased as the absolute deadline approaches, independently of its period or any other static parameter.

Consequences:

  • Deadlines are easier to met.

  • As the deadline approaches preemptions suffered by a given task are reduced.

  • The slack of tasks that are quick but have large deadlines can be used by other task (higher jitter on tasks with shorter periods).

-> 1 activation per period NOT guaranteed.

<=> one activation per period IS guaranteed.