Чтобы написать продолжение предыдущей статьи мне пришлось перечитать множество материалов, имеющих отношение к теме. Я так и не нашел пример хоть какой‑то практической задачи, определяющей хоть какие‑то детали, имеющие отношение к возможности распараллеливания. По большому счету все пишут о том, что распараллеливание улучшает производительность, и это в общем‑то все к чему нужно стремиться с невнятными оговорками о том, что при этом можно получить кучу проблем.
Но хуже того, что никто не рассматривает практических задач, для которых можно или нужно применять многопоточность, никто не вспоминает что многопоточность придумали в те времена, когда никто не рассчитывал на то, что процессоры могут быть многоядерными.
Мне кажется нельзя считать что вы до конца понимаете концепцию многопоточности (Multithreading/ Concurrency) если вы не понимаете когда (для каких задач) ее можно и/или нужно использовать на однопроцессорной машине, 2-х процессорной, N‑процессорной машине и от чего это зависит.
Начнем, пожалуй, с самой простой задачи с точки зрения распараллеливания. Задача достаточно абстрактная, но достатоно показательная и не совсем уж оторвана от реальности, на мой взгляд. Если кто‑то предложит для рассмотрения более подходящую задачу буду только рад ее обсудить или даже внимательно рассмотреть.
Пример с распаралеливанием практической задачи
Мне кажется для введения в анализ проблем связанных с производительностью многопоточных решений вполне подходит следующая задача. Допустим нам надо выполнить некоторый запрос к огромной базе данных, точнее нам надо выбрать записи из таблицы на миллион записей по какому‑то критерию (алгоритму), вполне логично предположить что мы можем распараллелить такую задачу просто запустив один поток по первой половине миллиона записей и второй поток по второй половине миллиона записей, а по завершению этих потоков нам надо будет смержить полученные в соответствии с критерием два списка и отправить суммарный список в ответ на запрос. Вполне рабочая стратегия ускорения выполнения запроса.
Посмотрим, как такой способ распараллеливания задачи отразится на ее производительности (на времени исполнения) на однопроцессорной машине:
На рисунке можно наглядно наблюдать что время выполнения такой задачи в единственном потоке будет меньше, чем время выполнения той же задачи, разделенной на два потока на однопроцессорной машине, просто потому что добавится время, когда система переключает потоки. Здесь я не стал рисовать период необходимый для создания и запуска потоков (пролог) и период для объединения данных из каждого завершенного потока для подготовки интегрального ответа на запрос (эпилог), очевидно это не улучшает результат. Полную схему с двумя потоками на многопроцессорной машине и коментарии к ней смотрите в конце статьи, я ее действительно написал после того как написал Выводы.
Но, конечно, при наличии хотя бы 2-х процессоров задача, реализованная на 2-х потоках, действительно ускоряется примерно в два раза если пренебречь длительностью необходимых пролога и эпилога.
Теоретически, проявляя фанатизм, мы могли бы создать поток для проверки каждой записи, то есть нам пришлось бы создать миллион потоков в надежде в миллион раз ускорить выполнение нашего запроса при наличии миллиона доступных ядер процессора. Ответ на вопрос нужно ли стремиться к такой глобально фанатичной многопоточности, я думаю, всем понятен, так делать не только не нужно, так делать нельзя, потому что такое бездумное расходование ресурсов системы с очень большой вероятностью приведет к коллапсу и краху любой системы!
Позволю себе остановиться только на одной проблеме распараллеливания такой задачи. Я подозреваю что для многих эта проблема может показаться неожиданной. Дело в том, что миллион записей из некоторой базы данных, конечно, будут храниться на каком‑то физическом носителе с каким‑то физическим интерфейсом доступа к данным (шиной данных) и даже если вы создадите всего сто потоков которые должны будут читать данные с разных позиций в памяти этого носителя эти 100 потоков выстроятся в очередь для доступа к этой внешней памяти, и вместо ускорения выполнения запроса мы получим его замедление, связанное с обслуживанием этой очереди, скорее всего, вполне возможно.
Историческая справка
Теперь давайте попробуем сопоставить факт снижения производительности многопоточного решения на однопроцессорной машине с тем фактом, что многопоточность была изобретена и стала применяться во времена, когда абсолютно все компьютеры (меня поправили, большинство компьютеров) были однопроцессорными. Сначала давайте убедимся, что это так.
Стандартный набор функций (и структур и всего что обычно пишут в заголовочных файлах языка С — в хидерах) впервые был зафиксирован в 1995 году в стандарте POSIX (хотя термин thread был определен, очевидно, раньше, но надо же на что-то ориентироваться):
https://en.wikipedia.org/wiki/Pthreads
In computing, POSIX Threads, commonly known as pthreads, is an execution model that exists independently from a programming language, as well as a parallel execution model. It allows a program to control multiple different flows of work that overlap in time. Each flow of work is referred to as a thread, and creation and control over these flows is achieved by making calls to the POSIX Threads API. POSIX Threads is an API defined by the Institute of Electrical and Electronics Engineers (IEEE) standard POSIX.1c, Threads extensions (IEEE Std 1003.1c-1995).
(Спасибо @lexa0 за комментарий с ключевыми словами, по ним я нашел "The History of the Development of Parallel Computing", но разбираться что там написано, честно говоря очень тяжело и поэтому не хочется, очень много очень низкоуровневой специфики, которая очень устарела, как мне кажется.)
Это значит, что к тому времени он, этот набор функций для работы с потоками, относительно широко применялся и, соответственно, был достаточно хорошо проработан чтобы выпустить стандарт. По результатам поисков в интернете у меня сложилось впечатление что концепция многопоточности появилась в 80-х годах.
По поводу многоядерных процессоров Гугл говорит, что первый такой процессор был спроектирован в 1998 году, а на рынок IBM впервые представила экземпляр в 2001 году:
Kunle Olukotun, a Stanford Electrical Engineering professor, and his students designed the first multi‑core chip in 1998.In 2001, IBM introduced the world's first multicore processor, a VLSI (very‑large‑scale integration) chip with two 64-bit microprocessors comprising more than 170 million transistors.
Первые двухпроцессорные материнские платы появились в 1999 году, тогда они реально были двухпроцессорные — в виде двух физических камней на материнской плате, хотя такая конструкция наверно и сейчас никуда не делась, где‑то применяется.
И я сам помню, что мы в Интеле уже работали на двух процессорных пентиумах не позднее 2002 года. Но большинство персональных компьютеров в те годы были однопроцессорными и одноядерными. И многопоточные приложения тоже замечательно работали на этих однопроцессорных ПК и под Linux, и под Windows (замечательно работали у тех, по крайней мере, у кого получалось их правильно написать).
Анализ определений
Но что же побудило программистов однопроцессорных компьютеров разработать и начать применять многопоточность в своих программах, если эта концепция в действительности замедляет работу на таком оборудовании? (Мне напоминает вступление для описания результатов исследования пирамид в Египте:)
В интернете можно найти, например, вот такое определение слова multiprogramming, которое не переводится односложно на русский язык, но которое поможет нам ответить на наш вопрос:
Multiprogramming: In the early days, it was seen that at times certain processes where using peripherals (e.g.: I/O). In such cases, the CPU remained idle. To use the CPU more efficiently, it was prudent to load multiple processes in the memory. This way, if a certain process were to use the peripheral, certain other process would use the CPU. This was multiprogramming in action.
Тут определяется‑формулируется понимание термина как возможность дать другой программе исполняться, пока текущая программа находится в ожидании ответа от периферийных устройств (клавиатура, принтер, последовательный порт, контроллер шины, контроллер жесткого‑гибкого диска, контроллер дисплея‑видеокарта, …). Таким образом, пока некоторые процессы используют периферию, другие процессы могли бы использовать CPU, формулирует автор определения.
Это одна из очевидных причин, которая побудила софтваре‑инженеров изобрести концепцию multiprogramming‑а или многозадачности, которые в итоге были оформлены как концепция многопоточности, насколько я понимаю.
Вторая причина очевидно связана с первой или даже является как бы обратной стороной медали. Когда за компьютером (за терминалом к компьютеру) сидит человек, он ожидает увидеть какой-то отклик от работающей программы и хочет иметь возможность какого-то текущего управления процессом (хотя бы возможность остановки вычислений) и это опять же упирается в параллельное выполнение основной задачи программы и периодические уведомления пользователю о прогрессе выполнения, опрос устройств ввода данных. Все это осуществляется через те же устройства периферии.
Multithreading, Threads, Concurrency ...
Но давайте рассмотрим еще хотя бы пару определений, чтобы получить более общую картину:
https://www.geeksforgeeks.org/multithreading-in-cpp/
"Multithreading is a feature that allows concurrent execution of two or more parts of a program for maximum utilization of the CPU. Each part of such a program is called a thread. So, threads are lightweight processes within a process.
Multithreading support was introduced in C++11. Prior to C++11, we had to use POSIX threads or <pthreads> library. While this library did the job the lack of any standard language-provided feature set caused serious portability issues. C++ 11 did away with all that and gave us std::thread. The thread classes and related functions are defined in the <thread> header file."
developer apple documentation:
"Threads are one of several technologies that make it possible to execute multiple code paths concurrently inside a single application. Although newer technologies such as operation objects and Grand Central Dispatch (GCD) provide a more modern and efficient infrastructure for implementing concurrency"
В этих определениях нет никаких подробностей кроме того, что они определяют потоки (Threads) или многопоточность (Multithreading) как возможность или набор функций, которые позволяют выполнять несколько частей программы (parts of a program) или несколько веток кода (code paths) одновременно (concurrently).
Разобрать понятие одновременности нам поможет всем известный практический пример. Этот пример у всех перед глазами, это визуализация движения курсора мыши на экране вслед за движением мышью.
Так или иначе многопоточность определяется через «одновременность исполнения» (concurrent execution), но если начать разбираться, то мы выясним, что события или процессы, которые кажутся одновременными человеку, для периферийных устройств компьютера являются последовательным набором абсолютно разделенных по времени событий. Возьмем для примера визуализацию движения курсора мыши на экране в след за движением материальной мышью, что здесь происходит на уровне железа:
срабатывание датчика, отправка пакета с параметрами, прием пакета, расчет новой позиции курсора, последовательность операций связанных с отрисовкой курсора на новом месте.
Таким образом оказывается, что на уровне взаимодействия единиц оборудования понятие «одновременно» перестает существовать и переходит в четкую и однозначную последовательность действий по отношению к управляемым устройствам, в нашем случае это мышь и экран (а между ними и процессором видеокарта, USB контроллер приемника, передатчика, или какой то контроллер последовательного порта ввода‑вывода, PCI шина данных со своими контроллерами, провода, сигналы, фронты, и бог знает что еще, но это уже совсем другая история из другого мира).
Таким образом, получается, что многопоточность – это способ создания иллюзии одновременности для человека, но если мы занимаемся созданием этой иллюзии, ее техническим оформлением, так сказать, мы должны понимать что действие в физическом мире, такое как движение мышью, и его результат в виде перемещения курсора на экране разделены последовательностью невидимых, а главное, настолько коротких операций, что человек не в состоянии их разделить во времени, опираясь на свои, так сказать, штатные органы чувств. Единственное, что может быть доступно человеку – это разобрать записи, которые делает аппаратура, которая предназначена чтобы фиксировать информацию об этих операциях. Только таким образом мы способны заглянуть из нашего неторопливого человеческого мира в мир сверхскоростей взаимодействия аппаратуры, где происходят миллионы и миллиарды событий за секунду, тогда как наше восприятие ограничено максимум 10 (десятью!) последовательными событиями в секунду.
Иллюзия одновременности или параллельности исполнения двух (нескольких) потоков операций может создаваться за счет последовательного поочередного исполнения операций из этих потоков по кругу. И если мы будем наблюдать за результатами исполнения с периодом намного большим, чем частота чередования, мы каждый раз будем наблюдать что все потоки продвинулись в своем исполнении. При таком способе наблюдения-исполнения невозможно отличить последовательное поочередное исполнение от действительно параллельного. Именно таким образом это работает на однопроцессорной машине или там где процессоров не хватает на все исполняющиеся одновременно потоки операций, а их в общем-то никогда не хватает. Я где то читал Notepad при запуске создает больше 25 потоков, конечно они не все активные, но число впечатляет, не правда ли?
На этом уровне понимания организации работы аппаратуры появляется понятие дискретность или «разрешение по времени», которое я сформулировал в конце своей самой первой статьи на Хабре про операционные системы (включая Windows), и их отношение к понятию «Реального Времени». Тем, кому интересны все аспекты, хоть как‑то связанные с многопоточностью, возможно будет любопытно узнать и то, что там написано, по крайней мере я на это надеюсь.
Выводы
Все что я тут написал, должно подвести читателя к мысли о том, что многопоточность, в первую очередь, предназначена для работы с аппаратными функциями внутреннего компьютерного оборудования и со всем чем компьютер обвешан, а не для того, чтобы что‑то ускорить. То есть ускорение тоже вполне можно считать целью, только приоритет этой цели намного ниже, чем приоритет того, что, например вы можете редактировать текстовый файл, пока происходит копирование‑закачка какого‑то другого файла.
Если бы не было многопоточности, подавляющее большинство привычных функций на компьютере просто не могли бы работать или работали бы невыносимо сложно! Насколько корректно сравнивать наличие огромного списка возможностей и того, что некоторые возможности могут быть несколько улучшены в плане скорости их выполнения? Очевидно, что наличие этих разнообразных возможностей многократно важнее, чем локальные улучшения производительности пусть и множества программ, хотя никто не запрещает заниматься и производительностью тоже.
Также не стоит забывать, что многопоточность гораздо важнее для низкоуровневого программирования, то есть там, где и сосредоточена основная работа с периферией, с аппаратными устройствами. В области применения высокоуровневых языков мы всегда будем ограничены в использовании многопоточности из‑за того, что тут никогда не существует полноценного доступа к аппаратным функциям, которые в первую очередь нуждаются в применении возможностей, предоставленных концепцией многопоточности. Высокоуровневые языки всегда будут довольствоваться интерфейсами, предоставленными им с некоторого аппаратно‑зависимого уровня, и всегда будут зависеть от эффективности библиотек, которые они используют для утилизации многопоточности в комбинации с реализацией абстракций аппаратных функций.
Но на любом уровне программирования и в любом случае полезно знать как можно больше о концепции многопоточности, если вы хотите чего-то добиться в прикладном программировании.
Полная схема с двумя потоками на многопроцессорной машине
Давайте все-таки попробуем нарисовать полную схему взаимодействия потоков, на многоядерной машине, исходя из того, что каждому потоку может быть выделен отдельный физический процессор для исполнения, то есть попробуем рассмотреть, что получается, когда потоки действительно выполняются параллельно‑одновременно. Это в каком-то смысле второй предельный случай, а ситуацию на однопроцессорной машине можно рассматривать как первый предельный случай для любого проектируемого взаимодействия потоков, которые в первую очередь надо анализировать, обычно.
Только я еще более усложнил возможную схему исполнения потоков (хотя все еще недостаточно — см. замечание в самом конце), обратите внимание: 1-й поток все‑таки прерывается системой, которая приостанавливает поток для какой‑то своей неотложной работы. Мы ведь не знаем, сколько еще потоков обслуживает система, таким образом мы имитируем ситуацию, когда ядер‑процессоров в какой‑то момент все‑таки не хватает для всех потоков в системе, включая те потоки, про которые мы знаем, и работу которых мы проектируем.
Я думаю, схема наглядно демонстрирует проблему сложности программирования многопоточных программ. Кстати, можно сравнить со схемами, которые можно найти в еще одной моей статье. Мне кажется можно найти некоторую аналогию особенно, если представить себе горизонтальное расположение линий исполнения.
Что‑то подобное должно быть у вас в голове, а лучше на бумаге, когда вы анализируете, проектируете работу с многопоточностью. Мы, вообще говоря, должны продумать все варианты завершения потоков в данном случае. Я намеренно добавил задержку от системы в 1-м потоке чтобы, в том числе продемонстрировать, что порядок завершения является случайным. Вы не должны рассчитывать что поток который запущен первым также и закончится первым. Более того, даже если у вас есть какие‑то данные о том, что алгоритм в одном из потоков легче и должен быстрее закончиться, вы не можете основать логику обработки завершения потоков на таких данных.
Если вам надо, чтобы один поток не завершился, пока не завершится какой‑то другой поток, вам надо будет передать дескриптор (ссылку) на ожидаемый поток и в коде зависимого потока явно прописать это ожидание в какой‑то действующей функции. Собственно, это здесь и должно происходить в функции main потока. Здесь main поток запускает два потока и должен запомнить их, например в массиве. Он должен заблокироваться, то есть вызвать системную функцию, которая исключает его выполнение до тех пор, пока любой из потоков не закончится. Система проверяет кто ждет окончания закончившегося потока и возвращает управление «подписанному на это событие» потоку — main потоку. (это то, что было определено еще POSIX стандартом, это из области фундаментальных основ потоковой концепции, и вряд ли поменяется вплоть до создания квантовых компьютеров). Далее main поток должен дождаться обоих событий окончания созданных им потоков и потом объединить результаты.
Эта схема не оптимальна в том смысле что у нас main поток не используется для реальной работы, а просто ждет завершения созданных им потоков. Это можно исправить и решение будет не только компактнее с точки зрения визуализации схемы, но и с точки зрения однородности кода, так как все объекты‑задачи будут делить одну и ту же функцию завершения, а объект потока можно передать при создании такому объекту‑задаче, либо сказать, что надо выполняться в текущем потоке, но это упражнение могло бы быть темой или частью какой‑то новой статьи, мне кажется. И там еще надо рассмотреть наложение обработки второго завершения потока на обработку завершения первого потока, там придется применить какой‑то объект синхронизации (мутекс, семафор, критическая секция, <?>), но...
Но позвольте мне на этом прервать мое повествование, так как я чувствую, что вдохновение покидает меня. Очень не хватает вовлеченности и заинтересованности аудитории.
