Обзор примитивов синхронизации — спинлоки и тайны ядра процессора

Последняя статья про классические примитивы синхронизации.

(Наверное, потом напишу ещё одну про совсем уже нетипичную задачу, но это потом.)

Сегодня мы немножко заглянем в процессор. Чуть-чуть.

По сути, мы будем говорить про единственный примитив, который принципиально отличается от остальных: спинлок. Spinlock.

В комментариях к предыдущим заметкам возникла дискуссия — насколько справедливо вообще выделять спинлок как примитив, ведь по сути он — просто мьютекс, верно? Он выполняет ту же функцию — запрещает одновременное исполнение фрагмента кода несколькими параллельными нитями.

На уровне процесса всё так и есть — различия между спинлоком и мьютексом — чисто технические, вопрос реализации и производительности.

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

Дело в том, что внутри ядра мьютекс реализован с помощью спинлоков, а вот спинлоки реализованы сами по себе, автономно. Они — действительно базовый примитив. Ниже — только сам процессор.

Есть и ещё одно, семантическое различие. Мьютекс допускает и предполагает снятие нити с процессора, долгую остановку вызывающей нити. Мьютексом можно запереть объект на час или сутки, это приемлемо и нормально. Спинлок принципиально рассчитан только на кратчайшие приостановки, это всегда работа с неатомарным стейтом объекта. Присваивание группы переменных, небольшой цикл — это максимум того, что можно сделать под спинлоком.

Итак, иерархия реализации такова: mutex/cond/sema сделаны на базе спинлоков, спинлоки — на базе атомарных операций, предоставляемых процессором. Мы в них немного заглянем сегодня.

Как устроен спинлок?

Принцип невероятно прост. Спинлок — это просто переменная, которая содержит ноль или единицу (бывают варианты).

Если ноль — спинлок свободен, и его можно захватить. Если не ноль — спинлок заперт, и нить, которая желает его захватить, будет ждать, крутясь (spin — вращение) в небольшом цикле непрерывной проверки освобождения спинлока. Вот, собственно, реализация:

    while( !  _spin_try_lock( &(sl->lock)  ) )
        while( sl->lock )
            ;

Операция _spin_try_lock — атомарная, реализована на ассемблере соответствующего процессора. Пытаемся запереть спинлок, если не удалось — крутимся в цикле, пока он заперт, потом снова пытаемся.

Вот и всё, в целом.

Теперь детали. Операция _spin_try_lock тоже очень проста:

#define        _spin_try_lock(p)\
        (!({  register int _r__; \
            __asm__ volatile("movl $1, %0; \n\
                          xchgl %0, %1" \
                        : "=&r" (_r__), "=m" (*(p)) ); \
            _r__; }))

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

Что происходит? Мы меняем местами значение sl->lock и регистр, в котором лежит единица. Если спинлок не был заперт (sl->lock был равен нулю), он станет равен единице и _spin_try_lock вернёт ноль — мы успешно заперли спинлок. Если sl->lock был равен единице, то в итоге sl->lock после обмена опять будет равен единице, но и результатом _spin_try_lock будет считанное предыдущее значение sl->lock — единица, что означает неуспех захвата спинлока.

Вообще проблема с атомарными операциями на уровне процессора очень велика. Пока в системе один процессор, этой проблемы нет. Но и ситуации такой реально тоже давно уже нет. Даже в дешёвых машинах уже несколько процессоров, или один многоядерный, и/или гипертредный.

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

Интересно, что есть совершенно иная схема работы с атомарными объектами. Процессоры mips не имеют инструкции вида «атомарно что-то сделать с ячейкой памяти». Вместо этого у MIPS есть интересная связанная пара инструкций:

LL - load linked
SC - store conditional


Первая инструкция — load linked — просто читает значение из памяти. Но при этом в процессоре взводится триггер, который «следит» за считанной ячейкой — не было ли в неё записи.

Вторая — store conditional — сохраняет значение в память. Но! Если со времени исполнения load linked в эту ячейку кто-то уже записал новое значение, store conditional вернёт признак неуспеха (и, конечно, ничего в ячейку памяти записывать не будет).

Как оно устроено внутри

Судя по всему, механизм MIPS гораздо дешевле в реализации, потому что для этого используются уже существующие механизмы синхронизации состояния кеш-памяти между процессорами. Упомянутый триггер сбрасывается, если процессор получает апдейт состояния кеша для адреса, на котором «висит» триггер. То есть «атомарная» операция не требует от соседних процессоров никакой работы по обслуживанию атомарности.

В отличие от Интеловского xchg такая пара позволяет делать не только спинлоки, но и реализовывать более сложные алгоритмы. Вернёмся к разговору о семафорах:

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

Все проблемы с этим кодом на процессоре MIPS можно решить довольно просто:

do 
{
    rpos = load_linked( &read_pos )
    ret = buf[rpos++];
    rpos %= sizeof(buf);
} while( !store_conditional( &read_pos, rpos ) );

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

Что ещё важно знать про спинлоки в среде ядра ОС (или при программировании для микроконтроллеров, где, как правило, нет режима пользователя): при захвате спинлока прерывания должны быть запрещены.

Дело в том, что спинлок может защитить нас от другого процессора, но не от нашего же — если внутри запертого спинлока случится прерывание и в прерывании процессор попробует захватить тот же спинлок, наступит клинч: до возврата из прерывания отпереть спинлок некому, а прерывание не закончится, пока спинлок не отперт.

Поэтому типовая реализация спинлоков или запрещает прерывания сама, или, по крайней мере, проверяет, не забыл ли их запретить вызывающий код.

Возвращаясь к вопросу о мьютексах и спинлоках: внутри спинлока много чего нельзя. Нельзя спать — нас ждут, нельзя переключать контекст (отдавать процессор) — это чревато дедлоком аналогично ситуации с прерываниями. Нельзя вызывать функции, которые имеют шанс выполнить вышеперечисленное. Например, в ядре или в коде микроконтроллера может быть невозможно вызвать malloc — как правило, он сам синхронизирован и может при нехватке памяти ожидать её освобождения. Ну и, например, могут быть под запретом функции записи в лог — особенно если они пытаются отправить данные на сервер логирования через syslog over UDP.

При всём сказанном выше в прерываниях спинлоками пользоваться можно и нужно. Собственно, только ими и можно. Правда, это имеет смысл только если в машине несколько процессоров. Иначе вся синхронизация сводится к запрету прерываний, включая запрет прерываний при исполнении собственно прерывания.

На этом сочтём обзор традиционных примитивов синхронизации завершённым. Через недельку я постараюсь вернуться к теме и окончательно взорвать вам мозг статьей о проблемах реализации примитивов синхронизации в среде персистентной виртуальной памяти. :)

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.