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

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