MAST

Modeling and Analysis Suite for Real-Time Applications

Introduction
MAST elements
Processing Resources
Shared Resources
Scheduling Servers
Operations
Transactions
Performing the Analysis

Introduction

MAST is an open source set of tools that enables modeling real-time applications and performing timing analysis of those applications. MAST is still under development. Its analysis tools include worst-case response time schedulability analysis, calculation of blocking times, calculation of slack times, optimized priority assignment, and simulation tools.

This document describes how to use the MAST suite through a guided simple example. The example is a real-time application with four tasks. Three of them are periodic tasks that synchronize through the use of two shared resources. The fourth task is an aperiodic sporadic task. Although MAST support multiprocessor and distributed systems, this simple example runs all its tasks concurrently in the same CPU. The figure below shows the main timing requirements of the task set.

In this figure T represents the period of a task, and C its worst-case execution time (i.e., the time it takes to execute it supposing that no other tasks are running). The numbers inside the shared resources are the worst-case execution times of the corresponding protected operations (Read, Write, Send, and Receive). We can see that the deadlines of the periodic tasks are equal to their periods.

For this example, we want to perform the worst-case response time analysis. This implies calculating the worst case response times (or finalization times) of all tasks, taking into account that they all run concurrently, and taking into account the effects of synchronization for using the shared resources in a mutually exclusive way, and the overheads introduced by the task context switching.

MAST Elements

The elements that we need to define to build the MAST model of this application are:

Processing resources: Just one CPU
Shared Resources: Representing the two resources: Data Server, and Communication Server, and the associated mutually exclusive lock, with is real-time synchronization protocol for avoiding priority inversions
Scheduling Servers: With the scheduling parameters of each of the four tasks (i.e., their priorities)
Operations: on the one hand, the protected operations of the shared resources; on the other hand, the operations executed by each of the tasks; each operation defines its worst-case execution time
Transactions: they define the events that arrive at the system, and the activities that these events release; they also define the timing requirements imposed on each activity

Processing Resources

The MAST description starts with the processing resources, which can be fixed priority processors, or fixed priority networks. In this case, we only have one processor, that we will call CPU_1. We can add the worst-case context switch times to take into account the associated overhead. Other more complex overhead modeling possibilities are included in the MAST model, but we will just use the context switch overhead, for simplicity. The description of this section of the MAST model is:

Processing_Resource (
        Type                    => Fixed_Priority_Processor,
        Name                    => CPU_1,
        Worst_Context_Switch    => 0.25);

Shared Resources

The next objects in the MAST description are the shared resources. In our example we have the Data_Server, and the Comm_Server. We have to indicate the synchronization protocol to use, which can be Priority_Inheritance_Resource, or Immediate_Ceiling_Resource. In this case let's assume that we are using the Immediate Priority Ceiling Protocol (also called Ceiling_Locking in Ada, or PRIO_PROTECT in POSIX).

For this protocol we can specify the priority ceiling of each resource, or we can let the tool calculate the optimum ceilings. We will do the latter. Therefore, the shared resources section will look like:

Shared_Resource (
        Type    => Immediate_Ceiling_Resource,
        Name    => Data_Server);

Shared_Resource (
        Type    => Immediate_Ceiling_Resource,
        Name    => Comm_Server);

Scheduling Servers

The scheduling servers are the tasks or threads of control that execute the different activities in the system. They contain a reference to the processor used, and the scheduling policy and parameters for that task.

Among the different scheduling policies that are available, we will chose the simplest one: Fixed_Priority_Policy. For this policy, the only scheduling parameter is the priority. For our task set, we will use the deadline monotonic priority assignment, which is optimum for tasks with deadlines at or before their periods. In this assignment, the highest priority is assigned to the shortest deadline. Therefore, we will assign priorities as follows:

Task Deadline Priority

Control_Task 100 3

Planning_Task 150 2

Status_Task 350 1

Emergency 6 4

With this priority assignment, the scheduling servers section will be described as follows:

Scheduling_Server (
        Type                            => Fixed_Priority,
        Name                            => Control_Task,
        Server_Sched_Parameters         => (
                Type            => Fixed_Priority_policy,
                The_Priority            => 3),
        Server_Processing_Resource      => CPU_1);

Scheduling_Server (
        Type                            => Fixed_Priority,
        Name                            => Planning_Task,
        Server_Sched_Parameters         => (
                Type            => Fixed_Priority_policy,
                The_Priority            => 2),
        Server_Processing_Resource      => CPU_1);

Scheduling_Server (
        Type                            => Fixed_Priority,
        Name                            => Status_Task,
        Server_Sched_Parameters         => (
                Type            => Fixed_Priority_policy,
                The_Priority            => 1),
        Server_Processing_Resource      => CPU_1);

Scheduling_Server (
        Type                            => Fixed_Priority,
        Name                            => Emergency,
        Server_Sched_Parameters         => (
                Type            => Fixed_Priority_Policy,
                The_Priority            => 4),
        Server_Processing_Resource      => CPU_1);

Operations

In the first place, we will describe the operations associated with the protected operations Read, Write, Send, and Receive, all associated with the mutually exclusive use of shared resources. For each operation, we have to describe its name, worst case execution time, and the shared resources that are used. In our case each protected operation uses a single resource only. The description is:

Operation (
        Type                      => Simple,
        Name                      => Read,
        Worst_Case_Execution_Time => 2,
        Shared_Resources_List     => (Data_Server));

Operation (
        Type                      => Simple,
        Name                      => Write,
        Worst_Case_Execution_Time => 20,
        Shared_Resources_List     => (Data_Server));

Operation (
        Type                      => Simple,
        Name                      => Send,
        Worst_Case_Execution_Time => 10,
        Shared_Resources_List     => (Comm_Server));

Operation (
        Type                      => Simple,
        Name                      => Receive,
        Worst_Case_Execution_Time => 10,
        Shared_Resources_List     => (Comm_Server));

Now we can define the operations that are executed by each of the four tasks. The operations that use protected operations (also called critical sections) are defined as enclosing operations (because they encloses the critical sections together with some other code). The Emergency task does not invoke any of the protected operations, and thus is defined as a simple operation. The description is:

Operation (
        Type                      => Enclosing,
        Name                      => Control,
        Worst_Case_Execution_Time => 20,
        Composite_Operation_List  => (Read,Send));

Operation (
        Type                      => Enclosing,
        Name                      => Planning,
        Worst_Case_Execution_Time => 40,
        Composite_Operation_List  => (Write));

Operation (
        Type                      => Enclosing,
        Name                      => Status,
        Worst_Case_Execution_Time => 100,
        Composite_Operation_List  => (Receive));

Operation (
        Type                      => Simple,
        Name                      => Emergency,
        Worst_Case_Execution_Time => 5);

Transactions

And the final part of the MAST description corresponds to the transactions. A MAST transaction is a graph that shows the flow of events in the system, and the activities that each event releases. Very complex graphs are possible, to represent complex event synchronization patterns; but in our example we only have simple transactions, each with one external input event, one output event, and just one activity, that corresponds to one of the four tasks in the example. The following figure shows a diagram of the four transactions.

In the description of each transaction there are three groups of data that we need to specify:

External events: each with its name, type, and timing parameters. In our case, three of the external events are periodic, while the fourth is a sporadic event.
Internal events: each with its name, and the timing parameters associated with their generation. We have four internal events, each generated at the output of each of the four activities or tasks. All have hard global deadlines as timing requirements. Global deadlines are referred to an external event, as we will see in the description.
Event handlers: they are the elements that handle the events. In our example all the event handlers are activities, that represent the execution of an operation, by a given task. The distinction between an activity and an operation is that the activity is an instance of an operation executed by a given task. For example, we could have a procedure written just once (an operation), but we could create two or three tasks that could be executing that procedure, and thus we would have three activities or instances of the operation. In our case, each activity describes its input event, its output event, its scheduling server, and its operation.

The description of the transactions is:

Transaction (
        Type => Regular,
        Name => Control_Task,
        External_Events => (
                (Type   => Periodic,
                 Name   => E1,
                 Period => 100)),
        Internal_Events => (
                (Type   => regular,
                 name   => O1,
                 Timing_Requirements => (
                         Type             => Hard_Global_Deadline,
                         Deadline         => 100,
                         Referenced_Event => E1))),
        Event_Handlers => (
                (Type               => Activity,
                 Input_Event        => E1,
                 Output_Event       => O1,
                 Activity_Operation => Control,
                 Activity_Server    => Control_Task)));

Transaction (
        Type    => Regular,
        Name    => Planning_Task,
        External_Events => (
                (Type   => Periodic,
                 Name   => E2,
                 Period => 150)),
        Internal_Events => (
                (Type   => regular,
                 name   => O2,
                 Timing_Requirements => (
                         Type             => Hard_Global_Deadline,
                         Deadline         => 150,
                         Referenced_Event => E2))),
        Event_Handlers => (
                (Type               => Activity,
                 Input_Event        => E2,
                 Output_Event       => O2,
                 Activity_Operation => Planning,
                 Activity_Server    => Planning_Task)));

Transaction (
        Type => Regular,
        Name => Status_Task,
        External_Events => (
                (Type   => Periodic,
                 Name   => E3,
                 Period => 350)),
        Internal_Events => (
                (Type   => regular,
                 name   => O3,
                 Timing_Requirements => (
                         Type             => Hard_Global_Deadline,
                         Deadline         => 350,
                         Referenced_Event => E3))),
        Event_Handlers => (
                (Type               => Activity,
                 Input_Event        => E3,
                 Output_Event       => O3,
                 Activity_Operation => Status,
                 Activity_Server    => Status_Task)));

Transaction (
        Type => Regular,
        Name => Emergency,
        External_Events => (
                (Type => Sporadic,
                 Name => E4,
                 Min_Interarrival => 50)),
        Internal_Events => (
                (Type => regular,
                 name => O4,
                 Timing_Requirements => (
                         Type             => Hard_Global_Deadline,
                         Deadline         => 6,
                         Referenced_Event => E4))),
        Event_Handlers => (
                (Type               => Activity,
                 Input_Event        => E4,
                 Output_Event       => O4,
                 Activity_Operation => Emergency,
                 Activity_Server    => Emergency)));

Performing the Analysis

The described MAST objects are all stored in a text file called controller.txt. Press here to view this file.

Once we have described the application in the MAST description file, we can execute the analysis tool to determine the worst-case response time for each or the tasks. By comparing these response times with the timing requirements, we can determine if the system is schedulable or not.

In our example, all the analysis tools that we have will provide the same exact response time results. They provide different results only for distributed systems, because the offset-based techniques are more exact than the holistic analysis. For distributed systems, they all provide upper bounds to the real response times.

The simplest way to invoke the analysis tool is through the "gmast" graphical driver. A screenshot of this graphical tool is shown next:

On the left hand side of the gmast window we can choose the analysis tool to use (The Offset_Based tool is selected in the figure), and the directory and input file to use. The "File..." button allows us browsing the directory searching for the desired file. In the figure we can see that the file "controller.txt", containing the MAST description of our example, is selected. We can also specify where the output will go to. If we leave it blank, it will go to the standard output. Otherwise, it will be stored in the specified file, in the same directory as the input file.

On the right hand side we can choose the options used for the tool. We have chosen "Calculate Ceilings", because we did not set the priority ceilings of the shared resources. In addition, we have requested calculation of the slacks. The latter will cause the tool to provide the transaction slack of each transaction, as well as the system slack. The transaction slack is the percentage of execution time that we can add to all the operations of the transaction while still keeping the system schedulable (or, if negative, the percentage by which we need to reduce the execution times to make the system schedulable). The system slack is the percentage by which we can increase (or decrease) the execution times of all the operations in the system while keeping the system schedulable (or to make it schedulable). The slacks are a very important piece of data, because they tell us how close or how far we are from becoming unschedulable (or schedulable).

Once we have set all the desired options, we press the "GO" button, and the analysis tool is invoked. In this case, the results will be stored in file "controller.out". By looking at this file, we can determine the following response times and slacks for our system:

Transaction Worst-Case Response Time Slack

Control Task 46.0 39.84%

Planning Task 82.0 29.69%

Status Task 276.0 23.44%

Emergency 5.5 9.38%

And the system slack is 8.59%. We can see that the system is schedulable. The emergency task has very little possibility of growth, but one of the other tasks may grow its execution time between 23 and 39%.

More Examples

You can now try analyzing the examples found with the MAST distribution. You will find the results of these examples in mast-examples.html.