Многопоточное программирование возвращается

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

Читал ли ты мою предыдущую статью «Ох уж это многопоточное программирование»? Если да, то ты можешь со спокойной душой читать мою статью. Если же нет, то рекомендую сначала прочитать ту предыдущую статью, и уже потом приниматься за этот «десерт».

Ещё кое‑что о синхронизации потоков

Семафоры и их теория

Как я писал ранее, для синхронизации потоков в Win32 API (и не только) предназначено много всяких интересных технологий: критические секции, мьютексы и так далее. Среди этих штук есть технология семафоров.

Семафор представляет собой счётчик, используемый несколькими потоками для синхронизации. По умолчанию он может быть равен 0 или какому‑нибудь положительному (но только не отрицательному!) числу.

Для работы с семафорами нужны 2 функции: down и up. Первая функция проверяет, равен ли семафор 0. Если нет, то функция уменьшает значение семафора на 1 и поток продолжает работу. Если же да, то поток приостанавливается и начинает терпеливо ждать, пока значение семафора не увеличится и ему не выпадет счастливый шанс продолжить своё выполнение, завершив работу функции down. Функция up вне зависимости от значения семафора увеличивает его на 1. Если с этим семафором связаны один или несколько ожидающих потоков, то по определённому алгоритму выбирается один из таких потоков, а дальше этому потоку предоставляется уникальный шанс продолжить свою работу. В этом случае значение семафора как было, так и останется равно 0, но зато кол‑во ожидающих потоков уменьшится на 1.

typedef volatile int semaphore; // Объявляем о таком новом типе переменных, как семафоры

void down(semaphore *s){
  if(*s == 0){ // Семафор равен 0?
    lock(); // Если да, то заблокироваться
  }	
  *s--; // Уменьшить значение семафора на 1
}

void up(semaphore *s){
  unlock(); // Разблокировать один из потоков (например, случайным образом или по алгоритму FIFO)
  *s++; // Увеличить значение семафора на 1
}

Нужно отметить, что все операции с объектами синхронизации (вход и выход для критических секций, блокировка и разблокировка для мьютексов, up и down для семафоров и так далее) должны выполняться атомарно (неделимо). Т. е. если мы, например, увеличиваем семафор на 1 и тем самым освобождаем один из потоков от долгого и мучительного ожидания через какой‑либо API, то этот самый API гарантирует нам то, что выполнение нашего потока не будет прервано между операциями увеличения семафора и освобождения одного из потоков. Если такие операции не будут выполняться атомарно (неделимо), то вся синхронизация потеряет смысл.

Семафоры и их реализация в Win32 API

С семафорами в Win32 API особо заморачиваться не надо. Вот 2 функции для управления ими:

HANDLE CreateSemaphore (LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCSTR lpName);
WINBOOL ReleaseSemaphore (HANDLE hSemaphore, LONG lReleaseCount, LPLONG lpPreviousCount);

В 1-й функции lpSemaphoreAttributes — указатель на структуру атрибутов безопасности, lInitialCount — значение, которое присваивается семафору в самом начале его «жизни», lMaximumCount — максимальное значение для семафора (оно обязательно должно быть больше 0!), а lpName позволяет сделать семафор именованным — так же, как и в случае с мьютексами. Если в этом параметре для имени указать NULL, то семафор будет безымянным.

2-я функция позволяет увеличить значение семафора (аналог нашей псевдофункции up в предыдущем примере). hSemaphore — это, конечно же, дескриптор семафора. Заметь, что в этой функции можно увеличить значение семафора не только на 1, но и на 2, на 3 и так далее. Таким образом можно освободить сразу несколько потоков, но при этом не стоит забывать про максимальное значение семафора (ещё не забыл про параметр lMaximumCount?). Значение увеличения настраивается параметром lReleaseCount. lpPreviousCount является указателем на переменную, в которую будет помещено предыдущее значение семафора. Но, возможно, для тебя это будет пока лишним — можешь указать NULL.

Выполнить нашу псевдофункцию down в «оригинальной обёртке от Microsoft» можно, опять‑таки, через уже знакомую нам функцию WaitForSingleObject. Вот же выскочка эта функция! Везде она нам себя предлагает!

Чтобы уменьшить значение семафора на 1 (и, возможно, подождать до «лучших времён»), надо просто вызвать эту функцию, передав ей дескриптор семафора в качестве 1-ого параметра. Готово.

События, их теория и реализация в Win32 API

События используются для доставки потокам какого‑либо сообщения, например «У нашей компании резко выросли доходы — обновить базу данных!» или «Один рабочий поток жёстко завис и не отвечает — свистать всех наверх!». События бывают 2-х типов: с ручным и автоматическим сбросом.

Чтобы работать с событиями, в Win32 API есть следующие функции:

HANDLE CreateEvent (LPSECURITY_ATTRIBUTES lpEventAttributes, WINBOOL bManualReset, WINBOOL bInitialState, LPCSTR lpName)
WINBOOL SetEvent (HANDLE hEvent)
WINBOOL ResetEvent (HANDLE hEvent)
WINBOOL PulseEvent (HANDLE hEvent)

В 1-й функции lpEventAttributes — атрибуты безопасности для события, bManualReset определяет тип сброса события, а lpName позволяет сделать событие именованным (или безымянным, если указан NULL). bInitialState мы рассмотрим ниже.

Примечание: все имена объектов синхронизации в Win32 API вносятся в единый «реестр» имён, так что не пытайся создать мьютекс «Объект синхронизации» и семафор «Объект синхронизации».

Вот пример использования событий. Представь себе многопоточную систему, управляющую сервером Хабра. Через функцию CreateEvent создаётся событие NewArticle. Оно сообщает о том, что к какому‑либо автору на Хабре пришла муза, и он написал гениальную статью, а затем ещё и отправил её на сервер Хабра для того, чтобы эту гениальную статью могли прочитать все‑все‑все. Но пока никаких новых статей нет. Потоки‑рабочие вызывают функцию WaitForSingleObject с дескриптором NewArticle, выстраиваются в очередь и начинают ждать, пока на сервер не отправится новая статья. Как только на сервере появится новая статья, готовая к публикации, поток‑хозяин (или ещё кто‑нибудь) вызывает функцию SetEvent (а потом — ResetEvent) для того, чтобы перевести событие в сигнальное состояние и освободить сразу все рабочие потоки либо функцию PulseEvent для того, чтобы вызвать сразу последовательность функций SetEvent и ResetEvent. Если NewArticle является событием с автосбросом, то после вызова функции SetEvent вызывать функцию ResetEvent не надо — событие в любом случае возобновит работу лишь 1-ого потока. Значение bInitialState в функции CreateEvent позволяет создать событие сразу в сигнальном состоянии.

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

Мьютексы в библиотеке Pthreads

В POSIX‑совместимой библиотеке Pthreads тоже есть мьютексы. Вот все функции для работы с ними:

int pthread_mutex_lock(pthread_mutex_t *m)
int pthread_mutex_timedlock(pthread_mutex_t *m, const struct timespec *ts)
int pthread_mutex_unlock(pthread_mutex_t *m)
int pthread_mutex_trylock(pthread_mutex_t *m)
int pthread_mutex_init(pthread_mutex_t *m, const pthread_mutexattr_t *a)
int pthread_mutex_destroy(pthread_mutex_t *m)

1-я функция позволяет заблокировать мьютекс, 2-я может заблокировать мьютекс с ограничением по времени (то есть если мьютекс свободен, поток сразу захватывает его, если мьютекс захвачен, поток блокируется только на определённый промежуток времени), 3-я — разблокировать мьютекс, 4-я — попробовать заблокировать мьютекс, 5-я — создать мьютекс и 6-я — уничтожить его. Во всех функциях параметр m является указателем на переменную типа pthread_mutex_t.

Последствия синхронизации

Даже очень умно продуманная синхронизация для потоков может преподнести нежданные «подарочки». Представь себе 2 потока. Они хотят получить доступ к компакт‑диску и принтеру, используя мьютексы для синхронизации. 1-й поток действует по своему порядку захвата компакт‑диска и принтера, а 2-й — по своему. Ниже приведён их код на C++ с использованием Win32 API:

DWORD WINAPI FirstThread (LPVOID){
  WaitForSingleObject(CD, INFINITE);
  WaitForSingleObject(Printer, INFINITE);
  UseCD();
  UsePrinter();
  ReleaseMutex(Printer);
  ReleaseMutex(CD);
}

DWORD WINAPI SecondThread (LPVOID){
  WaitForSingleObject(Printer, INFINITE);
  WaitForSingleObject(CD, INFINITE);
  UseCD();
  UsePrinter();
  ReleaseMutex(CD);
  ReleaseMutex(Printer);
}

Предположим, что 1-й поток может завладеть компакт‑диском (и делает это), но у него заканчивается квант времени и управление передаётся 2-му потоку. 2-й поток захватывает принтер и тоже передаёт управление 1-му потоку. Теперь 1-й поток пытается получить доступ к принтеру, но блокируется из‑за того, что он уже принадлежит 2-му потоку, а 2-й поток пытается получить доступ к компакт‑диску, но тоже блокируется — компакт‑диск уже принадлежит 1-му потоку. Теперь потоки будут заблокированы навсегда. Эта ситуация называется взаимоблокировкой, её схема показана ниже.

Схема взаимоблокировки

Как видишь, стрелки на схеме взаимоблокировки (или, по‑научному, на графе ресурсов) образуют цикл в виде знака бесконечности. Соответственно, потоки будут ждать по‑настоящему бесконечно.

«Взаимоблокировка в группе процессов возникает в том случае, если каждый процесс из этой группы ожидает события, наступление которого зависит исключительно от другого процесса из этой же группы» — пишет Э. Таненбаум в своей книге «Современные операционные системы». В нашем случае вместо процессов — потоки, но суть дела это не меняет.

В состояние взаимоблокировки могут попасть сколько угодно потоков и ресурсов, причём каких угодно ресурсов — семафоров, мьютексов, критических секций, событий и так далее. Главное, чтобы ресурс являлся синхронизированным через ожидание. Взаимоблокировки — отдельная «отрасль» многопоточного программирования, про которую много чего написано.

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

Заключение

Мы подходим к логическому концу статьи. С какими только технологиями мы не знакомились! Критические секции, семафоры, мьютексы, события, Pthreads — всё это мы уже осмотрели. Я надеюсь, ты усвоил весь материал по многопоточному программированию и готов использовать его на практике. Но, конечно, писать и проектировать многопоточные программы достаточно непросто. Так что если есть возможность написать однопоточную программу вместо многопоточной, то лучше всё‑таки писать однопоточную.

Ой, а ведь кроме потоков, есть ещё и нити…

Всё, хватит. Больше не надо.