![]() |
![]() |
![]() |
![]() |
![]() |
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:
- A C structure defining the entries in the queue
- A C structure defining the header of each signal
- A generated C structure representing the parameters of the signal
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_SIGNALxPID rec; /* Receiver process */#endifxmk_T_SIGNAL signal; /* Signalcode */#ifdef XMK_USE_SIGNAL_PRIORITIESxmk_T_PRIO prio; /* Priority */#endif#ifdef XMK_USE_SIGNAL_TIME_STAMPxmk_T_TIME time_stamp;/* Timestamp */#endif#ifdef XMK_USE_SENDER_PID_IN_SIGNALxPID send /* Sender process */#endif#ifdef XMK_USED_SIGNAL_WITH_PARAMSxmk_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;
- signal:
represents a C constant which uniquely identifies the signal or timer across the complete system.- rec and send:
represents the PID values of the receiver and sender of the signal. See the subsection Processes and Process IDs (PID) for details. These are conditionally compiled.- prio:
is used to store the priority of the signal. This is specified by using the directive #PRIO in the SDL diagram. It is compiled only, if signals with priority are stipulated by the user.- timestamp:
is used to store a timestamp, which is set when the SDL signal is put into the queue (output time). This component is also conditionally compiled.- mess_length:
represents the amount of parameter bytes in the signal.Three different cases are to be considered concerning signals with parameters:
- If the signal has no parameters, then mess_length is set to 0 and ParPtr is a NULL pointer.
- If the signal parameters are larger than XMK_MSG_BORDER_LEN (*) bytes, then mess_length is set to the number of bytes and ParPtr is undefined.
- If more than XMK_MSG_BORDER_LEN (*) bytes of parameters are to be transferred, then mess_length defines the amount of bytes used for the parameters and ParPtr points to a dynamically allocated area.
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_SAVExmk_T_STATE SaveState;#endif /* XMK_USED_SAVE */} T_E_SIGNAL ;
- next:
is a pointer which refers to the next entry of the queue. This is used by the Cmicro Kernel to get the next signal after the current one has been worked on.- SaveState:
contains either a dummy state value XEMPTYSTATEID or the state in which the process saved the signal. This is necessary to compare when the signal is to be consumed after state changes in the receiver process. It is used only if save is used anywhere in the SDL system.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:
- 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.
- 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.
This configuration is not available when the preemptive scheduling mechanism is used.
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
- for signals which have 127 parameter bytes or less, the parameters are copied into the xmk_T_SIGNAL structure.
- for signals which have more than 127 parameter bytes, the parameters are copied into an allocated area (using the C function xAlloc()).
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
- charstring
- any ASN.1 sort that is based on charstring
- predefined Generators like Array (without a specified upper limit), String, Powerset, Bag, Ref
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.
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.
When working on a signal, the Cmicro Kernel decides between four different constellations:
- The receiving process instance is active. In its current state the signal is to be saved. The Cmicro Kernel tags the signal as "saved" and works on the next signal.
- The receiving process instance is active and there is a transition to be executed receiving the current signal. The Cmicro Kernel fires the transition.
- The receiving process instance is active but there is no transition to be executed for that signal in the current process state. The signal is in accordance with SDL rules implicitly consumed by the process.
- The receiving process instance is not active, i.e. either not yet created or already stopped. The signal will be discarded and the C function ErrorHandler(), discussed within the subsection User Defined Actions for System Errors - the ErrorHandler, will be called.
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.
- next is used to refer to the next entry;
- signal is the timer identification;
- time is used to store the absolute time when the timer should expire;
- OwnerProcessPID is used to refer to the process PID for which the timer was set.
As can be seen above, timers are implemented as a forward linked list.
- An array of timers is allocated during compile time
- The size of the array is calculated by the Cmicro SDL to C Compiler as the required maximum. It is defined by the macro MAX_SDL_TIMER_INSTS. This is also valid for multiple process instances, so that there is always enough memory to handle all timer instances which are possible. (If the user wishes to reduce the occupied RAM memory for timers, he must evaluate the maximum amount of timer instances required during run-time and modify the above define by hand).
- The timer which expires first is always put to the front of the linked list (increasing performance).
- The time value is stored as absolute time from the start of the SDL system.
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:
- Non Preemptive Scheduling:
Transitions in SDL cannot be interrupted.- Preemptive Scheduling with Process Priorities:
Transitions in SDL can be interrupted by any external or internal output. This could be a signal coming from the environment, i.e. an interface driver.- In addition, signal priorities can be used to specify the ordering of signals in the signal queue. Signal priorities are discussed in each of the subsections mentioned above.
General Scheduling Rules
- All of the above policies basically operate on the SDL queue. Physically, the Cmicro Kernel uses one array for all process queues in the system. From the SDL point of view, the implementation conforms to SDL because each SDL process virtually has its own queue in the implementation.
- signal priorities can be used in all cases.
- process priorities are given priority treatment.
- If no signal priorities are assigned, then the ordering of signals depends on their arrival (FIFO strategy).
- In order to increase the performance, there is no process ready queue implemented. The scheduling of processes is fully derived from the SDL queue.
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.
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.
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
The Cmicro preemptive kernel is only available if the according license is available.
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:
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
- At system start, SDL processes are statically created in accordance with their defined priority. During their start transitions it is possible for processes to send signals or create other processes but no preemption will take place until the start-up phase is completed, i.e. all static processes have completed the transition from start state to first state.
- Processes running on a priority level never interrupt other processes running on the same priority level, thus two instances of the same type never run at one time.
- A higher priority level is entered, if a signal results in a process with a higher priority running.
- A lower priority level is entered, if all signals on the currently active priority level are consumed so that still no process is running on this priority level.
- Global variables are used to store some information concerning processes. The Cmicro Kernel is responsible for the storing and reloading of these, if a preemptive kernel is implemented.
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:
- A typedef struct representing PID values (parent and offspring) stored for an instance
- A typedef struct representing SDL states of an instance
- A typedef struct representing SDL data of an instance
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.
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:
- A struct variable is initialized with the type of the signal parameters, not using memory allocation.
- The struct variable is then filled, parameter per parameter in generated code.
- One of the xmk_Send* functions is called with a pointer to the location of the struct variable. There are several xmk_Send* functions in order to use the most effective one in SDL output.
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.
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
- An ordinary SDL state change, the value is a C constant representing the SDL state as a simple integer (generated as #define),
- no SDL state change, indicated by the value SDL_DASH_STATE,
- SDL process stop operation, indicated by the value SDL_STOP.
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.
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:
- The location of data and how to access data
- Scope and visibility rules
- Procedures with states
- Recursivity
- Who can call a procedure
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.
TASK i := (call p(1)) + (call Q(i,k));is translated to something like:
i = p(1) + Q(i,k);
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 |
![]() |
![]() |
![]() |
![]() |