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
  • Pros
  • Cons
  • Priority allocation approaches
  1. Dynamic Priority Scheduling

On-line scheduling with dynamic priorities

PreviousDeveloping an applicationNextAnalysis: CPU utilization bound

Last updated 2 years ago

Dynamic priorities

Ready Queue sorted by instantaneous priorities and dynamically re-sorted (if/when necessary)

Scheduling is based in dynamic criteria, i.e. one that is known only at run-time.

The dynamic parameter used to sort the ready tasks can be understood as a dynamic priority.

The ready queue is (re)sorted according with decreasing priorities whenever there is a priority change. Executes first the task that has the greater instantaneous priority.

  • Complexity O(n.log(n))

Pros

  • Scales well (wrt SCS).

    • Changes made to the task set are immediately seen by the scheduler.

  • Accommodates easily sporadic tasks (wrt SCS).

  • Allows higher utilization levels than Fixed Priorities.

Cons

  • More complex implementation (wrt SCS and FP).

  • Higher overhead (wrt SCS and FP).

    • Re-sorting of the ready queue; depends on the algorithm.

  • “Unpredictability” on overloads (wrt FP).

    • It is not possible to know a priori which tasks will fail deadlines.

Priority allocation approaches

Inversely proportional to the time to the deadline.

  • EDF – Earliest Deadline First.

    • Optimal among all dynamic priority criteria.

  • Inversely proportional to the laxity or slack.

    • LSF (LST or LLF) – Least Slack First.

      • Optimal among all dynamic priority criteria.

  • Inversely proportional to the service waiting time.

    • FCFS –First Come First Served.

      • Not optimal with respect to meet deadlines; extremely poor real-time performance.