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

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

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

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

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

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

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

    Комментарии 18

      +1
      read_pos %= sizeof(buf);
      этот кусочек тоже должен быть атомарным, правильнее делать
      rpos %= sizeof(buf);
        0
        Спасибо. Всё ещё хуже. Вот что значит накидать пример навскидку. Атомарной должна быть операция считывание-инкремент-ограничение.
          0
          Я написал врезку про эту проблему. Ещё раз спасибо!
          +5
          О чем статья? Мне интересно программирование, особенно микроконтроллеров. До ката не понятно, чего и на чем, и под какую ОС писать будем. Ок. Перехожу на статью. И опять изложение какого-то материала по теме абстрактного программирования. Вижу ссылку на предыдущую статью, теперь-то уж наверняка станет понятно что и для чего! Перехожу… опять кирпич. Тут уж читать текст непонятной направленности у меня терпения не хватило.
          Уважаемы Дмитрий, вы чего пишете-то? Судя по тексту вы хороша разбираетесь в теме, но вот в какой теме?
          На мой консервативный взгляд, в любой статье должно быть введение, где кратко выполняется постановка задачи. По традиции Хабра это введение размещается до ката. Прочитал его и становится ясно, стоит ли читать дальше.
            +1
            Базовые примитивы в любой ОС, как правило, соответствуют трём перечисленным. Для чего именно они нужны и каковы основные механизмы применения — показано в примерах. Возможно, Вам пока не встретилась задача, которая требует синхронизации. Встретится — возвращайтесь.
              –1
              Виноват. Не разобрался. Глупые вопросы задаю. Спасибо, что карму понизили.
              Справедливо урезонили дерзость зарвавшегося юнца. (с)
            0
            Вот пример для микроконтроллера. Это туннель TCP/IP-RS485 для atmega128 под EtherNut NutOs, там мьютексы используются для синхронизации работы механизма управление полудуплексом.
          0
          Семафоры, спины… о каких процессорах идет речь? Мне подобное встречалось только в VME — циклы Read-Modify-Write, ловушки на на указанный диапазон адресов, спины — но все это было аппаратное. На какое железо рассчитана эта статья, какая архитектура?
            0
            Они могут быть реализованы не только апаратно а и вполне софтово. И реализация есть почти в любой OC.
            0
            Спасибо за труды. Написано легко, компактно и на русском, потому читаю хоть и знал. Пожелания — в тексте предполагается многопроцессорная машина, а описанные примитивы вовсю применяются на однопроцессорных системах с разделением времени. Как обстоят в этом случае дела, раскройте тему.
              +1
              Желательно также не забыть, что переменные, через которые мы обмениваемся данными между нитями, должны быть помечены как volatile, иначе компилятор запросто построит нам такую оптимизацию, которая легко сломает логику работы кода.
              Лишнее. Кэширование переменной не может пересекать барьер, которым является мьютекс, а если реализация вызываемой функции для компилятора непрозрачна, он не имеет права делать кэширование из-за возможности алиасинга.

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

              Правда, останутся проблемы с read_pos %= sizeof(buf); — строго говоря, эту операцию нужно делать атомарно «внутри» atomic_add. То есть должна быть полная атомарная операция считывание-инкремент-ограничение.
              Можно так:
              do
              {
                  rpos = atomic_read(&read_pos);
              } while (rpos != atomic_cmpxchg(&read_pos, rpos, (rpos + 1) % sizeof(buf));
              ret = buf[rpos];
              
                0
                Про volatile — Вы предполагаете, что логика использования переменной обязательно пересекается с вызовами примитивов синхронизации, что необязательно. Правы Вы в том, что не всегда обязательно и помечать переменные как volatile, но статья-то вводная, лучше перебдеть.

                Насчёт процессоров и памяти — да, я выдал Интелу избыточный кредит, Вы правы. Вероятно, меня сбил с толку тот факт, что типичная реализация спинлока для Интела является барьером, поэтому целостность появляется автоматически при использовании любого примитива синхронизации.
              0
              Вы предполагаете, что логика использования переменной обязательно пересекается с вызовами примитивов синхронизации, что необязательно.
              Можете привести пример? По мне, если без volatile не работает, это баг, который через перебдение предлагается замести под ковёр.
                0
                (Вообще признаю, что мне пришлось задуматься. Но:)

                Кусок данных, который читает железка на другой стороне. С ней нельзя договориться о синхронизации. Нужно выставить данные в нужном порядке и гарантировать, что до того, как будет выставлен бит "данные готовы" они будут действительно готовы. То есть — явно запретить реордер записи в память.

                (Там ещё и кеш надо явно сбрасывать, или через некешируемое окно работать.)

                Но в изрядной степени я Ваше возражение приму. В целом lock — поработали — unlock при том, что lock-unlock являются fence-ами — вполне типичная картина.
                  0
                  Ещё один, менее очевидный и не связанный с железом вариант: ресурс с доступом по схеме RCU. Реализация rcu_dereference(p) должна обращаться к p как к volatile, чтобы компилятор не мог повторно обратиться к p (вместо lp) в следующем примере:

                  T *p;
                  
                  rcu_read_lock();
                  T *lp = rcu_dereference(p);
                  <use lp>
                  <use lp again>
                  rcu_read_unlock();

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое