Модель согласованности - Consistency model

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

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

Языки высокого уровня, Такие как C ++ и Ява, частично поддерживать контракт, переводя операции с памятью в операции низкого уровня таким образом, чтобы сохранить семантика памяти. Для выполнения контракта компиляторы могут переупорядочить некоторые инструкции памяти и вызовы библиотек, такие как pthread_mutex_lock () инкапсулировать требуемую синхронизацию.^[1]

Проверка последовательная последовательность через проверка модели является неразрешимый в общем, даже для конечных состояний согласованность кеша протоколы.^[2]

Модели согласованности определяют правила для очевидного порядка и видимости обновлений и находятся на континуум с компромиссами.^[3]

Пример

Предположим, что имеет место следующий случай:^[3]

• Строка X реплицируется на узлах M и N.
• Клиент A записывает строку X в узел M
• По прошествии периода времени t клиент B считывает строку X из узла N

Модель согласованности должна определять, видит ли клиент B запись, выполненную клиентом A, или нет.

Типы

Есть два метода определения и категоризации моделей согласованности; выпуск и просмотр.

Проблема

Метод задачи описывает ограничения, которые определяют, как процесс может выполнять операции.

Вид

View метод, который определяет порядок операций, видимых процессам.

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

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

Строгая последовательность

Строгая согласованность - самая сильная модель согласованности. Согласно этой модели, запись в переменную любым процессором должна быть мгновенно видна всем процессорам.

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

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

Последовательная согласованность

В последовательная последовательность модель была предложена Лэмпортом (1979). Это более слабая модель памяти, чем модель строгой согласованности. Запись в переменную не должна происходить мгновенно, однако записи в переменные разными процессорами должны выполняться всеми процессорами в одном и том же порядке. По определению Лэмпорта (1979),^[4] последовательная согласованность достигается, если «результат любого выполнения такой же, как если бы операции всех процессоров были выполнены в некотором последовательном порядке, и операции каждого отдельного процессора появляются в этой последовательности в порядке, указанном его программой».

Следует поддерживать порядок программ внутри каждого процессора и последовательный порядок операций между процессорами. Чтобы сохранить последовательный порядок выполнения между процессорами, все операции должны выполняться мгновенно или атомарно по отношению к любому другому процессору. Эти операции должны только «казаться» завершенными, потому что физически невозможно мгновенно отправить информацию. Например, в системе, использующей одну глобально разделяемую шину, как только линия шины отправлена ​​с информацией, гарантируется, что все процессоры увидят информацию в один и тот же момент. Таким образом, передача информации на шину завершает выполнение по отношению ко всем процессорам и выглядит как выполненная. Архитектуры без кэша или кэшированные архитектуры с межсетевыми соединениями, которые не являются мгновенными, могут содержать медленный путь между процессорами и памятью. Эти медленные пути могут привести к последовательной несогласованности, потому что одни блоки памяти получают широковещательные данные быстрее, чем другие.

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

Линеаризуемость (также известная как атомарная согласованность) может быть определена как последовательная согласованность с ограничением в реальном времени.

Причинная последовательность

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

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

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

W₁ не связана причинно с W₂. R1 будет последовательно противоречивый но это причинно последовательный.^{[требуется разъяснение ][5]}

W (x) 1 и W (x) 2 причинно связаны из-за того, что P2 считывает x перед W (x) 2.^[5]

Согласованность процессора

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

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

Модель согласованности процессора^[6] похоже на Последовательность PRAM Модель с более строгим условием, определяющим все записи в одну и ту же ячейку памяти, должна просматриваться в одном и том же последовательном порядке всеми другими процессами. Согласованность процессора слабее, чем последовательная согласованность, но сильнее, чем модель согласованности PRAM.

В Многопроцессорная система Stanford DASH реализует вариант согласованности процессора, который несравним (ни слабее, ни сильнее) с определениями Гудмана.^[7] Все процессоры должны быть согласованы в порядке, в котором они видят записи одним процессором, и в том, как они видят записи, сделанные разными процессорами в одно и то же место. Однако они не обязательно должны быть согласованными, если записи производятся разными процессорами в разные места.

Конвейерная согласованность RAM или согласованность FIFO

Конвейерная согласованность RAM (Согласованность PRAM) была представлена ​​Lipton и Sandberg в 1988 г.^[8] как одна из первых описанных моделей согласованности. Из-за неформального определения, на самом деле существует как минимум две слегка разных реализации:^[7] один от Ахамада и др. и один Мосбергер.

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

Согласованность кеша

Согласованность кеша^[6][9] требует, чтобы все операции записи в одну и ту же ячейку памяти выполнялись в некотором последовательном порядке. Согласованность кэша слабее, чем согласованность процесса, и несопоставима с согласованностью PRAM.

Медленная консистенция

Медленная память

В медленной последовательности,^[9] если процесс считывает значение, ранее записанное в ячейку памяти, он не может впоследствии прочитать какое-либо более раннее значение из этой ячейки. Записи, выполненные процессом, немедленно видны этому процессу. Медленная согласованность - более слабая модель, чем PRAM и согласованность кеша.

Пример:Диаграмма медленной памяти показывает пример медленной согласованности. Первый процесс записывает 1 в ячейку памяти X, а затем записывает 1 в ячейку памяти Y. Второй процесс считывает 1 из Y, а затем читает 0 из X, даже если X был записан до Y.

Хатто, Филипп В. и Мустак Ахамад (1990)^[10] проиллюстрируйте, что при соответствующем программировании медленная память (согласованность) может быть выразительной и эффективной. Они упоминают, что медленная память имеет два ценных свойства; локальность и поддерживающая редукция из атомарной памяти. Они предлагают два алгоритма для демонстрации выразительности медленной памяти.

Следующие модели требуют специальной синхронизации программистами.

Слабый порядок

Программный порядок и атомарность поддерживаются только для группы операций, а не для всех операций чтения и записи. Это было основано на понимании того, что определенные операции с памятью - например, выполняемые в критической секции - не обязательно должны быть видны всем процессорам - например, до тех пор, пока не будут завершены все операции в критической секции. Он также использует тот факт, что программы, написанные для выполнения в многопроцессорной системе, содержат необходимую синхронизацию, чтобы гарантировать, что не происходит скачков данных и всегда создаются результаты SC. Таким образом, при слабом порядке операции, отличные от операций синхронизации, можно классифицировать как данные операции.^[11]

Х = 1;изгородь xready = 1;

изгородьпока (! xready) {}; изгородь у = 2;

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

В программе очень часто используется явная синхронизация. Для моделей со слабым упорядочением программист должен использовать инструкции атомарной блокировки, такие как test-and-set, fetch-and-op, store conditional, load connected, или должен помечать переменные синхронизации или использовать ограждения.

Последовательность выпуска

В согласованность выпуска Модель ослабляет модель слабой согласованности, отделяя операцию синхронизации входа от операции синхронизации выхода. При слабом порядке, когда должна быть видна операция синхронизации, все операции во всех процессорах должны быть видны до того, как операция синхронизации будет выполнена и процессор продолжит работу. Однако в рамках модели согласованности выпуска во время входа в критическую секцию, называемую «получение», все операции с переменными локальной памяти должны быть завершены. Во время выхода, называемого «выпуском», все изменения, сделанные локальным процессором, должны распространяться на все другие процессоры. Согласованность сохраняется.

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

Среди переменных синхронизации может поддерживаться последовательная согласованность или согласованность процессора. Используя SC, все конкурирующие переменные синхронизации должны быть обработаны по порядку. Однако в случае с ПК пара конкурирующих переменных должна следовать только этому порядку. Более молодые приобретения могут происходить до более старых выпусков.^[12]

Последовательность входа

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

Общая согласованность

В целом согласованность,^[13] все копии области памяти в конечном итоге становятся идентичными после завершения записи всех процессов.

Локальная согласованность

В локальной последовательности,^[9] каждый процесс выполняет свои собственные операции в порядке, определенном его программой. Нет ограничений на порядок выполнения операций записи других процессов. Локальная согласованность - самая слабая модель согласованности в системах с общей памятью.

Другие модели согласованности

Вот некоторые другие модели согласованности:

• Причинная + последовательность^[14][15]
• Дельта-согласованность
• Конечная последовательность
• Консистенция вилки
• Возможность сериализации в одну копию
• Сериализуемость
• Согласованность векторного поля
• Слабая консистенция
• Сильная консистенция

Несколько других моделей согласованности были задуманы для выражения ограничений в отношении порядка или видимости операций или для работы с конкретными допущениями об ошибках.^[16]

Расслабленные модели согласованности памяти

Некоторые разные модели согласованности можно определить, ослабив одно или несколько требований в последовательная последовательность называется моделями расслабленной согласованности.^[17] Эти модели согласованности не обеспечивают согласованности памяти на аппаратном уровне. Фактически, программисты несут ответственность за обеспечение согласованности памяти путем применения методов синхронизации. Вышеупомянутые модели классифицируются по четырем критериям и детализируются далее.

Есть четыре сравнения для определения расслабленной согласованности:

Расслабление

Один из способов классифицировать ослабленную согласованность - определить, какие требования к последовательной согласованности ослаблены. Мы можем иметь менее строгие модели, ослабив либо порядок программ, либо записав требования атомарности, определенные Adve и Gharachorloo, 1996.^[18] Программный порядок гарантирует, что каждый процесс выдает запрос памяти, упорядоченный его программой, а атомарность записи определяет, что запросы памяти обслуживаются на основе порядка одной очереди FIFO. При ослаблении порядка выполнения программы любой или все упорядочение пар операций, запись-после-запись, чтение-после-запись или чтение / запись-после-чтения, может быть ослаблено. В модели ослабленной атомарности записи процесс может просматривать свои записи раньше, чем другие процессоры.

Синхронизация и несинхронизация

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

Проблемы и просмотры

^[9] Метод Issue обеспечивает имитацию последовательной согласованности, определяя ограничения для процессов, выполняющих операции с памятью. Принимая во внимание, что метод просмотра описывает ограничения видимости для порядка событий для процессов.

Относительная сила модели

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

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

Возможные релаксации:

• Напишите, чтобы прочитать порядок программы
• Напишите, чтобы написать порядок программ
• Читать, чтобы читать, и читать, чтобы писать программные заказы

Модели релаксации

Следующие модели представляют собой некоторые модели расслабленной консистенции:

Расслабленное письмо, чтобы прочитать

Подход к повышению производительности на аппаратном уровне заключается в ослаблении PO записи с последующим чтением, которое эффективно скрывает задержку операций записи. Оптимизация, на которую опирается этот тип ослабления, заключается в том, что он позволяет последующим операциям чтения быть в расслабленном порядке по сравнению с предыдущими записями из процессора. Из-за этого расслабления некоторые программы, такие как XXX, могут не дать результатов SC из-за этого расслабления. Принимая во внимание, что такие программы, как YYY, по-прежнему должны давать стабильные результаты из-за соблюдения оставшихся ограничений порядка выполнения программы.

Под эту категорию попадают три модели. Модель IBM 370 - самая строгая модель. Чтение может быть завершено до более ранней записи по другому адресу, но запрещается возвращать значение записи, если все процессоры не увидели запись. Модель общей модели заказа хранилища (TSO) SPARC V8 частично ослабляет модель IBM 370, она позволяет считыванию возвращать значение записи собственного процессора по отношению к другим операциям записи в то же место, то есть возвращает значение собственной записи перед другие видят это. Как и в предыдущей модели, он не может вернуть значение записи, если все процессоры не увидели запись. Модель согласованности процессора (ПК) является наиболее упрощенной из трех моделей и снимает оба ограничения, так что чтение может завершиться до более ранней записи, даже до того, как оно станет видимым для других процессоров.

В примере A результат возможен только в IBM 370, потому что чтение (A) не выполняется до тех пор, пока запись (A) в этом процессоре не завершится. С другой стороны, этот результат возможен в TSO и PC, поскольку они позволяют считывать флаги перед записью флагов в одном процессоре.

В примере B результат возможен только с ПК, поскольку он позволяет P2 возвращать значение записи даже до того, как оно станет видимым для P3. В двух других моделях это невозможно.

Чтобы обеспечить последовательную согласованность в приведенных выше моделях, используются страховочные сетки или ограждения, чтобы вручную обеспечить соблюдение ограничения. Модель IBM370 имеет несколько специализированных инструкции по сериализации которые размещаются вручную между операциями. Эти инструкции могут состоять из инструкций памяти или инструкций, не относящихся к памяти, таких как ветви. С другой стороны, модели TSO и PC не обеспечивают сетей безопасности, но программисты по-прежнему могут использовать операции чтения-изменения-записи, чтобы все выглядело так, как будто программный порядок все еще сохраняется между записью и последующим чтением. В случае TSO, PO, по-видимому, сохраняется, если R или W, которые уже являются частью R-modify-W, заменяются R-modify-W, для этого требуется, чтобы W в R-modify-W был 'пустышка', возвращающая прочитанное значение. Аналогично для ПК, PO, кажется, сохраняется, если чтение заменено записью или уже является частью R-modify-W.

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

Спокойно писать, чтобы читать, и писать, чтобы писать

Некоторые модели еще больше ослабляют порядок программ, ослабляя даже ограничения на порядок между записью в разные места. Модель частичного заказа в магазине SPARC V8 (PSO) - единственный пример такой модели. Возможность конвейерной и перекрывающейся записи в разные места от одного и того же процессора - это ключевая оптимизация оборудования, обеспечиваемая PSO. PSO похож на TSO с точки зрения требований атомарности в том смысле, что он позволяет процессору считывать значение своей собственной записи и предотвращает чтение другими процессорами записи другого процессора до того, как запись станет видимой для всех других процессоров. Программный порядок между двумя операциями записи поддерживается PSO с помощью явной инструкции STBAR. STBAR вставляется в буфер записи в реализациях с буферами записи FIFO. Счетчик используется для определения, когда все записи до инструкции STBAR были завершены, что запускает запись в систему памяти для увеличения счетчика. Подтверждение записи уменьшает счетчик, и когда счетчик становится 0, это означает, что все предыдущие записи завершены.

В примерах A и B PSO допускает оба этих непоследовательно согласованных результата. Сеть безопасности, которую предоставляет PSO, аналогична TSO, она устанавливает порядок выполнения программы от записи до чтения и обеспечивает атомарность записи.

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

Расслабляющее чтение и чтение для написания программных заказов

В некоторых моделях все операции с разными местами упрощены. Чтение или запись могут быть переупорядочены относительно другого чтения или записи в другом месте. В слабый порядок могут быть отнесены к этой категории, и два типа моделей согласованности выпуска (RCsc и RCpc) также подпадают под эту модель. В рамках этой категории релаксации также предлагаются три коммерческие архитектуры: модели Digital Alpha, SPARC V9 с ослабленным порядком памяти (RMO) и модели IBM PowerPC. Все эти модели позволяют переупорядочивать считывания в одно и то же место, кроме Digital Alpha. Эти модели нарушают последовательный порядок в примерах A и B. Дополнительное ослабление, разрешенное в этих моделях, которое отсутствует в предыдущих моделях, заключается в том, что операции с памятью, следующие за операцией чтения, могут перекрываться и переупорядочиваться по отношению к чтению. Все эти модели, за исключением RCpc и PowerPC, позволяют при чтении возвращать значение ранней записи другого процессора. С точки зрения программиста, все эти модели должны поддерживать иллюзию атомарности записи, даже если они позволяют процессору считывать собственную запись раньше.

Эти модели можно разделить на две категории в зависимости от типа предоставляемой системы безопасности. Здесь видна необходимость в тщательно написанных программах. Природа синхронизации помогает разделить модели на модели слабого упорядочения, RCsc и RCpc.Модели Alpha, RMO и PowerPC предоставляют ограничительные инструкции, так что порядок программ может быть установлен между различными операциями с памятью.

Слабый порядок

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

Согласованность выпуска: RCsc и RCpc

Существует два типа согласованности выпуска: согласованность выпуска с последовательной согласованностью (RCsc) и согласованность выпуска с согласованностью процессора (RCpc). Последний тип указывает, какой тип согласованности применяется к тем операциям, которые ниже указаны как особые.

Существуют специальные (ср. Обычные) операции с памятью, состоящие из двух классов операций: синхронизировать или же nsync операции. Последние операции не используются для синхронизации; первые являются и состоят из приобретать и релиз операции. Получение фактически представляет собой операцию чтения памяти, используемую для получения доступа к определенному набору общих ячеек. С другой стороны, Release - это операция записи, которая выполняется для предоставления разрешения на доступ к общим расположениям.

Для последовательной согласованности (RCsc) существуют следующие ограничения:

• приобрести → все,
• все → релиз,
• специальный → специальный.

Для согласованности процессора (RCpc) порядок записи для чтения программы ослаблен, имея ограничения:

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

Примечание. Приведенное выше обозначение A → B означает, что если операция A предшествует B в порядке выполнения программы, то порядок выполнения программы применяется.

Альфа, RMO и PowerPC

Эти три коммерческие архитектуры демонстрируют четкие инструкции по ограждению как свою страховочную сетку. Модель Alpha предоставляет два типа инструкций по ограждению: барьер памяти (МБ) и запись барьера памяти (WMB). Операция MB может использоваться для поддержания программного порядка любой операции с памятью до MB с операцией с памятью после барьера. Точно так же WMB поддерживает программный порядок только между записями. Модель RMO SPARC V9 предоставляет инструкцию MEMBAR, которую можно настроить для упорядочивания предыдущих операций чтения и записи относительно будущих операций чтения и записи. Нет необходимости использовать чтение-изменение-запись для достижения этого порядка, потому что инструкция MEMBAR может использоваться для упорядочивания записи относительно последующего чтения. Модель PowerPC использует единственную команду ограничения, называемую инструкцией SYNC. Она похожа на инструкцию MB, но с небольшим исключением, что чтение может происходить вне программного порядка, даже если SYNC помещается между двумя чтениями в одно и то же место. Эта модель также отличается от Alpha и RMO атомарностью. Это позволяет увидеть запись до завершения чтения. Для создания иллюзии атомарности записи может потребоваться комбинация операций чтения, модификации и записи.

Модели транзакционной памяти

Модель транзакционной памяти^[17] представляет собой комбинацию моделей согласованности кэша и согласованности памяти в качестве модели связи для систем с общей памятью, поддерживаемых программным или аппаратным обеспечением; Модель транзакционной памяти обеспечивает как согласованность памяти, так и согласованность кеша. Транзакция - это последовательность операций, выполняемых процессом, преобразующим данные из одного согласованного состояния в другое. Транзакция либо фиксируется при отсутствии конфликта, либо прерывается. В коммитах все изменения видны всем другим процессам, когда транзакция завершена, а при отмене все изменения отменяются. По сравнению с моделями ослабленной согласованности, транзакционная модель проще в использовании и может обеспечить более высокую производительность, чем модель последовательной согласованности.

Последовательность и репликация

Таненбаум и др., 2007^[19] определяет две основные причины тиражирования; надежность и производительность. Надежность может быть достигнута в реплицированной файловой системе путем переключения на другую реплику в случае сбоя текущей реплики. Репликация также защищает данные от повреждения, предоставляя несколько копий данных на разных репликах. Это также улучшает производительность за счет разделения работы. Хотя репликация может улучшить производительность и надежность, она может вызвать проблемы согласованности между несколькими копиями данных. Множественные копии согласованы, если операция чтения возвращает одно и то же значение из всех копий, а операция записи, поскольку одна атомарная операция (транзакция) обновляет все копии до того, как будет выполнена какая-либо другая операция. Таненбаум, Эндрю и Мартен Ван Стин, 2007 г.^[19] называют этот тип согласованности плотная консистенция обеспечивается синхронной репликацией. Однако применение глобальной синхронизации для обеспечения согласованности всех копий обходится дорого. Одним из способов снизить стоимость глобальной синхронизации и улучшить производительность может быть ослабление ограничений согласованности.

Модели согласованности, ориентированные на данные

Таненбаум и др., 2007^[19] определяет модель согласованности как договор между программным обеспечением (процессами) и реализацией памяти (хранилище данных). Эта модель гарантирует, что если программное обеспечение следует определенным правилам, память будет работать правильно. Поскольку в системе без глобальных часов определение последней операции среди записей затруднено, могут применяться некоторые ограничения на значения, которые могут быть возвращены операцией чтения.

Последовательный порядок операций

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

Последовательная согласованность

Целью моделей согласованности, ориентированных на данные, является обеспечение согласованного представления о хранилище данных, в котором процессы могут выполнять одновременные обновления. Одна из важных моделей согласованности, ориентированных на данные: последовательная последовательность определено Лэмпортом (1979).^[4] Таненбаум и др., 2007^[19] определяет последовательная последовательность при следующих условиях:

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

Адве и Гарачорлоо, 1996 г.^[18] определить два требования для реализации последовательной согласованности; порядок программ и атомарность записи.

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

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

Линеаризуемость^[20] (Атомная память)^[17] можно определить как последовательную согласованность с ограничением в реальном времени, учитывая время начала и время окончания для каждой операции. Выполнение является линеаризуемым, если каждая операция выполняется в линеаризуемом порядке путем помещения точки между временем начала и временем окончания и гарантирует последовательную согласованность.

Причинная последовательность

В причинная последовательность^[19] определено Хутто и Ахамадом, 1990 г.^[10] представляет собой более слабую модель согласованности, чем последовательная согласованность, поскольку она проводит различие между причинно-связанными операциями и теми, которые не связаны между собой. Например, если событие b вступает в силу из более раннего события a, причинная последовательность гарантирует, что все процессы увидят событие b после события a.

Таненбаум и др., 2007^[19] определяет, что хранилище данных считается причинно-следственным при следующих условиях:

Записи, которые потенциально причинно связаны, должны просматриваться всеми процессами в одном и том же порядке. Параллельные записи могут отображаться в другом порядке на разных машинах.^[19]

Конечная последовательность

An возможная последовательность^[19] модель слабой согласованности в системе с отсутствием одновременных обновлений. Он определяет, что, если обновление не занимает очень много времени, все реплики в конечном итоге становятся согласованными.

Большинство общих децентрализованных баз данных имеют модель конечной согласованности, либо BASE: в основном доступна; мягкое состояние; в конечном итоге согласованный или комбинация КИСЛОТА и BASE, иногда называемая SALT: последовательная; согласовано; выступ; взломостойкие, а также симметричные; без админки; выступ; и по согласованию во времени.^[21][22][23]

Группировка операций^[19]

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

Непрерывная последовательность

Непрерывная согласованность определяется позже в разделе протокола согласованности.

Модели согласованности, ориентированные на клиента^[19]

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

Монотонная последовательность чтения

Таненбаум и др., 2007^[19] определяет последовательность монотонного чтения следующим образом:

«Если процесс читает значение элемента данных x, любая последующая операция чтения этого процесса всегда будет возвращать то же значение или более новое значение».^[19]

Монотонная согласованность чтения гарантирует, что после того, как процесс прочитает значение элемента данных x в момент времени t, он никогда не увидит более старое значение этого элемента данных.

Монотонная последовательность записи

Условие согласованности монотонной записи определено Tanenbaum et al., 2007^[19] следующее:

«Операция записи процесса в элементе данных X завершается до любой последующей операции записи в X тем же процессом».^[19]

Последовательность чтения и записи

Значение, записанное процессом для элемента данных X, всегда будет доступно для последующей операции чтения, выполняемой тем же процессом для элемента данных X.^[19]

Последовательность записи-следует-чтения

При согласованности операций записи и чтения обновления распространяются после выполнения предыдущих операций чтения. Таненбаум и др., 2007^[19] определяет следующее условие согласованности операций записи и чтения:

«Операция записи, выполняемая процессом для элемента данных x, следующая за предыдущей операцией чтения для элемента x тем же процессом, гарантированно будет иметь место для того же или более позднего значения x, которое было прочитано».^[19]

Протоколы согласованности

Реализация модели согласованности определяется протоколом согласованности. Таненбаум и др., 2007^[19] иллюстрирует некоторые протоколы согласованности для моделей, ориентированных на данные.

Непрерывная последовательность

Непрерывная согласованность введена Ю и Вахдатом (2000).^[24] В этой модели семантика согласованности приложения описывается с помощью конусов в приложении. Поскольку требования к согласованности могут различаться в зависимости от семантики приложения, Yu and Vahdat (2000)^[24] считают, что предопределенная модель единообразной согласованности может быть неподходящим подходом. Приложение должно указывать требования согласованности, которые удовлетворяют семантике приложения. В этой модели приложение определяет каждое требование согласованности как conits (сокращение единиц согласованности). Conit может быть физической или логической согласованностью и используется для измерения согласованности. Таненбаум и др., 2007^[19] описывает понятие conit на примере.

Приложения могут допускать три несоответствия.

Отклонение числовых значений

^[24] Численное отклонение ограничивает разницу между значением conit и относительным значением последнего обновления. Записи могут быть присвоены весу, который определяет важность записей в конкретном приложении. Общий вес невидимых записей для объекта можно определить как численное отклонение в приложении. Есть два разных типа числового отклонения; абсолютное и относительное числовое отклонение.

Отклонение в заказе

^[24] Отклонение порядка записи - это несоответствие между локальным порядком записи в реплике и их относительным порядком в конечном конечном изображении.

Отклонение в устаревании между репликами

^[24] Отклонение устаревания определяет достоверность самой старой записи, ограничивая разницу между текущим временем и временем самой старой записи в конит, который не виден локально. У каждого сервера есть локальная очередь с неопределенной записью, для которой требуется определить фактический порядок и применить его к conit. Максимальная длина очереди с неопределенной записью является границей отклонения от порядка. Когда количество операций записи превышает лимит, вместо того, чтобы принимать новую отправленную запись, сервер будет пытаться зафиксировать неопределенные записи, связываясь с другими серверами в соответствии с порядком, в котором записи должны выполняться.

Если все три границы отклонения равны нулю, модель непрерывной согласованности является сильной согласованностью.

Первичные протоколы

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

Протокол первичного резервного копирования (локальная запись)

Первичные протоколы^[19] можно рассматривать как класс протоколов согласованности, которые проще реализовать. Например, последовательное упорядочение - это популярная модель согласованности, когда рассматривается согласованный порядок операций. Последовательный порядок можно определить как протокол на основе первичного. В этих протоколах есть связанный первичный элемент для каждого элемента данных в хранилище данных для координации операций записи в этот элемент данных.

Протоколы удаленной записи

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

Пример: Таненбаум и др., 2007^[19] дает пример протокола первичного резервного копирования. Схема протокола первичного резервного копирования показывает пример этого протокола. Когда клиент запрашивает запись, запрос записи перенаправляется на первичный сервер. Первичный сервер отправляет запрос в резервные копии для выполнения обновления. Затем сервер получает подтверждение обновления от всех резервных копий и отправляет подтверждение завершения записи клиенту. Любой клиент может прочитать последнее доступное обновление локально. Компромисс этого протокола заключается в том, что клиенту, который отправляет запрос на обновление, возможно, придется ждать так долго, чтобы получить подтверждение, чтобы продолжить. Эту проблему можно решить, выполнив обновления локально, а затем попросив другие резервные копии выполнить свои обновления. Неблокирующий протокол первичного резервного копирования не гарантирует согласованности обновления на всех серверах резервного копирования. Однако это улучшает производительность. В протоколе основного резервного копирования все процессы будут видеть один и тот же порядок операций записи, поскольку этот протокол упорядочивает все входящие записи на основе глобального уникального времени. Протоколы блокировки гарантируют, что процессы просматривают результат последней операции записи.

Протоколы локальной записи

В основных протоколах локальной записи^[19] первичная копия перемещается между процессами, желающими выполнить обновление. Чтобы обновить элемент данных, процесс сначала перемещает его в свое местоположение. В результате при таком подходе последовательные операции записи могут выполняться локально, в то время как каждый процесс может читать свою локальную копию элементов данных. После того, как основной завершает обновление, обновление перенаправляется на другие реплики, и все они выполняют обновление локально. Этот неблокирующий подход может привести к улучшению. Схема протокола локальной записи изображает подход локальной записи в основанных на первичных протоколах. Процесс запрашивает операцию записи в элементе данных x. Текущий сервер считается новым первичным для элемента данных x. Операция записи выполняется, и когда запрос завершен, основной отправляет запрос на обновление другим резервным серверам. Каждая резервная копия отправляет подтверждение основному после завершения операции обновления.

Протоколы реплицированной записи

В протоколах репликации записи^[19] в отличие от основного протокола, все обновления выполняются для всех реплик.

Активная репликация

При активной репликации^[19] с каждой репликой связан процесс для выполнения операции записи. Другими словами, обновления отправляются каждой реплике в форме операции для выполнения. Все обновления необходимо выполнять во всех репликах в одном порядке. В результате требуется полностью упорядоченный механизм многоадресной рассылки. При реализации такого механизма многоадресной рассылки в больших распределенных системах существует проблема масштабируемости. Есть еще один подход, при котором каждая операция отправляется центральному координатору (секвенсору). Координатор сначала присваивает порядковый номер каждой операции, а затем пересылает операцию всем репликам. Второй подход также не может решить проблему масштабируемости.

Протоколы на основе кворума^[19]

Голосование может быть другим подходом в протоколах репликации записи. В этом подходе клиент запрашивает и получает разрешение от нескольких серверов для чтения и записи реплицированных данных. В качестве примера предположим, что в распределенной файловой системе файл реплицируется на N серверов. Чтобы обновить файл, клиент должен отправить запрос по крайней мере N / 2 + 1 чтобы дать согласие на выполнение обновления. После заключения соглашения к файлу применяются изменения, и обновленному файлу присваивается номер новой версии. Точно так же для чтения реплицированного файла клиент отправляет запрос на N / 2 + 1 серверов, чтобы получить связанный номер версии с этих серверов. Операция чтения завершена, если все полученные номера версий являются самой последней версией.

Протоколы согласованности кеш-памяти

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

Модели согласованности кэша могут различаться по своим стратегиям обнаружения согласованности, которые определяют, когда возникают несоответствия. Есть два подхода к обнаружению несоответствия; статические и динамические решения. В статическом решении компилятор определяет, какие переменные могут вызвать несогласованность кеша. Таким образом, компилятор применяет инструкцию, чтобы избежать проблемы несогласованности. В динамическом решении сервер проверяет несогласованность во время выполнения, чтобы контролировать согласованность кэшированных данных, которые изменились после кэширования.

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

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

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

• Согласованность кеша
• Распределенная разделяемая память
• Неравномерный доступ к памяти

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

дальнейшее чтение

• Паоло Виотти; Марко Вуколич (2016). «Согласованность в нетранзакционных распределенных системах хранения». Опросы ACM Computing. 49 (1): 19:1–19:34. arXiv:1512.00168. Дои:10.1145/2926965.
• Али Сезгин (2004). «Формализация и проверка общей памяти» (PDF). Цитировать журнал требует | журнал = (помощь) (содержит много ценных ссылок)
• Кэти Йелик; Дэн Боначеа; Чак Уоллес (2004). «Предложение по модели согласованности памяти UPC (v1.0)» (PDF). Цитировать журнал требует | журнал = (помощь)
• Мосбергер, Дэвид (1993). «Модели согласованности памяти». Обзор операционных систем. 27 (1): 18–26. CiteSeerX  10.1.1.331.2924. Дои:10.1145/160551.160553.
• Сарита В. Адве; Курош Гарачорлоо (декабрь 1996 г.). «Модели согласованности общей памяти: Учебное пособие» (PDF). IEEE Computer. 29 (12): 66–76. CiteSeerX  10.1.1.36.8566. Дои:10.1109/2.546611. Получено 2008-05-28.
• Стейнке, Роберт С.; Гэри Дж. Натт (2004). «Единая теория согласованности разделяемой памяти». Журнал ACM. 51 (5): 800–849. arXiv:cs.DC / 0208027. Дои:10.1145/1017460.1017464.

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

• Слайды IETF
• Упорядочивание памяти в современных микропроцессорах, часть I и Часть II, Пол Э. Маккенни (2005). Linux журнал