Поддержка многозадачности, многоядерность и виртуализация (обзор)

Темы без привязки к практике.

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

Общая задача масштабирования

Требования:

0. Простой процессора ⇒ запуск нескольких задач в режиме разделения времени
   • Скорее всего, пакетный вариант (задача или успевает отработать за один запуск, или снимается с выполнения + очередь таких задач)
1. (условное) Разделение задач на «обменные» и «счётные»: пока обменная задача ждёт конца операции ввода-вывода, счётная может немного посчитать
   • Вытесняющая многозадачность с приоритетом и планировщиком
   • Виртуализация памяти для задач, MMU
2. Если очередь велика или их несколько (сложные/перегруженные/реалтайм операционные системы и комплексы), возникает необходимость актуально одновременного (а не вытесняющего) выполнения задач
   • ⇒ многоядерность и многопоточность
3. Простой процессора ⇒ запуск нескольких программных окружений (ядер ОС)

   • Виртуализация ресурсов, в первую очередь внешних устройств, а для памяти — двойная виртуализация (например, виртуальный MMU для ядра)

Вытесняющая многозадачность

Общий алгоритм:

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

Правила смены контекстов определяет т. н. «планировщик» (scheduler) — часть ядра

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

Понятие «контекст задачи» и оперативное переключение между контекстами

• сохранение контекста (регистров, специальных регистров и т. п.) и восстановление

Аппаратное решение — а где и сколько контекстов хранить? Программное — а насколько это быстро?

Общая память — доступ одной задачи к памяти другой

• Ядро операционной системы должно это уметь, чтобы формировать адресные пространства задач и управлять ими
• Обычные задачи — только по согласованию с ядром (обычно — нет)

Решается заданием двух режимов работы процессора, которые отличаются правами — supervisor mode (режим ядра, при котором доступна вся физическая память и все инструкции процессора) и user mode (пользовательский режим, в котором доступен ограниченны набор инструкций процессора, а сами user-mode задачи могут выполняться в изолированном адресном пространств)е).

Изоляция адресных пространств порождает проблему фрагментации памяти, выделенной под задачу: допустим, мы запустили 200 задач, каждой из которых было выделено по мегабайту. После чего каждая вторая завершалась. Можно ли освобожденные 100 мегабайт выделить новой задаче в качестве единого фрагмента памяти?

Решение: Блок управления памятью (MMU):

• Виртуализация памяти отдельной задачи:

  • специальные доступные только в supervisor mode регистры, т. н. Буфер ассоциативной трансляции (TLB), определяют, какие участки физической памяти склеиваются в единое непрерывное адресное пространство процесса.

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

• Внутри пользовательской памяти можно использовать «плоские» конвенции
• Можно использовать разделяемую память (одна и та же страница в нескольких адресных пространства)

Менее очевидные проблемы:

• Выгорание кешей — множественный очаг активности (нарушение принципа локальности + больший суммарный объём «горячего отпечатка»)
• Опосредованный доступ к ресурсам только через ядро ОС⇒ частое переключение контекстов
  • Одно время была (ещё не прошла) мода на микроядра — там эта проблема стояла особенно остро
• Большой разброс между пиковым, маршевым и «ленивым» потреблением ресурсов
  • ⇒ paging (выгрузка отдельных страниц на «большое» устройство хранения) и swap (выгрузка целых процессов)

Дублирование вычислительных устройств

Причины появления:

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

Решением этой задачи были векторные и суперскалярные варианты архитектуры (о них мы упоминался в лекции про конвейер и предсказание переходов

• реалтайм-системы — нужна поддержка нескольких одновременно работающих процессов

• критичные к своевременному выполнению участки кода (как минимум ядра)

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

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

Исторически первое, более «простое» решение (нет) — использовать два или более процессоров в одной вычислительной системе

• Воткнём несколько процессоров в системную плату (или даже в одном камне изваяем)
• Память и внешние устройства при этом остаются общими

• Обеспечим последовательный доступ к контроллеру прерываний и памяти

• …
• Процессы работают физически одновременно
• Profit!

Проблемы:

• Последовательный доступ — это очень медленно
• Многоканальный доступ (параллельный по нескольким каналам) — это арбитраж и тупики (контроллеры памяти и прерываний усложняются в разы)
  • Он всё равно последовательный, если задача больше,чем каналов

• Синхронизация и когерентность кешей

• Физическое / топологическое различие скорости доступа к памяти, NUMA и вообще сверхвысокое межпроцессорное взаимодействие

• MMIO тоже требует дополнительной прослойки (видимо, тот же контроллер памяти?)
• …

Аппаратная многопоточность (hardware threads, harts)

Вводятся две абстракции:

• Окружение (execution environment) — полное описание среды, в которой запускается программа.
  • В случае «чистого железа» это собственно процессор, модель памяти, уровни выполнения, MMIO и т. п., и собственно hart-ы.
  • Однако с точки зрения программы, выполняемой, допустим, на уровне user, окружение частично виртуализовано (память, MMIO) и обладает другой логикой (например, ecall и ebreak обращаются «неизвестно куда», может вообще не быть прерываний и т. п.).

• Поток (hardware thread, hart) — это часть окружения, которая самостоятельно выбирает инструкции из памяти и исполняет их. Поток должен быть быть минимум один, но бывает и несколько. Применение потоков (упреждающее выполнение, программный параллелизм, иное) не фиксировано. Потоки могут пользоваться одной и той же памятью (в терминах окружения), полностью разной или частично пересекающейся. До тех пор, пока выполнение идёт в рамках окружения, оно отвечает за логику выполнения потоков (своевременное переключение, доступ и т. п.); при выходе за пределы окружения (например, обработка или ожидание прерывания, ecall и т. п.) — нет.

  • На уровне Machine потоки реализованы аппаратно (возможно, аппаратная поддержка переключения контекстов, несколько регистровых блоков и т. п.); их фиксированное число, возможно, один.
  • На уровне Supervisor ядро ОС пользуется потоками вышестоящего уровня для создания окружений уровня User, при этом потоков столько, сколько требуется для работы
  • (есть ещё уровень гипервизора)

(Про execution environment и hart в спецификации, См. также Hyper-threading)

Модель доступа к ресурсам (в первую очередь памяти, и, как следствие, MMIO) оперирует понятием hart в качестве субъекта доступа.

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

• Работа с несколькими контекстами выполнения (в том числе вложенными)
  • ⇒ Экономия (если она нужна) на переключении контекстов за счёт аппаратной поддержки

• Логически доказуемая безопасная модель «слабо упорядоченного» доступа к памяти

  • разъяснения

  • Формальное описание на языке Alloy

Что произойдёт, если не строить такую модель?

• Допустим, у нас есть кеш, предсказание переходов и упреждающие вычисления на уровне Machine (или ниже, на микропрограммном уровне)

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

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

  • Кроме кеша

  • Правда, мы сами прочитать кеш не можем — память-то не наша

• Тогда дополним этот цикл куском, в котором прочитанной из памяти значение используется как индекс для доступа к нашему массиву на 256 элементов

  • Если упреждающее вычисление достаточно глубокое, прочтётся и закешируется не только чужой байт, но и соответствующая ячейка нашего массива

  • Теперь сравним скорость чтения всех ячеек массива. Одна из них прочитается быстрее — она закеширована

  • Её индекс — это значение байта из чужой памяти

• Profit!

Это было краткое описание семейства атак Spectre

Какие задачи hart не решает:

• Не повышается быстродействие (в смысле инструкций в секунду)
• Нет актуального параллелизма — вычислчительное ядро может быть одно
  • ⇒ Нет необходимости в межпроцессорной связи
  • ⇒ Нет необходимости в двуслойном кеше
  • Простая логика контроллера прерываний (только «распределение ответственности» + исходная логика)

Виртуализация

Задача

равномерная/произвольная загрузка вычислительных мощностей готовыми «окружениями»

Условие

«окружение» — это операционная система, уже состоящая из двух уровней: ядра и юзерспейса

Решение

+ещё один уровень приоритета, при котором операционная система (ядро + юзерспейс) запускается под управлением гипервизора.

Аппаратные потребности:

• Разделение на режим гипервизора (host, больше прав) и режим супервизора (guest, меньше прав)
• Виртуализация устройств В/В, чтобы ими могли пользоваться операционные системы

  • Т. н. паравиртуализация: вместо того, чтобы имитировать реальное устройство (например, сетевого интерфейса) со всем аппаратным legacy, гипервизор предоставляет ядру простое полностью виртуальное устройство (в случае сети или диска — т. н. Virtio). Паравирутализованное устройство, с одной стороны, унифицировано и удобно в управлении со стороны гостевой системы, а с другой — может по определённым правилам непосредственно использовать ресурсы «настоящего» устройства. Таким образом по сравнению с полной эмуляцией быстродействие снижается незначительно; более того, зная о вирутальной природе устройства, ядро гостевой системы может распоряжаться им более эффективно.

• «Проброс» реального железа в окружение
  • Актуально, например, для видеокарт / GPU

• Трёхуровневый кеш: третий уровень — общий для всех ядер

• Ещё больше ада с прерываниями, DMA и MMIO

Бонусы:

• Дедупликация памяти: аппаратное определение идентичных страниц памяти в различных окружениях. Относится к страницам памяти, запись в которые не производится. Встречается довольно часто на «фермах» с идентичными операционными системами: скорее всего, можно будет дедуплицировать часть памяти ядер, общие библиотеки, неизменяемую часть приложений и т. п.
• Потенциально равномерная загрузка до 100% (⇒ отработка энергетического ресурса). В больших дата-центрах проблема энергопотребления и отвода тепла становится очень значимой.
• Резкое сужение аппаратного разнообразия внутри окружений (унификация виртуализованных устройств)
  • ⇒ облака, миграция окружений между узлами и т. п. становится намного проще

BTW: RISC-V — 4 уровня

1. Machine (первоначальный старт и инициализация, аппаратные hart-ы)

2. Hypervisor — уровень виртуализации
3. Supervisor — уровень ядра
4. User — пользовательский уровень

Всё остальное

Железо:

• использование GPU
• кластеризация и облака
• суперкомпьютерные архитектуры
• (накидайте ещё тем!)

Программирование:

• программирование на Ассемблере и Си
• ядро ОС и его логические компоненты
• взаимодействие с аппаратурой из ЯП ВУ
• (накидайте ещё тем!)

…нельзя объять необъятного!