Cheddar Release 3.x user's guide

VI. User-defined simulation code : how to run simulations of specific systems.

Usual feasibility tests are limited to only few task models (mainly periodic tasks) and to only few schedulers. When an application built with a particular task activation pattern or scheduled with a particular scheduler has to be checked, feasibility tests are not necessarily available. In this case, the only solution consists in analyzing the scheduling simulation. Cheddar allows the user to design and easily build framework extensions to do simulation of user-defined schedulers or task activation patterns. By easy, we mean quickly write and test framework extensions without a deep understanding of the framework design and of the Ada language. We propose the use of a simple language to describe framework extensions. Framework extensions are interpreted at simulation time. As a consequence, they can be changed and tested without recompiling the framework itself.

Figure 6.1 How a user-defined code is run by the scheduling engine

Figure 6.1 gives an idea on the way the simulation engine is implemented in the framework. Running a simulation with Cheddar is a three-step process.

The first step consists of computing the scheduling : we have to decide which events occur for each unit of time. Events can be allocating/releasing shared resources, writing/reading buffers, sending/receiving messages and of course running a task at a given time. At the end of this step, a table is built which stores all the generated events. The event table is built according to the XML description file of the studied application and according to a set of task activation patterns and schedulers. Usual task activation patterns and schedulers are predefined in the Cheddar framework but users can add their own schedulers and task activation patterns.

In the second step, the analysis of the event table is performed. The table is scanned by "event analyzers" to find properties on the studied system. At this step, some standard information can be extracted by predefined event analyzers (worst/best/average blocking time, missed deadlines ..) but users can also define their own event analyzers to look for ad-hoc properties (ex : synchronization constraints between two tasks, shared resources access order, ...). The results produced during this step are XML formatted and can be exported towards other programs.

Finally, the last step consists of displaying XML results in the Cheddar main window (see Figure 1.4).

VI.1 Defining new schedulers or task activation patterns.

Now, let's see how user-defined schedulers or task activation patterns can be added into the framework. Basically, all tasks are stored in a set of arrays. Each array stores a given information for all tasks (ex : deadline, capacity, start time, ...). The job of a scheduler is to find a task to run from a set of ready tasks. To achieve this job, Cheddar models a scheduler with a 3 stages pipe-line which is similar to the POSIX 1003.1b scheduler (see [GAL 95]). These 3 stages are :

The priority stage. For each ready task, a priority is computed.
The queueing stage. Ready tasks are inserted into different queues. There is one queue per priority level. Each queue contains all the ready tasks with the same priority value. Queues are managed like POSIX scheduling queues : if a quantum is associated with the scheduler, queues work like the SCHED_RR scheduling queueing policy. Otherwise, the SCHED_FIFO queueing policy is applied.
The election stage. The scheduler looks for the non empty queue with the highest priority level and allocates the processor to the task at the head of this queue. The elected task keeps the processor during one unit of time if the designed scheduler is preemptive or during all its capacity if the scheduler is not preemptive.

Defining a new scheduler is simply giving piece of code for some of the pipe-line stages we described above. Each of these stages can be defined by a user without the need to have a deep knowledge of the way the scheduling simulator works. User-defined schedulers are stored in text files. These files are organized in several sections :

The start section. In this section, you may declare variables needed to schedule your tasks. Many variables are already predefined in Cheddar. Some of them are those defined at task/processor/buffer/message definition (ex : period, deadline, capacity ...). This set of predefined variables can be extended with the "Edit/Update Tasks" submenu (see user-defined parameters). The others are managed by the simulator engine and describe the state of tasks/processors/buffers/messages at simulation time. See section VI.5 for a list of all predefined variables. All variables used in a scheduler should have a type. The framework provides two type families : scalar types and arrays. One can define variable with scalar type of double, integer, boolean, string and also of random (a random is a type which allows the user to generate ramdom values). An array is a type which stores one scalar data per task, message, buffer or shared resource. Arrays are declared as usual Ada Table. Vectorial operations can be done on this kind of variable.
The priority section. The section contains the code necessary to compute task priorities. The code given here is called each time a scheduling decision has to be made (at each unit of time for preemptive scheduler and when a task has run during all its capacity for non preemptive scheduler). The code given here can be composed of many differents statements described in section VI.5
The election section. This section just decides which task should receive the processor for next units of time. This section should only contain one return statement.
The task activation section. This section describes how tasks could be activated during a simulation. In Cheddar, 3 kinds of tasks exists : aperiodic tasks which are activated only one time and periodic or poissons process tasks which are activated several times. In the case of periodic tasks, two successive task activations are delayed by an amount of fixed time called period. In the case of poisson process tasks, two successive task activations are delayed by an exponential random delay. The task activation section allows you to define new kinds of task activation patterns (ex : sporadic task, randomly activated task, burst of activations, ...). .

In the sequel, we first give you some simple examples of user-defined schedulers. Then, we explain how to use this kind of scheduler to do scheduling simulation with Cheddar. The list of statements and the list of predefined variables is given at the end of this section.

VI.1 Examples of user-defined schedulers.

In this section, we give some user-defined scheduler examples. We first show that a user-defined scheduler can be built with two kinds of statements : high-level and low-level statements. Second, we present how to add new task parameters with User's defined task parameters.

VI.1.1 Low-level statements versus High-level statements

Now let's see some very simple user-defined schedulers. The most simple user-defined scheduler can be defined like below :

election_section:
     return min_to_index(tasks.period);
end section;

Figure 6.2 a simple Rate Monotonic scheduler

This first example shows you how to give the processor to the task with the smallest period. This scheduler is equivalent to the Rate monotonic implemented into Cheddar. tasks.period is a predefined variable initialized at task definition time by the user. To implement a Rate Monotonic scheduler, no dynamic priorities are computed and no variable is necessary. Then, the scheduler designer does not have to redefine the start and priority sections. The only section which is defined is the election one. The election section contains an unique return statement to inform the scheduling simulator engine which task should be run for the next unit of time. The return statement uses the high level min_to_index operator. This operator scans the task array to find the ready task with the minimum value for the variable tasks.period. In Cheddar, the scheduler designer can use two kinds of statements : high-level and low-level statements. High level statements like min_to_index, hides the data type organization of the scheduling simulator engine. For example, the scheduler designer do not need to give statement into its user-defined scheduler to scan manually the task array. Writing a scheduler with high-level statements is then easy work. On the contrary, low-level statements assume that the user has a deeper idea of the design of the scheduling engine simulator. By the way, these statements are sometimes necessary when the scheduler designer wants to code a too much specific scheduler.

Now let's see how to define an EDF like scheduler :

1 start_section:
2       dynamic_priority : array (tasks_range) of integer;
3 end section;
4
5 priority_section:
6       dynamic_priority := tasks.start_time + tasks.deadline
7          + ((tasks.activation_number-1)*tasks.period);
8 end section;
9
10 election_section:
11       return min_to_index(dynamic_priority);
12 end section;

Figure 6.3 an EDF like scheduler using vectorial operators

EDF is a dynamic scheduler which computes a dynamic priority for each task. This dynamic priority is in fact a deadline. EDF just gives the processor to the task with the shortest deadline. In our example, this deadline is stored in a variable called dynamic_deadline. Since we need one value per task, the type of this variable is integer array. With this example the priority_section is not empty any more and contains (lines 5 to 7) the necessary code to compute EDF dynamic priorities. You should notice that the code in line 6/7 is in fact a vectorial operation : the arithmetic operation to compute the deadline is done for each item of the table dynamic_priority ranging from 1 to nb_tasks (nb_tasks is a static predefined variable initialized by the number of tasks in the current processor). To compute the dynamic priorities of our example, we used many predefined variables :

tasks.deadline, tasks.start_time and tasks.period : they are the deadline, start time and period values given by the user at task definition time (in the window Edit/Update tasks).
tasks.activation_number : it's a variable updated by the simulation engine. The simulator increments this variable each time a periodic or a poisson process task starts a new activation. For instance, if tasks.activation_number(i) is equal to 3, it means that the task i has started its 4th activation.

You can find in VI.5 a list of all predefined variables and all available statements you can used to build your user-defined scheduler.

The example of the Figure 5.3 is built with vectorial operators : each arithmetic operation is done for all the tasks of the system. The scheduler designer does not need to take care of the task array and just gives rules to computed the EDF dynamic deadline. As max_to_index/min_to_index, these statements are High-level ones because they do not required to directly access the data type organization of the scheduling engine of Cheddar (mainly the task arrays).

Now, let's see a third example:

start_section:
      to_run : integer;
      current_priority : integer;

      priority_section:
      current_priority:=0;
      for  i in tasks_range  loop
           if (tasks.ready(i) = true) and (tasks.priority(i)>current_priority)
                      then to_run:=i;
                           current_priority:=tasks.priority(i);
           end if;
      end loop;
end section;

election_section:
      return to_run;
end section;

Figure 6.4 Building a user-defined with low-level statement

This scheduler looks for the highest priority ready task of a processor and is fully equivalent to the scheduler described by :

election_section:
      return max_to_index(tasks.priority);
end section;

Figure 6.5 a HPF scheduler built with hight-level statements

but, in the example of Figure 6.4, the code scans itself the task array to find a ready task to run. To achieve this, the example of Figure 6.4 is built with low-level instructions : a for loop and an if statement. The priority_section is then composed of a loop that tests each task entry. This loop is made with a for statement, a loop that runs the inner statement for each task defined in the task array. Contrary to a high-level implementation, a scheduler made of low-level statements has to carry out more tests. For instance, the example of the Figure 6.4 checks with the ready dynamic variable if tasks are ready at the time the scheduler is called. Low-level scheduler are then more complicated and more difficult to test. The reader will find some tips to help test complicated user-defined schedulers in section VI.3 .

VI.1.2 User-defined scheduler built with User's defined Task Parameters

In the previous examples, the data used to built user-defined schedulers were either static variables initialized at task definition time, either dynamic variables predefined or declared in the start section. A last type of data exists in Cheddar : User's defined task parameters. This kind of data are static ones and are defined at task definition time. User's defined task parameters allow the user to extend the set of static variables. Since they describe new task parameters, User's defined task parameters are table type. User's defined task parameters can be boolean, integer, double or string table type. To define User's defined task parameters, you have to update the third part of the entity task. Use the submenu "Edit/Entities/Software/Task" :

Figure 6.6 Adding an Users's Defined Task Parameter

The example above shows you a system composed of 3 tasks (T1, T2 and T3) where a criticity level is defined. Like usual task parameters, you should give a value to a User's defined task parameter (ex : the criticity level for task T1 is 1) but you also have to set a type to the parameter (integer in our example). When tasks are created, as usually, you can call the scheduling simulation services of Cheddar. The next window is a snapshoot of the resulting scheduling of our example composed of 3 tasks scheduled according to their criticity level. (T2 is the most critical task and T1 the less critical).

Figure 6.7 Scheduling according to a criticity level.

To conclude this chapter, let's have a look to a more complex example of user-defined scheduler which summarises all the features presented before. This example is an ARINC 653 scheduler (see [ARI 97]). An ARINC 653 system is composed of several partitions. A partition is a unit of software and is itself composed of processes and memory spaces. A processor can host several partitions so that two levels of scheduling exist in an ARINC653 system : partition scheduling and process scheduling.

Process scheduling. In one partition, process are scheduled according to their fixed priority. The scheduler is preemptive and always gives the processor to the highiest fixed priority task of the partition which is ready to run. When several tasks of a partition have the same priority level, the oldest one is elected.
Partition scheduling. Partitions share the processor in a predefined way. On each processor partitions are activated according to an activation table. This table is built at design time and defines a cycle of partition scheduling. The table describes for each partition when it has to be activated and how much time it has to run for each of its activation.

Figure 6.8 An example of ARINC 653 scheduling

The Figure 6.8 displays an example of ARINC 653 scheduling (see the XML project file project_examples/arinc653.xml). The studied system is made of 3 tasks hosted by one processor. The processor owns 2 partitions : partition number P0 and partition number P1. The task T1 runs in partition P0 and the two others run in partition P1. Each task has a fixed priority level : the T1 priority is 1, the T2 priority is 5 and the T3 priority is 4. The cyclic partition scheduling should be done so that P0 runs before P1. In each cycle, P0 should be run during 2 units of time and P1 should run during 4 units of time. The user-defined scheduler source code used to compute the scheduling displayed in Figure 6.8 is given below :

start_section:
       partition_duration :  array (tasks_range) of integer;
       dynamic_priority :  array (tasks_range) of integer;
       number_of_partition : integer :=2;
       current_partition : integer :=0;
       time_partition : integer :=0;
       i : integer;

       partition_duration(0):=2;
       partition_duration(1):=4;
       time_partition:=partition_duration(current_partition);
end section;

priority_section:
       if time_partition=0
           then  current_partition:=(current_partition+1)
              mod number_of_partition;
                 time_partition:=partition_duration(current_partition);
       end if;

       for i in tasks_range loop
           if tasks.task_partition(i)=current_partition
                     then dynamic_priority(i]:=priority(i);              

                    else  dynamic_priority(i):=0; tasks.ready(i):=false;
           end if;
        end loop;
       time_partition:=time_partition-1;
end section;

election_section:
           return max_to_index(dynamic_priority);
end section;

Figure 6.9 Processes and partitions scheduling into an ARINC 653 system

In this code, tasks.task_partition is a User's defined task parameter. tasks.task_partition stores the partition number hosting the associated task. The variable partition_duration stores the partition cyclic activation table.

VI.2 Scheduling with specific task models.

In the same way you can define specific schedulers, you can also define specific task activation patterns. By default, 3 kinds of task activation pattern are defined in Cheddar :

Periodic task : a fixed amount of time exists between two successive task activations.
Aperiodic task : the task is activated only once at a given time.
Poisson process task : tasks are activated several times and the delay between two successive activations is a random delay. The static variable period in this case is the average time between two successive activations. The delay between activations is generetad according to a random poisson process.

If the application you want to study can not be modeled with this 3 kinds of activation rules above, a possible solution is to explain your own task activation pattern with a user-defined scheduler. The description of task activation pattern is done in .sc files in a particulary section which is called task_activation_section. In this section, you can define named activation rules with set statements. The set statement just link a name/identifier (the left part ot the set statement) and an expression (the right part of the set statement). The expression explains the amount of time the scheduling simulator engine has to wait between two activations of a given task.

start_section:
	gen1 : random;
	gen2 : random;
	exponential(gen1, 200);
	uniform(gen2, 0, 100);
end section;

election_section:
        return max_to_index(tasks.priority);
end section;

task_activation_section:
        set activation_rule1 10;
        set activation_rule2 2*tasks.capacity;
        set activation_rule3 gen1*20;
        set activation_rule4 gen2;
end section;

Figure 6.10 Defining new task activation patterns : how to run simulation with specific task models

The example of the Figure 6.10 describes a Highest Priority First scheduler which hosts tasks activated with different patterns. Each pattern is described by a set statement :

The pattern activation_rule1 describes periodic tasks with a period equal to 10.
The pattern activation_rule2 describes periodic tasks with a period equal to twice their capacity.
The pattern activation_rule3 describes randomly activated tasks. Two successive activations are delayed by an amount of time which is randomly computed. Delays are computed according to a random exponential distribution pattern with a mean value of 400. 400 is then the average period value of the tasks. The seed used during random delay generation depends on the scheduling options set at simulation time (see section I.3 ) : the user can choose to associate a seed per task or a seed for all the tasks. Seeds can be initialized in a predictable way or in an unpredictable way. In the case of a predictable seed, the random generator is initialized with the seed value given at task definition time or in the scheduling option window. In the case of an unpredictable seed, the seed is initialized by the "gettimeofday" at simulation time.
The pattern activation_rule4 describes randomly activated tasks. Two successive activations are delayed by an amount of time that is randomly computed. Delays are computed according to a random uniform distribution pattern with a mean value of 50. At each periodic task activation, the period can have a value between 0 and 100. The seed used during random delay generation is managed in the same way than activation_rule3.

When task activation rules are defined, task activation names (ex : activation_rule1) have to be associated with "real" task. The picture below shows you an "Edit/Entities/Software/Task" window :

Figure 6.11 Assigning activation rules to tasks

In this example, the task activation rule activation_rule1 is associated with task T1. The task activation rule activation_rule2 is associated with task T2. The task activation rule activation_rule3 is associated with tasks T3.

VI.3 Running a simulation with a user-defined scheduler.

Let's see how to run a simulation with one or several user-defined schedulers. First, you have to add a scheduler by selecting the submenu "Edit/Entities/Hardware/Core". The following window is then launched :

Figure 6.13 Define a core with a user-defined scheduler

To add a user-defined scheduler into a Cheddar project, select the right item of the Combo Box and give a name to your scheduler. You should then provide the code of your user-defined scheduler. This operation can be done by pushing the "Read" button.
In this case, the following window is spawned and you should give a file name containing the code of your user-defined scheduler :

Figure 6.14 Selecting the .sc file which contains the user-defined scheduler

By convention, files that contain user-defined scheduler code should be prefixed by .sc. For example, the file rm.sc in our example should almost contain an election section and of course, can also contain a start and a priority sections. When a processor is defined, you have to add tasks on it. To do so, select the submenu "Edit/Entities/Software/Task" like in section I. Just place the task on the previously defined processor. Finally, you can run scheduling simulations as the usual case.

Since a user-defined scheduler is also a piece of code, you sometimes need to debug it. To do so, you can use the following tips :

First, a special instruction can be used to display the value of a variable on the screen : the put statement. For instance, running the following user-defined code will display the value of the dynamic variable to_run each time the scheduler is called :

--!TRACE

start_section:
         to_run : integer;
         current_priority : integer;
end section;

priority_section:
   current_priority:=0;
   for i in tasks_range loop
         if  (tasks.ready(i)=true) and (tasks.priority(i)>current_priority)
                    then to_run:=i;
                         put(to_run);
                         current_priority:=tasks.priority(i);
         end if;
    end loop;
end section;

election_section:
    return to_run;
end section;

Figure 6.15 Using the put statement

A second tip can help you to test if the syntax of your user-defined scheduler is correct. In all .sc file, you can add the line --!TRACE anywhere. If you add this line, the parser will give extra information during the syntax analysis of your user-defined scheduler. It's useful if you want to test a .sc file before using it in a Cheddar project file. You can also test it with sc, a program designed to read, parse and check .sc files.

VI.4 Looking for user-defined properties during a scheduling simulation.

start_section:
   	  i           : integer;
        nb_T2       : integer;
        nb_T1           : integer;
        bound_on_jitter : integer;
        max_delay       : integer;
        min_delay       : integer;
        tmp             : integer;
        T1_end_time     : array (time_units_range) of integer;
        T2_end_time     : array (time_units_range) of integer;
        min_delay:=integer'last;
        max_delay:=integer'first;
        i:=0;
	nb_T1:=0; nb_T2:=0;
end section;

gather_event_analyzer_section:
        if (events.type = "end_of_task_capacity")
		then
			if (events.task_name = "T1")
				then
                                T1_end_time(nb_T1):=events.time;
				nb_T1:=nb_T1+1;
			end if;
			if (events.task_name = "T2")
				then
                                T2_end_time(nb_T2):=events.time;
				nb_T2:=nb_T2+1;
			end if;
	end if;
end section;

display_event_analyzer_section:
     while (i < nb_T1) and (i < nb_T2) loop
            tmp:=abs(T1_end_time(i)-T2_end_time(i));
            min_delay:=min(tmp, min_delay);
            max_delay:=max(tmp, max_delay);
	    i:=i+1;
      end loop;
      bound_on_jitter:=abs(max_delay-min_delay);

      put(min_delay);
      put(max_delay);
      put(bound_on_jitter);
end section;

Figure 6.16 Example of user-defined event analyzer : computing task termination jitter bound

In the same way that users can define new schedulers, Cheddar makes it possible to create user-defined event analyzers. These event analyzers are also writen with an Ada-like language and interpreted at simulation time.

The event table produced by the simulator records events related to task execution and related to objects that tasks access. Event examples stored in this table can be :

Events produced when a task becomes ready to run (event task_activation), when a task starts or ends running its capacity (events start_of_task_capacity and end_of_task_capacity),
Events produced when a task reads or writes data from/to a buffer (events write_to_buffer and read_from_buffer),
Events produced when a task sends or receives a message (events send_message and receive_message),
Events produced when a task starts waiting for a busy resource (event wait_for_a_resource), allocates or releases a given resource (events allocate_resource and release_resource).

Each of these events is stored with the time it occurs and with information related to the event itself (eg. name of the resource, of the buffer, of the message, of the task ...). The event table is scanned sequentially by event analyzers. User-defined event analyzers are composed of several sections : a start section, a data gathering section and an analyze and display section.

As user-defined schedulers, the start section is devoted to variable declarations and initializations.
The gathering section contains code which is called for each item of the event table. Most of the time, this section contains statements which extract useful data from the event table, and store them for the event analyzer.
Finally, the display section performs analysis on data previously saved by the gathering section and displays the results in the main window of the Cheddar Editor.

Figure 6.16 gives an example of user-defined event analyzer. From an ARINC 653 scheduling this event analyzer computes the minimum, the maximum and the jitter on the delay between end times of two tasks owned by different partitions (tasks T1_P0 and T2_P1 ; see Figure 6.9).

VI.5 List of predefined variables and available statements.

The tables below list all predefined variables that are available when you write a user-defined code:

*Name*	*Type*	*Is updated by the simulator engine*	*Can be changed by user code*	*Meaning*
*Variables related to processors*
nb_processors	integer	no	no	Gives the number of processors of the current analyzed system.
processors.speed	integer	yes	yes	Gives the speed of the processor hosting the scheduler.
*Variables related to tasks*
tasks.period	array (tasks_range) of integer	yes	yes	Stores the value of the parameter given at task definition time. For the meaning of this variable, see section I.
tasks.name	array (tasks_range) of string	no	no	Name of the task
tasks.type	array (tasks_range) of string	no	no	Type of the task (periodic, aperiodic, sporadic, poisson_process or userd_defined)
tasks.processor_name	array (tasks_range) of string	no	no	Stores the processor name of the cpu hosting the corresponding task.
tasks.blocking_time	array (tasks_range) of integer	no	yes	Stores the sum of the bounded times the task has to wait on shared resource accesses.
tasks.deadline	array (tasks_range) of integer	yes	yes	Stores the value of the parameter given at task definition time. For the meaning of this variable, see section I.
tasks.capacity	array (tasks_range) of integer	yes	yes	Stores the value of the parameter given at task definition time. For the meaning of this variable, see section I.
tasks.start_time	array (tasks_range) of integer	yes	yes	Stores the value of the parameter given at task definition time. For the meaning of this variable, see section I.
tasks.used_cpu	array (tasks_range) of integer	yes	no	Stores the amount of processor time wasted by the associated task.
tasks.activation_number	array (tasks_range) of integer	yes	no	Stores the activation number of the associated task. Of course, using this variable is meaningless for aperiodic tasks.
tasks.jitter	array (tasks_range) of integer	yes	yes	Stores the value of the parameter given at task definition time. For the meaning of this variable, see section I.
tasks.priority	array (tasks_range) of integer	yes	yes	Stores the value of the parameter given at task definition time. For the meaning of this variable, see section I.
tasks.used_capacity	array (tasks_range) of integer	yes	no	This variable stores the umount of time unit the task had consumed since its last activation. When tasks.used_capacity reaches tasks.capacity, the task stops to run and waits its next activation
tasks.rest_of_capacity	array (tasks_range) of integer	yes	no	For each task activation, this variable is initialized to the task capacity each time the task starts a new activation. If rest_of_capacity is equal to zero, the task has over its its current activation and then task is blocked upto its next activation.
tasks.suspended	array (tasks_range) of integer	yes	yes	This variable can be used by scheduler programmers to block a task : remove a task from schedulable tasks.
nb_tasks	integer	no	no	Gives the number of tasks of the current analyzed system.
tasks.ready	array (tasks_range) of boolean	yes	no	Stores the state of the task : this boolean is true if the task is ready ; it means the task has a capacity to run, does not wait for a shared resource, does not wait for a delay, does not wait for a offset constraint and does not wait for a precedency constraint.
*Variables related to messages*
nb_messages	integer	no	no	Gives the number of messages of the current analyzed system.
messages.name	array (messages_range) of string	no	no	Gives the names of each message.
messages.jitter	array (messages_range) of integer	no	no	Jitter on the time the periodic message becomes ready to be sent.
messages.period	array (messages_range) of integer	no	no	Gives the sending period if the message is a periodic one.
messages.delay	array (messages_range) of integer	no	no	time needed by a message to go from the sendrer to the receiver node.
messages.deadline	array (messages_range) of integer	no	no	Stores the deadline if the message has to meet one.
messages.size	array (messages_range) of integer	no	no	Stores the size of the message.
messages.users.time	array (messages_range) of integer	no	no	Stores the time when the task should send or receive the message.
messages.users.task_name	array (messages_range) of string	no	no	Stores the task name that sends/receives the message.
messages.users.type	array (messages_range) of string	no	no	Stores `sender` if the corresponding task sends the message or stores `receiver` if the task receives it.
*Variables related to buffers*
nb_buffers	integer	no	no	Gives the number of buffers of the current analyzed system.
buffers.max_size	array (buffers_range) of integer	no	no	The maximum size of a given buffer.
buffers.processor_name	array (buffers_range) of string	no	no	Gives the processor name that owns the buffer.
buffers.name	array (buffers_range) of string	no	no	Unique name of the buffer.
buffers.users.time	array (buffers_range) of integer	no	no	Stores the time a given task consumes/produces a message from/into a buffer.
buffers.users.size	array (buffers_range) of integer	no	no	Stores the size of the message produced/consumed into/from a buffer by a given task.
buffers.users.task_name	array (buffers_range) of string	no	no	Stores the task name that procudes/consumes messages into/from a given buffer.
buffers.users.type	array (buffers_range) of string	no	no	Stores `consumer` if the corresponding task consumes messages from the buffer or stores `producer` if the task produces messages.
*Variables related to shared resources*
nb_resources	integer	no	no	Gives the number of shared resources of the current analyzed system.
resources.initial_state	array (resources_range) of integer	no	no	Stores the state of the resource when the simulation is started. If this integer is equal of less than zero, the first allocation request will block the requesting task.
resources.current_state	array (resources_range) of integer	no	no	Stores the current state of the resource. If this integer is equal of less than zero, the first allocation request will block the requesting task. After an allocation of the resource, this counter is decremented. After the task has released the resource, this counter is incremented.
resources.processor_name	array (resources_range) of string	no	no	Stores the name of the processors hosting the shared resource.
resources.protocol	array (resources_range) of string	no	no	Contains the protocol name used to manage the resource allocation request. Could be either no_protocol, priority_ceiling_protocol or priority_inheritance_protocol
resources.name	array (resources_range) of integer	no	no	Unique name of the shared resource
resources.users.task_name	array (resources_range) of string	no	no	Gives the name of a task that can access the shared resource.
resources.users.start_time	array (resources_range) of integer	no	no	Gives the time the task starts accessing the shared resource during its capacity.
resources.users.end_time	array (resources_range) of integer	no	no	Gives the time the task ends accessing the shared resource during its capacity.
*Variables related to the scheduling simulation*
previously_elected	integer	yes	no	At the time the user-defined scheduler runs, this variable stores the TCB index of the task elected at the previous simulation time
simulation_time	integer	yes	no	Stores the current simulation time .
*Variables related to the event table*
events.type	string	no	no	Type of event on the current index table. Can be `task_activation`, `running_task`, `write_to_buffer`, `read_from_buffer`, `send_message`, `receive_message`, `start_of_task_capacity`, `end_of_task_capacity`, `allocate_resource`, `release_resource`, `wait_for_resource`.
events.time	integer	no	no	The time when the event occurs.
events.processor_name	string	no	no	The processor name hosting the task/resource/buffer related to the current event.
events.task_name	string	no	no	The task name related to the current event.
events.message_name	string	no	no	The message name related to the current event.
events.buffer_name	string	no	no	The buffer name related to the current event.
events.resource_name	string	no	no	The resource name related to the current event.

The BNF syntax of a .sc file is given below :

entry := start_rule priority_rule election_rule task_activation_rule gather_event_analyzer display_event_analyzer

declare_rule := "start_section:" statements
priority_rule := "priority_section:" statements
election_rule := "election_section:" statements
task_activation_rule := "task_activation_section" statements
gather_event_analyzer := "gather_event_analyzer_section" statements
display_event_analyzer:= "display_event_analyzer_section" statements

statements := statement {statement}
statement :=
"put" "(" identifier [, integer] [, integer]")" ";"
| identifier ":" data_type [ ":=" expression ] ";"
| identifier ":=" expression ";"
| "if" expression "then" statements [ "else" statements ] "end" "if" ";"
| "return" expr ";"
| "for" identifier "in" ranges "loop" statements "end" "loop" ";"
| "while" expression "loop" statements "end" "loop" ";"
| "set" identifier expression ";"
| "uniform" "(" identifier "," expression "," expression ")" ";"
| "exponential" "(" identifier "," expression ")" ";"

data_type := scalar_data_type
| "array" "(" ranges ")" "of" scalar_data_type
ranges := "tasks_range" | "buffers_range" | "messages_range" | "resources_range" | "processors_range" | "time_units_range"
scalar_data_type := "double" | "integer" | "boolean" | "string" | "random"

operator := "and" | "or" | "mod" | "<" | ">" | "<=" | ">=" | "/=" | "=" | "+" | "/" | "-" | "*" | "**"

expression := expression operator expression
| "(" expression ")"
| "not" expression
| "-" expression
| "max_to_index" "(" expression ")"
| "min_to_index" "(" expression ")"
| "max" "(" expression "," expression ")"
| "min" "(" expression "," expression ")"
| "lcm" "(" expression "," expression ")"
| "abs" "(" expression ")"
| identifier "[" expression "]"
| identifier
| integer_value
| double_value
| boolean_value

Notes on the BNF of .sc file syntax :

entry is the entry point of the grammar.
The data_type rule describes all data types available in a .sc file
The operator rule lists all binary operators.
The expression rule gives all possible expressions that you can use to define your scheduler.
The statement rule contains all statements that can be used in a .sc file.
identifier is a string constant.
integer_value is a integer constant.
double_value is a double constant.
boolean_value is a boolean constant.

Two kinds of statements exist to build your user-defined scheduler : low-level and high-level statements. high-level statements operate on all task information. low-level statements operate only on one information of a task at a time. all these statements work as follows :

The if statement : works like in Ada or most of programming languages : run the else or the then statement branch according to the value of the if expression.
The while statement : works like in Ada or most of programming languages : run the statements enclosed in the loop/end loop block until the while condition becomes false.
The for statement : it's an Ada loop with a predefined iterator index. With a for statement, the statements enclosed in the loop are run for each task defined in the TCB table. At each iteration, the variable defined in the for statement is incremented. Then, in the case of task loop for instance (use keyword tasks_range in this case), its value ranges from 1 to nb_tasks (nb_tasks is a predefined static variable initiliazed to the number of tasks hosted by the currently analyzed processor).
The return statement. You can use a return statement in two cases :

With any argument in any section except in the election_section. In this case, the return statement just end the code of the section.
With a integer argument and only in the election_section . Then, the return statement give the task number to be run. When the return statement returns the -1 value, it means that no task has to be run at the nuext unit of time.

The put(p,a,b) statement : displays the value of the variable p on the screen. This statement is useful to debug your user-defined scheduler. If a and b are not equal to zero and if p is an array type, put(p,a,b) displays entries of the table with index between a and b. If a and b are equal to zero and if p is an array, all entries of the array are displayed.
The delete_precedence "a/b" statement : remove the dependency between task a and b (a is the source task while b is the destination/sink task).
The add_precedence "a/b" statement : add a dependency between task a and b (a is the source task while b is the destination/sink task).
The exponential(a,b) statement : intializes the random generator a to generate exponential random values with an average value of b.
The uniform(a,b,c) statement : intializes the random generator a to generate uniformly random values between b and c.
The set statement : description of new task activation model : assign an expression which shows how to compute task wake up time with an identifier.

The predefined operators and subprograms are the following:

abs(a) : returns the unsigned value of a.
lcm(a,b) : returns the last common multiplier of a and b.
max(a,b) : returns the maximum value between a and b.
min(a,b) : returns the minimum value between a and b.
max_to_index (v) : firstly finds the task in the TCB with the maximum value of v ,and then returns its position in the TCB table. Only ready tasks are considered by this operator.
min_to_index(v) : firstly finds the task in the TCB with the minimum value of v, and then returns its position in the TCB table Only ready tasks are considered by this operator.
a mod b : computes the modulo of a on b (rest of the integer division).
to_integer(a) : cast a from double to integer. a must be a double.

to_double(a) : cast a from integer to double. a must be an integer.
integer'last : return the largest value for the integer type.
integer'first : return the smallest value for the integer type.
double'last : return the largest value for the double type.
double'first : return the smallest value for the double type.
get_task_index (a) : return the index in the task table for the task named a>.
get_buffer_index (a) : return the index in the buffer table for the buffer named a>.
get_resource_index (a) : return the index in the resource table for the resource named a>.
get_message_index (a) : return the index in the message table for the message named a>.

Contact : Frank Singhoff mailto:singhoff@univ-brest.fr
Last update : March, the 14th, 2021