Математическое моделирование восстановления деревьев процессов на графах реконструкции тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Ефанов Николай Николаевич

• Ефанов Николай Николаевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Ефанов Николай Николаевич

Введение

Глава 1. Обзор

1.1 Задача сохранения и восстановления по контрольным

точкам (Checkpoint-Restore)

1.1.1 Терминология

1.1.2 Применение Checkpoint-Restore процессов

1.2 Обзор существующих решений Checkpoint-Restore

1.3 Ориентированные графы и деревья

1.3.1 Терминология

1.3.2 Алгоритмы на графах и структуры данных

1.4 Частично-упорядоченные множества, полурешётки и замыкания

1.4.1 Частично упорядоченные множества, решётки и полурешётки

1.4.2 Замыкания и пред-замыкания

1.5 Конечные автоматы, формальные языки и грамматики

1.5.1 Языки и грамматики

1.5.2 Конечные автоматы

1.6 Особенности разделения ресурсов в Unix-подобных операционных системах

1.6.1 Иерархия процессов в Unix-подобных ОС

1.6.2 Ресурсы процессов

1.6.3 Атрибуты процессов

1.6.4 Системные вызовы

1.6.5 Сессии и группы процессов

1.6.6 Пространства имён

Глава 2. Построение математической модели

восстановления дерева процессов

2.1 Исследование деревьев процессов

2.1.1 Комбинаторные оценки числа различных деревьев

процессов

2.2 Исследование синтаксических свойств деревьев процессов . . 45 2.2.1 Атрибутная грамматика деревьев процессов

2.3 Атрибутные свойства деревьев процессов

2.4 Математическая модель атрибутного восстановления дерева процессов

2.4.1 О корректности дерева процессов

2.4.2 Моделирование роста дерева процессов набором конечных автоматов

2.4.3 Общие свойства графа реконструкции

2.5 Формальная постановка задачи реконструкции

2.6 Разработка алгоритма реконструкции для подмножества атрибутов

2.6.1 О проверке значений атрибутов

2.6.2 Стадии работы алгоритма реконструкции

2.6.3 Стадия пост-обработки графа реконструкции

2.6.4 Свойства построенного алгоритма реконструкции

Глава 3. Формальный анализ зависимостей в графах

реконструкции

3.1 Зависимости и иерархии атрибутов

3.1.1 Отношение зависимости по атрибутам и связанные определения

3.1.2 Полурешётка состояний процессов

3.1.3 О предзамыканиях и замыканиях на полурешётке V +

3.1.4 Типы атрибутов и их зависимости

3.1.5 О формальной корректности дерева процессов

3.2 Связь аномалий в графах с нарушением полурешёточной упорядоченности

3.2.1 Исправление аномалий на полурешётке

3.2.2 Альтернативные способы внесения исправлений

3.3 Обобщённый алгоритм построения графа реконструкции

3.3.1 Построение обобщённого алгоритма

3.3.2 О росте числа промежуточных состояний при реконструкции

3.3.3 Восстановление подмножества процессов, не изолированного в контейнер

3.4 Заключение

Глава 4. Программный комплекс и численное моделирование

4.1 Описание программного комплекса

4.2 Численный эксперимент

4.2.1 Постановка эксперимента

4.2.2 Тестовые нагрузки

4.2.3 Результаты эксперимента

4.3 Заключение

Заключение

Список рисунков

Список таблиц

Приложение А. Элементы синтаксического анализа

дерева процессов в строчной нотации

Введение диссертации (часть автореферата) на тему «Математическое моделирование восстановления деревьев процессов на графах реконструкции»

Введение

В диссертационной работе рассматривается построение математической модели реконструкции дерева процессов при восстановлении состояния набора приложений из снимка состояний или из упрощённого атрибутного описания [1—5]. Данная задача связана с активно развивающимися в последнее время технологиями сохранения-восстановления состояний окружения исполнения в ОС [1—3; 6], виртуализации [1; 2; 7—10], и, как следствие, является подзадачей ряда актуальных задач, решаемых программными комплексами: живой миграции и балансировки нагрузки [1; 9; 11; 12], контейнерной виртуализации [1; 8—10], восстановления после сбоев [13—15] , отложенной отладки [16], ускорения загрузки приложений [12; 17], остановки/возобновления работы приложений [2; 6; 16], поддержки инфраструктуры в системах высокопроизводительных вычислений [4; 5; 18; 19].

Существующие на момент проведения исследования индустриальные и исследовательские системы сохранения-восстановления так или иначе решают задачу восстановления дерева процессов: любая такая система, работающая в Unix-подобной ОС, поддерживающая многозадачность и разделение ресурсов, должна обеспечивать реконструкцию иерархии процессов, их изоляцию - разделение на группы, сессии, пространства имён, осуществлять передачу наследуемых и разделяемых иными способами ресурсов в правильном порядке, что обуславливается переводом дерева процессов в надлежащее состояние. Способы такого восстановления различны. Существует класс решений, осуществляющий запись активности программ в ходе работы, с последующим воспроизведением данной активности при восстановлении (БЫТС^ [5], ^ [19], Pin/PinPlay [20; 21] и др.). Такой подход имеет ряд недостатков, связанных как со сложностью обеспечения прозрачности переноса состояния относительно целевого приложения, так и со сложностью сохранения-воспроизведения активности: накладными расходами на запись, платформозависимостью. Другой класс решений производит восстановление на основе эвристического анализа данных снимков

состояния (СШи [3; 22], БЬСИ, [4; 11]). Как правило, такие решения имеют в своей основе фиксированные последовательности шагов по восстановлению, покрывающие конкретные случаи деревьев процессов. Такой подход также обладает недостатками в смысле надёжности и универсальности: существуют особые случаи [23; 24], в которых эвристические решения генерируют некорректные последовательности действий или выходят из строя [23]. Также следует отметить, что ряд решений [4; 5; 7; 11; 25; 26] требует модификации ядра ОС или использования специальных библиотек, компонуемых с целевым приложением, что является архитектурным недостатком.

Наконец, существует ряд исследований, решающих задачу восстановления строго для одного типа ресурса, к примеру, для групп процессов одного контейнера (Миркин [1; 8]) или множества сессий (Лаадан [6], Осман [27]), либо обрабатывающие множество различных ресурсов, но имеющие определённые недостатки в моделях анализа и представления ресурсов (Горбунов, Баталов [24]), из которых вытекает снижение надёжности. В виду недостатков вышеперечисленных решений, актуальна задача построения математической модели восстановления дерева процессов, обобщающей эвристические подходы и другие существующие модели, гарантирующая восстановление состояний процессов, владеющих системными ресурсами различных типов. С целью обеспечения широты использования, модель должна учитывать возможность восстановления на немодифицированном ядре, то есть построение на её базе системы восстановления из пространства пользователя, по аналогии с таким решением, как СШИ [3].

В работе предлагается построение модели реконструкции на базе промежуточного представления в виде специального ацикличного графа реконструкции, содержащего минимальным остовным покрытием подмножество рёбер с метками-системными вызовами.

Целью данной работы является построение вышеуказанной математической модели реконструкции дерева процессов, учитывающей некоторый ограниченный класс атрибутов ресурсов различного типа: групп процессов, сессий, идентификаторов процесса, с возможностью обобщения на более широкий класс атрибутов со схожими свойствами. Для деревьев, по-

лученных из реальных системных конфигураций, модель должна гарантировать корректность выдачи последовательностей команд пространства пользователя, приводящих к реконструкции.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Исследовать свойства деревьев процессов, позволяющие производить обобщение эвристических принципов восстановления. [3; 6], оценить возможность непосредственной генерации деревьев.

2. Разработать полиномиальный алгоритм, строящий последовательность команд реконструкции дерева процессов, с учётом идентификаторов процесса, сессии, группы процессов, обеспечивающий восстановление дерева из корневой вершины при воспроизведении данных команд.

3. Провести формальное исследование зависимостей между различными атрибутами процессов, определить частичный порядок по разрешению зависимостей на множестве состояний процессов, исследовать свойства множеств состояний относительно вводимого порядка.

4. Обобщить метод реконструкции на более широкий класс атрибутов процессов, обладающих схожими свойствами с исследованными ранее атрибутами.

5. Связать построенную модель с корректностью восстановления деревьев, соответствующим реальным конфигурациям ОС.

Основные положения, выносимые на защиту:

1. Разработана математическая модель восстановления дерева процессов на базе построения графа реконструкции. Разработан полиномиальный алгоритм восстановления сессий, групп процессов и обратных усыновлений, гарантирующий реконструкцию в смысле разрешения требуемых зависимостей в момент исполнения системного вызова.

2. Предложена обобщённая математическая модель разрешения атрибутных зависимостей между состояниями процессов, в рамках которой возможно восстановление деревьев с любой древес-

ной иерархией атрибутов, восстановление подмножества процессов. Сформулирован формальный критерий корректности деревьев процессов в терминах обобщённой математической модели.

3. Разработан комплекс программ для проведения экспериментов по построению графов реконструкции и сравнению результатов с профилирующими решениями.

4. Проведена серия численных экспериментов с использованием разработанного программного комплекса. Результаты моделирования подтвердили теоретические оценки сложности задачи, а измеренное время работы по реконструкции и получению списков команд в экспериментах сопоставимо с временными издержками на профилирование.

Научная новизна:

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

2. Впервые предложены новые промежуточные представления в задаче восстановления дерева процессов, такие как граф реконструкции и граф реконструкции с зависимостями, проведён структурный анализ данных представлений, сформулирован и формально обоснован механизм восстановления команд реконструкции как ре-бёрного покрытия ациклического графа.

3. Впервые формально определены свойства частичного порядка, задаваемого зависимостями на множествах состояний процессов. Впервые представлен формальный критерий корректности дерева процессов на разрешаемых зависимостях.

4. Впервые получен метод реконструкции дерева процессов, гарантированно обеспечивающий восстановление для атрибутов некоторого типа и структуры за полиномиальное время.

Научная и практическая значимость работы заключается в возможности использования предложенных алгоритмов в системах сохранения-восстановления с целью повышения их надёжности, так как заданных ограничениях на типы атрибутов реконструкция гарантируется. Критерий корректности деревьев процессов может служить основой для разработки методов валидации деревьев процессов и генерации синтетических тестов систем сохранения и восстановления. Разработанный в ходе работы программный комплекс может служить инструментом исследования деревьев процессов и графов реконструкции.

Степень достоверности полученных результатов обеспечивается использованием формальных методов исследования, выполнением формальных доказательств и программными экспериментами. Результаты находятся в соответствии с результатами, полученными другими авторами [1—6; 8; 24; 27].

Апробация работы. Основные результаты работы докладывались на ряде международных и всероссийских конференций: 59-62 Научно-практических конференциях МФТИ, IX Московской международной конференции по исследованию операций, XV-XVII Международных конференциях "Алгебра, теория чисел и дискретная геометрия", международных конференциях "Software Engineering Conference in Russia (CEE-SECR)" 2017-2019. Доклад на конференции CEE-SECR 2017 был награждён премией Бертрана Мейера за лучшую научно-исследовательскую работу в области программной инженерии.

Личный вклад. все основные результаты диссертационной работы получены автором лично.

Публикации. Основные результаты по теме диссертации изложены в 16 публикациях, 4 из которых изданы в журналах, рекомендованных ВАК [28—31], 5 — в изданиях, входящих в Scopus / RSCI Web Of Science [28; 30—33], 9 — в тезисах докладов конференций. Работы [32—37] были выполнены в соавторстве. В работе [32] Н.Ефанову принадлежит идея

атрибутно-управляемой трансформации дерева, алгоритм, анализ вычислительной сложности и постановка эксперимента, в работах [33; 34] - построение метода двухстадийного анализа, оценки вычислительной сложности и постановка эксперимента, в [36] - идеи и обоснование исследуемых метрик эффективности, техническая постановка эксперимента, в [35; 37] -идеи и обоснование использования конкретных алгоритмов.

Благодарности. Автор выражает благодарность Тормасову А.Г. за научное руководство, Емельянову П.В., как ведущему эксперту по теме диссертации, руководству и сотрудникам кафедр информатики, теоретической и прикладной информатики, вычислительной физики МФТИ за создание рабочих условий (рекомендации к публикации, важные замечания, рецензирование статей): Петрову И.Б., Рязанову В.В., представителям программного комитета конференции СЕЕ-БЕСИ, за конструктивные замечания и рецензии работ, опубликованных по результатам конференций, Баталову Е.А. и Горбунову Е.А. за научное взаимодействие, примеры и идеи, Григорьеву С.В. за консультации по формальным языкам и грамматикам.

Объем и структура работы. Диссертация состоит из введения, четырёх глав, заключения и одного приложения. Полный объём диссертации составляет 170 страниц с 20 рисунками и 3 таблицами. Список литературы содержит 98 наименований.

Глава 1. Обзор

1.1 Задача сохранения и восстановления по контрольным

точкам (Checkpoint-Restore)

1.1.1 Терминология

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

Целевой программой или приложением называется процесс или группа процессов, состояние которых сохраняется и восстанавливается. Таким образом подразумевается, что рассматриваются запущенные программы.

Действие над приложением происходит прозрачно, если данное действие не заметно из приложения: к примеру, для сохранения и восстановления приложение не требует модификации, трассировки и иных специфических действий, заметных из приложения, а сами сохранение и восстановление не влияют на работу приложения.

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

Задачей Checkpoint-Restore для процессов называется задача создания и сохранения снимка состояния процессов в ходе работы, с последующим возобновлением их работы из данного снимка. При этом говорят, что состояниям объектов из снимка соответствует контрольная точка (checkpoint), откуда и происходит данное название.

Будем подразумевать, что рассматривается Checkpoint-Restore нескольких процессов, с возможностью консистентного восстановления не только приватных, но и общих ресурсов. В такой постановке подчёркивается [2; 3; 6] необходимость предварительного восстановления дерева процессов для обеспечения порядка реконструкции и наследования ресурсов.

1.1.2 Применение Checkpoint-Restore процессов

Основные сценарии применения Checkpoint-Restore процессов представлены в [6; 16; 18]. Перечислим наиболее очевидные к практическому применению из них.

— Повышение отказоустойчивости программных комплексов: восстановление состояния при сбоях из снимка состояний, созданного предварительно [5; 6; 13; 14; 18].

— Миграция процессов, групп процессов, контейнеров: управление ресурсами и балансировка нагрузки в распределённой вычислительной системе за счёт переноса единиц исполнения с более нагруженных узлов на менее нагруженные [4; 9; 10; 12].

— Отложенная отладка программ: сохранение снимков нужных состояний в персистентное хранилище для дальнейшего восстановления и исследования [16].

— Ускорение загрузки сложных программных комплексов: зачастую, снимок состояния может хранить предзагруженные ресурсы приложения, на инициализацию и загрузку которых и уходит основное время запуска [12; 17].

— Обновление ядра без прерывания работы ОС [16].

— Пауза в компьютерных играх и прочих мультимедиа приложениях: приостановка и возобновление исполнения мультимедийного приложения, возможно, не поддерживающего такие действия.

1.2 Обзор существующих решений Checkpoint-Restore

В последние несколько десятилетий тема Checkpoint-Restore процессов была предметом обширных практических исследований [1; 2; 4—6; 8; 22], что связано, в первую очередь, с ускоряющимся развитием и ростом вычислительных систем, серверных и облачных инфраструктур, виртуа-лизованных окружений, работающих под управлением Unix-подобных ОС. Исследования подчёркивают, в первую очередь, инструментальные возможности и особенности сохранения и возобновления работы сохранённого состояния из контекста различных уровней абстракции программно-аппаратных комплексов, а также подходы к записи и воспроизведению событий, приводящих к целевым состояниям. Выделяются 3 уровня, на которых действия по сохранению и восстановлению процессов могут производиться программно, при этом некоторые решения могут использовать сразу несколько уровней, то есть быть гибридными:

1. Уровень приложений (Userspace). Наиболее гибкий и широко используемый в настоящее время способ сохранения и восстановления в Unix-подобных ОС, не требующий модификации ядра и компоновки с дополнительными сервисными библиотеками [22; 38].

2. Механизмы компоновки с сервисными библиотеками пространства пользователя (Library-Based). При таком способе решения, как правило, производится динамическая компоновка [38] целевой программы со специальной библиотекой, осуществляющей сервисные действия по обработке состояния программы, либо подмены уже используемых библиотек посредством выставления специальных переменных окружения [11]. Менее гибкий, небезопасный и зачастую опирающийся на сложные эвристики способ. В ряде случаев не позволяет производить сохранение и восстановление прозрачно [22], а также понижает производительность итоговых приложений.

3. Уровень ядра (Kernel-based). Позволяет осуществлять прозрачный Checkpoint-Restore, однако требует модификации ядра ОС, что ограничивает широту применимости. Получил распространение на

ранних этапах развития Checkpoint-Restore, а также в специализированных решениях, связанных с высокопроизводительными суперкомпьютерными вычислениями [4; 5; 18; 19] и серверной виртуализацией [1; 7; 8; 25].

В то же время, подходы к записи и воспроизведению событий, приводящих к целевым состояниям процессов, можно разделить на 3 класса1:

1. Логгирующий или профилирующий подход - (Logging, Profiling-based) - на базе записи журнала изменения состояний в ходе работы программы до сохранения и воспроизведения активности по такому журналу при восстановлении [19—21; 39].

2. Эвристический подход - (Heuristics) - на базе эвристик [22].

3. Анализ состояния - (State analysis reconstruction) - восстановление последовательностей операций, реконструирующих состояние, хранящееся в снимке, из некоторого начального состояния. В снимке хранятся только финальные состояния. Способ призван максимально обобщить процесс реконструкции, уменьшить размер контрольных точек, гарантировать успешное восстановление широкого ряда конфигураций исполнения. Является открытой проблемой, которой в данный момент посвящается ряд исследований [1; 6; 8; 22—24].

Пользуясь введёнными выше классификациями, рассмотрим существующие на момент проведения исследования инструменты, поддерживающие Checkpoint-Restore процессов, разработанные для использования в Unix-подобных ОС общего назначения.

1. DMTCP [5] - (Distributed MultiThreaded Checkpointing) - открытый проект, реализующий Checkpoint-Restore многопоточных и многопроцессных приложений. Разрабатывается с 2006 года по настоящее время. Эксперименты по сохранению и восстановлению состояний [39] заключают поддержку большого списка приложений и вычислительных систем: MPI, OpenMP, SLURM, MATLAB, Python,

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

Perl, R, TightVNC и пр. Тем не менее, архитектура DMTCP имеет ряд недостатков, присущих библиотечным решениям: для успешного сохранения снимков состояний целевой процесс должен быть запущен с помощью стартового скрипта, выставляющего переменную окружения LD_PRELOAD для загрузки специальных динамических библиотек DMTCP раньше используемых по умолчанию системных библиотек. Стартовый скрипт запускает дополнительный поток, в котором и создаются снимки состояний, а также создаёт Unix-сокет для связи с процессом-координатором, предварительно запущенным в системе и управляющим Checkpoint-Restore. DMTCP является логгирующим решением: информация о процессе собирается в течение его работы через обёртки над некоторыми функциями (g)libc. При этом времена выполнения системных вызовов не сохраняются, что затрудняет процедуру восстановления. Кроме того, к недостаткам проекта можно отнести:

— Отсутствие поддержки пространств имён

— Отсутствие поддержки восстановления атрибутов процессов с теми же идентификаторами, что и при снятии снимка состояния. Небезопасное поведение по обеспечению прозрачности, в частности, перехват getpid() с выставлением ложного значения идентификатора процесса.

— Как результат оборачивания функций (g)libc, DMTCP не поддерживает логгирование состояний программ, собранных статически и использующих соответствующие вызовы из (g)libc напрямую.

— Процесс-координатор является единой точкой отказа и для сохранения снимка, и для восстановления.

2. BLCR [4] - открытый проект Национальной Лаборатории им. Лоренса университета Беркли, США, активно разрабатываемый до 2013 г. BLCR ориентирован на работу с системами высокопроизводительных вычислений (HPC), использующими MPI [40]. Основная цель проекта - поддержка Checkpoint-Restore при параллельных вычислениях. Является гибридным решением, поставляемым

в виде модуля ядра и динамической библиотеки, компонуемой с целевым приложением, что является факторами, ограничивающими широту использования данной системы. Существенными ограничениями по применимости BLCR также являются:

— Отсутствие поддержки восстановления сетевых соединений и Unix-сокетов.

— Отсутствие поддержки файлов устройств, кроме /dev/null и /dev/zero.

— Отсутствие поддержки средств межпроцессного взаимодействия SYS V IPC.

3. CRIU [3] - (Checkpoint-Restore In Userspace) - открытый проект, ориентированный на поддержку сохранения и восстановления состояний процессов в пространстве пользователя. Представлен в 2011 году группой разработчиков под управлением Павла Емельянова, и продолжает активно разрабатываться. Требует поддержки некоторых специфичных операций на уровне ядра ОС, поддерживаемых в Linux версии 3.11 и более новых ядрах. Реализует сохранение снимков состояний и их восстановление в пространстве пользователя, не требуя при этом компоновки с динамическими библиотеками и их подмены. Сохранение состояния производится чтением информации о процессе из псевдофайловой системы procfs, выполнением системных вызовов и чтением страниц памяти процесса. В результате, CRIU производит анализ корректного, реализовавшегося в ОС, дерева процессов, сохраняет его и набор описаний связанных с ним системных ресурсов в снимок состояния. Восстановление состояния производится реконструкцией дерева процессов и связанных ресурсов через набор нетривиальных эвристических правил, применимых для большого количества различных состояний процессов. В качестве поддерживаемых приложений можно отметить JVM [12] в различных конфигурациях, Linux-контейнеры [9], Docker [10], планируются к поддержке инструменты для высокопроизводительных вычислений [18]. На момент исследования, проект является ведущим проектом Checkpoint-Restore по причине

поддержки восстановления большого числа различный приложений и активного развития, при этом использование не требует модификации ядра ОС. Тем не менее, фиксированный порядок действий и их сложность индуцируют ошибки при восстановлении ряда конфигураций [23; 24; 28] с нетривиальными зависимостями между ресурсами и состояниями процессов. Более того, в особых случаях вопрос возможности и гараний восстановления конфигураций является открытым.

4. OpenVZ [7]- система контейнерной виртуализации, виртуализации на уровне ОС и живой миграции, поддерживающая Checkpoint-Restore, предоставляемый комплектом вспомогательных инструментов уровня ядра. Требования, предоставляемые к ядру - базирование на ядрах RHEL версий 4-6 [41] и необходимость модификации - уменьшают широту потенциального использования данной системы, а также диктуют специальность областей применимости: преимущественно, это системы серверной виртуализации и высокопроизводительных вычислений. Преимуществами является открытость и широкая поддержка в индустриальных решениях

[7].

5. PinLit/PinPlay [21] - инструменты Checkpoint-Restore, построенные на базе проприетарной системы Intel PIN binary instrumentation tool [20]. PinPlay является логическим продолжением PinLIT, который был разработан Кристиано Перейрой [20] в исследовательских целях. Обе утилиты являются профилирующими: они логгируют состояния регистров процессора и события, происходящие во время работы целевого процесса, сохраняют отображения виртуальной памяти, причём поддерживают уменьшение размера снимков состояний благодаря хранению только изменённых страниц памяти. Основным недостатком PinLit [21]/PinPlay является невозможность перезапуска целевого приложения: в виду архитектурных особенностей, отсутствует возможность записи начального состояния приложения и связанного с ним набора системных ресурсов. Тем не менее,

решения применяются для ускорения восстановления состояний приложений после сбоя [15].

6. "Ideal process tracker" [19] - экспериментальная подсистема программного комплекса технической поддержки международной сети распределённых вычислений "Open Science Grid" [42] - логгиру-ющее решение, в котором информация собирается периодическим получением дерева процессов с заданным интервалом. В связи с тем, что таким образом сохраняется состояние только относительно долгоживущих процессов, некоторая информация автоматически фильтруется, что делает снимки состояний более компактными. Тем не менее, информация между двумя снимками состояний может теряться, что является недостатком.

7. CryoPID - утилита для сохранения и восстановления состояния одного процесса, разработанная Бернардом Блекхемом в 2005 году. Решение работает в пространстве пользователя, и при этом не требует дополнительных динамических библиотек. Основным недостатком CryoPID является невозможность консистентного восстановления многопроцессных приложений, что в целом характерно для ранних имплементаций решений задачи [6].

8. CKPT [26] - (Linux ChecKpoint/restarT) - открытый проект, основанный на модификации ядра Linux. Разрабатывался Ореном Ла-аданом из Университета Коламбии в 2008-2010 гг для поддержки Checkpoint-Restore Linux-процессов на уровне ядра ОС. Поддерживает восстановление широкого списка системных ресурсов: идентификаторов, потоков, сигналов, дескрипторов регулярных файлов и SYS V IPC-примитивов, сокетов, практически всех типов пространств имён. Отсутствует поддержка восстановления точек монтирования и их пространств имён, трассируемых ptrace приложений, различных устройств, отображаемых в системе. Требует внесения изменений в ядро, которые не были включены в основные ветки ядра Linux, что ограничивает широту использования системы как в связи с необходимостью внесения изменений, так и в связи с относительным устареванием проекта. Тем не менее,

Список литературы диссертационного исследования кандидат наук Ефанов Николай Николаевич, 2020 год

Список литературы

1. Mirkin A., Kuznetsov A., Kolyshkin K. Containers checkpointing and live migration // Proceedings of the In Ottawa Linux Symposium. — Ottawa, Canada, 2008. — С. 85—90.

2. Laadan O, Hallyn S. E. Linux-CR: Transparent application checkpointrestart in Linux // Linux Symposium. Т. 159. — 2010.

3. CRIU. Checkpoint-Restore in Userspace: Main Page. — 2019. — URL: https://criu.org/.

4. Hargrove P. H, Duell J. C. Berkeley lab checkpoint/restart (BLCR) for Linux clusters // Journal of Physics: Conference Series. — 2006. — Сент. — Т. 46. — С. 494—499. — DOI: 10.1088/1742-6596/46/1/067.

5. Ansel J., Arya K., Cooperman G. DMTCP: Transparent checkpointing for cluster computations and the desktop //. — 2009. — DOI: 10.1109/ IPDPS.2009.5161063. — URL: https://www.scopus.com/inward/record. uri ?eid = 2-s2.0-70449844295 &doi= 10.1109% 2fIPDPS. 2009.5161063 & partnerID=40&md5=4b851c686d18787361a9810bdae726b6.

6. Laadan O, Nieh J. Transparent Checkpoint-Restart of Multiple Processes on Commodity Operating Systems. // USENIX Annual Technical Conference. — 2007. — С. 323—336.

7. Comp. V. OpenVZ: Open source container-based virtualization for Linux. — 2019. — URL: https://openvz.org/.

8. Миркин А. Л, Петров В. А. Система миграции виртуальных серверов в режиме реального времени // Вестник Новосибирского государственного университета. Серия: Информационные технологии. — 2008. — Т. 6, № 3.

9. Migrating LinuX containers using CRIU / S. Pickartz [и др.] // International Conference on High Performance Computing. — Springer. 2016. — С. 674—684.

10. Chen Y. Checkpoint and Restore of Micro-service in Docker Containers // 2015 3rd International Conference on Mechatronics and Industrial Informatics (ICMII 2015). — Atlantis Press. 2015.

11. Load balancing using process migration for linux based distributed system / R. A. Vyas [и др.] // 2014 International Conference on Issues and Challenges in Intelligent Computing Techniques (ICICT). — IEEE. 2014. — С. 248—252.

12. Bruno R., Ferreira P. ALMA: GC-assisted JVM Live Migration for Java Server Applications // Proceedings of the 17th International Middleware Conference. — Trento, Italy : ACM, 2016. — 5:1—5:14. — (Middleware '16). — ISBN 978-1-4503-4300-8. — DOI: 10.1145/2988336.2988341. — URL: http://doi.acm.org/10.1145/2988336.2988341.

13. Xu Y, Yu H., Zheng W. A Consistent Backup Mechanism for Disaster Recovery that Using Container Based Virtualization // 2012 Seventh ChinaGrid Annual Conference. — IEEE. 2012. — С. 95—100.

14. Optimization of Cloud Task Processing with Checkpoint-restart Mechanism / S. Di [и др.] // Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. — Denver, Colorado : ACM, 2013. — 64:1—64:12. — (SC '13). — ISBN 9781-4503-2378-9. — DOI: 10.1145/2503210.2503217.

15. Pereira C. Reproducible user-level simulation of multi-threaded workloads : дис. ... канд. / Pereira Cristiano. — UC San Diego, 2007.

16. CRIU. Checkpoint-Restore in Userspace: Usage Scenarios. — 2019. — URL: https://criu.org/Usage_scenarios.

17. Flood C. H. Checkpoint Restore Fast Start-up For Java Applications. — 2019. — URL: https://www.jfokus.se/jfokus19-preso/Checkpointing-Java.pdf.

18. Vasyukov A., Beklemysheva K. Using CRIU with HPC Containers: Field Experience // International Journal Of Engineering And Computer Science. — 2018. — Июль. — Т. 7. — С. 424106—24108. — DOI: 10.18535/ ijecs/v7i7.01.

19. Pilot job accounting and auditing in Open Science Grid / I. Sfiligoi [и др.] // Proceedings of the 2008 9th IEEE/ACM International Conference on Grid Computing. — IEEE Computer Society. 2008. — С. 112—117.

20. PIN: A Binary Instrumentation Tool for Computer Architecture Research and Education / V. J. Reddi [и др.] // Proceedings of the 2004 Workshop on Computer Architecture Education: Held in Conjunction with the 31st International Symposium on Computer Architecture. — Munich, Germany : ACM, 2004. — (WCAE '04). — ISBN 978-1-4503-4733-4. — DOI: 10.1145/1275571.1275600.

21. PinPlay: A Framework for Deterministic Replay and Reproducible Analysis of Parallel Programs / H. Patil [и др.] // Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization. — Toronto, Ontario, Canada : ACM, 2010. — С. 2—11. — (CGO '10). — ISBN 978-1-60558-635-9. — DOI: 10.1145/1772954.1772958.

22. CRIU. Checkpoint-Restore in Userspace: Comparison to Other CR Projects. — 2019. — URL: https://criu.org/Comparison_to_other_ CR_projects.

23. CRIU. Checkpoint-Restore in Userspace: When C/R fails. — 2019. — URL: https://criu.org/When_C/R_fails.

24. Горбунов Е. Алгоритм генерации команд восстановления дерева процессов ОС Linux на основе модели жизненного цикла ресурсов ОС : дис. ... маг. / Горбунов Егор. — OT6AY РАН, 2017.

25. Cruz: Application-transparent distributed checkpoint-restart on standard operating systems / G. J. Janakiraman [и др.] // 2005 International Conference on Dependable Systems and Networks (DSN'05). — IEEE. 2005. — С. 260—269.

26. Laadan O. Linux Checkpoint/Restart. — 2013. — URL: https://ckpt. wiki.kernel.org/index.php/Main_Page.

27. The design and implementation of Zap: A system for migrating computing environments / S. Osman [и др.] // ACM SIGOPS Operating Systems Review. — 2002. — Т. 36, SI. — С. 361—376.

28. Ефанов Н. Н. Исправление аномалий в графах реконструкции деревьев процессов Linux // Труды МФТИ. — 2019. — Т. 3. — С. 50—60.

29. Ефанов Н. Н. Классификация правил проверки атрибутов в деревьях процессов Linux // Естественные и технические науки. — М., 2018. — № 6. — С. 216—221.

30. Ефанов Н. On some combinatorial properties of LINUX process trees [О некоторых комбинаторных свойствах деревьев процессов LINUX] // Чебышевский сборник. — 2018. — Т. 19, № 2. — С. 151—162. — DOI: 10.22405/2226-8383-2018-19-2-151-162.

31. Ефанов Н. О полурешётке состояний процессов Linux // Чебышевский сборник. — 2019. — Т. 20, № 4. — С. 124—136.

32. Efanov N., Emelyanov P. Linux Process Tree Reconstruction Using The Attributed Grammar-Based Tree Transformation Model // Proceedings of the 14th Central and Eastern European Software Engineering Conference Russia. — Moscow, Russian Federation : ACM, 2018. — 2:1—2:7. — (CEE-SECR '18). — ISBN 978-1-4503-6176-7. — DOI: 10.1145/3290621. 3290626. — URL: http://doi.acm.org/10.1145/3290621.3290626.

33. Efanov N., Emelyanov P. Constructing the Formal Grammar of System Calls // Proceedings of the 13th Central & Eastern European Software Engineering Conference in Russia. — St. Petersburg, Russia : ACM, 2017. — 12:1—12:5. — (CEE-SECR '17). — ISBN 978-1-4503-6396-9. — DOI: 10.1145/3166094.3166106. — URL: http://doi.acm.org/10.1145/ 3166094.3166106.

34. Ефанов Н. Н., Емельянов П. В. Построение формальной грамматики системных вызовов // Информационное обеспечение математических моделей. — М., 2017. — С. 83—90.

35. Efanov N., Shtypa E. Optimization of syscall sequences using minimal spanning trees search // Труды IX Московской международной конференции по исследованию операций (ORM2018-GERMEYER100). — М., 2018. — С. 12—18.

36. Ефанов Н. Н., Щекотихина Д. Д. Измерение времени выполнения системных вызовов для выработки метрик эффективности восстановления состояний исполнения в OS Linux // 61-я Научно-Практическая Конференция МФТИ. ФПМИ. — М. : МФТИ, 2018. — С. 89—90.

37. Ефанов Н., Михайлов В. О генерации команд восстановления дерева процессов Linux // 62-я Научно-Практическая Конференция МФТИ. ФПМИ. — М. : МФТИ, 2019.

38. Franz M. Dynamic linking of software components // Computer. — 1997. — Т. 30, № 3. — С. 74—81.

39. Ansel J., Arya K., Cooperman G. e. a. DMTCP: Distributed MultiThreaded CheckPointing. — 2019. — URL: http : / / dmtcp . sourceforge.net/.

40. The MPI Forum C. MPI: A Message Passing Interface // Proceedings of the 1993 ACM/IEEE Conference on Supercomputing. — Portland, Oregon, USA : ACM, 1993. — С. 878—883. — (Supercomputing '93). — ISBN 0-8186-4340-4. — DOI: 10.1145/ 169627.169855. — URL: http: //doi.acm.org/10.1145/169627.169855.

41. Perkov L, Pavkovic N., Petrovic J. High-availability using open source software // 2011 Proceedings of the 34th International Convention MIPRO. — IEEE. 2011. — С. 167—170.

42. Grid O. S. Open Science Grid. — 2019. — URL: https://opensciencegrid. org/.

43. Завалишин Д. Операционная система "Фантом" // Открытые системы. СУБД. — 2011. — № 3. — С. 20—20.

44. Velte A., Velte T. Microsoft Virtualization with Hyper-V. — 1-е изд. — New York, NY, USA : McGraw-Hill, Inc., 2010. — ISBN 0071614036, 9780071614030.

45. Лекции по теории графов / В. Емеличев [и др.]. — М.: Наука, 1990. — 384 с.

46. Харари Ф. Теория графов. — Издательство "Мир", 1973. — 300 с.

47. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб. : БХВ-Петербург, 2003. — 1104 с.

48. Knuth D. E. The Art of Computer Programming. — 3rd. — Addison Wesley Longman Publishing Co., Inc., 1998. — (Fundamental Algorithms). — (book).

49. Райгородский А. Модели случайных графов. — М. : Litres, 2017. — 141 с.

50. Barabasi A.-L., Albert R. Emergence of scaling in random networks // science. — 1999. — Vol. 286, no. 5439. — P. 509-512.

51. Aho A. V., Garey M. R., Ullman J. D. The transitive reduction of a directed graph // SIAM Journal on Computing. — 1972. — Т. 1, № 2. — С. 131—137.

52. Lowe M. Algebraic approach to single-pushout graph transformation // Theoretical Computer Science. — 1993. — Т. 109, № 1/2. — С. 181—224.

53. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ—2-е изд // М.:«Вильямс. — 2006. — С. 1296.

54. Tarjan R. E. Edge-disjoint spanning trees and depth-first search // Acta Informatica. — 1976. — Т. 6, № 2. — С. 171—185.

55. Pearce D. J., Kelly P. H. A dynamic topological sort algorithm for directed acyclic graphs // Journal of Experimental Algorithmics (JEA). — 2007. — Т. 11. — С. 1—7.

56. Kahn A. B. Topological sorting of large networks // Communications of the ACM. — 1962. — Т. 5, № 11. — С. 558—562.

57. Floyd R. W. Algorithm 97: Shortest Path // Commun. ACM. — New York, NY, USA, 1962. — Июнь. — Т. 5, № 6. — С. 345—. — DOI: 10.1145/ 367766.368168. — URL: http://doi.acm.org/10.1145/367766.368168.

58. Arvind V., Köhler J. Graph isomorphism is low for zpp (np) and other lowness results // Annual Symposium on Theoretical Aspects of Computer Science. — Springer. 2000. — С. 431—442.

59. Биркгоф Г. Теория решёток. — 3-е изд. — М. : Наука, 1984. — С. 148— 174.

60. Ершов Ю. Верхняя полурешетка нумераций конечного множества. // Алгебра и логика. — 1975. — Т. 14, № 3. — С. 258—283.

61. Ершов Ю. Л. Полурешётки Роджерса конечных частично упорядоченных множеств // Алгебра и логика. — 2006. — Т. 45, № 1. — С. 44— 84.

62. Компиляторы: принципы, технологии и инструментарий / А. Ахо [и др.] // М.: Вильямс. — 2008.

63. Kleene S. C. On notation for ordinal numbers // The Journal of Symbolic Logic. — 1938. — Т. 3, № 4. — С. 150—155.

64. Brown R. F. Fixed Point Theory and Its Applications: Proceedings of a Conference Held at the International Congress of Mathematicians, August 4-6, 1986. Т. 72. — American Mathematical Soc., 1988.

65. Sinaceur H. Alfred Tarski: Semantic shift, heuristic shift in metamathematics // Synthese. — 2001. — Т. 126, № 1/2. — С. 49—65.

66. Chomsky N. Formal properties of grammars // Handbook of Math. Psychology. — 1963. — Т. 2. — С. 328—418.

67. Lex & yacc / J. R. Levine [и др.]. — "O'Reilly Media, Inc.", 1992. — 335 с.

68. Levine J. Flex & Bison: Text Processing Tools. — "O'Reilly Media, Inc.", 2009. — 273 с.

69. Knuth D. E. The genesis of attribute grammars // Attribute Grammars and Their Applications. — Springer, 1990. — С. 1—12.

70. Amhati V., Lavie A. Improving syntax driven translation models by re-structuring divergent and non-isomorphic parse tree structures // Proceedings of the Eighth Conference of the Association for Machine Translation in the Americas. — 2008. — С. 235—244.

71. Теория и реализация языков программирования / В. А. Серебряков [и др.]. — М. : МЗ Пресс, 2006. — 347 с.

72. Schmauch C. H. ISO 9000 for Software Developers. — 2nd. — ASQ Quality Press, 1995. — ISBN 0873893484.

73. The Single UNIX Specification, Version 2. — 1997. — URL: https://pubs. opengroup.org/onlinepubs/7990989775/.

74. He J. LINUX System Call Quick Reference // Dec. — 2008. — Т. 3. — С. 1—3.

75. Conway M. E. A Multiprocessor System Design // Proceedings of the November 12-14, 1963, Fall Joint Computer Conference. — Las Vegas, Nevada : ACM, 1963. — С. 139—146. — (AFIPS '63 (Fall)). — DOI: 10. 1145/1463822.1463838.

76. Ritchie D. M. The UNIX System: The Evolution of the UNIX Timesharing System // AT&T Bell Laboratories Technical Journal. — 1984. — Т. 63, № 8. — С. 1577—1593.

77. Abrossimov E., Rozier M., Shapiro M. Generic virtual memory management for operating system kernels // ACM SIGOPS Operating Systems Review. Т. 23. — ACM. 1989. — С. 123—136.

78. Kerrisk M. The Linux programming interface: a Linux and UNIX system programming handbook. — San Francisco : No Starch Press, 2010. — 1552 с.

79. Лав Р. Linux. Системное программирование. — 2-е изд. — СПб. : Питер, 2014. — 448 с.

80. Таненбаум Э. Современные операционные системы. — 4-е изд. — Питер, 2010. — 1120 с. — (Классика computer science : CS). — ISBN 9785498073064.

81. Herber. R. J. UNIX System V (Concepts). Zombies(5). — 1997. — URL: https://www-cdf.fnal.gov/offline/UNIX_Concepts/concepts.zombies.txt.

82. Linux. Linux Programmer's Manual. PRCTL(2). — 2019. — URL: http: //man7.org/linux/man-pages/man2/prctl.2.html.

83. Карпов В., Коньков К. Основы операционных систем / под ред. В. Иванникова. — М. : ИНТУИТ.РУ, 2013. — 496 с.

84. Лав Р. Ядро Linux: описание процесса разработки. — 3-е изд. — М. : И.Д. Вильямс, 2005. — 536 с.

85. Kerrisk M. POSIX Programmer's Manual: JOBS(1P). — 2019. — URL: http://man7.org/linux/man-pages/man1/jobs.1p.html.

86. Lewis R. P. The number of spanning trees of a complete multipartite graph // Discrete mathematics. — 1999. — Т. 197. — С. 537—541.

87. Knuth D. E. Backus Normal Form vs. Backus Naur Form // Commun. ACM. — 1964. — Дек. — Т. 7, № 12. — С. 735—736.

88. Хопкрофт Д. Э., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. — 2-е изд, перераб. и доп. — М. : Вильямс, 2008. — 528 с.

89. Horn A. On Sentences Which are True of Direct Unions of Algebras //J. Symbolic Logic. — 1951. — Март. — Т. 16, № 1. — С. 14—21.

90. Dowling W. F., Gallier J. H. Linear-time algorithms for testing the satisfiability of propositional Horn formulae // The Journal of Logic Programming. — 1984. — Т. 1, № 3. — С. 267—284.

91. Appel A. W. SSA is functional programming // SIGPLAN Not. — 1998. — Т. 33, № 4. — С. 17—20.

92. Zengin M, Vafeiadis V. A programming language approach to fault tolerance for fork-join parallelism // 2013 International Symposium on Theoretical Aspects of Software Engineering. — IEEE. 2013. — С. 105— 112.

93. (Silence) P. B. Checkpoint and Restore of File Locks in Userspace // Proceedings of the 13th Central & Eastern European Software Engineering Conference in Russia. — St. Petersburg, Russia : ACM, 2017. — 13:1— 13:4. — (CEE-SECR '17). — DOI: 10.1145/3166094.3166107.

94. Ellson J., Gansner E. Graphviz - Graph Visualization Software. — 2019. — URL: https://www.graphviz.org/.

95. PyPlot tutorial. — 2018. — URL: https://matpl0tlib.0rg/3.l.l/tut0rials/ introductory/pyplot.html.

96. Gregg B. Strace: Wow Much Syscall. — 2014. — URL: http://www. brendangregg.com/blog/2014-05- 11/strace-wow- much-syscall.html.

97. Gregg B. Perf Examples. — 2019. — URL: http://www.brendangregg. com/perf.html.

98. Nievergelt J., Reingold E. M. Binary search trees of bounded balance // SIAM journal on Computing. — 1973. — T. 2, № 1. — C. 33—43.

Список рисунков

1.1 Переупорядочивание процессов-потомков к гш£-процессу при завершении родителя. При реконструкции некоторых процессов требуется восстановление завершённых родителей. 33

2.1 Пример дерева процессов Т с атрибутами

аИг = {pid,pgid,sid,ppid} (а), визуализация эволюции Т из корневой вершины (б) и список вызовов, произведённых при построении в контексте соответствующих процессов (в). . . 40

2.2 к доказательству утверждения 2.3. Вершины с метками -

процессы, совершившие вызов к_са11(0), остальные

вершины либо наследуют, либо изменяют значение атрибута

на некоторое значение из дерева, что показано стрелками. . 45

2.3 Переход от дерева разбора к абстрактному синтаксическому дереву................................ 48

2.4 Пополнение вершин дерева разбора атрибутами........ 48

2.5 К доказательству свойства сохранения единственного наследуемого значения: при нарушении единственности

цепи распадаются в деревья................... 51

2.6 Схемы обратного переупорядочивания потомков завершённых процессов...................... 52

2.7 Моделирование роста дерева процессов набором конечных автоматов.............................. 65

2.8 Примеры применения трансформаций к подграфам графа С(Т) на основной стадии построения (б-и), и при пред-

(к-л) и пост-обработке (м).................... 80

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

3.1 Входное дерево процессов Т, граф реконструкции С(Т) и

граф реконструкции с зависимостями С3ер(Т)......... 106

3.2 Иерархии атрибутов процессов для идентификаторов процессов, сессий, групп процессов в едином пространстве

имён................................. 106

3.3 Общая схема реконструкции состояния и с атрибутом "аИг" по генерирующему множеству Сеп(и.аЫг) (а), фактическая схема из алгоритма Главы 2 до стадии пост-обработки (б) и вариант исправления в пост-обработке из Главы 2 (в)..... 112

3.4 Выделенные типы атрибутов ресурсов: жестко наследуемые (а), устанавливаемые в подобласти (б), мягко-наследуемые

(в), свободно выставляемые (г).................113

3.5 К исследованию примера из подраздела 2.6.3: граф зависимостей на множестве V +, дополненный иерархическими рёбрами Н из входного дерева процессов (а), диаграмма Хассе частично упорядоченного множества

(б)................................ 119

3.6 Изменение конфликтного подмножества (а) на этапе пост-обработки - добавление носителя (б) и диаграмма Хассе исправленного подмножества (в). Подмножество с избыточно созданными носителями (г) можно переупорядочить (д) и вложить в полурешётку, не нарушая

её свойств.............................. 122

4.1 Схема программного комплекса................. 141

4.2 Результаты эксперимента..................... 148

4.3 Результаты эксперимента по генерации графов и профилированию э^асе в логарифмической шкале по оси ординат............................... 149

А.1 Стадии работы анализатора дерева в строчной префиксной

нотации............................... 169

Список таблиц

2.1 Атрибутная грамматика деревьев процессов ......... 49

4.1 Время реконструкции в миллисекундах на тесте "simple load" 150

4.2 Время реконструкции в миллисекундах на тесте "context load" 151

Приложение А

Элементы синтаксического анализа дерева процессов в

строчной нотации

В качестве альтернативы атрибутному анализу дерева как графа, проводилось исследование вопроса о правомерности решения задачи на основании непосредственного анализа записи дерева процессов как строки, порождаемой в некоторой формальной грамматике. Для этого предложено описывать шаблоны сопоставления строк в специальной нотации, из которых в дальнейшем формируются левые и правые части правил конструируемой грамматики. Отдельныи процесс в даннои нотации записывается как "р § б [*]", где р, б - идентификаторы процесса, группы и сессии, а символы " ["."]" - терминальные символы начала и конца списка потомков данного процесса. Таким образом поддерживается префиксная структура дерева на входнои строке, что позволяет восстановить иерархию за один проход по ней. В отличие от синтаксического анализа подраздела 2.2.1, атрибуты процесса, включаемые в единый терминал р^, теперь могут рассматриваться как отдельные грамматические единицы. Для исследования эффекта от такого рассмотрения был набор правил сопоставления подстрок в префиксной строке дерева. Если шаблон правила удовлетворяет подстроке, то правая часть правила порождена соответствующим системным вызовом:

1. 1Ьгк(): ^гк(***[*]) ^ * * * [* \2 \3 []\4].

2. Бе1в1а(): * * [*]) ^ \1 \1 \1 [\4].

3. {р р * [*],setpgid(p,* * \3 [*])} ^ {р р * [*], \1 \1 \3 [\4] | р р \3 [\4]}, где нетерминальные символы {,}

интерпретируются как «в системе существует или существовала такая конфигурация».

4. ехй(): {1 * * [*],ехгЬ(* * * [*])} ^ 1 \1 \2 [ \3 \7 ]

Заметим, что правило 3 затруднительно выразить в терминах обыкновенных грамматик: «в системе существует или существовала такая кон-

фигурация» буквально означает, что и левой, и правой частям правила соответствует разрывная конструкция. Но даже перейдя к частному случаю1, когда конструкция неразрывна, то есть если А = p p * [*], В = setpgid(p,* * \3 [*]), С = \1 \1 \3 [\4], D=p p \3 [\4]} ^ АВ ::= АС\И, правило даёт грамматику типа 1 по Хомскому [66], так как присутствует левый контекст: правило применяется тогда и только тогда, когда и в левой, и в правой частях слева от соответствующего терма стоит А. Если оставить лишь вторую подстроку, такой шаблон будет соответствовать случаю создания процессом только собственной группы, что ещё больше нарушает требование по покрытию всех случаев требуемых системных вызовов. Тем не менее, такое упрощение соответствует КС-случаю, так как контекст исчезает из правила.

Кроме того, подобная формализация правила 4, соответствующего вызову ехй(), приводит к грамматике типа 0, так как в правой части правила происходит укорачивание. Такие случаи предлагается обрабатывать 2

эвристиками .

Разработан двухэтапный метод анализа. Анализатор осуществляет на первом этапе восходящии разбор входной префиксной строки по бесконтекстным частям правил системных вызовов следующим образом: вводится стековая память с механизмом стекового кадра для каждого из процессов. Каждыи процесс сохраняется на стеке в виде пары строк:

1. состояние ^ системный вызов ^ ... ^ состояние

2. метаданные, ссылки на родителя и процессы-потомки.

Ссылки на конкретное состояние родителя будут созданы в дальнейшем и хранятся в специальном словаре. При встрече символа [ создаётся новый кадр стека, и по мере считывания символов происходит заполнение кадра (аналог операции "сдвиг"), а при встрече ] происходит его размотка (аналог операции "свёртка"), с восстановлением системных вызовов по бесконтекстным частям правил. По окончании свёрток (что эквивалентно тому, что баланс скобок [,] совпал), на соответствующем кадре хранится результат разбора подстроки соответствующего процесса и его потомков.

хЧто неминуемо нарушает требование об обеспечении реконструкции для любых возможных конфигураций атрибутов.

2 Что также не даёт гарантий реконструкции любого дерева

По окончании в стеке хранится дерево с частично восстановленными системными вызовами и добавленными по левым частям их правил промежуточными состояниями.

На втором этапе происходит эвристический анализ атрибутов, в котором восстанавливаются остальные части правил. Для обработки ех^() используются следующие эвристики:

1. сессии потомка не существует ниже по стеку. Тогда создается потомок т^ с идентификатором, равным идентификатору даннои сессии, и производится setsid(). Данныи процесс помечается как вышедшии и кладется на стек с соответствующеи пометкой. Исследуемый потомок присоединяется к созданному процессу.

2. сессия существует, но в неи нет вышедших процессов. Вышед-шии процесс присоединяется к лидеру сессии, после чего к нему присоединяется исследуемыи через последовательность setpgid(), setpgid(). Восстановленныи процесс помечается как вышедшии и кладется на стек аналогично эвристике 1;

3. сессия существует, в неи есть вышедшие процессы. Находится под-ходящии вышедшии процесс, после чего к нему присоединяется исследуемыи через последовательность setpgid(), setpgid(). В случае, если подходящих процессов не наидено, реализуется эвристика 2.

Рисунок А.1 — Стадии работы анализатора дерева в строчной

префиксной нотации.

Алгоритмическая сложность анализатора может быть оценена в предположении, что для поиска сеансов, групп и процессов используются структуры данных на основе ЛУЬ-деревьев [98]. В связи с этим любой поиск определенных данных имеет сложность логарифмическую сложность, а каждый проход и по строке, и по стеку, и по состояниям одного процесса считаем линейным. Тогда справедлива оценка 0(\У+\)1од(\У\)1од(\С\)1од(\Б\), где \У+\ - общее число состояний процессов, \Р\,\С|,\^\ - число входных процессов, групп процессов, сессий соответственно. Добавление нового атрибута, обрабатываемого аналогично сессиям и группам, увеличивает асимптотику в 0(log(\Z\))-раз, где \Z\ - число различных значений атрибута.

С некоторыми экспериментальными результатами исследования анализатора, сравнениями с профилирующими решениями на 2 синтетических тестах, являющихся аналогами тестов, используемых в главе 4, несколько упрощённых, дабы гарантировать восстановление на предложенном анализаторе, и с аналогичной метрикой временных затрат, можно ознакомиться в работе [33], опубликованной автором ранее. Результаты продемонстрировали время работы порядка времени работы профилировщиков, и до значительного числа процессов (3000-4000, в зависимости от теста), эксперименты показали лучший результат, чем трассировка в^асе. Тем не менее, гарантий реконструкции любого дерева процессов такой анализатор не даёт.

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