Next: Role
Up: Connector Type
Previous: RemoteProcCall

RTScheduler

Semantics

The connector type RTScheduler mediates interaction between SchedProcess components in competition for a processor resource. Recall that a SchedProcess component is a process in a real-time operating system environment that is scheduled according to some real-time scheduling algorithm. This type of process performs some work, runs to completion, and then gets rescheduled in the operating system to run again. Because of this, the process runs periodically and requires a certain percentage of the processor resource over time. When there are multiple such processes in the system, the scheduling of each process becomes important; if scheduling is not done efficiently, the processes in contention for the resource may or may not be able to complete their work before they must run again. Similary, the processor resource may be idle for significant periods of time, while at the same time some processes are not completing their work.

The RTScheduler connector type corresponds to the mediation of this interaction between real-time processes in contention for the CPU resource. It requires an operating system with appropriate real-time capabilities; the UniCon compiler currently supports implementation mechanisms for the Real-Time Mach operating system. The processor resource in the Real-Time Mach kernel can be managed according to one of six different algorithms: the rate monotonic, deadline monotonic, earliest deadline first, fifo fixed priority, round robin fixed priority, or timesharing algorithm. The system designer can specify the particular algorithm with the Algorithm property in an RTScheduler connector instantiation. The system designer can also specify the particular processor to be managed with the Processor property in the connector instantiation.

If the system designer specifies the rate monotonic scheduling algorithm for the processor, UniCon will automatically prepare some input for a rate monotonic analysis (RMA) tool that will determine if the set of real-time processes in the RTScheduler connection will all meet their deadlines (i.e., complete execution before they must run again). To facilitate this, the system designer is required to specify one Trace property in the connector instantiation for each event that is being managed in the RTScheduler connection. The RMA is performed on events rather than processes; the schedulability of the events implies the schedulability of the processes.

An event in UniCon is a complete thread of execution in a real-time system that can span multiple processes because of the presence of RPC calls. An event describes execution of a thread from the time control is first given to a client process by the operating system via a trigger (the mechanism by which control is transferred; e.g., an timer interrupt), until control is returned to the operating system as a result of the client finishing its work. An event consists of a trigger, followed by a specific sequence of smaller chunks of code called segments. Segments are atomic blocks of work within a given process, atomic meaning that the thread of control within the block is continuous (i.e., not transferred to another process). The sequence of segments in an event are executed in an order that is defined by the thread of control in the application. For example, a client process gets activated by the operating system. The client does some work (a segment), and then, perhaps, makes an RPC call to a server process. The server process does some work (another segment) and either returns to the client, or makes an RPC call itself. This continues until control is eventually returned back to the client, which does more work (another segment). Work proceeds this way until control is returned back to the operating system.

There can be potentially many events in a single RTScheduler connection. There will be one for each trigger that transfers control to a client process in the set of application processes whose interaction is mitigated by the RTScheduler connector. The system designer must specify a Trace property for each one of these events. The value in the Trace property is a list of names. The first names a trigger, and the rest name the segments, in the proper sequence. Each name consists of three dot-separated <identifier>s. The third names the trigger or segment, the second names the RTLoad player in which the trigger/segment is defined, and the first names the component instantiation in which the RTLoad player is defined.

Role types

A role of the following type can be legally defined in the protocol of a connector of type RTScheduler:

Load

the total execution time that a single SchedProcess component places on the CPU while executing code associated with a particular event

Properties

The following properties can be legally included in the property list of a connector of type RTScheduler. Properties legal in a <protocol> property list have a P in parentheses after the property name; those legal in an <instantiation> or <establish> property list have an I:

InstFormals (P)

The syntax for an InstFormals property in a connector of type
RTScheduler is a comma-separated list of <parameter>s enclosed in parentheses. A <parameter> consists of an <identifier>, followed by a `=', followed by a <complex string> or the language keyword NODEFAULT. A <complex string> is a simple "string" or a sequence of "string"s concatenated by the `&' character:

INSTFORMALS (first_parameter = "an initial value",

second_parameter = "a much" &
"longer initial value that " &
"will not fit on one line",
third_parameter = NODEFAULT)

Algorithm (P, I)

The syntax for an Algorithm property in a connector of type RTScheduler 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, and surrounded by parentheses:

ALGORITHM (rate_monotonic)
ALGORITHM ("fixed_priority")

If no Algorithm property is specified in the property list of an RTScheduler connector definition or instantiation, the default value is "rate_monotonic".

Processor (P, I)

The syntax for the Processor property in a connector of type
RTScheduler is an <identifier> or "string", surrounded by parentheses:

PROCESSOR ("testbed.xx.cmu.edu")
PROCESSOR (my_hostname)

If no Processor property is specified in the property list of an RTScheduler connector definition or instantiation, the default value is the current processor name (i.e., the name of the processor that the UniCon compiler executes on while compiling/building the system). It is the name returned by the Unix "hostname" command executed compilation/building of the system.

Trace (I)

The syntax for the Trace property in a connector of type
RTScheduler is a comma-separated list containing a trigger name followed by one or more segment names, surrounded by parentheses. Trigger and segment names contain three dot-separated
<identifier>s. The first <identifier> names a component instantiation, the second names an RTLoad player in the component instantiation named by the first, and the third names a trigger or segment in the RTLoad player named by the second:

TRACE (process_one.load.trigger,

process_one.load.segment_one,
process_two.load.segment,
process_one.load.segment_two)

Semantic Checks

The following are the semantic checks made in connections of type RTScheduler:

If the Algorithm property in an RTScheduler connection specifies a rate_monotonic algorithm, then at least one Trace property must also be specified in the connection.
Every RTScheduler connection must be intended for a different processor (i.e., specified with the Processor property).
Every SchedProcess component involved in an RTScheduler connection must be designated to run on the same processor that the RTScheduler is intended for (Warning only).
Every SchedProcess component involved in an RTScheduler connection must not be involved in any other RTScheduler connection (i.e., it must only be involved in one such connection).
Every SchedProcess component instantiated in a system must be involved in an RTScheduler connection.
If an RTScheduler connection specifies more than one Trace property such that more than one trigger from the same SchedProcess component is used, then the SchedProcess must not be a server process because the system designer is attempting to assign more than one period to a process (and server processes have no periods - they run continuously).

Implementation Semantics

An RTScheduler connector is realized in the final system by the interaction of processes competing for the processor resource via some scheduling algorithm implemented by the real-time operating system. Real-time scheduling requires each process to be initialized with certain properties, such as period and priority. The UniCon compiler generates C language initialization source code for each SchedProcess involved in an RTScheduler connection. This code is a C "main" program that creates and initializes the process in the real-time environment with the specified period and priority and performs initialization required to support remote procedure calls between it and other processes.

In addition to the process initialization code, the UniCon compiler generates a program executable that initializes the real-time scheduler in the operating system environment prior to the creation of the processes in the application.

Lastly, the UniCon compiler generates a Unix shell script that invokes the scheduler initialization program and starts the application processes at run-time, in the correct order (i.e., all processes providing services via remote procedure call are started before the processes that require these services).

All of this is done automatically. No additional support is required to be implemented by the system designer in order to realize an RTScheduler connector.

Analysis
Support

As mentioned above, when the algorithm of choice for an RTScheduler connection is the rate monotonic algorithm, UniCon automatically generates input for a tool that will perform a rate monotonic analysis (RMA) of the schedulability of the processes that will run on the particular processor. UniCon extracts the period, priority, and execution time data for each process from the appropriate property lists in the associated component definition, formats it, and writes it to a file with the name "RMA_<processor_name>". <processor_name> is the name of the processor as it appears in the Processor property in the RTScheduler connector instantiation. The RMA tool analyzes the data and returns a result indicating whether or not the schedule is achievable. It is achievable if each process can complete its work within its given period (i.e., before it must be activated to run again).

The RMA tool is an Excel spreadsheet program that runs on IBM PCs, so for now the invocation of the tool is carried out manually.