On semilattice of Linux processes’ states

Abstract

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 checkpointrestore 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.