Работа без блокировок: чтение — копирование — обновление

Самые быстрые блокировки — это отсутствие всяких блокировок. Вопрос в том, можно ли разрешить одновременный доступ для чтения и записи к общим структурам данных без блокировки. Если говорить в общем смысле, то ответ, конечно же, будет отрицательный.
Представим себе, что процесс А сортирует числовой массив, в то же время процесс Б вычисляет среднее значение. Поскольку A перемещает значения по массиву, процессу Б некоторые значения могут попасться несколько раз, а некоторые не встретиться вообще. Результат может быть каким угодно, но, скорее всего, неправильным.

И тем не менее в некоторых случаях можно позволить процессу, ведущему запись, обновить структуру данных, даже если ею пользуются другие процессы. Здесь важно обеспечить, чтобы каждый считывающий процесс читал либо старую, либо новую версию данных, но не некую непонятную комбинацию из старой и новой версий. В качестве иллюстрации рассмотрим дерево, показанное на рис. 2.19. Читатели обходят дерево от корня до листьев. В верхней половине рисунка добавлен новый узел X. Перед тем как сделать этот узел видимым в дереве, мы доводим его до полной готовности: инициализируем все значения в узле X, включая его дочерние указатели. Затем с помощью одной атомарной записи превращаем X в дочерний элемент узла A. Несогласованную версию не сможет считать ни один читатель. В нижней части рисунка последовательно удаляются узлы B и D. Сначала мы перенацеливаем левый дочерний указатель узла A на узел C. Все читатели, попавшие в A, продолжат считывание с узла C и никогда не увидят узел B или D. Иными словами, они увидят только новую версию. В то же время все читатели, находящиеся в этот момент в узле B или D, продолжат чтение, следуя указателям исходной структуры данных, и увидят старую версию. Все будет хорошо, и блокировка вообще не понадобится.

Удаление B и D работает без блокировки структуры данных в основном потому, что RCU (Read — Copy — Update, чтение — копирование — обновление) отделяет фазу удаления от фазы восстановления обновления.

Но есть и проблема. Пока нет уверенности в полном отсутствии читателей в B или D, мы не можем фактически от них избавиться. Но сколько же должно продлиться ожидание? Одну минуту? Десять минут? Мы вынуждены ждать до тех пор, пока эти узлы не оставит последний читатель. RCU обязательно определяет максимальное время, в течение которого читатель может удерживать ссылку на структуру данных. По истечении этого срока память может быть безопасно освобождена. Точнее говоря, читатели получают доступ к структуре данных в области, которая известна как критический раздел чтения (read-side critical section), где может содержаться любой код, поскольку он не заблокирован или не пребывает в режиме ожидания. В этом случае известно максимальное время вынужденного ожидания. А именно нами определяется отсрочка (grace period) в виде любого периода времени, в течение которого известно, что каждый

Рис. 2.19. RCU: вставка узла в дерево с последующим удалением ветви, и все это без блокировок


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

2.4.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Работа без блокировок: чтение — копирование — обновление:

  1. Копирование движений
  2. Копирование движений
  3. БЕЗ СЛЕДОВ, БЕЗ ТЕНИ, БЕЗ ЭГО
  4. Обновление
  5. Обновление
  6. Глава 7 Чудо духовного обновления
  7. Цензура и журналистика при «обновленном строе»
  8. 2. Всестороннее развитие без детской любви – ничто. Гармония с самим собой немыслима без гармонических отношений с другими
  9. ГЛАВА ПЯТАЯ Пришествие - обновление 2004
  10. ЧТЕНИЕ ГУБНОЕ
  11. Чтение между строк
  12. 13.10.1. Раннее чтение
  13. Чтение мысли дня:
  14. Чтение мысли дня:
  15. Чтение мысли дня:
  16. Чтение мысли дня: