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.