Понятие мьютекса (Mutex) и основные операции с ним. Пример использование мьютекса для синхронизации нитей.
Процессом (process) называется экземпляр программы, загруженной в память. Этот экземпляр может создавать нити (thread), которые представляют собой последовательность инструкций на выполнение. Важно понимать, что выполняются не процессы, а именно нити. Если некоторая структура данных может быть доступна двум параллельно работающим нитям (или нити и прерыванию), и являет собой сущность, к которой нельзя обеспечить атомарный доступ, то работу с такой структурой нужно производить так, чтобы только одна нить одновременно выполняла сложные манипуляции с состоянием структуры.
Простойпример. Список: structlist{list *next; list *prev};
Вставляем элемент в список:
new_el->next = curr_el->next;
new_el->prev = curr_el;
curr_el->next->prev = new_el;
// 3 curr_el->next = new_el;
Но если этот код будут исполнять две нити параллельно, то вместо связного списка получится не понятно, что. Например, если вторая нить включится в момент, когда первая нить закончила строку 3, то обходя список слева направо мы встретим на одном и том же месте один объект, а справа налево — другой. Применим мьютекс — mutually exclusive lock. Этот замок запрещает параллельное исполнение запертого им кода — если одна нить начала его исполнять, вторая будет ждать на входе до тех пор, пока первая не закончит.
mutex_lock (&list->mutex);
new_el->next = curr_el->next;
new_el->prev = curr_el;
curr_el->next->prev = new_el;
// 3 curr_el->next = new_el;
mutex_unlock (&list->mutex);
Что же такое нити? Точно также как многозадачная операционная система может делать несколько вещей одновременно при помощи разных процессов, один процесс может делать много вещей при помощи нескольких нитей. Каждая нить представляет собой независимо выполняющийся поток управления со своим счетчиком команд, регистровым контекстом и стеком. Понятия процесса и нити очень тесно связаны и поэтому трудноотличимы, нити даже часто называют легковесными процессами. Основные отличия процесса от нити заключаются в том, что, каждому процессу соответствует своя независимая от других область памяти, таблица открытых файлов, текущая директория и прочая информация уровня ядра. Нити же не связаны непосредственно с этими сущностями. У всех нитей, принадлежащих данному процессу всё выше перечисленное общее, поскольку принадлежит этому процессу. Кроме того, процесс всегда является сущностью уровня ядра, то есть ядро знает о его существовании, в то время как нити зачастую является сущностями уровня пользователя и ядро может ничего не знать о ней. В подобных реализациях все данные о нити хранятся в пользовательской области памяти, и соответственно такие процедуры как порождение или переключение между нитями не требуют обращения к ядру и занимают на порядок меньше времени.
|
|
|
Для организации взаимоисключения стандарт POSIX предлагает использовать так называемый mutex /от mutual exclusion/. 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_tprint lock = PTHREAD_MUTEX_INITIALIZER;
Voidprint1() {
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'ы неудачным образом.
Ниже изображен граф (рис. 10), иллюстрирующий ситуацию тупика между двумя нитями. Захваты и ожидания ресурсов изображены в виде дуг, нити и ресурсы в виде вершин. Графически тупик выражается в виде наличия цикла в данном графе.
Рис. 10. Тупик между двумя нитями.
Во-первых, можно использовать подход, основанный на применении иерархии mutex'ов. При этом подходе мы устанавливаем некое отношение старшинства между всеми mutex'ами в нашей программе, и в любой ситуации, когда нам необходимо захватить несколько mutex'ов одновременно, мы захватываем строго по старшинству, то есть сначала самый старший, потом mutex который младше первого, но старше остальных и т.п. Если строго соблюдать это правило, то тупиков не возникнет. Оставляя в стороне формальное доказательство этого факта, рассмотрим, как действует этот подход, на нашем примере с двумя mutex'ами и двумя нитями. Согласно правилу обе нити должны будут захватывать сначала mutex A, и только потом B, ясно, что тогда тупиковой ситуации не возникнет, так как после того как первая нить захватит первый 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 /. То есть нет теоретической гарантии работы схемы. Практически же в ситуациях, когда конкуренция за ресурсы не высока, данный подход работает вполне эффективно и надежно.
Дата добавления: 2018-08-06; просмотров: 1953; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!