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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание[править | править вики-текст]

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

Изменение элемента в списке[править | править вики-текст]

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

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

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

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

Освобождение памяти[править | править вики-текст]

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

Чтение в критической области[править | править вики-текст]

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

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

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

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

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

Название[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]