Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Название и обзор [ править ]

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

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

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

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

Подробное описание [ править ]

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

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

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

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

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

Первый государственный показывает связанный список , содержащий элементы , 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) выше), часто полезно подумать о них. раздельно.

Использует [ редактировать ]

К началу 2008 года в ядре Linux [5] использовалось почти 2000 случаев использования RCU API, включая стеки сетевых протоколов [6] и систему управления памятью. [7] По состоянию на март 2014 года было более 9 000 использований. [8] С 2006 года исследователи применяют RCU и аналогичные методы для решения ряда проблем, включая управление метаданными, используемыми в динамическом анализе, [9] управление временем жизни кластеризованных объектов, [10] управление временем жизни объекта в исследовательской операционной системе K42. , [11] [12] и оптимизация программной реализации транзакционной памяти . [13] [14] Dragonfly 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 (истекшим 2009 г.) -05-18) и 6,886,162 (срок действия истек 25 мая 2009 г.). Патент США 4809168 с истекшим сроком действия охватывает тесно связанный метод. РКО также тема одного иска в 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будет не обязательно ждать каких - либо последующих РКО чтения боковые критические секции для завершения. Например, рассмотрим следующую последовательность событий:
 ЦП 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_read_lock, rcu_read_unlock, synchronize_rcuи call_rcuвызовов , с тем чтобы определить , когда (1) synchronize_rcuвызовы могут вернуться к своим абонентам и (2) call_rcuобратные вызовы могут быть вызваны. В эффективных реализациях инфраструктуры RCU интенсивно используется пакетная обработка, чтобы компенсировать накладные расходы, связанные с множеством использований соответствующих API.

Простая реализация [ править ]

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

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

В примере кода, 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 (); / * nop на большинстве архитектур * / \  (_value); \ })

Обратите внимание на это 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  struct  el  {  1  struct  el  {  2  struct  list_head  lp ;  2  struct  list_head  lp ;  3  длинных  ключа ;  3  длинных  ключа ;  4  spinlock_t  взаимной блокировки ;  4  spinlock_t  взаимной блокировки ;  5  int  data ;  5  int  data ;  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 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  * результат  =  p -> данные ; 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  delete ( длинный  ключ )  1  int  delete ( длинный  ключ )  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 ( п ); 11 kfree ( p ); 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 deleteтеперь может блокироваться. Если это проблема, call_rcuможно использовать call_rcu (kfree, p)вместо synchronize_rcu. Это особенно полезно в сочетании с подсчетом ссылок.

История [ править ]

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

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

Внешние ссылки [ править ]

  • Пол Э. Маккенни, Матьё Деснуайерс и Лай Цзяншань: RCU пользовательского пространства . Еженедельные новости Linux .
  • Пол Э. Маккенни и Джонатан Уолпол: Что такое RCU в целом? , Что такое RCU? Часть 2: Использование и часть 3 RCU: API RCU . Еженедельные новости Linux .
  • Веб-страница RCU Пола Э. Маккенни
  • Харт, МакКенни и Демке Браун (2006). Создание беззамочные синхронизации Быстрота: Производительность Последствия памяти Рекультивация КПРРП Best Paper 2006 Сравнение производительности РКО на том , что другие механизмы синхронизации беззамочные. Версия журнала (включая Уолпола в качестве автора).
  • Патент США 5,442,758 (1995) «Устройство и способ для достижения уменьшенных накладных расходов, взаимного исключения и поддержания когерентности в многопроцессорной системе с использованием истории выполнения и мониторинга потоков».
  • Пол МакКенни: Сонный RCU . Еженедельные новости Linux .