IBM
Contents Index Previous Next



The SDL Scheduler Concepts


In this section, the concepts of the Cmicro SDL scheduler are outlined, with particular emphasis on basic SDL, the handling of the queue, scheduling, signals, timers, states etc. To obtain information about data in SDL, especially ADTs, please consult The Cadvanced/Cbasic SDL to C Compiler. Here both predefined and user defined ADTs are outlined.

Signals, Timers and Start-Up Signals

Data Structure for Signals and Timers

Each signal that is either an ordinary SDL signal, a timer or the start-up signal used for the dynamic process creation, is represented by three structures:

The first and the second is defined in ml_typ.h, the third is defined in the generated code as yPDef_SignalName. Some structure components are conditionally compiled, which is used to scale the system. Please view the following C structure:

typedef struct
{
   #ifdef XMK_USE_RECEIVER_PID_IN_SIGNAL
       xPID          rec;   /* Receiver process */
   #endif

   xmk_T_SIGNAL  signal;    /* Signalcode       */

   #ifdef XMK_USE_SIGNAL_PRIORITIES
      xmk_T_PRIO  prio;     /* Priority         */
   #endif

   #ifdef XMK_USE_SIGNAL_TIME_STAMP
      xmk_T_TIME time_stamp;/* Timestamp        */
   #endif

   #ifdef XMK_USE_SENDER_PID_IN_SIGNAL
       xPID         send    /* Sender process   */
   #endif

   #ifdef XMK_USED_SIGNAL_WITH_PARAMS
     xmk_T_MESS_LENGTH mess_length;
     union
     {
        void          *ParPtr;
        #if (XMK_MSG_BORDER_LEN > 0)
          unsigned char ParCopy[XMK_MSG_BORDER_LEN];  
        #endif
     } ParUnion;
   #endif

} xmk_T_MESSAGE;

Three different cases are to be considered concerning signals with parameters:

Note:

This margin of XMK_MSG_BORDER_LEN bytes can of course be modified by the user to prevent dynamic memory allocation for any signal in the queue, or in contrast, to always use dynamic memory allocation. See the file ml_mcf.h to modify this.

The second structure, which encapsulates the above one, is used to administrate the signals in the queue, as required by the FIFO handling and SDL save construct:

typedef struct _T_E_SIGNAL
{
  xmk_T_MESSAGE       Signal;
  struct _T_E_SIGNAL *next;

#ifdef XMK_USED_SAVE
  xmk_T_STATE         SaveState; 
#endif /* XMK_USED_SAVE */
} T_E_SIGNAL ;

As already mentioned, the above structure is used for ordinary SDL signals, timers and the start-up signal for the dynamic process creation.

No differentiation is made between signals and timers, except that signals and timers have a different identification (signal in the xmk_T_SIGNAL structure).

When a process is to be created, a start-up signal is sent. The start-up signal is tagged by a special priority value and a special id.

Dynamic Memory Allocation

Dynamic memory allocation is in principle not necessary with Cmicro. There are SDL systems which can live without any dynamic memory allocation and there are SDL systems that require dynamic memory allocation from the user's point of view. The users should in general try to prevent any dynamic memory allocation due to the problems this introduces. Soon or later memory leaks will occur.

Cmicro offers its own dynamic memory allocator. Please view Dynamic Memory Allocation for getting more information on this.

In the following subsections, the exceptions for when Cmicro uses dynamic memory allocation are listed.

Signals and Signal Parameters

In order to cope with efficiency, dynamic memory allocation should not be done, whenever possible. Cmicro offers two principles of memory allocation for signal instances, namely:

  1. Signal instances are allocated from a static memory pool only.
    The static memory is allocated during compilation. The pool's size is predefined with the XMK_MAX_SIGNALS macro. To enable this configuration, the macro XMK_USE_STATIC_QUEUE_ONLY is to be set. This principle has the disadvantage that if there is no free memory in the static memory pool, a fatal error occurs. The user is however given the possibility to react on this error situation because the ErrorHandler C function is called.
  2. As another principle, it is possible to first take memory from the static memory pool. If no more memory is available in that pool, further signal instances are created from the dynamic memory pool.

    Caution!

    This configuration is not available when the preemptive scheduling mechanism is used.

    To enable the configuration, the macro XMK_USE_STATIC_AND_DYNAMIC_QUEUE must be set. The static memory pool's size is still predefined with the XMK_MAX_SIGNALS macro.

When signal instances are allocated from the static memory pool, the allocation procedure is the most efficient.

When the second principle is used, the execution speed will of course dramatically slow down because dynamic memory allocation happens. This change in the behavior of the Cmicro Kernel may cause problems in a real-time environment and the user should keep this in mind.

The static memory pool above is implemented as a predefined array in C. The array is dimensioned with the XMK_MAX_SIGNALS macro.

Dynamic memory is requested with the xAlloc C function and released again with the xFree C function. The body of both these C functions must in any case be filled out appropriately by the user in all cases.

Signal parameters are to be allocated dynamically, if the amount of parameter bytes exceeds a predefined constant. If the amount of signal parameters is below or equal this predefined constant, the parameter bytes are put into the signal's header.

The default value for this predefined constant XMK_MSG_BORDER_LEN is 4 bytes. Dynamic memory allocation only occurs if a signal carries more than XMK_MSG_BORDER_LEN bytes, where the latter is defined as 4.

If the user defines XMK_MSG_BORDER_LEN as 0, then for each signal, which has parameters, the C function xAlloc() is called.

If the user defines XMK_MSG_BORDER_LEN to 127, then

Due to this mechanism, the allocation of signal parameters is also very fast. Releasing the memory is performed automatically by calling the xFree C function.

Predefined Sorts

Some of the predefined sorts require dynamic memory allocation. The sorts are

SDL Target Tester

If the SDL Target Tester is used, there are some more allocations from the dynamic memory pool. The SDL Target Tester allocates one block of dynamic memory in the start phase. This block is never de-allocated again. The size of the block depends on the amount of process types in the system. Another dynamic memory allocation takes place when a binary frame is to be sent to the host machine. The blocks that are allocated here are de-allocated again after the frame is put into the physical transmitter buffer.

Overview for Output and Input of Signals

Output and input of signals is performed according to the rules of SDL. To get detailed information about the implementation of output and input, please consult the subsection Output and Input of Signals.

Signal instances are sent using the C function xmk_Send() or xmk_SendSimple(). The function takes a signal and puts it into the input port of the receiving process instance.

Figure 589 : Queueing - sending side

There is no process ready queue. Physically, the queues of the different processes of the system are represented by just one queue. There are different principals to create signal instances which the user can choose between. The principals are explained within the subsection Signals and Signal Parameters.

From an abstract point of view, it does not matter, if there is one physical queue for all the signal instances in the system, or if there is one physical queue for all the signal instances sent to one process instance. The fact that Cmicro uses one physical queue for all signals in the system only, has no effect on SDL users and conforms to the semantic rules of SDL. The scheduling simply depends on the ordering of signals in the queue. In the case of a preemptive Cmicro Kernel scaled this way, there is one linked list of signals per priority level all using the array mentioned above. See the subsection Scheduling for details.

Figure 590 : Queueing - receiving side

When working on a signal, the Cmicro Kernel decides between four different constellations:

In any case, except when being saved, the signal will be removed from the queue and returned to the list of free signals.

After performing the nextstate operation, the input port is scanned in accordance with the rules of SDL to find the next signal which would cause an implicit or explicit transition.

There is no specific input function. This functionality is contained in the Cmicro Kernel.

Timers and Operations on Timers

With the delivered timer model, all timer management entities fully conform to SDL. This means that more memory is required to implement this timer.

For each timer, there is a C structure defined in ml_typ.h.

typedef struct _TIMER        
{
  struct _TIMER *next ;      

  xmk_T_SIGNAL   Signal   ;  
  xmk_T_TIME     time     ;  
  xPID           OwnerProcessPID ; 

} TIMER ;

xmk_T_TIME is defined as a long value.

Figure 591 : Handling of timers (timer model 1)

The component

As can be seen above, timers are implemented as a forward linked list.

Processes

Data Structure for Processes

Each process is represented by structures and tables containing SDL information, for example, tables containing transition definitions and a structure representing the variables of the process. The typedef for variables is generated in the generated code and named yVDef_ProcessName. For each process instance, there is one array element defined statically during compile time.

The structures and tables for processes are described in detail in the subsection Tables for Processes.

Scheduling

The Cmicro Kernel supports in principle the following scheduling policies:

General Scheduling Rules

Further explanation of the scheduling is in the next subsection.

Non Preemptive Scheduling

The Cmicro Kernel takes the first signal from the queue and if the signal is not to be saved the appropriate SDL transition is executed until a nextstate operation is encountered. Outputs in SDL transitions as well as SDL create operations are represented by signals, where create signals are given priority treatment no matter whether signal priorities are used or not. This guarantees that there will not be any problems when a signal is sent to a process just before the process has been dynamically created.

The ordering of signals in the queue can be affected by using signal priorities (#PRIO directive for signals).

Whenever an output takes place, the Cmicro Kernel inserts the signal into the queue according to its priority. High priority signals are inserted at the queue's head, low priority signals at the queue's end. Create signals are still given priority treatment.

Note:

The priority of a create signal in the standard delivery is set to one.

This, as well as all the default signal priorities, is user-definable in the file ml_mcf.h (generated by the Targeting Expert). In this way it is possible to define signals with a higher priority then the create signal. The user should remember not to do so!

Figure 592 : Non preemptive scheduling

Figure 593 : Scheduling for Create

A signal (this is either an ordinary SDL signal, a timer signal or the internal start-up signal in the event of SDL create) with the highest priority is always put in front of the SDL queue, a signal with the lowest priority is always put at the end of the SDL queue.

Figure 594 : Signal priorities

For applications, which do not have time critical requirements, the non preemptive scheduling policy is the correct one to implement. The Cmicro Kernel memory requirements are also reduced when the non-preemptive scheduling policy is implemented. For example, for an interface with a very high transmission rate, the preemptive scheduling policy is better suited in order to increase the reaction time on external signals coming from the environment.

On starting the SDL system, processes are statically created according to their order of priority.

Preemptive Scheduling with Process Priorities

Note:

The Cmicro preemptive kernel is only available if the according license is available.

Figure 595 : Preemptive scheduling

SDL assumes the start transitions of all statically created processes are already finished at system start-up (a transition takes no time according to SDL semantics). To simulate this, the Cmicro Kernel starts all statically created processes in the order of their priority before working on any signal. Preemption is disabled during the start-up phase of the system. There are two C functions namely xmk_DisablePreemption and xmk_EnablePreemption which can be used to prevent the Cmicro Kernel from performing a context switch. In this way it is possible to affect the scheduling from within the SDL system (using the #CODE directive).

The preemptive scheduling policy is absolutely necessary if an application consists of a mixture of processes, of which some have to react very quickly to external events, while others require enough time for processing. The Cmicro Kernel does all things necessary to schedule such a mixture of processes.

Users only have to specify a high priority for processes which have to react after a short time. This can be done with the #PRIO directive for processes. If no #PRIO directive is specified, then a process is given the default value, which is specified by the user in the file ml_mcf.h (please view the subsection Compilation Flags).

The highest priority is represented by the value zero. The numbering has to be consecutive with the priority decreasing with increasing numbers. Processes with the same priority are on the same priority level. The default process priority must be in the range of zero to the lowest priority value used in the system. Assume the following priority levels:

Figure 596 : Priority levels

In the figure above there are signals queued for processes on four different priority levels. These would be worked on in this order:

According to their priorities the signals on priority level zero are consumed first, afterwards those of level one, two and last three. This is relevant only, if no signals are sent during the transitions executed because of the signals.

Rules

Note:

If C variables are to be used in the SDL application, i.e. (x, N) declarations are used where N > 1 these variables are only available once and not once per process instance.

Restrictions

In order to produce portable C code, this version of the Cmicro Kernel uses recursive C function calls. A few C compilers available on the market do not support recursion. If such a C compiler is required, the user cannot use preemptive scheduling with process priorities.

Create and Stop Operations

No dynamic memory allocation occurs if an SDL create operation is performed. No freeing of memory occurs if an SDL stop operation is performed.

Data of a process instance is represented by the following typedef structs:

The reason for using such a structure is to make it possible for the Cmicro Kernel to operate on the PID structure and the table with SDL states, so that no code needs to be generated in the application to update such variables.

An array of N elements for each of these typedef structs is generated, where N is the maximum number of process instances. The maximum number is to be specified in the process declaration header in the SDL diagram.

After performing a stop action, old PID values might exist in variables of other processes. The synchronization between processes to prevent situations where signals are sent to dead processes is left to the discretion of the user. If a process sends a signal to a non existent process, where nonexistent means either "never created" or "is dead", the ErrorHandler is called and the signal is discarded (SDL conform).

When the Cmicro Kernel stops a process, the input queue assigned to the process stopped will be removed. No interpretation error occurs for the signals which existed in the queue before the process was stopped.

Note:

It is also possible for the user to implement dynamic memory allocation for process instance data. Some C defines are to be redefined in this case.

Output and Input of Signals

The actions to perform an output in the generated code are as follows:

Within the xmk_Send*- functions there are a few checks performed. For example, if the receiver is a NULL-PID, then the ErrorHandler is called.

Next, the environment C function xOutEnv is called. This function is to be filled out by the user. The function decides if the signal should be sent to the environment. The information necessary can be extracted from the signal ID, the priority or the receiver of the signal. If xOutEnv has "consumed" the signal, xmk_Send* returns immediately.
xOutEnv has to copy the parameters of the signal to the receiver of the signal in the environment because after returning, the parameters will no longer exist.

If the signal is not environment bound, then the signal is sent to an internal SDL system process and xmk_Send* inserts the signal into the queue. This is done according to the priority of the signal (see subsection Assigning Priorities - Directive #PRIO.

If the signal carries no parameters, or if the signal parameters are represented by less than or equal to XMK_MSG_BORDER_LEN bytes, no dynamic memory allocation occurs and possible parameters are transferred directly by copying them into the signal header.

If more than XMK_MSG_BORDER_LEN bytes parameters are to be transferred dynamic memory allocation occurs. A pointer in the signal header then points to this allocated memory area. Freeing is done after consumption of the signal at the receiver process after executing the nextstate operation or after the signal was consumed by the environment.

In order to implement this strategy, each signal carries a field "data length" in its header, to detect if a pointer is transferred or a copy of the parameters.

Note:

There are several possibilities to send signals to the environment by not using xOutEnv. The user should have a look at the #EXTSIG, #ALT and #TRANSFER directives which can be used in SDL Output. The one most similar to SDL, however, is the one which simply uses the C function xOutEnv.

At the receiver's side, when the input operation is to be performed, it is checked if the signal is to be saved or discarded. In the case of save, the next signal contained in the queue is checked and worked on. If on the other hand the signal is to be discarded, in the case of an "implicit transition", i.e. no definition is present to handle that signal in the current state, the signal is then deleted from the input port of the process and, using the SDL Target Tester, the user is notified.

Otherwise, the signal leads to the execution of the transition. After performing the nextstate operation, the signal is deleted from the input port of the process and scheduling continues according to the rules of the scheduler again.

In the case of a so scaled preemptive Cmicro Kernel, the signal remains active in the input port until the nextstate operation is executed, although other processes can interrupt the running one (preemption).

Nextstate Operation

The nextstate operation is implemented by a return (return value) statement in the generated code. Several return values are possible to control the action to be taken by the Cmicro Kernel. The PAD function representing the SDL process can return any of the following (PAD means "Process Activity Description").

The return-value either expresses

After recognizing the action to be taken, the Cmicro Kernel either writes the process state variable or stops the SDL process.

The signal which was just being worked on is deleted from the input port. This includes the freeing of the memory area allocated for the signal, if memory was previously allocated.

Decision and Task Operations

No action is to be performed by the Cmicro Kernel for decisions and tasks, except those to trace these actions for the SDL Target Tester.

For SDL decisions and SDL tasks, C assignments and C function calls are implemented. Function calls are used in the case of an ADT or where simple C data operations (i.e. =, >, >=, ==) cannot represent the SDL operation wanted.

Note:

Function calls, however, are not necessarily generated, i.e. if the user defines C macros/defines instead of C functions for an ADT. Please consult the subsection Abstract Data Types.

Procedures

There are some special topics regarding procedures in SDL. The most important are:

Note that procedures with states and remote procedure calls are not supported within the Cmicro Package.

It is possible to use global procedures (SDL'92) which makes it possible to specify a procedure once, by allowing several processes to call it.

Recursion is allowed, but should be introduced only if an algorithm cannot be designed alternatively. In most cases, algorithms and recursivity are subjects for an ADT.

Procedures returning values are also implemented. The return value in SDL is mapped to a return value in C. Procedures not returning values are mapped to C functions returning void.

The remaining part is the location of procedure data and the access to procedure data. Here another restriction exists, namely that it is not possible to access data of the father procedure of a procedure without declaring this explicitly.

Data, which belongs to a process is always located as a global array in C (for x, N process declarations, where N is >1). Data which belongs to a procedure is always allocated on a C stack for the called procedure.

Procedure Calls

An SDL procedure call is implemented as a direct function call in C. Each formal parameter is passed as a C parameter to the function. Access to global data of the calling process is possible only if the procedure is not a global procedure. The C code generated for a local procedure uses global C variables of the surrounding process.

Data which is declared locally within a procedure is also allocated on the C stack.

No dynamic memory allocation is performed as procedures with states are not handled.

The following example shows the mapping for procedures returning values.

Example 605 : Procedure Call

TASK i := (call p(1)) + (call Q(i,k));

is translated to something like:

i = p(1) + Q(i,k);

Note:

The value returning procedure calls are transformed to C functions returning values.

An SDL procedure can be called more than once. No conflicts occur if using a preemptive Cmicro Kernel.

Procedure Body

For each SDL procedure, there is one C function generated. The Procedure body can contain the same SDL actions as the process body. The same code generation is performed with the exception of a few statements declaring temporary variables.

Within global procedures, no objects of the calling process can be used without declaring them via formal parameters. Another restriction is that each output in a global procedure must be specified with to PID.

Blocks, Channels and Signal Routes

No C code is generated for blocks, channels and signal routes, except the C comment, which tells the user the location of processes and procedures.


http://www.ibm.com/rational
Contents Index Previous Next