О полурешётке состояний процессов Linux

Аннотация

В работе рассматривается структура данных - множество состояний процессов Linux,
которая используется в задаче восстановления дерева процессов в Unix-подобных операционных системах. Целью исследования является анализ зависимостей в такой структуре,
введение естественного порядка по зависимостям, предложение и обоснование возможности его введения как верхней полной полурешётки. Следующие из технических свойств
прикладной задачи иерархии атрибутов позводяют ввести дополнительные ограничения
на минимальные верхние границы в полурешётке. Ограничения формально описываются в
виде подходящих операторов предзамыкания и замыкания. Из ограничений следует необходимое условие корректности дерева процессов. На основании свойств точек, возвращае-
мых введёнными операторами и схемы выполнения системного вызова, приводится достаточное условие корректности: для каждого атрибута, возникающего в контексте процесса,
должно существовать решёточно упорядоченное относительно наследуемого порядка множество, содержащее промежуточные состояния процессов, через которые и разрешаются
зависимости. Введённые условия формируют критерий корректности дерева процессов,
что может быть полезно в таких задачах как генерация тестов для систем сохранения и
восстановления состояний Unix-подобных ОС, поиск аномалий, повышение портабельности и надёжности программных комплексов. Приводятся также схемы зависимостей между атрибутами, которые вводят частные ограничения на реконструирующее множество.
Рассматриваются открытые вопросы и предлагаются дальнейшие шаги.