The Cheddar AADL Property sets (Release 2.x)

LISyC technical report number singhoff-03-07

First publication : february 2007
Last update : July the 7th, 2008
Frank Singhoff

Abstract :

This report describes the property sets which have to be used to perform performance analysis of AADL models with Cheddar.

1. Introduction

2. The Cheddar Property set

3. An `AADL_Project` property set for Cheddar

4. Defining property sets for user-defined thread dispatching protocols and scheduling protocols

5. Conclusion

6. Bibliography

1. Introduction

This report describes the property sets which have to be used to perform performance analysis of AADL models with Cheddar. The Cheddar framework provides analysis tools based on the real time scheduling theory [1] and based on the queueing system theory [2]. The framework also provides extensible simulation services [3]. Some examples of the use of such analysis tools with AADL can be read in [5] and [6]. Furthermore, the reader can find a brief bibliography section at the end of this report in order to have other details on the relationships between AADL and Cheddar.

This report is organized as follows. The section 2 lists all properties specifically defined for Cheddar. All these properties are defined in a set called Cheddar_Properties. In section 3, we describe the standard AADL properties customized for the use of Cheddar. Such customized properties are defined in the standard AADL_Project property set. The AADL properties for Cheddar can be extended in the case of specifications of user-defined thread dispatching protocols and scheduling protocols. The user-defined property extensions are shortly described in section 4. Finally, we conclude in section 5.

2. The Cheddar Property set

Cheddar implements the usual feasibility tests and simulation tools in the context of concurrent real time applications. To run such analysis methods, an AADL specification has to provide extra information on AADL process, processor, data and thread components. This extra information is specified by extra properties saved in a file called Cheddar_Properties.aadl. The table below describes all properties of this file. For each property, the table provides the meaning of the property and its default value, if a default value exists.

Scheduler_Quantum : inherit Time
applies to (processor,process);

This property specifies the quantum of a given processor. The quantum is a maximum bound on the delay a thread can held the processor without beeing preempted. A quantum is typically used in time sharing scheduling and in POSIX 1003.1b scheduling (with the SCHED_RR policy for example). The quantum can also be used with any Cheddar user-defined schedulers. If the quantum is not specified for a given processor, the Cheddar scheduling simulation engine assumes that the quantum has a positive infinitive value.

Preemptive_Scheduler : aadlboolean
applies to (processor,process);

This property specifies if the processor can preempt a thread during its execution. By default, if this property is not specified, the processor owns a preemptive scheduler.

Scheduling_Protocol : list of Supported_Scheduling_Protocols
applies to (processor,process);

This property is the same that the one provided by the standard AADL property set, except that it can be applied on processes in order to model hierarchical schedulers.

Data_Concurrency_State : aadlinteger
applies to (data);

This property specifies the scheduling simulator initial state of a data. From the scheduling simulator point of view, a data is seen as a semaphore. A semaphore contains a counter which has to be first initialized before the semaphore can be used. The Data_Concurrency_State property provides such an initialization. If Data_Concurrency_State provides a positive value, the first thread which requires the access to the data will not be blocked. If Data_Concurrency_State initializes the counter to zero or to a negative value, the thread will be blocked. By default, if this property is not specified, the data semaphore counter is initialized to 1.

Fixed_Priority : aadlinteger 0..255
applies to (thread, thread group, data);

This property specifies the priority of a thread. This priority is fixed : it means that the thread priority does not change during the execution of the system, except when the thread get the access to a data supporting a protocol such as PCP or PIP. Such a property may be used by fixed priority schedulers such as Rate Monotonic, Deadline Monotonic, POSIX 1003.1b scheduler or any user-defined scheduler. There is no default value for such a property : if this property is not specified, the thread fixed priority is undefined. The priority levels can be customized at Cheddar compilation time. In the distributed implementation of Cheddar :

255 is the highest fixed priority.
0 is the lowest fixed priority.

Is_Preemptible : aadlboolean
applies to (thread, thread group);

This property specifies if a thread can be preempted during its execution time by a scheduler in order to run an other thread. By default, if this property is not specified, the thread is supposed to be preemptible.

POSIX_Scheduling_Policy : enumeration (SCHED_FIFO, SCHED_RR, SCHED_OTHERS)
applies to (thread, thread group);

The POSIX_Scheduling_Policy property is used with the POSIX_1003_HIGHEST_PRIORITY_FIRST_PROTOCOL or any user-defined scheduling protocols. Such a property specifies the policy associated to a given thread. The policy may be either SCHED_FIFO, SCHED_RR or SCHED_OTHERS. In a POSIX 1003 system, the policy allows the scheduler to choose the thread to run when several threads have the same fixed priority (specified with the Fixed_Priority property). If a thread does not define the POSIX_Scheduling_Policy property, it has by default the SCHED_FIFO policy. In the current implementation of Cheddar, the POSIX policy and the POSIX fixed priority behavior is similar to the one found on a Linux machine :

SCHED_FIFO implements a FIFO scheduling protocol : a thread stays on the processor until it has terminated or until a highest priority thread is released.
SCHED_RR is similar to SCHED_FIFO except that the quantum is used. At the end of the quantum, the running thread leaves the processor.
SCHED_OTHERS implements a time sharing scheduling. A thread with a SCHED_OTHERS policy must have a fixed priority equal to zero.

Dispatch_Jitter : inherit Time
applies to (thread, thread group);

This property specifies a maximum bound on the lateness of a thread dispatching. In the case of a periodic thread for instance, the thread is supposed to be dispatched according to a fixed delay called the period. However, for many reasons, a periodic thread dispatching event can be delayed. The Dispatch_Jitter property can be used to specify such a delay. The Dispatch_Jitter property can be specified on any thread which can be dispatched several times (ie. Periodic, Sporadic, Poisson_Process or User_Defined threads).

Bound_On_Data_Blocking_Time : inherit Time
applies to (thread, thread group);

This property specifies the maximum duration a thread has to wait for the access to a protected data. Such delay is computed with feasibility tests according to the data access procotol or can be computed by analysis of a scheduling simulation. Bound_On_Data_Blocking_Time is also used to compute the worst case response time of a thread (with feasibility tests).

Dispatch_Absolute_Time : inherit Time
applies to (thread, thread group);

This property specifies the very first arrival time of the thread. By arrival time, we mean the first dispatching time of the thread. Cheddar provides repetitive AADL threads and non repetitive threads. Repetitive threads such as Periodic threads, are dispatched several times. The dispatch absolute time specifies the first dispatching time of repetitive threads. Non repetitive threads such as Background thread are dispatched only one time. Such a unique dispatching time is also specified with the dipatch absolute time. In the context of real time scheduling simulation, for Background threads, the dispatch absolute time is usually randomly generated. A dispatch absolute time equal to zero is required for some feasibility tests.

Criticality : aadlinteger
applies to (thread, thread group);

This property specifies the criticality level of a thread. This property is used by the MAXIMUM_URGENCY_FIRST_BASED_ON_LAXITY_PROTOCOL and MAXIMUM_URGENCY_FIRST_BASED_ON_DEADLINE_PROTOCOL scheduling protocols. Such a property can also be used by any user-defined scheduling protocols.

Dispatch_Offset_Value_k : aadlinteger
applies to (thread, thread group);

This property is associated to the Dispatch_Offset_Time_k property. Dispatch_Offset_Time_k and Dispatch_Offset_Value_k allow the user to force a scheduling protocol to delay the dispatching of a thread. Such properties can be usefull for the design and the test of new user-defined scheduling protocols. The Dispatch_Offset_Time_k property specifies the thread dispatching event number to be delayed and the Dispatch_Offset_Value_k property specifies the delay to apply at thread dispatching. Several (Dispatch_Offset_Time_k,Dispatch_Offset_Value_k) property couples can be expressed, where k is the number of couples. The number of couples can be customized at Cheddar compilation time.

Dispatch_Offset_Time_k : inherit Time
applies to (thread, thread group);

This property is associated to the Dispatch_Offset_Value_k property. See the Dispatch_Offset_Value_k property for explanation.

Dispatch_Seed_Value : aadlinteger
applies to (thread, thread group);

This property specifies the seed value which is used by the Cheddar simulator engine. To compute a scheduling with Background, Poisson_Process, Sporadic or User_Defined threads, the simulator engine has to generate random dispatching time. Such random generator is initialized with the Dispatch_Seed_Value property. If this property is ommited, the seed random generator is initialized to zero : it means that several simulations of an AADL specification will lead to the same computed scheduling.

Dispatch_Seed_is_Predictable : aadlboolean
applies to (thread, thread group);

This property specifies how the seed must be generated. The seed is used by the Cheddar simulator engine. To compute a scheduling with Background, Poisson_Process, Sporadic or User_Defined threads, the simulator engine has to generate random dispatching time. The Dispatch_Seed_is_Predictable property specifies how the seed has to be initialized. If Dispatch_Seed_is_Predictable is true, the seed is initialized with the same value for all scheduling simulation. In this case, the successive simulations of an AADL specification lead to the same computed scheduling. If you plan to run several simulations of an AADL specification and if you plan to generate different scheduling for each simulation, then, the Dispatch_Seed_is_Predictable property has to be initialized with false. If this property is ommited, the seed is randomly initialized.

Critical_Section : list of aadlstring
applies to (process, thread, data);

This property specifies the list of critical sections of a process, a thread or a data. This property has no default value. By critical section, we mean the time interval a thread access to a shared data. Critical sections may be used by feasibility tests to compute thread blocking times on shared data and worst case thread response times. They also may be used to compute the scheduling simulation. The Critical_Section property is an ordered list which expresses shared data access as follows :

Critical_Section => "D1", "T1", "start1", "end1", "D2", "T2", "start2", "end2" ... ;

means that the thread T1 requires the access to the data D1 from the start1 unit of time of its execution time, to the end1 unit of time of its execution time. This example also specifies that the thread T2 requires the access to the data D2 from the start2 unit of time of its execution time, to the end2 unit of time of its execution time.

Source_Global_Text_Size : Size
applies to (process);

This property specifies the size of the text memory segment of the process. This property can be used in order to perform memory footprint analysis.

Source_Global_Stack_Size : Size
applies to (process);

This property specifies the size of the stack memory segment of the process. This property can be used in order to perform memory footprint analysis.

Source_Global_Data_Size : Size
applies to (process);

This property specifies the size of the data memory segment of the process. This property can be used in order to perform memory footprint analysis.

Source_Global_Heap_Size : Size
applies to (process);

This property specifies the size of the heap memory segment of the process. This property can be used in order to perform memory footprint analysis.

Thread_Precedencies : list of aadlstring
applies to (system);

This property specifies the list of thread precedences of an AADL specification. This property has no default value. It is composed of an ordered list of thread name. Such a thread precedencies do not express any data exchange between thread but only contraints related to the scheduling of the threads : such a property expresses thread precedencies without event or event data port. For example, the following specification :

Thread_Precedencies => "a", "b", "c", "d" ...  ;

means that the thread a has to be executed before the thread b and that the thread c has to be executed before the thread d.

Source_Text : inherit list of aadlstring
applies to (thread, process, processor);

This property specifies the name of .sc files. This property can contain several .sc file names. In this case, the file names are separeted by a comma. The .sc files contain pieces of code which can be interpreted by the scheduling engine of Cheddar. These part of code are part of user-defined schedulers. With such .sc files, one can design and perform simulations with specific thread dispatching protocols or specific scheduling protocols. See [3] and [4] for details.

3. An `AADL_Project` property set for Cheddar

The Cheddar property set assumes that the AADL_Project property set contains the following Cheddar specific declarations :

property set AADL_Project is
...
	Supported_Dispatch_Protocols : type enumeration (
		Periodic, 
		Background, 
		Poisson_Process, 
		Sporadic, 
		User_Defined);
	Supported_Scheduling_Protocols : type enumeration (
		COMPILED_USER_DEFINED_PROTOCOL, 
		AUTOMATA_USER_DEFINED_PROTOCOL, 
		PIPELINE_USER_DEFINED_PROTOCOL, 
		USER_DEFINED_PROTOCOL, 
		EARLIEST_DEADLINE_FIRST_PROTOCOL, 
		LEAST_LAXITY_FIRST_PROTOCOL, 
		RATE_MONOTONIC_PROTOCOL, 
		DEADLINE_MONOTONIC_PROTOCOL, 
		ROUND_ROBIN_PROTOCOL, 
		TIME_SHARING_BASED_ON_WAIT_TIME_PROTOCOL, 
		POSIX_1003_HIGHEST_PRIORITY_FIRST_PROTOCOL, 
		D_OVER_PROTOCOL, 
		MAXIMUM_URGENCY_FIRST_BASED_ON_LAXITY_PROTOCOL, 
		MAXIMUM_URGENCY_FIRST_BASED_ON_DEADLINE_PROTOCOL, 
		TIME_SHARING_BASED_ON_CPU_USAGE_PROTOCOL, 
		NO_SCHEDULING_PROTOCOL, 
		HIERARCHICAL_CYCLIC_PROTOCOL, 
		HIERARCHICAL_ROUND_ROBIN_PROTOCOL, 
		HIERARCHICAL_FIXED_PRIORITY_PROTOCOL);
	Supported_Concurrency_Control_Protocols : type enumeration (
		No_Protocol, 
		Priority_Ceiling_Protocol, 
		Immediate_Priority_Ceiling_Protocol, 
		Priority_Inheritance_Protocol);
...
end AADL_Project;

The Supported_Dispatch_Protocols enumeration specifies the list of thread dispatching protocols currently available with Cheddar. With the Cheddar 2.x release, the available protocols are :

Background. This kind of thread arrives in the system at a time specified by the property Dispatch_Abosolute_Time, run a job and leaves the system.
Periodic. This kind of thread periodically runs a job. A periodic thread has a start time (specified with the Dispatch_Abosolute_Time property). Its period (see the Period property) stores the fixed delay between two successive thread wakeup times.
Poisson process. As periodic thread, a poisson process thread periodically runs a job. With a poisson process thread, the Period property stores the average delay between two successive threads wakeup times. The effective delay between two wakeup times is computed with an exponential random generator.
Sporadic : threads are awoken up with a minimal inter-waking up period delay. The miminum delay is stored in the Period property.
User_Defined. Such thread dispatching protocol is defined by the user. See [3] and [4] for details.

The Supported_Concurrency_Control_Protocols enumeration specifies the list of scheduling protocols currently available with Cheddar. A scheduling protocol may be specified for any processor but also for processes if the binded processor owns a hierarchical scheduling protocol [5]. The Cheddar Release 2.x scheduling protocols are :

NO_SCHEDULING_PROTOCOL. This means that the processor or the process does not have a scheduling protocol. This is the scheduling protocol for a process or a processor if the Scheduling_Protocol property is not specified.
EARLIEST_DEADLINE_FIRST_PROTOCOL. Threads can be periodic or not and are scheduled according to their deadline which is computed from the Deadline, the Period and the Dispatch_Absolute_Time properties.
LEAST_LAXITY_FIRST_PROTOCOL. Threads can be periodic or not and are scheduled according to their laxity which is computed from the Deadline, the Period and the Dispatch_Absolute_Time properties.
RATE_MONOTONIC_PROTOCOL. Threads have to be periodic, and their deadline must be equal to their period. Threads are scheduled according to their Period property.
DEADLINE_MONOTONIC_PROTOCOL, Threads have to be periodic and are scheduled according to their Deadline property.
POSIX_1003_HIGHEST_PRIORITY_FIRST_PROTOCOL, Threads can be periodic or not. Threads are scheduled according to the priority and the policy of the threads. This scheduling protocol shares the processor according to the Fixed_Priority, the POSIX_Scheduling_Policy and the Dispatch_Absolute_Time properties.
TIME_SHARING_BASED_ON_WAIT_TIME_PROTOCOL and TIME_SHARING_BASED_ON_CPU_USAGE_PROTOCOL. These two schedulers provide a way to share the processor as on a time sharing operating system. With the first scheduler, the more a ready thread waits for the processor and the more its priority increases. With the second scheduler, the more a ready thread runs and the more its priority decreases.
ROUND_ROBIN_PROTOCOL. The processor is regulary shared between all the threads. A quantum (see the Scheduler_Quantum property) must be given.
MAXIMUM_URGENCY_FIRST_BASED_ON_LAXITY_PROTOCOL and MAXIMUM_URGENCY_FIRST_BASED_ON_DEADLINE_PROTOCOL. Such scheduling protocols are based on an hybrid priority assignment : a thread priority is made of a fixed part and a dynamic part.
D_OVER_PROTOCOL. This scheduler is an EDF like but which works fine when the processor is over-loaded. When the processor is over-loaded, D-Over is always able to predict which thread that will miss its deadline (in contrary to EDF).
COMPILED_USER_DEFINED_PROTOCOL, AUTOMATA_USER_DEFINED_PROTOCOL, PIPELINE_USER_DEFINED_PROTOCOL and USER_DEFINED_PROTOCOL. These scheduling protocols are the cheddar's User-defined schedulers. These schedulers allow users to define their own scheduler into Cheddar (see [4]). The scheduling protocols may define their own properties in order to perform the scheduling simulation (see section 4 of this report).
Finally HIERARCHICAL_CYCLIC_PROTOCOL, HIERARCHICAL_ROUND_ROBIN_PROTOCOL and HIERARCHICAL_FIXED_PRIORITY_PROTOCOL. These scheduling protocols implement some examples of hierarchical schedulers [7]. These protocols provide experimental analysis tools. Use them with care !

The Supported_Concurrency_Control_Protocols enumeration specifies the list of data access protocol currently available with Cheddar. With the Cheddar 2.x release, the available protocols are :

No_Protocol. With No_Protocol, no particular protocol is used when a data is accessed by threads. At simulation time, the data is supposed to work as a semaphore if No_Protocol is used. This protocol is also the default protocol of a data component if the Concurrency_Control_Protocol property is not specified.
Priority_Inheritance_Protocol. With this protocol, the Cheddar scheduling simulator increases the priority of a lower priority thread which blocks a higher priority thread.
Priority_Ceiling_Protocol. This protocol applies the priority inheritance of Priority_Inheritance_Protocol and introduces a new thread blocking condition in order to avoid deadlock and to decrease thread blocking time.
Immediate_Priority_Ceiling_Protocol. This last protocol is similar to Priority_Ceiling_Protocol.

For further reading about the protocols specified by the Supported_Concurrency_Control_Protocols, the Supported_Dispatch_Protocols and the Supported_Concurrency_Control_Protocols enumeration, please see [4].

4. Defining property sets for user-defined thread dispatching protocols and scheduling protocols

For AADL specifications modeling thread dispatching protocols or scheduling protocols which do not exist in the current AADL standard, a user may define its own thread/processor/process properties. Such user-defined properties have to be defined in the User_Defined_Cheddar_Properties AADL property set. The property set has to be saved in a file called User_Defined_Cheddar_Properties.aadl. By default, this AADL file does not define any property and provides the following content :

property set User_Defined_Cheddar_Properties is
	Dummy_User_Defined_Cheddar_Properties : aadlboolean
		applies to (thread, thread group);
end User_Defined_Cheddar_Properties;

If you plan to extend the list of thread property by an ARINC 653 partition number [8], for example, you can specify such an extension as follows :

property set User_Defined_Cheddar_Properties is
	thread_partition : aadlinteger
		applies to (thread, thread group);
end User_Defined_Cheddar_Properties;

and then, use the new property :

thread implementation T1.Impl
	properties
		Dispatch_Protocol => Periodic;
		User_Defined_Cheddar_Properties::thread_partition =>  1;
		Compute_Execution_Time =>  5 ms ..  5 ms;
		Cheddar_Properties::Fixed_Priority =>  5;
		Deadline  =>  10 ms;
		Period =>  10 ms;
end T1.Impl;

If you meet such property extension mechanisms, the Cheddar scheduling simulator will be able to read the new property that you will define (See [4] for details).

5. Conclusion

This report gives an overview of the properties which have to be used in order to run Cheddar on AADL specifications. This report does not describe the analysis tools provided by Cheddar and the way they are supposed to be used. Futher readings about Cheddar and AADL can be found in [2], [3] and [4]. Some examples of use of Cheddar and AADL can also be found from the Cheddar Web page.

6. Bibliography

Scheduling in Real-Time Systems. F. Cottet, J. Delacroix, C. Kaiser et Z. Mammeri. Wiley, pp. 282, Wiley, 2002.
Queueing systems : Computer Applications. L. Kleinrock. Wiley-intersciences. 1975.
Cheddar : a Flexible Real Time Scheduling Framework. F. Singhoff, J. Legrand, L. Nana, L. Marcé. ACM SIGAda Ada Letters, volume 24, number 4, pages 1-8. Edited by ACM Press, New York, USA. December 2004, ISSN:1094-3641.
Cheddar Release 2.x User's Guide. Frank Singhoff. LISyC Technical report number singhoff-01-2007, February 2007.
Scheduling and Memory requirement analysis with AADL. F. Singhoff, J. Legrand, L. Nana, and L. Marcé. ACM SIGAda Ada Letters, volume 25, number 4, pages 1-10. Edited by ACM Press, New York, USA, November 2005, ISSN:1094-3641.
Implementing an AADL performance analyzer. F. Singhoff, L. Nana, J. Legrand. Berlin, 22-25 May, 2006, In the DAta Systems in Aerospace Conference (DASIA 2006), European Space Agency Publication Division.
AADL modeling and analysis of hierarchical scheduler. F. Singhoff and A. Plantec. ACM SIGAda Ada Letters, volume 27, number 3, pages 41-50. Edited by ACM Press, New York, USA, November 2007, ISSN:1094-3641.
Arinc Committee. Avionics Application Software Standard Interface . January 1, 1997.

Contact : Frank Singhoff mailto:singhoff@univ-brest.fr
Last update : July the 7th, 2008