Статья посвящена проблемам построения средств трассировки систем жесткого реального времени. В настоящее время практически в каждой операционной системе реального времени (ОС РВ) имеются программные средства трассировки событий. Их задача состоит в поиске «обычных» программных ошибок (с которыми не справляются традиционные отладчики) и ошибок реального времени. При этом приходится анализировать не только последовательности событий, но и «утечки» памяти, динамику состояний процессора и потоков управления (профилирование), состояний семафоров, мьютексов и других средств синхронизации, а также очереди потоков управления, ожидающих освобождения необходимых им ресурсов. Рассматривается методология проектирования программ просмотра и анализа журналов событий (трасс), сформированных приложениями реального времени. Рассмотрены особенности отображения (в том числе, в виде деревьев) журналов событий и временных диаграмм состояний объектов анализируемой системы, представленных наборами данных, содержащими большое количеством записей. Предложено формальное описание моделей данных трассировки, механизмов их визуализации и механизмов управления запросами к записям трассы и состояниям объектов. Эффективность указанных моделей и механизмов подтверждена опытом эксплуатации программы просмотра и анализа протоколов событий ОС РВ семейства «Багет», реализованной с помощью библиотеки графических элементов GTK+.

Статья посвящена проблеме выявления и оперативного анализ ошибок, возникающих при эксплуатации гиперконвергентных систем. Одним из подходов к организации гиперконвергентных систем является установка на каждый физический сервер отдельного экземпляра операционной системы (ОС), несущей в себе средства виртуализации и инструментарий для администрирования и использования распределенного хранилища данных. Возникновение ошибок возможно как на уровне отдельного экземпляра ОС, так и на уровне всего кластера, Например, некорректные команды управляющих элементов с одного узла инфраструктуры могут вызвать сбой ПО на другом узле. Кроме того, ошибки со стороны подсистем кластера могут спровоцировать нештатные ситуации внутри виртуальных машин. Сложность архитектуры гиперконвергентных систем обуславливает сложность анализа возникающих в них ошибок. Для упрощения такого анализа и повышения его эффективности необходима автоматизация процесса обнаружения проблем и сбора данных, необходимых для их изучения и исправления. Рассматриваются подходы к автоматизации подобных процессов в существующих ОС и предлагаются способы их адаптации к системам, использующим распределенное хранилище данных и виртуализацию. Описывается опыт применения адаптированных решений в продуктах Virtuozzo.

Создание надежных беспилотных летательных аппаратов является важной задачей для науки и техники, потому что такие устройства могут иметь множество применений в современной жизни и в цифровой экономике, следовательно  необходимо обеспечивать надежность таких решений. В этой статье предлагается использование аппаратного прототипа квадрокоптера и разработка программного решения для полетного контроллера с высокими требованиями к надежности, которое будет соответствовать новым стандартам для программного обеспечения авионики и будет использовать существующие программные решения с открытым исходным кодом. В ходе исследования мы анализируем состав квадрокоптеров и полетных контроллеров для них. Мы описываем открытое программное обеспечение Ardupilot для беспилотных летательных аппаратов, контроллер APM и методы ПИД-регулирования. Сегодняшним стандартом надежного программного обеспечения для бортовых контроллеров являются партицированные операционные системы реального времени, которые способны реагировать на события от оборудования с ожидаемой скоростью, а также разделять процессорное время и память между изолированными разделами. Хорошим примером такой ОС с открытым исходным кодом является POK (Partitioned Operating Kernel). В репозитории она содержит пример описания системы для дронов с использованием языка AADL с моделированием аппаратного и программного обеспечения решения. Мы применяем такую технику к демонстрационной системе, которая работает на реальном оборудовании и содержит процесс управления полетом с PID-регулятором в виде изолированного процесса. Использование партицированной ОС выводит надежность программного обеспечения полетного контроллера на новый уровень. Для того, чтобы повысить уровень корректности логики управления, мы предлагаем использовать формальные методы верификации и демонстрируем примеры проверяемых свойств на уровне кода, используя дедуктивный подход, а также проводя моделирование на уровне киберфизической системы с использованием динамической дифференциальной логики для доказательства устойчивости.

В статье рассматривается задача записи управляемой исследователем стереовизуализации сложной динамической виртуальной сцены в видеопоследователь­ность стереопар (стереоролика) сверхвысокого разрешения. Предлагается технология отложенного синтеза стереороликов, которая позволяет создавать такие стереоролики, не нарушая масштаб реального времени визуализации. Технология включает в себя построение в масштабе реального времени сценария процесса визуализации и офлайн-преобразование сценария в стереоролик. В работе рассматриваются методы реализации этих этапов на примере задачи стереовизуализации изоповерхности насыщенности вытесняющей жидкости. В исследовании предлагается разработанный оригинальный файловый формат «scr» сценария визуализации, основанный на чанковой структуре данных, который реализует компактное представление соседних одинаковых кадров. Преобразование файла сценария в последовательность 4K-стереопар выполняется с помощью технологии внеэкранного рендеринга виртуальной сцены, а добавление стереопар в стереоролик – с помощью набора открытых библиотек FFmpeg обработки цифровых видеозаписей. В основе стереоролика используется медиаконтейнер MP4 и стандарт H.264 сжатия видео (оба являются частями международного стандарта MPEG-4). Предложенные технология и методы отложенного синтеза 4K-стереороликов реализованы в программном комплексе визуализации результатов моделирования неустойчивого вытеснения нефти из пористых сред. С помощью данного программного комплекса был синтезирован 4K-стереоролик, иллюстрирующий процесс изменения изоповерхности насыщенности вытесняющей жидкости на стадии развития процесса неустойчивого вытеснения нефти. Проведенная апробация подтвердила адекватность созданных решений поставленной задаче. Разработанные решения могут быть использованы в виртуальных лабораториях, при построении систем виртуального окружения, систем научной визуализации, в образовательных приложениях и др.

Растущая популярность смартфонов привела к появлению большого количества мобильных приложений. Мобильные приложения динамичны по своей природе, поэтому классические подходы к разработке для них не подходят. Индивидуальные потребности пользователей, новые технологии, необходимость снижать энергопотребление и многие другие факторы побуждают разработчиков поставлять на рынок все новые и новые приложения. Однако из-за отсутствия формальных и специализированных для данной области практик разработки с мобильными приложениями связано множество различных проблем. Наличие таких проблем отрицательно сказывается на качестве приложений и на их восприятии конечными пользователями. В этой статье рассматриваются пятнадцать различных проблем, связанных с мобильными приложениями. Мы применили метод fuzzy-DEMATEL для анализа таких критически важных факторов и выделили среди этих факторов группы в соответствии с причинно-следственными связями. Сначала группа экспертов оценивает непосредственные связи между существенными проблемами мобильных приложений. Результаты оценок представляются в виде треугольных нечётких чисел (triangular fuzzy numbers,TFN). На втором шаге в TFN преобразуются лингвистические термины. На третьем шаге при помощи методов DEMATEL выполняется причинно-следственная классификация проблем. Проблемы из группы причин идентифицируются как критически важные в области разработки мобильных приложений. Результаты исследования сравниваются с другими вариантами DEMATEL, такими как G-DEMATEL и E-DEMATEL. Результаты сравнения показывает, что fuzzy-DEMATEL является наиболее подходящим методом анализа взаимосвязей между различными проблемами мобильных приложений. Выводы, содержащиеся в этой работе, могут способствовать эффективной идентификации значимых проблем, на которых должны быть сфокусированы усилия специалистов и менеджеров проектов в индустрии мобильных приложений.

Описывается подход к тестированию искусственных нейронных сетей, реализованный в программе на языке Си++ в виде набора структур данных и алгоритмов их обработки. В качестве структур данных используются классы языка Си++, реализующие работу с такими объектами, как вершина графа, ребро, ориентированный и неориентированный граф, остовное дерево, цикл. Приводятся интерфейсы важнейших перегруженных операций над используемыми объектами и тестирующих процедур. Дан пример реализации одной из тестирующих процедур, использующий перегруженные операции над используемыми объектами.

В статье рассматривается задача обучения с учителем: требуется восстановить зависимость, отображающую векторное множество в скалярное по конечному набору примеров такого отображения – обучающей выборке. Данная задача относится к классу обратных задач, и, как и большинство обратных задач, является математически некорректной. Это выражается в том, что если строить решение методом наименьших квадратов по точкам обучающей выборки, то можно столкнуться с переобучением – ситуацией, когда модель хорошо описывает обучающее множество, но дает большую ошибку на тестовом. Нами применяется подход, когда решение ищется в виде ансамбля предиктивных моделей. Ансамбли строятся с использованием метода бэггинга. В качестве базовых обучаемых моделей в работе используются персептроны и деревья решений. Конечное решение получается путем взвешенного голосования предикторов. Весовые коэффициенты подбираются путем минимизации ошибки ансамбля на обучающей выборке. Для борьбы с переобучением при подборе весовых коэффициентов применяется байесовская регуляризация решения. Чтобы подобрать параметры регуляризации, в работе предложено использовать метод ортогонализованных базисных функций, который позволяет получить их оптимальные значения без использования ресурсоемких итерационных процедур.

Задача маршрутизации – одна из широко известных задач комбинаторной оптимизации. Она состоит в отыскании оптимального множества маршрутов для транспортных средств с целью однократного обслуживания определенного множества клиентов. В данной работе исследуется подвид задачи маршрутизации – задача маршрутизации с ограничением по грузоподъемности, в которой каждое транспортное средство имеет свою грузоподъемность. Задача является NP-трудной, поэтому вместо точных алгоритмов решения исследуются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. Данная работа является продолжением исследования, посвященного алгоритмам конструирования маршрута; оно позволяет получить первоначальные решения для данной задачи. Было выяснено, что эвристика Clarke and Wright Savings (CWS) является одной из лучших, за исключением наборов данным с геометрическим расположением точек, для которых лучшим является алгоритм Nearest Neighbor (NN). Целью работы является сравнение локально-оптимальных метаэвристических алгоритмов решения задачи маршрутизации с ограничением по грузоподъемности по двум критериям: точность и время решения, для получения начального решения используются алгоритмы CWS и NN. Выявлено пять Парето оптимальных групп алгоритмов для различных типов входных данных. Интересно, что алгоритм «Lin, Kernighan and Helsgaun heuristic» (LKH-3), входящий во все Парето оптимальные группы для смежной задачи (задача коммивояжера), в данном случае вошел только в четыре группы из пяти.

UML диаграммы деятельности широко используются для представления процессов в программной инженерии. Модели, построенные по журналам событий, могут предоставить ценную информацию о реальные процессах в информационных системах, на основании которой эти процессы можно улучшить. Данная статья представляет новый метод майнинга UML диаграмм деятельности по журналам событий. Метод основам на параметрической схеме, которая состоит из трех вложенных ступеней, включающих в себя набор преобразований над моделями. Начальная модель извлекается из журнала событий один из существующих алгоритмов синтеза. Эта модель, если требуется, преобразуется в промежуточную форму, и затем конвертируется в целевую диаграмму деятельности с помощью предлагаемого алгоритма. Алгоритмы синтеза, помимо используемого на последней стадии, являются параметрами схемы и могут быть изменены, исходя из имеющихся или требуемых моделей. В статье представлены примеры применения подхода к журналам событий из реальной жизни.

Журналы событий программных систем используются для анализа их поведения и взаимодействия между компонентами. Искусственные журналы событий с подходящими свойствами необходимы для тестирования алгоритмов, используемых для такого анализа. Современные методы позволяют генерировать искусственные журналы событий в результате симуляции обычных сетей Петри. В этой статье мы представляем алгоритм, генерирующий журналы событий для сетей Петри с ингибиторными дугами и дугами сброса. Сети с ингибиторными дугами более выразительны, по сравнению с классическими сетями Петри, и позволяют удобно моделировать условия в реальном программном обеспечении. Операции сброса также распространены в реальных системах. В этой статье описывается алгоритм симуляции сетей Петри с ингибиторными дугами и сбросами, а также показано, каким образом его можно применять для генерации журнала событий.

В данной статье представлен подход к реализации алгоритма вычисления приоритетов срабатывания переходов для живых сетей Петри. Приоритеты являются одной из форм условий срабатывания и могут быть присвоены переходам для обеспечения живости и ограниченности сети Петри. Наличие этих свойств крайне желательно при анализе различных систем, начиная от бизнес-процессов и заканчивая встраиваемыми системами. Необходимость в них обусловлена ограниченностью ресурсов, характеризующей большинство систем из реальной практики. Рассматриваемый в данном исследовании алгоритм для вычисления приоритетов срабатывания переходов имеет экспоненциальную временную сложность, так как основан на процедурах построения и обхода графа покрытия. Однако, его производительность может быть достаточна для большинства практических целей. В данной работе затронуты различные аспекты проектирования реализации, включая подход к решению проблемы высокой сложности алгоритма и примененные к нему оптимизации. В качестве основного метода повышения производительности алгоритма были выбраны параллельные вычисления. Не смотря на то, что для одних шагов алгоритма данный подход продемонстрировал свою жизнеспособность, для других его эффективность оказалась не столь однозначной. В работе представлен анализ различных решений. Также, на основе реализации алгоритма было разработано приложение для вычисления приоритетов срабатывания. Данное приложение может быть использовано для дальнейших исследований реальной применимости алгоритма.

Конечно автоматные методы широко используются при синтезе проверяющих тестов с гарантированной полнотой для дискретных систем. Поскольку поведение современных информационных и управляющих систем часто зависит от времени, классическая модель конечного автомата расширяется введением временных переменных. Более того, опциональность в спецификациях реальных систем побуждает к исследованиям в области синтеза тестов для недетерминированных автоматов. В настоящей работе мы адаптируем классические конечно автоматные методы синтеза тестов к недетерминированным автоматам с временными ограничениями и таймаутами (временным автоматам). Показывается, что в отличие от классических конечных автоматов, проверка отношений конформности между временными автоматами не может быть сведена к проверке соответствия между переходами, что нарушает основной принцип конечно автоматных методов синтеза тестов. Соответственно, предложенный подход и модель неисправности основаны на конечно автоматной абстракции автомата-спецификации, которая используется для описания поведения временного автомата. Область неисправности содержит временные автоматы с известной верхней границей числа состояний конечно автоматных абстракций и позволяет избежать явного перечисления множества тестируемых реализаций. Мы исследуем свойства конечно автоматных абстракций недетерминированных временных автоматов и показываем, что использование такой абстракции позволяет адаптировать классические методы к синтезу тестов с гарантированной полнотой для временных автоматов. Предложенный метод синтеза тестов позволяет строить полные проверяющие тесты для полностью определённых возможно недетерминированных автоматов с таймаутами и временными ограничениями для тестирования реализаций, поведение которых описывается детерминированными временными автоматами.

Рассматривается распределённая сеть, граф связи которой является неориентированным деревом. Предполагается, что сеть может сама менять свою топологию. Для этого предлагается предельно локальная атомарная трансформация – добавление ребра, соединяющего разные концы двух смежных ребер, и одновременное удаление одного из этих ребер. Такая трансформация выполняется по «команде» от вершины дерева, а именно, общей вершины двух смежных ребер. Показывается, что из любого дерева можно получить любое другое дерево с помощью только атомарных трансформаций. Если рассматриваются деревья с ограничением d (d ³ 3) на степени вершин, то трансформация не нарушает этого ограничения. В качестве примера цели такой трансформации рассматриваются задачи максимизации и минимизации индекса Винера дерева с ограниченной степенью вершин без изменения множества его вершин. Предлагаются соответствующие распределённые алгоритмы и доказываются линейные оценки их сложности.

Графовая модель данных активно используется в научных и прикладных областях, например, в графовых базах данных, биоинформатике, при анализе социальных сетей и в статическом анализе кода. Одной из основных задач, связанных с графовыми моделями, является поиск специфичных путей в графе. Естественным способом задать ограничения на пути являются формальные грамматики над метками рёбер графа, при этом запрос к графу может быть представлен в виде множества всех троек , для которых существует путь в графе от вершины  до вершины  такой, что метки на ребрах этого пути образуют строку, выводимую из нетерминала  в данной грамматике. Использование булевых грамматик позволяет формулировать более выразительные запросы по сравнению с традиционно используемыми регулярными и контекстно-свободными грамматиками. Известно, что задача выполнения запросов к графу с использованием булевых грамматик является неразрешимой. В данной работе предложен приближённый алгоритм поиска путей в ориентированных графах без циклов с ограничениями, заданными с помощью булевых грамматик. Благодаря ограничению на тип анализируемых графов, предложенный алгоритм является более асимптотически оптимальным, чем наивный итерационный алгоритм.