О некоторых комбинаторных свойствах деревьев процессов LINUX

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