✖


Jump to content

Чтение-копирование-обновление

В информатике одновременно читают и обновляют элементы , чтение-копирование-обновление ( RCU ) — это механизм синхронизации , который позволяет избежать использования примитивов блокировки , когда несколько потоков которые связаны указателями и принадлежат общим структурам данных (например, связанным спискам , деревьям) . , хеш-таблицы ). [1]

Всякий раз, когда поток вставляет или удаляет элементы структур данных в разделяемой памяти , все читатели гарантированно видят и проходят либо старую, либо новую структуру, что позволяет избежать несоответствий (например, разыменования нулевых указателей ). [1]

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

Название и обзор

[ редактировать ]

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

  • создать новую структуру,
  • скопируйте данные из старой структуры в новую и сохраните указатель на старую структуру,
  • изменить новую, скопированную структуру,
  • обновите глобальный указатель, чтобы он ссылался на новую структуру,
  • спать до тех пор, пока ядро ​​операционной системы не определит, что не осталось читателей, используя старую структуру, например, в ядре Linux, используя синхронизировать_rcu() ,
  • после пробуждения ядра освободите старую структуру.

Таким образом, структура читается потока одновременно с копированием для выполнения обновления , отсюда и название «обновление чтения-копирования». Аббревиатура «RCU» была одним из многих вкладов сообщества Linux. Другие названия подобных методов включают пассивную сериализацию и отсрочку MP программистами VM/XA , а также генерации программистами K42 и Tornado .

Подробное описание

[ редактировать ]
Процедура прошивки чтение-копирование-обновление. Поток выделяет структуру с тремя полями, затем устанавливает глобальный указатель gptr, чтобы указать на эту структуру.

Ключевым свойством RCU является то, что читатели могут получить доступ к структуре данных, даже когда она находится в процессе обновления: средства обновления RCU не могут блокировать считыватели или заставлять их повторить попытку доступа. Этот обзор начинается с демонстрации того, как данные можно безопасно вставлять в связанные структуры и удалять из них, несмотря на одновременные операции чтения. Первая диаграмма справа изображает процедуру вставки с четырьмя состояниями, в которой время продвигается слева направо.

Первое состояние показывает глобальный указатель с именем gptr это изначально NULL , окрашенный в красный цвет, чтобы указать, что читатель может получить к нему доступ в любое время, что требует от разработчиков обновлений проявлять осторожность. Выделение памяти для новой структуры переходит во второе состояние. Эта структура имеет неопределенное состояние (отмечено знаками вопроса), но недоступна для читателей (отмечено зеленым цветом). Поскольку структура недоступна для читателей, средство обновления может выполнять любую желаемую операцию, не опасаясь нарушить работу параллельных операций чтения. Инициализация этой новой структуры переходит в третье состояние, которое показывает инициализированные значения полей структуры. Присвоение ссылки на эту новую структуру gptr переходит в четвертое и последнее состояние. В этом состоянии структура доступна для читателей и поэтому окрашена в красный цвет. Примитив rcu_assign_pointer используется для выполнения этого присваивания и гарантирует, что присвоение является атомарным в том смысле, что одновременные операции чтения либо увидят NULL- указатель или действительный указатель на новую структуру, но не смесь двух значений. Дополнительные свойства rcu_assign_pointer описаны далее в этой статье.

Процедура удаления чтения-копирования-обновления

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

Первое состояние показывает связанный список, содержащий A , B и C. элементы Все три элемента окрашены в красный цвет, чтобы указать, что считыватель RCU может обратиться к любому из них в любое время. С использованием list_del_rcu для удаления элемента B из этого списка переходит во второе состояние. Обратите внимание, что ссылка от элемента B к C остается нетронутой, чтобы позволить читателям, ссылающимся в данный момент на элемент B, просмотреть оставшуюся часть списка. Читатели, получившие доступ к ссылке из элемента A, получат либо ссылку на элемент B , либо элемент C , но в любом случае каждый читатель увидит действительный и правильно отформатированный связанный список. Элемент B теперь окрашен в желтый цвет, чтобы указать, что, хотя ранее существовавшие считыватели все еще могут иметь ссылку на элемент B , новые считыватели не имеют возможности получить ссылку. Операция ожидания читателей переходит в третье состояние. Обратите внимание, что эта операция ожидания чтения должна ожидать только уже существующих читателей, но не новых читателей. Элемент B теперь окрашен в зеленый цвет, чтобы указать, что читатели больше не могут ссылаться на него. Таким образом, теперь средство обновления может безопасно освободить элемент B , перейдя таким образом в четвертое и последнее состояние.

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

Эта процедура демонстрирует, как старые данные могут быть удалены из связанной структуры данных, даже если читатели одновременно просматривают структуру данных до, во время и после удаления. Учитывая вставку и удаление, с помощью RCU можно реализовать самые разнообразные структуры данных.

Считыватели RCU выполняются в критических секциях на стороне чтения , которые обычно разделяются rcu_read_lock и rcu_read_unlock . Любой оператор, который не находится в критической секции на стороне чтения RCU, считается находящимся в состоянии покоя , и таким операторам не разрешается хранить ссылки на структуры данных, защищенные RCU, а также не требуется операция ожидания чтения. для потоков в состояниях покоя. Любой период времени, в течение которого каждый поток хотя бы один раз находится в состоянии покоя, называется периодом отсрочки . По определению, любая критическая секция на стороне чтения RCU, существующая в начале данного льготного периода, должна завершиться до окончания этого льготного периода, что составляет фундаментальную гарантию, предоставляемую RCU. Кроме того, операция ожидания чтения должна дождаться истечения хотя бы одного льготного периода. Оказывается, эту гарантию можно обеспечить с чрезвычайно небольшими накладными расходами на стороне чтения, фактически в предельном случае, который фактически реализуется сборками ядра Linux серверного класса, накладные расходы на стороне чтения равны ровно нулю. [2]

Фундаментальную гарантию RCU можно использовать, разделив обновления на этапы удаления и восстановления . Фаза удаления удаляет ссылки на элементы данных внутри структуры данных (возможно, заменяя их ссылками на новые версии этих элементов данных) и может выполняться одновременно с критическими разделами на стороне чтения RCU. Причина, по которой безопасно запускать этап удаления одновременно со считывателями RCU, заключается в том, что семантика современных процессоров гарантирует, что читатели увидят либо старую, либо новую версию структуры данных, а не частично обновленную ссылку. По истечении льготного периода никакие читатели больше не могут ссылаться на старую версию, поэтому на этапе восстановления можно безопасно освободить ( восстановить ) элементы данных, составлявшие эту старую версию. [3]

Разделение обновления на этапы удаления и восстановления позволяет программе обновления немедленно выполнить этап удаления и отложить этап восстановления до тех пор, пока все считыватели, активные во время этапа удаления, не завершатся, другими словами, пока не истечет льготный период. [примечание 1]

Итак, типичная последовательность обновления RCU выглядит примерно следующим образом: [4]

  1. Убедитесь, что все считыватели, обращающиеся к структурам данных, защищенным RCU, выполняют свои ссылки из критической секции на стороне чтения RCU.
  2. Удалите указатели на структуру данных, чтобы последующие читатели не могли получить ссылку на нее.
  3. Подождите, пока истечет льготный период, чтобы все предыдущие считыватели (у которых все еще могли быть указатели на структуру данных, удаленную на предыдущем шаге) завершили свои критические разделы на стороне чтения RCU.
  4. На этом этапе не может быть каких-либо читателей, которые все еще содержат ссылки на структуру данных, поэтому теперь ее можно безопасно вернуть (например, освободить). [примечание 2]

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

RCU — это, пожалуй, самый распространенный неблокирующий алгоритм для общей структуры данных. RCU совершенно не требует ожидания для любого количества читателей. Реализации с одним записывающим устройством RCU также не блокируются для записывающего устройства. [5] Некоторые реализации RCU с несколькими записывающими устройствами не блокируются. [6] Другие реализации RCU с несколькими записывающими устройствами сериализуют записывающие устройства с блокировкой. [7]

Использование

[ редактировать ]

К началу 2008 года в ядре Linux было почти 2000 использований API RCU. [8] включая стеки сетевых протоколов [9] и система управления памятью. [10] По состоянию на март 2014 г. , было более 9000 использований. [11] С 2006 года исследователи применили RCU и аналогичные методы для решения ряда задач, включая управление метаданными, используемыми в динамическом анализе. [12] управление временем жизни кластеризованных объектов, [13] управление временем жизни объектов в исследовательской операционной системе K42 , [14] [15] и оптимизация реализации программной транзакционной памяти . [16] [17] Dragonfly BSD использует технику, аналогичную RCU, которая больше всего напоминает реализацию Sleepable RCU (SRCU) в Linux.

Преимущества и недостатки

[ редактировать ]

Возможность ждать, пока все считыватели завершат работу, позволяет считывателям RCU использовать гораздо более легкую синхронизацию — в некоторых случаях вообще без синхронизации. Напротив, в более традиционных схемах, основанных на блокировках, считыватели должны использовать тяжелую синхронизацию, чтобы предотвратить удаление программой обновления структуры данных из-под них. Причина в том, что средства обновления на основе блокировки обычно обновляют данные на месте и поэтому должны исключать считыватели. Напротив, средства обновления на основе RCU обычно используют тот факт, что запись в одновыровненные указатели на современных процессорах является атомарной, что позволяет атомарно вставлять, удалять и заменять данные в связанной структуре, не нарушая чтения. Параллельные считыватели RCU могут затем продолжить доступ к старым версиям и обойтись без атомарных инструкций чтения-изменения-записи, барьеров памяти и промахов в кэше, которые так дорого обходятся современным компьютерным системам SMP , даже при отсутствии конкуренции за блокировки. [18] [19] Легкость примитивов RCU на стороне чтения обеспечивает дополнительные преимущества, помимо превосходной производительности, масштабируемости и отклика в реальном времени. Например, они обеспечивают невосприимчивость к большинству состояний взаимоблокировок и активных блокировок. [примечание 3]

Конечно, у RCU есть и недостатки. Например, RCU — это специализированный метод, который лучше всего работает в ситуациях, когда в основном выполняется чтение и мало обновлений, но часто менее применим к рабочим нагрузкам, связанным только с обновлением. Другой пример: хотя тот факт, что считыватели и средства обновления RCU могут выполняться одновременно, обеспечивает легковесный характер примитивов на стороне чтения RCU, некоторые алгоритмы могут быть несовместимы с параллельным чтением/обновлением.

Несмотря на более чем десятилетний опыт работы с RCU, точная степень его применимости все еще является предметом исследования.

Патенты

[ редактировать ]

Этот метод защищен патентом США на программное обеспечение № 5,442,758 , выданным 15 августа 1995 г. и переданным Sequent Computer Systems , а также патентом США № 5,608,893 (истекший 30 марта 2009 г.), патентом США № 5,727,209 (истекшим в 2010 г.). 05), патент США 6 219 690 (истёк срок действия 18 мая 2009 г.) и патент США 6 886 162 (истёк срок действия 25 мая 2009 г.). Патент США с истекшим сроком действия. Патент США № 4,809,168 охватывает тесно связанную технологию. RCU также является предметом одного иска в SCO против IBM иске .

Пример интерфейса RCU

[ редактировать ]

RCU доступен во многих операционных системах и был добавлен в ядро ​​Linux реализации уровня пользователя, такие как liburcu . в октябре 2002 года. Также доступны [20]

Реализация RCU в версии 2.6 ядра Linux входит в число наиболее известных реализаций RCU и будет использована в качестве вдохновения для API RCU в оставшейся части этой статьи. Основной API ( интерфейс прикладного программирования ) довольно мал: [21]

  • rcu_read_lock(): помечает структуру данных, защищенную RCU, чтобы она не была восстановлена ​​в течение всего срока действия этого критического раздела.
  • rcu_read_unlock(): используется считывателем для информирования восстановителя о том, что считыватель выходит из критического раздела на стороне чтения RCU. Обратите внимание, что критические секции на стороне чтения RCU могут быть вложенными и/или перекрываться.
  • sync_rcu(): Блокируется до тех пор, пока не будут завершены все ранее существовавшие критические секции чтения RCU на всех процессорах. Обратите внимание, что synchronize_rcu обязательно будет не ждать завершения каких-либо последующих критических разделов RCU на стороне чтения. Например, рассмотрим следующую последовательность событий: 
	         CPU 0                  CPU 1                 CPU 2
	     ----------------- ------------------------- ---------------
	 1.  rcu_read_lock()
	 2.                    enters synchronize_rcu()
	 3.                                               rcu_read_lock()
	 4.  rcu_read_unlock()
	 5.                     exits synchronize_rcu()
	 6.                                              rcu_read_unlock()
С synchronize_rcu — это API, который должен определять, когда читатели закончили работу. Его реализация является ключом к RCU. Чтобы RCU был полезен во всех ситуациях, кроме наиболее интенсивного чтения, synchronize_rcuНакладные расходы также должны быть весьма небольшими.
Альтернативно, вместо блокировки,sync_rcu может зарегистрировать обратный вызов, который будет вызываться после завершения всех текущих критических секций на стороне чтения RCU. Этот вариант обратного вызова называется call_rcu в ядре Linux.
  • rcu_assign_pointer(): средство обновления использует эту функцию для присвоения нового значения указателю, защищенному RCU, чтобы безопасно передать изменение значения от средства обновления читателю. Эта функция возвращает новое значение, а также выполняет все инструкции барьера памяти , необходимые для данной архитектуры ЦП. Возможно, что еще более важно, он служит для документирования того, какие указатели защищены RCU.
  • rcu_dereference(): читатель использует rcu_dereference для получения указателя, защищенного RCU, который возвращает значение, которое затем можно безопасно разыменовать. Он также выполняет любые директивы, необходимые компилятору или ЦП, например, изменчивое приведение для gcc, загрузку Memory_order_consume для C/C++11 или инструкцию ограничения памяти, необходимую для старого ЦП DEC Alpha. Значение, возвращаемое rcu_dereference действителен только в пределах критической секции стороны чтения, содержащейся в RCU. Как и в случае с rcu_assign_pointer, важная функция rcu_dereference заключается в документировании того, какие указатели защищены RCU.
Связь API RCU между считывателем, средством обновления и восстановителем

На диаграмме справа показано, как каждый API взаимодействует между средством чтения, средством обновления и средством восстановления.

Инфраструктура RCU наблюдает за временной последовательностью rcu_read_lock, rcu_read_unlock, synchronize_rcu, и call_rcu вызовы, чтобы определить, когда (1) synchronize_rcu вызовы могут вернуться к вызывающему абоненту и (2) call_rcu могут быть вызваны обратные вызовы. В эффективных реализациях инфраструктуры RCU интенсивно используется пакетная обработка, чтобы амортизировать накладные расходы при многократном использовании соответствующих API.

Простая реализация

[ редактировать ]

RCU имеет чрезвычайно простые «игрушечные» реализации, которые могут помочь в понимании RCU. В этом разделе представлена ​​одна такая «игрушечная» реализация, работающая в невытесняющей среде . [22] 

void rcu_read_lock(void) { }

void rcu_read_unlock(void) { }

void call_rcu(void (*callback) (void *), void *arg)
{
    // add callback/arg pair to a list
}

void synchronize_rcu(void)
{
    int cpu, ncpus = 0;

    for each_cpu(cpu)
        schedule_current_task_to(cpu);

    for each entry in the call_rcu list
        entry->callback (entry->arg);
}

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

#define rcu_assign_pointer(p, v) ({ \
    smp_wmb(); /* Order previous writes. */ \
    ACCESS_ONCE(p) = (v); \
})

#define rcu_dereference(p) ({ \
    typeof(p) _value = ACCESS_ONCE(p); \
    smp_read_barrier_depends(); /* nop on most architectures */ \
    (_value); \
})

Обратите внимание, что rcu_read_lock и rcu_read_unlock ничего не делать. В этом большая сила классического RCU в невытесняющем ядре: накладные расходы на чтение равны нулю, поскольку smp_read_barrier_depends() — пустой макрос для всех кроме DEC Alpha ; процессоров, [23] [ не удалось пройти проверку ] такие барьеры памяти не нужны современным процессорам. ACCESS_ONCE() макрос — это изменчивое приведение типов, которое в большинстве случаев не генерирует дополнительный код. И нет никакого способа, чтобы rcu_read_lock может участвовать в цикле взаимоблокировки , вызывать нарушение крайнего срока планирования процессом реального времени, ускорять инверсию приоритета или приводить к высокой конкуренции за блокировки . Однако в этой игрушечной реализации RCU блокировка внутри критической секции на стороне чтения RCU незаконна, так же как и блокировка при удержании чистой спин-блокировки.

Осуществление synchronize_rcu перемещает вызывающую сторону синхронизации_cpu к каждому процессору, блокируя таким образом до тех пор, пока все процессоры не смогут выполнить переключение контекста. Напомним, что это среда без вытеснения и что блокировка в критическом разделе на стороне чтения RCU является незаконной, что означает, что в критическом разделе на стороне чтения RCU не может быть никаких точек вытеснения. Следовательно, если данный ЦП выполняет переключение контекста (чтобы запланировать другой процесс), мы знаем, что этот ЦП должен завершить все предыдущие критические разделы на стороне чтения RCU. Как только все ЦП выполнят переключение контекста, все предыдущие критические секции на стороне чтения RCU будут завершены.

Аналогия с блокировкой чтения и записи.

[ редактировать ]

Хотя RCU можно использовать по-разному, наиболее распространенное использование RCU аналогично блокировке чтения-записи. Следующее параллельное отображение кода показывает, насколько тесно могут быть связаны блокировка чтения-записи и RCU. [24] 

   /* reader-writer locking */              /* RCU */

 1 struct el {                            1 struct el {
 2   struct list_head lp;                 2   struct list_head lp;
 3   long key;                            3   long key;
 4   spinlock_t mutex;                    4   spinlock_t mutex;
 5   int data;                            5   int data;
 6   /* Other data fields */              6   /* Other data fields */
 7 };                                     7 };
 8 DEFINE_RWLOCK(listmutex);              8 DEFINE_SPINLOCK(listmutex);
 9 LIST_HEAD(head);                       9 LIST_HEAD(head);

 1 int search(long key, int *result)      1 int search(long key, int *result)
 2 {                                      2 {
 3   struct el *p;                        3   struct el *p;
 4                                        4
 5   read_lock(&listmutex);               5   rcu_read_lock();
 6   list_for_each_entry(p, &head, lp) {  6   list_for_each_entry_rcu(p, &head, lp) {
 7     if (p->key == key) {               7     if (p->key == key) {
 8       *result = p->data;               8       *result = p->data;
 9       read_unlock(&listmutex);         9       rcu_read_unlock();
10       return 1;                       10       return 1;
11     }                                 11     }
12   }                                   12   }
13   read_unlock(&listmutex);            13   rcu_read_unlock();
14   return 0;                           14   return 0;
15 }                                     15 }

 1 int delete(long key)                   1 int delete(long key)
 2 {                                      2 {
 3   struct el *p;                        3   struct el *p;
 4                                        4
 5   write_lock(&listmutex);              5   spin_lock(&listmutex);
 6   list_for_each_entry(p, &head, lp) {  6   list_for_each_entry(p, &head, lp) {
 7     if (p->key == key) {               7     if (p->key == key) {
 8       list_del(&p->lp);                8       list_del_rcu(&p->lp);
 9       write_unlock(&listmutex);        9       spin_unlock(&listmutex);
                                         10       synchronize_rcu();
10       kfree(p);                       11       kfree(p);
11       return 1;                       12       return 1;
12     }                                 13     }
13   }                                   14   }
14   write_unlock(&listmutex);           15   spin_unlock(&listmutex);
15   return 0;                           16   return 0;
16 }                                     17 }

Различия между этими двумя подходами весьма невелики. Блокировка стороны чтения перемещается в rcu_read_lock и rcu_read_unlock, блокировка на стороне обновления переходит от блокировки чтения-записи к простой спин-блокировке, а synchronize_rcu предшествует kfree.

Однако есть одна потенциальная загвоздка: критические разделы на стороне чтения и на стороне обновления теперь могут работать одновременно. Во многих случаях это не будет проблемой, но все равно необходимо тщательно проверить. Например, если несколько независимых обновлений списка должны рассматриваться как одно атомарное обновление, преобразование в RCU потребует особой осторожности.

Также наличие synchronize_rcu означает, что версия RCU delete теперь могу заблокировать. Если это проблема, call_rcu можно использовать как call_rcu (kfree, p) вместо synchronize_rcu. Это особенно полезно в сочетании с подсчетом ссылок.

История

[ редактировать ]

Техники и механизмы, напоминающие RCU, изобретались независимо несколько раз: [25]

  1. Х. Т. Кунг и К. Леман описали использование сборщиков мусора для реализации доступа к бинарному дереву поиска, подобного RCU. [26]
  2. Уди Манбер и Ричард Ладнер распространили работу Куна и Лемана на среды без сбора мусора, отложив восстановление до тех пор, пока все потоки, работающие во время удаления, не завершатся, что работает в средах, где нет долгоживущих потоков. [27]
  3. Ричард Рашид и др. описал реализацию резервного буфера отложенной трансляции (TLB), которая откладывала освобождение виртуального адресного пространства до тех пор, пока все процессоры не очистили свои TLB, что по духу похоже на некоторые реализации RCU. [28]
  4. Джеймс П. Хеннесси, Дамиан Л. Осисек и Джозеф В. Сей II получили патент США № 4 809 168 в 1989 году (срок действия которого истек). Этот патент описывает механизм, подобный RCU, который, по-видимому, использовался в VM/XA на мэйнфреймах IBM . [29]
  5. Уильям Пью описал механизм, подобный RCU, который основан на явной установке флагов читателями. [30]
  6. Аджу Джон предложил реализацию, подобную RCU, в которой средства обновления просто ждут фиксированный период времени, предполагая, что все читатели завершат работу в течение этого фиксированного времени, что может быть уместно в системе жесткого реального времени. [31] Ван Джейкобсон предложил аналогичную схему в 1993 году (вербальное общение).
  7. Дж. Слингвайн и П. Е. Маккенни получили в августе 1995 года патент США № 5 442 758, в котором описан RCU, реализованный в DYNIX/ptx , а затем и в ядре Linux. [32]
  8. Б. Гамса, О. Кригер, Дж. Аппаву и М. Штумм описали механизм, подобный RCU, используемый в Университета Торонто исследовательской операционной системе Tornado и тесно связанных с ней IBM Research K42 . исследовательских операционных системах [33]
  9. Расти Рассел и Фил Румпф описали RCU-подобные методы обработки выгрузки модулей ядра Linux. [34] [35]
  10. Д. Сарма добавил RCU в версию 2.5.43 ядра Linux в октябре 2002 года.
  11. Роберт Колвин и др. формально проверен ленивый параллельный алгоритм набора на основе списков, напоминающий RCU. [36]
  12. М. Деснуайерс и др. опубликовал описание пользовательского пространства RCU. [37] [38]
  13. А. Гоцман и др. выведена формальная семантика для RCU на основе логики разделения. [39]
  14. Илан Френкель, Роман Геллер, Йорам Рамберг и Йорам Снир получили патент США № 7 099 932 в 2006 году. Этот патент описывает механизм, подобный RCU, для получения и хранения информации управления политикой качества обслуживания с использованием службы каталогов таким образом, чтобы обеспечить чтение/запись. согласованность и обеспечивает параллелизм чтения/записи. [40]

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Необходимо учитывать только считыватели, которые активны на этапе удаления, поскольку любое считывающее устройство, начавшееся после этапа удаления, не сможет получить ссылку на удаленные элементы данных и, следовательно, не может быть прервано этапом восстановления.
  2. ^ сборщики мусора , если таковые имеются. Для выполнения этого шага можно использовать
  3. ^ Взаимные блокировки на основе RCU все еще возможны, например, при выполнении оператора, который блокируется до тех пор, пока не завершится льготный период в критическом разделе на стороне чтения RCU.

Ссылки

[ редактировать ]
  1. ^ Jump up to: а б Таненбаум, Эндрю (2015). Современные операционные системы (4-е изд.). США: Пирсон. п. 148. ИСБН  9781292061429 .
  2. ^ Гунигунтала, Динакар; Маккенни, Пол Э.; Триплетт, Джошуа; Уолпол, Джонатан (апрель – июнь 2008 г.). «Механизм чтения-копирования-обновления для поддержки приложений реального времени в многопроцессорных системах с общей памятью под управлением Linux». IBM Systems Journal . 47 (2): 221–236. дои : 10.1147/sj.472.0221 .
  3. ^ Маккенни, Пол Э.; Уолпол, Джонатан (17 декабря 2007 г.). «Что такое RCU по сути?» . Еженедельные новости Linux . Проверено 24 сентября 2010 г.
  4. ^ Маккенни, Пол Э.; Слингвейн, Джон Д. (октябрь 1998 г.). Обновление для чтения и копирования: использование истории выполнения для решения проблем параллелизма (PDF) . Параллельные и распределенные вычисления и системы . стр. 509–518. {{cite conference}}: Внешняя ссылка в |journal= ( помощь )
  5. ^ Наама Бен-Давид; Гай Э. Блелох; Ихань Сунь; Юаньхао Вэй. «Эффективный параллелизм с одним автором» .
  6. ^ «Многопоточность без блокировки с атомарными операциями» .
  7. ^ Эдди Колер. «Примечания по обновлению чтения-копирования» . цитата: «Для управления конфликтами записи-записи большинство структур данных RCU используют регулярную блокировку».
  8. ^ Маккенни, Пол Э.; Уолпол, Джонатан (июль 2008 г.). «Внедрение технологии в ядро ​​Linux: практический пример». СИГОПС Опер. Сист. Преподобный . 42 (5): 4–17. дои : 10.1145/1400097.1400099 . S2CID   12748421 .
  9. ^ Олссон, Роберт; Нильссон, Стефан (май 2007 г.). «TRASH - динамическая структура LC-trie и хэш-данных». 2007 Семинар по высокопроизводительной коммутации и маршрутизации . стр. 1–6. дои : 10.1109/HPSR.2007.4281239 . ISBN  978-1-4244-1205-1 . S2CID   17493674 .
  10. ^ Пиггин, Ник (июль 2006 г.). Lockless Pagecache в Linux — Введение, прогресс, производительность . Оттавский симпозиум по Linux .
  11. ^ «Пол Э. Маккенни: Использование RCU Linux» .
  12. ^ Каннан, Хари (2009). «Упорядочение разделенного доступа к метаданным в многопроцессорах». Материалы 42-го ежегодного международного симпозиума IEEE/ACM по микроархитектуре — Micro-42 . стр. 381–390. дои : 10.1145/1669112.1669161 . ISBN  978-1-60558-798-1 . S2CID   2465311 .
  13. ^ Мэтьюз, Крис; Коуди, Ивонн; Аппаву, Джонатан (2009). События переносимости: модель программирования для масштабируемых системных инфраструктур . PLOS '06: Материалы 3-го семинара по языкам программирования и операционным системам . Сан-Хосе, Калифорния, США. дои : 10.1145/1215995.1216006 . ISBN  978-1-59593-577-9 .
  14. ^ Да Силва, Дилма ; Кригер, Орран; Вишневский, Роберт В.; Уотерленд, Амос; Тэм, Дэвид; Бауманн, Эндрю (апрель 2006 г.). «К42: инфраструктура для исследования операционных систем». СИГОПС Опер. Сист. Преподобный . 40 (2): 34–42. дои : 10.1145/1131322.1131333 . S2CID   669053 .
  15. ^ Аппаву, Джонатан; Да Силва, Дилма; Кригер, Орран; Ауслендер, Марк; Островский, Михал; Розенбург, Брайан; Уотерленд, Амос; Вишневский, Роберт В.; Ксенидис, Джими (август 2007 г.). «Опыт распространения объектов в ОС SMMP». Транзакции ACM в компьютерных системах . 25 (3): 1–6 июня 52. дои : 10.1145/1275517.1275518 . S2CID   931202 .
  16. ^ Фрейзер, Кейр; Харрис, Тим (2007). «Параллельное программирование без блокировок». Транзакции ACM в компьютерных системах . 25 (2): 34–42. CiteSeerX   10.1.1.532.5050 . дои : 10.1145/1233307.1233309 . S2CID   3030814 .
  17. ^ Портер, Дональд Э.; Хофманн, Оуэн С.; Россбах, Кристофер Дж.; Бенн, Александр; Витчел, Эммет (2009). «Транзакции операционных систем». Материалы 22-го симпозиума ACM SIGOPS по принципам операционных систем - SOSP '09 . п. 161. дои : 10.1145/1629575.1629591 . hdl : 2152/ETD-UT-2010-12-2488 . ISBN  978-1-60558-752-3 . S2CID   28504 .
  18. ^ Харт, Томас Э.; Маккенни, Пол Э.; Демке Браун, Анджела; Уолпол, Джонатан (декабрь 2007 г.). «Производительность восстановления памяти для блокировки блокировки». Дж. Параллельное распределение. Вычислить . 67 (12): 1270–1285. дои : 10.1016/j.jpdc.2007.04.010 .
  19. ^ Маккенни, Пол Э. (4 января 2008 г.). «RCU часть 2: Использование» . Еженедельные новости Linux . Проверено 24 сентября 2010 г.
  20. ^ Денуайе, Матье (декабрь 2009 г.). Отслеживание операционной системы с низким уровнем воздействия (PDF) . Монреальская политехническая школа (Диссертация).
  21. ^ Маккенни, Пол Э. (17 января 2008 г.). «RCU, часть 3: API RCU» . Еженедельные новости Linux . Проверено 24 сентября 2010 г.
  22. ^ Маккенни, Пол Э.; Аппаву, Джонатан; Кляйн, Энди; Кригер, Орран; Рассел, Расти; Сарма, Дипанкар; Сони, Маниш (июль 2001 г.). Обновление для чтения и копирования (PDF) . Оттавский симпозиум по Linux .
  23. ^ Волшебник, The (август 2001 г.). «Общая память, потоки, межпроцессное взаимодействие» . Хьюлетт-Паккард . Проверено 26 декабря 2010 г.
  24. ^ Маккенни, Пол Э. (октябрь 2003 г.). «Использование {RCU} в ядре {Linux} 2.5» . Linux-журнал . Проверено 24 сентября 2010 г.
  25. ^ Маккенни, Пол Э. (июль 2004 г.). Использование отложенного разрушения: анализ методов чтения-копирования-обновления (PDF) . Школа науки и техники OGI Орегонского университета здравоохранения и наук (диссертация).
  26. ^ Кунг, ХТ; Леман, К. (сентябрь 1980 г.). «Параллельное обслуживание двоичных деревьев поиска». Транзакции ACM в системах баз данных . 5 (3): 354. CiteSeerX   10.1.1.639.8357 . дои : 10.1145/320613.320619 . S2CID   13007648 .
  27. ^ Манбер, Уди; Ладнер, Ричард Э. (сентябрь 1984 г.). «Управление параллелизмом в структуре динамического поиска». Транзакции ACM в системах баз данных . 9 (3).
  28. ^ Рашид, Ричард; Теванян, Авадис; Янг, Майкл; Голуб, Дэвид; Барон, Роберт; Болоски, Уильям; Чу, Джонатан (октябрь 1987 г.). Машинно-независимое управление виртуальной памятью для страничных однопроцессорных и многопроцессорных архитектур (PDF) . Второй симпозиум по архитектурной поддержке языков программирования и операционных систем . Ассоциация вычислительной техники.
  29. ^ США 4809168 , Хеннесси, Джеймс П.; Осисек, Дамиан Л. и Сей II, Джозеф В., «Пассивная сериализация в многозадачной среде», опубликовано в феврале 1989 г.  
  30. ^ Пью, Уильям (июнь 1990 г.). Параллельное ведение списков пропуска (Технический отчет). Институт перспективных исследований в области компьютерных наук, факультет компьютерных наук, Университет Мэриленда. CS-TR-2222.1.
  31. ^ Джон, Аджу (январь 1995 г.). Динамические вноды — проектирование и реализация . USENIX Зима 1995 года .
  32. ^ US 5442758 , Слингвейн, Джон Д. и Маккенни, Пол Э., «Устройство и метод для достижения уменьшенных накладных расходов, взаимного исключения и поддержания согласованности в многопроцессорной системе», опубликовано в августе 1995 г.  
  33. ^ Гамса, Бен; Кригер, Орран; Аппаву, Джонатан; Штумм, Майкл (февраль 1999 г.). Торнадо: максимизация локальности и параллелизма в многопроцессорной операционной системе с общей памятью (PDF) . Материалы третьего симпозиума по проектированию и внедрению операционных систем .
  34. ^ Рассел, Расти (июнь 2000 г.). «Re: модульные сетевые драйверы» . Архивировано из оригинала 31 марта 2012 г. Проверено 1 октября 2010 г.
  35. ^ Рассел, Расти (июнь 2000 г.). «Re: модульные сетевые драйверы» . Архивировано из оригинала 31 марта 2012 г. Проверено 1 октября 2010 г.
  36. ^ Колвин, Роберт; Гроувс, Линдси; Лучанко, Виктор; Мойр, Марк (август 2006 г.). Формальная проверка алгоритма ленивых параллельных наборов на основе списков (PDF) . Компьютерная проверка . Архивировано из оригинала (PDF) 17 июля 2009 г.
  37. ^ Деснуайе, Матье; Маккенни, Пол Э.; Стерн, Алан; Дажене, Мишель Р.; Уолпол, Джонатан (февраль 2012 г.). «Реализация обновления чтения-копирования на уровне пользователя» (PDF) . Транзакции IEEE в параллельных и распределенных системах . 23 (2): 375–382. дои : 10.1109/TPDS.2011.159 . S2CID   832767 .
  38. ^ Маккенни, Пол Э.; Деснуайе, Матье; Цзяншань, Лай (13 ноября 2013 г.). «Пользовательское пространство RCU» . Еженедельные новости Linux . Проверено 17 ноября 2013 г.
  39. ^ Гоцман, Алексей; Ринецкий, Ноам; Ян, Хонсок (16–24 марта 2013 г.). Грамотная проверка алгоритмов одновременного освобождения памяти (PDF) . ESOP'13: Европейский симпозиум по программированию .
  40. ^ США 7099932 , Френкель, Илан; Геллер, Роман и Рамберг, Йорам и др., «Метод и устройство для получения информации о политике качества обслуживания сети из каталога в системе управления политиками качества обслуживания», опубликовано 29 августа 2006 г., передано Cisco Tech Inc.  

Бауэр, RT, (июнь 2009 г.), «Оперативная проверка релятивистской программы», Технический отчет PSU TR-09-04 ( http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/ tr0904.pdf )

[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Read-copy-update&oldid=1220602118"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3f64606ed8dc0754aadef6b5ad7381c3__1713979560
URL1:https://arc.ask3.ru/arc/aa/3f/c3/3f64606ed8dc0754aadef6b5ad7381c3.html
Заголовок, (Title) документа по адресу, URL1:
Read-copy-update - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)