Read-copy-update (Read-copy-update)

Read-Copy-Update, RCU (Чтение-модификация-запись^{[уточнить]}, чтение-копирование при обновлении, чтение — копирование — обновление, Прочитать-Скопировать-Обновить) — механизм синхронизации в многопоточных системах. Реализует неблокирующую синхронизацию для всех читателей структуры данных. Запись может производиться параллельно чтению, однако одновременно может быть активен только один писатель.

Описание

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

Изменение элемента в списке

Рассмотрим для примера, как произвести изменение элемента в односвязном списке с применением данного механизма синхронизации.

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

Данный метод нельзя назвать эффективным из-за необходимости копировать весь список. Однако, если можно гарантировать, что читать можно будет лишь один элемент списка и при переходе к следующему будет обновляться блокировка, то при записи можно оставить необходимость копировать и изменять только один элемент, после чего атомарно обновлять указатель в предыдущем элементе списка (или указатель на первый элемент).

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

Освобождение памяти

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

Чтение в критической области

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

Чтение-модификация-запись в Linux

В операционной системе Linux поддержка RCU присутствует начиная с версии ядра 2.5. Основные функции RCU API:

1. rcu_read_lock() — объявляет о входе потока на чтение в критическую секцию;
2. rcu_read_unlock() — объявляет о выходе читающего потока из критической секции;
3. synchronize_rcu() — вызывая эту функцию, поток, открытый на запись, ожидает, пока все операции чтения, имевшие доступ к старой версии структуры данных, не прекратят свою работу. После этого поток, открытый на запись, может свободно удалить устаревшую копию.

Также, для защиты от оптимизаций компилятора, меняющих последовательность исполнения инструкций, определены макросы для безопасного получения и обновления указателя на структуру данных rcu_dereference() и rcu_assign_pointer(), соответственно.

Действия до и после записи

Сначала необходимо произвести чтение структуры данных, затем - модификацию её копии, после чего - атомарно записать указатель на обновлённую структуру данных.

Альтернативы

На некоторых платформах (например, RISC) данная инструкция недоступна. Эквивалентных результатов можно достичь с помощью инструкций:

1. загрузка с пометкой (LL — load linked);
2. попытка записи (SC — store conditional).

Литература

• Paul E. McKenney, John D. Slingwine. Read-Copy_update: using execution history to solve concurrency problems  (неопр.).
• What is RCU?  (неопр.)
• Paul E. McKenney, Jonathan Walpole. What is RCU, Fundamentally?  (неопр.)