Независимо от того, какой набор элементов синхронизации окажется предпочтительным для разрабатываемой вами системы, важным является тот факт, что в случае, если предлагаемые системой средства синхронизации по каким-то причинам вас не устраивают, то ничто не мешает разработать собственные средства синхронизации, используя тот или иной базис или даже их комбинацию. И эффективность полученного нового средства синхронизации будет зависеть только от вас.
Мы постараемся проиллюстрировать эту идею примерами использования базовых средств синхронизации в качестве "конструктора" при построении более сложных. Три базовых элемента синхронизации ОС QNX - мьютекс, условная переменная и семафор - реализуются на уровне микроядра системы и создаются вызовом системной функции:
SyncTypeCreate(unsigned type, sync_t* sync, const struct _sync_attr_t* attr);
Здесь type может принимать значения:
_NTO_SYNC_MUTEX_FREE - для создания мьютекса;
_NTO_SYNC_SEM - для создания семафора;
_NTO_SYNC_COND - для создания условной переменной.
Стоит обратить внимание на два важных факта. Во-первых, типы мьютекса (pthread_mutex_t), условной переменной (pthread_cond_t) и семафора (sem_t) являются псевдонимами типа sync_t. А во-вторых, типы атрибутов этих объектов также являются псевдонимами одного-единственного типа - sync_attr_t, содержащего поле protocol, значение которого определяет, каким способом ОС будет варьировать приоритеты во избежание их инверсии.
В соответствии с документацией QNX 6.2.1 это поле присутствует у параметров всех трех базовых объектов синхронизации, но доступно оно только для переопределения мьютексов. По умолчанию (например, когда вместо attr передается NULL) поле protocol принимает значение PTHREAD_PRIO_INHERIT. Это означает, что ОС будет использовать протокол наследования приоритетов для предотвращения инверсии.
Таким образом, все примитивы синхронизации QNX в теории могут учитывать эффект инверсии приоритетов. Однако на практике важны следующие два вопроса: возможно ли в принципе возникновение ситуации инверсии приоритетов для данного типа примитивов, и если да, то актуально ли для данного типа примитивов препятствовать возникновению инверсии (в качестве иллюстрации этого утверждения можно рассмотреть примитив типа барьер).
Тесты [4] показывают, что только для мьютексов наследованием приоритетов (или альтернативными протоколами) однозначно предотвращается возникновение инверсии приоритетов. По-видимому, в первую очередь это связано с тем, что сама по себе инверсия может возникнуть именно в тех случаях, когда из всех элементов синхронизации необходимо использовать именно мьютекс или что-либо из его наследников (например, блокировки чтения-записи).
Семафор (счетный)
Семафор является весьма специфическим (в сравнении с прочими) для ОС QNX средством синхронизации, и хотя функции работы с ним также определяются стандартом POSIX, даже семантика этих функций отличается от всех прочих объектов синхронизации.
Примечание
Функции работы с семафором определяются стандартом POSIX 1003.1 (1993) расширения реального времени, а не стандартом POSIX 1003b (1995), которым определены pthread_* и все другие примитивы синхронизации; соответственно функции манипулирования семафорами не начинаются с префикса pthread_*.
В классической работе Дейкстры [10] семафор определяется как объект, над которым можно провести две атомарные операции: инкремент и декремент внутреннего счетчика - при условии, что внутренний счетчик не может принимать значение меньше нуля. Если некий поток пытается уменьшить на единицу значение внутреннего счетчика семафора, значение которого уже равно нулю, то этот поток блокируется до тех пор, пока внутренний счетчик семафора не примет значение, равное 1 или больше (посредством воздействия на него других потоков). Разблокированный поток сможет осуществить декремент нового значения.
Принято рассматривать семафоры двух видов: бинарные, счетчик которых может принимать только значения 0 либо 1, и счетные, или простые, счетчик которых может принимать большие положительные значения. В QNX 6.2.1 максимальное значение счетчика определяется переменной SEM_VALUE_MAX, значение которой равно 32 767.
Отметим важный момент: семафор является наиболее простым и соответственно наиболее универсальным средством синхронизации. И классические решения задач раздельного использования ресурсов, предложенные в теории первоначально Э. Дейкстрой, базируются именно на понятии семафора. Однако в случае систем реального времени применение семафоров для разделения доступа к ресурсу влечет потенциальную опасность возникновения инверсии приоритетов [4], избежать которой никак нельзя.
Причина этого в том, что семафор по определению не может знать своего владельца (захватившего его), поскольку у счетного семафора в принципе не может быть владельца, а бинарный семафор, который отличает своего владельца (поток, заблокировавший в данный момент другие потоки на обращении к семафору), уже перестает быть собственно семафором и называется мьютексом, или эксклюзивной блокировкой. По-видимому, именно этим обстоятельством вызван тот факт, что все объекты синхронизации QNX, не реализованные на уровне native API, но предоставляемые на уровне API POSIX, строятся без использования семафоров.
Принципиально схема работы семафора позволяет использовать его для решения максимально широкого круга задач. Приведем только несколько схематичных примеров:
• Ожидание условия (уведомление). Часто возникает необходимость остановить (заблокировать) поток до тех пор, пока не наступит некое событие (выполнится условие). Разблокировать остановленный поток в таком случае может только другой, активный к этому времени поток. Предварительно инициализируем семафор нулевым значением:
Поток А Поток В
while (!expression) expression = true;
sem_wait(&sem); sem_post(&sem);
В этом случае поток А ожидает выполнения некоего условия (операция sem_wait()), а поток В уведомляет (операция sem_post()) о выполнении условия любые ожидающие этого условия потоки.
Примечание
В принципе конструкция while() здесь не обязательна, можно обойтись и простым if(), но проверка выполнения условия и после разблокирования потока будет более строгой формой в многопоточной системе, особенно если выполнения условия ожидают более одного потока.
• Взаимное исключение. С помощью семафора можно решить и другую классическую проблему синхронизации - безопасное совместное исполнение кода. Эта проблема возникает, когда из нескольких потоков необходимо провести модификацию общих переменных или обратиться к одному системному ресурсу. В таком случае необходимо установить четкий порядок обращений, не допускающий одновременности исполнения соответствующего участка кода (взаимное исключение). Здесь семафор инициализируется единицей:
Поток А Поток В
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).
Для каждого типа семафоров существует своя группа функций, применение которых не должно смешиваться.
sem_init() и sem_destroy() - создание и разрушение неименованного семафора. При создании указывается параметр доступа из других потоков и начальное значение счетчика семафора. С неинициализированным семафором никаких операций проводить нельзя (это общее правило справедливо и для всех иных примитивов синхронизации). После разрушения семафора его необходимо повторно инициализировать для использования.
Обе функции возвращают 0 в случае успеха и -1 в случае ошибки. Код ошибки записывается в переменной errno. В частности, функция sem_init() может сигнализировать о следующих ошибках выполнения:
EAGAIN - в данный момент нет ресурсов для инициализации семафора;
EINVAL - начальное значение счетчика превышает SEM_VALUE_MAX;
EPERM - у процесса недостаточно привилегий для инициализации семафора;
ENOSPC - ресурсы, необходимые для инициализации, исчерпаны;
ENOSYS - функция sem_init() не поддерживается реализацией системы.
При вызове функции sem_destroy() может регистрироваться только одна ошибка:
EINVAL - неправильный описатель семафора.
sem_open() и sem_close() - открытие и закрытие именованного семафора (если отсутствует ранее созданный семафор с таким именем, то его создание). В вопросе подключения и отключения работа с именованным семафором аналогична работе с обычным файлом. Также для именованных семафоров существует операция sem_unlink(), аналогичная операции unlink() для обычного файла. В функцию sem_open() передается имя семафора, параметры открытия семафора и дополнительные параметры в случае создания семафора.