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

Read-copy-update

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

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

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

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

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

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

Когда поток, создавший копию, пробуждается ядром, он может безопасно освободить старую структуру.

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

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

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

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

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

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

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

Первое состояние показывает связанный список, содержащий элементы А, B, и C. Все три элемента окрашены в красный цвет, чтобы указать, что считыватель RCU может ссылаться на любой из них в любое время. С помощью list_del_rcu удалить элемент B из этого списка переходит во второе состояние. Обратите внимание, что ссылка от элемента B на C остается нетронутой, чтобы читатели, в настоящее время ссылающиеся на элемент B для перехода к оставшейся части списка. Читатели, получающие доступ к ссылке из элемента А либо получит ссылку на элемент 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) выше), часто полезно подумать о них. раздельно.

Использует

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

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

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

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

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

Патенты

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

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

RCU доступен в ряде операционных систем и был добавлен в Ядро Linux в октябре 2002 года. Реализации на уровне пользователя, такие как Liburcu также доступны.[17]

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

  • rcu_read_lock (): помечает структуру данных, защищенную RCU, так, что она не будет восстановлена ​​в течение всего времени этого критического раздела.
  • rcu_read_unlock (): используется считывателем, чтобы сообщить реклаймеру, что считыватель выходит из критического раздела RCU на стороне чтения. Обратите внимание, что критические разделы RCU на стороне чтения могут быть вложенными и / или перекрываться.
  • synchronize_rcu (): блокируется до тех пор, пока не будут завершены все ранее существовавшие критические разделы на стороне чтения RCU на всех процессорах. Обратите внимание, что synchronize_rcu буду нет обязательно дождитесь завершения всех последующих критических разделов на стороне чтения RCU. Например, рассмотрим следующую последовательность событий:
ЦП 0 ЦП 1 ЦП 2 ----------------- ------------------------- - ------------- 1. rcu_read_lock () 2. входит в synchronize_rcu () 3. rcu_read_lock () 4. rcu_read_unlock () 5. выходит из synchronize_rcu () 6. rcu_read_unlock ()
С synchronize_rcu - это API, который должен понять, когда считыватели закончили, его реализация является ключевой для RCU. Чтобы RCU был полезен во всех ситуациях, кроме наиболее интенсивных по чтению, synchronize_rcuнакладные расходы также должны быть довольно небольшими.
В качестве альтернативы, вместо блокировки, synchronize_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.
Связь RCU API между считывателем, программой обновления и сборщиком

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

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

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

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

пустота rcu_read_lock(пустота) { }пустота rcu_read_unlock(пустота) { }пустота call_rcu(пустота (*Перезвоните) (пустота *), пустота *аргумент){    // добавляем пару callback / arg в список}пустота synchronize_rcu(пустота){    int ЦПУ, ncpus = 0;    за each_cpu(ЦПУ)        schedule_current_task_to(ЦПУ);    за каждый Вход в в call_rcu список        Вход->Перезвоните (Вход->аргумент);}

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

#define rcu_assign_pointer (p, v) ({    smp_wmb (); / * Заказ предыдущей записи. * / \    ACCESS_ONCE (p) = (v); })#define rcu_dereference (p) ({    typeof (p) _value = ACCESS_ONCE (p);     smp_read_barrier_depends (); / * нет на большинстве архитектур * / \    (_ценить); })

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

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

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

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

   / * блокировка чтения и записи * /              / * RCU * / 1 структура эль {                            1 структура эль { 2   структура list_head lp;                 2   структура list_head lp; 3   длинный ключ;                            3   длинный ключ; 4   spinlock_t мьютекс;                    4   spinlock_t мьютекс; 5   int данные;                            5   int данные; 6   / * Другие поля данных * /              6   / * Другие поля данных * / 7 };                                     7 }; 8 DEFINE_RWLOCK(listmutex);              8 DEFINE_SPINLOCK(listmutex); 9 LIST_HEAD(голова);                       9 LIST_HEAD(голова); 1 int поиск(длинный ключ, int *результат)      1 int поиск(длинный ключ, int *результат) 2 {                                      2 { 3   структура эль *п;                        3   структура эль *п; 4                                        4 5   read_lock(&listmutex);               5   rcu_read_lock(); 6   list_for_each_entry(п, &голова, lp) {  6   list_for_each_entry_rcu(п, &голова, lp) { 7     если (п->ключ == ключ) {               7     если (п->ключ == ключ) { 8       *результат = п->данные;               8       *результат = п->данные; 9       read_unlock(&listmutex);         9       rcu_read_unlock();10       возвращаться 1;                       10       возвращаться 1;11     }                                 11     }12   }                                   12   }13   read_unlock(&listmutex);            13   rcu_read_unlock();14   возвращаться 0;                           14   возвращаться 0;15 }                                     15 } 1 int Удалить(длинный ключ)                   1 int Удалить(длинный ключ) 2 {                                      2 { 3   структура эль *п;                        3   структура эль *п; 4                                        4 5   write_lock(&listmutex);              5   spin_lock(&listmutex); 6   list_for_each_entry(п, &голова, lp) {  6   list_for_each_entry(п, &голова, lp) { 7     если (п->ключ == ключ) {               7     если (п->ключ == ключ) { 8       list_del(&п->lp);                8       list_del_rcu(&п->lp); 9       write_unlock(&listmutex);        9       spin_unlock(&listmutex);                                         10       synchronize_rcu();10       kfree(п);                       11       kfree(п);11       возвращаться 1;                       12       возвращаться 1;12     }                                 13     }13   }                                   14   }14   write_unlock(&listmutex);           15   spin_unlock(&listmutex);15   возвращаться 0;                           16   возвращаться 0;16 }                                     17 }

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

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

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

История

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

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

Смотрите также

Примечания

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

Рекомендации

  1. ^ а б Таненбаум, Эндрю (2015). Современные операционные системы (4-е изд.). США: Пирсон. п. 148. ISBN 9781292061429.
  2. ^ Гунигунтала, Динакар; Маккенни, Пол Э .; Триплетт, Джошуа; Уолпол, Джонатан (апрель – июнь 2008 г.). «Механизм чтения-копирования-обновления для поддержки приложений реального времени в многопроцессорных системах с общей памятью и Linux». Журнал IBM Systems. 47 (2): 221–236. Дои:10.1147 / sj.472.0221.
  3. ^ Маккенни, Пол Э .; Уолпол, Джонатан (17 декабря 2007 г.). «Что такое RCU, по сути?». Еженедельные новости Linux. Получено 24 сентября, 2010.
  4. ^ Маккенни, Пол Э .; Slingwine, Джон Д. (октябрь 1998 г.). Обновление для чтения и копирования: использование истории выполнения для решения проблем параллелизма (PDF). Параллельные и распределенные вычисления и системы. С. 509–518. Внешняя ссылка в | журнал = (помощь)
  5. ^ Маккенни, Пол Э .; Уолпол, Джонатан (июль 2008 г.). «Внедрение технологии в ядро ​​Linux: пример из практики». SIGOPS Oper. Syst. Rev. 42 (5): 4–17. Дои:10.1145/1400097.1400099.
  6. ^ Ольссон, Роберт; Нильссон, Стефан (май 2007 г.). TRASH: динамическая структура LC-дерева и хэш-таблицы.. Семинар по высокопроизводительной коммутации и маршрутизации (HPSR'07). Дои:10.1109 / HPSR.2007.4281239.
  7. ^ Пиггин, Ник (июль 2006 г.). Кэш страницы без блокировки в Linux --- Введение, прогресс, производительность. Симпозиум по Linux в Оттаве.
  8. ^ "Пол Э. Маккенни: Использование RCU Linux".
  9. ^ Каннан, Хари (2009). «Упорядочивание доступа к несвязанным метаданным в мультипроцессорах». Материалы 42-го ежегодного международного симпозиума IEEE / ACM по микроархитектуре - Micro-42. п. 381. Дои:10.1145/1669112.1669161. ISBN 978-1-60558-798-1.
  10. ^ Мэтьюз, Крис; Коуди, Ивонн; Аппаву, Джонатан (2009). События переносимости: модель программирования для масштабируемых системных инфраструктур. PLOS '06: Материалы 3-го семинара по языкам программирования и операционным системам. Сан-Хосе, Калифорния, США. Дои:10.1145/1215995.1216006. ISBN 978-1-59593-577-9.
  11. ^ Да Силва, Дилма; Кригер, Орран; Вишневски, Роберт В .; Уотерленд, Амос; Тэм, Дэвид; Бауман, Эндрю (апрель 2006 г.). «K42: инфраструктура для исследования операционных систем». SIGOPS Oper. Syst. Rev. 40 (2): 34–42. Дои:10.1145/1131322.1131333.
  12. ^ Аппаву, Джонатан; Да Силва, Дилма; Кригер, Орран; Ауслендер, Марк; Островски, Михал; Розенбург, Брайан; Уотерленд, Амос; Вишневски, Роберт В .; Ксенидис, Джими (август 2007 г.). «Опыт распределения объектов в ОС SMMP». ACM-транзакции в компьютерных системах. 25 (3): 6/1–6/52. Дои:10.1145/1275517.1275518.
  13. ^ Фрейзер, Кейр; Харрис, Тим (2007). «Параллельное программирование без блокировок». ACM-транзакции в компьютерных системах. 25 (2): 34–42. CiteSeerX 10.1.1.532.5050. Дои:10.1145/1233307.1233309.
  14. ^ Портер, Дональд Э .; Hofmann, Owen S .; Россбах, Кристофер Дж .; Бенн, Александр; Витчел, Эммет (2009). «Операции операционных систем». Материалы 22-го симпозиума ACM SIGOPS по принципам операционных систем - SOSP '09. п. 161. Дои:10.1145/1629575.1629591. ISBN 978-1-60558-752-3.
  15. ^ Харт, Томас Э .; Маккенни, Пол Э .; Демке Браун, Анджела; Уолпол, Джонатан (декабрь 2007 г.). «Выполнение рекуперации памяти для безблокирующей синхронизации». J. Parallel Distrib. Вычислить. 67 (12): 1270–1285. Дои:10.1016 / j.jpdc.2007.04.010.
  16. ^ Маккенни, Пол Э. (4 января 2008 г.). «RCU, часть 2: использование». Еженедельные новости Linux. Получено 24 сентября, 2010.
  17. ^ Деснуайе, Матье (декабрь 2009 г.). Трассировка операционной системы с низким уровнем воздействия (PDF). École Polytechnique de Montreal (Тезис).
  18. ^ Маккенни, Пол Э. (17 января 2008 г.). «RCU, часть 3: RCU API». Еженедельные новости Linux. Получено 24 сентября, 2010.
  19. ^ Маккенни, Пол Э .; Аппаву, Джонатан; Клин, Энди; Кригер, Орран; Рассел, Расти; Сарма, Дипанкар; Сони, Маниш (июль 2001 г.). Чтение-копирование обновления (PDF). Симпозиум по Linux в Оттаве.
  20. ^ Волшебник, The (август 2001 г.). «Общая память, потоки, межпроцессное взаимодействие». Hewlett Packard. Получено 26 декабря, 2010.
  21. ^ Маккенни, Пол Э. (октябрь 2003 г.). "Использование {RCU} в ядре {Linux} 2.5". Linux журнал. Получено 24 сентября, 2010.
  22. ^ Маккенни, Пол Э. (июль 2004 г.). Использование отложенного уничтожения: анализ методов чтения-копирования-обновления (PDF). Школа науки и инженерии OGI при Орегонском университете здравоохранения и наук (Тезис).
  23. ^ Kung, H.T .; Леман, К. (сентябрь 1980 г.). «Параллельное обслуживание деревьев двоичного поиска». Транзакции ACM в системах баз данных. 5 (3): 354. CiteSeerX 10.1.1.639.8357. Дои:10.1145/320613.320619.
  24. ^ Манбер, Уди; Ladner, Ричард Э. (сентябрь 1984). «Управление параллелизмом в динамической структуре поиска». Транзакции ACM в системах баз данных. 9 (3).
  25. ^ Рашид, Ричард; Теванян, Авадис; Янг, Майкл; Голуб, Давид; Барон, Роберт; Болоски, Уильям; Чу, Джонатан (октябрь 1987 г.). Машинно-независимое управление виртуальной памятью для однопроцессорных и многопроцессорных архитектур с разбивкой на страницы (PDF). Второй симпозиум по архитектурной поддержке языков программирования и операционных систем. Ассоциация вычислительной техники.
  26. ^ США 4809168, «Пассивная сериализация в многозадачной среде» 
  27. ^ Пью, Уильям (июнь 1990 г.). Параллельное ведение списков пропуска (Технический отчет). Институт перспективных компьютерных исследований, факультет компьютерных наук, Мэрилендский университет. CS-TR-2222.1.
  28. ^ Джон, Аджу (январь 1995 г.). Динамические vnodes - дизайн и реализация. USENIX Зима 1995 г..
  29. ^ США 5442758, "Устройство и метод для достижения уменьшения взаимного исключения накладных расходов и поддержания когерентности в многопроцессорной системе" 
  30. ^ Гамса, Бен; Кригер, Орран; Аппаву, Джонатан; Штумм, Майкл (февраль 1999 г.). Tornado: максимизация локальности и параллелизма в многопроцессорной операционной системе с общей памятью (PDF). Труды третьего симпозиума по разработке и внедрению операционных систем.
  31. ^ Рассел, Расти (июнь 2000 г.). "Re: модульные сетевые драйверы".
  32. ^ Рассел, Расти (июнь 2000 г.). "Re: модульные сетевые драйверы".
  33. ^ Колвин, Роберт; Гровс, Линдси; Лучангко, Виктор; Мойр, Марк06 (август 2006 г.). Формальная проверка алгоритма отложенного параллельного набора на основе списков (PDF). Компьютерная проверка (CAV 2006). Архивировано из оригинал (PDF) 17 июля 2009 г.
  34. ^ Деснуайе, Матьё; Маккенни, Пол Э .; Стерн, Алан; Dagenais, Michel R .; Уолпол, Джонатан (февраль 2012 г.). Реализации обновления для чтения и копирования на уровне пользователя (PDF). Транзакции IEEE в параллельных и распределенных системах. Дои:10.1109 / TPDS.2011.159.
  35. ^ Маккенни, Пол Э .; Деснуайе, Матьё; Цзяншань, Лай (13 ноября 2013 г.). «Пользовательское пространство RCU». Еженедельные новости Linux. Получено 17 ноября, 2013.
  36. ^ Гоцман Алексей; Ринецки, Ноам; Ян, Хонсок (16–24 марта 2013 г.). Изящная проверка параллельных алгоритмов восстановления памяти (PDF). ESOP'13: Европейский симпозиум по программированию.
  37. ^ США 7099932, Френкель, Илан; Геллер, Роман и Рамберг, Йорам и др. «Метод и устройство для извлечения информации о политике качества обслуживания в сети из каталога в системе управления политикой качества обслуживания», опубликовано 29 августа 2006 г., передано Cisco Tech Inc. 

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

внешняя ссылка