Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 65
Текст из файла (страница 65)
Поскольку формат выражений предпочтителен, можно спросить, есть ли причинастроить систему императивно, как мы поступили в этом разделе. Одна из причин состоит в том, что языкограничений, не ориентированный на выражения, дает нам возможность работать не только с объектамисоединителями, но и с объектами-ограничениями (например, значением, порождаемым процедурой adder).Это будет полезно, если мы захотим расширить систему новыми операциями, которые работают с ограничениями напрямую, а не только косвенным образом через операции над соединителями. Хотя реализовать работус выражениями на основе императивной реализации просто, сделать обратное значительно труднее.282Глава 3.
Модульность, объекты и состояние(withdraw 25)75(withdraw 25)50Здесь последовательное вычисление одного и того же выражения приводит к различным результатам. Такое поведение возникает из-за того, что выполнение предложенийприсваивания (в данном случае присваивания переменной balance) отмечает моментывремени (moments in time), когда значения меняются. Результат вычисления выражениязависит не только от самого выражения, но и от того, происходит ли вычисление доили после таких моментов. Построение моделей в терминах вычислительных объектовс внутренним состоянием заставляет нас рассматривать время как существенное дляпрограммирования понятие.Можно пойти еще дальше в структурировании наших вычислительных объектов, чтобы точнее отразить наше восприятие физического мира.
Объекты мира изменяются непоследовательно один за другим. Мы воспринимаем их как действующие параллельно(concurrently) — все вместе. Так что зачастую бывает естественно моделировать системы как сообщества вычислительных процессов, работающих параллельно. Точно так же,как можно сделать программы модульными, организуя их в виде объектов с раздельнымвнутренним состоянием, часто имеет смысл разделять вычислительные модели на части,вычисляющиеся раздельно и одновременно. Даже если на самом деле предполагаетсявыполнять программы на последовательном компьютере, практика написания программтак, как будто вычисление будет параллельным, заставляет программиста избегать несущественных временны́х ограничений, и таким образом повышает модульность программ.Параллельное вычисление не только делает программы модульнее, оно к тому жеможет дать выигрыш в скорости перед последовательным.
Последовательные компьютеры выполняют только одну операцию за раз, так что время, необходимое для решения задачи, пропорционально общему количеству выполняемых операций34 . Однако есливозможно разбить задачу на части, которые относительно независимы друг от друга идолжны общаться между собой редко, может оказаться возможным раздать эти кускиотдельным вычисляющим процессорам и получить выигрыш, пропорциональный числуимеющихся процессоров.К несчастью, проблемы, связанные с присваиванием, становятся только тяжелее вприсутствии параллелизма. Связано ли это с тем, что параллельно работает мир, иликомпьютер, но явление одновременных вычислений привносит дополнительную сложность в наше понимание времени.3.4. Параллелизм: время имеет значениеПетр283БанкПавел$100Считать balance: $100Считать balance: $100новое значение: 100-10=90новое значение: 100-25=75установить balance в $90$90установить balance в $75$75времяРис.
3.29. Временная диаграмма, показывающая, как чередование действий при двухоперациях со счетом может привести к неправильному балансу.284Глава 3. Модульность, объекты и состояние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. Как показано на диаграмме, причина аномалии состоит в том,34 На самом деле большинство процессоров выполняют несколько операций за раз, используя стратегию,называемую конвейеризация (pipelining). Хотя этот метод значительно повышает степень использования аппаратных ресурсов, он используется только для ускорения выполнения последовательного потока вычислений,сохраняя поведение последовательной программы.35 Граффити на одной стене в Кембридже: «Время — это устройство для того, чтобы случалось не все сразу».3.4. Параллелизм: время имеет значение285что у Павла присваивание переменной значения 75 основано на предположении, чтозначение balance, которое надо уменьшить, равно 100.
Однако это предположениестало неверным, когда Петр сделал balance равным 90. Для банковской системы этокатастрофическая ошибка, так как не сохраняется общее количество денег в системе.До транзакций общая сумма была 100 долларов. После же у Петра оказывается 10долларов, у Павла 25, и у банка 7536 .Общее явление, иллюстрируемое здесь, состоит в том, что различные процессы могутразделять одну и ту же переменную состояния. Сложность возникает оттого, что с этойпеременной в одно и то же время может пытаться работать более одного процесса.
Впримере с банковским счетом во время каждой транзакции клиент должен иметь возможность действовать так, как будто остальных клиентов не существует. Когда клиентизменяет баланс, исходя из его предыдущего значения, ему надо обеспечить гарантиитого, что прямо перед моментом изменения баланс все еще соответствует его, клиента,представлениям.Правильное поведение параллельных программВышеприведенный пример демонстрирует типичную неочевидную ошибку, котораяможет возникнуть в параллельной программе.
Сложность здесь восходит к присваиванию переменным, разделяемым между различными процессами. Мы уже знаем, чтопри работе с set! требуется осторожность, потому что результаты вычислений зависятот порядка, в котором происходят присваивания37. При наличии параллелизма нужнобыть острожным вдвойне, поскольку не всегда можно управлять порядком, в которомприсваивания происходят в разных процессах. Если несколько таких изменений могутпроисходить одновременно (как в случае с двумя вкладчиками, имеющими доступ кобщему счету), нам требуется способ обеспечить правильную работу системы. Например, в случае со снятием денег с общего счета, мы должны сделать так, чтобы общееколичество денег оставалось неизменным.
Чтобы заставить параллельные программы работать корректно, иногда требуется наложить некоторые ограничения на одновременноеисполнение.Одно из возможных ограничений на параллелизм может состоять в том, что никакие две операции, способные изменить разделяемые переменные состояния, не могут исполняться одновременно. Это очень серьезное ограничение. Для распределенной банковской системы это означало бы, что проектировщик системы должен сделать так, что в каждый момент происходит не более одной транзакции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
