Синхронизация нужна в любой малтитредной программе. (Если, конечно, она не состоит из локлесс алгоритмов на 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, которая передаст нам сигнал «проснуться», и запертый мьютекс:

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, который таки пробудит всех страждущих, дав им возможность в честной драке определиться, кому достанется ресурс.

Посмотреть на фактическую реализацию этих примитивов можно здесь:

mutex.c, cond.c

В следующей серии — sema семафор, который в одиночку заменяет и mutex, и cond. Практически без ансамбля.

Это серия статей «Обзор примитивов синхронизации»:

• mutex и cond
• Семафор и немного lockless-а
• спинлоки и тайны ядра процессора