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

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

Общий принцип развития компьютерной техники:

1. Актуальная задача
2. Решение задачи современными техническими методами
3. Превращение этого решения в легаси на многие десятилетия

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

Требования:

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

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

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

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

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

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

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

• Понятие «контекст задачи» и оперативное переключение между ними
  • сохранение контекста (регистров, специальных регистров и т. п.) и восстановление
  • аппаратное? а где и сколько контекстов хранить?
• Общая память — доступ одной задач к памяти другой
  • Ядро должно это уметь — supervisor mode
  • Обычные задачи — нет — user mode
  • Фрагментация и непрерывность памяти отдельной задачи

Блок управления памятью (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, при этом потоков столько, сколько требуется для работы
  • (есть ещё уровень гипервизора)

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

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

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

Отличия от многоядерности:

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

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

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

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

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

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

  • Кроме кеша

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

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

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

  • И мы можем узнать, что это был за байт, потому что закешированные значения читаются быстрее

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

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

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

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

Решение: второй уровень косвенности, при котором операционная система запускается под управлением гипервизора.

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

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

Бонусы:

• дедупликация памяти
• Таки равномерная загрузка до 100%
• Резкое сужение аппаратного разнообразия внутри appliance (унификация виртуализованных устройств)
  • ⇒ облака, миграция appliance-ов между узлами и т. п.

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

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

• Hypervisor
• Supervisor
• User