Параллелизм с точки зрения программиста
Ты выбежал за угол купить вина
Ты вернулся, а вместо дома стена.
Б. Гребенщиков
На палубу вышел, и палубы нет
В глазах у него помутилось.
В. Пелевин
В предыдущей главе мы видели, что даже в современном однопроцессорном персональном компьютере происходит множество параллельных процессов: звуковая карта играет, жесткий диск и сетевой интерфейс передают данные, пользователь двигает мышью – работа кипит! А что начнется, если пользователь запустит задание на печать, так и просто страшно подумать. Написание программ, способных работать в среде с множеством параллельно происходящих процессов, представляет собой нетривиальную задачу.
На первый взгляд, сложности здесь никакой нет – аппаратура предоставляет нам механизм прерываний. Обработал прерывание – и наступило счастье. В действительности, никакого счастья от одной только обработки прерывания не наступит, пока мы не сообщим о происшедшем событии основному потоку программы, заинтересованной в этом событии.
Основной поток программы и реализуемые этой программой обработчики прерываний должны взаимодействовать и разделять те или иные данные. При этом в обработчике прерывания мы не всегда можем точно выяснить, в какой точке основной поток программы был прерван (в принципе, можно проанализировать сохраненный счетчик команд и, возможно, локальные переменные основного потока, но это очень сложно и само по себе вряд ли приблизит нас к реализации корректно взаимодействующих потоков), а основной поток не всегда может знать, в какой момент происходило (и происходило ли) прерывание.
Большинство практически применяемых структур данных должны соответствовать тем или иным предположениям, критериям целостности. Например, в упорядоченном массиве каждый следующий элемент должен быть больше (то, что в данном конкретном случае подразумевается под "больше", называется критерием или условием сортировки) предыдущего или равен ему основной способ модификации упорядоченного массива – это вставка в него дополнительного элемента. Вставка в такой массив может быть осуществлена различными способами, например, добавлением нового элемента в конец и выполнением сортировки методом "пузырька", или поиском места, куда элемент должен быть вставлен, и перемещением элементов с большими индексами.
Важно, что любой способ вставки происходит не мгновенно, и все время работы этой процедуры массив не является упорядоченным. Если вставка происходила в основном потоке программы, обработчик прерывания, который в это время попытается работать с массивом, как с упорядоченным – например, произвести в нем дихотомический поиск – будет жестоко разочарован.
Задача разработки программы, взаимодействующей с обработчиком прерывания, таким образом, может быть переформулирована как написание программы, некоторые переменные которой подвержены изменению в непредсказуемые моменты времени.
Это обстоятельство резко усложняет анализ алгоритмов (в частности, доказательство корректности программ) и доставило в свое время много волнений теоретикам программирования. Например, в [Дейкстра 1978] один из основателей структурного программирования, Э. Дейкстра, очень эмоционально описывает свою реакцию при первом столкновении с системой, использующей прерывания. Кроме теоретических сложностей, разработка таких программ сопряжена и со сложностями практическими.
При разработке параллельной программы мы можем неявно сделать и использовать при кодировании предположение, что состояние некоторого объекта в некоторый период времени не меняется – а оно может измениться. Если такая ошибка сделана в последовательно исполняющейся программе, она может быть выявлена при первом же тестовом прогоне. Для выявления же ее в программе с асинхронно исполняющимися модулями потребуется гораздо больше тестовых запусков, при которых мы должны вызывать прерывание в различные моменты времени.
Для исчерпывающего тестирования необходимо перебрать все возможные относительные моменты вызова прерывания, т. е. обеспечить хотя бы раз вызов прерывания после каждой из команд в каждой из возможных последовательностей исполнения основной программы. Стоимость такого тестирования запретительно высока, поэтому ошибки такого рода (в англоязычной литературе они называются race condition (дословно – ошибка соревнования), хорошего же русского термина автору неизвестно) практически невозможно искоренить в процессе тестирования.
Таким образом, единственный способ избежать ошибок соревнования – это не делать их. Для того чтобы не делать ошибок, нужна формальная методика разработки и кодирования параллельно исполняющихся программ. Понятно, что и наличие методики не может полностью исключить ошибки. Однако, если выработанная методика адекватна, каждая ошибка будет ее нарушением, поэтому ошибки могут выявляться анализом кода на соответствие формальным требованиям.
К счастью, автору этой книги нет необходимости заниматься разработкой такой методики с чистого листа. Достаточно лишь, по возможности связно, изложить уже изобретенные методы. Не буду утруждать себя и читателя полным доказательством корректности предлагаемых методик, приводя лишь "интуитивное" обоснование их применимости. Сомневающимся могу предложить либо разработать полное доказательство самостоятельно, либо обратиться к специальной литературе, например [Хоар 1989].
Приведенная ранее формулировка задачи справедлива не только для взаимодействия основного потока программы с обработчиком прерывания, но и для взаимодействия программ, исполняющихся на различных процессорах, а также для программы, непосредственно взаимодействующей с внешними событиями, например посредством опроса. В разд. "Вытесняющая многозадачность" мы увидим, что [псевдо]параллельные нити исполнения, не являющиеся обработчиками прерываний, довольно легко можно реализовать на однопроцессорной машине, и практически все современные ОС предоставляют такой сервис.
Большинство концепций, обсуждаемых в этой главе, приложимы ко всем перечисленным случаям, поэтому далее в тексте мы будем говорить не о программе и обработчике прерывания, а о двух или более потоках или нитях исполнения. В действительности, одна из взаимодействующих "нитей" может не быть процессом исполнения программы, а представлять собой физический процесс (например, перемотку ленты, перемещение считывающей головки дисковода, или химическую или даже ядерную реакцию в установке, которой управляет наш компьютер) или процесс, происходящий в голове или других модулях нервной системы пользователя-человека, но в большинстве случаев нас эта тонкость не интересует.