Underground InformatioN Center [&articles] 
[network & security news] [RSS & Twitter] [articles, programing info] [books] [links, soft & more...] [soft archive][home]

Процессы и нити в ОС Linux

Интродакшн
Этот документ я написал когда учился на третьем курсе универа. Вещь замечательно прокатила как курсовой проект [ к ней прилагалась еще программа, в которой демонстрировались возможности многонитевого программирования - небольшой файл-сервер [возможно, будет время, поищу его в залежах архивов и напишу еще одну статейку]. Так вот, третий курс прошел, а курсовая работа осталась. Чтобы не выкидывать в архивы эту работу я решил представить ее вам. Посему убедительная просьба не пугаться чересчур официальному языку - все-таки научный доклад. Претензии по неверной пунктуации расматриваются в последнюю очередь - это все-таки научный доклад студента физтеха :]
Лев Пяхтин /Lev L. Pyakhtin/, also known as .cens [truer at mail ru]

Содержание
Процессы
Примечание: Вся тема "Процессы" полностью повторяет статью г-на cl1mp3x'a
Немного об архитектуре процессов
Ядро представляет собой некую программу, которая является резидентом и обслуживает все таблицы, используемые для управления ресурсами и процессами компьютера.

На самом деле операционная система только управляет образом процесса или сегментами кода и данных, определяющих среду выполнения, а не самим процессом. Сегмент кода содержит реальные инструкции центральному процессору, в которые входят как строки, написанные и скомпилированные пользователем, так и код, сгенерированный системой, который обеспечивает взаимодействие между программой и операционной системой. Данные связанные с процессом, тоже являются частью образа процесса, некоторые из которых хранятся в регистрах [регистры это области памяти, к которым центральный процессор может оперативно получать доступ ]. Для ускорения доступа регистры хранятся внутри центрального процессора.

Для оперативного хранения рабочих данных существует динамическая область памяти /куча[heap ]/. Эта память выделяется динамически и использование ее от процесса к процессу меняется. С помощью кучи программист может предоставить процессу дополнительную память.

Автоматически, при запуске программы, переменные размещаются в стеке [стек служит хранилищем для временного хранения переменных и адресов возврата из процедур ]. Обычно при выполнении или в режиме ожидания выполнения процессы находятся в оперативной памяти компьютера. Довольно большая ее часть резервируется ядром операционной системы, и только к оставшейся ее части могут получить доступ пользователи. Одновременно в оперативной памяти может находится несколько процессов. Память, используемая процессором, разбивается на сегменты, называемые страницами /page/. Каждая страница имеет определенный размер, который фиксирует операционная система в зависимости от типа компьютера. Если все страницы используются и возникает потребность в новой странице, то та страница которая используется меньше остальных помещается в область подкачки /swap area/, а на ее месте создается новая. Но если область подкачки не была определена, то с помощью специальных команд можно разместить область подкачки в файле. Но есть такие страницы которые всегда должны находится в оперативной памяти, которые называются невытесняемыми /nonpreemptable pages/. Обычно такие страницы используются ядром, либо программами подкачки. Главная особенность в постраничном использовании памяти заключается в том, что процесс может использовать больше памяти, чем есть на самом деле.

Процессы могут функционировать в двух режимах: системном и пользовательском. Работа в системном режиме означает выполнение процессом системных вызовов. Он наиболее важен, так как в нем выполняется обработка прерываний, вызванных внешними сигналами и системными вызовами, а также управлением доступом к диску, распределение дополнительной динамической памяти и других ресурсов системы. Процесс функционирует в пользовательском режиме, когда выполняется код, заданный пользователем.

Для каждого процесса создается свой блок управления, который помещается в системную таблицу процессов, находящихся в ядре. Эта таблица представляет собой массив структур блоков управления процессами. В каждом блоке содержатся данные:
  • слово состояния процесса
  • приоритет
  • величина кванта времени, выделенного системным планировщиком
  • степень использования системным процессором
  • признак диспетчеризации
  • идентификатор пользователя, которому принадлежит процесс
  • эффективный идентификатор пользователя
  • реальный и эффективный идентификаторы группы
  • группа процесса
  • идентификатор процесса и идентификатор родительского процесса
  • размер образа, размещаемого в области подкачки
  • размер сегментов кода и данных
  • массив сигналов, ожидающих обработки.
Чтобы система функционировала должным образом, ядру необходимо отслеживать все эти данные.
Создание процесса
Процесс порождается с помощью системного вызова fork(). При этом вызове происходит проверка на наличие свободной памяти, доступной для размещения нового процесса. Если требуемая память доступна, то создается процесс-потомок текущего процесса, представляющий собой точную копию вызывающего процесса. При этом в таблице процессов для нового процесса строится соответствующая структура. Новая структура создается также в таблице пользователя. При этом все ее переменные инициализируются нулями. Этому процессу присваивается новый уникальный идентификатор, а идентификатор родительского процесса запоминается в блоке управления процессом.

Вы скажете: все это замечательно, но если новый процесс - всегда копия существующего, то каким образом в системе работают разные программы? И откуда берется самая первая из них?

Процессы, выполняющие разные программы, образуются благодаря применению имеющихся в стандартной библиотеке Unix функций "семейства exec": execl, execlp, execle, execv, execve, execvp. Эти функции отличаются форматом вызова, но в конечном итоге делают одну и ту же вещь: замещают внутри текущего процесса исполняемый код на код, содержащийся в указанном файле. Файл может быть не только двоичным исполняемым файлом Linux, но и скриптом командного интерпретатора, и двоичным файлом другого формата [например, классом java, исполняемым файлом DOS ]

Таким образом, операция запуска программы, которая в DOS и Windows выполняется как единое целое, в Linux [и в Unix вообще ] разделена на две: сначала производится запуск, а потом определяется, какая программа будет работать. Есть ли в этом смысл и не слишком ли велики накладные расходы? Ведь создание копии процесса предполагает копирование весьма значительного объема информации.

Смысл в данном подходе определенно есть. Очень часто программа должна совершить некоторые действия еще до того, как начнется собственно ее выполнение. Например, создать неименованный канал для общения с другими процессами. Такие каналы создаются системным вызовом pipe, речь о котором пойдет ниже. Реализуется это очень просто - сначала "отпочковываются" процессы, затем проделываются необходимые операции /вызов pipe()/ и только после этого вызван exec.

Аналогичного результата [как показывает, в частности, пример Windows NT ] можно было бы добиться и при запуске программы за один шаг, но более сложным путем. Что же касается накладных расходов, то они чаще всего оказываются пренебрежимо малыми: при создании копии процесса его индивидуальные данные физически никуда не копируются. Вместо этого используется техника, известная под названием copy-on-write /копирование при записи/: страницы данных обоих процессов особым образом помечаются, и только тогда, когда один процесс пытается изменить содержимое какой-либо своей страницы, она дублируется.
Завершение процесса
Для завершения процесса используется системный вызов exit(), при котором освобождаются все используемые ресурсы, такие как память и структуры таблиц ядра. Кроме того, завершаются и процесс-потомки, порожденные данным процессом.

Затем из памяти удаляются сегменты кода и данных, а сам процесс переходит в состояние зомби [ в поле Stat такие процессы помечаются буквой "Z". Зомби не занимает процессорного времени, но строка в таблице процессов остается, и соответствующие структуры ядра не освобождаются. После завершения родительского процесса "осиротевший" зомби на короткое время становится потомком init, после чего уже "окончательно умирает" ]. И, наконец, родительский процесс должен очистить все ресурсы, занимаемые дочерними процессами.

Если родительский процесс по какой-то причине завершится раньше дочернего, последний становится "сиротой" /orphaned process/. Такие "Сироты" также автоматически "усыновляются" программой init, выполняющейся в процессе с номером 1, которая и принимает сигнал об их завершении.

Также, процесс может впасть в "сон", который не удается прервать: в поле Stat это обозначается буквой "D". Процесс, находящийся в таком состоянии, не реагирует на системные запросы и может быть уничтожен только перезагрузкой системы.
Взаимодействие процессов
Самым распространенным средством взаимодействия процессов являются сокеты /sockets/. Программы подключаются к сокету и выдают запрос на привязку к нужному адресу. Затем данные передаются от одного сокета к другому в соответствии с указанным адресом.

Сигнал информирует другой процесс о возникновении определенных условий внутри текущего процесса, требующих реакции текущего процесса. Многие программы обработки сигналов для анализа возникшей проблемы выводят дамп памяти.

Каналы реализованы в двух классах. Первый из них создается с помощью системного вызова pipe(). При этом для обмена информацией между процессами инициализируется специальная структура в ядре. Вызывающему процессу два дескриптора файла, один - для чтения, а другой для записи информации. Затем, когда процесс порождает новый процесс, между двумя процессами открывается коммуникационный канал. Другим типом каналов являются именованные каналы. При их использовании с управляющей структурой в ядре связывается специальный каталог, через который два автономных процесса могут обмениваться данными. При этом, каждый процесс должен открыть канал в виде обычных файлов [ один - для чтения, другой - для записи ]. Затем операции ввода/вывода выполняются обычным образом.

Очередь сообщений представляет собой механизм, когда один процесс предоставляет блок данных с установленными флагами, а другой процесс разыскивает блок данных, флаги которого установлены в требуемых значениях.

Семафоры представляют собой средство передачи флагов от одного процесса к другому. "Подняв" семафор, процесс может сообщить, что он находится в определенном состоянии. Любой другой процесс в системе может отыскать этот флаг и выполнить необходимые действия.

Совместно используемая память позволяет процессам получить доступ к одной и той же области физической памяти.
Нити

Что такое нить?
Точно также как многозадачная операционная система может делать несколько вещей одновременно при помощи разных процессов, один процесс может делать много вещей при помощи нескольких нитей. Каждая нить представляет собой независимо выполняющийся поток управления со своим счетчиком команд, регистровым контекстом и стеком. Понятия процесса и нити очень тесно связаны и поэтому трудноотличимы, нити даже часто называют легковесными процессами. Основные отличия процесса от нити заключаются в том, что, каждому процессу соответствует своя независимая от других область памяти, таблица открытых файлов, текущая директория и прочая информация уровня ядра. Нити же не связаны непосредственно с этими сущностями. У всех нитей принадлежащих данному процессу всё выше перечисленное общее, поскольку принадлежит этому процессу. Кроме того, процесс всегда является сущностью уровня ядра, то есть ядро знает о его существовании, в то время как нити зачастую является сущностями уровня пользователя и ядро может ничего не знать о ней. В подобных реализациях все данные о нити хранятся в пользовательской области памяти, и соответственно такие процедуры как порождение или переключение между нитями не требуют обращения к ядру и занимают на порядок меньше времени.
Создание нити и идеология POSIX API
При выбранном нами для изучения низкоуровневом подходе к поддержке нитей в языке все операции связанные с ними выражаются явно через вызовы функций. Соответственно теперь, когда мы получили общее представление о том, что такое нить, пора рассмотреть вопрос каким же образом мы можем создавать нити и управлять ими в наших программах. Напомню, что мы говорим о программах на языке C и интерфейсе поддержки нитей соответствующему стандарту POSIX. Согласно нему нить создается при помощи следующего вызова:


int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void* (*start)(void *), void *arg)



Упрощенно вызов pthread_create[&thr,NULL,start,NULL] создаст нить которая начнет выполнять функцию start и запишет в переменную thr идентификатор созданной нити. На примере этого вызова мы подробно рассмотрим несколько вспомогательных концепций POSIX API с тем, чтобы не останавливаться на них дальше.

Первый аргумент этой функции thread - это указатель на переменную типа pthread_t, в которую будет записан идентификатор созданной нити, который в последствии можно будет передавать другим вызовам, когда мы захотим сделать что-либо с этой нитью. Здесь мы сталкиваемся с первой особенностью POSIX API, а именно с непрозрачностью базовых типов. Дело в том, что мы практически ничего не можем сказать про тип pthread_t. Мы не знаем целое ли это или указатель? Мы не можем сказать существует ли упорядоченность между значениями этого типа, то есть можно ли выстроить из них неубывающую цепочку. Единственное что сказано в стандарте, это что эти значения можно копировать, и что используя вызов int pthread_equal[pthread_t thr1, pthread_t thr2] мы можем установить что оба идентификатора thr1 и thr2 идентифицируют одну и ту же нить [ при этом они вполне могут быть неравны в смысле оператора равенства ]. Подобными свойствами обладает большинство типов используемых в данном стандарте, более того, как правило, значения этих типов даже нельзя копировать!

Второй аргумент этой функции attr - это указатель на переменную типа pthread_attr_t, которая задает набор некоторых свойств создаваемой нити. Здесь мы сталкиваемся со второй особенностью POSIX API, а именно с концепцией атрибутов. Дело в том, что в этом API во всех случаях, когда при создании или инициализации некоторого объекта необходимо задать набор неких дополнительных его свойств, вместо указания этого набора при помощи набора параметров вызова используется передача предварительно сконструированного объекта представляющего этот набор атрибутов. Такое решение имеет, по крайней мере, два преимущества. Во-первых, мы можем зафиксировать набор параметров функции без угрозы его изменения в дальнейшем, когда у этого объекта появятся новые свойства. Во-вторых, мы можем многократно использовать один и тот же набор атрибутов для создания множества объектов.

Третий аргумент вызова pthread_create это указатель на функцию типа void* ()[void *]. Именно эту функцию и начинает выполнять вновь созданная нить, при этом в качестве параметра этой функции передается четвертый аргумент вызова pthread_create. Таким образом можно с одной стороны параметризовать создаваемую нить кодом который она будет выполнять, с другой стороны параметризовать ее различными данными передаваемыми коду.

Функция pthread_create возвращает нулевое значение в случае успеха и ненулевой код ошибки в случае неудачи. Это также одна из особенностей POSIX API, вместо стандартного для Unix подхода когда функция возвращает лишь некоторый индикатор ошибки а код ошибки устанавливает в переменной errno, функции Pthreads API возвращают код ошибки в результате своего аргумента. Очевидно, это связано с тем что с появлением в программе нескольких нитей вызывающих различные функции возвращающие код ошибки в одну и ту же глобальную переменную errno, наступает полная неразбериха, а именно нет никакой гарантии что код ошибки который сейчас находится в этой переменной является результатом вызова произошедшего в этой а не другой нити. И хотя из-за огромного числа функций уже использующих errno библиотека нитей и обеспечивает по экземпляру errno для каждой нити, что в принципе можно было бы использовать и в самой библиотеке нитей, однако создатели стандарта выбрали более правильный а главное более быстрый подход при котором функции API просто возвращают коды ошибки.
Завершение нити, особенности главной нити
Нить завершается когда происходит возврат из функции start. При этом если мы хотим получить возвращаемое значение функции то мы должны воспользоваться функцией:


int pthread_join(pthread_t thread, void** value_ptr)



Эта функция дожидается завершения нити с идентификатором thread, и записывает ее возвращаемое значение в переменную на которую указывает value_ptr. При этом освобождаются все ресурсы связанные с нитью, и следовательно эта функция может быть вызвана для данной нити только один раз. На самом деле ясно, что многие ресурсы, например, стек и данные специфичные для нити, могут быть уже освобождены при возврате из функции нити, а для возможности выполнения функции pthread_join достаточно хранить идентификатор нити и возвращаемое значение. Однако стандарт говорит лишь о том что ресурсы связанные с нитью будут освобождаться после вызова функции pthread_join.

В случае если нас чем-то не устраивает возврат значения через pthread_join, например, нам необходимо получить данные в нескольких нитях, то следует воспользоваться каким либо другим механизмом, например, можно организовать очередь возвращаемых значений, или возвращать значение в структуре указатель на которую передают в качестве параметра нити. То есть использование pthread_join это вопрос удобства, а не догма, в отличие от случая пары fork() - wait(). Дело тут в том, что в случае если мы хотим использовать другой механизм возврата или нас просто не интересует возвращаемое значение то мы можем отсоединить [ detach ] нить, сказав тем самым что мы хотим освободить ресурсы связанные с нитью сразу по завершению функции нити. Сделать это можно несколькими способами. Во-первых, можно сразу создать нить отсоединенной, задав соответствующий объект атрибутов при вызове pthread_create. Во-вторых, любую нить можно отсоединить вызвав в любой момент ее жизни [ то есть до вызова pthread_join() ] функцию


int pthread_detach(pthread_t thread)



и указав ей в качестве параметра идентификатор нити. При этом нить вполне может отсоединить саму себя получив свой идентификатор при помощи функции pthread_t pthread_self[void]. Следует подчеркнуть, что отсоединение нити никоим образом не влияет на процесс ее выполнения, а просто помечает нить как готовую по своем завершении к освобождению ресурсов. Фактически тот же pthread_join, всего лишь получает возвращаемое значение и отсоединяет нить.

Замечу, что под освобождаемыми ресурсами подразумеваются в первую очередь стек, память в которую сохраняется контекст нити, данные специфичные для нити и тому подобное. Сюда не входят ресурсы выделяемые явно, например, память выделяемая через malloc, или открываемые файлы. Подобные ресурсы следует освобождать явно и ответственность за это лежит на программисте.

Помимо возврата из функции нити существует еще один способ завершить ее, а именно вызов аналогичный вызову exit() для процессов:


int pthread_exit(void *value_ptr)



Этот вызов завершает выполняемую нить, возвращая в качестве результата ее выполнения value_ptr. Реально при вызове этой функции нить из нее просто не возвращается. Надо обратить также внимание на тот факт, что функция exit() по-прежнему завершает процесс, то есть в том числе уничтожает все потоки.

Как известно, программа на Си начинается с выполнения функции main(). Нить, в которой выполняется данная функция, называется главной или начальной [ так как это первая нить в приложении ]. С одной стороны это нить обладает многими свойствами обычной нити, для нее можно получить идентификатор, она может быть отсоединена, для нее можно вызвать pthread_join из какой-либо другой нити. С другой стороны она обладает некоторыми особенностями, отличающих ее о других нитей. Во-первых, возврат из этой нити завершает весь процесс, что бывает иногда удобно, так как не надо явно заботиться о завершении остальных нитей. Если мы не хотим чтобы по завершении этой нити остальные нити были уничтожены, то следует воспользоваться функцией pthread_exit. Во-вторых, у функции этой нити не один параметр типа void* как у остальных, а пара argc-argv. Строго говоря функция main не является функцией нити так как в большинстве ОС, она сама вызывается некими функциями которые подготавливают ее выполнение автоматически формируемыми компилятором. В-третьих, многие реализации отводят на стек начальной нити гораздо больше памяти чем на стеки остальных нитей. Очевидно, это связано с тем что уже существует много однониточных приложений [ то есть традиционных приложений ] требующих значительного объема стека, а от автора нового многониточного приложения можно потребовать ограниченности аппетитов.
Жизненный цикл нити
Рассмотрим теперь жизненный цикл нити, а именно последовательность состояний в которых пребывает нить за время своего существования. В целом можно выделить четыре таких состояния:

Состояние нитиЧто означает
Готова /Ready/ Нить готова к выполнению, но ожидает процессора. Возможно она только что была создана, была вытеснена с процессора другой нитью, или только что была разблокирована [ вышла из соответствующего состояния ].

Выполняется /Running/ Нить сейчас выполняется. Следует заметить, что на многопроцессорной машине может быть несколько нитей в таком состоянии.

Заблокирована /Blocked/ Нить не может выполняться, так как ожидает чего-либо. Например, окончания операции ввода-вывода, сигнала от условной переменной, получения mutex и т.п.

Завершена /Terminated/ Нить была завершена, например, вследствие возврата из функции нити, вызова pthread_exit, прерывания выполнения нити /cancellation/. Нить при этом еще не была отсоединена и для нее не была вызвана функция pthread_join. Как только происходит одно из этих событий, нить перестает существовать.



Различные частные реализации могут вводить дополнительные к этим четырем состояния, но все они буду в сущности лишь подсостояниями этих. В целом диаграмму переходов между этими состояниями можно изобразить следующим образом:

Четыре основных состояния нити /ready-running-blocked-terminated/


Нити могут создаваться системой, например, начальная нить, которая создается при создании процесса, или могут создаваться при помощи явных вызовов pthread_create() пользовательским процессом. Однако любая создаваемая нить начинает свою жизнь в состоянии "готова". После чего в зависимости от политики планирования системы она может либо сразу перейти в состояние "выполняется" либо перейти в него через некоторое время. Здесь необходимо обратить внимание на типичную ошибку совершаемую многими, которая заключается в том, что в отсутствии явных мер по синхронизации старой и новой нитей предполагают, что после возврата из функции pthread_create новая нить будет существовать. Однако это не так, ибо при определенной политике планирования и атрибутах нити вполне может статься, что новая нить уже успеет выполниться к моменту возврата из этой функции.

Выполняющаяся нить, скорее всего, рано или поздно либо перейдет в состояние "заблокирована", вызвав операцию ожидающую чего-то, например, окончания ввода-вывода, прихода сигнала или поднятия семафора, либо перейдет в состояние "готова" будучи снята с процессора или более высокоприоритетной нитью или просто потому что исчерпала свой квант времени. Здесь надо подчеркнуть разницу между вытеснением /preemption/ то есть снятием с процессора вследствие появления готовой более приоритетной задачи, и снятием нити вследствие истечения ее кванта времени. Дело в том, что типичная ошибка предполагать что первое подразумевает второе. Существуют политики планирования которые просто не поддерживают понятие кванта времени. Такова, например политика планирования по умолчанию для нитей в ОС Solaris. Такова одна из стандартных [в смысле POSIX] политик планирования реального времени SCHED_FIFO.

Заблокированная нить, дождавшись события которого она ожидала, переходит в состояние "готова" при этом, конечно в случае если есть такая возможность, она сразу перейдет в состояние выполнения.

Наконец выполняющаяся нить может завершиться тем или иным способом. Например в следствии возврата из функции нити, вызова функции pthread_exit или вследствие насильственного прерывания ее выполнения при помощи вызова pthread_cancel. При этом, если нить была отсоединена, то она сразу освобождает все связанные с ней ресурсы и перестает существовать /На самом деле она скорее всего просто будет повторно использована библиотекой поддержки нитей, поскольку создание нити не самая дешевая операция/. В случае если нить не была отсоединена, то она, возможно, освободит часть ресурсов, после чего перейдет в состояние "завершена", в котором и будет находиться до тех пор, пока не будет отсоединена либо с помощью pthread_detach, либо pthread_join. После чего она опять же освободит все ресурсы и прекратит существование.

Синхронизация c использованием mutex

Что такое mutex?
Для организации взаимоисключения стандарт POSIX предлагает использовать так называемый mutex /от mutual exclusion/. Mutex можно рассматривать как изначально открытую комнату. Первая нить которая зашла под mutex, то первый человек вошедший в комнату закрывает ее. Другие нити или другие люди не могут попасть в эту комнату пока эта нить, то есть человек не откроет комнату и не выйдет из нее. То есть мы имеем взаимное исключение при доступе к общему ресурсу в чистом виде. Или модель туалетной кабинки кому, что больше нравится.

Почему mutex?
Как показывает практика правильно использовать его проще, чем другие механизмы синхронизации. На основе mutex и еще одного механизма, про который мы поговорим позже, легко построить все остальные механизмы синхронизации. Кроме того, его легко и дешево реализовывать [однако о реализации мы поговорим позже и отдельно].
Использование mutex
В программах написанных для OS Linux mutex представляется переменными типа pthread_mutex_t. Прежде начать использовать объект типа pthread_mutex_t по назначению, то есть для синхронизации, необходимо провести ее инициализацию. При этом возможно будут выделены какие-либо системные ресурсы, например, pthread_mutex_t может представлять собой всего лишь указатель на объект который представляет mutex и тогда при инициализации mutex'а требуется выделение памяти под этот объект. Это можно сделать при помощи функции:


int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);



В случае если мы хотим создать mutex с атрибутами по умолчанию, память под который будет выделяться статически, то мы можем воспользоваться макросом PTHREAD_MUTEX_INITIALIZER. Например, если мы имеем переменную этого типа объявленную вне всяких функций, то есть глобальную в рамках программы /extern/ или рамках модуля /static/ переменную и хотим создать на основе нее mutex с атрибутами по умолчанию то мы можем сделать это следующим образом:


pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;



После успешной инициализации mutex оказывается в свободном состоянии, то есть к нему можно применить операцию lock, соответственно мы будем употреблять такие словосочетания, как установить взаимоисключающую блокировку, захватить mutex, защелкнуть mutex. Вместо английского же названия операции освобождения для mutex'а unlock, мы будем употреблять такие термины, как снять блокировку, освободить mutex.

Итак после того как мы проинициализировали mutex, мы можем захватить его при помощи одной из функций:


int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);



Первая из двух функций просто захватывает mutex, при этом если на данный момент mutex уже захвачен другой нитью, эта функция дождется его освобождения. Вторая же функция попытается захватить mutex если он свободен, а если он окажется занят, то немедленно возвратит специальный код ошибки EBUSY. То есть pthread_mutex_trylock фактически является неблокирующим вариантом вызова pthread_mutex_lock /в том смысле что он не приводит к ожиданию в течение неопределенных промежутков времени/. Соответственно как и в случае с неблокирующим вводом/выводом вместо того чтобы ожидать чего-либо нить может заниматься какой-то полезной работой.

При этом надо заметить, что нить, которая уже владеет mutex, не должна повторно пытаться захватить mutex, так как при этом либо будет возвращена ошибка либо может произойти то, что в англоязычной литературе называется self-deadlock /самотупиковая ситуация :]/, то есть нить будет ждать освобождения mutex до тех пор пока сама не освободит его, то есть фактически до бесконечности.

Для освобождения захваченного mutex'а предназначена функция:


int pthread_mutex_unlock(pthread_mutex_t *mutex);



Стоит еще раз подчеркнуть, что нить может освобождать mutex только предварительно захваченный этой же нитью. Результат работы функции pthread_mutex_unlock() при попытке освободить захваченный другой нитью или вообще свободный mutex не определен. Другими словами вызов этой функции корректен если данная нить перед этим успешно выполнила либо pthread_mutex_lock() или pthread_mutex_trylock() и не успела выполнить комплиментарный им pthread_mutex_unlock().

Если мы инициализировали наш mutex при помощи функции pthread_mutex_init(), а не при помощи PTHREAD_MUTEX_INITIALIZER то мы обязаны рано или поздно /но в любом случае до повторного использования памяти в которой располагается объект типа pthread_mutex_t/ уничтожить его освободив связанные с ним ресурсы. Сделать это можно вызвав функцию:


int pthread_mutex_destroy(pthread_mutex_t *mutex);



При этом на момент вызова этой операции уничтожаемый mutex должен быть свободен, то есть, не захвачен ни одной из нитей, в том числе вызывающей данную операцию. Может возникнуть вопрос: как этого добиться? Обычно это условие выполняется за счет определенной логики организации программы.

Например, если у нас mutex защищает некий элемент списка, то, исключив этот элемент из списка и зная, что ни в одной из нитей не осталось ссылок на этот элемент [это можно проконтролировать, например, имея счетчик ссылок], мы можем спокойно уничтожать mutex.

В случае если мы инициализировали mutex при помощи макроса PTHREAD_MUTEX_INITIALIZER, то необходимость в его явном уничтожении отсутвует, то есть для него не нужно вызывать функцию phtread_mutex_destroy().

Рассмотрим еще раз как работает механизм mutex на следующем примере:

На первый взгляд каша, но если вглядеться, то все станет просто и понятно



Рассмотрим теперь простой пример использования mutex для организации взаимного исключения при доступе к такому общему ресурсу как стандартный вывод: Пусть у нас есть набор процедур выводящих некие группы строк на стандартный вывод, эти процедуры буду вызываться из разных нитей. При этом для нас важно чтобы некоторые из этих групп не прерывались выводом других строк. Тогда соответствующий код мог бы выглядеть таким образом [сначала рассмотрим случай с одной группой]:


  pthread_mutex_t print_lock = PTHREAD_MUTEX_INITIALIZER;

  void print1() {
    pthread_mutex_lock(&print_lock);
    printf("Print 1 - line 1\n");
    printf("Print 1 - line 2\n");
    pthread_mutex_unlock(&print_lock);
  }





То есть при входе в процедуру мы захватываем mutex, а перед выходом из нее его освобождаем. Таким образом, мы организовали из нашей процедуры критическую секцию. В случае если у нас есть другие процедуры, которые могут вызываться одновременно с данной, и в них следует организовать критические секции. Например:


  void print2() {
    pthread_mutex_lock(&print_lock);
    printf("Print 2\n");
    pthread_mutex_unlock(&print_lock);
  }





При этом мы естественно должны использовать тот же mutex. Сразу видно, что на самом деле mutex связан не с процедурой, а с данными [в данном случае со стандартным выводом], и что защищает он именно данные. Используя подход, ориентированный на данные, а не на код, мы с меньшей вероятностью совершим такую ошибку как не использование mutex'а при доступе к общему ресурсу. Из тех же соображений снижения количества ошибок mutex который защищает какие-либо данные то логично располагать рядом с этими данными так тогда его легко заметить.

При разработке многонитевых программ перед нами может встать вопрос о том, что именно должен защищать mutex. Например, в случае если мы имеем некий массив, доступ к одним и тем же элементам которого осуществляется из различных нитей, то мы можем пойти несколькими путями. Во-первых, мы можем иметь для каждого элемента массива свой персональный mutex, который его защищает. Во-вторых, мы можем завести один mutex, который будет защищать все элементы массива. Кроме, того существует целый ряд промежуточных вариантов, например, иметь k mutex'ов, где каждый m-тый из них защищает элементы массива остаток деления индекса которых на k равен m, можно иметь защищаемый одним mutex список элементов к которым сейчас осуществляется доступ и т.п. Одним словом, перед нами встает вопрос насколько велик должен быть mutex, то есть, сколько объектов он должен защищать. Чем больше объектов mutex защищает тем больше он считается [стоит, подчеркнуть что речь идет не о физических его размерах скажем в памяти, а скорее о логических размерах]. При принятии подобного решения нам приходится учитывать два противоположных фактора:
  • Mutex'ы не бесплатны. Операция захвата mutex'а занимает некоторое время, как впрочем и операция его освобождения. Таким образом, чем больше mutex'ов мы вынуждены захватывать/освобождать тем больше времени мы расходуем на накладные расходы. Кроме того, каждый mutex занимает некоторый, возможно маленький, объем памяти, соответственно чем больше абсолютное число mutex'ов в нашей программе тем больше памяти расходуется на них. Соответственно чем меньше mutex'ов мы вынуждены захватывать тем больше времени мы экономим, а чем меньше абсолютное количество mutex'ов в нашей программе тем больше экономим мы памяти.


  • Mutex'ы по своему определению организуют взаимное исключение и тем самым сериализуют выполнение программы. Тот есть возможно там, где у нас нити могли бы выполняться параллельно, например, когда они работают с независимыми данными, они выполняются последовательно. Как следствие по закону Амдала который упоминался на первой лекции уменьшается ускорение работы программы. Поэтому может быть выгодно иметь больше mutex'ов защищающих независимые данные обеспечивая тем самым большие возможности для параллелизма.
Обычно, в сложных программах принятие решения о размерах тех или иных mutex'ов происходит на основе ряда экспериментов. Как правило, программу проще писать если в ней больше mutex'ов, то есть, скажем, есть по mutex'у на каждый объект. Следовательно, получает право на жизнь следующая стратегия: изначально программа пишется с большим количеством mutex'ов, а если при этом возникают проблемы с производительностью или нехваткой других ресурсов, то пытаются провести ее оптимизацию, то есть, уменьшить каким либо образом количество mutex'ов. Основную идею этого подхода можно сформулировать и так: не надо оптимизировать пока нет проблемы. С другой стороны если ваш опыт подсказывает что в конкретном случае обязательно возникнет проблема с mutex'ами, то имеет смысл сразу принять какое-то более оптимальное решение.

Проблема тупиков
Из вышесказанного следует, что иногда в программах появляется необходимость захватывать и удерживать одновременно несколько mutex'ов. При этом возможно возникновение таких типичных для параллельного программирования ситуаций как тупиков. Тупик это ситуация в которой несколько потоков управления таким образом захватили в монопольное использование ресурсы что исключили возможность дальнейшего выполнения для себя. Типичный пример тупика это ситуация когда первая нить захватила mutex A, и пытается захватить mutex B, в то время как вторая нить уже захватила mutex B и для дальнейшего выполнения ей необходимо захватить mutex A. Ясно что в такой ситуация дальнейшее выполнение ни одной из нитей невозможно. В общем случае мы имеем несколько нитей, которые захватили mutex'ы неудачным образом.

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

проблема тупиков

Каким образом можно решить проблему тупиков?
Во-первых, можно использовать подход, основанный на применении иерархии mutex'ов. При этом подходе мы устанавливаем некое отношение старшинства между всеми mutex'ами в нашей программе, и в любой ситуации, когда нам необходимо захватить несколько mutex'ов одновременно, мы захватываем строго по старшинству, то есть сначала самый старший, потом mutex который младше первого, но старше остальных и т.п. Если строго соблюдать это правило то тупиков не возникнет. Оставляя в стороне формальное доказательство этого факта, рассмотрим, как действует этот подход, на нашем примере с двумя mutex'ами и двумя нитями. Согласно правилу обе нити должны будут захватывать сначала mutex A, и только потом B, ясно, что тогда тупиковой ситуации не возникнет, так как после того как первая нить захватит первый mutex, второй либо будет свободен [если вторая нить нуждается в обоих mutex'ах, то она остановится на захвате первого], либо будет захвачен, но на конечный отрезок времени / в случае если вторая нить хочет работать только со вторым mutex'ом, то ничто не помешает ей его захватить, но тупика не возникнет, так как она не имеет права пытаться захватить первый, и, следовательно, обязана освободить захваченный mutex в течение конечного периода времени /.

Стоит заметить, что часто не надо устанавливать отношения иерархии между всеми mutex'ами, так, например, если логика программы нам гарантирует что два mutex'а никогда не будет захватываться последовательно одной нитью, то нас не интересует отношение старшинства меду ними / иногда его можно вывести на основании правила транзитивности из отношений старшинства между этими и другими mutex'ами, а иногда и нельзя /.

Может возникнуть вопрос - а как именно устанавливать это самое отношение старшинства? Часто это отношение обусловлено самой структурой данных, которые защищают mutex'ы. Например, очевидно, что если мы имеем контейнер, который защищен mutex'ом и который содержит объекты каждый из которых сам защищен mutex'ом, то логично сначала захватывать mutex контейнера, а потом mutex объекта / при этом mutex контейнера можно освободить, дав другим нитям возможность работать с другими объектами в данном контейнере /. В случае если мы не можем просто задать иерархию опираясь на свойства данных, например, если мы имеем некоторое неизвестное заранее количество динамически создаваемых объектов, то можно воспользоваться следующим искусственным приемом для наведения иерархии. Этот прием заключается в том что мы определяем что первый mutex старше второго, если абсолютное значение адреса первого mutex'а больше соответствующего значения для второго [а можно использовать адреса защищаемых объектов или более того ввести нумерацию выдавая последовательный номер для каждого mutex'а при его инициализации]. Замечу что в реальных приложениях мы скорее всего будем использовать некую комбинацию этих двух подходов установления отношения старшинства.

Иногда подход предотвращения тупиков основанный на установлении иерархии mutex'ов неудобен. Так в случае если мы наперед не знаем к каким именно объектам нам потребуется получить доступ и соответственно мы не можем сказать какие mutex'ы мы захотим захватить до того как захватим ряд из них, нам придется при каждом захвате более старшего чем ранее захваченные mutex'ы освобождать эти mutex'ы чтобы вскоре снова захватить их начав с этого старшего. Опять же крайне неудобной при таком подходе представляется работа с двунаправленными списками с защищенными mutex'ами элементами обход по которым необходимо осуществлять в обоих направлениях.

В этих случаях имеет смысл использовать второй подход к предотвращению тупиков. Он основывается на использовании неблокирующего варианта операции захвата mutex'а, то есть pthread_mutex_trylock и называется "попытка и откат" / try and back-off /. Идея этого подхода очень проста: мы можем захватываем mutex'ы в произвольном порядке, но используем при этом операцию pthread_mutex_trylock, если эта операция в некоторый момент нам возвращает EBUSY / то есть если один из mutex'ов который мы пытаемся захватить уже захвачен /, то мы освобождаем все захваченные mutex'ы, как бы уступая дорогу нашему конкуренту. Ясно, что при таком подходе тупиков не возникает, с другой стороны сразу виден основной недостаток этого метода, а именно дополнительные накладные расходы, которые появляются из-за многократных попыток захвата и многократного освобождения mutex'ов. Кроме того, легко себе представить ситуацию, когда две нити пытаются захватить один и тот же набор mutex'ов A и B, но в разном порядке, и при этом ни одна из них не может сделать этого, так как все время натыкается на соперничающую нить / несмотря на то, что та регулярно освобождает свой mutex /. То есть нет теоретической гарантии работы схемы. Практически же в ситуациях, когда конкуренция за ресурсы не высока, данный подход работает вполне эффективно и надежно.
Анализ

Базовые термины
Прежде чем перейти к рассказу о том, какие же конкретно преимущества дает нам многонитевое программирование, необходимо пояснить значение некоторых терминов которые мы будем активно использовать.

Под асинхронными событиями мы будем понимать события, которые происходят независимо [возможно одновременно] за исключением случаев, когда зависимость устанавливается внешними силами. События в реальной жизни происходят асинхронно, зависимости между ними устанавливают законы природы, если между событиями нет зависимости то они могут происходить одновременно.

Термином конкуренция будем описывать ситуацию, когда кажется, что процессы происходят одновременно, однако на самом деле они могут происходить последовательно. Этим термином хорошо описывается, например, поведение одновременно выполняющихся процессов на однопроцессорной машине, хотя нам и кажется, что сейчас выполняется несколько процессов, но на самом деле в данный конкретный момент выполняется только один процесс получивший текущий квант процессорного времени.

Словом параллелизм будем описывать ситуацию, когда два процесса выполняются одновременно, то есть параллельно, не пересекаясь. Настоящий параллелизм может проявляться только на многопроцессорных системах, в то время как конкуренция и на однопроцессорных и на многопроцессорных системах. Иными словами конкуренция представляет собой лишь иллюзию параллелизма. А настоящий параллелизм требует для одновременного выполнения нескольких процессов нескольких исполнителей.
Преимущества многонитевого программирования
Эффективное использование аппаратуры поддерживающей параллелизм. И в первую очередь SMP систем, то есть машин, имеющих несколько процессоров и общую, то есть равнодоступную каждому из них память.

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

Замечу что, очевидно, того же эффекта, да и вообще всего что мы можем достичь при помощи нитей, можно достичь, распараллелив приложение на несколько процессов, организовав обмен данными между ними при помощи разделяемой памяти и других средств межпроцессной коммуникации. Однако такое даст большие, чем многонитевой вариант, накладные расходы и сложнее в реализации.
Использование конкуренции
Используя нити и конкуренцию, мы можем повысить производительность программ даже без использования аппаратуры обеспечивающей истинный параллелизм. Пусть мы имеем две нити в программе выполняющейся на однопроцессорной машине:

Нить Т1 выполняет длительную операцию ввода/вывода



Пусть первая нить начинает долгую операцию ввода/вывода, тогда вторая нить получает процессорное время. Таким образом, вместо того чтобы простаивать, как это было бы в случае однониточного варианта, наша программа продолжает выполняться.

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

Однако оба эти способа обладают тем существенным недостатком, что код получающийся при их реализации достаточно сложен, так как в нем приходится разносить ввод-вывод и обработку данных. Реально для каждого файла, в который производится ввод или вывод, приходится хранить состояние этой операции. Если мы немного подумаем над этим, то увидим что фактически мы храним состояние неких псевдонитей и при помощи нашего кода осуществляем планирование для них. Но поскольку точно также как обычная нить легче процесса, это состояние и работа с ним легче обычной нити, то в приложениях рассчитанных на большое количество одновременных операций ввода-вывода, как правило, используются именно эти более сложные подходы. Стоит заметить, что идею о том, что программирование с использованием неблокирующего ввода-вывода суть некое подобие многонитевого программирования, эксплуатируют некоторые библиотеки, реализующие механизм нитей, сочетая с одной стороны эффективность присущую неблокирующему вводу-выводу, с ясностью программ построенных на использовании нитей.

Особую остроту проблема ввода-вывода приобретает в сетевых приложениях, где блокирование однониточного процесса медленной операцией ввода-вывода в сеть при обслуживании одного из запросов, ведет к приостановке обслуживания других запросов. Как правило, такое поведение для этих приложений не приемлемо. Именно поэтому, практически сразу в них использовались возможности конкурентного выполнения запросов, сначала основанные на использовании многих процессов, потом на использовании многих нитей или неблокирующего ввода-вывода. Однако здесь, пожалуй, мы подошли к следующему преимуществу, которое дает нам использование конкуренции для нитей. Мы можем улучшить наши приложения, сократив время отклика на операции в них, это относится как к приведенной ситуации с сетевым вводом-выводом, так и к ситуациям, когда, скажем, одна нить в приложении обрабатывает нажатия кнопок и отвечает за перерисовку окон, а другая нить, например, выполняет какую-то вычислительную задачу. Таким образом, мы можем повысить качество наших интерфейсов, не заставляя пользователя ожидать выполнения какой либо длительной операции, показывая песочные часы.

Этот вариант использования нитей можно рассматривать, как нашу попытку придать программе возможность адекватно реагировать на события внешнего мира, которые обычно происходят асинхронно.

Опять же, в принципе, проблема вполне может быть решена с использованием архитектуры ориентированной на события, которую обычно используют в оконных системах. Основная идея этого подхода заключается в том, что вся работа асинхронного приложения рассматривается, как циклическая обработка событий любой внешний ввод или сигнал рассматривается как событие, которое надо обработать при помощи вызова некоей процедуры или некого метода некого объекта. Хотя при грамотной реализации такой подход скроет от программиста значительную часть сложности связанной с реализацией асинхронного ввода-вывода, он обладает тем недостатком, что в случае если нам необходимо в качестве реакции на событие выполнить некое длительное действие, то мы заблокируем на это время обработку остальных событий. Единственный выход - дробление таких длительных событий на набор мелких событий, что зачастую бывает сложно сделать, а иногда и вообще не возможно. Кроме того, ясно видно, что мы опять пытаемся реализовать некую функциональность уже реализованную в библиотеке нитей [а именно планирование переключений между потоками].
Улучшение структуры программ
Даже если мы уверены в том, что наша программа в многониточном варианте не будет работать производительнее, мы можем получить некие преимущества от использования нитей. А именно, выделяя в наших программах независимые события и последовательности событий и оформляя их в виде различных нитей, мы можем получить программы лучше отражающие реальность, которые как следствие будет удобнее сопровождать.
Недостатки у многонитевых программ
Естественно за все хорошее приходится платить. Чем же нам приходится платить в случае использования нитей?

Во-первых, возможной потерей производительности. Очевидно, что даже полностью распараллеливаемое вычислительно интенсивное приложение на однопроцессорной машине, в многониточном варианте будет выполняться медленнее своей однониточной версии. Это обусловлено в первую очередь накладными расходами на управление нитями и обеспечение согласования между ними [на синхронизацию]. Далее, даже при выполнении на многопроцессорной машине в случае плохо распараллеливаемого кода мы можем оказаться в ситуации, когда упомянутые накладные расходы превысят выигрыш от использования параллелизма.

Во-вторых, написание многониточных программ требует большей аккуратности, чем написание обычных программ. К стандартным проблемам, таким как выход за границы своей памяти, висячие ссылки и т.п. добавляются разнообразные проблемы связанные с параллельным программированием такие как тупики, условия гонок [race conditions] и многие другие. [сложность кодирования]

В-третьих, многонитевые программы по целому ряду причин труднее отлаживать, чем однониточные программы. Здесь сказывается и некоторая недоразвитость средств отладки таких приложений [хотя существуют программы облегчающие труд программиста, проверяя некие формальные признаки правильности программы], и то, что собственно сам процесс отладки, изменяя временные характеристики выполнения программы, может привести к ее поведению совершенно отличному от того, при котором проявлялась ошибка, и наконец тот простой факт что если раньше, например, испортить память мог только сам процесс, то сейчас это может сделать любая из нескольких нитей процесса. В результате наиболее мощным средством отладки подобных программ по-прежнему остается мозг программиста.

Только внимательно взвешивая все перечисленные и некоторые другие факторы следует принимать решение о том стоит ли использовать нити в программе или нет.


Статья написана специально для UiNC (www.uinc.ru)

Keywords: процессы, процессы в Unix, процессы в Юникс, процессы в Linux, процессы в Линукс, pthread_create, pthread_mutex, cl1mp3x, Потоки, Нити, Сокеты, Очередь, Мьютексы, Семафоры, Многозадачность

Все документы и программы на этом сайте собраны ТОЛЬКО для образовательных целей, мы не отвечаем ни за какие последствия, которые имели место как следствие использования этих материалов\программ. Вы используете все вышеперечисленное на свой страх и риск.

Любые материалы с этого сайта не могут быть скопированы без разрешения автора или администрации.


[network & security news] [RSS & Twitter] [articles, programing info] [books] [links, soft & more...] [soft archive][home]
 Underground InformatioN Center [&articles] Choose style:
2000-2015 © uinC Team