Неблокирующие алгоритмы широко применяются в ядре Linux когда традиционные примитивы блокировки либо не могут быть использованы, либо недостаточно быстры. Эта тема многим интересна и время от времени всплывает на LWN. Из недавнего — вот эта июльская статья, которая собственно и сподвигла меня написать свою серию. Ещё чаще разговор заходит про механизм read-copy-update (RCU — руководство 2007 года всё ещё актуально), подсчёт ссылок, и способы сделать более понятные, высокоуровные API ко всему этому разнообразию. Ну а сейчас вас ждёт погружение в идеи, стоящие за неблокирующими алгоритмами, а также их использованием в ядре.
Знание низкоуровневой модели памяти в целом считается продвинутым уровнем понимания, которого страшатся даже опытные программисты-ядерщики. Словами нашего редактора (из его июльской статьи): «Понять модель памяти можно лишь правильно повёрнутым мозгом». Говорят, что моделью памяти Linux (и файлом memory-barriers.txt в частности) можно пугать детей. Порой для достижения эффекта достаточно всего лишь рявкнуть “acquire” или “release”.
И в то же время, механизмы вроде RCU и seqlocks так широко применяются в ядре, что практически каждый разработчик рано или поздно сталкивается с фундаментально неблокирующими интерфейсами. Поэтому многим будет полезно иметь хотя бы базовое представление о неблокирующей синхронизации. В этой серии статей я расскажу, что же на самом деле означает acquire и release-семантика, а также приведу пять сравнительно простых паттернов, которые покрывают большинство вариантов использования неблокирующих примитивов.
В связи с терминологической путаницей в русском языке, в контексте всей серии слово «неблокирующий» следует понимать как «не блокирующий исполнение на ожидании входа в критическую секцию», что по-английски выражается очень лаконичным “lock-free” и означает совсем не то же самое, что и “wait-free”. Акцент ставится на многопоточных алгоритмах, которые могут координировать свою работу без использования блокирующих примитивов синхронизации.
Все статьи цикла:
Атомарные операции и частичные барьеры памяти
Полные барьеры памяти
Введение в compare-and-swap
(продолжение следует)
Acquire, release, и “happens before”
Чтобы покинуть зону (сравнительного) комфорта блокирующих примитивов синхронизации и перейти к неблокирующему программированию, сначала надо понять, почему блокировки вообще работают. Обычно этому учат на примере мьютексов: захваченный мьютекс блокирует все остальные потоки, не давая им одновременно читать и изменять общие данные. Но что такое «одновременно» на самом деле? И что происходит, когда поток T закончил работу, а поток U дождался мьютекса и принялся за свою работу?
Ответы на эти вопросы предлагает теория, разработанная Лесли Лемпортом в 1978 году и опубликованная в статье “Time, Clocks and the Ordering of Events in a Distributed System”. В соответствии с ней, события в распределённых системах можно упорядочить, если знать, когда событие P происходит перед событием Q:
- События в потоке линейно упорядочены. Другими словами, в пределах одного потока всегда понятно, какое событие происходит первым, а какое следующим.
- Для событий P и Q в разных потоках, событие P происходит перед Q, если P — это отправка сообщения, а Q — получение этого сообщения.
- Отношение порядка транзитивно. То есть, если P происходит перед Q, а Q происходит перед R, то P происходит перед R.
Отношение «происходит перед» (happens before) определяет частичный порядок: может так быть, что для событий P и Q ни одно из них не происходит чётко перед другим. Тогда говорят, что они происходят одновременно (concurrently). Помните что мьютексы предотвращают одновременный доступ к данным? Так вот, когда вы используете мьютексы, все операции над данными линейно упорядочиваются, как если бы они выполнялись одним потоком. Идея Лемпорта также позволяет описать передачу блокировки от одного потока другому: если поток T «отправит сообщение» о том, что он отпустил мьютекс, то это «происходит перед тем», как поток U получает мьютекс себе.
Так вышло, что теорией дело не ограничилось: для соблюдения протоколов когерентности кешей процессоры буквально обмениваются сообщениями на шине. Intel называет её QPI, а в AMD это HyperTransport. Однако, это мы слишком глубоко зашли. Остановимся на том, как отношением “happens before” описать любой примитив синхронизации.
Лемпорт понял суть: синхронизация происходит, когда два потока выполняют определённые симметричные операции со структурой данных. То есть: существуют пары операций (вроде отправки и получения сообщения через очередь), которые синхронизируют потоки между собой. Более того, одна из этих операций что-то отпускает (release), а другая — получает (acquire); говоря умными словами: «операции обладают release- или acquire-семантикой».
В каждой паре release-операция синхронизирована с соответствующей acquire-операцией. Под «синхронизацией» здесь понимается, что когда в одном потоке происходит release-операция, а одновременно в другом — acquire-операция, то работа потоков упорядочивается и release «происходит перед» acquire. При этом, в целом операции всё ещё упорядочены лишь частично — лишь между двумя потоками (или тремя и более, принимая во внимание транзитивность). Говоря формальным языком:
- Операции в потоке линейно упорядочены.
- Если операция P с release-семантикой синхронизирована с acquire-операцией Q, то операция P происходит перед операцией Q, даже если они происходят в разных потоках.
- Как и ранее, это отношение транзитивно и определяет частичный порядок операций.
Предыдущее определение можно получить, полагая отправку сообщений операцией с release-семантикой, а получение — выполняющим acquire. Поток, отправляющий сообщение, синхронизируется с потоком (или потоками), которые это сообщение получают. Мы также теперь можем формализовать понимание мьютексов: чтобы мьютекс работал, его надо отпускать с release-семантикой, синхронизируя это с захватом — который является acquire-операцией. Таким образом, если потоки работают с мьютексом «одновременно», то они делают это в определённом порядке.
Acquire и release-семантика выглядит как что-то абстрактное для учёных-теоретиков, но она действительно очень просто описывает многие приёмы многопоточного программирования. Например, пусть у нас есть два пользовательских потока и глобальная переменная:
поток 1 поток 2
-------------------------------- ------------------------
s = "hello";
pthread_create(&t, NULL, t2, NULL);
puts(s);
s = "world";
pthread_join(t, NULL);
puts(s);
Безопасно ли так делать? Может ли второй поток предполагать, что в переменной s будет "hello"? А первый поток может ли рассчитывать, что после pthread_join() там будет "world"? Да, да, и да. Всё это отлично объясняется в терминах acquire и release-семантики:
- pthread_create() обладает release-семантикой и синхронизируется с началом исполнения второго потока (что обладает acquire-семантикой). Соответственно, всё, что было записано до начала потока, можно безопасно считать в этом потоке.
- Завершение второго потока обладает release-семантикой и синхронизируется с завершением pthread_join() (acquire-семантика). Следовательно, всё, что было записано во втором потоке, будет видно в первом после pthread_join().
Внимательный читатель заметит, что данные передаются между потоками без единой блокировки: поздравляю, вы явно делаете успехи в неблокирующем программировании. Подводя итог:
- Если вам надо сделать так, чтобы поток B «увидел» что-то, что произошло в потоке A, то два потока должны синхронизироваться между собой: для этого поток A должен выполнить release-операцию, а поток B — соответствующую acquire-операцию.
- Знание семантики API позволяет вам писать код, полагающийся на гарантии порядка, предоставляемые этими API.
Осознав роль release и acquire-семантики в работе высокоуровневых примитивов синхронизации, рассмотрим их на уровне отдельных операций с памятью.
Паттерн «Передача сообщений»
В предыдущем разделе мы видели, как acquire и release-семантика вызовов pthread_create() и pthread_join() позволяет передать данные в создаваемый поток и назад. Теперь же рассмотрим, как организовать подобное общение — без блокировок — между потоками во время их работы.
Если ваше сообщение — это простое скалярное значение, вроде флажка, то его можно просто брать и читать-писать в памяти. Однако что делать, если надо передать указатель на данные, как в следующем примере?
поток 1 поток 2
-------------------------------- ------------------------
a.x = 1;
message = &a; datum = message;
if (datum != NULL)
printk("%d\n", datum->x);
Если в message изначально был NULL, то второй поток может прочитать либо NULL, либо &a — нельзя сказать конкретно. Но дело даже не в этой неопределённости. Даже если нам повезёт и
datum = message;
прочитает &a — это присваивание всё ещё не синхронизировано с тем, что происходит в первом потоке:
message = &a;
Соответственно, между потоками ничего не упорядочено. В каждом отдельном потоке всё чётко:
a.x = 1; datum = message;
| |
| происходит перед |
v v
message = &a; datum->x
Но между собой потоки никак не связаны, поэтому у нас нет никаких гарантий, что datum->x прочитает 1; мы не знаем, произойдёт ли присваивание a.x перед чтением или нет. Чтобы получить желаемое поведение, нужно синхронизировать работу потоков.
Для этого существуют операции “store-release” и “load-acquire”, выполняемые парами. Store-release операция P помимо записи в память синхронизирована с load-acquire операцией Q, если Q читает значение, записанное P. Корректный код использует smp_store_release() и smp_load_acquire():
поток 1 поток 2
-------------------------------- ------------------------
a.x = 1;
smp_store_release(&message, &a); datum = smp_load_acquire(&message);
if (datum != NULL)
printk("%x\n", datum->x);
Теперь, если в datum реально лежит &a, мы можем быть уверены, что запись a.x = 1 произошла перед чтением datum->x. (Я для простоты полагаю, что только один поток может записать что-то в message. Фразу «поток 2 читает значение, записанное потоком 1» следует понимать буквально: такой порядок наблюдается лишь потому, что запись из потока 1 — это последнее, что видно в потоке 2.) Отношения между потоками теперь выглядят так:
a.x = 1;
|
v
smp_store_release(&message, &a); -----> datum = smp_load_acquire(&message);
|
v
datum->x
И всё работает как положено. Транзитивность гарантирует, что когда поток 2 читает значение, записанное потоком 1, то всё, что поток 1 сделал до store-release, произошло перед тем, как поток 2 выполнил load-acquire. Обратите внимание, что в отличие от примера с pthread_join(), здесь «синхронизация» не подразумевает какого-либо ожидания. Поток 2 не будет ждать, пока поток 1 запишет своё значение, чтобы запись точно «произошла перед тем», как поток 2 прочитает это значение. Когда поток 2 читает значение, записанное потоком 1, то он его увидит. А когда читает другое значение — то видит что-то другое.
В ядре Linux аналогичный код часто пишут чуть по-другому:
поток 1 поток 2
-------------------------------- ------------------------
a.x = 1;
smp_wmb();
WRITE_ONCE(message, &a); datum = READ_ONCE(message);
smp_rmb();
if (datum != NULL)
printk("%x\n", datum->x);
В этом случае семантика acquire и release предоставляется барьерами памяти smp_wmb() и smp_rmb(). Барьеры тоже могут синхронизировать операции, но они сложнее для понимания, чем просто запись и чтение из памяти. Мы к ним ещё вернёмся, когда будем обсуждать seqlocks.
Пары load-acquire/store-release и smp_rmb()/smp_wmb() очень часто используются в ядре, поэтому следует чётко представлять, что именно они делают. Вот несколько примеров, где всплывают эти операции:
- Всевозможные кольцевые буферы. Данные в кольцевых буферах часто содержат указатели на другие данные. При работе с буфером обновляются индексы начала/конца буфера. Элементы вставляются в буфер через store-release, чтобы синхронизироваться с извлечением через load-acquire.
- RCU. Знакомые вам rcu_dereference() и rcu_assign_pointer() с точки зрения компилятора работают как load-acquire и store-release. Благодаря некоторым предположениям, на всех архитектурах кроме Alpha, rcu_dereference() может компилироваться в простое чтение из памяти; и тем не менее, rcu_assign_pointer() будет синхронизирована с rcu_dereference(), как если бы она была настоящей load-acquire операцией.
- Передача указателей через массив. В следующем (упрощённом) кусочке кода KVM если kvm_get_vcpu() видит инкремент kvm->online_vcpus, то значение в массие kvm->vcpus будет корректным:
kvm_vm_ioctl_create_vcpu() kvm_get_vcpu()
----------------------------------------- -----------------------------------------------
kvm->vcpus[kvm->online_vcpus] = vcpu; if (idx < smp_load_acquire(&kvm->online_vcpus))
smp_store_release(&kvm->online_vcpus, return kvm->vcpus[idx];
kvm->online_vcpus + 1); return NULL;
Помимо принципа парной работы load-acquire/store-release операций, не стоит также забывать и о другом аспекте передачи сообщений: что если отправителей больше одного? Если так, то они должны быть защищены друг от друга каким-то иным способом, например мьютексом. Неблокирующие алгоритмы — это не вершина эволюции, а всего лишь один из инструментов многопоточного программирования, каждому из которых находится своё место и ситуация, а порой требуется применять несколько из них.
История неблокирующих алгоритмов только начинается. Смотрите в следующей серии: как упорядочиваются атомарные операции в памяти и какую роль барьеры играют в механизме “seqcounts” и планировщике задач Linux.
