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

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

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

То есть порядок выполнения программы в том же процессоре (или потоке) совпадает с порядком программы, тогда как порядок выполнения программы на разных процессорах (или потоках) не определен. В таком примере:

Порядок выполнения между A1, B1 и C1 сохраняется, то есть A1 выполняется перед B1, а B1 перед C1. То же самое для A2 и B2. Но, поскольку порядок выполнения между процессорами не определен, B2 может выполняться до или после C1 (B2 может физически выполняться до C1, но эффект B2 может быть виден после C1, что то же самое, что «B2 выполняется после C1»)

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

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

Большинство архитектур набора инструкций , включая x86 , x86-64 , ARM и RISC-V , не предоставляют программам последовательно согласованную модель памяти. Некоторые важные аппаратные оптимизации, такие как кэширование с обратной записью , противоречат последовательной согласованности. Это означает, что многопоточные программы в многопроцессорных системах на этих архитектурах могут демонстрировать поведение, которое не согласуется с каким-либо чередованием инструкций в потоках, обычно путем чтения устаревших значений.

• Параллельная структура данных
• Линеаризуемость
• Сериализуемость