В Части I этой серии мы познакомились с основами параллельного аппаратного и программного обеспечения на самом базовом уровне. В нем говорилось о том, как параллельное программирование связано с одновременным выполнением нескольких вычислений и как это обеспечивается параллельным оборудованием. В этом посте, основанном на этих концепциях, говорится о наиболее распространенных парадигмах многоядерного программирования - многопроцессорность и многопоточность. Для этого мы представим процессы и потоки в контексте операционной системы (ОС) через низкоуровневые системные вызовы, а также рассмотрим некоторые из их недостатков.

Важно отметить, что этот пост посвящен использованию всех ядер компьютера, а не другим вариантам использования параллельного программирования. Таким образом, термин параллелизм следует понимать в контексте истинного параллелизма в многоядерных процессорах.

1. Модель программирования для Linux.

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

GNU / Linux - это Unix-подобная ОС с открытым исходным кодом, которая сегодня очень популярна. Название Linux фактически относится только к этому ядру, в то время как система GNU предоставляет все другие важные строительные блоки полнофункционального дистрибутива Linux. Отсюда и название GNU / Linux. Он работает везде, от самых больших серверов до мельчайших встраиваемых устройств.

Учитывая эти факты и наш собственный опыт, мы решили использовать программный интерфейс Linux для изучения этих идей. При этом детали должны быть почти одинаковыми для macOS (которая также является вариантом для Unix), и Windows также должна иметь эквиваленты.

Пространство ядра и пространство пользователя

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

В пользовательском режиме ЦП может обращаться к памяти только в пользовательском пространстве, в то время как в режиме ядра он может обращаться к обоим пространствам памяти. Ограничение программ пользовательского режима предотвращает их изменение и возможное повреждение критически важных данных и процедур ОС и, таким образом, предотвращает катастрофические сбои. Процессор переключается между двумя режимами с помощью аппаратных инструкций в зависимости от того, какой тип кода выполняется. На схеме ниже показаны два режима.

Стандартная библиотека

Поскольку только код пространства ядра имеет прямой доступ к базовому оборудованию, а код пользовательского пространства - нет, ядро ​​делает ряд служб доступными для пользователя через контролируемые точки входа, называемые s вызовами системы . Они берут начало в пространстве пользователя и заканчиваются в пространстве ядра. В Linux системные вызовы в основном выполняются C API с использованием libc или glibc библиотеки. Это также известно как стандартная библиотека. Не все стандартные библиотечные функции выполняют системный вызов.

2. Основы многопроцессорности

процесс - это, по сути, запущенный экземпляр программы. Когда программа выполняется, ядро ​​загружает код программы в виртуальную память, выделяет место для переменных программы и настраивает структуры данных для записи различной информации о программе. Итак, с точки зрения ядра, процессы - это фундаментальные сущности, которым оно распределяет системные ресурсы. Linux использует то, что называется упреждающей многозадачностью. В этой системе правила, определяющие, какие процессы используют какое ядро ​​ЦП и как долго, определяются планировщиком процессов ядра, а не позволяют процессам запускаться и останавливаться самостоятельно.

Когда ОС выделяет свои ресурсы, каждый из процессов изолирован друг от друга и от ядра. Таким образом, один процесс не может читать или изменять память другого процесса или ядра. Они могут даже находиться в разных ядрах ЦП, при этом работать одновременно. Однако некоторым процессам необходимо будет взаимодействовать друг с другом, используя некоторые средства связи друг с другом и синхронизации своих действий. Для этого Linux предоставляет богатый набор механизмов для межпроцессного взаимодействия (IPC) через сигналы, сокеты, каналы, семафоры и т. Д. Давайте посмотрим, как это работает.

IPC Linux через именованные каналы

Теперь мы кратко рассмотрим простой пример использования IPC в Linux с использованием безымянных каналов. Это самый старый механизм IPC, доступный в семействе Unix, который широко используется даже сегодня.

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

$ ls | wc -l

Эта команда вычисляет количество файлов в каталоге. Это происходит путем добавления «|» (вертикальная черта) после ls,, чтобы список файлов из его вывода использовался в качестве входных данных для команды wc.

Чтобы выполнить указанную выше команду, оболочка создает два процесса, выполняя ls и wc соответственно. Механизм того, как это работает, можно увидеть на рисунке ниже.

Мы можем имитировать эту команду, используя стандартные библиотечные функции pipe () и fork () в glibc. Обе эти функции доступны в заголовке unistd.h, который мы включаем в начало программы.

Родительский процесс (программа) создает несколько дочерних процессов для каждого из аргументов командной строки ls и wc. Системный вызов fork () используется для создания новых процессов. Чтобы поддерживать синхронизацию процессов, родительский процесс создает конвейер с помощью функции pipe () перед созданием дочерних процессов.

Каждый дочерний элемент наследует файловый дескриптор pipeFDs для чтения и записи канала и закрывает этот дескриптор после завершения своего действия. Родитель ждет, пока все дочерние элементы завершат свои действия.

С точки зрения обработки данных это было бы полезно, когда мы хотим создать конвейеры данных. В цепочке данных задачи обычно выполняются таким образом, что выходные данные одного этапа используются как входные данные другого. Также будут задачи, которые можно запускать параллельно, для которых мы можем создать множество дочерних процессов для этих задач без необходимости использования IPC между ними.

3. Основы многопоточности

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

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

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

Кодирование с помощью pthreads

С точки зрения реализации потоки создаются с использованием POSIX-совместимой библиотеки pthread в Linux. В Linux нет реальной концепции потока в пространстве ядра. Это строго конструкция пользовательского пространства. Внутренне функция clone () используется для создания как обычных, так и легких процессов. Это означает, что для создания обычного процесса используется функция fork (). Далее он вызовет функцию clone () с соответствующими флагами для выполнения фактического создания. Чтобы создать поток или облегченный процесс, функция из библиотеки pthread вызывает clone () с соответствующими флагами. Итак, основное различие возникает за счет использования разных флагов, которые можно передать в функцию clone ().

Давайте посмотрим на простой пример, в котором мы используем потоки для вычисления значения π. Хотя этот конкретный метод не является самым эффективным способом вычисления π, он неплохо подходит для демонстрации распараллеливания с помощью pthreads.

Основная идея для этого проистекает из тригонометрической формулы 1 = tan π / 4, из которой мы можем получить π = 4.arctan (1)

Ряд Маклорена для arctan (x) вычисляется по формуле:

Что затем можно использовать для вычисления приблизительного значения π как:

Слагаемые в суммировании не зависят друг от друга, их можно разделить на блоки равного размера для каждого из потоков. Каждый их поток вычисляет частичные суммы и складывает их в общую глобальную переменную sum. Приведенный ниже код предоставляет один из способов сделать это с помощью pthreads. Пока не обращайте внимания на строки с мьютексами. Они будут объяснены в следующем разделе. Также не забудьте скомпилировать этот код с помощью -lpthread,, который сообщает компилятору, что мы хотим связать библиотеку pthreads.

pthread.h предоставляет нам различные функции и переменные для использования функций pthread. Программа принимает количество потоков и количество терминов n для ряда в качестве аргументов от пользователя. Переменная sum объявляется как глобальная переменная, а затем создается один pthread_ t объект для каждого потока.

Затем функция pthread_create () запускает каждый из потоков, используя указатель на объект pthread_t и функцию PI_calc (). , что поток должен запускаться в качестве аргументов. Где запускаются эти потоки, определяется ОС в зависимости от доступности ядер в машине во время работы программы. Каждый из потоков независимо обновит глобальную переменную sum, чтобы получить общую сумму. Функция pthread_join () используется потоком main () для ожидания завершения других объектов pthread_t.

Когда мы запускали эту программу на ноутбуке MacBook Pro с 4 ядрами, используя n = 10⁸ и 2, 4, 8 и 16 потоков, мы получили ускорение в 1,9, 3,6, 5,1 и 4,9 раза соответственно по сравнению с последовательной версией. Уменьшение ускорения после 16 потоков может быть связано с тем, что накладные расходы на создание и обработку новых потоков перевешивают преимущество параллельного выполнения частичных сумм.

Безопасность потоков и блокировки

Мы увидели мощь, которую дают нам потоки, позволяя выполнять множество вычислений одновременно. Но поскольку пользователь отвечает за доступ к общей памяти для различных потоков, это может привести к проблемам, когда несколько потоков одновременно пытаются читать или писать из общей глобальной переменной. Это создает непредсказуемые результаты, которые могут дать нам неверный результат. Это называется состоянием гонки. Чаще всего состояние гонки - это критический раздел - блок кода, который может выполняться только одним потоком за раз.

Чтобы получить правильный результат, нам нужно убедиться, что, как только один из потоков начинает выполнение оператора, он заканчивает выполнение оператора до того, как другой поток начнет его выполнение. Функция или переменная считаются потокобезопасными только в том случае, если они могут быть безопасно вызваны несколькими потоками одновременно.

Есть несколько способов сделать функцию поточно-ориентированной. Один из способов - связать блокировку взаимного исключения или мьютекс с функцией или глобальной переменной. Что это значит, так это ограничить или заблокировать доступ к переменной для одного потока. Таким образом, мьютекс может использоваться, чтобы гарантировать, что один поток «исключает» все другие потоки, когда он обращается к глобальной переменной. Говорят, что потоки синхронизированы, что фактически делает эту часть кода последовательной.

Мьютекс - это именно то, что является кодом в нашем примере кода выше. Мы определяем, что критическая часть кода должна находиться в функции PI_calc (). В частности, строка, которая добавляет значение локальной суммы каждого потока my_sum к общей глобальной переменной sum. Мы получаем и освобождаем мьютекс только во время выполнения этой конкретной строки.

Теперь, когда мы успешно рассмотрели, как программируются потоки и процессы на уровне ОС, это должно быть хорошей отправной точкой для понимания того, как они работают. Однако ручное управление ими, как это в C, может быстро стать громоздким в более крупных проектах. Даже при осторожном применении блокировок мы все равно можем столкнуться с проблемами типа тупиковых ситуаций. Существуют и другие API C / C ++, такие как OpenMP и OpenMPI, которые обеспечивают абстракции более высокого уровня для разделяемой памяти и передачи сообщений соответственно. Всем, кому нужно использовать низкоуровневые потоки и процессы в нетривиальных случаях использования, рекомендуется изучить эти две библиотеки.

В следующей части мы рассмотрим модель параллелизма в таких языках, как Java, Python и Go. Они предоставляют типы данных и конструкции высокого уровня, которые упрощают работу с потоками и процессами, но делают это принципиально разными способами.

Спасибо за чтение.