Summary: The paper discusses a set of states of Linux processes as data structure, which is used in the task of process-tree reconstruction in Unix-like operating systems. The purpose of the study is 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. Following from the technical properties of the applied problem attributes’ hierarchy allow to introduce additional restrictions on the minimum upper bounds in such semilattice.
Constraints are formally described as suitable pre-closure and closure operators. The constraints implies the necessary condition for the correctness of the process tree. Based on the 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 for process-tree correctness, which can be useful in such tasks as generating tests for checkpoint-restore in Unix-like operating systems, anomalies detection, increasing portability and reliability of software. Dependency schemes between attributes that impose particular constraints on the reconstructing set are also shown. Opened questions are also highlighted and further steps are suggested.