Resource Management - III

Lecture 19

Introduction to Embedded Systems

Summary of Previous Lecture
• What we have learned :
– Embedded real time systems are an important class of problems.
• Key concepts in real time computing.
– How to analyze the schedulability of independent periodic tasks.
– (Dealing with transient overload
– Handling context-switching overhead)

Introduction to Embedded Systems

Quote of the Day

What you get by achieving your goals is not as

important as what you become by achieving your
goals.
– Zig Ziglar

Introduction to Embedded Systems

Outline of Lectures on Real-Time Systems
• Lecture 1
– Basic Definitions in Real-Time Systems
• Lecture 2
– Real time systems and you
– Fundamental concepts
– An Introduction to Rate-Monotonic Analysis: independent tasks
• Lecture 3:
– An Introduction to RMA
• RMA can be used to analyze ANY fixed-priority scheduling system
– Task synchronization and Aperiodics
– Summary

Introduction to Embedded Systems

Priority Inversion
• Ideally, under prioritized preemptive scheduling, higher priority tasks
should immediately preempt lower priority tasks.
• When lower priority tasks cause higher priority tasks to wait (e.g. the
locking of shared data), priority inversion is said to occur.
• It seems reasonable to expected that the duration of priority inversion
(also called blocking time) should be a function of the duration of the
critical sections.
• Critical section:
– the duration of a task using a shared resource.

Introduction to Embedded Systems

Unbounded Priority Inversion

Introduction to Embedded Systems

Basic Priority Inheritance Protocol
• Let the lower priority task τ3 use the highest priority of the higher
priority tasks it blocks. In this way, the medium priority tasks can no
longer preempt low priority task τ3, which has blocked the higher
priority tasks.
• Priority inheritance is transitive.
– If A blocks B and B blocks C, A should execute at the priority of max(B,C).

Introduction to Embedded Systems

Basic Priority Inheritance Protocol

Introduction to Embedded Systems

Chained Blocking

Introduction to Embedded Systems

Deadlock Under BIP

Introduction to Embedded Systems

Properties of Basic Priority Inheritance
• There will be no deadlock if there is no nested locks, or application level
deadlock avoidance scheme such the ordering of resource is used.
• Chained priority is fact of life. But a task is blocked at most by n lower
priority tasks sharing resources with it, when there is no deadlock.
• The priority inheritance protocol is supported in POSIX real time
extensions.
– It is easy to implement
– it is supported by not only most RT OS vendors but also OS/2, Windows 95,
Windows CE, AIX, HP/UX and Solaris.

Introduction to Embedded Systems

Priority Ceiling Protocol
• A priority ceiling is assigned to each mutex, which is equal to the
highest priority task that may use this mutex.
• A task can lock a mutex if and only if its priority is higher than the
priority ceilings of all mutexes locked by other tasks.
• If a task is blocked by a lower priority task, the lower priority task
inherits its priority.

Introduction to Embedded Systems

Blocked by At Most One Critical Section (PCP)

Introduction to Embedded Systems

Deadlock Avoidance: Using PCP

Introduction to Embedded Systems

A Sample Problem

Introduction to Embedded Systems

Sample Problem: Using BIP

Introduction to Embedded Systems

Schedulability Model Using BIP

Introduction to Embedded Systems

Concepts and Definitions
• Aperiodic task
– runs at irregular intervals.
• Aperiodic deadline:
– hard, minimum inter-arrival time
– soft, best average response

Introduction to Embedded Systems

Sporadic Server (SS)
• To provide on-demand service to aperiodic events, we can allocate a
budget periodically. A periodic event can execute as long as there is
budget left.
• Modeled as periodic tasks
– Fixed execution budget (C)
– Replenishment interval (T)
• Priority is based on T, just like periodic tasks.
• Replenishment occurs one “period” after start of use.

Introduction to Embedded Systems

A Sample Problem

Introduction to Embedded Systems

Sample Problems: Aperiodic
• Emergency Server (ES)
– Execution Budget, C = 5
– Replenish Interval, T= 50
• General Aperiodic Server (GS) Design guideline:
– Give it as high a priority as possible and as much “tickets” as possible,
without causing regular periodic tasks to miss deadlines:
• Execution Budget, C = 10
• Replenish Interval, T = 100
• Simulation and queuing theory using M/M/1 approximation indicate that
the average response time is ~2 msec.

Introduction to Embedded Systems

Summary
• We have reviewed
– the basic concepts of real time computing
– the basics of GRMS theory
– Independent tasks
– synchronization
– aperiodic tasks

Introduction to Embedded Systems

Additional Results
• In networks, distributed scheduling decision must be made with
incomplete information and yet the distributed decisions are coherent -
– lossless communication of scheduling messages, distributed queue
consistency, bounded priority inversion, and preemption control.
• From a software engineering perspective, software structures dealing
with timing must be separated with construct dealing with functionality.
• To deal with re-engineering, real time scheduling abstraction layers
(wrappers) are needed
– old software packages and network hardware behavior can be made to look
as if they are designed to support RMA.

Introduction to Embedded Systems

Recommended Study
1) Use your schedulability program to verify that all the periodic tasks are
still schedulable after adding the two sporadic tasks.
2) Study the slides on how to model interrupts and how to implement period
transformation.
3) Try to apply RMA to your lab work.

Introduction to Embedded Systems

Implementing Period Transformation
• Recall that period transformation is a useful technique to ensure:
– stability under transient overload
– improve system schedulability
• But it is undesirable to slice up the program codes.
– Thou shalt separate timing concerns from functional concerns.
– For example, a task with period T and exception time C, can be transformed
into a sporadic task with a budget C/2 and periodic T/2.
• This is transparent to the applications.
– What is the exception?

Introduction to Embedded Systems

Modeling Interrupts
• A hardware interrupt can have higher priority than software.
• When an interrupt service routine, R, is used to capture data for longer
period task, it will still preempt the execution of shorter period tasks.
• From the perspective of RMA, the time spent in R is a form of priority
inversion. Thus, we can add R into the blocking time from an analysis
perspective.
• Try to do as little as possible in the interrupt handling routine.
– For example, if you need to capture data and filter it, do not do the data
filtering within the interrupt routine.

Introduction to Embedded Systems

Summary of Lecture
• Synchronization in real-time systems
– Priority inversion
– Unbounded priority inversion
– Protocols to bound priority inversion
• basic priority inheritance protocol
• priority ceiling protocol
• Dealing with Aperiodic tasks
– sporadic servers
• Solving our example problem completely
– early deadlines
– average response time

Introduction to Embedded Systems