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.

Cost Enforcement

• the RTSJ requires that the priority scheduler gives a schedulable object a CPU budget of no more than its cost value on each release.
• if a schedulable objects overrun its cost budget, it is automatically descheduled (made not eligible for execution) immediately
• it will not be re-scheduled until either its next release occurs (in which case its budget is replenished) or its associated cost value is increased.

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 when Q overflows. 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 and the Q is full.

• • EXCEPT: Under this policy, if an arrival occurs and its time should be queued but the queue already holds a number of times equal to the initial queue length defined by this then the fire() method (the fire() method thrown by the AsyncEvent) shall throw a ArrivalTimeQueueOverflowException.
  • IGNORE: Under this policy, if an arrival occurs and its time should be queued, but the queue already holds a number of times equal to the initial queue length defined by this then the arrival is ignored.
  • REPLACE:Under this policy if an arrival occurs and should be queued but the queue already holds a number of times equal to the initial queue length defined by this then the information for this arrival replaces a previous arrival.
  • SAVE: Under this policy if an arrival occurs and should be queued but the queue is full, then the queue is lengthened and the arrival time is saved.

Sporadic Parameters

• Is a subclass of Aperiodic 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.
• Apart from the Q overflow behaviour, has a setMitViolationBehaviour(String policy) on what to do with release events that violate MIT - mitViolationIgnore, Except, Save, Replace.

• • Except: Under this policy, if an arrival time for any instance of Schedulable which has this as its instance of ReleaseParameters occurs at a time less then the minimum interarrival time defined here then the fire() method shall throw MITViolationException.
  • Ignore - Under this policy, if an arrival time for any instance of Schedulable which has this as its instance of ReleaseParameters occurs at a time less then the minimum interarrival time defined here then the new arrival time is ignored.
  • Save - Under this policy the arrival time for any instance of Schedulable which has this as its instance of ReleaseParameters is not compared to the specified minimum interarrival time. 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. For the save policy, the key point is that the fireCount will not be incremented until the

MIT has passed.

• • Replace - Under this policy if an arrival time for any instance of Schedulable which has this as its instance of ReleaseParameters occurs at a time less then the minimum interarrival time defined here then the information for this arrival replaces a previous arrival.

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.
• Aperiodic threads can be run as background activities at lower priority so that they cant preempt the other SOs. However, this causes them to miss their target completion times.
• To improve the situation, a server can be employed. Servers protect the processing resources needed by periodic and sporadic schedulable objects but otherwise allow aperiodic schedulable objects to run as soon as possible.
• The RTSJ provides support for aperiodic server technologies via processing group parameters. When processing group parameters are assigned to one or more aperiodic schedulable objects, a server is effectively created. The servers start time, cost (capac- ity) and period is defined by the particular instance of the parameters. These collectively define the points in time when the servers capacity is replenished.

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 priority.
• 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.

Changes to Parameter Classes

• Under the priority scheduler, changes to scheduling, release, memory, and processing group parameters take effect as follows:
• Changes to Scheduling Parameters (priority) take effect immediately.
• Changes to Release Profile parameters take effect in the next release, except for cost which is immediate.
• Changes to Memory Parameters immediately.
• Changes to PG Parameters at the next replenishment period.

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. This is the policy RTSJ adopts. This is not portable because programmer cant expect scheduler to exist

on different implementations.

• Portable schedulers can be created implementing own scheduling policy on to of FPS.

EDF Scheduler

• An EDF scheduler can be built on top of a Fixed Priority Scheduler.
• An SO when released runs at high priority. So the FPS will ensure it runs. Then it announces itself to the EDF scheduler by calling schedule().
• The EDFS will check if the caller has a lower deadline than the current SO with the earlier DL, if yes it sets the SO to medium priority and the SO with the next DL to low priority.
• If no, the caller will be set to low priority and placed on the queue.
• At the end of the release, SO calls deschedule() which makes the EDF change its priority to high (ready for next release).
• With this approach, a thread with a longer deadline will execute in preference to a shorter deadline thread but only for a small limited time when it is released
• This can be ensured by encapsulating the calls to reschedule and deschedule. [TODO : What?]