аспирант, ассистент/преподаватель кафедры информатики и вычислительной математики
PhD Student Teaching assistant, Department of Informatics
В работе рассматривается структура данных - множество состояний процессов Linux,которая используется в задаче восстановления дерева процессов в Unix-подобных операционных системах. Целью исследования является анализ зависимостей в такой структуре,введение естественного порядка по зависимостям, предложение и обоснование возможности его введения как верхней полной полурешётки. Следующие из технических свойствприкладной задачи иерархии атрибутов позводяют ввести дополнительные ограниченияна минимальные верхние границы в полурешётке. Ограничения формально описываются ввиде подходящих операторов предзамыкания и замыкания. Из ограничений следует необходимое условие корректности дерева процессов. На основании свойств точек, возвращае-мых введёнными операторами и схемы выполнения системного вызова, приводится достаточное условие корректности: для каждого атрибута, возникающего в контексте процесса,должно существовать решёточно упорядоченное относительно наследуемого порядка множество, содержащее промежуточные состояния процессов, через которые и разрешаютсязависимости. Введённые условия формируют критерий корректности дерева процессов,что может быть полезно в таких задачах как генерация тестов для систем сохранения ивосстановления состояний Unix-подобных ОС, поиск аномалий, повышение портабельности и надёжности программных комплексов. Приводятся также схемы зависимостей между атрибутами, которые вводят частные ограничения на реконструирующее множество.Рассматриваются открытые вопросы и предлагаются дальнейшие шаги.
The paper discusses a set of states of Linux processes as data structure, which is used in thetask of process-tree reconstruction in Unix-like operating systems. The purpose of the studyis to analyze dependencies in such structure, to introduce the natural order of dependencies,to propose the class of such reconstruction structure as upper complete semilattice. Followingfrom the technical properties of the applied problem attributes’ hierarchy allow to introduceadditional restrictions on the minimum upper bounds in such semilattice.Constraints are formally described as suitable pre-closure and closure operators. Theconstraints implies the necessary condition for the correctness of the process tree. Based onthe properties of points returned by the proposed operators and system call execution scheme,a sufficient condition for correctness is given. The introduced conditions form the criterion forprocess-tree correctness, which can be useful in such tasks as generating tests for checkpointrestore in Unix-like operating systems, anomalies detection, increasing portability and reliabilityof software. Dependency schemes between attributes that impose particular constraints on thereconstructing set are also shown. Opened questions are also highlighted and further steps aresuggested.
The authors declare that there are no conflicts of interest present.