В прошлой статье я немного слукавил, сказав, что мы будем разбирать атомики, барьеры и системные вызовы. Я пару дней поразмышлял и осознал – а зачем вообще это объяснять, если мы даже не знаем про причину их возникновения и проблемы, которые они решают
В части 1.1 мы рассмотрели базовые инструкции, которые выполняет наш CPU и которыми в конечном счете и являются наши прекрасные строчки на Go. Но возникает закономерный вопрос: “Окей, мы поняли как работает на одном ядре, но Go у нас во многом про многопоточку, соответственно как это будет работать на нескольких потоках?”
Если что, то это часть большого цикла по разбору Go! Данная статья – это подводка уже к тому, с чем мы имеем дело в Go достаточно часто(барьеры памяти, атомики, сисколы)
В этот раз будет без Go Assembler, но с +- реальными примерами, если что-то непонятно будет, то на Хабре есть классный ИИ-помощник
Многозадачность
Хоть мы и развенчиваем в этом цикле абстракции, придется немного к ним вернуться. Но ненадолго!
Вспоминаем, как у нас выполняются инструкции в процессоре и представляем следующую конфигурацию:
Есть какое-то количество ГБ RAM
Есть 1 ядро CPU
Соответственно в один момент CPU может выполнять ровно 1 набор инструкций
Но почему-то всё во времена одноядерных CPU работало непрерывно…
На самом деле нет!
Работало еще как с прерываниями(не путать с теми, которые interrupt), просто настолько быстро, что мы были неспособны это осознать, а для того, чтобы успевали работать фоновые службы, приложения и что бы то ни было ещё как раз и придумали многозадачность!
Введем определение
Многозадачность – это способность операционной системы выполнять несколько программ или потоков одновременно (или псевдопараллельно), быстро переключая процессор между ними
И вот ключевое здесь пока что для нас – “быстро переключаясь”. А схемы работы исторически было предложено 2:
-
Кооперативная
-
Прерываемая
Начнем с кооперативной. На самом деле, это интуитивное решение, что называется “в лоб”. Схема работы очень простая:
1) CPU начинает выполнять задачу
2) CPU исполняет инструкции задачи
3) Задача добровольно передает управление
4) CPU начинает выполнять следующую задачу
Вот упрощенный пример на x86-64 в Linux:
yield_cpu:mov rax, 24 ; Номер системного вызова sched_yield. Это означает системный вызов на “уступание” CPUsyscall ; сам вызов сискола. Инструкция процессора перехода из user mode в kernel mode.ret_start:; "task A"mov rsi, msg1 ; msg1 помещаем в rsimov rdx, len1 ; len1 помещаем в rdxcall yield_cpu ; добровольно отдаем CPU; "task B"mov rsi, msg2 ; msg2 помещаем в rsimov rdx, len2 ; len2 помещаем в rdxcall yield_cpu ; снова добровольно отдаем CPU
Чувствуете запах зависания? Я тоже. Действительно в Windows 3.1 например могла повиснуть программа(и вместе с ней ОС) на бесконечном цикле. В целом, это и есть ключевая проблема кооперативной многозадачности
Теперь про прерываемую многозадачность:
Как ясно из названия, в схеме работы такой многозадачности кто-то эти самые задачи прерывает и обычно это таймер планировщика.
Для понимания прерываемой многозадачности нам следует ввести также понятие
Прерывание процессора – это механизм, позволяющий системе приостановить выполнение текущей программы для немедленной обработки внешнего или внутреннего события, а после чего система может вернуться к прерванному коду
Схема работы тут уже такая:
1) CPU начинает выполнять задачу
2) CPU исполняет инструкции задачи
3) Аппаратный таймер генерирует interrupt, либо задача заканчивается(-> п.5)
4) CPU передает управление обработчику прерывания (interrupt handler)
5) Планировщик выбирает следующую задачу
Вот упрощенный пример на x86-64 в Linux:
task: mov rax, 1 ; какая-то работа задачи mov rbx, 2 ; еще работа add rax, rbx ; считаем ; <- в этот момент может прийти прерывание таймера sub rax, 1 ; после возврата продолжаем отсюда jmp task ; задача крутится дальшеtimer_interrupt: ; обработчик прерывания push rax ; сохраняем часть контекста push rbx ; сохраняем регистры ; здесь логика ядра / планировщика ; можно выбрать другую задачу pop rbx ; восстанавливаем регистры pop rax ; восстанавливаем контекст iret ; возврат в прерванную точку
Отмечу отдельно, что процессор автоматически сохраняет часть контекста (RIP, CS, RFLAGS) перед переходом в обработчик.
У кого-то может возникнуть вопрос, откуда процессор знает про timer_interrupt. Вопрос резонный. Процессор не знает конкретный обработчик заранее. Он использует таблицу прерываний (IDT), которую заполняет операционная система. В ней каждому номеру прерывания соответствует адрес обработчика
А вот теперь интересный момент. Допустим, задача прервалась и наш дорогой CPU переключился на другую задачу, не выполнив прерванную.Очевидно, что прерванную надо как-то восстановить позже, чтобы всё-таки доделать.
И вот мы познакомились с одной из задач RAM – временно хранить данные о задачах, которые состоят из:
-
Значений регистров процессора для данной задачи
-
Указателя текущей инструкции (RIP)
-
Указателя стека (RSP)
-
Регистра флагов (RFLAGS)
-
Данных, лежащих в стеке
Это называется контекстом задачи
Зафиксируем:
Контекст задачи — это состояние процессора, которое нужно восстановить, чтобы продолжить выполнение
Переключение контекста(context switching) – это операция сохранения контекста одной задачи и загрузки контекста другой
В упрощённом виде это выглядит как сохранение регистров в память (push) и восстановление их позже (pop). Кстати, часть контекста процессор переносит в RAM сам
Многопоточность
В процессе эволюции, развитие(увеличение) производительности однопоточных CPU по закону Мура замедлилось, но вот проблема – требования к софту росли и в 2002 году Intel представила технологию Hyper-Threading в процессорах Pentium 4. Она позволила одному физическому ядру выполнять два потока инструкций одновременно, что операционная система воспринимала как два логических процессора.
На уровне CPU корректнее говорить о многоядерности и SMT, тогда как многопоточность — абстракция ОС и языков программирования. Что при этом интересно, разделяются физические и логические ядра.
Физическое ядро — это реальный вычислительный блок процессора, содержащий конвейер исполнения инструкций, арифметико-логические устройства, кэши и другие элементы, необходимые для выполнения программы.
Логическое ядро — это виртуальное вычислительное ядро, которое операционная система видит как отдельный процессор, но которое делит часть ресурсов физического ядра с другим логическим ядром
Хотя прожжённые линуксоиды уже наверняка вспомнили, что в Linux можно ограничивать, на каких ядрах будет выполняться процесс. Например, можно закрепить задачу только за физическими ядрами или наоборот — разрешить ей работать лишь на логических потоках одного ядра. Это делается с помощью механизма CPU affinity, который позволяет управлять распределением процессов по ядрам процессора
Заметим, что
-
Каждое ядро выполняет свой поток инструкций независимо
-
Регистры у каждого ядра свои
-
RAM общая
Поэтому два потока могут одновременно читать и писать одну и ту же память и выполнять инструкции независимо
Давайте не будем томить и рассмотрим, как вообще выполняются инструкции на нескольких ядрах
; Пусть у нас есть 2 потока:; Thread A Linux запустил на Core 0; Thread B Linux запустил на Core 1thread_a:mov rax, [counter] ; Core 0 читает counter из RAM в свой raxadd rax, 1 ; Core 0 увеличивает значение в своем регистреmov [counter], rax ; Core 0 записывает новое значение обратно в RAMjmp thread_a ; повторяемthread_b:mov rax, [counter] ; Core 1 читает counter из RAM в свой raxadd rax, 1 ; Core 1 увеличивает значение в своем регистреmov [counter], rax ; Core 1 записывает новое значение обратно в RAMjmp thread_b ; повторяем
Что же тут особенного? Почему нет каких-то специфических инструкций? А все очень просто!
Процессор сам по себе не настолько умен. Глобально – он лишь занимается исполнением разного рода инструкций, поэтому решение относительно того, какое конкретно ядро будет исполнять необходимые инструкции лежит на планировщике ОС.
Но откуда он вообще знает, о том какие ядра у нас есть?
А вот тут уже процессором предусмотрена инструкция CPUID, с помощью которой ядро может узнать характеристики процессора:
-
Количество физических ядер
-
Количество логических потоков
-
Топологию CPU
Далее BIOS или UEFI передают эту информацию ядру в его таблицу аппаратуры
-
ACPI tables
-
MADT (APIC table)
После инициализации ядро присваивает каждому процессору идентификатор (CPU ID):
CPU 0
CPU 1
CPU 2
CPU 3
Например так
Кому интересно, на Linux можете посмотреть это так:
cat /proc/cpuinfo
То есть при появлении новой задачи планировщик помещает её в очередь выполнения одного из CPU!
Процессорные кэши
До этого момента мы исходили из упрощённой(и староватой) модели:
CPU + RAM
По факту, если использовать только RAM, то CPU в основном только и будет, что ждать данные оттуда т.к. RAM – устройство медленное в масштабах железа. Даже современная оперативная память имеет задержки в десятки наносекунд, тогда как процессор выполняет инструкции за единицы наносекунд. Время простоя представили на многозадачности?
Чтобы решить эту проблему, в архитектуру процессоров были введены кэши!
Уверен, что многие видели эту схему кучу раз
Но… мы её рассмотрим для общей картины.
L1 Cache
Самый быстрый и самый маленький.
Размер ~32–64 KB
Задержка ~4 такта
Обычно отдельный для инструкций и данных
Он находится внутри каждого ядра.
L2 Cache
Больше по размеру, но медленнее
размер ~256 KB – 1 MB
задержка ~10–15 тактов
Чаще всего также принадлежит одному ядру
L3 Cache
Самый большой и самый медленный из кэшей.
размер ~8–40 MB
задержка ~30–50 тактов
Обычно общий для всех ядер процессора
Часто выполняет роль буфера между ядрами и RAM
И вот возникают несколько логичных вопросов:
-
Зачем нам уровни кэша?
-
Кто принимает решение о помещении в кэш?
-
И какие вообще у них назначения?
Главная причина разделения на уровни — компромисс между скоростью, размером и стоимостью памяти, потому что чем память быстрее, тем она:
-
Дороже
-
Меньше
-
Сложнее масштабируется
Физически невозможно сделать огромный и быстрый кэш, поэтому пришлось разделять!
Вот примерное время доступа к разным уровням памяти:
Регистры ~1 такт
L1 cache ~4 такта
L2 cache ~12 тактов
L3 cache ~40 тактов
RAM ~100-300 тактов
Но кто же все-таки принимает решение о размещении чего-либо в кэше?
Ответ: Сам процессор. Ни ядро ОС, ни пользователь не могут управлять кэшами, это делает аппаратная логика процессора (cache controller)
Но уже чувствуется ситуация, когда в таком случае разные ядра могут иметь собственные копии фрагментов из L3 в своих L1/L2
Чтобы разные ядра не работали с устаревшими данными, процессоры используют cache coherence protocols.
Самый известный – MESI
Он следит за тем, чтобы в случае когда одно ядро изменило данные, другие ядра получили обновление
Строка кэша(сache line) – это минимальный блок данных, которым процессор обменивается между кэшем и оперативной памятью. Обычно 64 байт для большинства современных x86-64 процессоров
Название MESI – это аббревиатура четырёх состояний, в которых может находиться cache line:
M – Modified
E – Exclusive
S – Shared
I – Invalid
Modified
Cache line изменена текущим ядром и отличается от значения в RAM
Только одно ядро владеет данными
RAM устарела
При необходимости данные позже будут записаны обратно в память
Exclusive
Cache line находится только в одном кэше и совпадает с RAM
Ядро может изменить её без уведомления других
Shared
Одна и та же cache line присутствует в нескольких кэшах
Данные можно читать
Но изменять нельзя без invalidation других копий
Invalid
Cache line считается недействительной
Ядро должно заново запросить данные
Но даже несмотря на существование протоколов согласованности кэшей, проблема полностью не исчезает
Рассмотрим ситуацию, когда два ядра работают с одной и той же переменной
; Представим, что поток A выполняется на Core 0, а поток B — на Core 1.mov rax, [counter]add rax, 1mov [counter], rax
А теперь что происходит в состоянии процессора:
1) Core 0 читает counter
RAM → L3 → L2 → L1 (Core 0)
Cache line получает состояние Shared
2) Core 1 читает counter
RAM → L3 → L2 → L1 (Core 1)
Теперь оба ядра имеют копию cache line
3) Core 0 хочет изменить значение
Чтобы записать данные, ядро должно получить эксклюзивное владение cache line.
По протоколу MESI происходит:
Core 0 → инвалидирует cache line у других ядер
Core 1 вынужден выбросить свою копию
4) Теперь Core 1 снова хочет изменить значение
Теперь происходит обратный процесс:
Core 1 → инвалидирует cache line у Core 0
Получается, что cache line начинает прыгать между ядрами.
Core 0 <-> Core 1
Core 0 <-> Core 1
Core 0 <-> Core 1
Следовательно, становится ясно, что такая ситуация приводит к накладным расходам из-за:
-
Задействования MESI
-
Инвалидации кэша
Что портит нам производительность
Такая ситуация называется состязанием за кэш(cache contention)
Давайте зафиксируем:
Состязание за кэш(cache contention) – это проблема производительности, возникающая в многоядерных системах, когда несколько ядер процессора одновременно пытаются получить доступ к одной и той же строке кэша
Ремарка
Даже если ядра работают с разными переменными из кэша, также может возникать состязание за кэш из-за того, что 2, казалось бы, независимые переменные лежат в одной строке кэша
Состояние гонки
Race condition (гонка данных) – ситуация, когда несколько потоков обращаются к одной памяти без синхронизации и результат зависит от порядка их выполнения
Я думаю, что исходя из вышесказанного становится очевидно, что состояние гонки – это фундаментальная проблема вычислительных систем. Даже на таком примитивном инструменте, как ASM можно легко получить гонку
Допустим 2 ядра выполняют инструкции:
mov rax, [counter]add rax, 1mov [counter], rax
Вроде бы обычный инкремент, но из кода ясно, что операции вообще-то 3:
1) load
2) add
3) store
Становится неясно, кто в какой момент сделает load, инкремент, store. Тут всё по принципу “кто последний store, тот и прав”, но вот вопрос – кто. Ядра соревнуются в получении доступа и обработке данных, между ними происходит гонка, и, собственно в разных случаях выполнения одних и тех же инструкций мы получаем разные результаты – 0, 1, 2
Думаю, что с постановкой проблем мы закончили, теперь делаем JMP на решения этих проблем, но в следующей статье!
ссылка на оригинал статьи https://habr.com/ru/articles/1024868/