18. Synchronization. Cache coherence.md

Лекция 18. Синхронизация. Когерентность кеш

Содержание

• Лекция 18. Синхронизация. Когерентность кеш
  • Содержание
  • Параллелизм уровня потоков
    • Коммуникационные модели
    • Синхронизация (необходима при процессах, которые выполняются параллельно)
  • Потокобезопасное программирование
  • Синхронная связь
    • Буфер FIFO(First input, first output)
    • Буфер FIFO с общей памятью
    • Семафоры
    • Семафоры для приоритета
    • Семафоры для распределения ресурсов
    • Буфер FIFO с семафорами
    • Одновременные транзакции
    • Семафоры для взаимных исключений
    • Проблемы атомарности
    • Мощность семафора
    • Реализация семафоров
    • Синхронизация : обратная сторона
    • Обедающие философы
    • Решение
    • Исправленный метод передачи на основе вышеописанного алгоритма с избежанием тупика
  • Многоядерность
  • Когерентность кэш
    • Поддержание когерентности
    • Реализация когерентности
    • Snooping-Based Coherence
    • Протокол Valid/Invalid (VI)
    • Modified/Shared/Invalid (MSI) протокол
    • MSI протокол FSM
    • Оптимизация MSI: состояние E
    • MESI: усовершенствованный
    • Когерентность кэш и ложное совместное использование
    • Основные материалы лекции

Параллелизм уровня потоков

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

• несколькими независимыми последовательными потоками, которые конкурируют за общие ресурсы, такие как память, устройства ввода/вывода;
• несколькими взаимодействующими последовательными потоками, которые взаимодействуют друг с другом.

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

Существует две основные коммуникационные модели:

• общая память;
• обмен.

Коммуникационные модели

В коммуникационной моделью с общей памятью есть:

• есть единое адресное пространство для потоков;
• общение между потоками происходит через неявную связь с помощью загрузки и сохранения в память.

Рис. 1. Коммуникационная модель с общей памятью.

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

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

Рис. 2. Коммуникационная модель с обменом сообщениями.

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

Синхронизация (необходима при процессах, которые выполняются параллельно)

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

• Вилки и соединения (fork and join): параллельный процесс должен подождать, пока не произойдёт несколько событий.

Рис. 3. Способ синхронизации параллельных процессов "Вилки и соединения" (fork and join).

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

• Проиводитель-потребитель (producer-consumer): потребительский процесс должен ждать, пока процесс производителя не произведет данные (то есть потребитель не может продолжать выполнение, пока производитель не произведёт какие-то данные).

*Рис. 4. Способ синхронизации параллельных процессов "Проиводитель-потребитель" (producer-consumer).

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

Потокобезопасное программирование

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

• Каждый поток выполняется некоторое время (например до очередного прерывания по таймеру), после чего ОС переключается на другой поток и все повторяется заново.

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

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

Синхронная связь

*Рис. 5. Пример программы с синхронной связью.

Метка loop указывает на последовательность инструкций xxxᵢ, которые генерируют данные с. После этого производитель оправляет эти данные для потребителя и потом возвращается к началу цикла и так далее. В свою очередь потребитель получает данные (receive) от производителя, выполняет над ними нужные операции и снова возвращается к началу цикла.

Приоритет очерёдности a⩽b,a предшествует b:

• Потребитель не может использовать данные до их получения (событие sendᵢ должно происходить раньше или в тот же момент времени, когда происходит rcvᵢ (получение) этих данных);

*Рис. 6. Пример программы с синхронной связью c учётом приоритета очерёдности.

• Производитель не может перезаписать данные до их использования потребителем (получение данных должно происходить раньше, чем их перезапишет следующая i+1 посылка).

Буфер FIFO(First input, first output)

*Рис. 7. Пример буфера FIFO без ограничений приоритета.

Буфер FIFO ослабляет ограничения, связанные с синхронизацией. Производитель может опередить потребителя на N значений (где N — глубина данного буфера).

rcvᵢ ≤ sendᵢ₊₁

Обычно реализуется как кольцевой буфер в общей памяти:

*Рис. 8. Пример кольцевого буфера без ограничений приоритета с указателями на начало и конец очереди.

У нас есть буфер на 3 элемента (очередь) и два указателя: один указывает на место, куда мы будем писать (write_ptr), а другой указывает на место, откуда мы будем читать (read_ptr). В очередной момент времени происходит генерация новых данных (send c₀) — они записываются в место, куда указывает write_ptr. После этого данный указатель сдвигается на одну ячейку вправо (i+1). Далее мы снимаем данные с первой ячейки (rcv()) c₀ и указатель read_ptr сдвигается на следующую ячейку (c₁) и так далее.

Буфер FIFO с общей памятью

*Рис. 9. Пример программы буфера FIFO с общей памятью без ограничений приоритета.

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

Семафоры

Семафоры — это программная конструкция для синхронизации.

Semaphore — это тип данных, число ≥ 0. Объявляется следующим образом : semaphore s = K; // инициализируем s значением K.

Операции, которые определены для семафоров:

• wait (semaphore s) - ждёт если семафор s == 0 (если в момент времени, когда мы доходим до операции wait, семафор = 0 — программа останавливает свою работу на этой строчке и не двигается дальше), как только семафор стал > 0 программа идёт дальше, а сам семафор уменьшается на 1: s = s - 1;
• signal (semaphore s) - каждый раз когда программа проходит эту операцию, семафор увеличивается на 1: s = s + 1 (один ожидающий поток теперь может быть в состоянии продолжить).

Семантические гарантии: семафор s инициализированный как K, применяет ограничение приоритета:

signal(s)ᵢ < wait(s)ᵢ₊ₖ,i-ый вызов signal(s) должен завершиться до завершения (i+K) вызова wait(s).

Семафоры для приоритета

Нам нужно, чтобы оператор А₂ в потоке А был завершён до того. как начнётся оператор B₄ в потоке B: А₂ < B₄

*Рис. 10. Потоки А и B .

Решение:

• объявить semaphore = 0;
• signal(s) в начале стрелки (после A₂>A);
• wait(s) в конце стрелки.

*Рис. 11. Потоки A и B с семафорами для приоритета.

Если мы в потоке B придём раньше до B₄, то s по умолчанию = 0 и мы застрянем на инструкции wait(s). В это время первый поток А доходит до signal(s), то есть увеличивает s на 1, соответственно внутри wait s тоже увеличилось на 1. Мы прошли этот wait и семафор снова стал нулём.Таким образом, мы получили синхронизацию, которую хотели.

Семафоры для распределения ресурсов

Описание проблемы:

1. существует K ресурсов;
2. существует множество потоков, каждый из которых нуждается в ресурсах в случайные моменты времени;
3. необходимо гарантировать, что в любой момент времени используется не более K ресурсов.

Решение с использованием семафоров:

• В основной памяти : semaphore s = K;//K ресурсов;
• Используемые ресурсы wait(s);//выделение ресурса ...//использование его некоторое время signal(s);//возвращение ресурса.

То есть если количество wait произойдет столько же раз сколько и K, то мы обнулим этот ресурс и очередной wait не даст нам повторно использовать этот ресурс.

Буфер FIFO с семафорами

*Рис. 12. Пример программы буфера FIFO с семафорами.

• выполняется приоритет, управляемый семафором sendᵢ ≤ revᵢ;
• здесь есть один ресурс, управляемый семафором: количество символов в буфере;
• всё ещё некорректная ситуация, так как производитель может переполнить буфер;
• должны применять требование rcvᵢ ≤ sendᵢ₊₁>.

*Рис. 13. Пример программы буфера FIFO с семафорами с применением требования rcvᵢ ≤ sendᵢ₊₁.

Ресурсы, управляемые семафорами: символы в FIFO, свободное место в FIFO. Работает с одним производителем и потребителем.

Одновременные транзакции

Предположим, что вы и ваш друг посещаете банкомат в одно и то же время и снимаете 100 рублей со своего счёта. Что происходит?

*Рис. 14. Код к конкретной задаче.

Результат: у вас есть 200 рублей и баланс счёта уменьшился на 200 рублей.

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

*Рис. 15. Перекрытие потоков.

Результат: у вас есть 200 рублей, а баланс счёта уменьшился на 100 рублей.

Необходимо быть осторожным при написании параллельных программ. В частности, при изменении общих данных. Для некоторых сегментов кода, называемых критическими секциями (critical sections) мы хотели бы убедиться, что никакие два выполнения не перекрываются. Это ограничение называется взаимным исключением (mutual exclusion).

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

Семафоры для взаимных исключений

*Рис. 16. Функция из предыдущего примера.

Нам нужно гарантировать, что двойной вызов функции debit не пересекается. То есть либо a предшествует b, либо b предшествует a (они не пересекаются!).

Для этого:

• берём семафор semaphore lock, инициализируем его единицей;
• вначале функции ставим wait(lock), то есть вначале мы его блокируем;
• в конце ставим signal(lock), снимаем блокировку.

*Рис. 17. Итоговая функция с семафором для взаимных исключений.

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

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

*Рис. 18. Потоки производители для нашего примера.

Справиться с этим помогут наши блокировки:

*Рис. 19. Программа буфера FIFO с блокировками.

Мощность семафора

Семафор — это единый примитив синхронизации, обеспечивающий:

• Отношение приоритета;
  • sendᵢ ≤ rcvᵢ (событие send<sub>i </sub> должно происходить раньше или в тот же момент времени, когда происходит rcvᵢ(полупение) этих данных);
  • rcvᵢ ≤ sendᵢ₊₁ (получение данных должно происходить раньше, чем их перезапишет следующая i+1 посылка).
• Отношение взаимного исключения;
• Защита переменных in и out.

Пример с синхронизированными потоками:

*Рис. 20. Итоговая программа буфера FIFO с блокировками для защиты переменных in и out.

Реализация семафоров

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

• Использовать специальную инструкцию (например, "test and set"), которая выполняет атомарное чтение-изменение-запись. Зависит от атомарности выполнения одной команды. Это самый распространённый подход.
• Реализуется с помощью системных вызовов. Работает только в однопроцессорных системах, где ядро бесперебойно.

Синхронизация : обратная сторона

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

*Рис. 21. Пересылка одинаковой суммой денег с одного счёта на другой.

*Рис. 22. Функция пересылки денег.

Что же может пойти не так? Thread 1: wait (lock [0903]); (поток 1 блокирует 0903)

Thread 2: wait (lock [1103]); (поток 2 параллельно блокирует 1103)

Thread 1: wait (lock [1103]); //не завершиться, пока не произойдёт signal 2 потока (заблокирован, потому что предыдущий поток его уже заблокировал, кончился ресурс)

Thread 1: wait (lock [0903]); //не завершиться, пока не произойдёт signal 1 потока.

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

Обедающие философы

*Рис. 23. Карикатура обедающих философов за столом.

Философы мыслят глубокими мыслями, но имеют простые мирские потребности. Когда вы голодны, группа из N философов будет сидеть вокруг стола с N палочками для еды, разбросанными между ними. Еда подаётся, и каждый философ наслаждается неторопливой едой, используя палочки для еды с обеих сторон. Они очень вежливы и терпеливы, и каждый соблюдает обеденный протокол. Алгоритмы философа:

• взять (дождаться) ЛЕВУЮ палочку;
• взять (дождаться) ПРАВУЮ палочку;
• кушать, пока не насытится;
• заменить обе палочки.

Никто не может добиться прогресса, потому что все они ждут недоступного ресурса. Условия:

1. Взаимное исключение: только один поток может содержать ресурс в данный момент времени;
2. Удержание и ожидание: поток удерживает выделенные ресурсы, ожидая других;
3. Отсутствие вытеснения: ресурс не может быть удалён из потока, удерживающего его;
4. Происходит круговое ожидание.

Решение

Назначить уникальный номер каждой палочке для еды. Запрашивать ресурсы в последовательном порядке (алгоритм Дейкстры).

Новый алгоритм:

• Взять палочку с МЕНЬШИМ номером;
• Взять палочку с БОЛЬШИМ номером;
• ЕСТЬ;
• Заменить ОБЕ палочки.

*Рис. 24. Решение проблемы обедающих философов.

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

Исправленный метод передачи на основе вышеописанного алгоритма с избежанием тупика

*Рис. 25. Исправленный метод передачи денежной суммы.

Многоядерность

*Рис. 26. Многоядерность.

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

Когерентность кэш

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

Проблема:

*Рис. 27. Проблема многоядерности.

1. Ядро 0 загружает данные из памяти по адресу A число два.
2. Ядро 2 выгружает в память по адресу A число три.
3. Нулевое ядро после этого опять загружает данные по этому же адресу, но в кэше лежат старые данные.

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

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

Например, сделать копию A ядра 0 недействительной, прежде чем позволить ядру 2 писать в него.

Поддержание когерентности

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

• Только один кэш одновременно имеет разрешение на запись;
• Никакой кэш не может иметь устаревшую копию данных после того, как была выполнена запись по адресу.

Реализация когерентности

Протоколы когерентности должны обеспечивать соблюдение двух правил:

• распространяющаяся запись (Write propagation): записи в конечном итоге становятся видимыми для всех процессоров (если кто-то из процессоров пишет куда-то, то нужно однозначно остальным об этом сообщить); сериализация записи (Write serialization): записи в одно и то же место сериализуются (все процессоры видят их в том же порядке).

Как обеспечить распространение записи:

• write-invalidate protocols: аннулировать все другие кэшированные копии перед выполнением записи;
• write-update protocols: обновить все другие кэшированные копии после выполнения записи.

Как обеспечить сериализацию записи:

• snooping-based protocols: все кэши наблюдают за действиями друг друга через общую шину;
• directory-based protocols: каталог когерентности отслеживает содержимое частных кэшей и сериализует запросы.

Snooping-Based Coherence

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

*Рис. 28. Процессоры со Snoopy Cache, которые подключены к основной памяти.

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

Шина обеспечивает задачу сериализации:

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

Snoopy кэш отличается от обычного кэша наличием дополнительного поля State (состояние) и контроллером, который следит за шиной и содержимым состояния каждой записи.

В ячейку State может быть записан один дополнительный бит (0 или 1). Этот бит указывает, на валидность или не валидность записи исходя из когерентности данных в кэше.

*Рис. 29. Упрощенная форма Snoopy Cache.

Snoopy протокол (FSM) — это конечный автомат, который зависит от того что происходит на шине и обновляет значения состояния.

• Диаграмма состояний переходов.
• Действия.

Протокол Valid/Invalid (VI)

Поддерживается только кэшем со сквозной записью (нужно чтобы все видели что происходит на шине).

*Рис. 30. Протокол VI.

Когда мы находимся в состоянии Invalid, и какое-то ядро запрашивает данные, то происходит Processor Read (PrRd). Затем он получает данные в свой кэш и выставляет эти данные как Valid. В какой-то момент это ядро видит, что какое-то ядро записало по этому адресу (то есть на шине произошла запись Bus Write), тогда оно сразу меняет состояние этой ячейки на Invalid, потому что в этот момент времени у него неактуальные данные.

*Рис. 31. Основные действия для данного протокола.

Таким образом, если мы читаем данные, то мы переходим в состояние Valid.Если мы видим, что какое-то ядро записывает по этому адресу, то переходим в состояние Invalid.

Пример:

*Рис. 32. Пример применения протокола Valid/Invalid.

1. Допустим, ядро 0 сначала загружаю по адресу A. На шине запрашивается чтение, в кэш попадает запись с состоянием Valid.
2. Затем загружается второе ядро по адресу A, теперь там тоже запись Valid.
3. Теперь происходит запись числа в память, кэш видит это и делает Invalidate данных (обнуляет их).
4. Когда произойдёт очередной load, он увидит, что мы находимся в состоянии Invalidate.
5. Теперь просто зачитаем обновленные данные.

*Рис. 33. Пример применения протокола Valid/Invalid с пояснениями.

Проблемы VI:

• каждая запись обновляет основную память;
• каждая запись требует широковещательной передачи и слежки.

Modified/Shared/Invalid (MSI) протокол

Каждая строка в каждом кэше поддерживает MSI состояния:

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

MSI протокол FSM

Если процессор считывает данные (PrRd), то тогда на шине появляется значение, что мы читаем данные (BusRd) и мы переходим в состояние S.

Если мы увидим, что где-то происходит эксклюзивное чтение данных для записи этих данных (BusRdX), то мы перейдём в состояние Invalidate (потому что данные больше не актуальны).

Если же мы находимся в состоянии Invalidate и процессор хочет осуществить запись в какую-либо ячейку памяти, то шина об этом конечно узнает, потому что мы запрашиваем эксклюзивное пользование данными (BusRdX), и мы перейдём в состояние M. Дальше происходит чтение и запись данных. Если мы находимся в состоянии M и кто-то прочитает данные, то мы автоматически перейдём в состояние чтения (S).

*Рис. 34. MSI протокол.

*Рис. 35. Основные действия для данного протокола.

• Недостатки VI: каждая запись обновляет основную память, и каждая запись требует широковещательной передачи и слежки.
• MSI: возможность реализации кэша с обратной записью (writeback) + удовлетворяет локальную запись.

Оптимизация MSI: состояние E

Наблюдение: выполнение последовательной чтения-изменения-записи на частных данных является обычным делом.

В чём проблема MSI?

• Две данные транзакции для каждого чтения-изменения-записи частных данных.

Решение: Е-состояние (Exclusive)

• Если данные ни с кем не разделяются, то чтение переводит строку в состояние E вместо состояния S.
• Запись не вещается на шину, потому что E → M (exclusive).

MESI: усовершенствованный

Каждая строка в кэше содержит тег и биты состояния:

• M: Modified Exclusive.
• E: Exclusive, unmodified.
• S: Shared.
• I: Invalid.

*Рис. 36. Протокол MESI: усовершенствованный.

Когерентность кэш и ложное совместное использование

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

*Рис. 37. Строка кэша.

Предположим P₁ записывает wordᵢ и P₂ записывает wordₖ и оба слова имеют один и тот же адрес строки. Что может произойти?

Из-за того что присутствуют алгоритмы когерентности, будет происходить пинг-понг. Строка может быть недействительной (пинг-понг) много раз без необходимости, потому что адреса находятся в одной строке.

Основные материалы лекции

1. Ссылка на видеозапись лекции
2. Ссылка на лекцию в формате Power Point