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

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

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

Пример

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

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

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

Типы

Модели согласованности определяют правила очевидного порядка и видимости обновлений и находятся в континууме компромиссов. Существует два метода определения и классификации моделей согласованности; выпуск и просмотр.

Проблема

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

Вид

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

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

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

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

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

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

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

Последовательность	Строгая модель		Нестрогая модель
	П1 1	П 2	П1 1	П 2
1	Вт ( х )1		Вт ( х )1
2		р ( х )1		р ( х )0
3				р ( х )1

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

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

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

Модель последовательной согласованности была предложена Лэмпортом (1979). Это более слабая модель памяти, чем модель строгой согласованности. Запись в переменную не обязательно должна происходить мгновенно, однако записи в переменные разными процессорами должны быть видны всем процессорам в одном и том же порядке. Последовательная согласованность достигается, если «результат любого выполнения такой же, как если бы операции (чтения и записи) всех процессов в хранилище данных выполнялись в некотором последовательном порядке, и операции каждого отдельного процессора появляются в этой последовательности в порядок, указанный в его программе». Адве и Гарачорлоо, 1996 г. определить два требования для реализации последовательной согласованности; порядок программы и атомарность записи.

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

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

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

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

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

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

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

Причинно-следственная связь определено Хутто и Ахамадом, 1990 г., Это ослабление модели последовательной согласованности за счет разделения событий на те, которые причинно связаны, и те, которые не связаны между собой. Он определяет, что только операции записи, которые причинно связаны, должны просматриваться всеми процессами в одном и том же порядке. Например, если событие b вступает в силу из более раннего события a, причинно-следственная согласованность гарантирует, что все процессы увидят событие b после события a. Таненбаум и др., 2007 дают более строгое определение: хранилище данных считается причинно-согласованным при следующих условиях:

• Записи, потенциально имеющие причинно-следственную связь, должны просматриваться всеми процессами в одном и том же порядке.
• На разных машинах одновременную запись можно увидеть в разном порядке.

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

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

Последовательность	П1 1	П 2	P3 3	P4 4
1	Вт(х)1	Р(х)1	Р(х)1	Р(х)1
2		Вт(х)2
3	Вт(х)3		Р(х)3	Р(х)2
4			Р(х)2	Р(х)3

W(x)2 происходит после W(x)1 из-за чтения, сделанного P2 в x до W(x)2, следовательно, этот пример является причинно последовательным согласно определению Хутто и Ахмада (хотя и не согласно Таненбауму и др., поскольку W(x)2 и W(x)3 не отображаются в одном и том же порядке для всех процессов). Однако R(x)2 и R(x)3 встречаются в разном порядке на P3 и P4, поэтому этот пример последовательно несовместим .

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

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

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

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

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

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

Конвейерная согласованность ОЗУ (согласованность PRAM) была представлена ​​Липтоном и Сэндбергом в 1988 году. как одна из первых описанных моделей согласованности. Из-за его неформального определения на самом деле существует как минимум две слегка разные реализации: один от Ахмада и др. и один от Мосбергера.

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

Последовательность	П1 1	П 2	P3 3	P4 4
1	Вт(х)1
2		Р(х)1
3		Вт(х)2
4			Р(х)1	Р(х)2
5			Р(х)2	Р(х)1

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

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

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

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

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

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

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

Гарантии сеанса

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

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

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

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

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

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

Условие монотонной согласованности записи определено Таненбаумом и др., 2007. следующее:

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

Согласованность чтения и записи

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

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

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

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

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

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

Слабая упорядоченность

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

П1 1	П 2
X = 1; fence xready = 1;	fence while (!xready) {}; fence y = 2;

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

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

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

Согласованность выпуска

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

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

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

RCsc и RCpc

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

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

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

• приобрести → все,
• все → выпустить,
• особенный → особенный.

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

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

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

Согласованность входа

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

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

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

Общая последовательность

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

Окончательная согласованность

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

Большинство общих децентрализованных баз данных имеют модель конечной согласованности: BASE: в принципе доступна; мягкое состояние; в конечном итоге последовательный или комбинация ACID и BASE, иногда называемая SALT: последовательная; согласованный; ведомый; устойчивый к взлому, а также симметричный; без администратора; ведомый; и согласованное во времени.

Модели расслабленной согласованности памяти

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

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

Релаксация

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

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

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

Проблема и просмотр на основе

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

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

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

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

Возможные послабления:

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

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

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

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

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

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

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

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

Пример А

П1 1	П 2
А = флаг1 = флаг2 = 0
флаг1 = 1	флаг2 = 1
А = 1	А = 2
рег1 = А	рег3 = А
reg2 = флаг2	reg4 = флаг1
рег1 = 1; рег3 = 2, рег2 = рег4 = 0

Пример Б

П1 1	П 2	P3 3
А = Б = 0
А = 1
	если (А == 1)
	Б = 1	если (В == 1)
		рег1 = А
Б = 1, рег1 = 0

Расслабленно пишите, чтобы читать, и пишите, чтобы писать.

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

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

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

Расслабляющее чтение и чтение для написания команд программ: Alpha, RMO и PowerPC.

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

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

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

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

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

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

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

• Причинно-следственная связь + последовательность
• Межклиентская монотонность
• Дельта-согласованность
• Консистенция вилки
• Сериализация в одной копии
• Сериализуемость
• Согласованность векторного поля
• Слабая консистенция
• Сильная консистенция

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

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

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

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

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

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

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

Группировка операций

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

Клиентоориентированные модели согласованности

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

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

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

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

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

Есть три несоответствия, которые могут быть допущены приложениями.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Протоколы на основе кворума

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

Протоколы когерентности кэша

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

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

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

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

См. также

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

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

• Паоло Виотти; Марко Вуколич (2016). «Согласованность в нетранзакционных распределенных системах хранения». Обзоры вычислительной техники ACM . 49 (1): 19:1–19:34. arXiv : 1512.00168 . дои : 10.1145/2926965 . S2CID   118557 .
• Сезгин, Али (август 2004 г.). Формализация и верификация общей памяти (PDF) (кандидатская диссертация). Университет Юты . Проверено 27 июня 2024 г. (содержит много ценных ссылок)
• Йелик, Кэтрин; Боначеа, Дэн; Уоллес, Чарльз (2004), Предложение по модели согласованности памяти UPC, версия 1.0 (PDF) , Технический отчет Национальной лаборатории Лоуренса Беркли, doi : 10.2172/823757 , LBNL-54983, заархивировано из оригинала (PDF) 20 мая. 2005 г.
• Мосбергер, Дэвид (1993). «Модели согласованности памяти» . Обзор операционных систем . 27 (1): 18–26. CiteSeerX   10.1.1.331.2924 . дои : 10.1145/160551.160553 . S2CID   16123648 .
• Сарита В. Адве; Курош Гарачорлоо (декабрь 1996 г.). «Модели согласованности общей памяти: учебное пособие» (PDF) . IEEE-компьютер . 29 (12): 66–76. CiteSeerX   10.1.1.36.8566 . дои : 10.1109/2.546611 . Архивировано из оригинала (PDF) 7 сентября 2008 г. Проверено 28 мая 2008 г.
• Стейнке, Роберт С.; Гэри Дж. Натт (2004). «Единая теория согласованности общей памяти». Журнал АКМ . 51 (5): 800–849. arXiv : cs.DC/0208027 . дои : 10.1145/1017460.1017464 . S2CID   3206071 .
• Терри, Дуг. «Согласованность реплицируемых данных объясняется с помощью бейсбола». Сообщения ACM 56.12 (2013): 82-89. https://www.microsoft.com/en-us/research/wp-content/uploads/2011/10/ConsistencyAndBaseballReport.pdf

Внешние ссылки

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