In high-level program languages, actions are designed by using methods. A method represents a communication between a sender that calls the method and a receiver that executes its program. The sender and receiver can belong to the same module. However, the sender and receiver (usually) represent different program blocks. This implies that a program block that is part of a method may call another method. It may even call its containing method. Careless usage of the latter may cause stack overflows.
A routine is the software implementation of a method. In software, routines, macro’s and inliners are used to implement the methods and memory is used to create the placeholders that represent the assets. Macro’s and inliners translate to internal code of routines. The body of a routine contains operands or operations that are more complex. They represent the actions that are implemented by the programming language. Beside of these operands, the body of a routine contains execution path selectors. These selectors enable the fine grain scheduling.
Modeling of dynamic systems in software introduces extra aspects that are not present in the subject that is modeled. This is due to the way memory is used. It is also due to the way that routines are reused. Processing units must be shared amongst the routines that implement concurrent operations.
In order to provide sufficient acuity and concurrency, the operations are spread over a series of threads. Threads have priorities that determine the access of the tread to the cycles of the processing units. The priority of a thread is derived from the priority of the task that currently runs on the thread.
In software, a task is implemented by a network of connected routines. This bunch of routines may be spread over a series of modules. During its execution, the task only uses a part of these routines. The used routines form a trail of methods and a corresponding communication path. The trail represents the operation that executes the task. During this execution, the routines check the assets that are accessible in its domain. The values of these assets are used by the path selectors in the task to navigate through the body of the routines and through the network of routines that implement the task. The navigation inside these routines and through the network of routines represents the fine grain scheduling of state transitions that is performed by the task itself. Course grain scheduling is done by a centralized task scheduler. However, this may be done on the instigation of a normal task.
Program blocks may contain nested program blocks. A routine always contains a program block. A program block may have private assets. These assets are only used internally. Software assets use pieces of the available memory to store their values. The size of the memory block depends on the type of the asset. Volatile memory can be used in different ways:
· Static: The memory location is fixed. When a routine is reused, that location and its contents stay available to this routine.
· Automatic: The memory location is only temporary available and is only assigned to a single run of the routine.
· Heap: The memory is obtained via a special request to a memory manager. The memory manager supplies a pointer to the returned memory area. This pointer is stored in a static or automatic memory location. Until it is explicitly released, the returned memory area plays the role of static memory.
A program block can also make use of other placeholders. Within a proper module, the attributes are placeholders that are accessible to all local routines. Each instance of a module has its own set of memory locations for the non-class-wide attributes. The parameters of routines are placeholders for the transmitted asset values. In principle, these placeholders can be reused. However, this practice may lead to confusion. It must be handled with the greatest care and it should be avoided when it is not strictly necessary.
There are two kinds of static memory: global and local. Local memory can only be accessed from within the program block, including the program blocks that are nested within the block. Global memory can be accessed by other program blocks as well. Within a module, the instance-specific and the module-wide assets are accessible for all program blocks. Other usage of global memory must be considered as bad practice. It makes memory management and value protection unworkable in complex situations.
Static memory must only be used when values must be exchanged between different crossings of the same program block. These memory locations are shared between tasks that use this program block. In real-time systems, the use of shared memory must be done with great care.
Memory obtained from the heap must be released when it is no longer in use. This can be done by the program block that made the request or by another routine, which is also using that memory location. In the latter case, a mechanism must be present that can detect whether the memory location is still in use. For example, Microsoft’s COM and the embedded component model that is used in the demonstration toolkit use reference counting for this purpose. In Microsoft’s COM this task is accomplished by the clients of the component. In the embedded component model, this is done by the infrastructure. The solution taken in the embedded component model enables the possibility to implement lightweight automated garbage collection for the dynamic instances of this component model.
Parameters can be passed by value or by reference. If a parameter is passed by value, a new placeholder is created automatically and a copy of the value is placed in that location. If a parameter is passed by reference, then only a placeholder for the reference is created and the value of the original asset is not copied. The parameters are placeholders and these places are available for reuse by the routine. This must be avoided or it must be done very carefully, because it can easily create confusion.
When an operation is divided in a trail of methods, the assets that are local to the operation must in general be passed by reference in a parameter from one section of the trail to the next section. However, if the local asset takes less or nearly the same memory space than the reference, then it is considered better to pass the local asset by value.
A routine performs its own fine grain scheduling. This is done by program instructions that perform an execution path selection. Examples of such selectors are if statements, loop controllers, case switches and method calls. The body of a routine contains operators that represent actions that are implemented by the program language. It must be reckoned that even these operators can be interrupted by the thread switcher. The implementation of the language or a special repair task must take care of the corresponding repair action that is necessary when the primary task is stopped.
Software tends to use the higher-level descriptors rather than the atomic descriptors. This may present problems when resource-restrictions or other causes of triggers break-up the sequence of state transitions that constitutes the method, which is currently executed. A possible resource restriction may be posed by the accessible processor time. This plays an important role in real-time systems.
If during the run of the stopped task a module has claimed resources, without releasing them or when its assets are left with values that are not expected by future clients, then the module is in an unsafe state. This must be compensated by an appropriate repair action.
A system that breaks these rules cannot behave according to the specification. Such systems can never be specified completely. This means that they can never be tested completely. With other words, the behavior of such systems cannot be guaranteed.
The occurrence of unsafe states can be prevented by using programs that avoid the use of static assets or by using critical sections on places where static assets are handled. Critical sections must always be short. On their turn, critical sections can cause faulty behavior, such as deadlocks and race-conditions.
In real-time systems, it is often necessary to be able to disrupt a task at any instance. This would create the unworkable necessity to plan a potential scheduling action at every clock tick. A solution is to start a repair action after stopping the current task. The repair action must set the modules that have been passed by the current task to a safe state. This means, that after repair the modules are left in a state that clients of the module expect when they want to make use of that server.
A method that causes an unsafe state when it is stopped before it ended its normal execution is a vulnerable method. A method that calls a vulnerable method that belongs to the same module is also vulnerable. Every vulnerable method must be accompanied by a repair method. The repair method must belong to the same module as the vulnerable method. If an interface method is vulnerable, then it must be accompanied by an interface method that acts as a repair method. The repair method may reside in another interface than the primary method. A single repair method can compensate a set of vulnerable methods. A repair method that is also an interface method may compensate vulnerable private methods. For example, the base interface contains a reset method that may also include the required cleanup processing. This method may serve as a general repair method. However, bluntly resetting an instance of a component class is not always a tolerated solution. Another way to implement a repair method is to use the same entry point as the primary method and use a Boolean parameter to distinguish between the primary task and the repair task.
It is wrong to think that, where the primary task represents a trail that sequentially passes a series of modules, the repair task must travel the same trail. A task may own a set of required connections to instances of module classes. Each of these module classes may have requested connections for their own purpose. A repair task may be an action that resets the modules that are connected according to the required connection scheme. When a module is reset, it will also release its requested connections. This brings all involved modules in a save state. The garbage collector will reclaim the memory that was occupied by freed instances that where created because of a connection request. Freed instances are dynamic instances that are no longer used by any other instance. This is the simplest way to implement a repair task. It is possible to implement the repair task in much more subtle way.
If a client module calls a vulnerable method of a server module, then the calling method may also be vulnerable, but it is quite possible that that method and its calling sequence did not cause unsafe states. If a method that is used by a subtask is vulnerable then that subtask is vulnerable. A vulnerable subtask must be accompanied by a repair task.
If the primary task is stopped, then the repair task must be started. If all modules that are crossed in the first part of a trajectory of the primary task are left in a safe state, then the repair task may start at the point where the first unsafe module state occurs. The design of the system will usually determine the start location of the repair task that corresponds with a given primary task. The simplest, but not necessarily the most efficient solution is to start the repair task at the same location where the primary task was started.
If the primary task is a periodic task, then the repair task must also end before the end of the period. If the primary task is sporadic, then the designer decides whether the repair task must also end before the deadline of the primary task. If the task pair only needs to reach a soft deadline, then the designer may choose to start the repair task after the deadline of the primary task.
During repair, the scheduler must prevent that other tasks make use of unsafe modules.
Starting a potentially vulnerable method with a reset action is in general not a good alternative for a repair method. It will only suffice, when all methods of the corresponding module would start with a reset action. Introducing a repair method is usually better manageable and more efficient.
In component-based systems, the tasks that have deadlines or that may be halted for other reasons, are always paired. The pair consists of a primary task and a repair task.
When properly configured, the primary task and the repair task can together guarantee a hard deadline. In that case, the primary task is treated as a soft deadline task. In order to determine the priority of the primary task, the scheduler uses the expected execution time of that task. If a hard deadline must be guaranteed, the repair task must be treated as a hard deadline task. In order to determine the priority of the repair task, the scheduler uses the worst-case execution time of that task. The time aware fault tolerant (TAFT) scheduling algorithm may be applied to this case. See: “Execution environment for dynamic scheduling real-time tasks” by L.B. Becker and M. Gergeleit. [http://ivs.cs.uni-magdeburg.de/EuK/Publikationen/RTSS01_WIP.pdf]
Tasks must never be stopped or paused during the pass of a critical section. Stopping tasks introduces the need for a repair action. The reason for stopping a task is not restricted to the case that a deadline is, or will be missed. Another reason is that some of the required resources are no longer present or the fact that reaching the target is no longer required.
A task may stop autonomously when it reaches its target. In that case, it must notice the task scheduler. Usually this is done by a return of the method that was called at the start of the task. The task scheduler may then start another task or it may restart at the proper instant a new cycle of the same task.
Carelessly pausing a task may also leave modules in unexpected states. Starting a repair task is only useful after stopping a task. Thus, pausing tasks must only be done when no modules will be left in an unexpected state. During the pause, other tasks must not obstruct the paused task.
A task must indicate to the scheduler that it can be paused without causing problems.