Preview

Чебышевский сборник

Расширенный поиск

О некоторых комбинаторных свойствах деревьев процессов LINUX

https://doi.org/10.22405/2226-8383-2018-19-2-

Полный текст:

Аннотация

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

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


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

Об авторе

Николай Николаевич Ефанов
МФТИ(ГУ)
Россия

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



Список литературы

1. Mirkin A., Kuznetsov A., Kolyshkin K. Containers checkpointing and live migration // Proceedings of the In Ottawa Linux Symposium, vol. 2, pp. 85-90 (2008).

2. Ефанов Н.Н., Емельянов П. В. Построение формальной грамматики системных вызовов // М. Информационное обеспечение математических моделей, 2017, 83-91 cc.

3. 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.3166106

4. Bozyigit 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.377091

5. Cayley A. A theorem on trees. // Collected Mathematical Papers, 1897, vol. 13. pp. 26-28.

6. 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.1159765

7. Leonardo 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.2491628

8. Белоусов А. И. Дискретная математика, 4-е изд., М.: МГТУ имени Н. Э. Баумана, 2006, 744 с.

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

10. Knuth, Donald E., The Art of Computer Programming Vol 1. 3rd edition, Boston: Addison-Wesley, 1997. ISBN 0-201-89683-4

11. Krippendorff, 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).

12. 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).

13. Охотин А. Формальные грамматики и вычислительная сложность синтаксического анализа. СПбГУ, программа “Математика”, 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).

14. David J. Weir. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1988. doi:10.1145/3166094.3166106

15. M. 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.

16. 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).

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

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

19. 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.1067825

20. Marina 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.41

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

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


Для цитирования:


Ефанов Н.Н. О некоторых комбинаторных свойствах деревьев процессов LINUX. Чебышевский сборник. 2018;19(2):151-162. https://doi.org/10.22405/2226-8383-2018-19-2-

For citation:


Efanov N.N. On some combinatorial properties of LINUX process trees. Chebyshevskii Sbornik. 2018;19(2):151-162. (In Russ.) https://doi.org/10.22405/2226-8383-2018-19-2-

Просмотров: 63


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)