Next: BuildOption
Up: Property
Previous: Accept

Algorithm

Description

The Algorithm property is used to further specify an RTScheduler connector. It is typically used to specify an instantiation of such a connector, but it can also be used to specify a definition. However, when left out of the definition, the connector is more general and can be parameterized at instantiation time with this property.

An RTScheduler connector governs the interaction of SchedProcess components contending for a single processor resource in a real-time environment. This connector corresponds to a scheduler in the kernel of a real-time operating system. The scheduler's responsibility is to provide each schedulable process in a system of such processes with access to the processor resource. This is done according to some algorithm.

In the Real-Time Mach operating system (the target evironment for instantiations of RTScheduler connectors in UniCon systems) there are six distinct real-time scheduling algorithms:

rate monotonic

Schedulable processes are given priorities based on their periods of execution. Processes with shorter periods are given higher priorities. Highest priority processes get access to the processor first.

deadline monotonic

Schedulable processes are given priorities based on the length of time between the start of the period and the deadline of the process. Processes with the shorter of these "deadline" periods are given higher priorities. Highest priority processes get access to the processor first.

earliest deadline first

The schedulable process with the closest deadline is given access to the processor first. A deadline is an absolute time, and the closest deadline is measured from the current time.

fifo fixed priority

The schedulable processes of a given priority are given access to the processor in the order in which they get rescheduled to run. The processes, in this case, always run to completion.

round robin fixed priority

The schedulable processes of a given priority are given access to the processor in the order in which they are created (the highest priority processes in a system still get access to the processor first). Each process is given a time slice in which to run. If the process completes or uses up the allotted time in the slice, it is moved to the back of its queue.

timesharing

Each schedulable process is initially given the same priority in the system by the scheduler and placed in a multi-level feedback queue. Processes that are compute bound have their priorities bumped down over time, and processes that are I/O bound have their priorities bumped up over time. Highest priority processes get access to the processor first.

The system designer uses the Algorithm property to specify the scheduling algorithm for a system of schedulable processes contending for the processor resource at run-time. The UniCon compiler generates an initialization program for the processor associated with the RTScheduler connector that sets the scheduling algorithm in the kernel to the one selected by the system designer. The UniCon compiler also generates a Unix shell script that initializes a real-time application at run-time. This shell script executes the scheduling algorithm initialization program prior to starting up the executables in the application system.

If the Algorithm property in an RTScheduler connector instantiation specifies the rate_monotonic scheduling algorithm, the UniCon compiler can facilitate a Rate Monotonic Analysis (RMA) on the events described by the Trace properties in that connector instantiation (see the Description for the Trace property for more information on events). For a RMA, the UniCon compiler collects the segment names, their execution times, and the period information for each event associated with a given processor; it also collects the priority information for each schedulable process associated with that same processor. It then formats this information and prepares a file containing input to a RMA tool which performs the analysis. This tool is invoked manually and reports a simple answer to indicate whether or not all of the events will meet their respective deadlines. The file that UniCon prepares with the input to the RMA tool is named RMA_<processor_name>, where <processor_name> is taken from the Processor property associated with the RTScheduler connector instantiation in which the Trace properties are specified. An RMA input file is generated by the UniCon compiler for each RTScheduler connector instantiation whose Algorithm property specifies a rate_monotonic scheduler.

Property Lists

The Algorithm property can legally be specified in the property list in the following UniCon language elements:

<establish>
<instantiation> of a connector
<protocol>

Value Syntax

The syntax of the value part of an Algorithm property is one of the six keywords rate_monotonic, deadline_monotonic, earliest_deadline_first, fifo_fixed_priority, round_robin_fixed_priority, or timesharing, optionally enclosed in double-quotes, surrounded by parentheses. The case of the letters can be upper, lower, or mixed.

Required Rule

Optional

The default value for the Algorithm property is rate_monotonic.

Merge Rule

REPLACE

Subsequent specifications of the Algorithm property in a single property list replace earlier specifications (i.e., the last specification is the one that the UniCon compiler uses).

Semantic Checks

The value of the Algorithm property must be one of the following six values: rate_monotonic, deadline_monotonic, earliest_deadline_first, fifo_fixed_priority, round_robin_fixed_priority, or timesharing.

Example

The following is an example of an Algorithm property. It is embedded in an
<establish> of an RTScheduler connector:

  ESTABLISH RTM-RealTime-Sched WITH
    client.load AS load
    server.load AS load
    PROCESSOR (TESTBED.XX.CMU.EDU)
    ALGORITHM (rate_monotonic)
    TRACE (client.load.trigger,
      client.load.segment1,
      server.load.segment,
      client.load.segment2)
  END RTM-RealTime-Sched