Параллельные вычисления
Потоки и процессы
Дейкстра, Хоар и рождение проблемы синхронизации
1965 год: Эдсгер Дейкстра формализует понятие семафора и описывает проблему critical section. Его статья 'Solution of a Problem in Concurrent Programming Control' - первое строгое определение race condition. 1968: Дейкстра описывает Dining Philosophers - классический пример deadlock. 1978: Хоар разрабатывает CSP (Communicating Sequential Processes) - альтернативный подход через передачу сообщений вместо shared memory. Go channels и Erlang actors - прямые наследники этой идеи. Флинн в 1966 классифицирует параллельные архитектуры (SISD/SIMD/MIMD) - фундамент теории параллельных вычислений.
Node.js обрабатывает 100,000 запросов в секунду в одном потоке. Java Tomcat по умолчанию создаёт по потоку на запрос - и упирается в 1000 concurrent connections. Не потому что один язык быстрее другого. Потому что архитектура потоков и процессов определяет, где будет bottleneck.
- **Chrome** - отдельный процесс на каждую вкладку и расширение: crash в одной вкладке не убивает браузер
- **Python gunicorn** - запускает worker processes (не threads) для обхода GIL: 4 worker processes = 4 ядра
- **Java Tomcat** - thread pool по 200 потоков: один поток на HTTP-запрос, ~50 KB overhead каждый
- **Nginx** - worker processes равные числу ядер, каждый в event loop: без context switch под нагрузкой
- **Go runtime** - 1 goroutine = ~2 KB памяти vs ~50 KB OS thread: миллион goroutines реально работают
- **LMAX Disruptor** - ring buffer + busy-wait потоки: 6 млн транзакций/с без единого context switch
Предварительные знания
Потоки (Threads)
PyTorch обучает нейросеть на 8 GPU. Каждый GPU-worker - отдельный поток. Все потоки видят одни веса модели в памяти. Градиент обновляется из нескольких потоков одновременно - и если синхронизация неверна, веса расходятся. Это и есть суть: **потоки** - несколько линий выполнения внутри одного процесса, делящих общее адресное пространство.
| Что общее у потоков | Что у каждого потока своё |
|---|---|
| Адресное пространство (heap) | Стек (stack) ~8 MB по умолчанию |
| Открытые файлы и сокеты | Регистры процессора (RAX, RBX, RSP, RIP) |
| Глобальные переменные | Program counter (PC) |
| Код программы | Локальные переменные |
| Аллоцированная память | Thread ID + сигнальная маска |
**Поток** - наименьшая единица выполнения, планируемая ОС. Создание потока стоит ~10-50 KB на стек и ~1 мкс CPU. Именно поэтому Java Tomcat поднимает сотни потоков под нагрузку. Проблема не в создании - проблема в **race conditions**: когда два потока читают и пишут одну ячейку памяти без синхронизации, результат непредсказуем.
Тысячи потоков - уже bottleneck. Не из-за памяти, а из-за context switching. Linux переключает поток каждые 4-15 мс по таймеру. При 1000 потоках на 8 ядрах - 125 потоков на ядро, переключение каждые 50-100 мкс. L1/L2 кеш постоянно "холодный" для каждого следующего потока. Именно поэтому Go goroutines и Rust tokio используют пользовательский M:N планировщик - сотни тысяч зеленых потоков на небольшом числе OS threads.
Два потока одновременно выполняют shared_counter += 1. Какой результат возможен?
Процессы (Processes)
Chrome держит по процессу на каждую вкладку. Сайт на JavaScript зависает в бесконечном цикле, пожирая CPU - другие вкладки не замедляются. Это **процессная изоляция**: каждый процесс живёт в собственном адресном пространстве. Ядро ОС строго разделяет их через MMU. Один процесс физически не может прочитать память другого без явного IPC.
| Свойство | Потоки (Threads) | Процессы (Processes) |
|---|---|---|
| Память | Общая (shared) | Изолированная (private) |
| Создание | ~1 мкс, ~50 KB | ~1 мс, ~MB (fork копирует page tables) |
| Коммуникация | Через общую память - наносекунды | IPC: pipe/socket/shm - микросекунды-миллисекунды |
| Crash isolation | Один поток падает - весь процесс | Один процесс падает - остальные живы |
| Безопасность | Race conditions, shared state bugs | Изоляция MMU по умолчанию |
| GIL (Python) | GIL блокирует CPU-параллелизм | Каждый процесс имеет свой GIL |
**IPC** (Inter-Process Communication): **pipes** - однонаправленный поток байтов, ~50 MB/s; **shared memory** - общий участок RAM через mmap, скорость памяти; **sockets** - универсально, работает по сети, ~10 мкс overhead; **message queues** - POSIX mq, асинхронно. Gunicorn и uWSGI выбирают процессы именно для обхода Python GIL - каждый worker независимо утилизирует одно ядро.
Python GIL не позволяет потокам выполнять Python-код параллельно. Как обойти это для CPU-bound задач?
Context Switch и его скрытая цена
Linux переключает поток по таймеру каждые 4-15 мс. Прямая стоимость: сохранить 168 байт регистров, загрузить следующие 168 байт, обновить указатель стека. Это ~1-5 мкс. Но реальная цена в 10-100 раз выше - **cache pollution**. После переключения L1/L2 кеш заполнен данными предыдущего потока. Следующий поток первые 50-200 мкс работает на cache miss latency вместо cache hit latency.
| Операция | Прямая стоимость | Реальная стоимость |
|---|---|---|
| Thread -> Thread (тот же процесс) | ~1-5 мкс | ~50 мкс с cache warmup |
| Process -> Process | ~5-30 мкс | ~100-300 мкс с TLB flush + cache |
| TLB miss после switch | ~100 нс x N | N = тысячи при холодном старте |
| L1 cache miss | ~4 нс | vs L1 hit ~1 нс - x4 разница |
| L2 cache miss | ~12 нс | Добавляет latency к каждой операции |
Вот почему **thread pools** эффективнее создания потока на каждый запрос. Java ExecutorService, Python ThreadPoolExecutor, Go goroutines - все держат пул готовых потоков. LMAX Disruptor (торговая система, 6 млн транзакций/с) идёт дальше: worker threads в busy-wait loop, никаких context switch вообще. Цена - 100% CPU на ядро даже в простое.
На сервере с 4 ядрами запущено 400 потоков, все CPU-bound. Что произойдёт с производительностью?
Планирование: CFS и EEVDF
Кто решает, какой поток запустить следующим? **Планировщик** (scheduler) ядра ОС. Linux с 2007 использует **CFS** (Completely Fair Scheduler). Идея простая: у каждого процесса есть виртуальное время (vruntime) - счётчик того, сколько CPU он получил. Следующим запускается тот, у кого vruntime меньший. Структура данных - red-black tree, O(log n) для выбора минимума.
| Алгоритм | Принцип | Используется в |
|---|---|---|
| Round Robin | Каждому фиксированный квант 10-100 мс | Встроенные системы, учебные ОС |
| Priority-based | Высший приоритет запускается первым | SCHED_FIFO/SCHED_RR в Linux для realtime |
| CFS (Linux 2.6.23+) | vruntime - кто меньше работал, тот следующий | Все обычные процессы Linux/Android |
| EEVDF (Linux 6.6+) | CFS + earliest eligible virtual deadline | Интерактивные задачи, низкая latency |
**CFS vruntime**: после каждого кванта vruntime(процесса) += delta_exec * (NICE_0_WEIGHT / weight). Процесс с nice=-20 получает в 88 раз больше CPU, чем с nice=19. Для realtime задач Linux предоставляет SCHED_FIFO (работает до явного yield) и SCHED_RR (round-robin среди RT) с приоритетом над CFS. Аудио-серверы (PulseAudio, PipeWire) используют SCHED_RR для гарантированного latency.
Threads всегда лучше processes, потому что они легче
Потоки быстрее создаются и обмениваются данными, но процессы безопаснее (crash isolation) и обходят GIL в Python. Go goroutines - компромисс: пользовательские потоки с M:N мультиплексированием на OS threads.
Threads разделяют память - быстрая коммуникация, но race conditions и один упавший поток убивает весь процесс. Chrome выбрал processes ради безопасности (sandbox). Nginx выбрал worker processes ради стабильности. Python gunicorn - ради обхода GIL. Выбор зависит от требований: threads для shared-state, processes для изоляции и CPU-bound.
В Linux CFS: процесс A (nice=0) и процесс B (nice=10). Кто получит больше CPU-времени?
Ключевые идеи
- **Потоки** разделяют память процесса - коммуникация за наносекунды, но race conditions и падение одного убивает всех
- **Процессы** изолированы через MMU - crash isolation и обход Python GIL, но IPC стоит микросекунды-миллисекунды
- **Context switch** стоит ~1-30 мкс прямо, но cache pollution добавляет 50-300 мкс реально
- **CFS** в Linux: red-black tree по vruntime, O(log n), nice=-20 даёт в 88 раз больше CPU чем nice=+19
- **Go goroutines** и **Rust tokio** обходят OS context switch через M:N мультиплексирование - сотни тысяч корутин на десятках OS threads
- Для CPU-bound оптимально N потоков/процессов по числу ядер; для I/O-bound - async/event loop эффективнее
Связанные темы
Потоки и процессы - фундамент для понимания параллельных систем:
- Синхронизация — Mutex, semaphore, barrier - инструменты координации потоков
- Зачем нужен параллелизм — Потоки и процессы - реализация параллелизма из предыдущего урока
- ОС: потоки и планировщик — Как ядро Linux создаёт и планирует потоки
Вопросы для размышления
- Почему Go выбрал goroutines вместо OS threads? В чём преимущество пользовательского M:N планировщика?
- Если бы Python не имел GIL, изменился бы выбор между threading и multiprocessing?
- Почему Nginx с worker_processes = 4 и event loop на каждый процесс эффективнее, чем 400 потоков на 4 ядра?
Связанные уроки
- par-01 — Мотивация параллелизма из предыдущего урока
- par-03 — Синхронизация потоков через mutex, semaphore, barrier
- os-02-processes — Внутреннее устройство процессов в ядре ОС
- os-03-threads — Планирование потоков и механика context switch
- os-04-scheduling — Алгоритмы планировщика: CFS, EEVDF, SCHED_FIFO
- arch-14-multicore — Multicore - аппаратная база, на которой живут потоки