chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2018-19-2-cheb-402Research ArticleСтатьиArticleО некоторых комбинаторных свойствах деревьев процессов LINUXOn some combinatorial properties of LINUX process treesЕфановНиколай НиколаевичEfanovNikolai Nikolayevich

Аспирант кафедры информатики и вычислительной ма-тематики МФТИ, преподаватель, программист ЛЦССН МФТИ.

graduate student of the department of informatics and computational mathematics, teacher, programmer

nefanov90@gmail.comМФТИ(ГУ)РоссияMIPT, LLSSN MIPTRussian Federation201817082018192Том 19, № 2, 2018151162Copyright © Ефанов Н.Н., 20192019Ефанов Н.Н.Efanov N.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/402

В работе рассматривается структура данных - дерево процессов Linux, возникающая вследствие иерархической схемы порождения процессов в Unix-подобных операционных системах. Целью исследования является выделение свойств деревьев процессов Linux, позволяющие заключить о применимых методах анализа таких деревьев, с целью решения задачи сохранения и восстановления состояний исполняемых сред операционной системы Unix-подобных операционных систем. Формулируется обратная дискретная задача восстановления цепочек системных вызовов, порождающих некоторое дерево процессов, а такжеряд ограничений на вид системного вызова и утверждение о существовании решения, заключающее корректность ввода. Приводятся комбинаторные оценки общего количества деревьев при порождении системным вызовом fork, вводится поправка на различимость идентификаторов. Осуществляется обоснование возможности индексирования деревьев по узлам, благодаря образованию некорневыми идентификаторами симметрической группы.Таким образом, доказывается функциональная эквивалентность автоморфных деревьевс перестановками некорневых идентификаторов. Демонстрируется комбинаторный взрыв числа функционально различных деревьев при добавлении нового системного вызова. Ввиду приведённых оценок, проводится заключение о неэффективности восстановления деревьев процессов перебором или прямым поиском, предлагается идея построения некоторых восстанавливающих математических формализмов, учитывающих структуру задачи.Далее рассматривается свойство наследования атрибутов в дереве процессов, позволяющее локализовать область поиска нужного атрибута при проверке применимости правила системного вызова, таким образом снизив количество проверок. Заключается свойство сегментации дерева процессов Linux. На базе приведённых свойств формулируется заключение о целесообразности построения решения задачи восстановления цепочек системных вызовов, восстанавливающих дерево процессов, на базе теории формальных языков и грамматик, используя формализмы класса мягко-контекстно-зависимых. Приводятся обзорно альтернативные способы решения задачи.

Ключевые слова: математическое моделирование, перечислительная комбинаторика, группы, деревья, Unix-подобные операционные системы, системные вызовы, дерево процессов, восстановление по контрольным точкам, формальные грамматики.

The paper examines the Linux process tree data structure, which arises from the hierarchical scheme of processes generation in Unix-like operating systems. The purpose of study is to highlight the properties of the Linux process trees, which allow to conclude the applicable methods for analyzing such trees, in aim to solve the checkpoint-restore problem of executable environments in Unix-like operating systems.

The inverse discrete problem of restoring chains of system calls that generate a certain tree of processes is formulated, as well as a number of restrictions on the form of the system call and an assertion about the existence of a solution that concludes the correctness of the input.

Combinatorial estimation of total trees number, which are provided by fork system call, is presented, and correction is noted for the discernibility of identifiers. The feasibility of indexing by nodes is substantiated, due to the formation of non-root identifiers of the symmetric group. Thus, the functional equivalence of automorphic trees with permutations of non-root identifiers is proved. A combinatorial explosion of the functionally different trees number is shown by the procedure of adding a new system call. In view of the above estimations, a conclusion about the ineffectiveness of process trees restoring by bruteforce or direct search is drawn. The idea of constructing restoring mathematical formalisms that take into account the structure of the problem is proposed.

Next, the inheritance property of attributes in the process trees is examined, which allows to localize a required attribute when checking the applicability of a system call rule, thus reducing the number of checks. The segmentation property of the Linux process trees is provided. On the basis of the above properties, the conclusion is formulated on the goal of constructing a solution of restoring the syscall chains, which constructing a certain process tree, on the basis of the theory of formal languages and grammars, using formalisms of the class of mildly-context-sensitive. The alternative methods of solution are reviewed too.

математическое моделированиеперечислительная комбинаторикагруппыдеревьяUnix-подобные операционные системысистемные вызовыдерево процессоввосстановление по контрольным точкамформальные грамматикиmathematical modelingenumeration combinatoricsgroupstreesUnix-like operating systemssystem callsprocess treecheckpoint restoreformal grammars.МФТИ(ГУ)ReferencesMirkin A., Kuznetsov A., Kolyshkin K. Containers checkpointing and live migration // Proceedings of the In Ottawa Linux Symposium, vol. 2, pp. 85-90 (2008).Mirkin A., Kuznetsov A., Kolyshkin K, 2008, “Containers checkpointing and live migration”, Proceedings of the In Ottawa Linux Symposium. Ottawa, Ontario, Canada, vol.2, pp. 85-90.Ефанов Н.Н., Емельянов П. В. Построение формальной грамматики системных вызовов // М. Информационное обеспечение математических моделей, 2017, 83-91 cc.Efanov N.N., Emelyanov P.V. 2017, “Postroenie formal’noj grammatiki sistemnyh vyzovov” , Informacionnoe obespechenie matematicheskih modelej, Moscow, Russia, pp. 83-91.Efanov N. N., Emelyanov P. V. Constructing the formal grammar of system calls // In Proceedings of the 13th Central & Eastern European Software Engineering Conference in Russia (CEE-SECR '17). ACM, New York, NY, USA, 2017, Article 12, 5 pages. doi: 10.1145/3166094.3166106Efanov N. N., Emelyanov P. V. “Constructing the formal grammar of system calls”, In Proceedings of the 13th Central \& Eastern European Software Engineering Conference in Russia (CEE-SECR '17), ACM, New York, NY, USA, Article 12, 5 pages. doi: 10.1145/ 3166094.3166106Bozyigit M., Wasiq M. User-level process checkpoint and restore for migration // ACM SIGOPS Operating Systems Review, 2017, vol. 35 no. 2, pp. 86-96. doi: 10.1145/377069.377091Bozyigit M., Wasiq M., 2001, “User-level process checkpoint and restore for migration”, ACM SIGOPS Operating Systems Review, vol. 35, no. 2, p.86-96. doi: 10.1145/377069.377091Cayley A. A theorem on trees. // Collected Mathematical Papers, 1897, vol. 13. pp. 26-28.Cayley A. 1897, “A theorem on trees”, Collected Mathematical Papers, Cambridge University Press, vol. 13, pp. 26-28.Clemente Izurieta, James Bieman. The evolution of FreeBSD and linux. // In Proceedings of the 2006 ACM/IEEE international symposium on Empirical software engineering (ISESE '06). ACM, New York, NY, USA, 2006, pp. 204-211. doi: 10.1145/1159733.1159765Clemente Izurieta and James Bieman. 2006, “The evolution of FreeBSD and linux”, In Pro\-cee\-dings of the 2006 ACM/IEEE international symposium on Empirical software engi\-nee\-ring (ISESE '06), ACM, New York, NY, USA, 204-211. doi: 10.1145/1159733.1159765Leonardo Passos, Jianmei Guo, Leopoldo Teixeira, Krzysztof Czarnecki, Andrzej Wąsowski, and Paulo Borba. Coevolution of variability models and related artifacts: a case study from the Linux kernel // In Proceedings of the 17th International Software Product Line Conference (SPLC '13). ACM, New York, NY, USA, 2013, pp. 91-100. doi: 10.1145/2491627.2491628Leonardo Passos, Jianmei Guo, Leopoldo Teixeira, Krzysztof Czarnecki, Andrzej Wąsowski, and Paulo Borba 2013, “Coevolution of variability models and related artifacts: a case study from the Linux kernel”, In Proceedings of the 17th International Software Product Line Conference (SPLC '13), ACM, New York, NY, USA, 91-100. doi: 10.1145/2491627.2491628Белоусов А. И. Дискретная математика, 4-е изд., М.: МГТУ имени Н. Э. Баумана, 2006, 744 с.Belousov, A.I. 2006, Discretnaya matematika, 4th edition, Bauman University (BMSTU), Moscow, p. 349.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill , 2001. ISBN 0-262-03293-7.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Knuth, Donald E., The Art of Computer Programming Vol 1. 3rd edition, Boston: Addison-Wesley, 1997. ISBN 0-201-89683-4Knuth, Donald E. 1997, The Art of Computer Programming, Vol 1., 3rd edition, Boston: Addison-Wesley, ISBN 0-201-89683-4Krippendorff, Klaus. "Combinatorial Explosion" // Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Retrieved 29 November 2010. URL: url{http://pespmc1.vub.ac.be/ASC/Combin_explo.html} (Дата обращения: 31.05.2018).Krippendorff, Klaus, 2010, "Combinatorial Explosion", Web Dictionary of Cybernetics and Systems, PRINCIPIA CYBERNETICA WEB, Retrieved 29 November 2010. Available at: \url{http://pespmc1.vub.ac.be/ASC/Combin_explo.html}Alfred V. Aho , Jeffrey D. Ullman , The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. URL: url{dl.acm.org/citation.cfm?id=578789} (Дата обращения: 31.05.2018).Alfred V. Aho , Jeffrey D. Ullman 1972, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA. Available at: \url{dl.acm.org/citation.cfm?id=578789}Охотин А. Формальные грамматики и вычислительная сложность синтаксического анализа. СПбГУ, программа “Математика”, 12 ноября 2017 г. noindent URL: url{https://compsciclub.ru/media/slides/for-mal_grammars_2017_autumn/2017_11_12_formal_grammars_2017_autumn.pdf} (Дата обращения: 31.05.2018).Okhotin A, 2017, “Formal’nye grammatiki i vychislitelnaya slojnost’ sintaksicheskogo analiza”, “Matematika” educational program, SPbSU. Available at: \url{https://compsciclub.ru/media/slides/formal_grammars_2017_autumn/2017_11_12_formal_grammars_2017_autumn.pdf}David J. Weir. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1988. doi:10.1145/3166094.3166106David J. Weir. 1988, Characterizing Mildly Context-Sensitive Grammar Formalisms, Ph.D. thesis, University of Pennsylvania, Philadelphia, USA. doi: 10.1145/3166094.3166106M. A. Alonso and V. J. D'iaz. Variants of mixed parsing of TAG and TIG // Traitement Automatique des Langues (TAL), 2003, no. 44(3), pp. 41–65.Alonso M. A. and D\'iaz V. J. 2003, “Variants of mixed parsing of TAG and TIG”, Traitement Automatique des Langues (T.A.L.), no. 44(3), pp. 41–65.Barash, Mihail. Defining Contexts in Context-Free Grammars, Turku Center for Computer Science, TCCS Dissertation no. 204, 2015. URL: url{https://www.doria.fi/bitstream/handle/10024/113793/TUCSDissertationD204.pdf} (Дата обращения: 31.05.2018).Barash Mihail, 2015, Defining Contexts in Context-Free Grammars, Turku Center for Computer Science, TCCS Dissertation No 204. Available at: \url{https://www.doria.fi/bitstream/handle/10024/113793/TUCSDissertationD204.pdf}Boullier, P. On Multicomponent TAG parsing. // In 6th conference annuelle sur le Traitement Automatique des Langues Naturelles (TALN 1999), Cargse, Corse, France, 1999, pp. 321–326.Boullier P. 1999, “On Multicomponent TAG parsing”, In 6th conference annuelle sur le Traitement Automatique des Langues Naturelles (TALN 1999), Cargse, Corse, France, pp. 321–326.Boullier P., Sagot B. Multi-Component Tree Insertion Grammars. // In: de Groote P., Egg M., Kallmeyer L. (eds) Formal Grammar. FG 2009. Lecture Notes in Computer Science, vol 5591. Springer, Berlin, Heidelberg, 2011.Boullier P., Sagot B. 2011. “Multi-Component Tree Insertion Grammars”, In: de Groote P., Egg M., Kallmeyer L. (eds) Formal Grammar, Lecture Notes in Computer Science, vol. 5591, Springer, Berlin-Heidelberg.Claire Gardent and Laura Kallmeyer. Semantic construction in feature-based TAG. // In Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics - Volume 1 (EACL '03), vol. 1, Association for Computational Linguistics, Stroudsburg, PA, USA, 2003, pp. 123-130. doi: 10.3115/1067807.1067825Claire Gardent and Laura Kallmeyer. 2003, “Semantic construction in feature-based TAG”, In Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics - Volume 1 (EACL '03), Vol. 1, Association for Computational Linguistics, Stroudsburg, PA, USA, pp. 123-130. doi: 10.3115/1067807.1067825Marina Kudinova and Pavel Emelyanov. Building Mathematical Model for Restoring Processes Tree during Container Live Migration. // IVth International Conference on Engineering and Telecommunication (EnT), November 2017, Dolgoprudniy. doi: 10.1109/ICEnT.2017.41Marina Kudinova and Pavel Emelyanov. 2017, “Building Mathematical Model for Restoring Processes Tree during Container Live Migration”, IVth International Conference on Engineering and Telecommunication (EnT), November 2017, Dolgoprudniy. doi: 10.1109/ICEnT.2017.41Zengin 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.Zengin M, Vafeiadis V. 2013, “A programming language approach to fault tolerance for fork-join parallelism”, Proceedings of the 7th International Symposium on Theoretical As\-pects of Software Engineering (TASE 2013), Max Planck Institute for Software Systems (MPI-SWS), Saarsbruchen, Germany, 2013. Available at: \url{http://plv.mpi-sws.org/ftpar/tase2013-ftpar.pdf}Adel Cherif, Masato Suzuki, and Takuya Katayama. A Replication Technique Based on a Functional and Attribute Grammar Computation Model. In Proceedings of the The Seventh International Symposium on Software Reliability Engineering (ISSRE '96), IEEE Computer Society, Washington, DC, USA, 1996, p. 266.Adel Cherif, Masato Suzuki, and Takuya Katayama. 1996, “A Replication Technique Based on a Functional and Attribute Grammar Computation Model”, In Proceedings of the The Seventh International Symposium on Software Reliability Engineering (ISSRE '96), IEEE Computer Society, Washington, DC, USA, p. 266.

The authors declare that there are no conflicts of interest present.