Scheduling

Intro

• RT Systems must be able to interact with their environment in a timely and predictable manner.
• Therefore an RT system must be analyzable whose timing properties can be proven and mathematically correct.
• Scheduling is the ordering of threads/processes so that the underlying hardware and software resources can be predictably and efficiently used.
• Scheduling consists of three components:
  • Scheduling policy: An algorithm for ordering access to resources.
  • Scheduling mechanism: An algorithm for allocation resources.
  • Schedulability/Feasibility analysis: A means of predicting the worst case behavior of the system when the policy and mechanism are applied. Once the worst case has been predicated, then it can be compared with the systems timing requirements to ensure that all deadlines will be met.

Fixed Priority Scheduling

Policy

• FPS Requires:
• Statically allocate SO's to a single processor.
• Order SO execution on a single processor according to their priority.
• Assign priorities to SO's at their creation time. Usually priorities are assigned according to deadlines.
• Priority Inheritance when accessing resources.

Mechanism

• Pre-emptive priority based dispatching of processes. The resource is always given to the highest priority runnable SO.

Feasibility Analysis

• Many different analysis techniques possible for FPS. Most flexible is Response Time Analysis.
• Most approaches view system as a number of SO's.
• Each SO is characterized by its:
  • Release profile.
  • Processing cost per release.
  • Hardware resources needed per release.
  • Software resources per release.
  • Deadline
  • Value

Release Profile

• Typically after a SO is started, it waits to be released. When released it does its work and then it waits to be released again.
• The release profile defines the frequency at which the release of a SO occurs. The release may be time triggered or event triggered.
• Time triggered releases are periodic releases.
• Event triggered releases are
  • Sporadic: They are irregular but with a minimum inter arrival time.
  • Aperiodic: No minimum inter arrival time assumptions can be made.

Processing Cost Per Release

• How much of CPU time is required to execute the computation of the SO per release.
• May be a worst case value or average value depending on the feasibility analysis.

Hardware and Software Resources

• Hardware resources:
  • Networks - bandwidth required
  • Memory - Amount of memory required by the SO's.
• Software resources
  • A list of non shareable resources that are required and the cost of using each resource.
  • Access to non shareable resources is a critical factor for schedulability analysis. The blocking time for shared resources has to be taken in to account during analysis.

Deadline

• The time within which the SO has to complete its computation associated with each release.
• The deadline is a relative value rather than a absolute value.

Value

• A metric which indicates the SO's contribution to the overall functionality of the application. Can be:
  • Coarse Indication (non critical to safety critical)
  • A numeric value giving a measure of successfully meeting the deadline.
  • A time valued function which takes time at which SO completes and returns a measure of the value based on the time.

Online vs Offline Analysis

• For safety critical systems - offline analysis is a must.
• Other systems which do not have stringent timing requirements or do not have predicatble worst case behavior - online analysis may be appropriate.
• These systems must be able to tolerate:
  • SO's not being schedulable and offer degraded services.
  • Handle missed deadlines or worst case times have been violated.

RTSJ Model

• RTSJ provides a framework in which on-line analysis of fixed priority systems can be conducted.
• RTSJ also allows the RTVM to monitor resources being used and to release Asynchronous Event Handlers if those resources go beyond specified limits.
• Introduces notion of a Schedulable object rather than just considering Threads.
• A schedulable object (SO) is an object which implements the Schedulable Interface.

Release Parameters

• ReleaseParameters class hierarchy allows:
  • Specification of processing cost per release.
  • Deadline
  • If a SO is periodic/sporadic then its interval.
  • Event Handlers can be specified for deadline misses or cost overruns.

Scheduling Parameters

• Allows priority of the SO to be specified.

Memory Parameters

• Max amount of memory consumed by the SO in a associated memory area.
• Max amount of immortal memory.
• Max allocation rate of heap memory.

Processing Group Parameters

• Allows several SO's to be treated as a group and have associated period,cost, deadline.

Schedulable Interface

• Three groups of methods.
• Methods which communicate with the scheduler and will result in scheduler adding/removing list of SO's it manages or changing parameters of an SO.
  • The scheduler performs a feasibility test on the objects it manages.
  • e.g. addIfFeasible(), setIfFeasible() etc.
• Methods which get/set parameter classes of the SO. e.g. getMemoryParameters(), setMemoryParameters().
• Methods which get/set the scheduler itself. e.g. getScheduler(), setScheduler().

RTSJ Priority Scheduler

Policy

• Orders SO's according to policy.
• Supports 28 different RT Priorities.
• Programmer can define priorities. Priorities can be changed at run-time.
• Allows Priority Inheritance and Priority Ceiling Emulation.

Mechanism

• Pre emptive priority based dispatching - resource always given to highest priority SO.
• Does not define where in the run queue a pre-empted object is placed.
• Places a blocked schedulable object which becomes runnable, or has its priority changed at the back of the run queue associated with its (new) priority.
• Places a thread which performs a yield operation at the back of the run queue associated with its (new) priority.