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. (worst case processor time per each run).
  • a relative deadline by which each run must have finished.
  • To define how often a SO runs. (Interval for a periodic/sporadic SO).
  • Event Handlers can be specified for deadline misses or cost overruns.

• Minimum info that a scheduler needs to perform feasibility analysis is cost and deadline.

Periodic Parameters

• Has a start time - relative/absolute value. If relative, time of calling start() + relative. If absolute max of start or absolute time.
• The deadline for a schedulable object with periodic parameters is measured from the time that it is released not when it is started or fired.

Aperiodic Parameters

• No start time or period defined because it can occur anytime.
• Accepts deadline, cost but deadline cannot be guaranteed because an AP SO can occur as often as it likes.
• When AP is released, it becomes runnable and is scheduled for execution.
• Before it completes execution, may be released again. So these releases events must be queued so that they arent lost.
• Programmer can specify length of queue and action to be taken. e.g. setArrivalTimeQueueOverflowBehavior(String policy) where policy can be EXCEPT, IGNORE, REPLACE, SAVE which specifies what

to do in the Q when a release event occurs.

Sporadic Parameters

• Released at irregular intervals, but any two releases will always occur at an interval greater than or equal to a minimum inter arrival time. (MIT)
• The scheduler must check for violations of this constraint and take corrective action.
• Again like Aperiodic, a sporadic SO might be released and before it completes, can be released again.
• So it is necessary to queue the release events so that they arent lost.
• Has a setMitViolationBehaviour(String policy) on what to do with release events that vilate mit - mitViolationIgnore, Except, Save, Replace.

• • Except throws an exception
  • Ignore - ignores the new violating release event.
  • Save - saves the event in the Q. However the time between this request and the other requests in the Q is set to the Minimum Inter Arrival time.
  • Replace - replaces the previous arrival in the Q.

Scheduling Parameters

• Abstract class. Allows priority of the SO to be specified.

Priority Parameters

• Concrete class which takes takes a single integer as priority.

Importance Parameters

• Subclass of PriorityParameters. Takes an additional importance parameter in addition to priority.

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.

Analysis

• Requires no particular analysis to be supported.

Alternative Schedulers

• Pluggable schedulers : System (RTJVM) provides a framework where different schedulers can be plugged in.
• Application defined schedulers: System notifies application on what scheduling decision to take, application then informs system.
• Implementation defined schedulers: Implementation RTJVM itself defines alternative schedulers.