Pull to refresh

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

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

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

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

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

Код и ещё кое-чем неверен
В этом примере кода отсутствует проверка на переполнение буфера. Её можно тоже сделать через семафор, но «в обратном включении» — release в get_byte, acquire — в put_byte, а начальное значение равно размеру буфера.


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

Оно есть.

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

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

    rpos = atomic_add( &read_pos, 1 );
    ret = buf[rpos];
    read_pos %= sizeof(buf);


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

Правда, останутся проблемы с read_pos %= sizeof(buf); — строго говоря, эту операцию нужно делать атомарно «внутри» atomic_add. То есть должна быть полная атомарная операция считывание-инкремент-ограничение.

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

Как можно исправить проблему? И, для начала, в чём она? Потенциальная ошибочная последовательность для нитей А и Б:

  • Стартовое значение read_pos = sizeof(buf)-1;
  • А: считывание и инкремент
  • Б: считывание и инкремент, при этом считанное значение = sizeof(buf), то есть выходит за границу массива.


Дальше последовательно сработают два read_pos %= sizeof(buf);, но уже поздно.

Здесь нам повезло. Достаточно простой корректировки:

rpos = atomic_add( &read_pos, 1 ) % sizeof(buf);


Кроме того, операция read_pos %= sizeof(buf);, как справедливо отметил degs, тоже должна быть атомарной, что малореально — gcc не предлагает такой операции среди встроенных атомарных функций (здесь).

Однако, эту операцию можно просто исключить, если размер массива кратен степени двойки. Коль скоро мы ограничиваем размером массива считанное в atomic_add значение, сам read_pos можно уже не трогать — пусть растёт и оборачивается через 0xFFFFFFFF в ноль, остаток от его деления на размер массива всегда будет верным.

(Для полного взрыва мозга добавлю, что всё будет работать и для некратных размеров, если работа с адресом считывания и адресом записи организована идентично. Просто в момент переполнения счётчика код не задействует часть буфера. )


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

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

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

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

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

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

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

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

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

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

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

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

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

Это серия статей «Обзор примитивов синхронизации»:
Tags: semaphoresynchronizationdriversфантомфантомосфантом ос
Hubs: Programming System Programming Programming microcontrollers
Total votes 28: ↑27 and ↓1 +26
Comments 18
Comments Comments 18

Popular right now

Top of the last 24 hours