Параллелизм, время и взаимодействие

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

Механизмы вроде test-and-set! требуют, чтобы процессы в произвольные моменты времени имели доступ к глобальному разделяемому флагу. На современных высокоскоростных процессорах это реализуется сложно и неэффективно, поскольку, благодаря средствам оптимизации вроде конвейеров и кэширования памяти, содержимое памяти не обязательно должно в каждый момент находиться в непротиворечивом состоянии. Из-за этого в современных многопроцессорных системах идея сериализаторов вытесняется новыми подходами к управлению параллелизмом.49

Кроме того, проблемы с разделяемым состоянием возникают в больших распределенных системах. Например, рассмотрим распределенную банковскую систему, в которой отдельные местные банки поддерживают собственные значения баланса счетов и время от времени сравнивают их со значениями, хранимыми в других местах. В такой системе значение «баланс счета» не будет определенным ни в какой момент, кроме как сразу после синхронизации. Если Петр вносит деньги на счет, который он делит с Павлом, когда мы должны считать, что баланс изменился, - когда меняется баланс в местном банке или только после синхронизации? А если Павел обращается к счету через другую ветвь системы, какие ограничения нужно наложить на банковскую систему, чтобы ее поведение считалось «правильным»? Единственное, что может иметь значение для определения «правильности», - это поведение, которое Павел и Петр наблюдают по отдельности, и состояние счета сразу после синхронизации. Вопросы о «настоящем» значении баланса или порядке событий между синхронизациями могут не иметь значения или даже смысла.50

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

49Один из подходов, альтернативных сериализации, называется барьерная синхронизация (barrier synchronization). Программист позволяет параллельным процессам выполняться как угодно, но устанавливает определенные точки синхронизации («барьеры»), так что ни один процесс не может продолжаться, пока все они не достигли барьера. Современные процессоры обладают машинными командами, которые позволяют программистам устанавливать точки синхронизации там, где требуется иметь непротиворечивое состояние. Например, в Power PCTM имеются две предназначенные для этого команды: SYNC и EIEIO (Enforced In-Order Execution of Input-Output, Гарантированно Последовательное Исполнение Ввода-Вывода).

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

51 Для распределенных систем эта точка зрения исследовалась Лэмпортом (Lamport 1978). Он показал, как при помощи взаимодействия установить «глобальные часы», через которые можно управлять порядком событий в распределенных системах.

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

3.5 Потоки

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

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

Возможен ли другой подход? Можно ли избежать отождествления времени в компьютере с временем в моделируемом мире? Должны ли мы заставить модель изменяться во времени, чтобы смоделировать явления изменяющегося мира? Давайте подумаем об этом в терминах математических функций. Можно описать изменение во времени величины x с помощью функции x(t), где время выступает как аргумент. Если мы сосредотачиваем внимание на x момент за моментом, мы думаем об изменяющейся величине. Однако если мы обращаем внимание на всю хронологию значений, мы не подчеркиваем изменение - функция сама по себе не изменяется.52

Если время измеряется дискретными интервалами, мы можем смоделировать функцию времени как последовательность (возможно, бесконечную). В этом разделе мы увидим, как моделировать изменение в виде последовательностей, которые представляют картины изменения во времени систем, подвергаемых моделированию. С этой целью мы вводим новую структуру данных, называемую поток (stream). С абстрактной точки зрения, поток - это просто последовательность. Однако, как мы увидим, прямое представление потоков в виде списков (как в разделе 2.2.1) не полностью раскрывает мощь работы с потоками. В качестве альтернативы мы введем метод задержанных вычислений (delayed evaluation), который позволит нам представлять очень большие (даже бесконечные) последовательности в виде потоков.

Работа с потоками позволяет моделировать системы, обладающие состоянием, совершенно не используя присваивание и изменяемые данные. Отсюда

52Физики иногда принимают эту точку зрения, вводя «мировые линии» частиц в рассуждениях о движении. Кроме того, мы уже упоминали (в разделе 2.2.3), что это естественный ход мысли при рассужднениях о системах обработки сигналов. Мы рассмотрим приложение потоков к обработке сигналов в разделе 3.5.3.

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

3.5.1 Потоки как задержанные списки

Как мы видели в разделе 2.2.3, последовательности можно использовать как стандартные интерфейсы для комбинирования программных модулей. Мы сформулировали мощные абстракции для работы с последовательностями, такие как map, filter и accumulate, с помощью которых можно описать широкий класс действий одновременно коротко и изящно.

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

Чтобы понять, почему это так, сравним две программы для вычисления суммы всех простых чисел на интервале. Первая программа написана в стандартном итеративном стиле:53

(define (sum-primes a b) (define (iter count accum) (cond ((> count b) accum)

((prime? count) (iter (+ count l) (+ count accum))) (else (iter (+ count l) accum))))

(iter a 0))

Вторая программа производит то же самое вычисление с помощью операций над последовательностями из раздела 2.2.3:

(define (sum-primes a b) (accumulate +

0

(filter prime? (enumerate-interval a b))))

Во время вычисления первая программа должна хранить только накапливаемую сумму. Напротив, фильтр во второй программе не может начать тестировать, пока enumerate-interval не создала полного списка чисел на интервале. Фильтр порождает еще один список, который, в свою очередь, передается accumulate, прежде, чем он сожмется в сумму. Первой программе не требуется такого количества промежуточной памяти, - мы можем считать, что она просто проходит интервал снизу вверх, добавляя к сумме каждое простое число, которое ей встретится.

Неэффективность использования списков становится болезненно очевидной, если мы воспользуемся парадигмой последовательностей для вычисления второго простого числа в интервале от 1000 до 1 000 000 при помощи следующего выражения:

53Мы предполагаем, что у нас имеется предикат prime? (например, из раздела 1.2.6), который проверяет, является ли число простым.