Мы разрабатываем проект CRIU (Checkpoint/Restore in Userspace) и у нас возникла достаточно интересная задача о том, как восстановить оригинальное дерево процессов. Я предлагаю вам попытаться решить ее.
Задача
CRIU — это утилита, которая позволяет сохранить состояние процессов на диск и постановить их позднее на этой или на любой другой машине. Одной из подзадач восстановления является нахождение последовательности действий для того, чтобы восстановить дерево процессов. Входные данные содержат набор параметров для каждого процесса: уникальный идентификатор (PID), ссылку на родителя (PPID), идентификатор сессии (SID).
Правила, по которым живут процессы в 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()
Автор: avagin
