RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2018, том 19, выпуск 2, страницы 151–162 (Mi cheb646)  

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

Н. Н. Ефанов

МФТИ, ЛЦССН МФТИ

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

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

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

Полный текст: PDF файл (382 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.[172-178]
Поступила в редакцию: 13.06.2018
Принята в печать:17.08.2018

Образец цитирования: Н. Н. Ефанов, “О некоторых комбинаторных свойствах деревьев процессов LINUX”, Чебышевский сб., 19:2 (2018), 151–162

Цитирование в формате AMSBIB
\RBibitem{Efa18}
\by Н.~Н.~Ефанов
\paper О некоторых комбинаторных свойствах деревьев процессов LINUX
\jour Чебышевский сб.
\yr 2018
\vol 19
\issue 2
\pages 151--162
\mathnet{http://mi.mathnet.ru/cheb646}
\crossref{https://doi.org/10.22405/2226-8383-2018-19-2-151-162}
\elib{http://elibrary.ru/item.asp?id=37112146}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb646
  • http://mi.mathnet.ru/rus/cheb/v19/i2/p151

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:28
    Полный текст:14
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020