Распределенная разделяемая память

Распределённая разделяемая память (Distributed Shared Memory, DSM) – это абстракция, позволяющая узлам распределённой системы обращаться к общей адресной области так, как будто это единая оперативная память, хотя физически данные рассредоточены по множеству узлов и передаются по сети. DSM объединяет идеи структур данных, графов (топология узлов), теории алгоритмов (корректность/сложность), логики (отношение «happens-before») и моделей памяти.
Для подготовки к ЕГЭ по информатике DSM полезна тем, что тренирует:

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

Формальная модель DSM

Пусть задана система из N ≥ 2 узлов:

S = <Nodes, Net, Mem, Ops, Consistency>

Nodes = {P1, P2, …, PN}          # процессы/узлы

Net   – сеть с конечной, но непостоянной задержкой

Mem   – распределённая адресная область (страницы/объекты)

Ops   – операции: Read(addr), Write(addr, val), Sync(...)

Consistency – выбранная модель согласованности

1. Абстракция адресации
   

   • Страничная DSM: память разбита на блоки фиксированного размера PageSize = 2^k.

   • Объектная DSM: единица когерентности – логический объект (структура/массив/запись).

2. Состояние блока
   

   Для каждого блока b и узла Pi хранится состояние:

   state(Pi, b) ∈ {Invalid, Shared, Exclusive}

   owner(b) ∈ Nodes ∪ {⊥}         # владелец эксклюзивной копии или нет

3. Операции чтения/записи
   

   Read(Pi, b, off)   → возвращает значение v из локальной копии или по запросу из сети

   Write(Pi, b, off, v) → требует эксклюзив; при необходимости вызывает протокол когерентности

4. Базовый инвариант когерентности:
   

   ∀b: не существует двух узлов Pi ≠ Pj с state(Pi,b)=Exclusive и state(Pj,b)∈{Shared,Exclusive}.

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

Модель определяет, какие результаты чтений/записей допустимы при параллельном доступе.

1. Последовательная согласованность (Sequential Consistency, SC)
   

   Все операции всех процессов можно упорядочить в одну последовательность, совместимую с порядком программ каждого процесса. Формально:

   ∃ тотальный порядок →  такой, что локальные порядки сохраняются и каждое Read видит последний предшествующий Write на тот же адрес.

   SC проста для рассуждений, но дорога по синхронизациям.

2. Когерентность по выпуску (Release Consistency, RC)
   

   Различают синхронизирующие операции:

   acquire(L) – вход в критическую секцию

   release(L) – выход из критической секции

   Гарантии согласованности распространяются при release/acquire, а не при каждой записи. Это снижает накладные расходы.

3. Причинно-согласованная (Causal Consistency)
   

   Если операция op1 причинно предшествует op2 (op1 →_hb op2), то все процессы наблюдают их в одном порядке; независимые операции могут наблюдаться по-разному.

   →_hb – транзитивное замыкание «локальный порядок» ∪ «передача через сообщение/синхронизацию».

4. PRAM/Processor Consistency
   

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

   Итог: SC → самый строгий, RC/causal/PRAM → слабее, но эффективнее. Для алгоритмических доказательств на ЕГЭ полезно уметь сопоставлять модель и необходимые барьеры/замки.

Протоколы когерентности: инвалидация и обновление

1. Write-invalidate (инвалидация)
   При получении эксклюзива владелец рассылает Invalidate(b) всем держателям блока b. Преимущество – меньше трафика при множественных локальных записях.

2. Write-update (обновление)
   Каждая запись транслируется как Update(b, delta) всем копиям. Преимущество – читатели всегда «свежие», но высокие сетевые расходы при частых записях.

3. Централизованный каталог (Directory-based)
   Поддерживается таблица владения: для каждого блока список читателей/владельца. Масштабируется лучше, чем широковещательные snoop-протоколы. 
   Инвариант каталога:∀b: owner(b)=Pi ⇒ state(Pi,b)=Exclusive ∧ ∀Pj≠Pi: state(Pj,b)≠Exclusive

Гранулярность и ложное разделение

• Гранулярность протокола – размер минимально передаваемого блока (страница/объект).

• Ложное разделение (false sharing) – разные переменные, интенсивно изменяемые разными узлами, попадают в один блок → постоянные инвалидации/миграции.
  Правило: выравнивайте часто изменяемые переменные по блокам (padding), используйте объектную DSM или более мелкую гранулярность в критических местах.

Синхронизация в DSM

1. Примитивы
   

   mutex.lock(), mutex.unlock()

   barrier()               # барьерная синхронизация

   atomic compare-and-swap # условная запись

   В RC-гарантиях: все записи до release(L) становятся видимыми тем, кто выполнит acquire(L) на том же L.

2. Барьер и порядок
   barrier(): все процессы достигают точки; после выхода – видят эффекты друг друга, согласно модели (обычно RC/SC для барьера).

Стоимость и оценки сложности

• Пусть Tcomp – локальные вычисления, Tcomm – коммуникации:

Ttotal = Tcomp + Tcomm

Tcomm ≈ α * (#сообщений) + β * (объём_данных)

где α – латентность, β – стоимость передачи байта.

• Для N узлов и каталога размера O(#блоков) память каталога:

Mem_dir = O(#блоков × среднее_число_держателей)

• Вероятность конфликтов растёт при увеличении степени параллелизма; для «горячих» блоков выгоднее write-update, для «локально-горячих» – write-invalidate.

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

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

Правило 2. Все записи в разделяемые данные – через критические секции или барьеры.
Подбирайте модель: RC требует release/acquire на границах.

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

Правило 4. Предпочитайте неизменяемые (immutable) структуры для чтения.
Один раз построили – много раз прочитали без когерентных конфликтов.

Правило 5. Явно документируйте модель памяти модуля.
Например: «Все обновления видимы только после barrier()».

Правило 6. Избегайте живых блокировок.
Гарантируйте глобальный порядок захвата нескольких замков (lock ordering).

Правило 7. Диагностика с учётом модели.
Баг «потерянной записи» в RC часто исчезает, если добавить нужный release/acquire – проверяйте границы критических секций.

Шаблоны проектирования алгоритмов в DSM

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

2. Produсer–Consumer через разделяемые буферы
   Используйте очереди/кольцевые буферы; запись сопровождайте release, чтение – acquire.

3. Map–Reduce (упрощённая DSM-версия)
   Map-фаза порождает локальные хэши (map[K]V), затем эмиссия в «глобальные» сегменты ключей с барьером и детерминированной редукцией.

Типичные ошибки и как их избежать

• Отсутствие барьеров/замков при RC → разъезжающиеся версии данных.

• Ложное разделение → лавина инвалидаций; лечится выравниванием.

• Гонка при инициализации: два узла «создают» один и тот же объект. Решение – «инициализирующий замок» или CAS.

• Чередование write-update и write-invalidate без стратегии → избыточный трафик.

Мини-шпаргалка 

Инвариант эксклюзива:

∀b: не существует Pi≠Pj с Exclusive на b одновременно.

SC (последовательная согласованность):

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

RC (release consistency):

Записи до release(L) видимы узлам, выполнившим acquire(L) для того же L.

Causal:

Если op1 →_hb op2, то все узлы наблюдают op1 перед op2.

Стоимость коммуникаций:

Tcomm ≈ α * (#сообщений) + β * (объём_передач)

Write-invalidate vs Write-update:

invalidate – дёшево при множественных локальных writes;

update – дёшево при множественных reads между редкими writes. 

Связь с ЕГЭ по информатике

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

• Оценка сложности и анализ узких мест (как в заданиях на алгоритмы).

• Аккуратная работа с моделями и условиями задачи – тренирует умение читать формулировки и выявлять скрытые ограничения.

• Построение конвейеров, синхронизаций, логических зависимостей – развивает навыки структурирования решений.

Пять упражнений (академический формат)

Упражнение 1. Модель памяти и барьеры
Дан параллельный алгоритм вычисления суммы массива A[0..n-1] на p узлах DSM (RC-модель). Каждый узел Pi считает локальную сумму Si по своему отрезку. Затем в общий массив S[0..p-1] записывается Si, и узел P0 вычисляет итог.
a) Укажите места, где необходимы release/acquire, чтобы P0 прочитал корректные S[i].
b) Запишите формальный инвариант корректности итога после барьера barrier().
c) Оцените Tcomm в зависимости от p и размера блока.

Упражнение 2. Выбор протокола: invalidate или update?
Имеется страница b, к которой P1 делает 1000 последовательных Write, а P2 периодически читает её (10 раз).
a) Сравните ожидаемые коммуникационные затраты для invalidate и update.
b) Предложите гибридную стратегию (переключение после k-записей без чтений).
c) Сформулируйте критерий переключения в терминах измеренных счётчиков.

Упражнение 3. Ложное разделение
В структуре:
struct Stat { int a; int b; }
узел P1 обновляет a, узел P2 – b, но оба поля лежат на одной странице.

a) Объясните, почему возникает thrashing (частые инвалидации).
b) Предложите два способа исправления (padding/разнос по страницам, объектная DSM).
c) Запишите инвариант отсутствия конфликтов после рефакторинга.

Упражнение 4. Каталог когерентности и масштабирование
В directory-based DSM каждый блок b хранит список держателей.
a) Оцените память каталога Mem_dir при B блоках и средней репликации r.
b) Предложите схему «битовой маски держателей» и оцените выигрыш/проигрыш при больших N.
c) Сформулируйте алгоритм обработки запроса эксклюзива: какие сообщения рассылает каталог?

Упражнение 5. Последовательная согласованность и корректность
Два узла:
P1: x := 1; y := 1;
P2: r1 := y; r2 := x;
Изначально x=y=0.

a) Возможна ли конфигурация r1=1, r2=0 при SC? Обоснуйте через единую линейную историю.
b) Повторите анализ для causal и RC с отсутствием синхронизаций.
c) Предложите минимальные синхронизации для гарантии r2=1 всякий раз, когда r1=1.

Заключение

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