Олег Цилюрик - QNX/UNIX: Анатомия параллелизма
Поток А Поток В
sem_wait(&sem); sem_wait(&sem);
/* код, который нужно защитить /* код, который нужно защитить
от совместного использования. */ от совместного использования. */
sem_post(&sem); sem_post(&sem);
В данном случае последовательность доступа потоков к защищаемому участку кода (такой участок кода еще называют критической секцией) не играет никакой роли; здесь важно не допустить, чтобы два потока исполняли этот код одновременно.
Поскольку семафор инициализируется единицей, первый вызов sem_wait() не приводит к блокированию потока, а лишь понижает счетчик семафора до нуля. В таком положении семафора любой поток, повторно вызвавший sem_wait() на входе в критическую секцию, будет блокирован до тех пор, пока первый вошедший поток не покинет этот участок кода и не вызовет sem_post(). После этого один из потоков, ожидающих увеличения счетчика семафора, получит управление (это будет один поток, и нельзя заранее сказать, какой именно) и выполнит операцию декремента над счетчиком, вновь заблокировав вход в критическую секцию. Таким образом можно гарантировать строго последовательное выполнение такого кода.
Однако при использовании семафоров для решения задачи взаимного исключения потоков разного приоритета может возникнуть серьезная проблема, известная как инверсия приоритетов. Вопрос инверсии рассматривался в нашей работе [4], и мы не будем здесь подробно останавливаться на этом. В простейшем случае проблема заключается в том, что если в системе присутствуют несколько (3 или более) потоков разного приоритета (высокого, среднего и низкого), использующих общий ресурс, то возможно возникновение ситуации, когда высокоприоритетный поток будет блокирован в ожидании ресурса, ранее захваченного потоком самого низкого приоритета, который в свою очередь вытеснен потоком среднего приоритета, причем такой неразрешимый «клинч» может продолжаться неограниченно долго.
Каким же образом можно предотвратить подобную ситуацию? Для этого необходимо проводить манипуляции с приоритетом потока, входящего в критическую секцию. Однако после выполнения потоком функции sem_wait() (при этом счетчик семафора уменьшается до нуля) и перехода к выполнению кода критической секции уже никак нельзя определить, какой поток заблокировал семафор, и нельзя ничего сделать с его приоритетом.
Для того чтобы система имела возможность влиять на поведение потоков с точки зрения профилактики инверсии приоритетов и взаимных блокировок («мертвых объятий» — deadlock) потоков или других подобных проблем, вызванных взаимным влиянием потоков, необходимо, чтобы объект синхронизации явным образом хранил информацию о том потоке, который его захватил (то есть знал своего хозяина). Семафор такой информации не хранит, и это необходимо помнить при проектировании системы с его использованием. Применение семафора оптимально для случаев слабо связанных и в идеале равноприоритетных потоков. Собственно, для этих случаев семафор как средство синхронизации и разрабатывался [10].
• Частным случаем задачи взаимного исключения является классическая задача последовательного доступа по типу производитель/потребитель. Такая ситуация возникает, когда один поток передает другому данные через общую переменную. Пока производитель не «положит» новые данные в эту переменную, потребитель должен простаивать в ожидании.
Приведем классическое решение этой задачи. В этом случае нам понадобится два семафора (по одному на каждый поток), которые должны инициализироваться следующим образом: тот, который защищает чтение (потребление), инициализируется нулем (блокирует читающий поток), а тот, который защищает запись (производство), — единицей (открывает доступ «писателю» к общему ресурсу).
Поток А Поток В
sem_wait(&sem_A); sem_wait(&sem_B);
/* критическая секция */ /* критическая секция */
sem_post(&sem_B); sem_post(&sem_A);
Положим, поток А является производителем данных, необходимых для работы потока В. Соответственно семафор sem_A инициализирован 1, а семафор sem_B инициализирован 0. Когда поток В попытается обратиться к общей переменной за данными для работы, он будет блокирован в ожидании результатов работы потока А. Поток А, подготовив необходимые данные, войдет в критическую секцию (поскольку его семафор разблокирован), установит новые данные и, покидая критическую секцию, разблокирует семафор потока В. После этого поток В будет разблокирован и сможет получить новые данные. Обратите внимание, что если данные производятся в цикле (а это обычная ситуация), то поток А не сможет повторно получить доступ к общей переменной до тех пор, пока поток В не закончит чтение этой переменной и не покинет критическую секцию.
ПримечаниеОписанная схема не является универсальной и хорошо работает для двух потоков. Однако возможна ситуация, когда существует множество потоков потребителей и производителей. В ОС QNX существует специальный примитив синхронизации, называемый «блокировкой чтения/записи» и предназначенный для синхронизации доступа в такой ситуации. Этот примитив предоставляет множественный доступ к критической секции кода со стороны «читателей», поскольку они не изменяют содержимого общих данных, и устанавливает эксклюзивный доступ для «писателей». Этот примитив будет подробнее рассмотрен позже.
• До сих пор мы фактически рассматривали работу семафора в бинарном режиме. Для большого количества задач именно такой режим семафора и является основным. Однако возможности счетного семафора, позволяющего контролировать количество обращений, допускают его применение в весьма специфических задачах, где другие средства синхронизации требуют от программиста дополнительной работы.
Проиллюстрируем работу счетного семафора. Предположим, нам надо синхронизировать работу двух потоков так, чтобы один из них всегда шел «вслед» за другим, то есть выполнял некие циклические операции только после их выполнения первым потоком. Для реализации этой схемы нам понадобится семафор, инициализированный нулевым значением.
Поток А Поток В
while (true) while (true)
{ {
/* работа A; */ /* sem_wait(&sem); */
sem_post(&sem); работа B;
} }
Поток А в каждом цикле увеличивает счетчик семафора на 1, а поток В в свою очередь стремится «выбрать слабину» и в каждом цикле уменьшает этот счетчик на единицу до тех пор, пока он не достигнет нуля. Вне зависимости от приоритетов, дисциплины диспетчеризации или любых источников блокировки потоков поток В будет «следовать» за потоком А и выполнять не больше циклов, чем его «ведущий» поток.
Всеми этими примерами мы хотели показать главную особенность семафора: любой поток может менять его состояние (внутренний счетчик), тем самым делая это элемент синхронизации идеальным средством управления порядком выполнения потоков. Семафор является идеальным инструментом для построения собственных средств планирования (диспетчеризации) выполнения потоков вашей системы. Стандарт POSIX предусматривает наличие специальных «именованных» семафоров, к которым может обращаться любой поток, принадлежащий любому процессу, выполняющемуся в системе, а в ОС QNX к семафорам может обращаться и любой поток любого процесса во всей сети QNX. Таким образом, семафор позволяет осуществлять планирование выполнения задач даже для вашей распределенной сетевой системы.
Ниже мы приводим краткое описание функций работы как с неименованными, так и с именованными семафорами, реализованными в ОС QNX. Функции работы с семафорами объявлены в заголовочном файле <semaphore.h>. Если для работы какой-либо функции необходимы дополнительные заголовочные файлы, они будут указываться явно.
Операции над семафорами
Создание семафора
QNX поддерживает два типа семафоров — неименованные и именованные. Разница между ними заключается в том, что к именованному семафору можно обратиться из любого процесса в системе (или даже по сети QNET с другого сетевого хоста), поскольку такой семафор имеет ассоциированное с ним имя в файловой системе QNX. Необходимо помнить, что именованные семафоры, при прочих равных условиях, медленнее и требуют для своей работы запущенного в системе менеджера очередей сообщений POSIX (mqueue).
Для каждого типа семафоров существует своя группа функций, применение которых не должно смешиваться.
