Введение
Механизм синхронизации
В информатике обновление копии при чтении (RCU) — это механизм синхронизации, который позволяет избежать использования блокирующих примитивов при одновременном чтении и обновлении элементов, связанных через указатели и принадлежащих общим структурам данных (например, связным спискам, деревьям, хеш-таблицам). Каждый раз, когда поток вставляет или удаляет элементы структур данных в общей памяти, всем читателям гарантированно будет видна либо старая, либо новая структура, что позволяет избежать несогласованностей (например, разыменования нулевых указателей). Основная гарантия RCU может быть использована путем разделения обновлений на фазы удаления и освобождения. Фаза удаления удаляет ссылки на элементы данных в структуре данных (возможно, заменяя их ссылками на новые версии этих элементов данных) и может выполняться одновременно с критическими секциями чтения RCU. Безопасность одновременного выполнения фазы удаления с читателями RCU обеспечивается семантикой современных процессоров, гарантирующих, что читатели увидят либо старую, либо новую версию структуры данных, а не частично обновленную ссылку. После истечения периода благодати больше не может быть читателей, ссылающихся на старую версию, поэтому фаза освобождения может безопасно освободить (восстановить) элементы данных, составлявшие эту старую версию. Разделение обновления на фазы удаления и освобождения позволяет обновляющему немедленно выполнить фазу удаления и отложить фазу освобождения до тех пор, пока все читатели, активные во время фазы удаления, не завершат работу, то есть пока не истечет период благодати. Таким образом, типичная последовательность обновления RCU выглядит следующим образом:
In computer science, read copy update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e. g., linked lists, trees, hash tables). Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e. g., dereferencing null pointers). RCU's fundamental guarantee may be used by splitting updates into removal and reclamation phases. The removal phase removes references to data items within a data structure (possibly by replacing them with references to new versions of these data items) and can run concurrently with RCU read side critical sections. The reason that it is safe to run the removal phase concurrently with RCU readers is the semantics of modern CPUs guarantee that readers will see either the old or the new version of the data structure rather than a partially updated reference. Once a grace period has elapsed, there can no longer be any readers referencing the old version, so it is then safe for the reclamation phase to free (reclaim) the data items that made up that old version. Splitting an update into removal and reclamation phases allows the updater to perform the removal phase immediately, and to defer the reclamation phase until all readers active during the removal phase have completed, in other words, until a grace period has elapsed. So, the typical RCU update sequence goes something like the following:
Убедитесь, что все читатели, обращающиеся к структурам данных, защищенным RCU, выполняют доступ к своим ссылкам из критической секции чтения RCU. Удалите указатели на структуру данных, чтобы последующие читатели не могли получить к ней ссылку. Дождитесь истечения периода благодати, чтобы все предыдущие читатели (у которых все еще могут быть указатели на удаленную структуру данных) завершили свои критические секции чтения RCU. На этом этапе не должно быть читателей, удерживающих ссылки на структуру данных, поэтому ее можно безопасно освободить (например, удалить из памяти). В описанной процедуре (которая соответствует предыдущей схеме) обновляющий выполняет как фазу удаления, так и фазу освобождения, но часто бывает полезно, чтобы фазу освобождения выполняла совершенно другая нить. Подсчет ссылок можно использовать, чтобы позволить читателю выполнять удаление, поэтому, даже если одна и та же нить выполняет шаг обновления (шаг (2) выше) и шаг освобождения (шаг (4) выше), часто полезно рассматривать их отдельно. RCU, пожалуй, является наиболее распространенным неблокирующим алгоритмом для общих структур данных. RCU полностью свободна от ожидания для любого количества читателей. Однопоточные реализации RCU также не блокируются для записи. Некоторые многопоточные реализации RCU не используют блокировки. Другие многопоточные реализации RCU сериализуют записи с помощью блокировки.
Применение
К началу 2008 года насчитывалось почти 2000 применений RCU API в ядре Linux, включая стеки сетевых протоколов и систему управления памятью. По состоянию на 2014 год их число превысило 9000. С 2006 года исследователи применяют RCU и подобные методы для решения ряда задач, в том числе управления метаданными, используемыми при динамическом анализе, управления временем жизни кластеризованных объектов, управления временем жизни объектов в исследовательской операционной системе K42 и оптимизации реализаций программной транзакционной памяти. Dragonfly BSD использует технику, аналогичную RCU, наиболее близкую к реализации Sleepable RCU (SRCU) в Linux.
Преимущества и недостатки
Возможность ожидать завершения работы всех читателей позволяет читателям RCU использовать значительно более легкую синхронизацию – в некоторых случаях, вообще без синхронизации. В отличие от более традиционных схем, основанных на блокировках, читатели должны использовать тяжеловесную синхронизацию, чтобы предотвратить удаление структуры данных обновляющим процессом прямо во время чтения. Это связано с тем, что обновляющие процессы, использующие блокировки, обычно обновляют данные непосредственно в памяти и, следовательно, должны исключать доступ читателей. В отличие от этого, обновляющие процессы RCU обычно используют тот факт, что запись в одиночные выровненные указатели является атомарной на современных процессорах, что позволяет атомарно вставлять, удалять и заменять данные в связных структурах, не прерывая работу читателей. Одновременные читатели RCU могут продолжать обращаться к старым версиям данных и избегать использования дорогих атомарных инструкций чтения-модификации-записи, барьеров памяти и промахов кэша, которые обходятся дорого на современных SMP-системах, даже при отсутствии конкуренции за блокировки. Легковесность примитивов чтения RCU предоставляет дополнительные преимущества, помимо отличной производительности, масштабируемости и быстродействия в реальном времени. Например, они обеспечивают устойчивость к большинству ситуаций взаимной блокировки и зависания. Разумеется, у RCU есть и недостатки. Например, RCU – это специализированная техника, которая наиболее эффективна в ситуациях с преобладанием чтения над записью, но часто менее применима к рабочим нагрузкам, состоящим только из записи. Кроме того, хотя возможность одновременного выполнения читателей и обновляющих процессов RCU и обеспечивает легковесность примитивов чтения RCU, некоторые алгоритмы могут быть несовместимы с одновременным чтением и обновлением. Несмотря на более чем десятилетний опыт использования RCU, точная область его применимости все еще является предметом исследований.
Патенты
Техника защищена патентом США на программное обеспечение, выданным 15 августа 1995 года и принадлежащим Sequent Computer Systems, а также патентами (срок действия истек 30.03.2009), (срок действия истек 05.04.2010), (срок действия истек 18.05.2009) и (срок действия истек 25.05.2009). Истекший патент США охватывает близкую по своей сути технологию. RCU также является предметом одного пункта обвинения в судебном разбирательстве SCO против IBM.