Последняя статья про классические примитивы синхронизации.
(Наверное, потом напишу ещё одну про совсем уже нетипичную задачу, но это потом.)
Сегодня мы немножко заглянем в процессор. Чуть-чуть.
По сути, мы будем говорить про единственный примитив, который принципиально отличается от остальных: спинлок. 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 вернёт признак неуспеха (и, конечно, ничего в ячейку памяти записывать не будет).
В отличие от Интеловского 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.
При всём сказанном выше в прерываниях спинлоками пользоваться можно и нужно. Собственно, только ими и можно. Правда, это имеет смысл только если в машине несколько процессоров. Иначе вся синхронизация сводится к запрету прерываний, включая запрет прерываний при исполнении собственно прерывания.
На этом сочтём обзор традиционных примитивов синхронизации завершённым. Через недельку я постараюсь вернуться к теме и окончательно взорвать вам статьей о проблемах реализации примитивов синхронизации в среде персистентной виртуальной памяти. :)
Автор: dzavalishin
