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

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

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

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

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

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

Пример [ править ]

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

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

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

Типы [ править ]

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

Проблема

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

Вид

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

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

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

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

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

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

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

Последовательная согласованность [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конвейерная согласованность RAM ( согласованность PRAM) была представлена ​​Липтоном и Сандбергом в 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 . Последние операции не используются для синхронизации; первые состоят из операций по приобретению и освобождению . Получение фактически представляет собой операцию чтения памяти, используемую для получения доступа к определенному набору общих ячеек. Освобождение, с другой стороны, - это операция записи, которая выполняется для предоставления разрешения на доступ к общим расположениям.

Для последовательной согласованности (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] представляет собой комбинацию моделей когерентности кэша и согласованности памяти в качестве модели взаимодействия для систем с общей памятью, поддерживаемых программным или аппаратным обеспечением; модель транзакционной памяти обеспечивает как согласованность памяти, так и согласованность кеша. Транзакция - это последовательность операций, выполняемых процессом, преобразующим данные из одного согласованного состояния в другое. Транзакция либо фиксируется при отсутствии конфликта, либо прерывается. В коммитах все изменения видны всем остальным процессам, когда транзакция завершена, а при отмене все изменения отменяются. По сравнению с моделями ослабленной согласованности, транзакционная модель проще в использовании и может обеспечить более высокую производительность, чем модель последовательной согласованности.

Согласованность и репликация [ править ]

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

Модели согласованности, ориентированные на данные [ править ]

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

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

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

Последовательная согласованность [ править ]

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

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

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

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

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

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

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

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

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

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

Возможная согласованность [ править ]

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

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

Группирующие операции ^[19] [ править ]

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

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

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

Клиентоцентричные модели согласованности ^[19] [ править ]

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

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

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

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

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

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

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

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

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

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

Последовательность "пишет-следует-читает" [ править ]

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

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

Протоколы согласованности [ править ]

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

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

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

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

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

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

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

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

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

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

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

Первичные протоколы [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Протоколы согласования кэширования [ править ]

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

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

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