Синхронизация нужна в любой малтитредной программе. (Если, конечно, она не состоит из локлесс алгоритмов на 100%, что вряд ли). Будь то приложение или компонента ядра современной операционной системы.
Меня всё нижесказанное, конечно, больше волнует с точки зрения разработки ядра ОС. Но почти всё применимо и к пользовательскому коду.
Кстати, ядра старых ОС в примитивах синхронизации не нуждались, поскольку преемптивной мультизадачности внутри ядра в старые добрые времена не было. (Уж за Юникс 7-й версии я отвечаю. Не было.) Точнее, единственным методом синхронизации был запрет прерываний. Но об этом позже.
Сначала перечислим героев. Мне известны следующие примитивы синхронизации:
User/kernel mode: mutex+cond, sema, enter/leave critical section.
Kernel only: spinlock, управление прерываниями.
Зачем всё это нужно, читатель, наверное, знает, но всё же уточним.
Если некоторая структура данных может быть доступна двум параллельно работающим нитям (или нити и прерыванию), и являет собой сущность, к которой нельзя обеспечить атомарный доступ, то работу с такой структурой нужно производить так, чтобы только одна нить одновременно выполняла сложные манипуляции состоянием структуры.
Простой пример. Список.
struct list { 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);
Теперь хорошо. (Ну, не очень хорошо, если у нас более ста процессоров и участок кода у них популярен, но это совсем отдельный разговор.)
Что происходит? Нить А делает вызов mutex_lock для мьютекса list->mutex. Который, очевидно, принадлежит списку, который мы хотим поменять, и защищает доступ именно к нему. Он не заперт, нить А запирает мьютекс (теперь он знает, что заперт, и знает, кто его запер) и продолжает работу. Если теперь нить Б попробует войти в тот же регион кода (или другой, защищённый тем же мьютексом — например, в функции удаления элемента списка), то второй раз запереть запертый мьютекс не получится. Нить Б будет ждать, пока нить А не вызовет mutex_unlock.
Кстати, если мы с вами — ядерные разработчики, то важно понимать ещё одно, неинтересное для прикладного программиста свойство мьютекса (как и всех «тяжеловесных» примитивов синхронизации) — если мы пытаемся запереть мьютекс, который уже заперт другой нитью, мы не просто ждём — нашу нить «снимут с процессора», произойдёт переключение контекста. Это ценно, потому что позволяет куда более эффективно загружать процессор, но есть и проблемы. Внутри обработчика прерываний
Это вполне решает задачу, если надо поработать со сложной структурой данных. Но есть и другие задачи. Например, проинформировать другую нить о событии, которое та, другая нить, ждёт.
Рассмотрим функции alloc_mem и free_mem:
// NB! Заведомо неверный код!
alloc_mem()
{
while(total_free_mem <= 0)
{
wait_cond(&got_free_mem);
}
// actually allocate
}
free_mem()
{
// actually free mem
total_free_mem++;
signal_cond(&got_free_mem);
}
Что здесь происходит? Всё банально. В функции аллокации памяти мы смотрим на глобальный счётчик свободной памяти. Если пусто, свободной памяти нет, ждём пока кто-то не освободит память — вызываем wait_cond, который нас приостанавливает, пока кто-то не просигналит — готово, память освободили.
Это, конечно, функция free_mem() — она возвращает память в кучу, увеличивает счётчик свободной памяти и вызывает signal_cond — сообщает страждущим, что память есть. Тот, кто спал внутри wait_cond, «проснётся» после такого сигнала, проверит что да, память есть, и выделит её. Всё верно?
Ну, нет, конечно. Если функцию alloc_mem вызовут две нити сразу, то будет беда — одна из них получит сигнал первой, проснётся, убедится, что свободная память есть, и тут вдруг шедулер возьми да сними её с процессора. И дай проснуться второй такой же нити. Вторая нить проснётся, тоже увидит, что память есть, заберёт её и закончится. Просыпается мафия первая нить, и у неё всё плохо. Только что она проверила переменную free_mem, убедилась, что всё есть, и вот — никакой свободной памяти в пуле не находится. Беда.
Для данного случая беда не смертельная — можно просто вернуться к началу функции и снова ждать у моря погоды. Хотя, конечно, и это плохо — мы теряем процессорное время на пустые метания.
Но, вроде бы, мы же знаем ответ? Добавим mutex!
// NB! Снова заведомо неверный код!
alloc_mem()
{
mutex_lock( &allocator_mutex );
while(total_free_mem <= 0)
{
wait_cond(&got_free_mem);
}
// actually allocate
mutex_unlock( &allocator_mutex );
}
free_mem()
{
mutex_lock( &allocator_mutex );
// actually free mem
total_free_mem++;
signal_cond(&got_free_mem);
mutex_unlock( &allocator_mutex );
}
Так хорошо? Нет. Освобождение памяти не случится — функция alloc_mem() его заперла, заснула на ожидании cond, и никто больше в мьютекс войти не может, и никто не освободит память, и не просигналит.
Беда. Но ладно же, мы знаем, что делать! Перед тем, как заснуть на ожидании cond, мы отопрём mutex, и позволим другим войти в free и вернуть нам память. Вот так:
// NB! И опять заведомо неверный код!
alloc_mem()
{
mutex_lock( &allocator_mutex );
while(total_free_mem <= 0)
{
mutex_unlock( &allocator_mutex );
wait_cond(&got_free_mem);
mutex_lock( &allocator_mutex );
}
// actually allocate
mutex_unlock( &allocator_mutex );
}
По комментарию вы уже видите, что опять не слава богу. Что теперь? А теперь есть щёлочка, тонкая линия между моментом, когда мы проснулись и вышли из функции wait_cond, получив от free_mem сигнал об освобождении памяти, и захватом мьютекса. В этот момент мьютекс не взят, и другие нити опять могут нас опередить и набезобразить. Именно по этой причине функция wait_cond выглядит несколько иначе:
wait_cond( cond *c, mutex *m );
Работает это вот как: функция принимает на вход conditional variable, которая передаст нам сигнал «проснуться», и запертый мьютекс:
// NB! И опять заведомо неверный код!
alloc_mem()
{
mutex_lock( &allocator_mutex );
while(total_free_mem <= 0)
{
wait_cond(&got_free_mem,&allocator_mutex);
}
// actually allocate
mutex_unlock( &allocator_mutex );
}
Функция wait_cond отопрёт мьютекс, во-первых, самостоятельно, а во-вторых сделает это атомарно по отношению к переходу в спящее состояние. То есть нить, входящая в wait_cond сначала заснёт, а потом, не прерывая сна, отопрёт мьютекс. И наоборот, просыпаясь, она сначала захватит мьютекс, а потом проснётся и продолжит работу. (Это требует от кода переключения нитей изрядной хитрости, постараюсь рассказать об этом в одной из следующих заметок.)
Только такая семантика обеспечивает 100% консистентность и отсутствие «гонок» — race conditions.
Отметим, что код функции free у нас получился вполне правильный:
free_mem()
{
mutex_lock( &allocator_mutex );
// actually free mem
total_free_mem++;
signal_cond(&got_free_mem); // 4
mutex_unlock( &allocator_mutex ); // 5
}
Только с учётом вышесказанного надо понимать, что хотя формально мы пробуждаем аллокатор на строке 4, реально проснётся он после исполнения строки 5, потому что до этого момента он не в состоянии захватить мьютекс.
К сказанному, наверное, имеет смысл добавить, что реальная функция signal_cond пробуждает не все ожидающие потоки, а только один (обычно — с наивысшим приоритетом), так что ситуация в приведённом примере несколько проще и сложнее одновременно. Проще потому что уже внутри сигнализации встроен механизм, который после одного free пробудит только один alloc, а сложнее потому, что реально это ничего не решает — мы не знаем, подойдёт ли данному alloc-у освобождённый участок, так что надо вместо signal_cond применить broadcast_cond, который таки пробудит всех страждущих, дав им возможность в честной драке определиться, кому достанется ресурс.
Посмотреть на фактическую реализацию этих примитивов можно здесь:
В следующей серии — sema семафор, который в одиночку заменяет и mutex, и cond. Практически без ансамбля.
Автор: dzavalishin
