Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 66
Текст из файла (страница 66)
Это требование чрезмерно консервативное и ведет к неэффективности. На рисунке 3.30 показан случай с совместным счетом Петра и Павла, причем у Павла есть еще и36 Еще худшая ошибка могла бы случиться, если бы две операции set! попытались одновременно изменитьбаланс. В результате содержимое памяти могло бы стать случайной комбинацией данных, записанных двумя процессами. В большинство компьютеров встроена блокировка элементарных операций записи в память,которая предохраняет от такого одновременного доступа.
Однако даже такой, казалось бы, простой метод защиты придает дополнительную сложность проектированию многопроцессорных компьютеров, где требуютсясложные протоколы согласованности кэша (cache coherence), чтобы у разных процессоров были непротиворечивые точки зрения на содержимое памяти, при том, что данные могут дублироваться («кэшироваться») вразных процессорах, чтобы увеличить скорость доступа к памяти.37 Программа подсчета факториала из раздела 3.1.3 демонстрирует это в рамках одного последовательногопроцесса.Глава 3. Модульность, объекты и состояние286ПетрБанк1ПавелБанк2$7$100$5$300W$17D$90$0$305$25$305W$17$65времяРис.
3.30. Одновременные операции при работе с совместным счетом в Банке 1 и личнымсчетом в Банке 2.собственный счет. Диаграмма показывает две операции снятия денег с совместного счета (одну проводит Петр, одну Павел), а также занесение Павлом денег наличный счет38 . Два снятия денег с одного счета не должны происходить одновременно (поскольку оба работают с одним счетом), и Павел не может одновременно снять деньги и занести их в банк (поскольку и та, и другая операция касаются кошелька Павла).
Однако не должно быть препятствий, мешающих Павлу заносить деньги на личный счет в то время, как Петр берет деньги с общего счета.Менее драконовское ограничение на параллелизм могло бы состоять в том, чтобы параллельная система выдавала такие же результаты, как если бы процессы происходилипоследовательно. У этого ограничения две важных стороны. Во-первых, от процессов насамом деле не требуется последовательного исполнения, а только результаты, совпадающие с теми, которые получались бы, если бы они работали один за другим. В примерена рис. 3.30, проектировщик банковской системы спокойно может разрешить одновременное занесение денег Павлом и снятие их Петром, поскольку общий результат будеттаков, как будто бы они шли последовательно.
Во-вторых, у параллельной программыможет быть более одного «правильного» результата, потому что мы требуем только, что38 По столбцам: содержимое кошелька Петра, общий счет (в Банке 1), кошелек Павла и личный счет Павла(в Банке 2), до и после каждого снятия (W) и занесения денег на счет (D). Петр берет 10 долларов из Банка1; Павел кладет 5 долларов в Банк 2, затем берет 25 долларов из Банка 1.3.4. Параллелизм: время имеет значение287бы он совпадал с результатом при каком-нибудь последовательном порядке.
Например,предположим, что общий счет Петра и Павла вначале равен 100 долларам, Петр кладетна него 40 долларов, а Павел снимает половину имеющихся там денег. При этом последовательное исполнение может привести к значению на счету либо в 70, либо в 90долларов (см. упражнение 3.38)39 .Можно найти и еще более слабые требования для корректного выполнения параллельных программ. Программа, имитирующая диффузию (например, поток тепла в объекте), может состоять из большого числа процессов, каждый из которых изображает маленький участок пространства, и которые параллельно обновляют свои значения.Каждый процесс в цикле изменяет свое значение на среднее между своим собственнымзначением и значениями соседей.
Этот алгоритм сходится к правильному ответу независимо от порядка, в котором выполняются операции; нет никакой нужды в ограниченияхна параллельное использование разделяемых значений.Упражнение 3.38.Пусть Петр, Павел и Мария имеют общий счет, на котором вначале лежит 100 долларов. Петркладет на счет 10 долларов, одновременно с этим Павел берет 20, а Мария берет половину денегсо счета. При этом они выполняют следующие операции:Петр: (set! balance (+ balance 10))Павел: (set! balance (- balance 20))Мария: (set! balance (- balance (/ balance 2)))а. Перечислите возможные значения balance после завершения операций, предполагая, чтобанковская система требует от транзакций исполняться последовательно в каком-то порядке.б.
Назовите какие-нибудь другие значения, которые могли бы получиться, если бы системаразрешала операциям чередоваться. Нарисуйте временные диаграммы, подобные рис. 3.29, чтобыобъяснить, как возникают такие результаты.3.4.2. Механизмы управления параллелизмомМы убедились, что сложность работы с параллельными процессами происходит изнеобходимости учитывать порядок чередования событий в различных процессах. Предположим, к примеру, что у нас есть два процесса, один с упорядоченными событиями(a, b, c), а другой с упорядоченными событиями (x, y, z). Если эти два процесса исполняются параллельно, без каких-либо дополнительных ограничений на чередование событий, то возможно 20 различных порядков событий, соблюдающих упорядочение ихвнутри каждого из процессов:(a, b, c, x, y, z)(a, b, x, c, y, z)(a, b, x, y, c, z)(a, b, x, y, z, c)(a, x, b, c, y, z)(a, x, b, y, c, z)(a, x, b, y, z, c)(a, x, y, b, c, z)(a, x, y, b, z, c)(a, x, y, z, b, c)(x, a, b, c, y, z) (x, a, y, z, b, c)(x, a, b, y, c, z) (x, y, a, b, c, z)(x, a, b, y, z, c) (x, y, a, b, z, c)(x, a, y, b, c, z) (x, y, a, x, b, c)(x, a, y, b, z, c) (x, y, x, a, b, c)39 Более формально это утверждение можно выразить, сказав, что поведение параллельных программ —недетерминированное (nondeterministic).
То есть, они описываются не функциями с одним значением, а функциями, чьи результаты являются множествами возможных значений. В разделе 4.3 мы рассмотрим язык длявыражения недетерминистских вычислений.288Глава 3. Модульность, объекты и состояниеПри разработке этой системы нам как программистам пришлось бы рассматривать результаты каждого из этих 20 упорядочений и проверять, что каждое из них допустимо.С ростом числа процессов и событий такой подход быстро становится нереалистичным.Более практичный подход к проектированию параллельных систем состоит в том,чтобы придумать общие механизмы, которые бы ограничивали чередование событий впараллельных процессах и тем самым давали нам уверенность, что поведение программыверно.
Для этой цели было разработано большое количество механизмов. В этом разделемы опишем один из них — сериализатор (serializer).Сериализация доступа к разделяемой памятиИдея сериализации заключается в следующем: процессы выполняются параллельно,но при этом существуют определенные группы процедур, которые не могут выполняться одновременно. Выражаясь точнее, сериализация порождает выделенные множествапроцедур, такие, что в каждом сериализованном множестве в любой момент может происходить выполнение только одной процедуры из множества. Если какая-то процедура измножества уже выполняется, то процесс, который пытается выполнить любую процедуруиз множества, будет приостановлен до тех пор, пока не закончится текущее вычислениепроцедуры.С помощью сериализации можно управлять доступом к разделяемым переменным.Например, если мы хотим присвоить разделяемой переменной значение, зависящее от еетекущего значения, мы помещаем доступ к прежнему значению и присваивание новогов одну процедуру.
Затем мы помещаем все такие процедуры в один сериализатор и темсамым добиваемся того, что никакая другая процедура, которая присваивает значенияэтой переменной, не может выполняться одновременно с нашей. Это гарантирует нам,что значение переменной не может измениться в промежутке между доступом к ней исоответствующим ему присваиванием.Сериализаторы в SchemeЧтобы сделать это описание более конкретным, предположим, что мы расширилиязык Scheme, добавив в него процедуру parallel-execute:(parallel-execute hp1 i hp2 i ...
hpk i)Каждый из hpi должен быть процедурой без аргументов. Parallel-execute создаетдля каждого hpi отдельный процесс, который выполняет hpi (с пустым набором аргументов). Все эти процессы выполняются параллельно40 .Чтобы продемонстрировать, как эта процедура используется, рассмотрим(define x 10)(parallel-execute (lambda () (set! x (* x x)))(lambda () (set! x (+ x 1))))40 Parallel-execute не входит в стандартную Scheme, но такая процедура может быть реализована вMIT Scheme. В нашей реализации новые процессы выполняются параллельно еще и с исходным Schemeпроцессом.
Кроме того, в нашей реализации значение, которое возвращает parallel-execute, представляетсобой специальный управляющий объект, с помощью которого можно остановить все новосозданные процессы.3.4. Параллелизм: время имеет значение289Здесь создаются два параллельных процесса — P1 , который присваивает x значение xумножить на x, и P2 , который увеличивает x на единицу. После того, как вычислениезакончено, x может иметь одно из пяти значений, в зависимости от чередования событийв P1 и P2 :• 101: P1 делает x равным 100, затем P2 его увеличивает.• 121: P2 увеличивает x, делая его равным 11, затем P1 присваивает ему значение xумножить на x.• 110: P2 изменяет x с 10 на 11 в промежутке между двумя обращениями к x из P1во время вычисления (* x x).• 11: P2 читает x, затем P1 присваивает ему значение 100, затем P1 пишет x• 100: P1 читает x (дважды), затем P2 присваивает ему значение 11, затем P1 записывает значение x.Мы можем ограничить параллелизм, используя сериализованные процедуры, которые создаются сериализаторами (serializers).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
