TO THE QUESTION ON IMPLEMENTATION OF MULTI-VERSION EXECUTION ENVIRONMENT SOFTWARE OF ONBOARD AUTONOMOUS UNMANNED OBJECTS BY MEANS OF REAL-TIME OPERATING SYSTEM

Texto integral

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 envi- ronment is no less important. There are a number of con- ditions necessary to ensure the operation of such an envi- ronment. 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 simi- lar decision is made by the arbitrator, as well as the sub- sequent addition of a new module, to maintain the speci- fied reliability indicator of OBS AUO. Search of solution. One of the approaches to imple- mentation multi-version execution environment - imple- mentation 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 (real- time 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. Ex- changing 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 begin- ning of the queue - FIFO principle implementation, API- function xQueueSendToFront() is used). Time point “3” - After accessing the queue and read- ing the data from it, the Trader-receiver is blocked again, since the queue is now empty. Control returns to the inter- rupted 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 “exe- cution” 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 cur- rent 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, respec- tively. Fig. 2 shows possible state of tasks. New ready- made 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() com- mand 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 re- spond 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 messag- ing mechanism. According to which, value, placed in queue by task, represented by constant. This task inter- prets N-version modules (Task-1, -2). Returned by the module as a result of voting true value, demands addi- tional algorithmization of N-version module [9; 10]. While the value generated by the module can take a dif- ferent format, including the format of both boolean and integer variables [11], depending on voting mechanism [12]. Thus, the messaging mechanism, together with the sched- uler, and the priority system implemented by FreeRTOS tools, allow you to build more flexible algorithms of vot- ing, 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 mul- tiversion 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 en- sure the priority execution of the most error-free versions. Moreover, improve the reliability of the multiversion sys- tem 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 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. 2. Interlocking - The situation is possible when sev- eral tasks need to access the same resources for its com- pletion: Task-1 is executed, captures mutex A, its performance is interrupted by Task-2, captures mutex B, tries to cap- ture 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 conse- quences when it occurs.

Sobre autores

I. Kovalev

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

V. Losev

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

M. Saramud

Reshetnev Siberian State University of Science and Technology

Email: msaramud@gmail.com
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

D. Kovalev

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

M. Petrosyan

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

V. Brezitskaya

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

Bibliografia

Arquivos suplementares