To the question on implementation of multi-version execution environment software of onboard autonomous unmanned objects by means of real-time operating system

Introduction. The task of designing and software implementation of multiversion on-board software (OBS) of autonomous unmanned objects (AUO), is not trivial [1; 2]. At the same time, the task of forming a multiversion environment is no less important. There are a number of conditions necessary to ensure the operation of such an environment. Firstly, the implementation of an adequate mechanism of voting [3]. Secondly, to ensure data exchange between software modules. Thirdly, to provide a mechanism for extrusion of module in case that a similar decision is made by the arbitrator, as well as the subsequent addition of a new module, to maintain the specified reliability indicator of OBS AUO.

Search of solution. One of the approaches to implementation multi-version execution environment – implementation of the principle of a pseudo-parallelism. For example – the imitation of parallel execution of tasks by dividing their execution time. Such a functional principle is realized by the real-time operating system RTOS (realtime operating system), namely one of the versions – FreeRTOS [4] ported. This version is portable i. e. adapted for execution on the SoC (System on a Chip) [5].

Consider the schedule (fig. 1) of process of message exchange between multiple tasks implementation. Exchanging process implement procedure of voting result return by queuing mechanism implemented by FreeR-TOS.

Task-receiver is a task that realizes the collection of data from N -version modules (Task-1, Task-2, …, Task- N ) with the purpose of subsequent decision by the arbitrator, however, in the described process performing only the receiver function [5; 6].

Task-1, -2 – these are tasks that interpret N -version modules [7; 8], which implement functions of OBS AUO.

Fig. 1. Cyclogram of message exchange process between multiple tasks

Рис. 1. Циклограмма процесса обмена сообщениями между задачами

Algorithmizing the messaging process. The time component of the given cyclogram is distributed over equal time quanta.

Time point “0” – Initialized launch of FreeRTOS planner, which uses the “execution” status of the task with the highest priority. In this instance it is Task-Receiver (Com. API-function vTaskSrartScheduler() is responsible for the launch of the scheduler, API-function xTaskCreate() is responsible for task creation).

Time point “1” – Task-Receiver initiates an attempt to read an item from the queue, but goes into the “blocking” state, since the queue is empty at the time it was created. In this state Task-Receiver resides until the data occur in the queue, or up to the moment of time-out (120 ms). The next stage is the transition to the “execution” state of one of the Task-transmitters. (Task-1 or Task-2). It is not possible to declare, which task will go into this state, because each of them has equal priority. Let’s suppose, this is Task-1 (Com. API-function vTaskSuspend()and vTaskResume() are respectively responsible for transition to the “blocking” state and exit from it).

Time point “2” – Task-1 writes a value “25” in the created empty queue. There is a return from “blocked” state at this point. Main function of this task is to capture data from the queue, and its priority is the highest (Com. API-function xQueueCreate(), is responsible for queue creation. To write an element to the end of the queue – FIFO principle implementation, API-function xQueue-SendToBack() is used, to write an element at the beginning of the queue – FIFO principle implementation, API-function xQueueSendToFront() is used).

Time point “3” – After accessing the queue and reading the data from it, the Trader-receiver is blocked again, since the queue is now empty. Control returns to the interrupted Task-1, which runs by call scheduler API-function taskYIELD() (Com. API-function xQueueReceive(), is responsible for reading element followed by removing it from the queue).

Time point “4” – The scheduler converts to the “execution” state an equitable Task-2, which, in turn, records the value of “50” in the queue.

Time point “5” – Leaves the “blocking” state of the high-priority Task-receiver and reads the data from the queue. Iteration of the loop happens next (Com. The current value of the time quantum counter may be received through API-function xTaskGetTickCount() ).

Status of tasks during the system operation. The software system running under FreeRTOS, consists of a set of tasks. Tasks carried out separately, and in their own context. The scheduler controls the execution order, the change of tasks and their contexts. Each task has its own stack. Thread context is stored in stack extracted from the stack, when you pause and resume execution, respectively. Fig. 2 shows possible state of tasks. New readymade task is created by command xTaskCreate(). The scheduler provide it with a time quantum for execution. The scheduler can leave thread in “ready” state if it is possible, taking into account the priorities or until such an opportunity arises. Also it is possible to send to the “blocking” state with the vTaskSuspend() command, from which only the scheduler can issue it by the vTask-Resume() command. From the “execution” state, the task can be transferred back to the “ready” state if it has not finished its work. However, the scheduler can decide to switch the task. For example, if a task with a higher priority has switched to a “ready” state. If the task needs to wait (the appearance of the element in the queue, the release of the mutex, the switching of the traffic light, and so on), then it is translated into the “waiting” state. Which can also be done by the command vTaskDelay(),setting the timeout after which the task goes into the “ready” state. When the expected event appears, the thread will be transferred to the ready state. By vTaskSuspend() command you can send the task from “execution” state to “blocking” state. If several tasks are in the “ready” state, the scheduler executes the task with the highest priority. Herewith tasks with lower priority are executed only after the higher priority task does not go into the “waiting” or “blocking” state. Task in the “waiting” or “blocking” state do not spend CPU time. The main difference between them is that the task in the “blocking” state does not respond to any events. And can be removed from this state only by the vTaskResume () command manually.

Fig. 2. Possible state of tasks

Рис. 2. Возможные состояния задач

Conclusion. This example demonstrates the messaging mechanism. According to which, value, placed in queue by task, represented by constant. This task interprets N -version modules (Task-1, -2). Returned by the module as a result of voting true value, demands additional algorithmization of N -version module [9; 10]. While the value generated by the module can take a different format, including the format of both boolean and integer variables [11], depending on voting mechanism [12]. Thus, the messaging mechanism, together with the scheduler, and the priority system implemented by FreeRTOS tools, allow you to build more flexible algorithms of voting, able to vary the weights of N -version modules, and as a consequence, affect the reliability of the multiversion software [13], including for the implementation of a multiversion environment for the execution of OBS AUO. In addition, thanks to the priority system, implementation of algorithm for changing the priority of each module, depending on its weight (reliability rating) is possible. This solution in conditions of limited resources will ensure the priority execution of the most error-free versions. Moreover, improve the reliability of the multiversion system in cases where, due to the limitation of the computing resources of the hardware platform, it is impossible to execute all versions within a specified period. Thus, the most reliable versions will not only have more weight in voting, but will be performed first, also. With the help of the priority system, the time limit for issuing answers to versions is limited. Task-receiver with the highest priority through the given time quantum reads all the responses from the queue and deletes (vTaskDelete ()) versions that did not have time to respond in time.

As a result of further analysis of mechanisms of the functioning of FreeRTOS and other real-time operating systems, one can note potential problems:

• 1.    Inversion of priorities – а situation in which Traid-1, which has priority higher than Task-2, expects completion of its work, since Task-2 was the first to capture the mutex. The peculiar feature of the mutex capture is that

• 2.    Interlocking – The situation is possible when several tasks need to access the same resources for its completion:

only the thread that captures the mutex takes the decision to release it. The mutex release occurs only when the thread does its work, regardless of its duration and the priority value of other threads.

Task-1 is executed, captures mutex A, its performance is interrupted by Task-2, captures mutex B, tries to capture mutex A, because it is busy, switches to standby, Task-1 continues its execution, tries to capture mutex B, since it is busy, it’s also goes into waiting. As a result, both tasks will not release needed mutexes and will be in the standby mode, effectively blocking each other.

We can exclude the occurrence of mutual interlocking during system design. Moreover, we can exclude the inversion of priorities or minimize the negative consequences when it occurs.