Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 67
Текст из файла (страница 67)
Сериализаторы порождаются процедуройmake-serializer, реализация которой дана ниже. Сериализатор принимает в качествеаргумента процедуру, и возвращает сериализованную процедуру с таким же поведением. Все вызовы сериализатора порождают сериализованные процедуры, принадлежащиеодному множеству.Таким образом, в отличие от предыдущего примера, выполнение(define x 10)(define s (make-serializer))(parallel-execute (s (lambda () (set! x (* x x))))(s (lambda () (set! x (+ x 1)))))может иметь только два результата, 101 и 121. Остальные возможности отбрасываются,поскольку выполнение P1 и P2 не может чередоваться.Ниже приведена версия процедуры make-account из раздела 3.1.1, в которой помещение денег на счет и снятие их со счета сериализованы:(define (make-account balance)(define (withdraw amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете"))(define (deposit amount)(set! balance (+ balance amount))balance)(let ((protected (make-serializer)))(define (dispatch m)(cond ((eq? m ’withdraw) (protected withdraw))((eq? m ’deposit) (protected deposit))((eq? m ’balance) balance)(else (error "Неизвестный запрос -- MAKE-ACCOUNT"m))))dispatch))290Глава 3.
Модульность, объекты и состояниеВ такой реализации два процесса не могут параллельно помещать деньги на счет илиснимать их. Таким образом устраняется источник ошибки, показанной на рис. 3.29, гдеПетр изменяет баланс на счете в промежутке между моментами, когда Павел считываетзначение баланса, и когда он производит присваивание.
С другой стороны, у каждогосчета свой собственный сериализатор, так что операции с различными счетами могутпроисходить параллельно.Упражнение 3.39.Какие из пяти возможных исходов параллельного выполнения сохраняются, если мы сериализуемвыполнение таким образом:(define x 10)(define s (make-serializer))(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))(s (lambda () (set! x (+ x 1)))))Упражнение 3.40.Укажите все возможные значения x при выполнении(define x 10)(parallel-execute (lambda () (set! x (* x x)))(lambda () (set! x (* x x x))))Какие из них сохраняются, если вместо этого мы выполняем сериализованные процедуры:(define x 10)(define s (make-serializer))(parallel-execute (s (lambda () (set! x (* x x))))(s (lambda () (set! x (* x x x)))))Упражнение 3.41.Бен Битобор считает, что лучше было бы реализовать банковский счет таким образом (измененнаястрока отмечена комментарием):(define (make-account balance)(define (withdraw amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете"))(define (deposit amount)(set! balance (+ balance amount))balance)(let ((protected (make-serializer)))(define (dispatch m)(cond ((eq? m ’withdraw) (protected withdraw))((eq? m ’deposit) (protected deposit))((eq? m ’balance)((protected (lambda () balance)))) ; сериализовано(else (error "Неизвестный запрос -- MAKE-ACCOUNT"m))))dispatch))3.4.
Параллелизм: время имеет значение291поскольку несериализованный доступ к банковскому счету может привести к неправильному поведению. Вы согласны? Существует ли сценарий, который демонстрирует обоснованность беспокойства Бена?Упражнение 3.42.Бен Битобор говорит, что слишком расточительно в ответ на каждое сообщение withdraw иdeposit создавать по новой сериализованной процедуре. Он говорит, что можно изменить makeaccount так, чтобы все вызовы protected происходили вне процедуры dispatch. Таким образом, счет будет возвращать одну и ту же сериализованную процедуру (созданную тогда же, когдаи сам счет) каждый раз, когда у него просят процедуру снятия денег:(define (make-account balance)(define (withdraw amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете"))(define (deposit amount)(set! balance (+ balance amount))balance)(let ((protected (make-serializer)))(let ((protected-withdraw (protected withdraw))(protected-deposit (protected deposit)))(define (dispatch m)(cond ((eq? m ’withdraw) protected-withdraw)((eq? m ’deposit) protected-deposit)((eq? m ’balance) balance)(else (error "Неизвестный запрос -- MAKE-ACCOUNT"m))))dispatch)))Безопасно ли такое изменение? В частности, есть ли разница в том, в каком порядке можетпроисходить параллельное выполнение в этих двух версиях make-account?Сложности при использовании множественных разделяемых ресурсовСериализаторы предоставляют нам мощную абстракцию, которая позволяет изолировать сложности выполнения параллельных программ, так что мы получаем возможностьработать с ними аккуратно (и, будем надеяться, без ошибок).
Однако, хотя при работетолько с одним разделяемым ресурсом (например, с одним банковским счетом) использовать сериализаторы относительно просто, при наличии множественных разделяемыхресурсов параллельное программирование может быть предательски сложным.Чтобы проиллюстрировать одну из ряда трудностей, которые могут возникнуть, предположим, что нам требуется поменять местами балансы на двух банковских счетах. Мычитаем каждый счет, чтобы узнать баланс, вычисляем разницу между балансами, снимаем ее с одного счета и кладем на другой. Это можно реализовать следующим образом41 :41 Мы упростили exchange, пользуясь тем, что наше сообщение deposit может принимать отрицательныесуммы. (Для банковской системы это серьезная ошибка!)292Глава 3. Модульность, объекты и состояние(define (exchange account1 account2)(let ((difference (- (account1 ’balance)(account2 ’balance))))((account1 ’withdraw) difference)((account2 ’deposit) difference)))Эта процедура работает правильно в том случае, когда только один процесс пытаетсяосуществить обмен.
Допустим, однако, что Петр и Павел имеют доступ к совместнымсчетам a1, a2 и a3, и что Петр меняет местами a1 и a2, а Павел в то же время обмениваетa1 и a3. Даже если снятие и занесение денег на отдельные счета сериализованы (какв процедуре make-account из предыдущего раздела), exchange может привести кневерным результатам.
Например, может оказаться, что Петр посчитает разницу междуa1 и a2, но Павел изменит баланс на a1 прежде, чем Петр закончит обмен42 . Чтобыдобиться правильного поведения, мы должны устроить так, чтобы процедура exchangeблокировала всякий параллельный доступ к счетам на все время обмена.Один из способов этого достичь — сериализовать всю процедуру exchange сериализаторами обоих счетов. Ради этого мы откроем доступ к сериализаторам счетов.
Обратите внимание, что, раскрывая сериализатор, мы намеренно ломаем модульное построениеобъекта-банковского счета. Следующая версия процедуры make-account идентичнаисходной версии из раздела 3.1.1, за исключением того, что имеется сериализатор длязащиты переменной баланса, и он экспортируется через передачу сообщений:(define (make-account-and-serializer balance)(define (withdraw amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете"))(define (deposit amount)(set! balance (+ balance amount))balance)(let ((balance-serializer (make-serializer)))(define (dispatch m)(cond ((eq? m ’withdraw) withdraw)((eq? m ’deposit) deposit)((eq? m ’balance) balance)((eq? m ’serializer) balance-serializer)(else (error "Неизвестный запрос -- MAKE-ACCOUNT"m))))dispatch))С помощью этой версии мы можем выполнять сериализованное занесение и снятиеденег.
Заметим, однако, что, в отличие от предыдущей версии сериализованного счета,теперь каждый пользователь объектов-банковских счетов должен явным образом управлять сериализацией, например, так43 :42 Если балансы на счетах вначале равны 10, 20 и 30 долларам, то после любого количества параллельных обменов балансы должны по прежнему быть 10, 20 и 30, в каком-то порядке. Сериализации доступа котдельным счетам недостаточно, чтобы это гарантировать. См. упр.
3.43.43 В упражнении 3.45 рассматривается вопрос, почему занесение и снятие денег теперь не сериализуются3.4. Параллелизм: время имеет значение293(define (deposit account amount)(let ((s (account ’serializer))(d (account ’deposit)))((s d) amount)))Экспорт сериализатора дает нам достаточно гибкости, чтобы реализовать сериализованную программу обмена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
