Программирование с интенсивным использованием параллелизма в последние годы набирает популярность. Можно назвать две веские причины этой популярности. Первая - широкое распространение многоядерных процессоров, возможности которых неплохо бы использовать эффективно. Второе - столь же широкое распространение разных распределённых сетевых приложений и служб, скорость коммуникации между частями которых сильно отстаёт даже от дисковых операций, что неизбежно вызывает сильное торможение параллельных программ.
Всё нижеизложенное написано по личному опыту как итог наблюдений и анализа творящегося в программировании, а также личных экспериментов и отбора эффективных практик программирования. Написанное относится к локальному масштабу программ, т. е. сферы так называемых «больших данных» (big data) и кластерных решений мы тут касаться не будем.
Можно сказать, что в отрасли наметился консенсус по техническим средствам реализации интенсивного параллелизма. Ключевым элементом является такой системный и методологический объект, как работа (job) или задача (task). С системной точки зрения понятие отнюдь не новое, корнями уходящее в многопользовательские операционные системы мейнфреймов 70-х. В нынешних условиях, однако, оно имеет специфические отличия от более традиционных, присущих операционным системам понятий процесса (process) и нити (thread). С методологической точки зрения понятие совершенно новое, опыта и надёжных практик использования которого пока ещё весьма мало.
В начале небольшая вводная справка о разных традиционных объектах параллельных систем. Процесс обычно связан с некоторой конкретной программой, которая внутри него исполняется, процесс существует, пока эта программа работает. Процесс обладает независимым виртуальным адресным пространством, поэтому разные процессы внутри операционной системы изолированы друг от друга. В частности это означает, что одна и та же программа может существовать в системе в нескольких независимо работающих экземплярах - в разных процессах. Нить обладает независимым стеком вызовов процедур, соответствующей стековой памяти и адресом текущей выполняемой инструкции. Но нить не имеет собственной изолированной виртуальной памяти. Поэтому нити могут существовать лишь внутри процессов, а любой процесс имеет хотя бы одну (главную) нить. Так же, как и процесс, нить привязана к исполнению конкретного кода - процедуры внутри программы. Главная нить процесса выполняет основную программу (например, функцию main). Кроме того, в ряде случаев нить бывает привязана к ядру процессора. Операционная система осуществляет диспетчеризацию нитей, распределяя их по ядрам процессора, а также управляя их состоянием (работает, спит). Понятие задача раньше часто употреблялось как синоним процесса. Понятие работы больше относилось к скриптам операционной системы, содержащим макросы автоматизации действий пользователя. В каком-то смысле работа является синонимом административной процедуры, которая может быть запущена пользователем, по некоторому событию или расписанию. Работа может исполняться в собственном процессе, а может в порядке очереди быть выполненной каким-то служебным процессом наряду с прочими работами. Часто работой называется некая фоновая разовая конечная деятельность, не предполагающая никакого диалога с пользователем. В отличие от столь же фоновой, но не разовой, а постоянной рутинной деятельности, которой занимаются особые процессы - службы или, что то же самое, демоны.
Новое понятие, о котором мы будем говорить, ещё достаточно свежо, чтобы получить устоявшееся название и, к сожалению, пока заимствует слова, употребление которых может вызвать путаницу. Мы здесь будем его называть задачей (task). Каковы же свойства задачи, и чем она отличается от вышеперечисленных объектов?
Во-первых, задача - это конечный или условно бесконечный (но, разумеется, когда-нибудь прерываемый) последовательный вычислительный процесс. Он может быть реализован в императивном стиле как алгоритм и оформлен в виде процедуры (могущей вызывать другие процедуры и функции). Он может быть реализован в функциональном стиле как некая структура из композиции функций, их аргументов, подвергаемая редукции. Задача не имеет собственного адресного пространства или стека. Задача - это не столько системный объект, сколько способ структуризации программы. В этом задача родственна вышеупомянутой работе. Внутри задачи нет никакого параллелизма. Задача внутри себя программируется традиционным последовательным образом. Это позволяет программисту снять неопределённость относительно содержания локальных для задачи переменных и сделать предположения (assertions) внутри алгоритма надёжными. Таким образом, если посмотреть на высокопараллельную вычислительную систему, на протекающие внутри неё вычислительные процессы, мы можем сказать, что задачи - это атомарные единицы параллельной декомпозиции кода. Каждая задача представляет собой (обычно короткую) последовательную подпрограмму. Это свойство в точности соответствует понятию задачи (task) в таком первом серьёзном языке параллельного программирования, как Ada.
Во-вторых, задача - это деятельность, бывает что останавливаемая ситуациями ожидания. Для своего исполнения между началом и концом, или между двумя ситуациями ожидания задача нуждается в вычислительном ресурсе. Такой вычислительный ресурс обычно предоставляется системным пулом нитей с общим диспетчером. Разные этапы активности задачи технически могут исполняться в разных нитях и на разных ядрах процессора. Т.е. задача не является синонимом нити, не является она и синонимом главной процедуры нити. Можно сказать, что каждая системная нить диспетчера задач, привязанная к отдельному ядру процессора, работает с задачами в режиме мультиплексирования: берёт из очереди готовые к исполнению и откладывает попавшие в ситуацию ожидания. Этим задачи напоминают не упоминавшиеся выше волокна (fiber) или зелёные нити (green thread) - объекты кооперативной многозадачности, самостоятельно определяющие момент перехода от работы к ожиданию и освобождение вычислительного ресурса в момент системного запроса или посредством оператора yield. Благодаря описанным свойствам множество задач внутри программы позволяет равномерно нагружать все имеющиеся ядра процессора и более эффективно утилизировать имеющиеся аппаратные вычислительные мощности.
В-третьих, задача может запускаться много раз. Каждый такой запуск, и весь временной континуум вычислительного процесса являются отдельным самостоятельным экземпляром задачи. Экземпляры задачи могут существовать в физическом времени как последовательно, так и одновременно. Это свойство роднит задачу с выше упоминавшимися процессами и работами. Отсутствие жёстко связанных с задачей системных ресурсов позволяет делать процесс запуска задач быстрым и лёгким, а количество экземпляров задач может быть чрезвычайно большим, намного превышая возможное количество процессов и нитей операционной системы. Кроме того, лёгкость задач делает процесс их диспетчеризации более эффективным, чем диспетчеризация нитей в операционной системе. Всё это открывает для программиста возможность использовать новый стиль структуризации кода, который был бы неэффективным по производительности для тех же нитей.
Языки и среды программирования начинают предлагать разработчику встроенные средства (разной степени удобности) для реализации задач в коде программы. Первым ключевым элементом, резко повышающим удобство программирования, являются лямбда-функции. Это даёт возможность в общем-то любой кусок последовательного кода в любом месте выделить в отдельную процедуру и запустить как задачу, параллельную всему прочему коду. Вторым элементом является конструкция запуска задачи. Язык Go предоставляет встроенный одноимённый оператор go, применяемый к функции. .NET Framework последних версий содержит специальный класс System.Threading.Tasks.Task, реализующий средства запуска и синхронизации задач.
Немаловажным свойством параллельных систем является сочетаемость вышеописанной декомпозиции кода на задачи с точки зрения параллелизма с другими формами декомпозиции:
- по процедурам/функциям и замыканиям локальных переменных с точки зрения структурного программирования,
- по объектам, их полям и методам с точки зрения объектно-ориентированного программирования,
- по местам подключения и отключения обработчиков и принадлежности их исполняемых экземпляров в событийно-управляемом программировании, а также в механизмах обработки сигналов и исключительных ситуаций.
Касательно последнего правилом хорошего тона стала трансляция необработанных исключительных ситуаций из задач, где эти ситуации возникли, в зависимые задачи, ожидающие событий от сбойного кода. В случае с нитями необработанные исключительные ситуации ведут лишь к аварийной ликвидации нити. И если это не последняя нить процесса, процесс продолжит работу, и никакой код не получит уведомления о произошедшем сбое. Благодаря механизму трансляции исключение теперь считается одним из видов события, передаваемым между задачами наравне с иными событиями синхронизации. Информация о сбое не распространится лишь из тех задач, событий от которых никакие другие задачи не ожидают.
Касательно сочетания с другими аспектами декомпозиции, можно отметить общий с нитями и процессами способ синхронизации задач через соответствующие объекты синхронизации. Лишь в языке Go предпринята попытка ввести единый универсальный объект для синхронизации и асинхронного обмена данными между задачами — канал (channel). В отличие от процессов и нитей задачи обычно не имеют средств внешнего управления: операций снятия (kill), приостановки (suspend) и возобновления (resume), управления приоритетами (nice) и т. п. Объясняется это всё тем же отсутствием у задач собственных выделенных ресурсов, таких как изолированная память и стек вызовов. В итоге все заботы о правильном программировании и управлении работой задач возлагаются на программиста, его добросовестность и опыт проектирования параллельных систем.
На данный момент, за исключением некоторых хотя и основательных, но малоизвестных широкой публике и отчасти устаревших книг по использованию языка Ada, а также обширной литературы по традиционным средствам синхронизации процессов в операционных системах, какой-то уважаемой общеизвестной методологии параллельного программирования на задачах не наблюдается. Как говорится, дело новое и неосвоенное. Можно предположить, что наработки в области методологии имеются внутри корпораций, поскольку и в Microsoft .NET Framework есть масса продуманных вспомогательных классов для различного рода «продолженных» вычислений, и в Google Go каналы появились явно не на ровном месте, а как итог экспериментов с распределёнными операционными системами Plan 9 и Inferno, архитектурно восходящими к UNIX с её процессами и каналами (pipe). Всё это подталкивает разработчиков к определённому стилю программирования, но, увы не даёт им внятной методологии для написания качественного код.
Опыт, сын ошибок трудных, говорит мне, что оператора go с каналами или класса Task как технических средств для качественного параллельного программирования недостаточно. Нужны дополнительные организационные и дисциплинарные меры, позволяющие подвергать решение систематической декомпозиции, причём по всем вышеперечисленным аспектам в комплексе. Если этого не делать, довольно быстро разработчик сталкивается с катастрофическим ростом сложности кода, обусловленным комбинаторным взрывом сочетаний состояний разных объектов, обрабатываемых разными параллельными задачами. Итогом является непременное упущение каких-нибудь частных случаев, приводящее к массе неприятных плавающих багов и в общем-то коллапсу всего проекта разработки, когда достижение определённого качества продукта становится попросту невозможным. Ниже как раз изложены выработанные мною принципы, благодаря следованию которым систематическое управление сложностью и качеством в параллельном программировании становится возможным. Общая стратегия управления сложностью всё та же: «разделяй и властвуй», т. е. это приципы декомпозиции решения на составные части с ясными границами.
Принцип 1. Задача как самостоятельный атомарный объект в параллельной вселенной должна быть организована подобно отдельному компьютеру или процессу UNIX. Это означает, что задача должна иметь ассоциированные с ней области памяти - контекст. Контекст включает в себя следующие разделы:
- собственная (local) память для локальных переменных задачи;
- разделяемая (shared) память (множество переменных) для взаимодействия с другими задачами;
- возможно, общая для всех задач память констант (constant) для чтения каких-то глобальных константных значений.
Применительно к процессу UNIX: собственная память - это адресное пространство процесса, разделяемая память - отображение в собственную память системной страницы, доступной нескольким процессам, общая для всех экземпляров программы память, как правило, содержит машинный код процесса и динамически загружаемых библиотек. Применительно к компьютеру: собственная память — оперативная, разделяемая память - область портов ввода-вывода и прочие каналы взаимодействия с периферийными устройствами, общая память - прошивка разной степени подробности (от BIOS до целой операционной системы).
Принцип 2. Собственная память задачи отличается тем свойством, что значения переменных в ней целиком и полностью зависят от действий самой задачи и только от них. Это позволяет писать и отлаживать код задачи по общим правилам написания и отладки алгоритмов. В частности, формулировать пред- и постусловия, инварианты циклов, фиксировать в коде контрольные assert-утверждения. Содержание собственной памяти может рассматриваться как состояние задачи. Будучи внутренне последовательной с сохраняемым состоянием задача как временной континуум эволюционирует в собственном локальном времени. Все события внутри неё происходят в подходящие моменты, когда задача сама по собственной логике готова к этим событиям. С точки зрения внешней системы задача может быть остановлена, заморожена на какое-то время, затем продолжена. Сама задача внутри себя такого изменения внешних условий не замечает.
Принцип 3. Задача работает с разделяемой памятью в двух режимах:
- осуществляет канальные, синхронизируемые операции ввода-вывода (чтения-записи),
- наблюдает самопроизвольно изменяющиеся (volatile) управляющие переменные-флаги.
Первое означает, что задача ни к одной переменной разделяемой памяти не обращается напрямую, а только посредством специальных процедур чтения-записи (read-write) или, в более простом случае, через защищённые критическими секциями процедуры-акссессоры (get-set). Второе означает, что задача может напрямую читать volatile-переменные, но использовать их может только в качестве управляющих логикой задачи флагов, но не в качестве источника исходных данных для обработки. Писать в volatile-переменные задача не должна. По крайней мере переменные для записи не являются для самой задачи volatile, хотя могут быть таковыми для каких-то других задач.
Принцип 4. В качестве задачи может выделяться лишь код, обладающий каким-нибудь из следующих свойств:
- он выполняет вычислительный процесс, длительность которого выходит за рамки кванта реального времени системы;
- он выполняет вычислительный процесс, длительность которого непредсказуема из-за наличия операций ввода-вывода.
Квант реального времени системы целиком зависит от прикладного назначения системы. Он может начинаться с длительности такта системной шины для самых низкоуровневых программ. Он может быть квантом переключения нитей в операционной системе для систем без жёсткого реального времени. Наконец он может быть периодом терпения пользователя (1-5 с), если речь идёт о системе с пользовательским интерфейсом. Он даже может быть периодом таймаута сетевых соединений (от 10 с до часов) в сетевых приложения. Коротко говоря, если кусок кода угрожает по какой-то причине зависнуть на неприлично долгое время, его стоит выносить в параллельно исполняемую задачу, за которой можно наблюдать «со стороны». Если же кусок кода не содержит в себе никаких потенциальных источников торможения и достаточно короткий - например, чисто вычислительный алгоритм без циклов и рекурсий, - его выделять в отдельную задачу не стоит.
Принцип 5. Для взаимодействия с другими задачами любая задача должна быть помещена в служебный объект, управляющий совместным использованием разделяемой памяти со стороны самой задачи и других внешних задач. Этот объект также должен предоставлять публичный интерфейс в виде набора асинхронных по отношению к внутренней задаче сервисов, позволяющий внешним задачам посылать сообщения, получать данные и дожидаться событий от внутренней задачи. Все сервисы (кроме ожидания событий) должны работать быстро в смысле принципа 4. Т.е. их операции должны быть подвергнуты декомпозиции на подзадачи до такой степени, чтобы оставшийся код каждого сервиса гарантированно бы завершал работу в рамках избранного кванта реального времени.
Принцип 6. Служебный объект управления задачей необходимо проектировать по принципам событийно-управляемого (в частности, автоматного) программирования. Отдалённо он напоминает шаблон проектирования «Посредник» (Mediator).
- Для каждого внешнего запроса, подразумевающего возврат данных, необходимо завести внутри объекта соответствующие переменные, хранящие подготовленные данные, чтобы возврат можно было произвести с минимальными задержками.
- Для каждого запроса ожидания события необходимо завести соответствующий объект синхронизации, снимающий блокировку и отпускающий всех ожидающих в момент наступления события.
- Для каждого посланного извне сообщения, а также для каждого наступившего внутри самой задачи события (отражённого изменением соответствующих переменных разделяемой памяти) необходимо завести внутренний метод-обработчик события.
- Любую операцию по изменению данных разделяемой памяти задачи или собственных переменных объекта необходимо выделить в метод-операцию.
- Аккуратно прописать правила вызова операций из обработчиков событий, если необходимо, ввести управляющие переменные состояния объекта и запрограммировать автоматное управление поведением объекта.
Итогом реализации этих принципов будет множество задач с изолированными контекстами, общающимися между собой посредством асинхронных сообщений, и передающих между собой данные по каналам связи, над которыми определены операции ввода-вывода. Если разрабатываемую программу систематически не приводить к такому состоянию, в ней неизбежно появится множество volatile-переменных с неизвестными писателями и читателями, и в итоге некоторые assert-утверждения будут время от времени непредсказуемо нарушаться - появятся плавающие ошибки. Описанная реализация, разумеется, громоздка - по сути повторяет свойства процессов операционной системы. Поэтому в ряде типовых простых случаев возможны типовые же упрощения реализации. Но любое упрощение должно делаться таким образом, чтобы результат не противоречил изложенным выше принципам. При появлении любой путаницы необходимо сначала восстановить недостающие до полного варианта элементы решения, отладить полученный результат и только потом пытаться его упростить.
Изоляцию контекста естественным образом обеспечивает инкапсуляция объекта, внутри которого реализован сервисный автомат, хранятся разделяемые каналы взаимодействия задачи с пользователями, а также могут храниться локальные переменные задачи, если сама задача подвергнута декомпозиции на процедуры по правилам структурного программирования. Открытые методы объекта выполняются в нитях других, внешних задач, поэтому по отношению к собственной задаче напоминают обработчики сигналов процессом UNIX.
Например, построим задачу, которая реализует доступ к некоторому неторопливому последовательно работающему процессору. Все внешние запросы асинхронные, ожидание пользователя не предусматривается.
// Модуль задачи
package mytask
import "time"
// Разделяемая память задачи - закрытый тип
type shared struct {
in chan interface{}
out chan interface{}
setStat func(s bool, m bool)
exit bool
}
// Собственно объект задачи - открытый тип
type MyTask struct {
// Закрытые переменные-индикаторы состояния и режима работы задачи
stat bool
mode bool
// закрытая переменная разделяемой памяти
mem *shared
// Объект синхронизации доступа к переменным
lock chan bool
}
// Закрытая часть
// Структурная декомпозиция тела задачи - заглушки-эмуляторы
func (this *MyTask) _init() {
time.Sleep(3 * time.Second)
}
func (this *MyTask) _proc(x interface{}) interface{} {
time.Sleep(1 * time.Second)
return x
}
func (this *MyTask) _done() {
time.Sleep(2 * time.Second)
}
// Тело задачи
func (this *MyTask) r_process() {
this._init()
this.mem.setStat(true, true)
for !this.mem.exit {
// x, y - переменные локальной памяти
x, ok := <-this.mem.in
if ok {
this.mem.setStat(true, false)
y := this._proc(x)
this.mem.setStat(true, true)
this.mem.out <- y
}
}
this.mem.setStat(false, false)
this._done()
}
// Операции задачи
// Обновление индикаторов
func (this *MyTask) o_setStat(s bool, m bool) {
// Индикаторы обновляются согласованно как атомарная операция в критической секции
this.lock <- true
this.stat = s
this.mode = m
if this.mem.exit && !this.stat {
// Когда закончили работу, закрываем выходной канал,
// чтобы отпустить ожидающего на нём пользователя
close(this.mem.out)
}
<-this.lock
}
// Запрос состояния
func (this *MyTask) o_getStat() (s bool, m bool) {
// Индикаторы сообщаются согласованно как атомарная операция в критической секции
this.lock <- true
s = this.stat
m = this.mode
<-this.lock
return
}
// Завершение задачи
func (this *MyTask) o_exit() {
// Устанавливаем управляющий флаг
this.mem.exit = true
// Закрываем входной канал,
// чтобы разбудить возможно ожидающую на нём задачу
close(this.mem.in)
}
// Операция вывода
func (this *MyTask) o_out() (x interface{}, ok bool) {
// Вывод работает только в особом режиме задачи
this.lock <- true
ok = this.stat && this.mode && len(this.mem.out) == 1
if ok {
x, ok = <-this.mem.out
}
<-this.lock
return
}
// Операция ввода
func (this *MyTask) o_in(x interface{}) (ok bool) {
// Ввод работает только в особом режиме задачи
this.lock <- true
ok = this.stat && this.mode && len(this.mem.in) == 0
if ok {
this.mem.in <- x
}
<-this.lock
return
}
// Открытая часть
// Конструктор
func NewMyTask() *MyTask {
this := new(MyTask)
this.stat = false
this.mode = false
this.lock = make(chan bool, 1)
this.mem = new(shared)
this.mem.in = make(chan interface{}, 1)
this.mem.out = make(chan interface{}, 1)
this.mem.exit = false
// вызов операции через лямбда-обработчик в замыкании конструктора, дающий ссылку на this
this.mem.setStat = func(s bool, m bool) { this.o_setStat(s, m) }
// Запуск задачи
go this.r_process()
// Возврат указателя на готовый, работающий объект
return this
}
// Запрос остановки задачи
func (this *MyTask) Close() {
this.o_exit();
}
// Запроса статуса задачи
func (this *MyTask) Status() (enabled bool, free bool) {
enabled, free = this.o_getStat()
return
}
// Запрос результата работы задачи
func (this *MyTask) Get() (value interface{}, good bool) {
value, good = this.o_out()
return
}
// Запрос выполнить новое задание
func (this *MyTask) Pass(value interface{}) (good bool) {
good = this.o_in(value)
return
}
Здесь использованы следующие систематические для любой задачи структуры и обозначения.
1) Для главной процедуры задачи использован префикс «r_», все вспомогательные процедуры и функции, предназначенные для декомпозиции тела задачи, идут с префиксом «_».
2) Содержимое разделяемой памяти сосредоточено во внутренней структуре shared.
3) Все операции над состоянием объекта и обработки внешних и внутренних событий имеют префикс «o_».
4) Почти все операции защищены критической секцией, что исключает их взаимно несогласованные действия относительно состояния объекта и разделяемой памяти. При этом все операции спроектированы таким образом, что не имеют шанса заметно долго зависнуть на операциях ввода-вывода.
5) Все запросы внешнего интерфейса рассматриваются как события, наряду с внутренним событием обновления состояния. Таким образом любой метод внешнего интерфейса (кроме конструктора) и процедура обновления состояния задачи рассматриваются как обработчики событий, напрямую ничего не делающие, а только вызывающие те или иные операции.
6) Разделяемая память содержит только элементы, доступные телу задачи, и ничего более. Там имеются каналы ввода-вывода, volatile-переменная управляющего флага и операции сигнализирования о событиях с сопутствующими информационными параметрами. И даже неплохо было бы имеющиеся каналы сделать типизированными, отдельно отображая их концы для ввода и вывода внутрь объекта и внутрь разделяемой памяти задачи.
7) Тело задачи имеет собственные локальные переменные - собственную память, в остальном оно обращается исключительно к процедурам собственной декомпозиции и только к разделяемой памяти. Никаких прямых вызовов операций, никакого прямого обращения к переменным объекта.
В данном конкретном случае выделение операций не является обязательным, так как любая операция вызывается строго из одного обработчика события. Можно упростить. Но в общем случае, когда программируются автоматы со сложным поведением, это не так: каждая операции может вызываться из множества обработчиков при разных условиях. Особенно часто это наблюдается при разработке сложных форм графического интерфейса, когда один элемент управления имеет множество обработчиков разноплановых событий от разных способов ввода, и связанное с этим элементом информационное поле модели может меняться в результате разного типа воздействий на элемент.
Небольшим упрощением может быть отказ от структуры shared и создание внутри объекта группы переменных с префиксом «s_». Особенно актуально, когда такая переменная лишь одна.
Значительное упрощение возможно в стандартном случае, когда задачей является отдельная разовая фоновая операция. Её отличительной чертой является отсутствие множества внешних запросов во время работы задачи и отсутствие внешнего управления. Есть только набор входных параметров, известных с самого начала, и набор выходных параметров, определяемый к самому концу работы задачи. Тогда внешний интерфейс объекта сводится лишь единственному методу вроде ReadResult с ожиданием, а то и просто Wait, если это процедура без выходных параметров. Такая задача может быть сосредоточена внутри одной запускающей функции и может возвращать лишь объект синхронизации, с помощью которого пользователь дождётся окончания работы задачи или убедится, что она закончила работу к моменту проверки.
Также стоит сказать о ряде чисто вспомогательных задач. Например, таких, которые обеспечивают канальную связь между двумя другими задачами:
go (func(x, y) { for { y.write(x.read()) } })(a, b)
или дают широковещательный (broadcast) доступ к результатам работы задачи:
type Broadcast struct {
x interface{}
m sync.Locker
}
func NewBroadcast(read func() interface{}) {
this := new(Broadcast)
this.m := new(sync.Mutex)
m.Lock()
go (func() {
this.x = read()
this.m.Unlock()
})()
return this
}
func (this *Broadcast) Read() (x interface{}) {
this.m.Lock()
x = this.x
this.m.Unlock()
return
}
В таких случаях тоже очевидны существенные упрощения. Как правило, набор подобных вспомогательных задач заранее реализуется в виде библиотеки для повторного использования.
