© Георгиевский Анатолий, 10.03.2006 - ...

Нитки и ветки

В статье приводится базовый набор понятий и описание основных способов взаимодейсвтия параллельных процессов.

Исполнение задач

Для выполнения задачи выделяется некоторый объем памяти сегментами с заранее предопределенным назначением. а) сегмент кода выделяется под загрузку кода программы. б) сегмент данных выделяется под данные. Память на уровне ядра операционной системы распределяется страницами, страницы памяти могут временно выгружаться в файл подкачки, чтобы освободить место для другой задачи.

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

Организация взаимодействия задач

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

Отсылка сообщений, очередь сообщений

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

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

В MPI, программном интерфейсе для обмена сообщениями между параллельными задачами, реализованы оба механизам: блокирующей и не блокирующей передачи данных, с ожиданием приема/передачи и без ожидания приема/приема передачи. Иногда называют такие процессы синхронными и асинхронными.

Чем нитки от процессов отличаются

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

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

Реализация совместного доступа с использованием блокировок

Условные блокирвки

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

Камыши, ветки растущие из водоемов

Есть такое понятие "ThreadPool", ветки растущие из лужи. Вводится оно, как раз для разрешения обратной проблемы, когда данные генерируются чаще, чем успевают обрабатываться. В этом случае надо либо накапливать данные, выстраивая их в очередь, либо запускать по треду на каждый элемент данных, который произвел первый процесс. Водоемом назовем такое специальное место, куда можно вываливать элементы данных подготовленные для обработки. Данные будут являться аргументом для функции обработки. Функции обработки запускаются с этими параметрами параллельно в том количестве, какое необходимо. Т.е. данные сваленные к кучу, в лужу, могут обрабатываться параллельно нескольким одинаковыми функциями-тредами с разными входными данными. В век параллельных систем это оказывается выгоднее, чем обрабатывать данные последовательно. Узким местом этой техники является накладные расходы на подготовку и запуск очередного треда-нитки-процесса. Именно этим качеством выделяется лужа с ветками, все необходимые ресурсы подготавливаются заранее, что делает эту технику выигрышной по сравнению с техникой отдельных тредов.

Это ещё что, бывают в природе ещё и тончайшие "волокна", fibers, из которых могут состоять "нити" процессов. Но большой разницы между нитями и волокнами мы не обнаружили, кроме того факта, что породившая их операционная система тратит меньше ресурсов на их обслуживание. Стало быть, волокна тоньше нитей.

Изменяемые данные

В языке Си есть специальное ключевое слово (volatile) для обозначения изменяемых данных, изменяемых извне программного кода. Признак volatile может быть приписан к любым данным, к целой структуре, к полю структуры или к отдельной переменной. Признак влияет на оптимизацию кода. Например, если вы в цикле производите сравнение переменной, ожидая пока где-то в другой ветке процесса произведут опреацию над этой переменой, то компилятор может понять по своему. Без признака "изменяемые данные" код преобразуется в следующую последовательность инструкций: до выполнения цикла содержимое ячейки памяти перекладывается в регистр, сравнение регистра с числом производится на каждом цикле. Содержимое регистра остается неизменным чтобы не делалось в других ветках программы. Компилятор прав, он оптимизирует код. Чтобы указать компилятору, что переменная может быть изменена где-то снаружи применятеся слово "volatile". В этом случае последовательность инструкций после компиляции кода будет содержать загрузку содержимого памяти в регистр непосредственно перед выполнением операции сравнения.

Атомарные операции

Не уверен что это устоявшийся термин, поэтому сначала дадим пример и определение атомарной операции. Пример. Пусть два процесса обращаются по адресу к одной и той же ячейке памяти, и выполняют некоторое действие, например, прибавляют единицу к содержимому. Каждый процесс выполняет три операции над данными в памяти. Загружает из памяти в регистр процессора, выполняет инструкцию, в нашем случае сложение, и, наконец, результат сохранятеся обратно по адресу. Может возникнуть ситуация, когда оба процесса последовательно прочитали содержимое памяти до изменения, оба выполнили операцию сложения, и по очереди сохранили содержимое обратно. Результат увеличится на единицу, а не на 2, поскольку, сложение выполнялось параллельно, а не последовательно. Такая ситуация может возникать как на многоядерных процессорах (параллельных архитекутрах), так и на однопотоковых. При исполнении программы на однопотоковой архитектуре, такая ситуация возникает, когда задачи переключаются в процессе выполнения операции, загрузка данных произведена до переключения задач, а сохранение результата после.

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

Атомарные операции могут применятся в ряде случаев в качестве альтернативы блокировкам доступа и не требуют поддержки со стороны операционной системы. Пример реализации атомарных операций можно найти в библиотеке glib. В библиотеке реализованы операции сравнения и сложения целых чисел и указателей. Эти операции ориенитированы на создание счетчиков, которые могут быть использованы в процессе взаимодействия программ с нитями (Thread). Например, счетчики на атомарных операций используеются для учета количества объектов созданных в "нитях" и для подсчета количества ссылок на объект. Так же могут использоваться для реализации флагов, при обмене сообщениями между задачами.

Совместное использование динамических данных

Начнем с примера, противного. Для программирования взаимодействия задач часто испоьзуют объекты сложной структуры. Например, это может быть фрагмент видео изображения, который должен быть распакован, обработан художественным образом, отрегулирован по насыщенности и выставлен вам в окно. Все эти действия выполняются совершенно разными программами, которые должны обмениваться блоками данных, создавая очереди и заторы, разрешая и запрещая совместное использование. Жизнь некоторого графического объекта зарождается в программе распаковки и заканчивается в программе отображения, по ходу дела создаются и удаляются ассоциированные с этим фрагментом контексты отображения и буферы обработки. Итого, для разрешения конфликтов совместного доступа вам прдется плодить взаимные и условные блокировки, чтобы сообщать другим процессам о готовности и выставлять признаки жизнедеятельности объекта. В частности, если в структуре объекта присутствуют ссылки на динамические данные, то для сохранения работоспособности системы в целом, приходится встраивать в код каждого процесса иерархические проверки целостности данных. Часто в таких случаях программа никогда не выходит в свет, а если выходит, содержит в себе 70-90% кода направленного на разрешение конфликтов и проверку целостности при создании и удалении объектов.

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

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

Объектная модель

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

Базовое понятие, которое надо переопределить - перемещаемый объект (portable). Всё равно, что вкладывается в понятие объект, для совместного использования наш_объект должен содержать индекс цитирования - счетчик процессов, которые его используют. Если на объект никто не ссылается, индекс цитирования - ноль - объект можно удалить, для него вызывается функция освобождения памяти. Для реализации этого условия каждому объекту приписывается счетчик ссылок, индекс цитирования, выполненый на атомарных операциях.

Для совместного использования объекта между разными процессами, наш_объект должен содержать дополнительное поле блокировки доступа. Блокировки используются в процессе чтения/изменения объекта.

Последовательное представление объекта (сериализация)

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

Разрешение символьных ссылок

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

Клубок ниток

Одно дело запустить процесс, совсем другое дело запустить пару сотен процессов. В моем понимании существует три уровня реализации: один процесс, два и "много". Хочется отдать задачу слежения за процессами какой-нибудь программке, менеджеру загрузки, и вообще забыть о параллельности.

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

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

Миграция процессов между вычислительными узлами

Есть способ современный, но не эффективный. Операционная система, в принципе, помечает память распределенную под задачу. Это свойство позволяет свернуть всю выделенную задаче память и отослать на другой компьютер. Существует открытая реализация, этого мехнизма - OpenMOSIX. MOSIX - это дополнение к ядру Linux, реализация миграции процессов на уровне ядра. Такой подход привлекателен тем, что не требуется переписыать программу. Однако, в нашем случае не работает, потому что нити процессов используют общий сегмент памяти программ и общий сегмент данных. Т.е. средствами операционной системы нельзя заплести одну нитку исполнения кода на другой компьютер.

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

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

Оптимизация загрузки вычислительных узлов кластера и миграция процессов - это тоже функция менеджера загрузки. Что же тогда остается разработчику? Увы, ничего. Опять не удалось идею кодом разбавить.

В следующий раз: Функциональное программирование..., Представление программ в виде графов...



GThreads - поддержка нитей процессов в библиотеке glib. В библиотеке также реализован механизм слежения за нитками в клубке.
PThreads - POSIX Thread.
GObject - объектная модель для использования в языке С.
Mutex - механизм блокировок реализованный в библиотеке glib.
MPI - интерфейс обмена сообщениями

( - )