Обзор примитивов синхронизации — Семафор и немного lockless-а

В прошлой заметке ^[1] мы обсудили самую известную пару из лагеря инструментов синхронизации тредов — mutex и cond. Сегодня встретимся с sema — примитивом, который умеет заменять предыдущие два в одиночку.

Но сначала — пара слов о случайных пробуждениях. (Спасибо xaizek ^[2], который мне об этом напомнил.) В принципе, строго реализованные механизмы синхронизации этим не страдают, но, тем не менее, опытный программист на это никогда не полагается.

Напомню фрагмент кода:

while(total_free_mem <= 0)
    {
    wait_cond(&got_free_mem, &allocator_mutex);
    }

Здесь цикл вокруг wait_cond гарантирует нам, что даже если мы вернёмся из ожидания события случайно или по ошибке, ничего страшного не случится — проверка в while обеспечит нам уверенность, что нужное состояние проверяемого объекта достигнуто. Если нет — поспим ещё в ожидании.

Отметим ещё раз, что проверяем мы состояние объекта (total_free_mem <= 0) при запертом мьютексе, то есть никто не может его менять в то же самое время.

Желательно также не забыть, что переменные, через которые мы обмениваемся данными между нитями, должны быть помечены как volatile, иначе компилятор запросто построит нам такую оптимизацию, которая легко сломает логику работы кода.

Ещё совсем уж вскользь упомяну, что реализация SMP в процессорах Интел совершенно всепрощающа и гарантирует программисту, что все процессоры видят память одинаково, хотя и имеют раздельные кеши. То есть обеспечивают так называемую когерентность кешей процессоров в многопроцессорной системе.

Это не везде так. Есть процессоры, в которых надо предпринимать специальные усилия для того, чтобы данные гарантированно были синхронизированы между процессорами. Или явно выключать кеширование для страниц памяти, в которых лежат данные, доступные нескольким процессорам. Это уже тема для совершенно отдельного разговора, здесь я лишь упомянул для полноты.

Хорошо. Вернёмся же к семафорам.

Для семафора, по сути, определены всего две операции:

    sem_acquire( &sema )
    sem_release( &sema )

Работают они очень просто. У каждого семафора есть целочисленное значение.

Операция acquire блокируется, если значение меньше или равно нулю (семафор заперт), и, по окончании блокировки (или сразу, если значение больше нуля), уменьшает значение семафора на 1.

Операция release увеличивет значение семафора на 1 и пробуждает нить, заснувшую в acquire, если таковая есть.

Семафор можно использовать и как mutex, и как cond (но не одновременно).

В самом деле, вот мьютекс:

    // начальное значение семафора = 1
    sem_acquire( &sema );
    // работаем с данными
    sem_release( &sema );

Первая нить, выполнив acquire, не заснёт (значение было больше нуля), но уменьшит значение на 1. Если до выполнения release кто-то ещё попытается сделать acquire, он заснёт, потому что значение теперь нулевое.

А вот и cond:

// Начальное значение семафора = 0
get_byte() 
{

    acquire(&got_data);

    ret = buf[read_pos++];
    read_pos %= sizeof(buf);

}

put_byte(b) 
{
    buf[put_pos++] = b;
    release(&got_data);
}

Что мы тут видим? Попытка вынуть байт из буфера заставит нас заснуть на acquire, если никто байт в буфер пока ещё не положил. А вот если байт положили — мы проснёмся и продолжим, пойдём забирать байт.

Такой код не сработал бы, будь вместо семафора cond. Рассмотрим сценарий: сначала нить А вызывает put_byte, потом нить B вызывает get_byte. Будь вместо семафора cond, попытка сделать get_byte ничем не кончилась бы — мы бы заснули на ожидании cond, потому что в момент вызова signal_cond мы этот cond не ждали, а значит put_byte никого не разбудил. А заснули мы позже побудки.

С семафором же всё хорошо, у него есть состояние, и семафор можно «открыть про запас» — ещё до того, как кто-то попытался его закрыть. То есть — release до acquire тоже можно!

Это замечательно, так как реально упрощает логику.

Но код выше всё равно неверен. Если после двух put_byte одновременно случатся get_byte, они «поссорятся» в точке работы с read_pos — может произойти неприятность: две нити сначала сделают инкремент пойнтера, а потом обе заберут один и тот же байт.

Не дело. Выходит, нужно «накрыть» зоны работы с буфером обычным mutex-ом или семафором «в режиме» мьютекса? Тогда в чём преимущество семафора перед обычным cond-ом?

Оно есть.

Во-первых, есть ситуации, когда одна из сторон гарантированно работает синхронно, из одной нити. Тогда для этой стороны не нужен мьютекс. Так часто бывает в драйвере — буфер драйвера наполняется (или, для обратного направления, опорожняется) из обработчика прерывания или единственной нити драйвера, и для этой части блокировка от одновременного доступа к буферу не нужна.

Во-вторых, применим лё-ёгенький lockless алгоритм:

    rpos = atomic-add( &read_pos, 1 );
    ret = buf[rpos];
    read_pos %= sizeof(buf);

Здесь atomic_add атомарно выполняет rpos = read_pos++. Это гарантирует нам, что для двух нитей параллельное исполнение пройдёт правильно — каждая получит свой байт, хотя и неизвестно, в какой очерёдности.

О семафорах на этом, пожалуй, всё.

Но ещё пара слов об инверсии приоритетов. Эта штука характерна и критична для ОС реального времени, но поскольку приоритеты реального времени сегодня есть почти везде, про неё нужно знать, пожалуй, всем.

Существует старая как мир проблема deadlock-а в теоретически верной программе из-за приоритетов нитей.

Предположим, у нас есть нити А, Б и В, приоритеты которых, соответственно, 3, 2 и 1, то есть у А — наивысший. Все приоритеты — класса реального времени, то есть если А есть что делать, то она получает процессор безусловно, а Б и В ждут.

А и В работают с общим ресурсом — например, низкоприоритетная В — это логгер, который забирает у А поток сообщений в лог и пишет их в сеть или в файл. Работа некритичная, поэтому В имеет низкий приоритет. Нить Б занимается чем-то менее важным, чем А, но длительным. А управляет ядерным реактором, и должна раз в 1 мсек проверить мощность и подрегулировать стержни.

В нормальной жизни А крутится в цикле — спит до окончания слота в 1 мсек, потом снимает показания и рулит стержнями. Б считает ворон нейтроны, и на следующие 5-6 сек у неё работа есть. Соответственно, нити В процессора вообще не перепадает. Б и А важнее.

Рано или поздно буфер переполняется, и А останавливается, ожидая семафора, чтобы положить байтик в буфер.

Останавливается навсегда или, как минимум, на 5-6 секунд — В не получит процессора, пока Б не досчитает. В итоге нить А пропустит свой таймслот и реактор останется без контроля.

Чтобы такого не происходило, в realtime OS все примитивы синхронизации автоматически поднимают приоритет процессу, которого ждут, до максимального уровня приоритета среди всех ожидающих нитей.

То есть, в нашем примере, В получит приоритет А и снесёт с процессора докучливого Б, чтобы А не ждал лишку.

Конечно, пример тенденциозен, но, надеюсь, суть он отразил.

В следующий раз рассмотрим спинлоки. В комментах уже пишут, что лето — это маленькая жизнь спинлок — это мелкий мьютекс, что не лишено оснований.

Но, как говорится, есть нюансы. :)

Автор: dzavalishin

Источник ^[3]