Geodesic
On semilattice of Linux processes' states
Čebyševskij sbornik, Tome 20 (2019) no. 4, pp. 124-136.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: mathematical modeling, applied algebra, semi-groups, trees, Unix-like operating systems, system calls, process tree, checkpoint restore, closures. 
@article{CHEB_2019_20_4_a8,
     author = {N. N. Efanov},
     title = {On semilattice of {Linux} processes' states},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {124--136},
     publisher = {mathdoc},
     volume = {20},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2019_20_4_a8/}
}
TY  - JOUR
AU  - N. N. Efanov
TI  - On semilattice of Linux processes' states
JO  - Čebyševskij sbornik
PY  - 2019
SP  - 124
EP  - 136
VL  - 20
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2019_20_4_a8/
LA  - ru
ID  - CHEB_2019_20_4_a8
ER  - 
%0 Journal Article
%A N. N. Efanov
%T On semilattice of Linux processes' states
%J Čebyševskij sbornik
%D 2019
%P 124-136
%V 20
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2019_20_4_a8/
%G ru
%F CHEB_2019_20_4_a8
N. N. Efanov. On semilattice of Linux processes' states. Čebyševskij sbornik, Tome 20 (2019) no. 4, pp. 124-136. http://geodesic.mathdoc.fr/item/CHEB_2019_20_4_a8/

[1] Efanov N., “On some combinatorial properties of LINUX process trees”, Chebyshevskii Sbornik, 19:2 (2018), 151–162 | MR | Zbl

[2] Checkpoint-Restore In Userspace (CRIU) usage scenarios, , 2019 (Data obrascheniya: 24.05.2019) https://criu.org/Usage_scenarios

[3] Kraemer S., Leupers R., Petras D., Philipp T., Hoffmann A., “Checkpointing SystemC-based virtual platforms”, International Journal of Embedded and Real-Time Communication Systems, 2:4 (2011), 21–37 | DOI

[4] Efanov N. N., Emelyanov P. V., “Constructing the formal grammar of system calls”, Proceedings of the 13th Central Eastern European Software Engineering Conference in Russia, CEE-SECR'17, 2017, 12, 5 pp. | DOI

[5] Efanov N. N., Emelyanov P. V., “Linux Process Tree Reconstruction Using The Attributed Grammar-Based Tree Transformation Model”, Proceedings of the 14th Central Eastern European Software Engineering Conference in Russia, CEE-SECR'18, ACM, NY, USA, 2018, 2, 7 pp. | DOI

[6] Gorbunov E., Algoritm generatsii komand vosstanovleniya dereva processov OS Linux na osnove modeli zhiznennogo tsykla resursov, Master's thesis, MIT SPbAU, 2017

[7] Linux namespaces, (Data obrascheniya: 24.05.2019) https://en.wikipedia.org/wiki/Linux_namespaces

[8] Alfred V. Aho, Jeffrey D. Ullman, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972 (Data obrascheniya: 24.05.2019) http://dl.acm.org/citation.cfm?id=578789

[9] Sukadev Bhattiprolu, Eric W. Biederman, Serge Hallyn, Daniel Lezcano, “Virtual servers and checkpoint/restart in mainstream Linux”, SIGOPS Oper. Syst. Rev., 42:5, July (2008), 104–113 | DOI

[10] Kalaee A., Rafe V., “Model-based test suite generation for graph transformation system using model simulation and search-based techniques”, Information and Software Technology, 108 (2019), 1–29 | DOI

[11] A.V. Arkhangelskii, L.S. Pontryagin, General Topology, v. 1, Springer-Verlag, Berlin, 1990 | MR

[12] Birkhoff G., Lattice Theory, 3rd ed., American Mathematical Society, Providence, RI, 1973 | MR

[13] Aho A. V., Garey M. R., Ullman J. D., “The transitive reduction of a directed graph”, SIAM Journal on Computing, 1:2 (1972), 131–137 | DOI | MR | Zbl

[14] Freese R., “Automated lattice drawing”, International Conference on Formal Concept Analysis, Springer, Berlin–Heidelberg, 2004, 112–127 | Zbl

[15] Tanenbaum A. S., Bos H., Modern Operating Systems, 4th edition, 2014

[16] Linux system calls. MANual pages(2), , 2019 (Data obrascheniya: 24.05.2019) http://man7.org/linux/man-pages/man2/syscalls.2.html

[17] Hargrove P. H., Duell J. C., “Berkeley lab checkpoint/restart (BLCR) for linux clusters”, Journal of Physics: Conference Series, 46:1 (2006), 494 | DOI

[18] Arya K., Cooperman G., “DMTCP: Bringing Checkpoint-Restart to Python”, Proceedings of the 12th Python in Science Conference, 2013, 2–7 | DOI

[19] Zengin M., Vafeiadis V., “A programming language approach to fault tolerance for fork-join parallelism”, Proceedings of the 7th International Symposium on Theoretical Aspects of Software Engineering, TASE 2013, Max Planck Institute for Software Systems (MPI-SWS), Saarsbruchen, Germany, 2013 http://plv.mpi-sws.org/ftpar/tase2013-ftpar.pdf

[20] M. Kudinova, P. Emelyanov, “Building Mathematical Model for Restoring Processes Tree during Container Live Migration”, IVth International Conference on Engineering and Telecommunication (EnT) (November 2017, Dolgoprudniy), 2017 | DOI