Задачка из реальной жизни: Как восстановить дерево процессов в Linux

    Мы разрабатываем проект CRIU (Checkpoint/Restore in Userspace) и у нас возникла достаточно интересная задача о том, как восстановить оригинальное дерево процессов. Я предлагаю вам попытаться решить ее.

    Задача


    CRIU — это утилита, которая позволяет сохранить состояние процессов на диск и постановить их позднее на этой или на любой другой машине. Одной из подзадач восстановления является нахождение последовательности действий для того, чтобы восстановить дерево процессов. Входные данные содержат набор параметров для каждого процесса: уникальный идентификатор (PID), ссылку на родителя (PPID), идентификатор сессии (SID).

    image


    Правила, по которым живут процессы в Linux


    • Иерархия процессов в Linux имеет древовидную структуру.
    • У каждого процесса есть уникальный PID (process ID)
    • У каждого процесса есть SID (session ID). Он наследуется от родителя, и в любой момент времени процесс может решить стать лидером, после чего его SID будет равен PID.
    • Если процесс умирает, то все его дочерние процессы переезжают к ближайшему предку, который является child-reaper-ом, а сам процесс переходит в состояние “зомби”.
    • Родитель может подобрать (уничтожить) любого из дочерних зомби.
    • Корневой процесс всегда является child-reaper-ом, остальные- по желанию (могут в любой момент включить и выключить эту функциональность).
    • Процессы могут рождаться не только вниз (стать дочерним), но и в бок (стать братом).


    Команды:


    • fork(pid) – создаёт процесс с заданным PID, который станет дочерним для текущего
    • clone(pid, CLONE_PARENT) – создаётся процесс с заданным PID, который станет братом для текущего
    • prctl(PR_SET_CHILD_SUBREAPER, flag) – говорит, что текущий процесс будет child-reaper-ом если flag = true и что текущий процесс отказывается быть child-reaper-ом, если flag = false
    • setsid() — делает текущий процесс лидером сессии.
    • exit() — процесс умирает, но не исчезает, а переходит в состояние “zombie”. Все его потомки переезжают к ближайшему child-reaper-у.
    • wait(pid) — подбирает (уничтожает) зомби с заданным PID. Эту операцию, может совершить только родитель зомби.


    Пример входных данных


    Входные данные содержат по строчке на каждый процесс. Каждая строка содержит 3 числа pid, ppid (pid родителя), sid и флаг zombie, который имеет значение 0 — если процесс мертвый (“зомби”), и 1 — если процесс живой.

    1 0 1 1
    6 1 6 1
    8 6 7 1
    15 6 12 1
    10 1 10 1
    11 10 7 1
    13 10 12 1

    Пример выходные данных


    1: fork(6)
    6: fork(7)
    7: setsid()
    7: clone(8, CLONE_PARENT)
    7: exit()
    6: wait()
    8: fork(9)
    9: fork(10)
    10: fork(11)
    10: fork(12)
    12: setsid()
    12: clone(13, CLONE_PARENT)
    12: clone(14, CLONE_PARENT)
    12: exit()
    10: wait(12)
    14: fork(15)
    6: prctl(PR_SET_CHILD_SUBREAPER, 1)
    14: exit()
    10: wait(14)
    6: prctl(PR_SET_CHILD_SUBREAPER, 0)
    9: exit()
    8: wait(9)
    6: setsid()
    10: setsid()
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 12

      0
      Хитрые какие :)
      Сначала свой покажите вариант.
        0
        В чем хитрость? CRIU — это opensource, если вы предложите хорошее решение, то мы обязательно напишем, что это придумано вами.

        Сразу скажу, у нас варианта, который бы нас устраивал, нет. Вы можете посмотреть то что есть на git.criu.org/?p=crtools.git;a=blob;f=pstree.c;hb=HEAD, но оно не покрывает все возможных случаев. Есть решение, которое покрывает все варианты, но оно нас не устраивает по сложности алгоритмов и по количеству вспомогательных процессов, которые создаются во время работы.

        Если тут никто не предложит хорошего решения, то я опишу своё отдельной статьей.
          +1
          Ах вона что, извините тогда.
          Я просто подумал что вы разрабатываете продукт и «споткнулись» на определенной проблеме, и таким образом хотите её решить.

          А можете привести несколько примеров, в каких случаях проще «заморозить» несколько процессов и потом их развернуть на другой машине?
            +1
            Миграция между нодами, для балансировки нагрузки или для проведения сервисных работ. Подобное решение есть в OpenVZ ядре для миграции Linux контейнеров. Оно широко используется хостинг компаниями.

            Обычному юзеру, может быть интересен сценарий с обновлением ядра, без перезагрузки юзерспейса habrahabr.ru/post/160201/.

            На сайте есть еще десяток сценариев, как можно использовать CRIU criu.org/Usage_scenarios
            –1
            Не знал про «криу». Интересненько. (с этой тулины надо бы и начать в статье)
            Я не спец по линуксам, работаю на них только.
            Но правильно ли я понимаю что с этой утилитой можно дампнуть любой процесс? Вместе с его деревом? и в последствии востановить?
            востановление возможно только в схожей системе? Какие ограничения?
              0
              Я о CRIU писал несколько отдельных статей
              habrahabr.ru/post/148413/
              habrahabr.ru/post/152903/
              habrahabr.ru/post/177499/

              Любой процесс задампить нельзя, потому что процесс может иметь внешние связи и некоторые из них нельзя разорвать и потом восстановить. Так же процессы ресторятся с теми же пидами, которые у них были до дампа. Если часть пидов в новой системе занята, то рестор отвалится с ошибкой. Эта проблема обходится использованием pid name-space-ов.

              Если вы хотите гарантировано задампить и поресторить дерево процессов, используйте Linux Containers.
                0
                Я еще не уверен хочу ли я это. Сначало надо разобраться какие есть возмопжности…
                Спасибо за ссылки, буду разбираться.
          0
          Идея навскидку: у каждого процесса есть время его порождения. В принципе, это позволит нам упростить перебор решений, так как более «старый» процесс может быть либо братом, либо отцом для более молодого.
            0
            Так же он может находиться ниже в параллельной ветке.
              0
              Да, не подумал.
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Так известны все потомки и родители. Проблема в другом. Мы не знаем историю, как это дерево было создано.

              Дерево жило своей жизнью, процессы там рождались, умирали, кто-то в какой-то момент времени становился лидером сессии, кто-то child-reaper-ом. Потом пришли мы и сбросили текущее состояние на диск. На ресторе надо восстановить его. Для этого нужно понять кто кого должен породить. В некоторых случаях придется вставлять вспомогательные процессы. К примеру если есть процессы принадлежащие к определенной сессиии, а лидера этот сессии нет.

              Посмотрите на предложенный пример. К нему есть картинка, входные данные и выходные данные.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое