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

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

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

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

По сути, мы будем говорить про единственный примитив, который принципиально отличается от остальных: спинлок. 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 такая пара позволяет делать не только спинлоки, но и реализовывать более сложные алгоритмы. Вернёмся к разговору о семафорах ^[1]:

    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.

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

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

Автор: dzavalishin

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