Параллельное выполнение процессов

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

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

Большинство практически применяемых структур данных должны соответствовать тем или иным предположениям, критериям целостности. Например, в упорядоченном массиве каждый следующий элемент должен быть больше (то, что в данном конкретном случае подразумевается под “больше”, называется критерием или условием сортировки) предыдущего или равен ему, основной способ модификации упорядоченного массива – это вставка в него дополнительного элемента. Вставка в такой массив может быть осуществлена различными способами, например, добавлением нового элемента в конец и выполнением сортировки методом “пузырька”, или поиском места, куда элемент должен быть вставлен, и перемещением элементов с большими индексами.

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

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

При разработке параллельной программы мы можем неявно сделать и использовать при кодировании предположение, что состояние некоторого объекта в некоторый период времени не меняется – а оно может измениться. Если такая ошибка сделана в последовательно исполняющейся программе, она может быть выявлена при первом же тестовом прогоне. Для выявления же ее в программе с асинхронно исполняющимися модулями потребуется гораздо больше тестовых запусков, при которых мы должны вызывать прерывание в различные моменты времени. Для исчерпывающего тестирования необходимо перебрать все возможные относительные моменты вызова прерывания, т.е. обеспечить хотя бы раз вызов прерывания после каждой из команд в каждой из возможных последовательностей исполнения основной программы. Стоимость такого тестирования запредельно высока, поэтому ошибки такого рода (в англоязычной литературе они называются race condition (дословно – ошибка соревнования), практически невозможно искоренить в процессе тестирования.

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

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

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

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

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

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

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

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

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

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

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

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

Программный модуль, внутри которого имеется хотя бы одна критическая секция, для которой не обеспечено взаимное исключение, называется нереентерабельным. Вызов процедур такого модуля из различных нитей приведет к ошибкам соревнования и допустим лишь при условии, что вызывающая программа реализует взаимное исключение самостоятельно. Соответственно, модуль, в котором таких секций нет, или который сам обеспечивает взаимное исключение для них, называется реентерабельным (от англ. re-enterable – способный к повторному вхождению) или реентрантным (reentrant). В современной англоязычной литературе часто также употребляются термины thread-unsafe (для обозначения нереентерабельных процедур) и thread-safe (соответственно, для реентерабельных).

Рассмотрим простейший случай разделяемого объекта: флаговую переменную, которая может принимать значения True и False. Такая переменная, в частности, может использоваться для реализации взаимного исключения в секции, работающей с более сложной структурой данных. Если в критической секции не находится ни одной нити, переменная равна False, иначе – True. При входе в секцию нам необходимо проверить значение переменной и, если блокируемый участок свободен, присвоить ей значение True.