Как на самом деле работает параллелизм?

Question

[Sazoks]

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

Текущее понимание
1. У нас есть CPU с, допустим, 4 ядрами. В моем текущем понимании это означает возможность выполнять истинно параллельно 4 потока операций.

2. Если у нас есть технология HyperThreading/SMT, то в некоторых случаях (допустим, когда операция ожидает подгрузку данных из L3-кеша или ОЗУ), ядро может обрабатывать второй конвейер с операциями. Итого имеем 8 логических ядер.
Вопрос 1: правильно ли я понимаю, что 2 конвейера с операциями повышают степень параллелизма каждого ядра (не линейно, конечно)?

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

4. Далее у нас появляется еще одна абстракция - потоки. Потоки - легковесные процессы, которые имеют общую память и более легкие контексты. В связи с этим их быстрее создавать и переключаться между ними, что экономит ресурсы компьютера.
Вопрос 2: правильно ли я понимаю, что с введением потоком "выполнение процесса" автоматически подразумевает под собой выполнение хотя бы одного потока на ядре?
Вопрос 3: правильно ли я понимаю, что пока работает какой-то поток/процесс, они отправляют по общей шине событий операции в конвейеры ядер?
Вопрос 4: существуют userspace-потоки и kernelspace-потоки. Как я понял, разница в том, что в первом случае мы как-то на уровне приложения создаем свои потоки, которые ядра воспринимают как один процесс и ничего не знают в отдельности про каждый поток. Из-за этого такие потоки физически выполняются по очереди. По сути, обычный механизм кооперативной многозадачности без выигрыша в скорости вычисления (т.к. параллелизма тут нет). Если так, то для чего такие потоки нужны (чем они полезны) и как их реализовать, допустим, в Python?
Вопрос 5: kernelspace-потоки выполняются напрямую на ядрах и имеют расширенный контекст. Они занимают больше памяти и переключение в kernel-режим обходится дороже, однако здесь мы приобретаем настоящий параллелизм, и тут выгода понятна. Насколько я понял, такие потоки и создают все встроенные библиотеки (threading в Python, например). Верно ли это утверждение?

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

Заранее большое спасибо за ответы.

Comments

[Sazoks]

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

[mayton2019]

1. У нас есть CPU с, допустим, 4 ядрами. В моем текущем понимании это означает возможность выполнять истинно параллельно 4 потока операций.

Очень малое количество операций может выполняться параллельно.
Например ядра обладают регистрами. И они могут действительно независимо пересылать регистры
ядра туда-сюда или складывать содержимое их или вычитать. На этом истинность заканчивается.

Как только kernel (thread) обращатеся к памяти или к внешним устройствам - тут нет никакого параллелизма.
Становимся в ожидание пока устройство ответит.

пока работает какой-то поток/процесс, они отправляют по общей шине событий операции в конвейеры ядер?

Это очень сложная фраза. Покажи источник где ты это прочитал. Иначе без контекста непонятно.

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

Тоже непонятно. Насчет Python. Я не специалист в этом языке но я думаю что вообще такие аналогии
неправильные и не стоит себе ставить такую задачу. Потоки ОС не обязаны отображаться в потоки языка
или Runtime. Надо читать документацию на ОС и язык. В любом случае ответ на этот вопрос будет
скорее лекцией чем ответом и он тебе поставит новые вопросы.

[Евгений Шатунов]

Sazoks, да нет, у тебя и правда много перемешано в вопросе. С первых строк видно что ты почти все неправильно понимаешь. И у тебя действительно несколько вопросов в одном.
Почему тебе сейчас пишут в комментариях, а не в ответах. Это потому что нормально ответить на твой текст очень тяжело. Я и другие люди так просто экономим свое время.
Подели свое обучение на три этапа. Первый этап - это программный параллелизм, системы планирования, системы разделения времени, системы пакетной обработки, системы реального времени. Второй этап - это архитектура вычислительных систем, SIMD, MISD, MIMD, топологии вычислительных систем и прочее (книга В. Г. Хорошевского). Третий этап - это аппаратный параллелизм современных процессорных архитектур, MESI, многоуровневый кэш и режимы параллельной обработки данных.
Так у тебя должна будет выстроиться единая линия понимания параллелизма.

[hint000]

в кучу я ничего не мешал

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

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

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

Вопрос 3: ...

Бред.

Вопрос 4: ...

Бред.

Вопрос 5: ...

Бред.

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

Мотор автобуса везёт пассажира какое-то время, затем отдаёт управление водителю. :)
Нет. Водитель (ОC) всегда управляет, ему не нужно "передавать управление". ОС решает, какое время работать какому-то процессу. ОС решает, когда прервать выполнение какого-то процесса. Ядро ничего не решает.

[ValdikSS]

Процессор не знает ни про процессы, ни про потоки, это абстракция ОС. Переключение происходит по таймеру: ОС настраивает аппаратный таймер на какое-то время и начинает выполнение процесса, проходит время, срабатывает таймер, отправляет прерывание контролеру прерываний, процессор переключается на обработчик прерываний и понимает, что произошло. И так по кругу.

В некоторых процессорах есть понятие процесса, какое-то время назад оно было и в x86, но едва ли использовалось какой-либо ОС длительное время либо вообще: https://www.maizure.org/projects/evolution_x86_con...

[Sazoks]

mayton2019, спасибо за комментарий! Да, я знаю, что довольно много сомнительных формулировок. Попытался максимально точно описать то, как я все это понял.

Как только kernel (thread) обращатеся к памяти или к внешним устройствам - тут нет никакого параллелизма.
Становимся в ожидание пока устройство ответит.

Но ведь это в рамках одного ядра, верно? Другие ядра могут совершать другие действия параллельно относительно друг друга, разве нет?

[Sazoks]

Юрий, я понимаю, я его упомянул лишь из-за библиотеки threading, т.к. в одной из статей сказано, что такие библиотеки и позволяют создавать kernelspace-потоки, либо я что-то не так понял. На асинхронность.. почему же, все равно ведь этот подход базируется на неблокирующих I/O-операциях, делегируя чтение/запись как раз-таки ядру, что и позволяет асинхронному Python-коду заниматься выполнением других полезных задач, разве нет?

[Sazoks]

Евгений Шатунов, большое спасибо за план и за книгу! Поизучаю. Насчет каши, ну, вероятно вы правы) Затем и обратился к знающим людям, чтоб эту кашу помогли переварить)

[Sazoks]

hint000, спасибо, что объяснили "на пальцах", стало попонятнее немного) Насчет бреда, почему же. Что плохого, что у меня на данный момент нет полных знаний? Тем более это не моя профильная область, мне просто хочется понять чуть лучше внутреннее устройства ОС и принципы работы ЦП. Вопросы задавал в силу своего (не)понимания.

[Василий Банников]

Если так, то для чего такие потоки нужны (чем они полезны) и как их реализовать, допустим, в Python?

Ресурсы экономить в тех ситуациях, когда параллелизм и не нужен.
В Python они собственно уже реализованы - async io

Answer 1

[Алексей Черемисин]

Ну, книги Вам уже посоветовал @firedragon
Я же хочу вкратце ответить на этот замечательный вопрос.
Давайте разберемся с одним CPU без потоков...
Когда процессоры были большими, а люди... В общем, на заре компухтеров был только один поток, и чтобы получить многозадачность, придумали ОС с вытеснением задач.
Смысл в том, что когда завершается "программа", то запускается следующая в очереди (очередь с приоритетом). Задача работает до тех пор, пока не завершится.

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

Но прерывания на ввод-вывод иногда можно ждать долго, и не дождаться. Но умные дяди придумали геренировать прерывания сами себе, от таймера. Да, в молодости это просто кварц и конденсатор, на ножку процессора. И вот, появились ОС с реальной многозадачностью, где система получает управление через сторого определенные промежутки времени - тики или клоки.

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

Ах, да, молодость процессоров - одно прерывание на все сразу :) И крутись, как хочешь :)

Comments

[Sazoks]

Большое Вам спасибо, хороший ответ! Теперь появилась какая-то устойчивая базовая картина и отправная точка для дальнейшего исследования. То, что я и хотел, в целом :)

Answer 2

[Владимир Коротенко]

Хм тут вам помогут книги
Эндрю Таненбаум
Торвальдса
Русиновича
Helen Custer , David N Cutler
David A. Solomon
https://slideplayer.com/slide/6865915/

Гляньте вот на эту презентацию https://www.hse.ru/data/2010/12/24/1223886397/%D0%...

А вот тут прикладная часть
https://basis.gnulinux.pro/ru/latest/basis/15/15._...

В общем тема большая и гуглить вам много, но основных авторов я дал

Comments

[Sazoks]

Большое спасибо!

Answer 3

[Vamp]

Вопрос 1. Два конвейера позволяют только сократить накладные расходы на context switch. Параллелизм это не увеличивает, так как вычислительное ядро по-прежнему одно.

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

Вопрос 3. Нет. Процессор сам подгружает инструкции из кеша/основной памяти. Потоки не совершают никаких дополнительных действий для этого. Всё происходит прозрачно для потока.

Вопрос 4. Kernelspace и userspace потоки отличаются только тем, в каких кольцах они исполняются. Kernel потоки исполняются в привилегированных кольцах, а user потоки в непривилегированных. Во всём остальном эти потоки ничем друг от друга не отличаются. Кольца ограничивают набор процессорных инструкций и системных вызовов, которые поток может использовать. Например, чтение файла с диска - это привилегированная операция (так как требует прямого доступа к девайсу), поэтому когда обычный userspace поток хочет прочитать файл, ОС приостанавливает userspace поток и передаёт управление kernelspace потоку, у которого достаточно привилегий на выполнение данной операции.

Кооперативную многозадачность можно сделать и самому. Концепция называется green threads. В языках программирования встречается уже готовая реализация грин тредов, только называется иначе: корутины (python), горутины (go), виртуальные потоки (java). Все они делают одно и то же - реализуют кооперативную многозадачность в userspace. При большом желании можно написать и свою реализацию грин тредов без использования уже готовых языковых инструментов. Хотя практического смысла в этом мало (кроме нарабатывания опыта).

Вопрос 5. Думаю, ответ на этот вопрос очевиден из ответа на предыдущий.

И всё же под "kernel" обычно подразумевают ядро ОС, а не ядро процессора (которое называют core, а не kernel). Единственный способ запустить поток в kernelspace - написать модуль/драйвер ядра. Обычные программы так не могут.

Финальный вопрос. Правильно понимаете. Вот только "пошаговая стратегия" - это про многозадачность, а не про параллелизм. Процессор с одним ядром многозадачным быть может. Параллельным - нет.

Comments

[Sazoks]

Это самый лучший ответ, спасибо большое, что так подробно разжевали все) После просмотра небольшого курса по архитектуре ОС Ваш ответ еще больше мне раскрыл глаза, как все устроено на самом деле.

[Sazoks]

А подскажите пожалуйста насчет userspace-потоков. Я в одной статье читал, что иногда таким потокам может сопоставляться kernelspace-поток. И также в той статье было сказано, что (здесь могу неточно выразиться) userspace-потоки не могут выполняться на разных ядрах, т.к. (вроде бы) у них нет контекста, а вот kernelspace-потоки - могут. Можете этот момент подробнее рассказать?

[Vamp]

Sazoks, можете дать ссылку на статью?

[Sazoks]

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


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

[Vamp]

Sazoks, под user-level тредом на этой картинке понимается инстанс класса threading.Thread (на примере библиотеки threading в Python), а под kernel-level понимается тред, которая создаёт сама операционная система (далее я буду такие треды называть "нативными").

Если питоновская библиотека threading на каждый инстанс класса threading.Thread создаёт нативный тред (вариант b на картинке), то здесь можно говорить о настоящей многопоточности и параллельном выполнении кода (так как ОС шедулит только свои нативные потоки на разные ядра процессора и знать не знает ни про какие threading.Thread объекты).

Но если на все инстансы threading.Thread имеется только один нативный тред (вариант а), то такая программа будет считаться однопоточной, так как в любой момент времени будет работать только один инстанс threading.Thread. Это как раз и есть грин треды. Для ОС существует только один тред, и пользовательский код, который в нём выполняется, уже сам решает в каком порядке и как долго будет выполняться код из всех имеющихся в программе объектов threading.Thread.

Я плохо знаю python, но насколько я понял, в нём нет настоящей многопоточности. То есть питоновские треды работают по модели грин тредов (вариант а с картинки).

На самом деле ваша картинка вносит путаницу, так как использует термин kernel space не совсем правильно. На картинке имеется ввиду, что процессы и kernel-level ("нативные" в моём описании) треды - это структуры, которые создаёт и которыми управляет сама ОС, а не то, что эти треды выполняются в привилегированном режиме, согласно упоминаемой мной кольцевой архитектуре безопасности.

[Sazoks]

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

При запуске .py-файла запускается однопоточный процесс, в котором запускается Сишная функция main, которая работает в 3 шага:

1. Инициализация интерпретатора
   
2. Компилирование Python-кода в платформонезависимый байт-код
   
3. Бесконечный цикл с гигантским switch'ем всех возможных байт-код инструкций
   

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

Эта проверка в потоках, которые как бы работают на процессоре, но Python не позволяет им заниматься обработкой Python-переменных, выполняется в том самом бесконечном цикле перед switch'ем. Конечно, потоки работают не всегда, т.к. пока работает основной поток, операционная система может второй поток уже усыпить и разбудить несколько раз. Однако если время пробуждения, установленное в интерпретаторе, еще не вышло, этот поток так и будет пытаться захватить GIL.

Еще раз большое Вам спасибо за столь подробный и терпеливый ответ)

P.S. Опять же, это связано именно с CPU-bound задачами. В I/O-bound задач Python-потоки реально могут работать параллельно, т.к. на блокирующих системных вызовах поток отпускает, а после выполнения операции снова захватывает GIL. То же самое и на тяжелых CPU-bound задач с помощью вызовов Си-функций. С этим я пока еще не разобрался.

[pindschik]

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