Главная проблема, стоящая за сложностями состояния, идентичности и изменения, состоит в том, что, введя присваивание, мы вынуждены внести в свои вычислительные модели понятие времени (time). До того, как появилось присваивание, наши программы от времени не зависели - в том смысле, что всякое выражение, обладающее значением, всегда имело одно и то же значение. Вспомним, однако, пример со снятием денег со счета и просмотром получившегося баланса из начала раздела 3.1.1:

(withdraw 25)

75

(withdraw 25) 50

Здесь последовательное вычисление одного и того же выражения приводит к различным результатам. Такое поведение возникает из-за того, что выполнение предложений присваивания (в данном случае присваивания переменной balance) отмечает моменты времени (moments in time), когда значения меняются. Результат вычисления выражения зависит не только от самого выражения, но и от того, происходит ли вычисление до или после таких моментов. Построение моделей в терминах вычислительных объектов с внутренним состоянием заставляет нас рассматривать время как существенное для программирования понятие.

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

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

К несчастью, проблемы, связанные с присваиванием, становятся только тяжелее в присутствии параллелизма. Связано ли это с тем, что параллельно

34 На самом деле большинство процессоров выполняют несколько операций за раз, используя стратегию, называемую конвейеризация (pipelining). Хотя этот метод значительно повышает степень использования аппаратных ресурсов, он используется только для ускорения выполнения последовательного потока вычислений, сохраняя поведение последовательной программы.

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

3.4.1 Природа времени в параллельных системах

На первый взгляд, время - вещь простая. Это порядок, накладываемый на события.35 Для всяких двух событий A и B, либо A случается раньше B, либо A и B происходят одновременно, либо A случается позже B. Например, возвращаясь к примеру с банковским счетом, пусть Петр берет с общего счета 10 долларов, а Павел 25, притом, что сначала на счету 100 долларов. На счету останется 65 долларов. В зависимости от порядка двух событий, последовательность балансов на счету будет либо $100 - $90 - $65, либо $100 - $75 - $65. В компьютерной реализации банковской системы эта изменяющаяся последовательность балансов может моделироваться через последовательные присваивания переменной balance.

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

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

(define (withdraw amount) (if (>= balance amount)

(begin (set! balance (- balance amount))

balance) "Недостаточно денег на счете"))

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

И это еще не самое худшее. Рассмотрим выражение (set! balance (- balance amount))

которое выполняется во время каждого снятия денег. Выполнение происходит в три шага: (1) считывание значения переменной balance; (2) вычисление нового значения баланса; (3) присвоение переменной balance этого нового значения. Если процессы Петра и Павла выполняют это предложение параллельно, то в двух процессах снятия денег порядок чтения переменной balance и присваивания могут чередоваться.

Временная диаграмма на рисунке 3.29 показывает порядок событий, при котором balance сначала равен 100. Петр берет 10, Павел берет 25, и однако в итоге balance оказывается равен 75. Как показано на диаграмме, причина аномалии состоит в том, что у Павла присваивание переменной значения

35Граффити на одной стене в Кембридже: «Время - это устройство для того, чтобы случалось не все сразу».

Петр

Банк

-$ню)-

Павел

С Считать balance: $100 ) ( Считать balance: $100 )

%

Гновое значение: 100-10=90j

( установить balance в $90)

(новое значение: 100-25=75")

/ $90 ) .

\ У ( установить balance в $75 )

$75)-

время

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

75 основано на предположении, что значение balance, которое надо уменьшить, равно 100. Однако это предположение стало неверным, когда Петр сделал balance равным 90. Для банковской системы это катастрофическая ошибка, поскольку не сохраняется общее количество денег в системе. До транзакций общая сумма была 100 долларов. После же у Петра оказывается 10 долларов, у Павла - 25, и у банка 75.36

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

36Еще худшая ошибка могла бы случиться, если бы две операции set! попытались одновременно изменить баланс. В результате содержимое памяти могло бы стать случайной комбинацией данных, записанных двумя процессами. В большинство компьютеров встроена блокировка элементарных операций записи в память, которая предохраняет от такого одновременного доступа. Однако даже такой, казалось бы, простой метод защиты придает дополнительную сложность проектированию многопроцессорных компьютеров, где требуются сложные протоколы согласованности кэша (cache coherence), чтобы у разных процессоров были непротиворечивые точки зрения на содержимое памяти, при том, что данные могут дублироваться («кэшироваться») в разных процессорах, чтобы увеличить скорость доступа к памяти.